probabilities estimation

requires the estimation of 2K+1 probabilities. Furthermore, even if there were ways to have an
estimation, its minimization would be computationally intractable.
At the other extreme, one could do a trivial random sampling which would ensure to some extent
independence between features (if different types of features are equally represented) but would not
account for predictive power. This could be dealt with by basing the choice on an estimate of this
predictive power. The main weakness of this approach is that although it takes care of individual
performance, it does not avoid at all redundancy among the selected features. One would pick many
similar features, as the ones carrying a lot of information are likely to be of a certain type. For face
detection with edge-like features for instance, edges on the eyebrows and the mouth would be the
only ones competitive as they are more face-specific than any other edge, yet numerous enough.
We propose an intermediate solution. Our approach deals with the tradeoff between individual
power and independence by comparing each new feature with the ones already picked. We say that
a feature X
0
is good only if ˆI(Y ; X
0
|X) is large for every X already picked. This means that X
0
is
good only if it carries information about Y, and if this information has not been caught by any of
the X already picked. More formally, we propose the following iterative scheme
ν(1) = argmax
n
ˆI(Y ; Xn) (1)
∀k, 1 ≤ k < K, ν(k +1) = argmax
n

min
l≤k
ˆI

Y ; Xn |Xν(l)

| {z }
s(n,k)
. (2)
As said before, ˆI

Y ; Xn |Xν(l)

is low if either Xn does not bring information about Y or if this
information was already caught by Xν(l)
. Hence, the score s(n, k) is low if at least one of the features
already picked is similar to Xn (or if Xn is not informative at all).
By taking the feature Xn with the maximum score s(n, k) we ensure that the new feature is both
informative and different than the preceding ones, at least in term of predicting Y.
The computation of those scores can be done accurately as each score I(Y ;Xn |Xν(l)
) requires
only estimating the distribution of triplets of boolean variables. Despite its apparent cost this algorithm can be implemented in a very efficient way. We will come back in details to such an
implementation in §4.
Note that this criterion is equivalent to maximizing I(X, Xν(k)
; Y)−I(Xν(k)
; Y), which is proposed in (Vidal-Naquet and Ullman, 2003).
2.4 Theoretical Motivation
In Koller and Sahami (1996) the authors propose using the concept of the Markov blanket to characterize features that can be removed without hurting the classification performance. A subfamily
of features M is a blanket for a feature Xi
if Xi
is conditionally independent of the other feature and
the class to predict given M. However, as the authors point out, such a criterion is stronger than
what is really required which is the conditional independence between Xi and Y given M.
CMIM is a forward-selection of features based on an approximation of that criterion. This approximation considers families M composed of a unique feature already picked. Thus, a feature X
can be discarded if there is one feature Xν already picked such that X and Y are conditionally independent given Xν. This can be expressed as ∃k, I(Y ; X |Xν(k)
) = 0. Since the mutual information is
positive, this can be re-writt