![](https://csdnimg.cn/release/download_crawler_static/84996396/bg3.jpg)
The computational complexity of this incremental search
method is OðjSjMÞ .
2.3 Optimal First-Order Incremental Selection
We prove in the following that the combination of Max-
Relevance and Min-Redundancy criteria, i.e., the mRMR
criterion, is equivalent to the Max-Dependency criterion if
one feature is selected (added) at one time. We call this type
of selection the “first-order” incremental search. We have
the following theorem:
Theorem. For the first-order incremental search, mRMR is
equivalent to Max-Dependency (2).
Proof. By definition of the first-order search, we assume
that S
m1
, i.e., the set of m 1 features, has already been
obtained. The task is to select the optimal mth feature x
m
from set fX S
m1
g.
The dependency D in (2) and (3) is represented by
mutual information, i.e., D ¼ IðS
m
; cÞ,whereS
m
¼
fS
m1
;x
m
g can be treated as a multivariate variable.
Thus, by the definition of mutual information, we have:
IðS
m
; cÞ¼HðcÞþHðS
m
ÞHðS
m
;cÞ
¼ HðcÞþHðS
m1
;x
m
ÞHðS
m1
;x
m
;cÞ;
ð8Þ
where Hð:Þ is the entropy of the respective multivariate
(or univariate) variables.
Now, we define the following quantity JðS
m
Þ¼
Jðx
1
; ...;x
m
Þ for scalar variables x
1
; ...;x
m
,
Jðx
1
;x
2
; ...;x
m
Þ¼
Z
Z
pðx
1
; ...;x
m
Þ log
pðx
1
;x
2
; ...;x
m
Þ
pðx
1
Þpðx
m
Þ
dx
1
dx
m
:
ð9Þ
Similarly, we define JðS
m
;cÞ¼Jðx
1
; ...;x
m
;cÞ as
Jðx
1
;x
2
; ...;x
m
;cÞ¼
Z
Z
pðx
1
; ...;x
m
;cÞ log
pðx
1
;x
2
; ...;x
m
;cÞ
pðx
1
Þpðx
m
ÞpðcÞ
dx
1
dx
m
dc:
ð10Þ
We can easily derive (11) and (12) from (9) and (10),
HðS
m1
;x
m
Þ¼HðS
m
Þ¼
X
m
i¼1
Hðx
i
ÞJðS
m
Þ; ð11Þ
HðS
m1
;x
m
;cÞ¼HðS
m
;cÞ¼HðcÞþ
X
m
i¼1
Hðx
i
ÞJðS
m
;cÞ:
ð12Þ
By substituting them to the corresponding terms in
(8), we have
IðS
m
; cÞ¼JðS
m
;cÞJðS
m
Þ
¼ JðS
m1
;x
m
;cÞJðS
m1
;x
m
Þ:
ð13Þ
Obviously, Max-Dependency is equivalent to simul-
taneously maximizing the first term and minimizing the
second term.
We can use the Jensen’s Inequality [16] to show the
second term JðS
m1
;x
m
Þ is lower-bounded by 0. A
related and slightly simpler proof is to consider the
inequality logðzÞz 1 with the equality if and only if
z ¼ 1. We see that
Jðx
1
;x
2
; ...;x
m
Þ
¼
Z
Z
pðx
1
; ...;x
m
Þ log
pðx
1
Þpðx
m
Þ
pðx
1
; ...;x
m
Þ
dx
1
dx
m
Z
Z
pðx
1
; ...;x
m
Þ
pðx
1
Þpðx
m
Þ
pðx
1
; ...;x
m
Þ
1
dx
1
dx
m
¼
Z
Z
pðx
1
Þpðx
m
Þdx
1
dx
m
Z
Z
pðx
1
; ;x
m
Þdx
1
dx
m
¼1 1 ¼ 0:
ð14Þ
It is easy to verify that the minimum is attained when
pðx
1
; ...;x
m
Þ¼pðx
1
Þpðx
m
Þ, i.e., all the variables are
independent of each other. As all the m 1 features have
been selected, this pair-wise independence condition
means that the mutual information between x
m
and any
selected feature x
i
ði ¼ 1; ...;m 1Þ is minimized. This is
the Min-Redundancy criterion.
We can also derive the upper bound of the first term in
(13), JðS
m1
;c;x
m
Þ. For simplicity, let us first show the
upper bound of the general form Jðy
1
; ...;y
n
Þ, assuming
there are n variables y
1
; ...;y
n
. This can be seen as follows:
Jðy
1
;y
2
; ...;y
n
Þ
¼
Z
Z
pðy
1
; ...;y
n
Þ log
pðy
1
; ...;y
n
Þ
pðy
1
Þpðy
n
Þ
dy
1
dy
n
¼
Z
Z
pðy
1
; ...;y
n
Þ log
pðy
1
jy
2
;...;y
n
Þpðy
2
jy
3
;...;y
n
Þpðy
n1
jy
n
Þpðy
n
Þ
pðy
1
Þpðy
n1
Þpðy
n
Þ
dy
1
dy
n
¼
X
n1
i¼1
Hðy
i
ÞHðy
1
jy
2
; ...;y
n
ÞHðy
2
jy
3
; ...;y
n
ÞHðy
n1
jy
n
Þ
X
n1
i¼1
Hðy
i
Þ:
ð15Þ
Equation (15) can be easily extended as
Jðy
1
;y
2
; ...;y
n
Þmin
X
n
i¼2
Hðy
i
Þ;
X
n
i¼1;i6¼2
Hðy
i
Þ; ;
X
n
i¼1;i6¼n1
Hðy
i
Þ;
X
n1
i¼1
Hðy
i
Þ
()
:
ð16Þ
It is easy to verify the maximum of Jðy
1
; ...;y
n
Þ or,
similarly, the first term in (13), JðS
m1
;c;x
m
Þ, is attained
when all variables are maximally dependent. When S
m1
has been fixed, this indicates that x
m
and c should have the
maximal dependency. This is the Max-Relevance criterion.
Therefore, according to (13), as a combination of Max-
Relevance and Min-Redundancy, mRMR is equivalent to
Max-Dependency for first-order selection. tu
Note that the quantity Jð:Þ in (9) and (10) has also been
called “mutual information” for multiple scalar variables[10].
We have the following observations:
1228 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 27, NO. 8, AUGUST 2005