Information Theoretic Learning with Infinitely Divisible Kernels
Authors: Luis Gonzalo Sánchez, Jose C. Principe
ICLR 2013

Abstract: In this paper, we develop a framework for information theoretic learning based on infinitely divisible matrices. We formulate an entropy-like functional on positive definite matrices based on Renyi's entropy definition and examine some key properties of this functional that lead to the concept of infinite divisibility. The proposed formulation avoids the plug in estimation of density and brings along the representation power of reproducing kernel Hilbert spaces. We show how analogues to quantities such as conditional entropy can be defined, enabling solutions to learning problems. In particular, we derive a supervised metric learning algorithm with very competitive results.

arXiv:1301.3551v6  [cs.LG]  4 Jun 2013
Information Theoretic Learning with Inﬁnitely
Divisible Kernels
Luis G. Sanchez Giraldo
Dept. of Electrical and Computer Engineering
University of Florida
Gainesville, Florida, USA
sanchez@cnel.ufl.edu
Jose C. Principe
Dept. of Electrical and Computer Engineering
University of Florida
Gainesville, Florida, USA
principe@cnel.ufl.edu
Abstract
In this paper, we develop a framework for information theoretic learning based on
inﬁnitely divisible matrices. We formulate an entropy-lik e functional on positive
deﬁnite matrices based on Renyi’s axiomatic deﬁnition of en tropy and examine
some key properties of this functional that lead to the concept of inﬁnite divisibil-
ity. The proposed formulation avoids the plug in estimation of density and brings
along the representation power of reproducing kernel Hilbert spaces. As an appli-
cation example, we derive a supervised metric learning algo rithm using a matrix
based analogue to conditional entropy achieving results comparable with the state
of the art.
1 Introduction
Information theoretic quantities are descriptors of the distributions of the data that go beyond second-
order statistics. The expressive richness of quantities su ch entropy or mutual information has been
shown to be very useful for machine learning problems where optimality based on linear and Gaus-
sian assumptions no longer holds. Nevertheless, operation al quantities in information theory are
based on the probability laws underlying the data generatio n process, which are rarely known in
the statistical learning setting where the only informatio n available comes from the sample {zi}n
i=1.
Therefore, the use of information theoretic quantities as d escriptors of data requires the develop-
ment of suitable estimators. In [1], the use of Renyi’s deﬁni tion of entropy along with Parzen
density estimation is proposed as the main tool for informat ion theoretic learning (ITL). The opti-
mality criteria is expressed in terms of quantities such as Renyi’s entropy, divergences based on the
Cauchy-Schwarz inequality, quadratic mutual information, among others. Part of the research effort
in this context has pointed out connections to reproducing kernel Hilbert spaces [2]. Here, we show
that these connections are not only valuable from a theoreti cal point of view, but they can also be
exploited to derive novel information theoretic quantities with suitable estimators from data.
Positive deﬁnite kernels have been employed in machine learning as a representational tool allowing
algorithms that are based on inner products to be expressed i n a rather generic way (the so called
“kernel trick”). Algorithms that exploit this property are commonly known as kernel methods. Let
X be a nonempty set. A function
κ : X × X ↦→R is called a positive deﬁnite kernel if for any
ﬁnite set {xi}N
i=1 ⊆ X and any set of coefﬁcients {
αi}N
i=1 ⊂ R, it follows that ∑i, j
αiαjκ(xi,xj) ≥ 0,
if at least one i, αi ̸= 0. In this case, there exist an implicit mapping φ : X ↦→H that maps any
element x ∈ X to an element φ(x) in a Hilbert space H , such that κ(x,y) =⟨φ(x),φ(y)⟩. The
above map provides an implicit representation of the object s of interest that belong to the set X .
The generality of this representation has been exploited in many practical applications, even for
data that do not come in standard vector representation Rd [3]. This is possible as long as a kernel
function is available.
More recently, it has been noticed that kernel induced maps a re also useful beyond the above ker-
nel trick in a rather interesting fashion. Namely, kernels c an be utilized to compute higher-order
statistics of the data in a nonparametric setting. Some exam ples exploring this idea are: kernel in-
dependent component analysis [4], the work on measures of de pendence and independence using
Hilbert-Schmidt norms [5], and the quadratic measures of in dependence proposed in [6]. It is not
surprising, yet important to mention, that a similar observation have also been reached from the work
on ITL since one of the original motivations in using information theoretic quantities is to go beyond
second order statistics. The work we introduce in this paper goes along these lines. The twist is that
rather than deﬁning an estimator of a conventional informat ion theoretic quantity such as Shannon
entropy, we propose a quantity build from the data that satisﬁes similar axiomatic properties to those
of well establish deﬁnitions such as Renyi’s deﬁnition of entropy
The main contribution of this work is to show that the Gram mat rix obtained from evaluating a
positive deﬁnite kernel on samples can be used to deﬁne a quantity based on the data with properties
similar to those of an entropy without assuming that the prob ability density is being estimated.
Therefore, we look at the axiomatic treatment of entropy andadapt it to the Gram matrices describing
the data. In this sense, we think about entropy as a measure in versely related to the amount of
statistical regularities (structure) directly from the data that can be applied as the optimality criterion
in a learning algorithm. As an application example, we derive supervised metric learning algorithm
that uses conditional entropy as the cost function. This is t he second contribution of this paper, and
the empirical results show that the proposed method is competitive with current approaches.
The main body of the paper is organized in two parts. First, weintroduce the proposed matrix-based
entropy measure using the spectral theorem along with a set of axiomatic properties that our quantity
must satisfy. Then, the notion of joint entropy is developed based on Hadamard products. We look
at some basic inequalities of information and how they trans late to the setting of positive deﬁnite
matrices, which ﬁnally allow us to deﬁne an analogue to condi tional entropies. In the development
of these ideas, we ﬁnd that the concept of inﬁnitely divisibl e kernels arises and become key to our
purposes. We revisit some of the theory on inﬁnitely divisib le matrices, to show how it links to
the the proposed information theoretic framework. In the la st part, we introduce an information
theoretic supervised metric learning algorithm. We show how the proposed analogue to conditional
entropy is a suitable cost function leading naturally to a gr adient descent procedure. Finally, we
provide some conclusions and future directions.
2 Positive Deﬁnite Matrices, and Renyi’s Entropy Axioms
Let us start with an informal observation that motivated our matrix based entropy. In [1], the use
of Renyi’s entropy is proposed as an alternative to the more c ommonly adopted deﬁnition of en-
tropy given by Shannon. In particular, it was found that Reny i’s second-order entropy provides an
amenable quantity for practical purposes. An empirical plu g in estimator of Renyi’s second-order
entropy based on the Parzen density estimator ˆf (x) =1
n ∑n
i=1
κ(xi,x), can be obtained as follows:
− log 1
n2
n
∑
i, j=1
h(xi,xj), (1)
where h(x,y) =
∫
X κσ (x,z)κσ (y,z)dz. Note that since h is a positive deﬁnite kernel, there exists a
mapping φ to a RKHS such that h(x,y) =⟨φ(x),φ(y)⟩; and the argument of the log in (1), called the
information potential, can be interpreted in this space as a norm:
⟨
1
n
n
∑
i=1
φ(xi), 1
n
n
∑
i=1
φ(xi)
⟩
=





1
n
n
∑
i=1
φ(xi)





2
, (2)
with the limiting case given by ∥E[
φ(X)]∥2. Thus, we can think of this estimator as an statistic
computed on the representation space provided by the positi ve deﬁnite kernel h. Now, let us look
at the case where κσ is the Gaussian kernel; if we construct the Gram matrix K with elements
Ki j = κ2σ (xi,xj), it is easy to verify that the estimator of Renyi’s second-order entropy based on (1)
corresponds to:
ˆH2(X) =−log
( 1
n2 tr(KK)
)
+C(σ). (3)
where C(σ) takes care of the normalization factor of the Parzen window.As we can see, the informa-
tion potential estimator can be related to the norm of the Gram matrix K deﬁned as ∥K∥2 = tr(KK).
From the above informal argument two important questions ar ise. First, it seems natural to ask
whether other functionals on Gram matrices allow informati on theoretic interpretations that can be
further utilized as objective functions in ITL. Secondly, even though h was originally derived from
a convolution of Parzen windows, was there anything about th e implicit representation that allows
to interpret (2) in information theoretic terms?
2.1 Renyi’s Axioms for Gram matrices
Real Hermitian matrices are considered generalizations of real numbers. It is possible to deﬁne a
partial ordering on this set by using positive deﬁnite matri ces, which are a generalization of the
positive real numbers. Let Mn be the set of all n × n real matrices; for two Hermitian matrices
A,B ∈ Mn, we say A ≽ B if A − B is positive deﬁnite. Likewise, A ≻ B means that A − B is strictly
positive deﬁnite.
The following spectral decomposition theorem [7] relates to the functional calculus on matrices and
provides a reasonable way to extend continuous scalar-valued functions to Hermitian matrices.
Theorem 2.1 Let D ⊂ C be a given set and let Nn(D) := {A ∈ Mn : A is normal and
σ(A) ⊂ D},
where σ(A) denotes the spectrum of A. If f (t) is a continuous scalar-valued function on D, then the
primary matrix function
f (A) =U



f (
λ1) ··· 0
.
.
. ... .
.
.
0 ··· f (
λn)


U∗ (4)
is continuous on Nn(D), where A = UΛU∗, Λ = diag(
λ1,... ,λn), and U ∈ Mn is unitary.
Equipped with the above result, we can deﬁne matrix functions such as f (A) =Ar for r ∈ R+, which
will be used in deﬁning the following matrix-based analogue to Renyi’s α-entropy. The functional
will then be applied to Gram matrices constructed by pairwise evaluation of a positive deﬁnite kernel
on the data samples.
Consider the set Δ+
n of positive deﬁnite matrices A ∈ Mn for which tr(A) ≤ 1. It is clear that this set
is closed under ﬁnite convex combinations.
Proposition 2.1 Let A ∈ Δ+
n and B ∈ Δ+
n and also tr(A) =tr(B) =1. The functional
S
α (A) = 1
1 − α log2 [tr(Aα )], (5)
satisﬁes the following set of conditions:
(i) S α (PAP∗) =Sα (A) for any orthonormal matrix P ∈ Mn
(ii) S α (pA) is a continuous function for 0 < p ≤ 1.
(iii) S α (1
n I) =log2 n.
(iv) S α (A ⊗ B) =Sα (A) +Sα(B).
(v) If AB = BA = 0; then for the strictly monotonic and continuous function g (x) =2(α−1)x for
α ̸= 1 and α > 0, we have that:
Sα (tA + (1 − t)B) =g−1 (tg(Sα (A)) + (1 − t)g(Sα(B))). (6)
Proof 2.1 The proof of (i) easily follows from Theorem 2.1. Take A = UΛU∗ now PU is also a
unitary matrix and thus f (A) = f (PAP∗) the trace functional is invariant under unitary transforma-
tions. For (ii), the proof reduces to the continuity of 1
1−α log2(p)α . For (iii), a simple calculation
yields trAα =
( 1
n
) α−1
. Now, for property (iv), notice that if trA = trB = 1, then, tr(A ⊗ B) =1.
Since A = UΛU∗ and B = VΓV∗ we can write A ⊗ B = (U ⊗ V)(Λ ⊗ Γ)(U ⊗ V)∗, from which
tr(A ⊗ B)α = tr(Λ ⊗ Γ)α = tr(Λα )tr(Γα ) and thus (iv) is proved. Finally, (v) notice that for any
integer power k of tA+ (1 −t)B we have: (tA + (1 −t)B)k = (tA)k + ((1 −t)B)k since AB = BA = 0.
Under extra conditions such as f (0) =0 the argument in the proof of Theorem 2.1 can be ex-
tended to this case. Since the eigen-spaces for the non-null eigenvalues of A and B are orthogonal
we can simultaneously diagonalize A and B with the orthonorm al matrix U, that is A = UΛU∗
and B = UΓU∗ where Λ and Γ are diagonal matrices containing the eigenvalues of A and B r e-
spectively. Since AB = BA = 0, then ΛΓ = 0. Under the extra condition f (0) =0, we have that
f (tA + (1 − t)B) =f (tA) +f ((1 − t)B) yielding the desired result for (v).
Notice also that if the rank of A, ρ(A) =1, the entropy Sα (A) =0 for any α ̸= 0.
It is also true that,
Sα (A) ≤ Sα (1
n I) =log2 n. (7)
As we can see (5) satisﬁes some properties attributed to entr opy. Nevertheless, such a character-
ization may not fully endow all unit-trace positive deﬁnite matrices with an information theoretic
interpretation. Which descriptors are suitable in represe nting joint-spaces? What properties should
be satisﬁed by the matrices in order to be applied to conceptsthat link them to random variables such
as conditioning? In what follows, we address these points by developing notions of joint entropy
and conditional entropy, for which, additional propertiesmust be fulﬁlled. Recall that the notions of
joint and conditional entropy are not only important for the above reasons, but they also provide the
means to propose objective functions for learning that are based on information theoretic quantities.
2.2 Hadamard Products and the Notion of Joint Entropy
Positive kernels are also useful in integrating multiple mo dalities. Using the the product kernel,
we can readily deﬁne the notion of joint-entropy. Consider a sequence of sample pairs {(xi,yi)}N
i=1
where xi ∈ X and yi ∈ Y . Assume, we have a positive deﬁnite kernels
κ1 deﬁned on X × X
and κ2 deﬁned on X × X . The product kernel κ((xi,yi),(xj,yj)) =κ1(xi,xj)κ(yi,yj) is a positive
deﬁnite kernel on (X × Y ) × (X × Y ). As we can see the Hadamard product arises as a joint
representation in a our matrix based entropy. Consider two m atrices A and B in Δn with unit trace,
for which there exists some relation between the elements Ai j and Bi j for all i and j. The joint
entropy can be deﬁned as:
Sα
( A ◦ B
tr(A ◦ B)
)
(8)
It is important then to verify that the deﬁnition of joint ent ropy (8) satisﬁes a basic intuition about
uncertainty. The joint entropy should never be smaller than any of the individual entropies of the
variables that conform it. The following proposition veriﬁ es this intuition for a subset of the unit
trace, positive deﬁnite matrices.
Proposition 2.2 Let A and B be two n × n positive deﬁnite matrices with trace 1 with nonnegative
entries, and Aii = 1
n for i = 1,2,..., n. Then, the following inequality holds:
Sα
( A ◦ B
tr(A ◦ B)
)
≥ Sα (B), (9)
2.3 Conditional Entropy as a Difference Between Entropies
The conditional entropy of X given Y , which can be understood as the uncertainty about X that
remains after knowing the joint distribution of X and Y, can be obtained from a difference between
two entropies. In the Shannon’s deﬁnition of conditional en tropy, H(X|Y) can be expressed as
H(X|Y) =H(X,Y)− H(Y). The properties of this deﬁnition has been recently studied in the case of
Renyi’s entropies [8] and in the matrix case, this deﬁnition yields:
S
α (A|B) =Sα
( A ◦ B
tr(A ◦ B)
)
− Sα(B), (10)
for positive semideﬁnite matrices A and B with nonnegative entries and unit trace, such that Aii = 1
n
for all i = 1,..., n. The above quantity is nonnegative and upper bounded by Sα (A). Certainly,
normalization is an important property of the matrices involved in the above results. If A and B are
normalized to have unit trace, then for r ∈ [0,1] it is true that the Hadamard product of
A◦r ◦ B◦(1−r), (11)
is also normalized. However, it is not always true that the re sulting matrix (11) is positive deﬁnite.
This product can be thought as a weighted geometric average for which the resulting matrix will give
more emphasis to either one of the matrices. However, if A and B satisfy a property called inﬁnitely
divisibility, the product is guaranteed to be positive deﬁnite 1.
3 Inﬁnitely Divisible Functions
The theory of inﬁnitely divisible developed below is not new, but it is included because it provides a
basic understanding about the role of inﬁnitely divisible kernels in computing the above information
theoretic quantities from data. To avoid confusion, let us d escribe the key points to bear in mind
before we move to the mathematical description. Inﬁnitely d ivisible kernels and negative deﬁnite
functions are tied together trough the exponential a logari thm functions. Both functions provide
Hilbert space representations of the data. We can think of the RKHS of the inﬁnitely divisible kernel
as a representation to compute the higher order descriptorsof the data. On the other hand, the Hilber-
tian metric can be the representation space for which we want to compute the high order statistics.
Normalization, as we show below is not only important in sati sfying the conditions for the infor-
mation theoretic quantities already deﬁned, but it also sho ws that many possible representational
choices are equivalent.
3.1 Negative Deﬁnite Functions and Hilbertian Metrics
Let M = (X ,d) be a separable metric space. A necessary and sufﬁcient condi tion for M
to be embeddable in a Hilbert space H is that for any set {xi} ⊂ X of n + 1 points,
∑n
i, j=1
αiαj
(
d2(x0,xi) +d2(x0,xj) − d2(xi,xj)
)
≥ 0, for any ααα ∈ Rn. This condition is equivalent
to ∑n
i, j=0
αiαjd2(xi,xj) ≤ 0, for any ααα ∈ Rn+1, such that ∑n
i=0
αi = 0. This condition is known
as negative deﬁniteness. Interestingly, the above condition implies that exp(−rd2(xi,xj)) is positive
deﬁnite in X for all r > 0 [9]. Indeed, matrices derived from functions satisfying the above property
conform a special class of matrices know as inﬁnitely divisible.
3.2 Inﬁnitely Divisible Matrices
According to the Schur product theorem A ≽ 0 implies A◦n = A ◦ A ◦ ··· ◦ A ≽ 0 for any positive
integer n. Does the above hold if we to take fractional powers of A? In other words,is the matrix
A◦ 1
m ≽ 0 for any positive integerm? This question leads to the concept of inﬁnitely divisible matrices
[10, 11]. A nonnegative matrix A is said to be inﬁnitely divisible if A◦r ≽ 0 for every nonnegative
r. Inﬁnitely divisible matrices are intimately related to negative deﬁniteness as we can see from the
following proposition
Proposition 3.1 If A is inﬁnitely divisible, then the matrix Bi j = −logAi j is negative deﬁnite
From this fact it is possible to relate inﬁnitely divisible m atrices with isometric embeddings into
Hilbert spaces. If we construct the matrix
Di j = Bi j − 1
2(Bii + Bj j), (12)
using the matrix B from proposition 3.1. There exists a Hilbert space H and a mapping φ such that
Di j = ∥φ(i) − φ( j)∥2
H . (13)
Moreover, notice that ifA is positive deﬁnite−A is negative deﬁnite and expAi j is inﬁnitely divisible.
In a similar way, we can construct a matrix,
Di j = −Ai j + 1
2 (Aii + Aj j), (14)
1By this, we also mean positive semideﬁnite
K
X Hd
HK
Infinitely
Divisible Kernel
d
Negative
Definite Function
Hilbertian
Metric
Embedding
exp
log
   Data
  Driven
Operator
Estimator
     IT
Quantity
Figure 1. Spaces involved in the inﬁnitely divisible matrix framework
with the same property (13). This relation between (12) and ( 14) suggests a normalization of in-
ﬁnitely divisible matrices with non-zero diagonal element s that can be formalized in the following
theorem.
Theorem 3.1 Let X be a nonempty set, and let d1 and d2 be two metrics on it, such that for any set
{xi}n
i=1,
n
∑
i, j=1
αiαjd2
ℓ (xi,xj) ≤ 0, for any ααα ∈ Rn, and ∑n
i=1
αi = 0, is true for ℓ = 1,2. Consider the
matrices A(ℓ)
i j = exp−d2
ℓ (xi,xj) and their normalizations ˆA(ℓ), deﬁned as:
ˆA(ℓ)
i j =
A(ℓ)
i j√
A(ℓ)
ii
√
A(ℓ)
j j
. (15)
Then, if ˆA(1) = ˆA(2) for any ﬁnite set {xi}n
i=1 ⊆ X , there exist isometrically isomorphic Hilbert
spaces H1 and H2, that contain the Hilbert space embeddings of the metric spaces (X ,dℓ), ℓ = 1,2.
Moreover, ˆA(ℓ) are inﬁnitely divisible.
Figure 1 summarizes the relation between spaces that are con sidered in the proposed framework.
The object space X can be directly mapped into H
κ using an inﬁnitely divisible kernel κ, or it
can be mapped to a Hilbert space Hd, if a negative deﬁnite function d, is employed as the distance
function. The spaces Hκ and Hd are related by the log and exp functions.
4 Application to Metric Learning
4.1 Adaptation Using the Matrix-Based Entropy
By deﬁnition, the matrix entropy functional (5) fall into th e family of matrix functions know as
spectral functions. These functions only depend on the eige nvalues of matrix and therefore their
name [12]. Using theorem (1.1) from [13] it is straightforward to obtain the derivative of (5) atA as
∇S
α (A) = α
(1 − α)tr(Aα )UΛα−1U∗, (16)
where A = UΛU∗. It is important to note that this decomposition can be used t o our advantage.
Instead of computing the full set of eigenvectors and eigenv alues of A, we can approximate the
gradient of Sα by using only a few leading eigenvalues. It is easy to see thatthis approximation will
be optimal in the Frobenius norm ∥X∥Fro =
√
tr(X∗X).
4.2 Metric Learning Using Conditional Entropy
Here, we apply the proposed matrix framework to the problem o f supervised metric learning. This
problem can be formulated as follows. Given a set of points {(xi,li)}n
i=1, we seek a positive
semideﬁnite matrix AAT, that parametrizes a Mahalanobis distance between samples x,x′ ∈ Rd
as d(x,x′) = (x − x′)TAAT(x − x′). Our goal is to ﬁnd parametrization matrix A such that the con-
ditional entropy of the labels li given the projected samples yi = ATxi with yi ∈ Rp and p ≪ d, is
minimized. This can be posed as the following optimization problem:
minimize
A∈Rd×p
Sα (L|Y )
subject to ATxi = yi, for i = 1,..., n;
tr(ATA) =p,
(17)
where the trace constraint prevents the solution from growi ng unbounded. We can translate this
problem to our matrix-based framework in the following way. Let K be the matrix representing the
projected samples
Ki j = 1
n exp
(
− (xi − xj)TAAT(xi − xj)
2σ2
)
,
and L be the matrix of class co-occurrences where Li j = 1
n if li = lj and zero otherwise. The condi-
tional entropy can be computed as Sα (L|Y ) =Sα (nK ◦ L)− Sα (K), and its gradient at A, which can
be derived based on (24), is given by:
XT(P − diag(P1))XA (18)
where
P = (nL ◦ ∇Sα (nK ◦ L)− ∇Sα (K)) ◦ K (19)
Finally, we can use (18) to search for A iteratively.
UCI Data: To evaluate the results we use the same experimental setup pr oposed in [14], we com-
pares 5 different approaches to supervised metric learning based on the classiﬁcation error obtained
from two-fold cross-validation using a 4-nearest neighbor classiﬁer. The reported errors are aver-
ages errors from 10 runs on the two folds for each algorithm; i n our case the parameters are p = 3,
α = 1.01 and σ =
√
3. The feature vectors were centered and scaled to have unit v ariance. Fig-
ure 2(a) shows the results of the proposed approach conditio nal entropy metric learning (CEML),
information theoretic metric learning (ITML) proposed in [ 14], neighborhood component analysis
(NCA) from [15], the maximally collapsing metric learning ( MCML) method from [16], the large
margin nearest neighbor (LMNN) method found in [17], and, as a baseline, the the inverse covari-
ance and Euclidean distances. The results for the Soybean dataset are not reported since there is
more than one possible data set in the UCI repository under th at name. The errors obtained by
the metric learning algorithm using the proposed matrix-ba sed entropy framework are consistently
among the best performing methods included in the comparison.
Choice of order α: Even though the choice of the entropy order above appears to be arbitrary, there
is a motivation in choosing α close to 1. The reason is that the higher the entropy order, th e more
prone the algorithm is to ﬁnd unimodal solutions. This can be advantageous if prior knowledge
or strong assumptions on the class distributions are taken i nto consideration. In our experiments,
we opted for lower entropy order and give the algorithm more ﬂ exibility in ﬁnding a good solu-
tion. To experimentally show this phenomena, we generated a two-dimensional dataset containing
points from two classes. In one direction the classes are ver y well separated but the distribution
has multiple modalities. On the orthogonal direction, the c lasses are not fully separable, but their
distributions are unimodal. Figure 3 shows a sample with poi nts drawn from both classes, as we
can see projecting the data onto the horizontal axis provides better separability at the cost of a more
complex decision boundary. We run our metric learning algor ithm 60 times for different values of
α and recorded the direction of the resulting one-dimensiona l feature extractor. Table 1 shows the
number of times a particular direction was picked by our algo rithm for different entropy orders. It
can be seen that for larger values of α, the algorithm selected the vertical direction more often.
α 1.01 1.3 2 5
Horizontal 58 35 1 1
Vertical 2 25 59 59
Table 1. Occurrence of horizontal and vertical solutions versus the entropy order
Wine Ionosphere Scale Iris
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35Error
 
 
CEML(proposed method)
ITML
NCA
MCML
LMNN
invCov
Euclidean
(a) Classiﬁcation error UCI data
−10 −5 0 5 10−10
−5
0
5
10
Projected Features
 Gram Matrix Projected Features
(b) Projected faces UMist dataset and resulting Gram matrix σ =
√
2
Figure 2. Results for the Metric learning application
−2 −1.5 −1 −0.5 0 0.5 1 1.5 2
−4
−3
−2
−1
0
1
2
3
Unimodal
Better
separability
Figure 3. Artiﬁcial data to illustrate the role of the entropy order
UMist Faces: We also run the algorithm on the UMist dataset; This data set c onsists of Grayscale
faces (8 bit [0-255]) of 20 different people. The total numbe r of images is 575 and the size of each
image is 112x92 pixels for a total of 10304 dimensions. Pixel values were normalized by dividing
by 255 and removing the mean. Figure 2(b) shows the images pro jected into R2. It is remarkable
how a linear projection can separate the faces, and it can als o be seen from the Gram matrix that it
tries to approximate the co-occurrence matrix L.
5 Conclusions
In this paper, we presented a data-driven framework for info rmation theoretic learning based on
inﬁnitely divisible matrices. We deﬁne estimators of entro py-like quantities that can be computed
from the Gram matrices obtained by evaluating inﬁnitely div isible kernels on pairs of samples.
The proposed quantities do not assume that the density of the data has been estimated, this can be
advantageous in many scenarios where even deﬁning a densityis not feasible. We discuss some key
properties of the proposed quantities and show how they can be applied to deﬁne useful analogues to
quantities such as conditional entropy. Based on the proposed framework, we introduce a supervised
metric learning algorithm with results that are competitive with the state of the art. Nevertheless, we
believe that many interesting formulations to learning pro blems based on the proposed framework
are yet to be found. It is also important to highlight that theconnection between the RKHS provided
by the inﬁnitely divisible kernel, and the Hilbertian metri cs associated with the negative deﬁnite
functions, opens an interesting avenue to investigate formulations of information theoretic learning
algorithms on both spaces, and the implications of choosing one or the other.
References
[1] J. C. Principe, Information Theoretic Learning: Renyi’s Entropy and Kerne l Perspectives, ser. Series in
Information Science and Statistics, M. Jordan, R. Nowak, and B. Sch¨ olkopf, Eds. Springer, 2010.
[2] J.-W. Xu, A. R. C. Paiva, I. Park, and J. C. Principe, “A rep roducing kernel hilbert space framework for
information theoretic learning,” IEEE Transactions on Signal Processing, vol. 56, no. 12, pp. 5891–5902,
December 2008.
[3] J. Shawe-Taylor and N. Cristianini, Kernel Methods for Pattern Analysis. Cambridge University Press,
2004.
[4] F. R. Bach and M. I. Jordan, “Kernel independent componen t analysis,” Journal of Machine Learning
Research, vol. 3, pp. 1–48, July 2002.
[5] A. Gretton, O. Bousquet, A. Smola, and B. Sch¨ olkopf, “Me asuring statistical dependence with hilbert-
schmidt norms,” in Proceedings of Algorithmic Learning Theory, S. Jain, H. Simon, and E. Tomita, Eds.,
2005, pp. 63–77.
[6] S. Seth, M. Rao, I. Park, and J. C. Pr´ ıncipe, “A uniﬁed fra mework for quadratic measures of indepen-
dence,” IEEE Transactions on Signal Processing, vol. 59, no. 8, pp. 3624–3635, August 2011.
[7] R. A. Horn and C. R. Johnson, Topics in Matrix Analysis. Cambridge University Press, 1991.
[8] A. Teixeira, A. Matos, and L. Antunes, “Conditional r´ enyi entropies,” IEEE Transactions on Information
Theory, vol. 58, no. 7, pp. 4273–4277, July 2012.
[9] I. J. Schoenberg, “Metric spaces and positive deﬁnite fu nctions,” Transactions of the American Mathe-
matical Society, vol. 44, no. 3, pp. 522–536, November 1938.
[10] R. Bhatia, “Inﬁnite divisible matrices,” The American Mathematical Monthly , vol. 113, no. 3, pp. 221–
235, March 2006.
[11] R. A. Horn, “The theory of inﬁnitely divisible matrices and kernels,” Transactions of the American Math-
ematical Society, vol. 136, pp. 269–286, February 1969.
[12] S. Friedland, “Convex spectral functions,” Linear and Multilinear Algebra, vol. 9, pp. 299–316, 1981.
[13] A. S. Lewis, “Derivatives of spectral functions,” Mathematics of Operations Research, vol. 21, no. 3, pp.
576–588, August 1996.
[14] J. V . Davis, B. Kulis, P. Jain, S. Sra, and I. S. Dhillon, “Information-theoretic metric learning,” in ICML,
Corvalis, Oregon, USA, June 2007, pp. 209–216.
[15] J. Goldberger, S. Roweis, G. Hinton, and R. Salakhutdinov, “Neighborhood component analysis,” inNIPS,
2004.
[16] A. Globerson and S. Roweis, “Metric learning by collaps ing classes,” in NIPS, 2005.
[17] K. Q. Weinberger, J. Blitzer, and L. K. Saul, “Distance m etric learning for large margin nearest neighbor
classiﬁcation,” in NIPS, 2005.
[18] R. Bhatia, Matrix Analysis, ser. Graduate Texts in Mathematics. Springer, 1996.
A Additional results and proofs
To prove (9), we need to introduce the concept of majorizatio n and some results pertaining the
ordering that arises from this deﬁnition. The proposition i s replicated in this appendix for the sake
of self containment.
Deﬁnition A.1 (Majorization): Let p and q be two nonnegative vectors in Rn such that ∑n
i=1 pi =
∑n
i=1 qi < ∞. We say p≼ q, q majorizes p, if their respective ordered sequences p[1] ≥ p[2] ≥ ··· ≥ p[n]
and q[1] ≥ q[2] ≥ ··· ≥ q[n] denoted by {p[i]}n
i=1 and {p[i]}n
i=1, satisfy:
k
∑
i=1
p[i] ≤
k
∑
i=1
q[i] for k = 1,... ,n (20)
It can be shown that if p ≼ q then p = Aq for some doubly stochastic matrix A [18]. It is also easy
to verify that if p ≼ q and p ≼ h then p ≼ tq + (1 − t)h for t ∈ [0,1]. The majorization order is
important because it can be associated with the deﬁnition of Schur-concave (convex) functions. A
real valued function f on Rn is called Schur-convex ifp ≼ q implies f (p) ≤ f (q) and Schur-concave
if f (q) ≤ f (p).
Lemma A.1 The function f
α : S n ↦→R+ (S n denotes the n dimensional simplex), deﬁned as,
fα (p) = 1
1 − α log2
n
∑
i=1
pα
i , (21)
is Schur-concave for α > 0.
Notice that, Schur-concavity (Schur-convexity) cannot be confused with concavity (convexity) of a
function in the usual sense. Now, we are ready to state the inequality for Hadamard products.
Proposition A.1 Let A and B be two n × n positive deﬁnite matrices with trace 1 with nonnegative
entries, and Aii = 1
n for i = 1,2,..., n. Then, the following inequality holds:
Sα
( A ◦ B
tr(A ◦ B)
)
≥ Sα (B), (22)
Proof A.1 In proving (9), we will use the fact that S α preserves the majorization order (inversely)
of nonnegative sequences on the n-dimensional simplex. First look at the identity
xT(A ◦ B)x = tr(ADxBDx) =1
n
In particular, if {xi}n
i=1 is an orthonormal basis for Rn, tr(A ◦ B) =
n
∑
i=1
xT
i (A ◦ B)xi. If we let {xi}n
i=1
be the eigenvectors of A ◦ B ordered according to their respective eigenvalues in decr easing order,
then,
k
∑
i=1
xT
i (A ◦ B)xi =
k
∑
i=1
tr(ADxi BDxi ) ≤ 1
n
k
∑
i=1
tr
(
11TDxi BDxi
)
= 1
n
k
∑
i=1
xT
i Bxi ≤ 1
n
k
∑
i=1
yT
i Byi, (23)
where k = 1,..., n and {yi}n
i=1 are the eigenvectors of B ordered according to their respective eigen-
values in decreasing order. The inequality (23) is equivalent to say that n
λ (A ◦ B) ≼ λ (B), that is,
the sequence of eigenvalues of (A ◦ B)/tr(A ◦ B) is majorized by the sequence of eigenvalues of B,
which implies (9) by Lemma A.1.
A beautiful observation from Theorem 3.1 is that, according to equation (10), the proposed normal-
ization procedure for inﬁnitely divisible matrices can be thought of as ﬁnding the maximum entropy
matrix among all matrices for which the Hilbert space embeddings are isometrically isomorphic.
A.1 Derivatives of Spectral Functions
Let Hn denote the vector space of real Hermitian matrices of size n × n endowed with inner product
⟨X,Y⟩= trXY; and let Un denote the set of n × n unitary matrices. A real valued function f deﬁned
on a subset of Hn is unitarily invariant if f (UXU∗) = f (X) for any U ∈ Un. Associated with each
spectral function f there is a symmetric function F on Rn. By symmetric we mean that F(x) =
F(Px) for any n × n permutation matrix P. Let
λ (X) denote the vector of ordered eigenvalues of X;
then, a spectral function f (X) is of the form F(λ (X)) for F a symmetric. We are interested in the
differentiation of the composition (F ◦ λ )(·) =F(λ (·)) at X2. The following result [13] allows us
to differentiate a spectral function f at X
Theorem A.1 Let the set Ω ⊂ Rn be open and symmetric, that is, for any x ∈ Ω and any n × n
permutation matrix P, Px ∈ Ω . Suppose that F is symmetric, Then, the spectral function F (λ (·))
is differentiable at a matrix X if and only if F is differentiable at the vector λ (X). In this case, the
gradient of F ◦ λ at X is
∇(F ◦ λ )(X) =Udiag(∇F(λ (X)))U∗, (24)
for any unitary matrix satisfying X = Udiag(λ (X))U∗.
2In here, ◦ denotes composition rather than Hadamard product


Peer review:
[Review]:
This paper introduces new entropy-like quantities on positive semi definite matrices. These quantities can be directly calculated from the Gram matrix of the data, and they do not require density estimation. This is an attractive property, because density estimation can be difficult in many cases. Based on this theory, the authors propose a supervised metric learning algorithm which achieves competitive results.

Pros: The problem studied in the paper is interesting and important. The empirical results are promising.

Cons: 
i) Although I believe that there are many great ideas in the paper, in my opinion the presentation of the paper needs significant improvement. It is very difficult to asses what exactly the novel contributions are in the paper, because the authors didn't separate their new results well enough from the existing results. For example, Section 3 is about infinitely divisible matrices, but I don't know what exactly the new results are in this section. 

ii) The introduction and motivation could be improved as well. The main message and its importance is a bit vague to me. I recommend revising Section 1. The main motivation to design new entropy like quantities was that density estimation is difficult and we might need lots of sample points to get satisfactory results. That's true that the proposed approach doesn't require density estimation, but it is still not clear if the proposed approach works better than those algorithms that use density estimators. 
The empirical results seem very promising, so maybe I would emphasize them more.

iii) There are a few places in the text where the presented idea is simple, but it is presented in a complicated way and therefore it is difficult to understand. For example Section 4.1 and 4.2 seem more difficult than they should be. The definition of function F is not clear either.

iv) There are  a few typos and grammatical mistakes in the paper that also need to be fixed before publication.
For example, on Page 1:
Page 1: know as --> known as
Page 1: jlearning