State Variation Mining: On Information Divergence
with Message Importance in Big Data
Rui She, Shanyun Liu, and Pingyi Fan

arXiv:1801.04064v2 [] 15 Jan 2018

State Key Laboratory on Microwave and Digital Communications
Tsinghua National Laboratory for Information Science and Technology
Department of Electronic Engineering, Tsinghua University, Beijing, P.R. China
Emails: {sher15, liushany16}@mails.tsinghua.edu.cn, fpy@tsinghua.edu.cn

Abstract—Information transfer which reveals the state variation of variables can play a vital role in big data analytics
and processing. In fact, the measure for information transfer
can reflect the system change from the statistics by using
the variable distributions, similar to KL divergence and Renyi
divergence. Furthermore, in terms of the information transfer in
big data, small probability events dominate the importance of
the total message to some degree. Therefore, it is significant to
design an information transfer measure based on the message
importance which emphasizes the small probability events. In
this paper, we propose the message importance divergence (MID)
and investigate its characteristics and applications on three
aspects. First, the message importance transfer capacity based on
MID is presented to offer an upper bound for the information
transfer with disturbance. Then, we utilize the MID to guide
the queue length selection, which is the fundamental problem
considered to have higher social or academic value in the caching
operation of mobile edge computing. Finally, we extend the MID
to the continuous case and discuss the robustness by using it to
measuring information distance.

I. I NTRODUCTION
Recently, the amount of data is exploding rapidly and the
computing complexity for data processing is also increasing.
To some degree, this phenomenon is resulted from more and
more mobile devices as well as the growing service of clouds.
In the literature, it is favored to process the collected data to
dig out the hidden important information. On the one hand,
it is necessary to improve the computation technologies for
big data processing, such as cloud computing, fog computing
and mobile edge computing (MEC). On the other hand, a
series of technologies for big data analysis and mining are
required, such as neural networks and machine learning, as
well as distributed parallel computing, etc.
In many scenarios of big data, the small probability events
attract more attention than the large probability ones [1]. That
is, the rarity of small probability events has higher social
or academic value. Message importance is used to reflect
such kind of values in applications. How to characterize the
message importance variation in the processing of big data is a
critical and interesting problem. Here, we shall investigate and
measure information transfer process by use of the message
importance, focusing on small probability events. Before we
proceed, let us review the definition of message importance
measure (MIM) briefly first [2].

In a finite alphabet, for a given probability distribution
P = {p(x1 ), p(x2 ), ..., p(xn )}, the MIM with importance
coefficient ̟ ≥ 0 is defined as
X
p(xi )e̟(1−p(xi )) ,
(1)
L(P, ̟) = log
xi

which measures the information importance of the distribution.
Then, by setting the parameter ̟ = 1 and simplifying the
form of MIM, it is easy to obtain its fundamental definition
as follows.

Definition 1. For the discrete probability P ={p(x1 ), p(x2 ),
...,p(xn )}, the MIM can be given by
X
p(xi )e−p(xi ) .
L(P ) =
(2)
xi

On account of the Definition 1, it is available to regard
the MIM as an element to measure the message importance
variation for a dynamic system. Then, new information transfer
measures based on the MIM are defined as follows.
Definition 2. In terms of two discrete probability Q =
{q(x1 ), q(x2 ), ..., q(xn )} and P = {p(x1 ), p(x2 ), ..., p(xn )},
the message importance divergence (MID) is defined as
X
{q(xi )e−q(xi ) − p(xi )e−p(xi ) }. (3)
DI (Q||P ) =
xi

Note that the Definition 2 characterizes the information
transfer from the statistics. That is, we can make use of MID
to measure the end-to-end change for an information transfer
process.
In fact, there exist a variety of different information measures handling the problem of information transfer process.
Shannon entropy and Renyi entropy are applicable to intrinsic
dimension estimation [3]. As well, the NMIM and M-I divergence can be used in anomaly detection [4], [5]. Moreover,
the directed information [6] and Schreibers transfer entropy [7]
are commonly applied to inferring the causality structure and
characterizing the information transfer process. In addition,
referring to the idea from dynamical system theory, new
information transfer measures are proposed to explore and
exploit the causality between states in the system control [8].
However, in spite of numerous kinds of information measures, few works focus on how to characterize the information

transfer from the perspective of message importance in big
data. To this end, the MID different from the above information measures is introduced.
We organize the rest of this paper as follows. In Section
II, we introduce the message importance transfer capacity
measured by the MID to describe the information transfer
with disturbance. In Section III, the MID is used to discuss
the queue length selection for the data caching in MEC from
the viewpoint of queue theory. Moreover, some simulations
are presented to validate our theoretical results. In Section IV,
we extend the MID to the continuous case to investigate the
correlation of message importance in the information transfer
process. Finally, we conclude it in Section VI.
II. M ESSAGE I MPORTANCE T RANSFER C APACITY BASED
ON M ESSAGE I MPORTANCE DIVERGENCE

Moreover, according to Eq. (5), we have
n
C(p, β) = max [p + β(1 − 2p)]e−[p+β(1−2p)]
p
o
+ [(1 − p) + β(2p − 1)]e−[(1−p)+β(2p−1)] − L(β).

(9)

Then, it is readily seen that
n
∂C(p, β)
= (1 − 2β) [1 − p − β(1 − 2p)]e−[p+β(1−2p)]
∂p
o
− [1 − (1 − p) − ε(2p − 1)]e−[(1−p)+β(2p−1)] .
(10)
for
In the light of the monotonically decreasing of ∂C(p,β)
∂p
p ∈ [0, 1], it is apparent that p = 1/2 is the only solution for
∂C(p,β)
= 0. Therefore, the proposition can be testified.
∂p

B. Strongly symmetric information transfer
In this section, we will introduce the MID to describe the
information transfer with additive disturbance. To do so, we
define the message importance transfer capacity measured by
the MID as follows.
Definition 3. Assume that there exists an information transfer
process as,
{X, p(y|x), Y },
(4)
where the p(y|x) denotes a probability distribution matrix
describing the information transfer from the variable X following distribution p(x) to the Y following p(y). We define
the message importance transfer capacity as
C = max{L(Y ) − L(Y |X)},

(5)

p(x)

P

where p(yj ) =
p(xi )p(yj |xi ), L(Y ) =
xi
P P
L(Y |X) = yj xi p(xi , yj )e−p(yj |xi ) .

P

p(yj )e−p(yj ) ,

yj

A. Binary symmetric information transfer
Proposition 1. Assume that there exists an information transfer process {X, p(y|x), Y }, where the information transfer
matrix is


1−β
β
p(y|x) =
,
(6)
β
1−β
which indicates that variables X and Y both obey binary
distributions. In this case, we have
1

(7)

where L(β) = βe−β + (1 − β)e−(1−β) and 0 < β < 1.
Proof. Considering a variable X following binary distribution
(p, 1 − p), it is not difficult to see that
L(Y |X) = βe−β + (1 − β)e−(1−β) .

which indicates that variables X and Y both follow Kary distributions. We have the message importance transfer
capacity as
β

1

C(β) = e− K − {(1 − β)e−(1−β) + βe− K−1 },

(8)

(12)

where the parameter β ∈ (0, 1).
Proof. On account of the information transfer matrix and the
Eq. (2), we have
β

In order to have an insight into the applications of message importance transfer capacity, some specific information
transfer scenarios are discussed as follows.

C(β) = e− 2 − L(β),

Proposition 2. Assume that there exists a strongly symmetric
information transfer matrix as follows

β 
β
...
1 − β K−1
K−1
β 
 β
1−β
...
K−1
K−1  ,
(11)
p(y|x) = 
 ...
...
...
... 
β
β
...
1−β
K−1
K−1

L(Y |X) = βe− K−1 + (1 − β)e−(1−β) .

(13)

Then, similar to the proof of Proposition 1, we can also use
Lagrange multiplier method to obtain the message information
transfer capacity. In this case, the distribution of Y should
satisfy p(y1 ) = p(y2 ) = ... = p(yK ) = 1/K.
In addition, consider that the probability distribution of variable X is {p(x1 ), p(x2 ), ..., p(xK )}. In the strongly symmetric
transfer matrix, if the variable X follows uniform distribution,
namely p(x1 ) = p(x2 ) = ... = p(xK ) = 1/K, we will have
p(yj ) =

K
X
i=1

p(xi , yj ) =

K
X

p(xi )p(yj |xi )

i=1

K
1
1 X
p(yj |xi ) = ,
=
K i=1
K

(14)

which indicates that Y also follows the uniform distribution.
Therefore, it is testified that when the variable X follows
uniform distribution which leads to the uniform distribution
for variable Y , we will obtain the message importance transfer
capacity C(β).

III. A PPLICATION

IN

THE

M OBILE E DGE C OMPUTING
M/M/ S / K QUEUE

WITH

Consider the MEC system that consists of numerous mobile
devices, an edge server cluster, and a central cloud far from the
local devices. The queue models for mobile devices, the edge
server cluster and the central cloud are regarded as a M/M/1
queue, a M/M/s queue, and a M/M/∞ queue, respectively.
In particular, each mobile device can offload a part of or the
entire service requests to the corresponding edge server cluster
when the communication is disturbed. As well, the overloaded
requests from edge servers will be offloaded to the central
cloud for processing [10].
In terms of the MID, it can be applied to distinguish the
state probability distributions in a queue model such as M/M/s
queue. In particular, the state probability is derived from the
stationary process, namely a dynamic equilibrium based on
birth and death process. Then, we can obtain the steady queue
state probability in the M/M/s/k model. By use of Taylor series
expansion, the approximate MIM is given by
s+k
X

pj e−pj =

s+k
X

pj [1 − pj + O(p2j )]

j=0

j=0

X

s−1
aj 2 (as /s!)2 [1 − ρ2(k+1) ]
.
2
( ) +
= 1 − p0
,
j!
1 − ρ2
j=0
(15)
where λ̃ and µ̃ are arrival rate and service rate, s is the number
of servers, k is the buffer or caching size, the traffic intensity
ρ = a/s as well as a = λ̃/µ̃. Note that, in the M/M/s/k queue,
the queue state probability pj (j = 0, ..., s + k) are given by
p0 =

s−1 j
hX
a
j=0
j

j!

+

as 1 − ρk+1 i−1
,
·
s!
1−ρ

(16a)

a
p0 , (0 < j < s),
j!
as
pj = ρj−s p0 , (s ≤ j ≤ s + k).
s!

pj =

(16b)
(16c)

Then, referring to Eq. (15), we can obtain the MID to
characterize the message importance gap for the queue model
M/M/s as follows.
Proposition 3. As for the M/M/s model, the information difference between two queue state probability distributions Pk+1
and Pk which are with buffer size k and k + 1 respectively,
can be measured by MID as
DI (Pk+1 ||Pk ) =

s+k+1
X

p̃j e−p̃j −

+

1
(ϕ1 +
ϕ22

−

k+1
2
ϕ2 1−ρ
1−ρ )
2(k+1)

1
(ϕ1 +

Similarly, it is not difficult to derive the MID between the
queue state probability distributions with buffer size ∞ and k,
which is given by
DI (P∞ ||Pk )
=(
+

1
k+1

2
(ϕ1 + ϕ2 1−ρ
1−ρ )

ϕ22

−

2(k+1)

s−1
X
1
aj
( )2
)
ϕ2 2
(ϕ1 + 1−ρ ) j=0 j!

(18)

1−ρ
1
−
[
ϕ2 2 ].
)
1 − ρ2 (ϕ1 + ϕ2 1−ρk+1 )2
(ϕ1 + 1−ρ
1−ρ

Especially, when the number of server is one, that is, the
queue model is M/M/1/k model, it it readily seen that
DI(s=1) (P∞ ||Pk ) =

2a
2a(1 − ak+1 )
−
,
1 + a (1 + a)(1 − ak+2 )

(19)

where DI(s=1) (P∞ ||Pk ) denotes the MID with s = 1. Moreover, for the queue length selection, it is required that the
distinction between two distribution P∞ and Pk should be
small enough, namely, |DI(s=1) (P∞ ||Pk )| ≤ ǫ. Then we have
ǫ(1+a)
ln a(2+ǫ−(2−ǫ)a)

(20)
− 1.
ln a
It is easy to see that ǫ plays a key role in the caching size
selection when using finite size caching to imitate the infinite
caching working mode.
Similar to MID, the KL divergence between the queue state
probability distributions with buffer size k + 1 and k is given
by
X
X
1
1
pj log
D(Pk ||Pk+1 ) =
pj log
−
p̃
p
j
j
j
j
k+1
(21)
(1−ρ)ρ
n
ϕ2 1−ρk+1 o
,
= log 1 + ϕ (1−ρ)
1
+ ϕ2
1−ρk+1
k≥

where the parameters pj , p̃j , ϕ1 and ϕ2 are the same as them
in Proposition 3.
Likewise, we can derive the KL divergence between the
queue state distributions with buffer size ∞ and k as
D(Pk ||P∞ ) = log

1
ϕ1 + ϕ2 1−ρ
k+1

ϕ1 + ϕ2 1−ρ
1−ρ

.

(22)

For the queue length selection with KL divergence, it is
readily seen that

pj e−pj

j=0

j=0

.
=(

s+k
X

where pj and p̃j are queue state probability in the M/M/s/k
and M/M/s/k+1 models respectively,
Ps−1 as well as parameter ϕ1
and ϕ2 are given by ϕ1 = j=0 aj /j! and ϕ2 = as /s!.

)

s−1
X

k+2
2
ϕ2 1−ρ
j=0
1−ρ )
2(k+2)

(

aj 2
)
j!

1−ρ
1−ρ
[
−
].
1−ρk+2 2
1 − ρ2 (ϕ1 + ϕ2 1−ρk+1 )2
)
(ϕ
+
ϕ
1
2
1−ρ
1−ρ

(17)

ln(1 − 21ǫ )
(23)
− 2.
ln a
To validate our derived results in theory, some simulations
are presented. The events arrivals are listed in Table I. It is
readily seen that they have the same average interarrival time
as 1/λ̃0 . Besides, the traffic intensity is selected as ρ = 0.9 in
all cases.
k≥

TABLE I
T HE D ISTRIBUTIONS OF E VENT I NTERARRIVAL T IME
Type of
Distribution

Exponential
Distribution

Uniform
Distribution

Normal
Distribution

P (X)

X ∼ E(λ̃0 )

X ∼ U (0, 2/λ̃0 )

X ∼ N(

0.6

g0 (x) = f0 (x) + ǫf0α (x)u(x),

D I-Sim-Poisson

0.15

D I-Sim-Uniform

0.5

Imfornation measure value

1
, 1 )
λ̃0 λ̃2
0

Then, we investigate the correlation of message importance
by using DMID, which can also reflect the robustness of
DMID. Consider the observation model, Pg0 |f0 : f0 (x) →
g0 (x), that denotes an information transfer map for the variable
X from the probability distribution f0 (x) to g0 (x). By using
the similar way in [9], the relationship between f0 (x) and
g0 (x) can be described as

0.1

D I-Sim-Normal

0.05

D-Sim-Poisson
D-Sim-Uniform
D-Sim-Normal
D I-Ana-Poisson

0.4
0.3

D-Ana-Poisson

0
0

1

2

3

4

5

0.2

and the constraint condition satisfies
Z
ǫf0α (x)u(x)dx = 0,

(26)

(27)

Sx

where ǫ and α are adjustable coefficients. u(x) is a perturbation function of the variable X in the interval Sx .
Then, by using the above model, the end-to-end information
distance measured by DMID is given as follows.
Proposition 4. For two probability distributions g0 (x) and
f0 (x) whose relationship satisfies the conditions Eq. (26) and
Eq. (27), the information distance measured by DMID is given
by

0.1
0
-0.1
0

5

10

15

20

25

Queue length

Fig. 1. The performance of different information measures between the queue
length k and k + 1 for the queue model in the case of different arrival events
distributions.

In Fig. 1, the legends DI -Sim, DI -Ana and D-Sim,
D-Ana are used to denote the simulation results and the
analytical results for MID and KL divergence, respectively.
It is illustrated that the convergence of MID is faster than that
of KL divergence, which indicates that MID may provide a
reasonable lower bound to select the caching size for MEC. In
addition, we can see that the Poisson distribution corresponds
the worst case for the arrival process among the three discussed
cases with respect to the convergence of both MID and KL
divergence.
IV. M ESSAGE I MPORTANCE D IVERGENCE IN C ONTINUOUS
C ASES
Similar to the definition 1 and 2, we can extend the two
definition to the case with continuous distributions as
Z
f (x)e−f (x) dx,
x ∈ Sx ,
L(f (x)) =
(24)
Sx

DI (g(x)||f (x)) = L(g(x)) − L(f (x))
Z
g(x)e−g(x) − f (x)e−f (x) dx, x ∈ Sx ,
=
Sx

(25)
where g(x) and f (x) are two probability distributions with
respect to the variable X in a given interval Sx . Moreover,
L(f (x)) and DI (g(x)||f (x)) can be called differential message importance measure (DMIM) and differential message
importance divergence (DMID).

DI (g0 (x)||f0 (x))
Z n
o
g0 (x)e−g0 (x) − f0 (x)e−f0 (x) dx
=
=ǫ

Sx
∞
X

(−1)i (i + 1)
i!

i=1
∞
2 X

ǫ
+
2

i=1

i

Z

(−1) (i + 1)
(i − 1)!

Sx

Z

f0i+α (x)u(x)dx

Sx

f0i−1+2α (x)u2 (x)dx + o(ǫ2 ),

(28)
where ǫ and α denote parameters, u(x) is a function of the
variable X in the interval Sx .
Proposition 4 describes the perturbation between f0 (x) and
g0 (x). Furthermore, it is not difficult to obtain the DMID
(u)
(u)
between two different distributions g1 and g2 based on
the same reference distribution f0 (x), which is given by
(u)

(u)

DI (g1 (x)||g2 (x))
(u)

(u)

= [L(g1 (x)) − L(f0 (x))] − [L(g2 (x)) − L(f0 (x))]
Z
∞
X
(−1)i (i + 1)
=ǫ
f0i+α (x)[u1 (x) − u2 (x)]dx
i!
S
x
i=1
Z
∞
ǫ2 X (−1)i (i + 1)
f0i−1+2α (x)[u21 (x) − u22 (x)]dx
+
2 i=1 (i − 1)!
Sx

+ o(ǫ2 ),

(29)
where
(u)

∀x ∈ Sx ,

(30a)

(u)

∀x ∈ Sx ,

(30b)

g1 (x) = f0 (x) + ǫf0α (x)u1 (x),
g2 (x) = f0 (x) + ǫf0α (x)u2 (x),

in which the ǫ and α are parameters, u1 (x) and u2 (x) are
functions of the variable X in the interval Sx .

Remark 1. It is apparent that when the parameter ǫ is small
enough, the DMID of two distributions is convergent with the
order of O(ǫ). Actually, this provides a way to apply DMID to
measure the correlation of message importance, if the system
does not have relatively large change.
In addition, by extending the information transfer process
described as Eq. (4) to the case with continuous distributions,
it is also significant to clarify the effect of the additive
disturbance on the message importance transfer capacity as
follows.
Theorem 1. Assume that there exists an information transfer process between the variable X and Y both following
continuous distributoins, denoted by {X, p(y|x), Y }, where
E[X] = 0, E[X 2 ] = Ps , Y = X + Z, and Z denotes independent memoryless additive variable, namely a continuous
additive disturbance, whose mean and variance satisfy that
E[Z] = µ and E[(Z − µ)2 ] = σ 2 , respectively. Then, the
message importance transfer capacity is determined by the
variances of the variable X and Z as
C(Ps ) = max DI (Y ||Z)
p(x)

= max{L(Y )} − L(Z)
p(x)
n Z +∞
o
= max
p(y)e−p(y) dy
p(x)

−

j=0

2

(−1)j
j!

pj+1 (z)dz,

−∞

s.t. E[Y ] = Ps + PN ,

(31b)

2
2
Rwhere PN = µ + σ , L(·) is the DMIM operator, and p(y) =
p(x)p(y|x)dx.
Sx

Proof. According to Eq. (4), we have
(
x(x, y) = x
z(x, y) = y − x.

(32)

Then, it is not difficult to see that
p(x, y) = p(x, z)|J(

xz
)| = p(x, z)
xy

∂x
∂x
∂z
∂x

∂x
∂y
∂z
∂y

= p(x, z).

(33)
Moreover, by virtue of the independence of X and Z, we have
p(x)p(y|x) = p(x)p(z), which indicates that p(y|x) = p(z).
Then, we have
Z Z
L(Y |X) =
p(x)p(y|x)e−p(y|x) dxdy
x y
Z Z
(34)
=
p(x)p(z)e−p(z) dxdz
Zx z Z
= p(x){ p(z)e−p(z) dz}dx = L(Z).
x

V. C ONCLUSION
In this paper, we investigated the information transfer problem in big data and proposed an information measure, i.e.,
MID. Furthermore, this information measure has its own dramatic characteristics on paying more attention to the message
importance hidden in big data. This makes the information
measure as a promising tool for information transfer measure
in big data. We presented the message importance transfer
capacity measured by the MID which can give an upper bound
for the information transfer with disturbance. Furthermore, we
employed the MID to discuss the caching size selection in
MEC. In addition, the MID was extended to the continuous
case to investigate the correlation of message importance in
the information transfer process.
ACKNOWLEDGMENT

∞

Z

In practice, the variance can be regarded as the power of
signals. Therefore, the message importance transfer capacity
in the Theorem 1 may be applied to guide the signal transfer
processing with an additive disturbance.

(31a)

−∞

∞
X

Furthermore, according to the fact that E[Y 2 ] = E[(X +
Z)2 ] = E[X 2 ] + E[Z 2 ] = Ps + PN , we have the constraint
condition Eq. (31b). As well, by substituting the definition of
MID into Eq. (31a), the Theorem 1 is proved.

z

Consequently, in terms of the Definition 3, it is readily seen
that L(Y ) − L(Y |X) can be written as L(Y ) − L(Z), which
testifies Eq. (31a).

We indeed appreciate the support of the China Major
State Basic Research Development Program (973 Program)
No.2012CB316100(2), and the National Natural Science Foundation of China (NSFC) No. 61771283.
R EFERENCES
[1] Y. Bu, S. Zou, and V. V. Veeravalli, “Linear-complexity exponentiallyconsistent tests for universal outlying sequence detection,” in Proc. 2017
IEEE International Symposium on Information Theory (ISIT), Aachen,
Germany, June. 2017, pp. 988–992.
[2] P. Fan, Y. Dong, J. Lu, and S. 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,
pp 1–5.
[3] K. M. Carter, R. Raich, and A. O. Hero, “On local intrinsic dimension
estimation and its applications,” IEEE Trans. Signal Process., vol. 58, no.
2, pp. 650–663, Feb. 2010.
[4] S. Liu, R. She, P. Fan, and K. B. Letaief. (2017). “Non-parametric message important measure: storage code design and transmission planning
for big data. [Online]. Available: https://arxiv.org/abs/1709.10280
[5] R. She, S. Y. Liu, and P. Fan, “Amplifying inter-message distance: on
information divergence measures in big data,” IEEE Access, vol. 5, pp.
24105–24119, Nov. 2017.
[6] L. Zhao, Y. H. Kim, H. H. Permuter, and T. Weissman, “Universal
estimation of directed information,” in Proc. IEEE Int. Symp. Inf. Theory
(ISIT), Austin, USA, June. 2010, pp. 230–234.
[7] T. Schreiber, “Measuring information transfer,” Physical Review Letters,
vol. 85, no. 2, pp. 461–464, July, 2000.
[8] S. Sinha and U. Vaidya, “Causality preserving information transfer
measure for control dynamical system, in Proc. IEEE 55th Conference
on Decision and Control (CDC) , Las Vegas, USA, Dec. 2016, pp. 7329–
7334.
[9] S. Huang, A. Makur, L. Zheng, and G. W. Wornell, “An informationtheoretic approach to universal feature selection in high-dimensional
inference,” in Proc. 2017 IEEE International Symposium on Information
Theory (ISIT), Aachen, Germany, June. 2017, pp. 1336–1340.

[10] L. Liu, Z. Chang, X. Guo, and T. Ristaniemi, “Multi-objective optimization for computation offloading in mobile-edge computing, In Proc.
IEEE Symposium on Computers and Communications (ISCC), Heraklion,
Greece, July. 2017, pp 832–837.

