1

Amplifying Inter-message Distance: On
Information Divergence Measures in Big Data

arXiv:1709.03690v1 [] 12 Sep 2017

Rui She, Shanyun Liu, and Pingyi Fan, Senior Member, IEEE

Abstract
Message identification (M-I) divergence is an important measure of the information distance between
probability distributions, similar to Kullback-Leibler (K-L) and Renyi divergence. In fact, M-I divergence
with a variable parameter can make an effect on characterization of distinction between two distributions.
Furthermore, by choosing an appropriate parameter of M-I divergence, it is possible to amplify the information distance between adjacent distributions while maintaining enough gap between two nonadjacent
ones. Therefore, M-I divergence can play a vital role in distinguishing distributions more clearly. In this
paper, we first define a parametric M-I divergence in the view of information theory and then present its
major properties. In addition, we design a M-I divergence estimation algorithm by means of the ensemble
estimator of the proposed weight kernel estimators, which can improve the convergence of mean squared
error from O(Γ −j/d ) to O(Γ −1 ) (j ∈ (0, d]). We also discuss the decision with M-I divergence for
clustering or classification, and investigate its performance in a statistical sequence model of big data
for the outlier detection problem.
Index Terms
Message Identification (M-I) Divergence, Discrete Distribution Estimation, Divergence Estimation,
Big Data Analysis, Outlier Detection

I. I NTRODUCTION
In the big data era, the amount of data from many kinds of areas is exploding greatly, and how
to analyze the collected big data attracts more and more attention. For big data analysis, there are
a series of relevant technologies including machine learning, pattern recognition, statistics, estimation
This work was supported by the China Major State Basic Research Development Program (973 Program)
No.2012CB316100(2), National Natural Science Foundation of China (NSFC) No. 61771283 and China Scholarship Council.
R. She, S. Liu, and P. Fan are with the Department of Electronic Engineering, Tsinghua University, Beijing, GA 30332 China
(e-mail: sher15@mails.tsinghua.edu.cn; liushany16@mails.tsinghua.edu.cn; fpy@tsinghua.edu.cn).

2

theory and so on. As an essential element in machine learning, the information divergence can be used
to deal with distribution problems by mapping the relationship between two probability distributions to
nonnegative values. Currently, information divergences have been extended for nonnegative tensors and
used to minimize the approximation error between the observed data and its model [1]. Additionally,
typical applications of information divergences also include faulty detection [2], key frame selection [3],
image and speech recognition [4], [?] and so on.
In the framework of the combination of information theory and big data analysis, information divergences were investigated as measures to handle the learning problem about distributions. In particular, the
relative entropy as a special case of K-L divergence is a superior tool of measuring information distance in
some applications such as anomaly detection [6], FMRI data processing [?], clustering and classification
[8]. Moreover, Shannon entropy can be also regarded as a special case of K-L divergence with an
uniform distribution. It is appropriate for entropy to be applied to intrinsic dimension estimation [9],
texture classification and image registration [10]. In addition, information divergences can be applicable
to extending methods of machine learning to distributional features [11].
Although there are a great deal of available information divergences, little research is investigated on
how to select a better one for a certain application to big data. Due to the different properties of different
divergences, this issue is a significant work for information divergences used in big data analysis. Besides,
another factor which can contribute to the issue is that a divergence-based estimation may depend on
the selected divergence in a given task. Then we can see that it is flexible for information divergences
to cope with different data learning tasks. For example, Euclidean distance has superior performance
on handling data with Gaussian noise; K-L divergence is suitable for topic collection of text documents
[12]; Itakura-Saito divergence can perform well on audio signal processing [13]; as well as the MIM and
non-parametric MIM which are similar to entropy, can be proven suitable for minority subset detection
[14]–[16]. In addition, the information distance between given distributions can be also as a factor to make
an effect on the divergence selection. Some divergences may not distinguish certain similar distributions
due to the confusion between information distance and the statistical error.
In this paper, to study the information divergence as a measure in big data application, we will focus
on the information distance measured by different divergences. As well, it is necessary to investigate the
more efficient divergence estimation for practical applications or models. Before our work, let us review
some typical information divergences first.

3

A. Information Divergence measures
There exist many different kinds of information divergences, which can play a vital role in the fields
of information theory, statistics and big data analysis. To simply summarize a variety of information
divergences, we focus on the most commonly used ones including K-L divergence, Renyi divergence and
α-, β - or γ -divergences [17]–[19], which belong to broader ones such as the f-divergences or Bregman

divergences [20].
For two finite discrete distributions P = (p1 , p2 , ..., pn ) and Q = (q1 , q2 , ..., qn ), the definitions of the
popularly used divergences and some of their special cases or relationships are given below.
a). K-L divergence is defined as
D(P k Q) =

b). Renyi divergence of order α is defined as
Dα (P k Q) =

X

pi log(

i

pi
).
qi

(1)

X
1
log
pαi qi1−α ,
α−1

(2)

i

where 0 < α < ∞, and α 6= 1. Notes that in the case of α → 1, Renyi divergence converges to K-L
divergence.
c). α-divergence is defined as
D

(α)

(P k Q) =

P

α 1−α
i pi q i

− αpi + (α − 1)qi
,
α(α − 1)

(3)

where α → 1, α = 2, α = −1 and α = 1/2 denote K-L, Pearson Chi-square, inverse Pearson and double
Hellinger distances, respectively.
d). β -divergence is defined as
D

(β)

(P k Q) =

P

β+1
i pi

(β+1)

− (β + 1)pi qiβ
+ βqi
,
β(β + 1)

(4)

where β = 1 and β → −1 denote the Euclidean distance and Itakura-Saito divergence, respectively.
e). γ -divergence is defined as
D (γ) (P k Q)
h
X γ+1
X γ+1
X γ i
1
log(
pi ) + γ log(
qi ) − (γ + 1) log(
pi q i ) ,
=
γ(γ + 1)
i

i

(5)

i

where K-L divergence becomes its special case if γ → 0.

However, there may be also situations where the commonly used divergences can not work well. To
this end, we introduce a new divergence different from the above divergences as follows.

4

B. Message Identification Divergence
In this subsection, we shall introduce a new parametric information identification measure, which is
referred to as the message identification divergence (M-I divergence).
Definition 1. For two given probability distributions with a same finite alphabet, P = (p1 , p2 , ..., pn )
and Q = (q1 , q2 , ..., qn ), the M-I divergence with parameter ̟ is defined as
DM I (P k Q, ̟) = D̟ (P k Q) = log

where ̟ > 0 is an adjustable identification parameter.

n
X



pi e

p

̟ qi
i



i=1

− ̟,

(6)

Note that the larger parameter ̟ is, the larger contribution the information distance elements pi /qi
have to M-I divergence. In the application, it is necessary to set an appropriate ̟ which is not too large
to compute easily.
C. Organization
The rest of this paper is organized as follows. In Section II, we discuss some major properties
of M-I divergence, such as its monotonicity, convexity and inequality. In Section III, we propose a
multidimensional kernel estimator with the weight window, which can be adapted to estimate a discrete
distribution. As well, we discuss its performance in the mean squared error (MSE) criterion. Then
an ensemble estimator for M-I divergence is also proposed by use of some weighted-window kernel
estimators. Section IV discuss how to use M-I divergence in big data analysis and apply it to a proposed
outlier detection model. Besides, some simulations are also presented to check our theoretical results.
Finally, we conclude the paper in Section V.
II. T HE P ROPERTIES

OF

M-I D IVERGENCE

In this section, some dominant properties of M-I divergence is investigated in details.

A. The Non-negative Property
Proposition 1. The M-I divergence D̟ (P k Q) with ̟ > 0 is non-negative for any probability P and
Q, namely
D̟ (P k Q) ≥ 0.

(7)

Proof:. Define f (x) = exp (̟x−1 ) with ̟ > 0. It is readily seen that the second order derivative

2
−1
f (x)
of f (x) with respect to x is positive, namely, ∂ ∂x
= ̟2 x−4 + 2̟x−3 e̟x > 0. Then, we know
2

5

that f (x) is a convex function for x ∈ R. According to Jensen’s inequality and the concavity of function
log(x), we have
D̟ (P k Q) = log

n
X

P
qi
−1
̟( n
i=1 pi ( p ))

p

̟ qi

pi e

i

i=1

− ̟ ≥ log e

i

− ̟ = log e̟ − ̟ = 0.

(8)

In particular, the equality holds if and only if pi = qi (i ∈ {1, 2, ..., n}).
B. Monotonicity
Proposition 2. For the identification parameter ̟ ∈ (0, +∞), the M-I divergence D̟ (P k Q) is
nondecreasing in ̟.
Proof:. By using the definition of M-I divergence and dividing its support set of i into two parts, it is
readily seen that the partial derivative of D̟ (P ||Q) with respect to ̟ satisfies

  pi 
P
̟q
pi
i
q i − 1 pi e
S
∂D̟ (P k Q)
i∈{i:pi ≥qi } {i:pi <qi }


=
p
P
∂̟
̟ qi
i
i pi e
(9)




P
P


pi
pi
̟
̟
P
q i − 1 pi e
q i − 1 pi e
e̟ i pqii − 1 pi
i∈{i:pi ≥qi }
i∈{i:pi <qi }






≥
+
=
.
p
p
p
P
P
P
̟ qi
̟ qi
̟ qi
i
i
i
i pi e
i pi e
i pi e
P qi −1
P pi
̟
̟
−1]. Thus,
According to Jensen’s inequality, it is readily seen that e
i ( qi − 1)pi ≥ e [( i pi pi )
it can be readily verified that

∂D̟ (P k Q)
≥
∂̟

e̟


P

−1
qi
−
i pi p i


p
P
̟ qi
i
p
e
i
i


1

= 0,

(10)

which means D̟ (P k Q) is monotonically nondecreasing in ̟ and the property is proved.
Remark 1. If and only if pi = qi (i ∈ {1, 2, ..., n}), M-I divergence D̟ (P k Q) remains zero with
increasing ̟. In other cases (pi 6= qi ), D̟ (P k Q) is increasing in ̟. According to this property, it
can be apparently deduced that ̟ is an adjustable parameter for M-I divergence to amplify the distance
between different probability distributions.
C. The Convexity Property
Proposition 3. For any ̟ > 0, M-I divergence D̟ (P k Q) is jointly convex in the case of exponential
function. That is, for two given pairs of probability distributions (P0 , Q0 ) and (P1 , Q1 ) without zero
elements, and any 0 < λ < 1, we have
(1 − λ) eD̟ (P0 kQ0 ) + λeD̟ (P1 kQ1 ) ≥ eD̟ (Pλ kQλ ) ,

(11)

6

where Pλ = (1 − λ)P0 + λP1 and Qλ = (1 − λ)Q0 + λQ1 .
Proof:. Define f (x) = xe̟x with ̟ > 0 and x ∈ R. It is easy to see that the first order and the
second order derivative of f (x) are both positive for ̟ > 0 and x > 0. Then, it is evident that f (x) is
convex for ̟ > 0 and x > 0. By using Jensen’s inequality, in the case of ̟ > 0, we have
  p0,i 
  p1,i 


̟ q
̟
λq
(1 − λ)q0,i p0,i
p
1,i
1,i
0,i
+
e
e q1,i
qλ,i
q0,i
qλ,i q1,i

  pλ,i 
̟
pλ,i
≥
e qλ,i ,
qλ,i

(12)

where pλ,i = (1 − λ)p0,i + λp1,i and qλ,i = (1 − λ)q0,i + λq1,i , as well as, pm,i and qm,i (m = 0, 1, λ; i =
0, 1, ..., n) are any elements in Pm and Qm (m = 0, 1, λ), respectively.

Then, for all elements of probability distributions Pm and Qm (m = 0, 1, λ), we have
(1 − λ)

X

̟

p0,i e



p0,i
q0,i



i

for any ̟ > 0, which proves the property.

+λ

X

̟

p1,i e



p1,i
q1,i

i



≥

X

̟

pλ,i e



pλ,i
qλ,i



,

(13)

i

Corollary 1. For any two pairs of probability distributions (P0 , Q0 ) and (P1 , Q1 ) without zero elements,
and any λ ∈ (0, 1), we have
max{D̟ (P0 k Q0 ), D̟ (P1 k Q1 )} ≥ D̟ (Pλ k Qλ ),

(14)

where Pλ = (1 − λ)P0 + λP1 and Qλ = (1 − λ)Q0 + λQ1 .
Proof: . In view of the convexity property of M-I divergence D̟ (P k Q), in the case of exponential
function, we have
(1 − λ) max{eD̟ (P0 kQ0 ) , eD̟ (P1 kQ1 ) } + λ max{eD̟ (P0 kQ0 ) , eD̟ (P1 kQ1 ) } ≥ eD̟ (Pλ kQλ ) .

(15)

As a result, it can be easily seen that
max{eD̟ (P0 kQ0 ) , eD̟ (P1 kQ1 ) } ≥ eD̟ (Pλ kQλ ) .

(16)

Further, we can gain this corollary by use of the monotonicity of exponential function.
Corollary 2. For any probability distributions P , Q0 and Q1 which consist of positive elements, and
λ ∈ (0, 1), we have,
(1 − λ) eD̟ (P kQ0 ) + λeD̟ (P kQ1 ) ≥ eD̟ (P k(1−λ)Q0 +λQ1 ) .

This can be verified by substituting p for p0 and p1 in the convexity property.

(17)

7

D. The Inequality Property
Proposition 4. For two given probability distributions with the finite support set, P = (p1 , p2 , ..., pn ) and
Q = (q1 , q2 , ..., qn ) (pi > 0, qi > 0, i = 1, 2, ..., n), the relationship among M-I divergence D̟ (P k Q),

K-L divergence D(P k Q) and Renyi divergence Dα (P k Q) can be indicated as
(18)

D̟ (P k Q) ≥ D(P k Q) ≥ Dα (P k Q),

where ̟ ≥ 1 and α ∈ [0, 1].
Proof: . Define a function f (x) = e̟(x−1) − x with ̟ > 0 and x ∈ (0, +∞). By setting
it can be readily testified that the minimum of f (x) is obtained at x0 = 1 +
1
̟ (1

is not difficult to see that only when ̟ = 1, can f (x0 , ̟) =

1
̟

∂f (x)
∂x

= 0,

1
log ̟
. Furthermore, it

+ log ̟) − 1 reach the maximum

f (x0 , ̟ = 1) = 0. Therefore, it is clear to see that
f (x) = e̟(x−1) − x ≥ 0,

(19)

where ̟ = 1, x ∈ (0, +∞) and f (x) = 0 for x = 1.
Now, the proof of left hand side inequality in Eq. (18) can be cast into the proof of D̟ (P k Q) ≥
D(P k Q) with ̟ = 1. This is due to the monotonicity of D̟ (P k Q) in Proposition 2.

By averaging f ( pqii ) in the distribution P = (p1 , p2 , ...., pn ) and considering the concavity of logarithmic
p
P
P
̟( i −1)
− log i pi pqii ≥ 0, with ̟ = 1. As well, in virtue of Jensen’s
function, we have log i pi e qi
inequality, it is apparent that

log

X

p

̟( qi −1)

pi e

i

i

−

X
i

pi log

pi
≥ 0,
qi

(20)

which implies that D̟ (P k Q) ≥ D(P k Q) does work for ̟ ≥ 1 due to the monotonicity of M-I
divergence.
Furthermore, Dα (P k Q) keeps increasing in the order of α, mentioned in Theorem 3 of [21].
Correspondingly, we have
D(P k Q) = sup Dα (P k Q).
0<α<1

(21)

Therefore, by combining Eq. (20) and Eq. (21), the inequality property of D̟ (P k Q) can be proved
readily.
Remark 2. According to the inequality property, the distance between two adjacent distributions can be
amplified by the measure of M-I divergence. Moreover, M-I divergence is more sensitive than the other
divergences to measure the distance between two nonadjacent distributions. Thus, it is more efficient for
M-I divergence to distinguish two distributions.

8

III. E STIMATION

OF

M-I D IVERGENCE

A. The Multidimensional Discrete Kernel Estimator
1) Multidimensional Kernel with Weight Window:
With regard to the discrete kernel, there is a general definition to characterize it specifically according
to [22] as follows.
Definition 2. Let S be the finite support of the unknown probability mass function (p.m.f), to be estimated,
with xi an element in S. A p.m.f Kxi ,s (·) on support Sx (not depending on s) is regard as a discrete
kernel with the parameter s > 0, if it satisfies the following conditions:
xi ∈ S x ,

(22a)

lim E(Zxi ,s ) = xi ,

(22b)

lim Var(Zxi ,s ) = 0,

(22c)

s→0
s→0

where Zxi ,s is a discrete random variable with p.m.f Kxi ,s (·).
Based on the above characteristics of the discrete kernel, some special kernel functions can be designed
in various ways. As well, we present a kernel estimator with the weight window for multidimensional
discrete distribution as follow.
Definition 3. Let X1 , X2 , ..., XN be independent and identically distributed (i.i.d) multidimensional
random variables with d-dimensional multivariate p.m.f p(xi ) on finite support U = [a1 , a2 , ..., aL ]d . A
discrete kernel estimator pes (xi ) with a weight window is defined as
pes (xi ) =

N
N
1 X
1 XX
W (s, xi , xj )I{Xk =xj } , xi,j ∈ U,
Kxi ,s,d̃ (Xk ) =
N
N
k=1

(23)

k=1 xj ∈U

in which the weight window function is

W (s, xi , xj ) =



1 − s,





s


(2d˜ + 1)d − 1





0,

|xui − xuj | = 0
, 0 < |xui − xuj | ≤ d˜ ,

(24)

|xui − xuj | > d˜

where u ∈ {1, 2, ..., d} denotes the dimension order, s is a smoothing parameter, the window size d˜ is
the distance of support indexes between xi and xj in every dimension, L is the size of support indexes
in every dimension, I{Xk =xj } is the indicator function and Kxi ,s,d̃ is the kernel function with 0 ≤ s < 1,

xi ∈ U and d˜ <

L−1
2 .

9

From the above definition of multidimensional kernel estimator with the weight window, it can be
clearly noted that when the smoothing parameter (or weight parameter) satisfies s = 0, the discrete
weight window function W (s, xi , xj ) degenerates into the indicator function I{xi =xj } . As well, it is
readily seen that regardless of weight parameter s or variable xi , the sum of W (s, xi , xj ) for all xj ∈
˜ xj ∈ U} fulfills
{xj : 0 ≤ |xui − xuj | ≤ d,

X

W (s, xi , xj ) = 1.

(25)

xj ∈U

Remark 3. As far as the kernel estimator pes (xi ) is concerned, it is the core idea that relative frequencies
derived from plug-in estimator are weighted to constitute the p.m.f estimator. In this way, more information
of samples can be made use of to estimate every probability element in p.m.f. Furthermore, it is implied
that the performance of the estimator pes (xi ) mainly depends on the selection of weight parameter in

the case of the given p.m.f and known samples. In addition, if the weight parameter s tends to zero as
N → +∞, the estimator pes (xi ) will tend to the real p(xi ).

2) Selection of Kernel Weight Parameter:

We now consider selecting the weight parameter s, which can make an effect on the performance of
kernel estimator. In general, the mean squared error (MSE) is accepted as a performance criterion for
estimators. For a given d-dimensional multivariate p.m.f p(xi ) and its kernel estimator pes (xi ), the MSE

can be treated as a function of s as follows,
fMSE (s)
X
=E
[pes (xi ) − p(xi )]2
xi ∈U

=

X

xi ∈U

=
+

P

Var [pes (xi )] +

xi ∈U

X

xi ∈U




P

X

xj ∈U W

xj ∈U

X

xi ∈U

2 (s, x

N

Bias2 [pes (xi )]

i , xj )p(xj )

−

P

2

xi ∈U

hP

i2
W
(s,
x
,
x
)p(x
)
i
j
j
xj ∈U

(26)

N

W (s, xi , xj )p(xj ) − p(xi ) .

What is more, it is readily realized that a value of s can be provided by minimizing the MSE with
respect to s. In that case, the optimal weight parameter is given by
s0 = arg min fMSE (s).
0≤s<1

(27)

10

By substituting Eq. (24) into Eq. (26), we have
)
(
P
P
N p(xi ) xj ∈Vd̃ p(xj )
1 − xi ∈U p2 (xi )
2 X
2
fMSE (s) =
s
p (xi ) − p(xi ) −
+
˜ + 1)d − 1
N
N
(2
d
xi ∈U
hP
i2
P
(
p(x
)
+
(N
−
1)
p(x
)
X
j
j
xj ∈Vd̃
xj ∈Vd̃
1
+
(N − 1)p2 (xi ) + p(xi ) +
h
i2
N
xi ∈U
(2d˜ + 1)d − 1
)
P
2(N − 1)p(xi ) xj ∈Vd̃ p(xj ) 2
−
s ,
(2d˜ + 1)d − 1

(28)

˜ x̃j ∈ U}.
where the set Vd˜ denotes {x̃j : 0 < |x̃uj − xui | ≤ d,

By setting

∂fMSE (s)
∂s

= 0, we can gain the minimum value of fMSE (s). Therefore, it is readily seen that

the optimal weight parameter is
s0 =

1−

P

xi ∈U

p2 (x

i)

+

P

xi ∈U

P

xj ∈V

d̃

p(xi )p(xj )

d −1
˜
(2d+1)

˜
Φ(p, N, d)

,

(29)

where the denominator is a function of p, N , and d˜, as
˜
Φ(p, N, d)
P
=1+

P

xj ∈Vd̃ p(xj )
h
i2
(2d˜ + 1)d − 1
xi ∈U

(

+ (N − 1)

X

p2 (xi ) +

xi ∈U

(30)
hP

i2
)
P
P
p(x
)
j
2 xi ∈U xj ∈Vd̃ p(xi )p(xj )
xj ∈Vd̃
xi ∈U
−
.
h
i2
(2d˜ + 1)d − 1
(2d˜ + 1)d − 1

P

It is worth noting that the optimal weight parameter s0 depends on the p.m.f p(xi ), the number of
multidimensional random variables N and the distance d˜. However, the p.m.f is hardly known and needs
estimating. For this reason, it can be thought over to replace the unknown p(xi ) with a consistent estimator,
plug-in estimator p̂(xi ). In that case, the suboptimal but practical solution ŝ0 of weight parameter under
the MSE criterion is put forward as
ŝ0 =

1−

P

2
xi ∈U p̂ (xi ) +

P

xi ∈U

˜
Φ(p̂, N, d)

P

xj ∈V

d̃

p̂(xi )p̂(xj )

d −1
˜
(2d+1)

.

(31)

Remark 4. For a given p.m.f p(xi ) and d˜, it is readily seen that the suboptimal weight parameter satisfies
ŝ0 = O(1/N ), which is similar to the optimal s0 . Moreover, if the weight parameter s is replaced by ŝ0 ,
fMSE (ŝ0 ) will tend to zero as N → +∞. That is, the estimator peŝ0 (xi ) tends to the real p(xi ) in the

MSE criterion.

11

3) Performance Analysis:
In the view of MSE criterion, the multidimensional window kernel estimator peŝ0 (xi ) keeps the same

large-sample properties as plug-in estimator p̂(xi ). However, it arises a question whether the former is

superior to the latter in the performance of estimation. In order to distinguish which one is better, the
measurements of MSE with respect to peŝ0 (xi ) and p̂(xi ) are given respectively by
MSE (peŝ0 ) = fMSE (ŝ0 ),
o
nX
MSE (p̂) = E
[p̂(xi ) − p(xi )]2 .

(32)

xi ∈U

P
Considering the definition of plug-in estimator, p̂(xi ) = N1 N
k=1 I{Xk =xi } , we have
X 

E p̂2 (xi ) − p2 (xi )
MSE (p̂) =
xi ∈U


X  p(xi ) + (N − 1)p2 (xi )
2
=
− p (xi )
N
xi ∈U
P
1 − xi ∈U p2 (xi )
=
.
N
By replacing s with ŝ0 in Eq. (28), the difference of the two MSE functions can be written as
˜ 0 + ψ(p̂, N, d)ŝ
˜ 2,
MSE (peŝ0 ) − MSE (p̂) = φ(p̂, N, d)ŝ
0

(33)

(34)

˜ and ψ(p̂, N, d)
˜ are both functions of p, N and d˜. What is more, it is apparent that the
where φ(p̂, N, d)
˜ and ψ(p̂, N, d)
˜ are O(1) + O(1/N ).
convergence of φ(p̂, N, d)
˜ 2 = O(ŝ2 ) tends to zero at a
Due to the fact that the parameter ŝ0 → 0 as N → +∞, the ψ(p̂, N, d)ŝ
0
0

˜ 0 , as N increasing. That is, the first term φ(p̂, N, d)ŝ
˜ 0 dominates the positive
faster rate than φ(p̂, N, d)ŝ
˜ < 0 always holds by
or negative nature of Eq. (34). In addition, it is not difficult to know that φ(p̂, N, d)

virtue of p2 (xi ) − p(xi ) ≤ 0 in the second term of Eq. (28). Therefore, it is sure that for large enough N ,
MSE(peŝ0 ) < MSE(p̂) holds for any p.m.f (p(xi ) 6= 0). This implies that peŝ0 (xi ) has better performance

than p̂(xi ) in the MSE criterion.

B. Multidimensional Weighted Ensemble Estimation
For an ensemble of estimators {D̂l1 , D̂l2 , ..., D̂lT } of a parameter D , the weighted ensemble estimator
with respect to the weight λ = {λl1 , λl2 , ..., λlT } is defined as
X
D̂λ =
λl D̂l ,

(35)

l∈l̄

where the ¯l = {l1 , l2 , ..., lT } denotes an index set. As well, the ensemble of weights is constrained by
P
l∈l̄ λl = 1, which can ensure that the weighted ensemble estimator D̂λ holds asymptotically unbiased

in the case of the asymptotically unbiased estimators {D̂l1 , D̂l2 , ..., D̂lT }.

12

Theorem 1. Assume the bias and variance of every estimator D̂l (l ∈ ¯l) satisfy the following conditions,
respectively:
Bias(D̂l ) =

X

γj ϕj (l)Γ −j/2d + ρbias (Γ −1/2 ),

(36a)

j∈J

Var(D̂l ) = ρvar (Γ −1/2 ),

(36b)

where γj are constants depending on a d-dimensional p.m.f p(xi ), d is the dimension number, J = {ji :
0 < ji ≤ d, 1 ≤ i ≤ I and I ≤ T − 1} denotes an index set, Γ is the number of samples, ϕj (l)

are independent functions of index l, and ρτ (Γ −1/2 ) with any subscript τ are functions of Γ −1/2 . Then,
there exists a weight vector λ∗ leading to
i
h
MSE(D̂λ∗ ) = E (D̂λ∗ − D)2 ≤ ρλ∗ (Γ −1/2 ).

(37)

The weight vector λ∗ is given by solving the following optimization problem:
λ∗ = arg min : ||λ||2
λ
X


λl = 1,



l∈l̄
s.t. X



λl ϕj (l) = 0, j ∈ J.



(38)

l∈l̄

Proof:. For the ensemble of estimators {D̂l }l∈l̄ , the bias of the weighted ensemble estimator D̂λ is
given by
Bias(D̂λ ) = E

X
l∈l̄

=

XX

λl D̂l − D



γj λl ϕj (l)Γ

=

X

λl Bias(D̂l )

l∈l̄

−j/2d

+ ρλbias (Γ

(39)
−1/2

).

l∈l̄ j∈J

Considering the Cauchy-Schwartz inequality, it is not difficult to derive the variance of D̂λ as follows:
X
2 X
i2
X h
Var(D̂λ ) = E
λl [D̂l − E(D̂l )] ≤
λl 2
E D̂l − E(D̂l ) = ||λ||2 Var(D̂l ).
(40)
l∈l̄

l∈l̄

l∈l̄

According to the condition I ≤ T − 1, it is readily seen that there exists at least one solution for the

constraint conditions of Eq. (38). Thus, there is a solution to minimize ||λ||22 , which can reduce the bias

of the ensemble estimator to ρλbias (Γ −1/2 ) and limit the contribution of the variance. Then, the MSE of
ensemble estimator with respect to the optimal solution λ∗ can be derived as
MSE(D̂λ∗ ) = Bias2 (D̂λ∗ ) + Var(D̂λ∗ )
≤ ρ2λ∗ bias (Γ −1/2 ) + ||λ∗ ||2 ρλ∗ var (Γ −1/2 )
= ρλ∗ (Γ −1/2 ),

(41)

13

which can verify the theorem.
In addition, from Theorem 1, it is not difficult to derive the corollary 3 by replacing functions ρτ (·)
with order O(·) or o(·) as follows.
Corollary 3. For the bias and variance of the ensemble of estimators {D̂l }l∈l̄ , the following conditions
are satisfied as
Bias(D̂l ) =

X
j∈J



γj ϕj (l)Γ −j/2d + o Γ −1/2 ,

(42a)


Var(D̂l ) = O Γ −1 .

(42b)

Then, there exists a weight vector λ∗ given by Eq. (38), which can lead to

MSE(D̂λ∗ ) = O Γ −1 .

(43)

In order to obtain the above convergence rate of MSE, it is sufficient for
order O(Γ −1/2 ). Thus, the optimal weight vector can be determind as
λ∗ = arg min δ
λ
X

λl = 1,




l∈l̄


 X
s.t.
λl ϕj (l)Γ 1/2−j/2d ≤ δ,



l∈l̄





||λ||22 ≤ ǫ,

P

l∈l̄

λl ϕj (l)Γ −j/2d to be of

(44)
j ∈ J,

where the parameter ǫ is small enough.

Remark 5. For the weighted ensemble estimator, on the one hand, it possesses a distinctive superiority
that the MSE is endowed with faster convergence by using the weight vector to eliminate the higher
order bias terms. On the other hand, it is visible that the weighted estimator applies to the circumstance
where there are estimators with different indexes.

C. Ensemble Estimator for M-I Divergence
In this subsection, we focus on the estimation of M-I divergence between two d-dimensional multivariate distributions P and Q whose p.m.fs are p(xi ) and q(xi ) with the known finite support U =
[a1 , a2 , ..., aL ]d . In terms of the definition of M-I divergence, it is apparent that the estimator of M-I
p(xi )
P
̟
divergence depends on the estimator of F̟ (P k Q) = xi ∈U p(xi )e q(xi ) , which can be approximately

calculated by using the samples splitting approach as follows.

14

Assume that the i.i.d. random samples from P are divided into two parts {X1 , ..., XN } and {XN +1 , ...,
XN +M }. The latter part is used to estimate the p.m.f of P at the N points {X1 , ..., XN } by means of

the weighted-window kernel. Similarly, the weighted-window kernel estimator of the p.m.f of Q at the
N points {X1 , ..., XN } is calculated by use of the i.i.d. samples {Y1 , ..., YM } drawn from Q. Then the

estimator of F̟ (P k Q) can be written as
N
p
e (X )
1 X ̟ qeŝŝ0 (Xii )
F̂d˜ =
e 0
,
N

(45)

i=1

where peŝ0 and qeŝ0 are weighted-window kernel estimators with the distance d˜ mentioned in the subsection
III-A.

Theorem 2. The bias of the estimator F̂d˜ with weighted-window kernel is given by
X  K j/d
K
1
1
Bias(F̂d˜) =
bj
+o
+o
+O
,
M
M
K
M

(46)

j∈J

˜
d
˜
where K = [ (2d+1)
L ] M is a real number determined by d <

L−1
2

and the parameter bj are constants

depending on the distributions P and Q.
Theorem 3. The variance of the estimator F̂d˜ with weighted-window kernel is given by
1
Var(F̂d˜) = O
.
N

(47)

The proof of Theorem 2 and 3 are given in Appendix A and B.
√
For a positive T ≥ I + 1 and a positive real number set ¯l = {l1 , ..., lT }, let K = ∆ M , ∆ =
˜l +1) d √
] M , l ∈ ¯l, M = µΓ and N = (1 − µ)Γ with 0 < µ < 1. Note that the l indexes over the
[ (2dL

distance size d˜ for the weighted-window kernel estimator. Then, the ensemble estimator of F̂d˜ is given
by
F̂λ =

X

λl F̂d˜l ,

(48)

l∈l̄

where F̂d˜l denotes a F̂d˜ with an index l for different d˜.
From Theorem 2 and 3, it is readily seen that the biases and variances of the ensemble estimators
satisfy the conditions mentioned in Eq. (42a) when ϕj (l) = ∆j/d and J = {1, ..., d}. Therefore, it is

available to find the optimal λ∗ by using Corollary 3 so that we can improve the MSE convergence for
the estimation of F̟ (P ||Q). That is, we can make good use of the better estimator F̂λ∗ to obtain the
better estimator of M-I divergence as
D̟̂ (P k Q) = log F̂λ∗ − ̟.

(49)

15

In addition, it is easily to see that the MSE of D̟̂ (P k Q) is given by
MSE(D̟̂ (P k Q)) = O(Γ −1 ),

(50)

whose proof is given in Appendix C.
In order to summarize the above process more specifically, the ensemble estimator with weightedwindow kernel for M-I divergence is listed in Algorithm 1.
Algorithm 1 Optimally weighted ensemble estimator with window kernel for M-I divergence
Input: µ, ǫ, L, the distance set {d˜l : l ∈ ¯l} with the index set ¯l, samples set {Y1 , ..., YM } from distribution
Q, samples set {X1 , ..., XΓ } from distribution P , dimension d, the parameter ̟ of M-I divergence.

Output: The optimally weighted ensemble estimator D̟̂ .
1:
2:
3:
4:
5:
6:
7:
8:

M ← µΓ , N ← Γ − M

˜l +1) d √
] M , j ∈ {1, ..., d} and l ∈ ¯l.
calculate the λ∗ by use of Eq. (44) with ϕj (l) = ∆j/d , ∆ = [ (2dL

for all l ∈ ¯l do

d˜l ← choosing a distance by l ∈ ¯l

for all Xi ∈ {X1 , ..., XN } do
1 PN +M
p̂(Xi ) and q̂(Xi ) ← M
k=N +1 I{Xk =Xi } and

1
M

PM

k=1 I{Yk =Xi } ,

respectively.

smoothing parameters ŝ0 (p) and ŝ0 (q) ← using Eq. (31) with M , d˜l , p̂(Xi ) and q̂(Xi ).
peŝ0 (p) (Xi ) and qeŝ0 (q) (Xi ) ← make full use of ŝ0 (p), ŝ0 (q), p̂(Xi ) and q̂(Xi ) to calculate the

two weighted-window kernel estimators by adopting Eq. (23) in definition 3.

9:
10:

end for
F̂λl ←

1
N

PN

p
e

(Xi )

̟ qeŝ0 (p)(X

i=1 e

ŝ0 (q)

i)

end for
P
∗
12: F̂λ∗ ←
l∈l̄ λl F̂d˜l
11:

13:

D̟̂ ← log F̂λ∗ − ̟

IV. A PPLICATION

TO

B IG DATA A NALYSIS

In this section, we will discuss how to exploit divergence measures to classify or cluster the data
belonging to different distributions. In particular, we take into account the following detection problem
about outlier or minority sequences in a set of sequences.
A. The Model with Unknown Number of Outliers
Assume that among a number of sample sequences, there are an unknown number of outlier sequences
to be detected. The i.i.d. samples in the typical sequences are gained from a known distribution Pt , while

16

in the outlier sequences, the i.i.d. samples are taken from an unknown distribution Qf . In order to design
a test to detect the outlier sequences, it is necessary to construct a model applying to the problem.
Consider T0 independent sequences (T0 ≥ 3), each of which can be denoted by X (i) for i = 1, ..., T0 .
(i)

(i)

As well, each X (i) consists of Γ0 i.i.d samples {X1 , ..., XΓ0 } drawn from either a typical distribution

Pt or an unknown outlier distribution Qf . It notes that there may exist k0 numbers of outlier sequences,
(i)

where the integer k0 ∈ [0, T20 ) is uncertain. As well, the notation Xk denotes the k-th sample in the i-th
sequence. Furthermore, by comparing the empirical typical distribution P̂t with the distribution estimation
P̂ (X (i) ) for every X (i) , we have the following test as


 F(P̂ti ; P̂t ),
(i)
F(P̂ (X ); P̂t ) →

 F(Q̂f ; P̂t ),
i

X (i) ∈ Mt
X

(i)

,

(51)

∈ Mf

where F(f1 ; f2 ) denotes a measurement between two distribution f1 and f2 , P̂ti and Q̂fi are estimations
with respect to Pt and Qf , Mt and Mf denote the typical sequences set and the outlier sequences set,
respectively.
In practice, our sequence model for outliers detection is applicable for the case in which the outlier
distributions Qf is unknown a priori, whereas the typical distribution Pt or at least the empirical
distribution P̂t is known. This is rational for many practical scenarios, in which systems regularly start
without any outliers and it is easy to possess sufficient information for Pt . In addition, the study of such
a model can apply to many applications, such as vacant channel detection in cognitive wireless networks,
fraud and anomaly detection in large data sets, state monitoring in sensor networks and so on.
B. Outlier Detection with Divergence Measures
Considering the performance of divergence measures on distinguishing different distributions, we can
use the information distances measured by divergences to detect the outliers in the above sequence model.
The method of outliers detection based on the sequence model is designed as following.
We make use of the i.i.d. samples to estimate the M-I divergence between a pending sequence and
the typical sequence. The M-I divergence estimation can be applicable to the outlier sequence model as
a measurement for clustering. Furthermore, a clustering algorithm such as k-means can be adopted to
distinguish the outlier sequences from the typical ones. The above process is more specifically summarized
in Algorithm 2. Similarly, it is feasible to design the outliers detection methods with other divergence

measures such as K-L divergence and Renyi divergence.
To demonstrate the divergence measures’ availability on outlier detection, we utilize the sequence model
with unknown number of outliers to characterize a kind of outlier detection scenario. As an example, we

1

1

0.8

0.8

Area under ROC

Ture Positive rate

17

0.6
ensemble D̟

0.4

kernel D̟
plug-in D

0.2

kernel D
kernel D

0.6
0.4
0.2

̟

α

0

0
0

0.2

0.4

0.6

0.8

1

False Positive rate

ensemble
D̟

(a) ROC curve of different divergences

plug-in
D̟

kernel
D̟

kernel
D

kernel
Dα

(b) AUC of different divergences

1

F-score

0.8
0.6
0.4
0.2
0

ensemble
D̟

plug-in
D̟

kernel
D̟

kernel
D

kernel
Dα

(c) F-score of different divergences
Fig. 1. Performance of different divergences in the example with each sequence size Γ0 = 6000, sequences number T0 = 200,
outlier sequences number k0 = 20 and the number of experiments NT0 = 100.

regard a binomial distribution B(n0 , pa ) as the typical distribution, in which the probability is denoted

as pti = Cni 0 pia (1 − pa )n0 −i with n0 = 11 and pa = 0.45. By contrast, the i.i.d. samples drawn from

another B(n0 , pb ) with pb = 0.445 are regarded as outliers. Then, we can randomly generate a set of
sample sequences, among which each sequence consists of Γ0 i.i.d samples drawn from either B(n0 , pa )
or B(n0 , pb ). In terms of the sequence model, our goal is to detect the k0 outlier sequences in the set of
T0 sequences.

In order to illustrate the performance of M-I divergence on outlier detection, we deal with the above
example by means of Algorithm 2. Besides, we also replace the ensemble estimator and M-I divergence
in that algorithm with other estimators and divergences to make comparisons, as shown in Fig. 1 and
Fig. 2. In our simulation, we choose the parameter µ = 1/2, ̟ = 1, ǫ = 3d and the distance set

18

0.9
0.85
ensemble D̟

Area under ROC curve

0.8

kernel D̟

0.75

plug-in D̟
kernel D
kernel Dα

0.7
0.65
0.6
0.55
0.5
0.45
0.4
0.6 0.8

1

1.2 1.4 1.6 1.8

2

2.2 2.4 2.6 2.8

Sample size of each sequence

Fig. 2.

3
4

×10

Means and variances of AUC with respect to different sample size in the example with sequences number T0 = 200,

outlier sequences number k0 = 20 and the number of experiments NT0 = 100.

Algorithm 2 Outlier Sequences Detection with M-I divergence
(i)

(i)

Input: Pending sequences {X1 , ..., XΓ0 } for i = 1, ..., T0 , the typical sequence {Y1 , ..., YΓ0 } obeying
a known empirical distribution P̂t , the parameter µ, ̟
Output: The results of the outlier detection, X (i) ∈ Mf
1:

Divide Γ0 into two parts: M0 ← µΓ0 (0 < µ < 1), N0 ← Γ0 − M0

2:

for all i ∈ [1, T0 ] do

3:

D̟̂,i (X (i) ||Y), D̟̂,i (Y||X (i) ) ← calculate the estimator of M-I divergence between {Y1 , ..., YM0 }
(i)

(i)

(i)

(i)

and {X1 , ..., XΓ0 } as well as the estimator of M-I divergence between {X1 , ..., XM0 } and
{Y1 , ..., YΓ0 } respectively, according to Algorithm 1.
4:

D̟̂,i ← {D̟̂,i (X (i) ||Y) + D̟̂,i (Y||X (i) )}/2

5:

end for

6:

Divide D̟̂,i into the normal set M̂t or the outlier set M̂f ← select a clustering algorithm such as
k-means.

7:

X (i) ∈ Mf ← D̟̂,i ∈ M̂f

{d˜l = l; l = 1, 2} for the weighted ensemble estimator of M-I divergence. As well, the weight window

is set to d˜ = 1 in kernel estimator, which is used to estimate the discrete distribution in K-L divergence,
Renyi divergence (with α = 1/2) and M-I divergence (with ̟ = 1).
From Fig. 1, it is seen that M-I divergence outperforms K-L divergence and Renyi divergence by using

19

the same estimator, which matches the inequality property well. Besides, this experiment shows that M-I
divergence performs better by using weighted ensemble estimator than other estimators, owing to the
convergence improvement. Moreover, due to the smaller reduction in the convergence term with large
samples, the kernel estimator is close to the ensemble estimator for M-I divergence.
The Fig. 2 shows that the result of outliers detection tends to be more precise as sample size increasing
for M-I and K-L divergence estimated by the ensemble or kernel estimator. However, that is not dramatically improved for Renyi and M-I divergence with plug-in estimator, which may result from the small
distinction between the typical distribution B(n0 , pa ) and the outlier distribution B(n0 , pb ). In short, it
still illustrates that M-I divergence can distinguish two closing distributions more clearly rather than K-L
divergence and Renyi divergence.
V. C ONCLUSION
In this paper, we investigated the information distance problem and proposed a parametric information
divergence, i.e., M-I divergence, which measures the distinction between two discrete distributions, similar
to K-L divergence and Renyi divergence. Furthermore, M-I divergence has its own dramatic properties
on amplifying the distance between adjacent distributions while maintaining enough gap between two
nonadjacent ones. This makes M-I divergence as a promising decision making tool for the statistical
big data analysis. We have investigated several fundamental properties of M-I divergence, and proposed
a multidimensional kernel estimator with a weight window to estimate probability distributions in MI divergence. Furthermore, we also presented a M-I divergence estimation algorithm by means of the
weighted ensemble estimator with the window kernel. In addition, we have investigated the performance
of M-I divergence on decision making of classification or clustering and applied it to design an algorithm
about the outlier detection problem. In the future, we plan to investigate a parameter selection method
for M-I divergence and design algorithms for other practical applications in big data.
A PPENDIX A
P ROOF
Define f (x) = e̟x

−1

OF

T HEOREM 2
qe (X)

q̄(X)
with ̟ > 0 and x > 0. Note that Bias(F̂d˜) = E[f ( peŝŝ0 (X) ) − f ( p̄(X)
)] +
0

qe (X)

q(X)
q̄(X)
) − f ( p(X)
)]. In order to find bounds for these terms, the Taylor series expansion of f ( peŝŝ0 (X) )
E[f ( p̄(X)
0

20

around

q̄(X)
p̄(X)

q̄(X)
and f ( p̄(X)
) around

f

f

where ξ̃X ∈
qeŝ0 (X)
peŝ0 (X)

−



q̄(X)
p̄(X)

q̄(X) qeŝ0 (X)
p̄(X) , peŝ0 (X)







q(X)
p(X)

are given by, respectively,


qeŝ0 (X)
peŝ0 (X)
q̄(X)
p̄(X)



=

=

2 f (i)
X
i=0

2 f (i)
X
i=0







q̄(X)
p̄(X)

i!

i!

and ȟ(X) denotes

q̄(xi ) =

Ûd,q
˜ (xi )
Vd˜

=

(52a)

ȟi (X)

(52b)

1
+ f (3) (ξ̌X )ȟ3 (X),
6

q(X) q̄(X)
p(X) , p̄(X) come
q̄ŝ0 (X)
q(X)
p̄ŝ0 (X) − p(X) . As well,

and ξ̌X ∈

h̃i (X)

1
+ f (3) (ξ̃X )h̃3 (X),
6


q(X)
p(X)





PM

from the mean value theorem, h̃(X) denotes
the q̄(xi ) is defined as

j=1 I{Yj ∈Ud̃,xi }

M Vd˜

(53)

,

u
u
˜
where xi ∈ U, and Vd˜ = (2d˜+ 1)d is the number of set Ud,x
˜ i = {xj : |xj − xi | ≤ d, xj ∈ U}. Similarly,

the p̄(xi ) can be calculated in the same way.
Lemma 1. Let a d-dimension variable X be a realization of p.m.f p independent of the window kernel
estimators qeŝ0 and peŝ0 . As well, p.m.f p and q are on the same support U = [a1 , ..., aL ]d . Then, for a

subscript z denoting p or q , we have
ẽz (X)
=

d
X
i=1

 K i/d
1 
K 
ĉ˜ez ,i,d̃ (X)
+O
,
+o
M
M
M

(54a)

E[ẽm
z (X)]
=

d
X
i=1

ĉem ,i,d̃
z

 K i/d
M

!m

1 
K 
+O
,
+o
M
M

(54b)

√
˜l +1) d √
where K = ∆ M with ∆ = [ (2dL
] M , ẽp (X) and ẽq (X) denote {p̃ŝ0 (X)− p̄(X)} and {q̃ŝ0 (X)−

q̄(X)} respectively, as well as, ĉem ,i,d˜(X) is a function of X and d˜, ĉem ,i,d˜ is a function of d.
z

z

21

Proof:. As far as ẽp (X) is concerned, it is easy to see
ẽp (X) = peŝ0 (X) − p̄(X)


N X
X
I{Xk ∈Ud̃,X } 
1
=
W (ŝ0 , X, xj )I{Xk =xj } −


N
Vd˜
k=1 xj ∈U


P
)
( xj ∈Ud̃,X I{Xk =xj }


N 
N


X
X
I{Xk ∈Ud̃,X }
1
1
xj 6=X
− I{Xk =X}
− ŝ0
I{Xk =X} −
=


N
Vd˜
Vd˜ − 1

 N k=1
k=1
Ûd,p
˜ (X)

= p̂(X) −

where Ûd,p
˜ (X) =

1
M

Vd˜

+ O(ŝ0 ),

(55)

PM

k=1 I{Xk ∈Ud̃,X } .

Assume that the continuous probability density function fˆp (x) has continuous partial derivatives of
order d. By use of Taylor series expansion, we can easily have the integral with respect to fˆp in the
integral range Bd,x
˜ as
Ûd,˜ fˆp (x) =

Z

fˆp (z)dz
Bd̃,x

= fˆp (x)Vd,˜ fˆp (x) +

where Vd,˜ fˆp (x) =

R

Bd̃,x

d
X
i=1

1+i/d
ĉi,d˜(x)V ˜ ˆ (x) +
d,fp

o



Vd,˜2fˆ (x)
p

˜
ˆ
dz is the volume of set Bd,x
˜ and ĉi,d˜ depends on d and fp .

(56)
,

u
u
u
Let the continuous set Bd,x
˜ = {x : x ∈ (xi−d−1
˜ , xi+d˜)} (u ∈ {1, ..., d} denotes u-th dimension)
R
u
u
˜
correspond to the discrete set Ud,x
dz =
˜ i = {xj : |xj − xi | ≤ d, xj ∈ U}, which means Vd,
˜ fˆp (x) = B
d̃,x

Vd˜. Then, fˆp (x) fulfills the following conditions,
 Z xi


fˆp (z)dz = p̂(xi )

xi−1

which implies that Ûd,˜ fˆp (xi ) =

R

Bd̃,xi

(57)



 fˆp (xi ) = p̂(xi ),

fˆp (z)dz = Ûd,p
˜ (xi ).

According to the Eq. (56), it is easy to see that the Ûd,p
˜ (X) can be expanded as ,
Z
fˆp (z)dz
Ûd,p
˜ (X) =
Bd̃,X

= p̂(X)Vd˜ +

d
X
i=1

where Vd˜ = (2d˜ + 1)d =

K d
ML .

1+i/d
ĉi,d˜(X)V ˜
d

 
+ o Vd˜2 ,

(58)

1
Considering Remark 4, namely ŝ0 = O( M
), and Eq. (55), it can be

readily seen that
ẽp (X) =

d
X
i=1

 K i/d
1
K 
ĉ˜ep ,i,d˜(X)
+O
.
+o
M
M
M

(59)

22

Furthermore, according to the binomial theorem, we have

Similarly, ẽq (X) and

E[ẽm
p (X)]
h X
d
 K i/d
 1 im 
K 
ĉ˜ep ,i,d˜(X)
=E
+O
+o
M
M
M
i=1
!
d
1 
K 
 K i/d m
X
+O
.
+o
ĉem ,i,d˜
=
p
M
M
M

i=1
n
E[ẽq (X)]

(60)

can also be derived. Therefore, it is apparent that Lemma 1 has been

testified.
Lemma 2. For a d-dimension variable X which denotes a realization of p.m.f p independent of the
window kernel estimators peŝ0 and qeŝ0 , we have
h̃(X) =

d
X
i=1

E[h̃t (X)] =

 K i/d
K
1 
ĉh,i,d˜(X)
+o
+O
,
M
M
M

d
X
i=1

where h̃(X) denotes
of X , d˜, p and q .

qeŝ0 (X)
peŝ0 (X)

Proof:. By expanding the
h̃(X)

ch̃t ,i,d̃

 K i/d
M

+o

K
1 
+O
,
M
M

(61a)

(61b)

q̄(X)
− p̄(X)
, ch̃t ,i,d˜ is a function of d˜, p and q , as well as, ĉh,i,d̃(X) is a function

qes0 (X)
pes0 (X) around

q̄(X) and p̄(X), we can readily have

qeŝ0 (X) q̄(X)
−
peŝ0 (X) p̄(X)
ẽq (X)ẽp (X)
ẽq (X)
q̄(X)
q̄(X) 2
− 2
ẽp (X) −
+ 3
ẽ (X)
=
p̄(X)
p̄ (X)
p̄2 (X)
p̄ (X) p
q̄(X)
+ 4
ẽq (X)ẽ2p (X) + o(ẽ2p (X) + ẽq (X)ẽ2p (X)),
p̄ (X)
=

(62)

where ẽp (X) and ẽq (X) denote {p̃ŝ0 (X) − p̄(X)} and {q̃ŝ0 (X) − q̄(X)}, respectively.
According to Lemma 1, it is not difficult to see that
h̃(X)
d
d
 K i/d  X
 K i/d 3
 K i/d 2  X
ĉh1 ,i,d̃ (X)
ĉh3 ,i,d˜(X)
ĉh2 ,i,d̃ (X)
+
+
M
M
M
i=1
i=1
i=1
!
X
d
K 
1 
 K i/d 3
+O
+o
ĉh3 ,i,d˜(X)
+o
M
M
M

=

d
X

i=1

=

d
X
i=1

1
K 
 K i/d
+O
.
+o
ĉh,i,d˜(X)
M
M
M

(63)

23

Furthermore, by applying the binomial theorem, we have
E[h̃t (X)]
d
X

=

 K i/d

c̃ˆh̃t ,i,d˜

i=1

=

d
X

M

I{i≥t} ĉh̃t ,i,d̃

i=1

!t

+o

 K i/d
M



+o

K
M





K
M

+O





+O

1
M





1
M



(64)
,

which can indicate that the lemma is proved.
According to Lemma 2 and Eq. (52a), it is readily seen that
 



qeŝ0 (X)
q̄(X)
E f
−f
peŝ0 (X)
p̄(X)
" 2
#


X
i
2
=E
c̃h̃i ,d˜(X)h̃ (X) + o c̃h̃3 ,d˜(X)h̃ (X)
i=1

=

d
X

c̃h̃1 ,i,d̃

i=1

=

d
X

ch̃,i,d̃

i=1

 K i/d
M

 K i/d
M

+

X
d

+o

c̃h̃2 ,i,d̃

i=1

K 
M

+O

 K i/d 2
M

+o

 X
d

 K i/d 2 

c̃h̃3 ,i,d˜

i=1

1 
.
M

M

+o

K 
M

+O

1
M

(65)

Lemma 3. Let a d-dimension variable X be a realization of p.m.f p independent of p̄ and q̄ mentioned
in Eq. (53). Then it can be given that
m
E[ēm
p (X)] = E [(p̄(X) − p(X)) ]

=

d
X

 K i/d

c̄em ,i,d˜
p

i=1

M

+o

K 
M

 1 
1
+o √
,
+o
K
M

(66a)

E[ēnq (X)] = E [(q̄(X) − q(X)n ]
=

d
X
i=1

 1 
K 
 K i/d
1
+o √
,
+o
c̄en ,i,d˜
+o
q
M
M
K
M

(66b)

where c̄em ,i,d̃ and c̄en ,i,d˜ are functions of d˜.
p

q

1
Proof:. Define Ud,p
˜ (X) = E[ M

p̄(X) −

Ud̃,p (X)
,
Vd̃

PM

i=1 I{Xi ∈Ud̃,X } ]

=

it is readily seen that

E[êp (X)] = E

"

Ûd,p
˜ (X)
Vd˜

P
−

xj ∈Ud̃,X

p(xj ). On the one hand, for êp (X) =

Ud,p
˜ (X)
Vd˜

#

= 0.

(67)

24

What is more, we have
 Û ˜ (X) 
d,p
Var
Vd˜
=

P
E[ M
i=1 I{Xi ∈Ud̃,X } ]
M 2 V ˜2

Ud,p
˜ (X)
M Vd˜2

−

j=1, I{Xi ∈Ud̃,X } I{Xj ∈Ud̃,X }
j6=i
M 2 V ˜2
d

i=1

+

d

=

PM PM

−

2 (X)
Ud,p
˜

V ˜2

(68)

d

2 (X)
Ud,p
˜
.
M 2 Vd˜2

which implies E[ê2p (X)] = O(1/M ).
By using Chebyshev’s inequality, we get


(
)
Ûd̃,p (X)
Var
Ûd,p
Ud,p
˜ (X)
˜ (X)
Vd̃
(69)
P
−
≥ε ≤
,
2
Vd˜
Vd˜
ε
1 η/2
1 PM
with some fixed η ∈ ( 32 , 1). In that case, we
where Ûd,p
˜ (X) = M
k=1 I{Xk ∈Ud̃,X } . Let ε = ( K )

have Var(

Ûd̃,p
2
Vd̃ )/ε

η

= O( K
M ). Thus, it is derived that

êp (X)


= êp (X) P {|êp (X)| < ε} + P {|êp (X)| ≥ ε}

 Kη 
= êp (X)I{|êp (X)|<ε} P {|êp (X)| < ε} + êp (X)I{|êp (X)|≥ε} }P {|êp (X)| < ε} + O
M
 Kη 
 1 
 Kη 
η/2
<ε+O
=O
.
+O
M
K
M
Furthermore, it is readily seen that


2
m
E[êm
p (X)] = E I{m=2} êp (X) + I{m≥3} êp (X)
 1

1 
mη/2
+ I{m≥3} O
= I{m=2} O
M
K
1 
1
= I{m=2} O
+ I{m≥3} o
.
M
K
Similarly, for E[ênq (X)], we get the same result as E[êm
p (X)].

(70)

(71)

On the other hand, it is not difficult to see that the relationship between Ud,p
˜ (X) and p(X) is similar
to Ûd,p
˜ (X) and p̂(X) in Eq. (58). Thus, it is easily seen that
ěp (X) =
=

Ud,p
˜ (X)
Vd˜
d
X
i=1

Furthermore, we have
E[ěm
p (X)]

=

K 
 K i/d
.
+o
c̄i,d˜(X)
M
M

d
X
i=1

− p(X)

čem ,i,d̃
p

 K i/d
M

!m

+o

K 
.
M

(72)

(73)

25

As for ēp (X), by applying the binomial theorem and Cauchy-Schwartz inequality, we have
m
X
m
āp,j êjp (X)ěm−j
(X)]
E[ēm
(X)]
=
E
{[ê
(X)
+
ě
(X)]
}
=
E
[
p
p
p
p
j=0

≤

m
X
j=0

q
2(m−j)
āp,j E[ê2j
(X)]
p (X)]E[ěp

q
m
q
X
2(m−j)
2m
āp,j E[ê2j
(X)]
= E[ěq (X)] +
p (X)]E[ěp

(74)

j=1

=

d
X
i=1

 K i/d
1
 1 
K 
c̄em ,i,d˜
+o
+o √
,
+o
p
M
M
K
M

where āp,j is the binomial coefficient.
Similarly, we can derive E[ēnq (X)], as well as, the proof of Lemma 3 is completed.
q̄(X)
p̄(X)

By expanding the
q̄(X)
p̄(X)

−

q(X)
p(X)

around q(X) and p(X), we can make use of Lemma 3 to derive ȟ(X) =

and E[ȟt (X)], similar to Lemma 2. Furthermore, using the same way as Eq. (65), we can

easily see that




 
q(X)
q̄(X)
−f
E f
p̄(X)
p(X)
" 2
#


X
i
2
=E
čȟi ,d˜(X)ȟ (X) + o čȟ3 ,d˜(X)ȟ (X)

(75)

i=1

=

d
X
i=1

 K i/d
K
1
+o
+o
.
cȟ,i,d˜
M
M
K

Therefore, by combining Eq. (65) and Eq. (75), the proof of Theorem 2 can be completed.
A PPENDIX B
P ROOF
For the function f (x) = e̟x
qe (X)
f ( peŝŝ0 (X) )
0

around

qe (X)
E[ peŝŝ0 (X) ]
0

f

where ξX
qe (X)
E[ peŝŝ0 (X) ].
0



−1

OF

T HEOREM 3

with ̟ > 0 and x > 0, we can do a Taylor series expansion of

as following

qeŝ0 (X)
peŝ0 (X)



=

2
X
i=0

f (i)




qe (X)
E[ peŝŝ0 (X) ]
0

i!

1
̺˜i (X) + f (3) (ξX )˜
̺3 (X),
6



qe (X) qe (X)
∈ E[ peŝŝ0 (X) ], peŝŝ0 (X) comes from the mean value theorem, and ̺˜(X) denotes
0

0

Define the operator H(Z) = Z − E(Z). Let
 

 qeŝ (Xi ) 
ai = H f E 0
,
peŝ0 (Xi )

 
 qeŝ0 (Xi ) 
′
̺˜(Xi ) ,
bi = H f E
peŝ0 (Xi )

(76)
qeŝ0 (X)
peŝ0 (X)

−

26

ci = H

 

X
r−1 f (j) E qeŝ0 (Xi )
peŝ (Xi )
0

j=2

j!


̺˜ (Xi ) ,
j


f (r) (ξ̃Xi ) r
̺˜ (Xi ) .
di = H
r!


Then the variance of F̂d˜ is
Var(F̂d˜) = E[(F̂d˜ − E(F̂d˜))2 ]

1
N −1
= E[(a1 + b1 + c1 + d1 )2 ] +
E[(a1 + b1 + c1 + d1 )(a2 + b2 + c2 + d2 )],
N
N
which can be bounded in the following.

(77)

Lemma 4. For a d-dimension variable X , a realization of p.m.f p independent of the window kernel
estimators qeŝ0 and peŝ0 , it can be given that

1
m

(78a)
(X)]
=
o
(X)
−
E
[p̃
E[em
(X)]
=
E
p̃
ŝ
ŝ
0
0
p
K
1
n

(78b)
=o
E[enq (X)] = E q̃ŝ0 (X) − E[q̃ŝ0 (X)]
K
√
˜l +1) d √
where K = ∆ M with ∆ = [ (2dL
] M , ep (X) and eq (X) denote {p̃ŝ0 (X) − E[p̃ŝ0 (X)]} and
{q̃ŝ0 (X) − E[q̃ŝ0 (X)]}, respectively.

Proof:. For the ep (X) = p̃ŝ0 (X) − E[p̃ŝ0 (X)], it is readily seen that


E[ep (X)] = E p̃ŝ0 (X) − E[p̃ŝ0 (X)] = 0.

(79)

In addition, by use of the definition 3, we have


Var p̃ŝ0 (X)




= E p̃2ŝ0 (X) − E2 p̃ŝ0 (X)
=

1
M

X

xj ∈Ud̃,X

W 2 (ŝ0 , X, xj )p(xj ) −



2

(80)

1  X
W (ŝ0 , X, xj )p(xj ) ,
M
xj ∈Ud̃,X

˜ xj ∈ U}. Consequently, it is evident to see that E[e2 (X)] = O(1/M ).
where Ud,X
= {xj : |xuj −X u | ≤ d,
˜
p

Similar to Eq. (70) with parameter ε = ( K1 )η/2 and η ∈ ( 32 , 1), we have
ep (X)


= ep (X) P {|ep (X)| < ε} + P {|ep (X)| ≥ ε}
 Kη 
= ep (X)I{|ep (X)|<ε} }P {|ep (X)| < ε} + O
M
 Kη 
 1 
 Kη 
η/2
<ε+O
=O
.
+O
M
K
M

(81)

27

Consequently, we get
E[em
p (X)]


= E I{m=2} e2p (X) + I{m≥3} em
p (X)
 1

1 
mη/2
+ I{m≥3} O
= I{m=2} O
M
K
1 
1
= I{m=2} O
+ I{m≥3} o
.
M
K
Similarly, it can be proved that E[enq (X)] has the same result as E[em
p (X)].
By using a Taylor series expansion of 1/peŝ0 (X) around E[peŝ0 (X)], we have
h
e2p (X) i
ep (X)
1
1
]=E
− 2
+ 3
E[
peŝ0 (X)
E[peŝ0 (X)] E [peŝ0 (X)]
ξ˜p,X

(82)

(83)

E[ep (X)]
1
− 2
+ o(E[e2p (X)]),
=
E[peŝ0 (X)] E [peŝ0 (X)]

where ep (X) denotes {peŝ0 (X) − E[pes0 (X)]}, and ξ̃p,X ∈ (E[pes0 (X)], peŝ0 (X)). Since the p and q are
independent, it is easily to see that
E[

qeŝ0 (X)
1
] = E[qeŝ0 (X)]E[
]
peŝ0 (X)
peŝ0 (X)
E[qeŝ0 (X)]
+ o(E[e2p (X)]).
=
E[peŝ0 (X)]

What is more, by expanding the
̺˜(X)

qes0 (X)
pes0 (X)

(84)

around E[qes0 (X)] and E[pes0 (X)], we have

eq (X)
eq (X)ep (X)
E[qes0 (X)]
E[qes (X)] 2
−
ep (X) − 2
+ 3 0
e (X)
E[pes0 (X)] E2 [pes0 (X)]
E [pes0 (X)]
E [pes0 (X)] p
E[qes (X)]
+ 4 0
eq (X)e2p (X) + o(E[e2p (X)]) + o(e2p (X) + eq (X)e2p (X)),
E [pes0 (X)]
In addition, by applying the Cauchy-Schwartz inequality and Lemma 4, it is readily seen that
=

n
|E[em
p (X)eq (X)]|
q

m
n
2n
≤ I{m≥1,n≥1} E[e2m
p (X)]E[eq (X)] + I{m>1,n=0} + I{m=0,n>1} |E[ep (X)eq (X)]|


n
+ I{m=1,n=0} + I{m=0,n=1} |E[em
p (X)eq (X)]|
 1 
1
,
=o √
+o
K
M
where m > 0 and n > 0 are integers.

Therefore, by applying the multinomial theorem to Eq. (85), it is apparent that

n
 qeŝ0 (X) ot
qeŝ0 (X)
t
−E
E[˜
̺ (X)] = E
peŝ0 (X)
peŝ0 (X)
 1 
1
=o √
,
+o
K
M

(85)

(86)

(87)

28

According to Eq. (87) and Eq. (77), we have
  qe (X ) 
i
ŝ
E[(a1 + b1 + c1 + d1 )2 ] = E[a21 ] + o(1) = cN E 0
+ o(1).
peŝ0 (Xi )

(88)

Moreover, due to the independent X1 and X2 , it can be readily seen that E[(a1 + b1 + c1 + d1 )(a2 +
b2 + c2 + d2 )] = 0. Therefore, we have
i
1
1 h   qeŝ0 (Xi ) 
Var(F̂d˜) =
cN E
,
+ o(1) = O
N
peŝ0 (Xi )
N

(89)

which indicates that Theorem 3 is proved.

A PPENDIX C
T HE MSE CONVERGENCE

OF

M-I

DIVERGENCE ESTIMATION

According to Eq. (45) and Taylor series expansion, we have
N
N
p
e (X )
n1 X
p(x ) o
X
p(X )
p(X )
1 X ̟ qeŝŝ0 (Xii )
̟ q(x j )
̟ q(X i )
̟ q(X i )
j
i
i
0
F̂d˜ − F̟ (P k Q) =
]+
−
p(xj )e
[e
e
−e
N
N
i=1

1
=
N

N 
X

i=1

p(X )

̟ q(X i )

̟e

i

i=1

xj ∈U

 pe (X ) p(X )  
h pe (X ) p(X ) i
i
i
i
i 2
ŝ0
ŝ0
+O
−
−
qeŝ0 (Xi ) q(Xi )
qeŝ0 (Xi ) q(Xi )

(90)

N
n1 X
p(xj ) o
X
p(Xi )
̟
̟
e q(Xi ) −
p(xj )e q(xj ) .
+
N
i=1

xj ∈U

Considering Remark 3 and the law of large numbers, it is easy to see that F̂d˜ − F̟ (P k Q) → 0.
Therefore, we have
F̂λ − F̟ (P k Q) =

X
l∈l̄

λl [F̂d˜l − F̟ (P k Q)] → 0,

(91)

which equally means F̂λ /F̟ (P k Q) → 1.
Additionally, in virtue of corollary 3 and the definition of MSE, it is readily seen that
(
)
h
i2
F̂λ∗
MSE(F̂λ∗ )
E
−1
= O(Γ −1 ),
= 2
F̟ (P k Q)
F̟ (P k Q)

(92)

where F̂λ∗ is the optimal ensemble estimation of F̟ (P k Q), and F̟ (P k Q) < ∞.
Therefore, by using the Taylor series expansion of log(x) around x = 1, we have
MSE(D̟̂ (P k Q))
)
(
i2
h
F̂λ∗
=E
log
F̟ (P k Q)
(
)


 1
2
2 2
F̂λ∗
F̂λ∗
F̂λ∗
=E
−1 −
−1 +o
−1
F̟ (P k Q)
2 F̟ (P k Q)
F̟ (P k Q)

h
i2
2 
F̂λ∗
F̂λ∗
−1 +o
−1
= O(Γ −1 ),
=E
F̟ (P k Q)
F̟ (P k Q)
which proves Eq. (50).

(93)

29

ACKNOWLEDGMENT
The authors would like to thank a lot for the support of the China Major State Basic Research
Development Program (973 Program) No.2012CB316100(2), National Natural Science Foundation of
China (NSFC) No. 61771283 and China Scholarship Council. Meanwhile, the work received the extensive
comments on the final draft from other members of Wistlab of Tsinghua University.
R EFERENCES
[1] O. Dikmen, Z. Yang, and E. Oja, “Learning the information divergence,” IEEE Transactions on Pattern Analysis and Machine
Intelligence, vol. 37, no. 7, pp. 1442–1454, July. 2014.
[2] A. Youssef, C. Delpha, and D. Diallo, “Analytical model of the KL Divergence for Gamma distributed data: application to
fault estimation,” In Proc. IEEE Signal Processing Conference (EUSIPCO), Nice, France, Aug. 2015.
[3] L. Li, Q. Xu, X. Luo, and S. Sun, “Key frame selection based on KL-divergence,” In Proc. IEEE International Conference
on Multimedia Big Data (BigMM), Beijing, China, Apr. 2015.
[4] Z. Youbi, L. Boubchir, and M. D. Bounneche, et al., “Human Ear recognition based on Multi-scale Local Binary Pattern
descriptor and KL divergence,” In Proc. IEEE Telecommunications and Signal Processing (TSP) , Vienna, Austria, Jun.
2016.
[5] Y. Qiao and N. Minematsu, “A Study on invariance of f -Divergence and its application to speech recognition,” IEEE
Transactions on Signal Processing, vol. 58, no. 7, pp. 3884–3890, July. 2010.
[6] A. Anderson and H. Haas, “Kullback-Leibler Divergence (KLD) based anomaly detection and monotonic sequence analysis,”
In Proc. IEEE Vehicular Technology Conference (VTC Fall) , San Francisco, USA, Sep. 2011.
[7] Chai B, Walther D, and Beck D, et al., “Exploring functional connectivities of the human brain using multivariate information
analysis,” In Proc. IEEE AAnnual Conference on Neural Information Processing Systems (NIPS), Vancouver, Canada, Dec.
2009.
[8] L. Yao, S. Qin, and H. Zhu, “Feature selection algorithm for hierarchical text classification using Kullback-Leibler
divergence,” In Proc. IEEE International Conference on Cloud Computing and Big Data Analysis (ICCCBDA) , Chengdu,
China, Apr. 2017.
[9] K. M. Carter, R. Raich, and A. O. Hero, “On local intrinsic dimension estimation and its applications,” IEEE Transactions
on Signal Processing, vol. 58, no. 2, pp. 650–663, Feb. 2010.
[10] A. O. Hero, B. Ma, O. J. Michel, and J. Gorman, “Applications of entropic spanning graphs,” IEEE Transactions on Signal
Processing, vol. 19, no. 5, pp. 85–95, Sep. 2002.
[11] Q. Wang, S. R. Kulkarni, and S. Verd, “Divergence estimation for multidimensional densities via k-nearest-neighbor
distances,” IEEE Trans. Inform. Theory, vol. 55, no. 5, pp. 2392–2405, May. 2009.
[12] D. Blei, A. Y. Ng, and M. I. Jordan, “Latent irichlet allocation,” Journal of Machine Learning Research, vol. 3, no. 1, pp.
993–1022, Jan. 2003.
[13] C. Fevotte, N. Bertin, and J.-L. Durrieu, “Nonnegative matrix factorization with the Itakura-Saito divergence: With
application to music analysis,” Neural Comput., vol. 21, no. 3, pp. 793–830, Mar. 2009.
[14] P. Y. Fan, Y. Dong, J. X. Lu, and S. Y. Liu, “Message importance measure and its application to minority subset detection
in big data,” In Proc. IEEE Globecom Workshops (GC Wkshps), Washington D.C., USA, Dec. 2016.
[15] R. She, S. Y. Liu, Y. Q. Dong, and P. Y. Fan, “Focusing on a probability element: parameter selection of message importance
measure in big data,” In Proc. IEEE International Conference on Communications (ICC), Paris, France, May. 2017.

30

[16] S. Y. Liu and R. She, et al., “Non-parametric message important measure: compressed storage design for big data in
wireless communication systems,” In Proc. IEEE Asia-Pacific Conference on Communicatioins (APCC), Perth, Australia,
Dec. 2017.
[17] H. Chernoff, “A measure of asymptotic efficiency for tests of a hypothesis based on a sum of observations,” Ann. Math.
Stat., vol. 23, pp. 493-507, 1952.
[18] S. Amari, Differential-geometrical methods in statistics, Springer Science & Business Media, Tokyo, 2012.
[19] H. Fujisawa and S. Eguchi, “Robust paramater estimation with a small bias against heavy contamination,” J. Multivariate
Anal., vol. 99, no. 9, pp. 2053-2081, 2008.
[20] J. Lin, “Divergence measures based on the Shannon entropy,” IEEE Trans. Inform. Theory, vol. 37, no. 1, pp. 145–151,
Jan. 1991.
[21] T. V. Erven and P. Harremoes, “Renyi Divergence and Kullback-Leibler Divergence,” IEEE Trans. Inform. Theory, vol.
60, no. 7, pp. 3797–3820, July. 2014.
[22] C. C. Kokonendji, T. S. Kiesse, and S. S. Zocchi, “Discrete triangular distributions and nonparametric estimation for
probability mass function,” Journal of Nonparametric Statistics, vol. 19, nos. 6–8, pp. 241–254, Aug.–Nov. 2007.
[23] G. L. Gilardoni, “On Pinsker’s and Vajda’s type inequalities for csiszar’s f-Divergences,” IEEE Trans. Inform. Theory, vol.
56, no. 11, pp. 5377–5386, Nov. 2010.

