Nonextensive Entropic Kernels
Andre F. T. Martins†‡
Mario A. T. Figueiredo‡
Pedro M. Q. Aguiar]
Noah A. Smith†
Eric P. Xing†
August 2008
CMU-ML-08-106

School of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213† School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, USA,
‡ Instituto de Telecomunicações / ] Instituto de Sistemas e Robótica, Instituto Superior Técnico,

Lisboa, Portugal

This work was partially supported by Fundação para a Ciência e Tecnologia (FCT), Portugal, grant PTDC/EEATEL/72572/2006 and by the European Commission under project SIMBAD. A.M. was supported by a grant from FCT
through the CMU-Portugal Program and the Information and Communications Technologies Institute (ICTI) at CMU.
N.S. was supported by NSF IIS-0713265 and DARPA HR00110110013. E.X. was supported by NSF DBI-0546594,
DBI-0640543, and IIS-0713379.

Keywords: Positive definite kernels, nonextensive information theory, Tsallis entropy, JensenShannon divergence, string kernels.

Abstract
Positive definite kernels on probability measures have been recently applied in classification problems involving text, images, and other types of structured data. Some of these kernels are related
to classic information theoretic quantities, such as (Shannon’s) mutual information and the JensenShannon (JS) divergence. Meanwhile, there have been recent advances in nonextensive generalizations of Shannon’s information theory. This paper bridges these two trends by introducing
nonextensive information theoretic kernels on probability measures, based on new JS-type divergences. These new divergences result from extending the the two building blocks of the classicalJS divergence: convexity and Shannon’s entropy. The classical notion of convexity is extended
to the wider concept of q-convexity, for which we prove a Jensen q-inequality. Based on this inequality, we introduce Jensen-Tsallis (JT) q-differences, a nonextensive generalization of the JS
divergence, and define a k-th order JT q-difference between stochastic processes. We then define
a new family of nonextensive mutual information kernels, which allow weights to be assigned
to their arguments, and which includes the Boolean, JS, and linear kernels as particular cases.
Nonextensive string kernels are also defined that subsume the p-spectrum kernel. We illustrate theperformance of these kernels on text categorization tasks, in which documents are modeled bothas bags-of-words and as sequences of characters.

1

Introduction

In kernel-based machine learning [Schölkopf and Smola, 2002, Shawe-Taylor and Cristianini,2004], there has been recent interest in defining kernels on probability distributions, to tackle
several problems involving structured data [Desobry et al., 2007, Moreno et al., 2004, Jebara et al.,2004, Hein and Bousquet, 2005, Lafferty and Lebanon, 2005, Cuturi et al., 2005]. By defining aparametric family S containing the distributions from which the data points (in the input space X)
are assumed to have been generated, and defining a map from X from S (e.g., through maximum
likelihood estimation), a distribution in S may be fitted to each datum. Therefore, a kernel that isdefined on S × S automatically induces a kernel on the original input space, through map composition. In text categorization, this framework appears as an alternative to the Euclidean geometry
inherent to the usual bag-of-words vector representations. In fact, approaches that map data tostatistical manifolds, equipped with well-motivated non-Euclidean metrics [Lafferty and Lebanon,
2005], often outperform support vector machine (SVM) classifiers with linear kernels [Joachims,
2002]. Some of these kernels have a natural information theoretic interpretation, establishing abridge between kernel methods and information theory [Cuturi et al., 2005, Hein and Bousquet,2005].
The main goal of this paper is to widen that bridge; we do that by introducing a new wideclass of kernels rooted in nonextensive information theory, which contains previous information
theoretic kernels as particular elements. The Shannon and Rényi entropies [Shannon, 1948, Rényi,1961] share the extensivity property: the joint entropy of a pair of independent random variables
equals the sum of the individual entropies. Abandoning this property yields the so-called nonextensive entropies [Havrda and Charvát, 1967, Lindhard, 1974, Lindhard and Nielsen, 1971, Tsallis,
1988], which have raised great interest among physicists in modeling certain phenomena (e.g.,long-range interactions and multifractals) and in the construction of a nonextensive generalizationof the classical Boltzmann-Gibbs statistical mechanics [Abe, 2006]. Nonextensive entropies havealso been recently used in signal/image processing [Li et al., 2006] and many other areas [GellMann and Tsallis, 2004]. The so-called Tsallis entropies [Havrda and Charvát, 1967, Tsallis, 1988]
form a parametric family of nonextensive entropies that includes the Shannon-Boltzmann-Gibbs
entropy as a particular case. Some attempts have been made to construct a nonextensive generalization of information theory [Furuichi, 2006].
Convexity is a key concept underlying several fundamental results in information theory, e.g.,
the non-negativity of the Kullback-Leibler (KL) divergence (also called relative entropy), namely
via the many implications of Jensen’s inequality [Cover and Thomas, 1991, Jensen, 1906]. Jensen’s
inequality also underlies the concept of Jensen-Shannon (JS) divergence, which is a symmetrized
and smoothed version of the KL divergence [Lin and Wong, 1990, Lin, 1991]. The JS divergence iswidely used in areas such as statistics, machine learning, image and signal processing, and physics.
In this paper, we introduce new extensions of JS-type divergences by generalizing its two pillars: convexity and Shannon’s entropy. These divergences are then used to define new informationtheoretic kernels between probability distributions. More specifically, our main contributions are:
• The concept of q-convexity, as a generalization of convexity, for which we prove a Jensen qinequality. The related concept of Jensen q-differences, which generalize Jensen differences,1

is also proposed. Based on these concepts, we introduce the Jensen-Tsallis q-difference, anonextensive generalization of the JS divergence, which is also a “mutual information” inthe sense of Furuichi [2006].
• Characterization of the Jensen-Tsallis q-difference, with respect to convexity and extrema,extending the work by Burbea and Rao [1982] and by Lin [1991] for the JS divergence.
• Definition of k-th order joint and conditional Jensen-Tsallis q-differences for families ofstochastic processes, and derivation of a chain rule.
• We propose a broad family of (nonextensive information theoretic) positive definite kernels,
which are interpretable as nonextensive mutual information kernels. This family ranges
from the Boolean to the linear kernels, and also includes the JS kernel proposed by Hein and
Bousquet [2005].
• We define a family of (nonextensive information theoretic) positive definite kernels between
stochastic processes, which subsume well-known string kernels like the p-spectrum kernel[Leslie et al., 2002].
• We extend results of Hein and Bousquet [2005] by proving positive definiteness of kernels
based on the unbalanced JS divergence. A connection between these new kernels and thosepreviously studied by Fuglede [2005] and by Hein and Bousquet [2005] is also established.
As a side note, we show that the parametrix approximation of the multinomial diffusion
kernel introduced by Lafferty and Lebanon [2005] is not positive definite in general.
The rest of the paper is organized as follows. Section 2 reviews the concepts of nonextensive
entropies, with emphasis on the Tsallis case. Section 3 introduces denormalization formulae forseveral entropies and divergences, to be used in later sections. Section 4 discusses Jensen differences and divergences. The concepts of q-differences and q-convexity are introduced in Section 5,
where they are used to define and characterize some new divergence-type quantities. In Section 6,
we define the Jensen-Tsallis q-difference and derive some of its properties; in that section, we also
define k-th order Jensen-Tsallis q-differences for families of stochastic processes. The new familyof entropic kernels is introduced and characterized in Section 7, after a brief review of some key results concerning positive definite kernels; that section also presents a brief review of string kernels,
and introduces nonextensive kernels between stochastic processes. Section 7 ends by proving thatthe parametrix approximation of the multinomial diffusion kernel is not positive definite. Section 8reports experiments on text categorization using both a bag-of-words and a sequential representation of documents. Finally, Section 9 contains concluding remarks and discusses directions for
future research.
Earlier and shorter versions of this work have appeared in Martins et al. [2008a] and Martinset al. [2008b].

2

2

Nonextensive entropies and Tsallis statistics

We start with a brief overview of nonextensive entropies. In what follows, R+ denotes the nonnegative reals, R++ denotes the strictly positive reals, and
(
n−1

∆

n

, (x1 , . . . , xn ) ∈ R |nX)

xi = 1, ∀i xi ≥ 0

(1)

i=1

denotes the (n − 1)-dimensional simplex.
Inspired by the Shannon-Khinchin axiomatic formulation of Shannon’s entropy [Khinchin,
1957, Shannon and Weaver, 1949], Suyari [2004] proposed an axiomatic framework for nonextensive entropies and a uniqueness theorem. Let q ≥ 0 be a fixed scalar, called the entropic index,
and let fq be a function defined on ∆n−1 . Consider the following set of axioms:(A1) Continuity: fq is continuous in ∆n−1 ;(A2) Maximality: For any q ≥ 0, n ∈ N, and (p1 , . . . , pn ) ∈ ∆n−1 ,fq (p1 , . . . , pn ) ≤ fq (1/n, . . . , 1/n);(A3) Generalized additivity: For i = 1, . . . , n, j = 1, . . . , mi , pij ≥ 0, and pi =Pmi

j=1 pij ,fq (p11 , . . . , pnmi ) = fq (p1 , . . . , pn ) +
!
n
X
pi1
pimi
q
,...,
;
pi fq
pi
pi
i=1
(A4) Expandability: fq (p1 , . . . , pn , 0) = fq (p1 , . . . , pn ).
The Suyari axioms (A1)-(A4) uniquely determine a function Sq,φ : ∆n−1 → R of the form(

Sq,φ (p1 , . . . , pn ) =Pk(1 − ni=1 pqi )φ(q)P−k ni=1 pi ln pi

if q 6= 1
if q = 1,(2)

where k is a positive constant, and φ : R+ → R is a continuous function that satisfies the following
three conditions:(i) φ(q) has the same sign as q−1;(ii) φ(q) vanishes if and only if q = 1;(iii) φ is differentiable in a neighborhood of 1 and φ0 (1) = 1.
Note that S1,φ = limq→1 Sq,φ , thus Sq,φ (p1 , . . . , pn ), seen as a function of q, is continuous at q =1. For any φ satisfying these conditions, Sq,φ has the pseudoadditivity property: for any two
independent random variables A and B, with probability mass functions pA ∈ ∆nA −1 and pB ∈3

∆nB −1 , respectively, consider the new random variable A ⊗ B defined by the joint distibutionpA ⊗ pB ∈ ∆nA nB −1 ; then,Sq,φ (A ⊗ B) = Sq,φ (A) + Sq,φ (B) −φ(q)Sq,φ (A)Sq,φ (B),kwhere we denote (as usual) Sq,φ (A) , Sq,φ (pA ).
For q = 1, Suyari’s axioms recover the Shannon-Boltzmann-Gibbs (SBG) entropy,
S1,φ (p1 , . . . , pn ) = H(p1 , . . . , pn ) = −knXpi ln pi ,

(3)

i=1

and pseudoadditivity turns into additivity, i.e., H(A ⊗ B) = H(A) + H(B) holds.
Several proposals for φ have appeared in the literature [Havrda and Charvát, 1967, Daróczy,
1970, Tsallis, 1988]. In the sequel, unless stated otherwise, we set φ(q) = q − 1, which yields theTsallis entropy:
!
n
X
k
q
1−
pi .
(4)
Sq (p1 , . . . , pn ) =q−1
i=1
To simplify, we let k = 1 and write the Tsallis entropy as
Sq (X) , Sq (p1 , . . . , pn ) = −X

p(x)q lnq p(x),

(5)

x∈X

where lnq (x) , (x1−q − 1)/(1 − q) is the q-logarithm function, which satisfies lnq (xy) = lnq (x) +x1−q lnq (y) and lnq (1/x) = −xq−1 lnq (x). This notation was introduced by Tsallis [1988].
Furuichi [2006] derived some information theoretic properties of Tsallis entropies. Tsallis joint
and conditional entropies are defined, respectively, as
Sq (X, Y ) , −X

p(x, y)q lnq p(x, y)

(6)

x,y

and
Sq (X|Y ) , −X

p(x, y)q lnq p(x|y) =Xx,yp(y)q Sq (X|y),(7)

yand the chain rule Sq (X, Y ) = Sq (X) + Sq (Y |X) holds.
For two probability mass functions pX , pY ∈ ∆n , the Tsallis relative entropy, generalizing the
KL divergence, is defined as
Dq (pX kpY ) , −Xx

pX (x) lnq

pY (x).
pX (x)(8)

Finally, the Tsallis mutual entropy is defined as
Iq (X; Y ) , Sq (X) − Sq (X|Y ) = Sq (Y ) − Sq (Y |X),(9)

generalizing (for q > 1) Shannon’s mutual information [Furuichi, 2006]. In Section 6, we establish
a relationship between Tsallis mutual entropy and a quantity called Jensen-Tsallis q-difference,4

generalizing the one between mutual information and the JS divergence (shown, e.g., by Grosse
et al. [2002], and recalled below, in Subsection 4.2).
Furuichi [2006] also mentions an alternative generalization of Shannon’s mutual information,
defined as
I˜q (X; Y ) , Dq (pX,Y kpX ⊗ pY ),(10)
where pX,Y is the true joint probability mass function of (X, Y ) and pX ⊗ pY denotes their joint
probability if they were independent. This alternative definition of a “Tsallis mutual entropy” hasalso been used by Lamberti and Majtey [2003]; notice that Iq (X; Y ) 6= I˜q (X; Y ) in general, thecase q = 1 being a notable exception. In Section 6, we show that this alternative definition also
leads to a nonextensive analogue of the JS divergence.

3

Entropies of unnormalized measures

In this section, we consider functionals that extend the domain of the Shannon-Boltzmann-Gibbs
and Tsallis entropies to include unnormalized measures. Although, as shown below, these functionals are completely characterized by their restriction to the normalized probability distributions,the denormalization expressions will play an important role in Section 7 to derive novel positive
definite kernels inspired by mutual informations.
In order to keep generality, whenever possible we do not restrict to finite or countable sample
spaces. Instead, we consider a measured space (X , M , ν) where X is Hausdorff and ν is a σ-finite
Radon measure. We denote by M+ (X ) the set of finite Radon ν-absolutely continuous measures
on X , and by M+1 (X ) the subset of those which are probability measures. For simplicity, we often
identify each measure in M+ (X ) or M+1 (X ) with its corresponding nonnegative density; this islegitimated by the Radon-Nikodym theorem, which guarantees the existence and uniqueness (upto equivalence within measure Rzero) of a density function f : X →R+ . In the sequel,LebesgueR
R
Stieltjes integrals of the form A f (x)dν(x) are often written as A f , or simply f, if A = X .
Unless otherwise stated, ν is the Lebesgue-Borel measure, if X ⊆ Rn and intX =6 ∅, or thecounting measure, if X is countable. In the latter case integrals can be seen as finite sums orinfinite series.

3.1

Denormalization of the Shannon-Boltzmann-Gibbs Entropy and the KL
Divergence

Define R , R ∪ {−∞, +∞}. For some functional G : M+ (X ) → R, let the set M+G (X ) ,{f ∈ M+ (X ) : |G(f )| < ∞} be its effective domain, and M+1,G (X ) , M+G (X ) ∩ M+1 (X ) be its
subdomain of probability measures.
The following functional [Cuturi and Vert, 2005], extends the Shannon-Boltzmann-Gibbs entropy from M+1,H to the unnormalized measures in M+H :H(f ) = −kZf ln f =5Z

ϕH ◦ f,(11)

where k > 0 is a constant, the function ϕH : R++ → R is defined as
ϕH (y) = −k y ln y,(12)and, as usual, 0 ln 0 , 0.
The generalized form of the KL divergence, often called generalized I-divergence [Csiszar,
1975], is a directed divergence between two measures µf , µg ∈ M+H (X ), such that µf is µg absolutely continuous (denoted µf  µg ). Let f and g be the densities associated with µf and µg ,respectively. In terms of densities, this generalized KL divergence isD(f, g) = kf
g − f + f ln
g

Z

!

.

(13)

Both functionals H and D are completely determined by their restriction to the normalizedmeasures, as the next proposition shows.
Proposition 1 The following equalities hold for any c ∈ R++ and f, g ∈ M+H (X ), with µf  µg :H(cf ) = c H(f ) + |f | ϕH (c),D(cf, cg) = c D(f, g),D(cf, g) = c D(f, g) − |f | ϕH (c) + k (1 − c) |g|,where |f | , f = µf (X ). Consider f ∈ M+H (X ) and g ∈ M+H (Y), and define f ⊗ g ∈
M+H (X × Y) as (f ⊗ g)(x, y) , f (x)g(y). Then,R

H(f ⊗ g) = |g| H(f ) + |f | H(g).
Naturally, if |f | = |g| = 1, we recover the additivity property of the Shannon-Boltzmann-Gibbs
entropy, H(f ⊗ g) = H(f ) + H(g).
Proof: Straightforward from (11) and (13).

3.2

Denormalization of Nonextensive Entropies
S

Let us now proceed similarly with the nonextensive entropies. For q ≥ 0, let M+q (X ) = {f ∈S
M+ (X ) : f q ∈ M+ (X )} for q 6= 1, and M+q (X ) = M+H (X ) for q = 1. The nonextensiveS
counterpart of (11), defined on M+q (X ), isZ

ϕq ◦ f,(14)

ϕH (y)
if q = 1,kq(y − y ) if q 6= 1,
φ(q)

(15)

Sq (f ) =where ϕq : R++ → R is given by(ϕq (y) =6

and φ : R+ → R satisfies conditions (i)-(iii) stated following equation (2). The Tsallis entropy is
obtained for φ(q) = q − 1,Z
Sq (f ) = −kf q lnq f.

(16)

Similarly, a nonextensive generalization of the generalized KL divergence (13) isk Z 
qf + (1 − q)g − f q g 1−q ,Dq (f, g) = −
φ(q)

(17)

for q 6= 1, and D1 (f, g) , limq→1 Dq (f, g) = D(f, g).
For |f | = |g| = 1, several particular cases are recovered: if φ(q) = 1 − 21−q , then Dq (f, g)
is the Havrda-Charvát or Daróczi relative entropy [Havrda and Charvát, 1967, Daróczy, 1970];
if φ(q) = q − 1, then Dq (f, g) is the Tsallis relative entropy (8); finally, if φ(q) = q(q − 1),then Dq (f, g) is the canonical α-divergence defined by Amari and Nagaoka [2001] in the realmof information geometry (with the reparameterization α = 2q − 1 and assuming q > 0 so thatφ(q) = q(q − 1) conforms with the axioms).
The following proposition generalizes Proposition 1 to the nonextensive case.
S

Proposition 2 The following equalities hold for any c ∈ R++ and f, g ∈ M+q (X ), with µf  µg :Sq (cf ) = cq Sq (f ) + |f |ϕq (c),Dq (cf, cg) = cDq (f, g),

(18)
(19)

Dq (cf, g) = cq Dq (f, g) − q ϕq (c)|f | +Sk(q − 1)(1 − cq )|g|.
φ(q)

(20)

φ(q)
Sq (f )Sq (g).
k

(21)

S

For any f ∈ M+q (X ) and g ∈ M+q (Y),Sq (f ⊗ g) = |g|Sq (f ) + |f |Sq (g) −If |f | = |g| = 1, we recover the pseudo-additivity property of nonextensive entropies:
Sq (f ⊗ g) = Sq (f ) + Sq (g) −φ(q)Sq (f )Sq (g).
k

Proof: Straightforward from (14) and (17).
For φ(q) = q − 1, Dq is the Tsallis relative entropy and (20) reduces to
Dq (cf, g) = cq Dq (f, g) − qϕq (c)|f | + k(1 − cq )|g|.

(22)

Naturally, all the equalities in Proposition 1 are obtained by taking the limit q → 1 in those of
Proposition 2.

7

4

Jensen Differences and Divergences

4.1

The Jensen Difference

Jensen’s inequality [Jensen, 1906] is at the heart of many important results in information theory.
Let E[.] denote the expectation operator. Jensen’s inequality states that if Z is an integrable randomvariable taking values in a set Z, and f is a measurable convex function defined on the convex hullof Z, thenf (E[Z]) ≤ E[f (Z)].
(23)
Burbea and Rao [1982] considered the scenario where Z is finite, and took f , −Hϕ , whereHϕ : [a, b]n → R is a concave function, called a ϕ-entropy, defined as
Hϕ (z) , −nXϕ(zi ),(24)

i=1

where ϕ : [a, b] → R is convex. They studied the Jensen differenceJϕπ (y1 , . . . , ym ) , HϕmX!

πt yt −

t=1m
X

πt Hϕ (yt ),

(25)

t=1

where π , (π1 , . . . , πm ) ∈ ∆m−1 , and each y1 , . . . , ym ∈ [a, b]n .
We consider here a more general scenario, involving two measured sets (X , M , ν) and (T , T , τ ),where the second is used to index the first.
Definition 3 Let µ , (µt )t∈T ∈ [M+ (X )]T be a family of measures in M+ (X ) indexed by T , andlet ω ∈ M+ (T ) be a measure in T . Define:JΨω (µ)

Z

, Ψ

T



ω(t) µt dτ (t) −ZTω(t)Ψ(µt ) dτ (t)(26)

where:(i) Ψ is a concave functional such that dom Ψ ⊆ M+ (X );(ii) ω(t)µt (x) is τ -integrable, for all x ∈ X ;
(iii)

R

T ω(t)µt dτ (t) ∈ dom Ψ;(iv) µt ∈ dom Ψ, for all t ∈ T ;(v) ω(t)Ψ(µt ) is τ -integrable.
If ω ∈ M+1 (T ), we still call (26) a Jensen difference.
In the following subsections, we consider several instances of Definition 3, leading to several
Jensen-type divergences.
84.2

The Jensen-Shannon DivergenceLet p be a random probability distribution taking values in {pt }t∈T according to a distribution
π ∈ M+1 (T ). (In classification/estimation theory parlance, π is called the prior distribution andpt , p(.|t) the likelihood function.) Then, (26) becomesJΨπ (p) = Ψ (E[p]) − E[Ψ(p)],(27)

where the expectations are with respect to π.
Let now Ψ = H, the Shannon-Boltzmann-Gibbs entropy. Consider the randomvariables T andR
X, taking values respectively in T and X , with densities π(t) and p(x) , T p(x|t)π(t). Using
standard notation of information theory [Cover and Thomas, 1991],πJ (p) ,JHπ (p)

Z

= H
T



π(t)pt −= H(X) −Z

Z
T

π(t)H(pt )π(t)H(X|T = t)T

= H(X) − H(X|T )= I(X; T ),(28)

where I(X; T ) is the mutual information between X and T . (This relationship between JS divergence and mutual information was pointed out by Grosse et al. [2002].) Since I(X; T ) is also
equal to the KL divergence between the joint distribution and the product of the marginals [Coverand Thomas, 1991], we haveJ π (p) = H (E[p]) − E[H(p)] = E[D(pkE[p])].

(29)

When X and T are finite with |T | = m, JHπ (p1 , . . . , pm ) is called the Jensen-Shannon (JS)divergence of p1 , . . . , pm , with weights π1 , . . . , πm [Burbea and Rao, 1982, Lin, 1991]. Equality(29) allows two interpretations of the JS divergence:• the Jensen difference of the Shannon entropy of p;• the expected KL divergence from p to the expectation of p.
A remarkable fact is that J π (p) = minr E[D(pkr)], i.e., r∗ = E[p] is a minimizer of E[D(pkr)]
with respect to r. It has been shown that this property together with equality (29) characterize theso-called Bregman divergences: they hold not only for Ψ = H, but for any concave Ψ and thecorresponding Bregman divergence, in which case JΨπ is the Bregman information [Banerjee et al.,2005].
When |T | = 2 and π = (1/2, 1/2), p may be seen as a random distribution whose value on{p1 , p2 } is chosen by tossing a fair coin. In this case, J (1/2,1/2) (p) = JS(p1 , p2 ), where
p1 + p2
H(p1 ) + H(p2 )JS(p1 , p2 ) , H
−
2
2




1
p1 + p21
p1 + p2= D p1+ D p2
,
2
2
2
2




9

(30)

√
as introduced by Lin [1991]. It has been shown that JS satisfies the triangle inequality (hence being a metric) and that, moreover, it is an Hilbertian metric1 [Endres and Schindelin, 2003, Topsøe,2000], which has motivated its use in kernel-based machine learning [Cuturi et al., 2005, Hein and
Bousquet, 2005] (see Section 7).

4.3

The Jensen-Rényi Divergence

Consider again the scenario above (Subsection 4.2), with the Rényi q-entropyZ
1
Rq (p) =ln p q1−q(31)

replacing the Shannon-Boltzmann-Gibbs entropy. It is worth noting that the Rényi and Tsallis
q-entropies are monotonically related through1Rq (p) = ln [1 + (1 − q)Sq (p)] 1−q ,(32)

or, using the q-logarithm function,
Sq (p) = lnq exp Rq (p).

(33)

The Rényi q-entropy is concave for q ∈ [0, 1) and has the Shannon-Boltzmann-Gibbs entropy
as the limit when q → 1. Letting Ψ = Rq , (27) becomes
JRπ q (p) = Rq (E[p]) − E[Rq (p)].

(34)

Unlike in the JS divergence case, there is no counterpart of equality (29) based on the Rényi qdivergenceZ1
ln pq1 p1−q
(35)
DRq (p1 kp2 ) =2 .
q−1
When X and T are finite, we call JRπ q in (34) the Jensen-Rényi (JR) divergence. Furthermore,when |T | = 2 and π = (1/2, 1/2), we write JRπ q (p) = JRq (p1 , p2 ), where

JRq (p1 , p2 ) = Rq

p1 + p2
Rq (p1 ) + Rq (p2 )
.
−
2
2


(36)

The JR divergence has been used in several signal/image processing applications, such as registration, segmentation, denoising, and classification [Ben-Hamza and Krim, 2003, He et al., 2003,
Karakos et al., 2007]. In Section 7, we show that the JR divergence is (like the JS divergence) an
Hilbertian metric, which is relevant for its use in kernel-based machine learning.
1

A metric d : X × X → R is Hilbertian if there is some Hilbert space H and an isometry f : X → H such thatd (x, y) = hf (x) − f (y), f (x) − f (y)iH holds for any x, y ∈ X [Hein and Bousquet, 2005].
2

10

4.4

The Jensen-Tsallis Divergence

Burbea and Rao [1982] have defined Jensen-type divergences of the form (27) based on the Tsallis
q-entropy Sq , defined in (16). Like the Shannon-Boltzmann-Gibbs entropy, but unlike the Rényi
entropies, the Tsallis q-entropy, for finite T , is an instance of a ϕ-entropy (see (24)). LettingΨ = Sq , (27) becomes
JSπq (p) = Sq (E[p]) − E[Sq (p)].
(37)
Again, like in Subsection 4.3, if we consider the Tsallis q-divergence,Z1
Dq (p1 kp2 ) =1 − p1 q p2 1−q ,
1−q




(38)

there is no counterpart of the equality (29).
When X and T are finite, JSπq in (37) is called the Jensen-Tsallis (JT) divergence and it has
also been applied in image processing [Ben-Hamza, 2006]. Unlike the JS divergence, the JT
divergence lacks an interpretation as a mutual information. Despite this, for q ∈ [1, 2], it exhibits
joint convexity [Burbea and Rao, 1982]. In the next section, we propose an alternative to the JT
divergence which, amongst other features, is interpretable as a nonextensive mutual information(in the sense of Furuichi [2006]) and is jointly convex, for q ∈ [0, 1].

5

q-Convexity and q-Differences

5.1

Introduction

This section introduces a novel class of functions, termed Jensen q-differences, which generalize Jensen differences. Later (in Section 6), use will these functions to define the Jensen-Tsallis
q-difference, which we will propose as an alternative nonextensive generalization of the JS divergence, instead of the JT divergence discussed in Subsection 4.4. We begin by recalling the conceptof q-expectation, used by Tsallis [1988] in nonextensive thermodynamics.
Definition 4 The unnormalized q-expectation of a random variable X, with probability density p,
isZ
Eq [X] , x p(x)q .
(39)
Of course, q = 1 corresponds to the standard notion of expectation. For q 6= 1, the qexpectation does not match the intuitive meaning of average/expectation (e.g., Eq [1] 6= 1, in
general). The q-expectation is a convenient concept in nonextensive information theory; e.g., ityields a very compact form for the Tsallis entropy: Sq (X) = −Eq [lnq p(X)].

5.2 q-Convexity
We now introduce the novel concept of q-convexity and use it to derive a set of results, namely the
Jensen q-inequality.
11Definition 5 Let q ∈ R and X be a convex set. A function f : X → R is q-convex if for any
x, y ∈ X and λ ∈ [0, 1],f (λx + (1 − λ)y) ≤ λq f (x) + (1 − λ)q f (y).

(40)

If −f is q-convex, f is said to be q-concave.
Of course, 1-convexity is the usual notion of convexity. The next proposition states the Jensen
q-inequality.
Proposition 6 If f : X → R is q-convex, then for any n ∈ N, x1 , . . . , xn ∈ X and π =(π1 , . . . , πn ) ∈ ∆n−1 ,
!
n
X

f

πi xi ≤

i=1

n
X
q

πi f (xi ).

(41)

i=1

Moreover, if f is continuous, the above still holds for countably many points (xi )i∈N .
Proof: In the finite case, the proof can be carried out trivially, by induction, exactly as in the
proof of the standard Jensen inequality [Cover and Thomas, 1991]. If f is continuous, it commuteswith taking limits, thus
f

∞
X
i=1

!

πi xi = f

lim
n→∞

n
X
i=1

!

πi xi = n→∞
lim f

n
X
i=1

!

πi xi ≤ n→∞
lim

n
X
q

∞
X
q

i=1

i=1

πi f (xi ) =πi f (xi ).

Proposition 7 Let f ≥ 0 and q ≥ r ≥ 0; then,f is q-convex
f is r-concave⇒ f is r-convex⇒ f is q-concave.

(42)
(43)

Proof: Implication (42) results fromf (λx + (1 − λ)y) ≤ λq f (x) + (1 − λ)q f (y) ≤ λr f (x) + (1 − λ)r f (y),where the first inequality states the q-convexity of f and the second one is valid because f (x), f (y) ≥0 and tr ≥ tq ≥ 0, for any t ∈ [0, 1] and q ≥ r. The proof of (43) is similar.

12

5.3

Jensen q-Differences

We now generalize Jensen differences, formalized in Definition 3, by introducing the concept ofJensen q-differences.
Definition 8 Let µ , (µt )t∈T ∈ [M+ (X )]T be a family of measures in M+ (X ) indexed by T , andlet ω ∈ M+ (T ) be a measure in T . For q ≥ 0, define
ω
Tq,Ψ
(µ)

Z

, Ψ

T



ω(t) µt dτ (t) −ZT

ω(t)q Ψ(µt ) dτ (t),(44)

where:(i) Ψ is a concave functional such that dom Ψ ⊆ M+ (X );(ii) ω(t) µt (x) is τ -integrable for all x ∈ X ;
(iii)

R

T ω(t) µt dτ (t) ∈ dom Ψ;(iv) µt ∈ dom Ψ, for all t ∈ T ;(v) ω(t)q Ψ(µt ) is τ -integrable.
If ω ∈ M+1 (T ), we call the function defined in (44) a Jensen q-difference.
Burbea and Rao [1982] established necessary and sufficient conditions on ϕ for the Jensen
difference of a ϕ-entropy (see (24)) to be convex. The following proposition generalizes that
result, extending it to Jensen q-differences.
Proposition 9 Let T and X be finite sets, with |T | = m and |X | = n, and let π ∈ M+1 (T ). Let
ϕ : [0, 1] → R be a function of class C 2 and consider the (ϕ-entropy [Burbea and Rao, 1982])Pπfunction Ψ : [0, 1]n → R defined as Ψ(z) , − ni=1 ϕ(zi ). Then, the q-difference Tq,Ψ: [0, 1]nm →R is convex if and only if ϕ is convex and −1/ϕ00 is (2 − q)-convex.
The proof is rather long, thus it is relegated to Appendix A.

6

The Jensen-Tsallis q-Difference

6.1

Definition

As in Subsection 4.2, let p be a random probability distribution taking values in {pt }t∈T according
to a distribution π ∈ M+1 (T ). Then, we may writeπTq,Ψ(p) = Ψ (E[p]) − Eq [Ψ(p)],

13

(45)

where the expectations are with respect to π. Hence Jensen q-differences may be seen as deformations of the standard Jensen differences (27), in which the second expectation is replaced by aq-expectation.
Let now Ψ = Sq , the nonextensive Tsallis q-entropy. Introducing the randomvariables T andR
X, with values respectively in T and X , with densities π(t) and p(x) , T p(x|t)π(t), we haveπ(writing Tq,S
simply as Tqπ )qTqπ (p) = Sq (E[p]) − Eq [Sq (p)]= Sq (X) −Z
T

π(t)q Sq (X|T = t)

= Sq (X) − Sq (X|T )= Iq (X; T ),(46)

where Sq (X|T ) is the Tsallis conditional entropy (7), and Iq (X; T ) is the Tsallis mutual information (9), as defined by Furuichi [2006]. Observe that (46) is a nonextensive analogue of (28).
Since, in general, Iq 6= I˜q (see (10)), unless q = 1 (in that case, I1 = I˜1 = I), there is no counterpart of (29) in terms of q-differences. Nevertheless, Lamberti and Majtey [2003] have proposed a
non-logarithmic version of the JS divergence, which corresponds to using I˜q for the Tsallis mutual
q-entropy (although this interpretation is not explicitally mentioned by those authors).
When X and T are finite with |T | = m, we call the quantity Tqπ (p1 , . . . , pm ) the JensenTsallis (JT) q-difference of p1 , . . . , pm with weights π1 , . . . , πm . Although the JT q-difference isa generalization of the JS divergence, for q 6= 1, the term “divergence” would be misleading inthis case, since Tqπ may take negative values (if q < 1) and does not vanish in general if p isdeterministic.
When |T | = 2 and π = (1/2, 1/2), define Tq , Tq1/2,1/2 ,p1 + p2
Sq (p1 ) + Sq (p2 )−.
2
2q
Notable cases arise for particular values of q:Tq (p1 , p2 ) = Sq

(47)

• For q = 0, S0 (p) = −1 + ν(supp(p)), where ν(supp(p)) denotes the measure of the supportof p (recall that p is defined on the measured space (X , M , ν)). For example, if X is finiteand ν is the counting measure, ν(supp(p)) = kpk0 is the so-called 0-norm (although it is nota norm) of vector p, i.e., its number of nonzero components. The Jensen-Tsallis 0-differenceis thus
p1 + p2
T0 (p1 , p2 ) = −1 + ν supp
+ 1 − ν (supp(p1 )) + 1 − ν (supp(p2 ))2= 1 + ν (supp(p1 ) ∪ supp(p2 )) − ν (supp(p1 )) − ν (supp(p2 ))= 1 − ν (supp(p1 ) ∩ supp(p2 )) ;(48)
if X is finite and ν is the counting measure, this becomesT0 (p1 , p2 ) = 1 − kp1

p2 k0 ,

(49)

where denotes the Hadamard-Schur (i.e., elementwise) product. We call T0 the Boolean
difference.
14

• For q = 1, since S1 (p) = H(p), T1 is the JS divergence,
T1 (p1 , p2 ) = JS(p1 , p2 ).

(50)• For q = 2, S2 (p) = 1 − hp, pi, where ha, bi = X a(x) b(x) dν(x) is the inner productP
between a and b (which reduces to ha, bi = i ai bi if X is finite and ν is the counting
measure). Consequently, the Tsallis 2-difference isR

T2 (p1 , p2 ) =1 1− hp1 , p2 i,
2 2

(51)

which we call the linear difference.

6.2

Properties of the JT q-differenceThis subsection presents results regarding convexity and extrema of the JT q-difference, for several
values of q, extending known properties of the JS divergence (q = 1). Some properties of the JS
divergence are lost in the transition to nonextensivity; e.g., while the former is nonnegative andvanishes if and only if all the distributions are identical, this is not true in general with the JT
q-difference. Nonnegativity of the JT q-difference is only guaranteed if q ≥ 1, which explains why
some authors (e.g., Furuichi [2006]) only consider values of q ≥ 1, when looking for nonextensive
analogues of Shannon’s information theory. Moreover, unless q = 1, it is not generally true thatTqπ (p, . . . , p) = 0 or even that Tqπ (p, . . . , p, p0 ) ≥ Tqπ (p, . . . , p, p). For example, the solution of the
optimization problem
minn Tq (p1 , p2 ),
(52)
p1 ∈∆

is, in general, different from p2 , unless q = 1. Instead, this minimizer is closer to the uniform
distribution if q ∈ [0, 1), and closer to a degenerate distribution, for q ∈ (1, 2] (see Fig. 1). This
is not so surprising: recall that T2 (p1 , p2 ) = 21 − 12 hp1 , p2 i; in this case, (52) becomes a linear
program, and the solution is not p2 , but p∗1 = δj , where j = arg maxi p2i .
We start by recalling a basic result, which essentially confirms that Tsallis entropies satisfy oneof the Suyari axioms (see Axiom A2 in Section 1), which states that entropies should be maximized
by uniform distributions.
Proposition 10 Let X be a finite set. The uniform distribution maximizes the Tsallis entropy for
any q ≥ 0.
Proof: Consider the problemmax
Sq (p), subject topi pi = 1 and pi ≥ 0.

P

Equating the gradient of the Lagrangian to zero yields
P∂(Sq (p) + λ( i pi − 1)) = −q(q − 1)−1 pq−1
+ λ = 0,i∂pi

for all i. Since all these equations are identical, the solution is the uniform distribution, which is a
maximum, due to the concavity of Sq .
15

Jensen Tsallis q−Difference to a fixed Bernoulli (p =0.3)
00.6
q=0.25
q=0.5
q=1
q=1.5
q=2

0.4

0.2

JTqD

0

−0.2

−0.4

−0.6

−0.8

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

p

Figure 1: Jensen-Tsallis q-difference between two Bernoulli distributions, p1 = (0.3, 0.7) and
p2 = (p, 1 − p), for several values of the entropic index q. Observe that, for q ∈ [0, 1), theminimizer of the JT q-difference approaches the uniform distribution (0.5, 0.5) as q approaches 0;
for q ∈ (1, 2], this minimizer approaches the degenerate distribution, as q → 2.
The next corollary of Proposition 9 establishes the joint convexity of the JT q-difference, forq ∈ [0, 1]. (Interestingly, this “complements” the joint convexity of the JT divergence (37), forq ∈ [1, 2], which was proved by Burbea and Rao [1982].)
Corollary 11 Let T and X be finite sets with cardinalities m and n, respectively. For q ∈ [0, 1], the1,S(i)
JT q-difference is a jointly convex function on M+ q (X ). Formally, let {pt }t∈T , and i = 1, . . . , l,be a collection of l sets of probability distributions on X ; then, for any (λ1 , . . . , λl ) ∈ ∆l−1 ,
Tqπ

l
X

l
X
(i)
λi p 1 , . . . ,λi p(i)
m
i=1
i=1

!

≤

l
X

(i)

λi Tqπ (p1 , . . . , p(i)
m ).

i=1

Proof: Observe that the Tsallis entropy (5) of a probability distribution pt = {pt1 , ..., ptn }can be written asnXx − xqSq (pt ) = −ϕ(pti ), where ϕq (x) =
;
1−q
i=1
thus, from Proposition 9, Tqπ is convex if and only if ϕq is convex and −1/ϕ00q is (2 − q)-convex.
Since ϕ00q (x) = q xq−2 , ϕq is convex for x ≥ 0 and q ≥ 0. To show the (2 − q)-convexity16

of −1/ϕ00q (x) = −(1/q)x2−q , for xt ≥ 0, and q ∈ [0, 1], we use a version of the power meaninequality [Steele, 2006],
−

l
X

!2−q

λi x i

≤−

l
X

2−q

(λi xi )

=−

λi

xi

,

i=1

i=1

i=1

l
X
2−q 2−qthus concluding that −1/ϕ00q is in fact (2 − q)-convex.
The next corollary, which results from the previous one, provides an upper bound for the JT
q-difference, for q ∈ [0, 1]. (Notice that this result is weaker than that of Proposition 13 below.)
Corollary 12 Let X , T and q be as in Corollary 11. Then, Tqπ (p1 , . . . , pm ) ≤ Sq (π).
Proof: From Corollary 11, for q ∈ [0, 1], Tqπ (p1 , . . . , pm ) is convex. Since its domain is aconvex polytope (the cartesian product of m simplices), its maximum occurs on a vertex, i.e., wheneach argument pt is a degenerate distribution at xt , denoted δxt . In particular, if |X | ≥ |T |, thismaximum occurs at the vertex corresponding to disjoint degenerate distributions, i.e., such thatxi 6= xj if i 6= j. At this maximum,
Tqπ (δx1 , . . . , δxm )

= Sq
= Sq

m
X
t=1
m
X

!

πt δxt −m
X

πt Sq (δxt )t=1!

πt δxt(53)

t=1= Sq (π)(54)

where the equality in (53) results from Sq (δxt ) = 0. Notice that this maximum may not be achieved
if |X | < |T |.
The next proposition (proved in Appendix B) establishes (upper and lower) bounds for the JT
q-difference, extending Corollary 12 to any non-negative q and to countable X and T .
Proposition 13 Let T and X be countable sets. For q ≥ 0,
Tqπ (p1 , . . . , pm ) ≤ Sq (π),(55)

and, if |X | ≥ |T |, the maximum is reached for a set of disjoint degenerate distributions. As in
Corollary 12, this maximum may not be attained if |X | < |T |.
For q ≥ 1,
Tqπ (p1 , . . . , pm ) ≥ 0,(56)
and the minimum is attained in the purely deterministic case, i.e., when all distributions are equal
to same degenerate distribution.
For q ∈ [0, 1] and X a finite set with |X | = n,Tqπ (p1 , . . . , pm ) ≥ Sq (π)[1 − n1−q ].
This lower bound (which is zero or negative) is attained when all distributions are uniform.
17

(57)

Finally, the next proposition characterizes the convexity/concavity of the JT q-difference.
Proposition 14 Let T and X be countable sets. The JT q-difference is convex in each argument,
for q ∈ [0, 2], and concave in each argument, for q ≥ 2.
Proof: Notice that the JT q-difference can be written as Tqπ (p1 , . . . , pm ) =Pj ψ(p1j , . . . , pmj ),

with
q
X
X
X q q
1
q
πi yi
.
πi yi −
ψ(y1 , . . . , ym ) =(πi − πi )yi +
q−1 i
i
i

! #

"

It suffices to consider the second derivative of ψ with respect to y1 . Introducing z =Pm

i=2 πi yi ,

h
i
∂2ψ
q q−2
2
q−2
=
q
π
y
−
π
(π
y
+
z)
1
1
1 1
1
∂y12
h

i

= q π12 (π1 y1 )q−2 − (π1 y1 + z)q−2 .

(58)

Since π1 y1 ≤ (π1 y1 + z) ≤ 1, the quantity in (58) is nonnegative for q ∈ [0, 2] and non-positivefor q ≥ 2.

6.3

Joint and conditional JT q-differences and a chain ruleThis subsection introduces joint and conditional JT q-differences, which will later be used as acontrast measure between stochastic processes. A chain rule is derived that relates conditional andjoint JT q-differences.
Definition 15 Let X , Y and T be measured sets. Let (pt )t∈T ∈ [M+1 (X × Y]T be a family of
measures in M+1 (X × Y) indexed by T , and let p be a random probability distribution taking
values in {pt }t∈T according to a distribution π ∈ M+1 (T ). Consider also:• for each t ∈ T , the marginals pt (Y ) ∈ M+1 (Y),• for each t ∈ T and y ∈ Y, the conditionals pt (X|Y = y) ∈ M+1 (X ),• the mixture r(X, Y ) , T π(t) pt (X, Y ) ∈ M+1 (X × Y),R• the marginal r(Y ) ∈ M+1 (Y),• for each y ∈ Y, the conditionals r(X|Y = y) ∈ M+1 (X ).
For notational convenience, we also append a subscript to p to emphasize its joint or conditional
dependency of the random variables X and Y , i.e., pXY , p, and pX|Y denotes a random conditional probability distribution taking values in {pt (.|Y )}t∈T according to the distribution π.
For q ≥ 0, we call joint JT q-difference of pXY to
Tqπ (pXY ) , Tqπ (p) = Sq (r) − Eq,T ∼π(T ) [Sq (pt )]
18

(59)

and conditional JT q-difference of pX|Y tohiTqπ (pX|Y ) , Eq,Y ∼r(Y ) [Sq (r(.|Y = y))] − Eq,T ∼π(T ) Eq,Y ∼pt (Y ) [Sq (pt (.|Y = y))] ,(60)

where we appended the random variables being used in each q-expectation, for the sake of clarity.
Note that the joint JT q-difference is just the usual JT q-difference of the joint random variable
X × Y , which equals (cf. (46))
Tqπ (pXY ) = Sq (X, Y ) − Sq (X, Y |T ) = Iq (X × Y ; T ),(61)

and the conditional JT q-difference is nothing but the usual JT q-difference with all entropies
replaced by conditional entropies (conditioned on Y ). Indeed, expression (60) can be rewritten as:
Tqπ (pX|Y ) = Sq (X|Y ) − Sq (X|T, Y ) = Iq (X; T |Y ),(62)i.e., the conditional JT q-difference may also interpreted as a Tsallis mutual information, as in (46),but now conditioned on the random variable Y .
Note also that, for q = 1 (the extensive case), (60) may also be rewritten in terms of theconditional KL divergences,hi

J π (pX|Y ) , T1π (pX|Y ) = EY ∼r(Y ) [H(r(.|Y = y))] − ET ∼π(T ) EY ∼pt (Y ) [H(pt (.|Y = y))]hi

= ET ∼π(T ) EY ∼r(Y ) [D(pt (.|Y = y)kr(.|Y = y))] .

(63)

Proposition 16 The following chain rule holds:
Tqπ (pXY ) = Tqπ (pX|Y ) + Tqπ (pY )(64)

Proof: Writing the joint/conditional JT q-differences as joint/conditional mutual informations(61)-(62) and invoking the chain rule provided by (7), we have that
I(X; T |Y ) + I(Y ; T ) = H(X|T, Y ) − H(X|Y ) + H(Y |T ) − H(Y )= H(X, Y |T ) − H(X, Y ),(65)

which is the joint JT q-difference associated with the random variable X × Y .
Let us now turn our attention to the case where Y = X k for some k ∈ N. In the following, thenotation (An )n∈N denotes a stationary ergodic process with values on some finite alphabet A.
Definition 17 Let X and T be measured sets, with X finite, and let F = [(Xn )n∈N ]T be a familyof stochastic processes (taking values on the alphabet X ) indexed by T . The k-th order JT qdifference of F is defined, for k = 1, . . . , n, as
joint,πTq,k(F ) , Tqπ (pX k )(66)

and the k-th order conditional JT q-difference of F is defined, for k = 1, . . . , n, as
cond,πTq,k(F ) , Tqπ (pX|X k ),joint,πcond,πand, for k = 0, as Tq,0
(F ) , Tq,1
(F ) = Tqπ (pX ).

19

(67)

Proposition 18 The joint and conditional k-th order JT q-differences are related through:joint,πTq,k(F ) =

k−1
X

cond,π
Tq,i
(F )

(68)

i=0

Proof: Use Proposition 16 and induction.

6.4

Asymptotic Analysis in the Extensive Case

We now focus on the extensive case (q = 1) for a brief asymptotic analysis of the k-th orderjoint and conditional JT 1-differences (or conditional Jensen-Shannon divergences) when k goesto infinity.
The conditional Jensen-Shannon divergence was introduced by El-Yaniv et al. [1998] to address
the two-sample problem for strings emitted by Markovian sources. Given two strings s and t, thegoal is to decide whether they were emitted by the same source or by different sources. Under
some fair assumptions, the most likely k-th order Markovian joint source of s and t is governed bya distribution r̂ given byr̂ = arg minλD(p̂s kr) + (1 − λ)D(p̂t kr).
r

(69)

where D(.k.) are conditional KL divergences, p̂s and p̂t are the empirical (k − 1)-th order conditionals associated with s and t, respectively, and λ = |s|/(|s| + |t|) is the length ratio. The solutionof the optimization problem isr̂(a|c) =(1 − λ) p̂t (c)λ p̂s (c)p̂s (a|c) +p̂t (a|c),
λ p̂s (c) + (1 − λ) p̂t (c)λ p̂s (c) + (1 − λ) p̂t (c)(70)

where a ∈ A is a symbol and c ∈ Ak−1 is a context; this can be rewritten as r̂(a, c) = λp̂s (a, c) +(1 − λ)p̂t (a, c); i.e., the optimum in (69) is a mixture of p̂s and p̂t weighted by the string lengths.
Notice that, at the minimum, we havecond,(λ,1−λ)D(p̂s kr̂) + (1 − λ)D(p̂t kr̂) = JSk(p̂s , p̂t ).

(71)

It is tempting to investigate the asymptotic behavior of the conditional and joint JS divergences,when k → ∞; however, unlike other asymptotic information theoretic quantities, like the entropy
rate or the cross entropy rate, this behavior fails to characterize the sources s and t. Intuitively, thisis justified by the fact that observing more and more symbols drawn from the mixture of the twosources rapidly decreases the uncertainty about which source generated the sample. Indeed, fromthe asymptotic equipartition property of stationary ergodic sources [Cover and Thomas, 1991], wehave that limk→∞ k1 H(pXk ) = limk→∞ H(pX|Xk ), which implies
1 joint,π1
JSk≤ lim H(π) = 0,
(72)
k→∞ k
k→∞ k
k→∞
where we used the fact that the JS divergence is upper-bounded by the entropy of the mixture
H(π) (see Proposition 13). Since the conditional JS divergence must be non-negative, we therefore
conclude that limk→∞ JSkcond,π = 0, pointwise.
lim JSkcond,π = lim

20

7

Nonextensive mutual information kernels

7.1

Introduction

In this section we consider the application of extensive and nonextensive entropies to define kernels on measures; since kernels involve pairs of measures, throughout this section |T | = 2. Basedon the denormalization formulae presented in Section 3, we devise novel kernels related to the JS
divergence and the JT q-difference; these kernels allow setting a weight for each argument, thus
will be called weighted Jensen-Tsallis kernels. We also introduce kernels related to the JR divergence (Subsection 4.3) and the JT divergence (Subsection 4.4), and establish a connection between
the Tsallis kernels and a family of kernels investigated by Hein et al. [2004] and Fuglede [2005],
placing those kernels under a new information-theoretic light. After that, we give a brief overview
of string kernels, and using the results of Subsection 6.3, we devise k-th order Jensen-Tsallis kernels between stochastic processes that subsume the well-known p-spectrum kernel of Leslie et al.
[2002]. Finally, we show that the parametrix approximation of the multinomial diffusion kernel,
proposed by Lafferty and Lebanon [2005], is not positive definite in general.

7.2

Positive and negative definite kernels

We start by recalling basic concepts from kernel theory [Schölkopf and Smola, 2002]; in the following, X denotes a nonempty set.
Definition 19 Let ϕ : X × X → R be a symmetric function, i.e., a function satisfying ϕ(y, x) =ϕ(x, y), for all x, y ∈ X . ϕ is called a positive definite (pd) kernel if and only ifn XnXci cj ϕ(xi , xj ) ≥ 0(73)

i=1 j=1

for all n ∈ N, xi , . . . , xn ∈ X and ci , . . . , cn ∈ R.
Definition 20 Let ψ : X × X → R be symmetric. ψ is called a negative definite (nd) kernel if andonly ifn XnX

ci cj ψ(xi , xj ) ≤ 0(74)

i=1 j=1

for all n ∈ N, xi , . . . , xn ∈ X and ci , . . . , cn ∈ R, satisfying the additional constraint c1 +. . . + cn = 0. In this case, −ψ is called conditionally pd; obviously, positive definiteness implies
conditional positive definiteness.
The sets of pd and nd kernels are both closed under pointwise sums/integrations, the former
being also closed under pointwise products; moreover, both sets are closed under pointwise convergence. While pd kernels “correspond” to inner products via embedding in a Hilbert space, nd
kernels that vanish on the diagonal and are positive anywhere else, “correspond” to squared Hilbertian distances. These facts, and the following propositions and lemmas, are shown in Berg et al.
[1984].
21

Proposition 21 Let ψ : X × X → R be a symmetric function, and x0 ∈ X . Let ϕ : X × X → R
be given by
ϕ(x, y) = ψ(x, x0 ) + ψ(y, x0 ) − ψ(x, y) − ψ(x0 , x0 ).
(75)
Then, ϕ is pd if and only if ψ is nd.
Proposition 22 The function ψ : X × X → R is a nd kernel if and only if exp(−tψ) is pd for allt > 0.
Proposition 23 The function ψ : X × X → R+ is a nd kernel if and only if (t + ψ)−1 is pd for allt > 0.
Lemma 24 If ψ is nd and nonnegative on the diagonal, i.e., ψ(x, x) ≥ 0 for all x ∈ X , then soare ψ α , for α ∈ [0, 1], and ln(1 + ψ).
Lemma 25 If f : X → R satisfies f ≥ 0, then, for α ∈ [1, 2], the function ψα (x, y) = −(f (x) +f (y))α is a nd kernel.
The following definition [Berg et al., 1984] has been used in a machine learning context by
Cuturi and Vert [2005].
Definition 26 Let (X , +) be a semigroup.2 A function ϕ : X → R is called pd (in the semigroupsense) if k : X × X → R, defined as k(x, y) = ϕ(x + y), is a pd kernel. Likewise, ϕ is called nd
if k is a nd kernel. Accordingly, these are called semigroup kernels.

7.3

Jensen-Shannon and Tsallis kernels

The basic result that allows deriving pd kernels based on the JS divergence and, more generally,on the JT q-difference, is the fact that the denormalized Tsallis q-entropies (14) are nd functions
S
on M+q (X ), for q ∈ [0, 2]. Of course, this includes the denormalized Shannon-Boltzmann-Gibbs
entropy (11) as a particular case, corresponding to q = 1. Although part of the proof was given
by Berg et al. [1984] (and by Topsøe [2000] and Cuturi and Vert [2005] for the Shannon entropycase), we present a complete proof here.
S

Proposition 27 For q ∈ [0, 2], the denormalized Tsallis q-entropy Sq is a nd function on M+q (X ).
Proof: Since nd kernels are closed under pointwise integration, it suffices to prove that ϕq(see (15)) is nd on R+ . For q 6= 1, ϕq (y) = (q − 1)−1 (y − y q ). Let’s consider two cases separately:
if q ∈ [0, 1), ϕq (y) equals a positive constant times −ι + ιq , where ι(y) = y is the identity map
defined on R+ . Since the set of nd functions is closed under sums, we only need to show that both−ι and ιq are nd. Both ι and −ι are nd, as can easily be seen from the definition; besides, since ι isnd and nonnegative, Lemma 24 guarantees that ιq is also nd. For the second case, where q ∈ (1, 2],2

Recall that (X , +) is a semigroup if + is a binary operation in X that is associative and has an identity element.

22

ϕq (y) equals a positive constant times ι − ιq . It only remains to show that −ιq is nd for q ∈ (1, 2]:Lemma 25 guarantees that the kernel k(x, y) = −(x + y)q is nd; therefore −ιq is a nd function.
For q = 1, we use the fact that,x − xq= lim ϕq (x),q→1 q − 1q→1

ϕ1 (x) = ϕH (x) = −x ln x = lim

where the limit is obtained by L’Hôpital’s rule; since the set of nd functions is closed under limits,
ϕ1 (x) is nd.
The following lemma [Berg et al., 1984] will also be needed below.
Lemma 28 The function ζq : R++ → R, defined as ζq (y) = y −q is pd, for q ∈ [0, 1].
Proof: We need to show that kq (x, y) : R++ × R++ → R, defined as kq (x, y) = ζq (x + y),is pd, for q ∈ [0, 1]. The proof results from observing thatkq (x, y) = (x + y)−q = lim+ [t + (x + y)q ]−1 ,

(76)

t→0

which is always well defined because x + y > 0, combined with the following facts: from
Lemma 24, since (x, y) 7→ x + y is nd and nonnegative, (x, y) 7→ (x + y)q is nd; from Proposition 23, (x, y) 7→ [t + (x + y)q ]−1 is pd for any t > 0; the set of pd kernels is closed under limits.
We are now in a position to present the main contribution of this section, which is a family of
weighted Jensen-Tsallis kernels, generalizing the JS-based (and other) kernels in two ways:• they allow using unnormalized measures; equivalently, they allow using different weights
for each of the two arguments;• they extend the mutual information feature of the JS kernel to the nonextensive scenario.

S

S

Definition 29 (weighted Jensen-Tsallis kernels) The kernel keq : M+q (X ) × M+q (X ) → R is
defined as
keq (µ1 , µ2 ) , keq (ω1 p1 , ω2 p2 )=Sq (π) − Tqπ (p1 , p2 ) (ω1 + ω2 )q ,where p1 = µ1 /ω1 and p2 = µ2 /ω2 are the normalized counterparts of µ1 and µ2 , with corresponding masses ω1 , ω2 ∈ R+ , and π = (ω1 /(ω1 + ω2 ), ω2 /(ω1 + ω2 )).
2S
The kernel kq : M+q (X ) \ {0} → R is defined askq (µ1 , µ2 ) , kq (ω1 p1 , ω2 p2 ) = Sq (π) − Tqπ (p1 , p2 ).
23

Recalling (46), notice that Sq (π) − Tqπ (p1 , p2 ) = Sq (T ) − Iq (X; T ) = Sq (T |X) can be interpreted as the Tsallis posterior conditional entropy. Hence, kq can be seen (in Bayesian classification terms) as a nonextensive expected measure of uncertainty in correctly identifying the class,given the prior π = (π1 , π2 ), and a random sample from the mixture distribution π1 p1 + π2 p2 . The
more similar the two distributions are, the greater this uncertainty.
Proposition 30 The kernel keq is pd, for q ∈ [0, 2]. The kernel kq is pd, for q ∈ [0, 1].
Proof: With µ1 = ω1 p1 and µ2 = ω2 p2 and using the denormalization formula of Proposition 2, we obtain keq (µ1 , µ2 ) = −Sq (µ1 + µ2 ) + Sq (µ1 ) + Sq (µ2 ). Now invoke Proposition 21 with
ψ = Sq (which is nd by Proposition 27), x = µ1 , y = µ2 , and x0 = 0 (the null measure). Observe
now that kq (µ1 , µ2 ) = keq (µ1 , µ2 )(ω1 + ω2 )−q . Since the product of two pd kernels is a pd kerneland (Proposition 28) (ω1 + ω2 )−q is a pd kernel, for q ∈ [0, 1], we conclude that kq is pd.
As we can see, the weighted Jensen-Tsallis kernels have two inherent properties: they areparameterized by the entropic index q and they allow their arguments to be unbalanced, i.e., tohave different weights ωi . We now mention some instances of kernels where each of these degrees
of freedom is suppressed. We start by the following subfamily of kernels, obtained by setting
q = 1.
Definition 31 (weighted Jensen-Shannon kernels) The kernel keWJS : (M+H (X ))2 → R is defined as keWJS , ke1 , i.e.,
keWJS (µ1 , µ2 ) = keWJS (ω1 p1 , ω2 p2 )= (H(π) − J π (p1 , p2 )) (ω1 + ω2 ),where p1 = µ1 /ω1 and p2 = µ2 /ω2 are the normalized counterpart of µ1 and µ2 , and π =(ω1 /(ω1 + ω2 ), ω2 /(ω1 + ω2 )).
2Analogously, the kernel kWJS : M+H (X ) \ {0} → R is simply kWJS , k1 , i.e.,
kWJS (µ1 , µ2 ) = kWJS (ω1 p1 , ω2 p2 ) = H(π) − J π (p1 , p2 ).

Corollary 32 The weighted Jensen-Shannon kernels keWJS and kWJS are pd.
Proof: Invoke Proposition 30 with q = 1.
The following family of weighted exponentiated JS kernels, generalize the so-called exponentiated JS kernel, that has been used, and shown to be pd, by Cuturi and Vert [2005].
Definition 33 (Exponentiated JS kernel) The kernel k EJS : M+1 (X ) × M+1 (X ) → R is defined,
for t > 0, as
k EJS (p1 , p2 ) = exp [−t JS (p1 , p2 )] .
(77)
24

Definition 34 (Weighted exponentiated JS kernels) The kernel kWEJS : M+H (X ) × M+H (X ) →R is defined, for t > 0, as
kWEJS (µ1 , µ2 ) = exp[t kWJS (µ1 , µ2 )]= exp(t H(π)) exp [−tJ π (p1 , p2 )] .

(78)

Corollary 35 The kernels k WEJS are pd. In particular, k EJS is pd.
Proof: Results from Proposition 22 and Corollary 32. Notice that although kWEJS is pd,
none of its two exponential factors in (78) is pd.
We now keep q ∈ [0, 2] but consider the weighted JT kernel family restricted to normalizedmeasures, kq |(M+1 (X ))2 . This corresponds to setting uniform weights (ω1 = ω2 = 1/2); note that inthis case keq and kq collapse into the same kernel,
keq (p1 , p2 ) = kq (p1 , p2 ) = lnq (2) − Tq (p1 , p2 ).

(79)

Proposition 30 guarantees that these kernels are pd for q ∈ [0, 2]. Remarkably, we recover threewell-known particular cases for q ∈ {0, 1, 2}. We start by the Jensen-Shannon kernel, introduced
and shown to be pd by Hein et al. [2004]; it is a particular case of a weighted Jensen-Shannon
kernel in Definition 31.
Definition 36 (Jensen-Shannon kernel) The kernel kJS : M+1 (X ) × M+1 (X ) → R is defined askJS (p1 , p2 ) = ln 2 − JS(p1 , p2 ).

Corollary 37 The kernel kJS is pd.
Proof: kJS is the restriction of kWJS to M+1 (X ) × M+1 (X ).
Finally, we study two other particular cases of the family of Tsallis kernels: the Boolean andlinear kernels.
Definition 38 (Boolean kernel) Let the kernel kBool : M+S0 ,1 (X ) × M+S0 ,1 (X ) → R be defined as
kBool = k0 , i.e.,kBool (p1 , p2 ) = ν (supp(p1 ) ∩ supp(p2 )) ,(80)
i.e., kBool (p1 , p2 ) equals the measure of the intersection of the supports (cf. the result (48)). In
particular, if X is finite and ν is the counting measure, the above may be written as
kBool (p1 , p2 ) = kp1
25

p2 k0 .

(81)

Definition 39 (Linear kernel) Let the kernel klin : M+S2 ,1 (X ) × M+S2 ,1 (X ) → R be defined as
klin (p1 , p2 ) =1
hp1 , p2 i.
2(82)Corollary 40 The kernels kBool and klin are pd.
Proof: Invoke Proposition 30 with q = 0 and q = 2. Notice that, for q = 2, we just recover
the well-known property of the inner product kernel [Schölkopf and Smola, 2002], which is equal
to klin up to a scalar.
In conclusion, the Boolean kernel, the Jensen-Shannon kernel, and the linear kernel, are simply
particular elements of the much wider family of Jensen-Tsallis kernels, continuously parameterizedby q ∈ [0, 2]. Furthermore, the Jensen-Tsallis kernels are a particular subfamily of the even wider
set of weighted Jensen-Tsallis kernels.
One of the key features of our generalization is that the kernels are defined on unnormalizedmeasures, with arbitrary mass. This is relevant, for example, in applications of kernels on empiricalmeasures (e.g., word counts, pixel intensity histograms); instead of the usual step of normalization[Hein et al., 2004], we may leave these empirical measures unnormalized, thus allowing objectsof different size (e.g., total number of words in a document, total number of image pixels) to beweighted differently. Another possibility opened by our generalization is the explicit inclusion ofweights: given two normalized measures, they can be multiplied by arbitrary (positive) weights
before being fed to the kernel function.

7.4

Other kernels based on Jensen differences and q-differences

It is worth noting that the Jensen-Rényi and the Jensen-Tsallis divergences also yield positive
definite kernels, albeit there are not any obvious “weighted generalizations” like the ones presented
above for the Tsallis kernels.
Proposition 41 (Jensen-Rényi and Jensen-Tsallis kernels) For any q ∈ [0, 2], the kernel(p1 , p2 ) 7→ Sq



p1 + p22

and the (unweighted) Jensen-Tsallis divergence JSq (37) are nd kernels on M+1 (X ) × M+1 (X ).
Also, for any q ∈ [0, 1], the kernel(p1 , p2 ) 7→ Rq

p1 + p22

and the (unweighted) Jensen-Rényi divergence JRq (34) are nd kernels on M+1 (X ) × M+1 (X ).
26

2
Proof: The fact that (p1 , p2 ) 7→ Sq ( p1 +p) is nd results from the embedding x 7→ x/2
2
Sq (p1 )+Sq (p2 )is trivially nd, we have that JSq is a sumof ndand Proposition 27. Since (p1 , p2 ) 7→2


p1 +p2functions, which turns it nd. To prove the negative definiteness of the kernel (p1 , p2 ) 7→ Rq,
2notice first that the kernel (x,y) 7→ (x + y)/2 is clearly nd. From Lemma 24 and integrating,R  p1 +p2 q
we have that (p1 , p2 ) 7→
is nd for q ∈ [0, 1]. From the same lemma we have that2(p1 , p2 ) 7→ ln t +R  p1 +p2 q 

p1 +p22

 2

is nd for any t > 0. Since

R  p1 +p2 q
2> 0, the nonnegativity offollows by taking the limit t → 0. By the same argument as above, we(p1 , p2 ) 7→ Rq
conclude that JRq is nd.
As a consequence, we have from Lemma 22 that the following kernels are pd for any t > 0:k̃EJR (p1 , p2 ) = exp −tRqp1 + p2
2



Z 

=

p1 + p22

q − t

1−q

,

(83)

and its “normalized” counterpart,R 

kEJR (p1 , p2 ) = exp(−tJRq (p1 , p2 )) =  qR  t
p1 +p2 q − 1−q2
pq1 pq2

.

R

(84)

Although we could have derived its positive definiteness without ever referring the Rényi entropy,
the latter has in fact a suggestive interpretation: it corresponds to an exponentiation of the JensenRényi divergence; it generalizes the case q = 1 which corresponds to the exponentiated JensenShannon kernel.
Finally, we point out a relationship between the Jensen-Tsallis divergences (Subsection 4.4)
and a family of difference kernels introduced by Fuglede [2005],
ψα,β (x, y) = α
x + y α 1/α2xβ + y β
−
2

!1/β

.

(85)

Fuglede [2005] derived the negative definiteness of the above family of kernels provided 1 ≤ α ≤∞ and 1/2 ≤ β ≤ α; he went further by
providing representations for these kernels. Hein et al.
R[2004] used the fact that the integration ψα,β (x(t), y(t))dτ (t) is also nd to derive a family of pd
kernels for probability measures that included the Jensen-Shannon kernel.
We start by noting the following property of the extended Tsallis entropy, that is very easy toestablish:
Sq (µ) = q −1 S1/q (µq )(86)
As a consequence, we have that

JSq (y1 , y2 ) = Sq

Sq (y1 ) + Sq (y2 )y1 + y2−22"= r Sr r
 !
x + xr 1/r
1

2

2, rJ˜Sr (x1 , x2 )!

Sr (x1 ) + Sr (x2 )
−
2

(87)
#

(88)
(89)

27

where we made the substitutions r , q −1 , x1 , y1q and x2 , y2q , and introduced
J˜Sr (x1 , x2 ) = Sr !
 rx + xr 1/r
1

2

2
−1

= (r − 1)−

Sr (x1 ) + Sr (x2 )2Z " rx + xr 1/r
1

2

2

#

x1 + x2
−
.
2

(90)

Since JSq is nd for q ∈ [0, 2], we have that J˜Sr is nd for r ∈ [1/2, ∞].
Notice that while JSq may be interpreted as “the difference between the Tsallis q-entropy of themean and the mean of the Tsallis q-entropies”, J˜Sq may be interpreted as “the difference between
the Tsallis q-entropy of the q-power mean and the mean of the Tsallis q-entropies”.
From (90) we have thatZψα,β (x, y) = (α − 1)J˜Sα (x, y) − (β − 1)J˜Sβ (x, y),(91)

so the family of probabilistic kernels studied in Hein et al. [2004] can be written in terms of JensenTsallis divergences.

7.5

k-th order Jensen-Tsallis string kernels

This subsection introduces a new class of string kernels inspired by the k-th order JT q-difference
introduced in Subsection 6.3. Although we refer to them as “string kernels,” they are more generally kernels between stochastic processes.
Several string kernels (i.e., kernels operating on the space of strings) have been proposed in
the literature [Haussler, 1999, Lodhi et al., 2002, Leslie et al., 2002, Vishwanathan and Smola,
2003, Shawe-Taylor and Cristianini, 2004]. These are kernels defined on A∗ × A∗ , where A∗ is
the Kleene closure of a finite alphabet A (i.e., the set of all finite strings formed by characters in A
together with the empty string .) The p-spectrum kernel [Leslie et al., 2002] is associated with afeature space indexed by Ap (the set of length-p strings). The feature representation of a string s,
Φp (s) , (φpu (s))u∈Ap , counts the number of times each u ∈ Ap occurs as a substring of s,
φpu (s) = |{(v1 , v2 ) : s = v1 uv2 }|.

(92)p

The p-spectrum kernel is then defined as the standard inner product in R|A|pkSK(s, t) = hΦp (s), Φp (t)i .

(93)

A more general kernel is the weighted all-substrings kernel [Vishwanathan and Smola, 2003],
which takes into account the contribution of all the substrings weighted by their length. Thiskernel can be viewed as a conic combination of p-spectrum kernels and can be written as
kWASK (s, t) =

∞
X
p=1

28

p
αp kSK(s, t),(94)

where αp is often chosen to decay exponentially with p and truncated; for example, αp = λp , ifpmin ≤ p ≤ pmax , and αp = 0, otherwise, where 0 < λ < 1 is the decaying factor.
pBoth kSK
and kWASK are trivially positive definite, the former by construction and the latterbecause it is a conic combination of positive definite kernels. A remarkable fact is that both kernels
may be computed in O(|s| + |t|) time (i.e., with cost that is linear in the length of the strings), as
shown by Vishwanathan and Smola [2003], by using data structures such as suffix trees or suffix
arrays [Gusfield, 1997]. Moreover, with s fixed, any kernel k(s, t) may be computed in time O(|t|),which is particularly useful for classification applications.
We will now see how Jensen-Tsallis kernels may be used as string kernels. In Subsection 6.3,
we have introduced the concept of joint and conditional JT q-differences. We have seen that joint
JT q-differences are just JT q-differences in a product space of the form X = X1 × X2 ; for k-thorder joint JT q-differences this product space is of the form Ak = A × Ak−1 . Therefore, they
still yield positive definite kernels as those introduced in Definition 29, where X = Ak . The next
definition and proposition summarize these statements.
Definition 42 (k-th order weighted JT kernels) Let S (A) be the set of stationary and ergodic
stochastic processes that take values on the alphabet A. For k ∈ N and q ∈ [0, 2], let the kernelk̃q,k : (R+ × S (A))2 → R be defined as
keq,k ((ω1 , s1 ), (ω2 , s2 )) , keq (ω1 ps1 ,k , ω2 ps2 ,k )
=



(95)


joint,πSq (π) − Tq,k(s1 , s2 )q

(ω1 + ω2 ) ,where ps1 ,k and ps2 ,k are the k-th order joint probability functions associated with the stochastic
sources s1 and s2 , and π = (ω1 /(ω1 + ω2 ), ω2 /(ω1 + ω2 )).
Let the kernel kq,k : (R++ × S (A))2 → R be defined as
kq,k ((ω1 , s1 ), (ω2 , s2 )) , kq (ω1 ps1 ,k , ω2 ps2 ,k )
=



(96)


joint,πSq (π) − Tq,k(s1 , s2 ) ,Proposition 43 The kernel keq,k is pd, for q ∈ [0, 2]. The kernel kq,k is pd, for q ∈ [0, 1].
1,S

Proof: Define the map g : R+ × S (A) → R+ × M+ q (Ak ) as (ω, s) 7→ g(ω, s) = (ω, ps,k ).
From Proposition 30, the kernel keq (g(ω1 , s1 ), g(ω2 , s2 )) is pd and therefore so is keq,k ((ω1 , s1 ), (ω2 , s2 ));proceed analogously for kq,k .
cond
At this point, one might wonder whether the “k-th order conditional JT kernel” keq,kthat would
joint,πcond,πbe obtained by replacing Tq,k with Tq,k in (95)-(96) is also pd. Formula (68) shows that such“conditional JT kernel” is a difference between two joint JT kernels, which is inconclusive. The
cond
cond
following proposition shows that keq,kand kq,k
are not pd in general. The proof, which is in
Appendix C, proceeds by building a counterexample.



cond,πcond
cond
Proposition 44 Let keq,kbe defined as keq,k(s1 , s2 ) , Sq (π) − Tq,k(s1 , s2 ) (ω1 + ω2 )q ; and

cond,π
cond
cond
cond
cond
kq,k
be defined as kq,k(s1 , s2 ) , Sq (π) − Tq,k(s1 , s2 ) . It holds that keq,kand kq,k
are not
pd in general.

29Despite the negative result in Proposition 44, the chain rule in Proposition 18 still allows us todefine pd kernels by combining conditional JT q-differences.
Proposition 45 Let (βk )k∈N be a non-increasing infinitesimal sequence, i.e. satisfying
β0 ≥ β1 ≥ . . . ≥ βn → 0
Any kernel of the form

∞
X

(97)

cond
βk keq,k

(98)

cond
βk kq,k(99)

k=0

is pd for q ∈ [0, 2]; and any kernel of the form∞X
k=0

is pd for q ∈ [0, 1], provided both series above converge pointwise.
Proof: From the chain rule, we have that (defining the 0-th order joint JT q-difference as
keq,0 , 0)
∞
X
k=0

cond
βk keq,k
=

∞
X
k=0

βk (keq,k+1 − keq,k ) = n→∞
lim

n
X
k=1

αk keq,k + βn keq,n+1 =∞X

αk keq,k

(100)

k=1

with αk = βk−1 − βk (the term lim βn keq,n+1 was dropped because βn → 0 and keq,n+1 is bounded).
Since (βk )k∈N is non-increasing, we have that (αk )k∈N\{0} is non-negative, which makes (100) the
pointwise limit of a conic combination of pd kernels, and therefore a pd kernel. The proof forP∞
cond
k=0 βk kq,k is analogous.
Notice that if we set β0 = . . . = βk−1 = 1 and βj = 0, ∀j ≥ k, in the above proposition, we
recover the k-th order joint JT q-difference.
Finally, notice that, in the same way that the linear kernel is a special case of a JT kernel whenq = 2 (see Cor. 40), the p-spectrum kernel (93) is a particular case of a p-th order joint JT kernel,
and the weighted all substrings kernel (94) is a particular case of a combination of joint JT kernels
in the form (98), both obtained when we set q = 2 and the weights ω1 and ω2 equal to the length of
the strings. Therefore, we conclude that the JT string kernels introduced in this section subsume
these two well-known string kernels.

7.6

The heat kernel approximation

The diffusion kernel for statistical manifolds, recently proposed by Lafferty and Lebanon [2005],
is grounded in information geometry [Amari and Nagaoka, 2001]. It models the diffusion of “information” over a statistical manifold according to the heat equation. Since in the case of themultinomial manifold (the relative interior of ∆n ), the diffusion kernel has no closed form, the30

authors adopt the so-called “first-order parametrix expansion,” which resembles the Gaussian kernel replacing the Euclidean distance by the geodesic distance that is induced when the manifold
is endowed with a Riemannian structure given by the Fisher information (we refer to Lafferty andLebanon [2005] for further details). The resulting heat kernel approximation isnk heat (p1 , p2 ) = (4πt)− 2 exp −1 2
d (p1 , p2 ) ,
4t g


(101)


P √
where t > 0 and dg (p1 , p2 ) = 2 arccospp
1i 2i . Whether k heat is pd has been an open problem
in[Hein et al., 2004, Zhang et al., 2005]. Let S+ be the positive orthant of the n-dimensional sphere,
i.e.,
)
(

Sn+ = (x1 , . . . , xn+1 ) ∈ Rn+1 |n+1X

x2i = 1, ∀i xi ≥ 0 .

i=1

The problem can be restated as follows: is there an isometric embedding from Sn+ to some Hilbert
space? In this section we answer that question in the negative.
Proposition 46 Let n ≥ 2. For sufficiently large t, the kernel kheat is not pd.
Proof: From Proposition 22, kheat is pd, for all t > 0, if and only if d2g is nd. We provide a
counterexample, using the following four points in ∆2 : p1 = (1, 0, 0), p2 = (0, 1, 0), p3 = (0, 0, 1)
and p4 = (1/2, 1/2, 0). The squared distance matrix [Dij ] = [d2g (pi , pj )] is
0
π2 
4
·

D=
4  4
1


4
0
4
1

4
4
0
4

1
1 

.
4 
0


(102)

Taking c = (−4, −4, 1, 7) we have cT Dc = 2π 2 > 0, showing that D is not nd. Although
p1 , p2 , p3 , p4 lie on the boundary of ∆2 , continuity of d2g implies that it is not nd on the relativeinterior of ∆2 . The case n > 2 follows easily, by appending zeros to the four vectors above.

8

Experiments

We illustrate the performance of the proposed nonextensive information theoretic kernels, in comparison with common kernels, for SVM-based text classification. We performed experimentswith two standard datasets: Reuters-215783 and WebKB.4 Since our objective was to evaluate
the kernels, we considered a simple binary classification task that tries to discriminate among thetwo largest categories of each dataset; this led us to the earn-vs-acq classification task for the
first dataset, and stud-vs-fac (students’ vs. faculty webpages) in the second dataset. Two different frameworks were considered: modeling documents as bags-of-words, and modeling them as
strings of characters. Therefore, both bags-of-words kernels and string kernels were employed foreach task.
3
4

Available at www.daviddlewis.com/resources/testcollections.
Available at www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-20/www/data.

31

8.1

Documents as bags-of-words

For the bags-of-words framework, after the usual preprocessing steps of stemming and stop-word
removal, we mapped text documents into probability distributions over words using the bag-ofwords model and maximum likelihood estimation; this corresponds to normalizing the term frequencies (tf) using the `1 -norm, and is referred to as tf [Joachims, 2002, Manning and Schütze,1999]. We also used the tf-idf (term frequencyı̈¿ 21 -inverse document frequency) representation,
which penalizes terms that occur in many documents [Joachims, 2002, Manning and Schütze,1999]. To weight the documents for the Tsallis kernels, we tried four strategies: uniform weighting, word counts, square root of the word counts, and one plus the logarithm of the word counts;
however, for both tasks, uniform weighting revealed the best strategy, which may be due to the factthat documents in both collections are usually short and do not differ much in size.
As baselines, we used the linear kernel with `2 normalization, commonly used for this task
[Joachims, 2002], and the heat kernel approximation (101) [Lafferty and Lebanon, 2005], which
is known to outperform the former, albeit not being guaranteed to be pd for an arbitrary choice oft (see (101)), as shown above. This parameter and the SVM C parameter were tuned by crossvalidation over the training set. The SVM-Light package (available at http://svmlight.
joachims.org/) was used to solve the SVM quadratic optimization problem.
Figs. 2–3 summarize the results. We report the performance of the Tsallis kernels as a functionof the entropic index q. For comparison, we also plot the performance of an instance of a Tsallis
kernel with q tuned by cross-validation. For the first task, this kernel and the two baselines exhibit
similar performance for both the tf and the tf-idf representations; differences are not statisticallysignificant. In the second task, the Tsallis kernel outperformed the `2 -normalized linear kernel
for both representations, and the heat kernel for tf-idf ; the differences are statistically significant(using the unpaired t test at the 0.05 level). Regarding the influence of the entropic index, we
observe that in both tasks, the optimum value of q is usually higher for tf-idf than for tf.
The results on these two problems are representative of the typical relative performance of thekernels considered: in almost all tested cases, both the heat kernel and the Tsallis kernels (for asuitable value of q) outperform the `2 -normalized linear kernel; the Tsallis kernels are competitive
with the heat kernel.

8.2

Documents as strings

In the second set of experiments, each document is mapped into a probability distribution overcharacter p-grams, using maximum likelihood estimation; we did experiments for p = 3, 4, 5. To
weight the documents for the p-th order joint Jensen-Tsallis kernels, four strategies were attempted:
uniform weighting, document lengths (in characters), square root of the document lengths, andone plus the logarithm of the document lengths. For the earn-vs-acq task, all strategies performed
similarly, with a slight advantage for the square root and logarithm of the document lengths; forthe stud-vs-fac task, uniform weighting revealed the best strategy. For simplicity, all experiments
reported here use uniform weighting.
As baselines, we used the p-spectrum kernel (PSK, see (93)) for the values of p referred above,and the weighted all substrings kernel (WASK, see (94)) with decaying factor tuned to λ = 0.75
32

tf−idf

2.5

WJTK−qLinL2Heat (σ )Average error rate (%)

Average error rate (%)

tf

CV

WJTK (qCV)

2

1.5

1

2.5

2

WJTK−qLinL2Heat (σCV)
WJTK (qCV)

1.5

1

0 0.25 0.5 0.75 1 1.25 1.5 1.75 2

0 0.25 0.5 0.75 1 1.25 1.5 1.75 2

Entropic index q

Entropic index q

Figure 2: Results for earn-vs-acq using tf and tf-idf representations. The error bars represent ±1
standard deviation on 30 runs. Training (resp. testing) with 200 (resp. 250) samples per class.
(which yielded the best results), with pmin = p set to the values above, and pmax = ∞. The SVM
C parameter was tuned by cross-validation over the training set.
Figs. 4–5 summarize the results. For the first task, the JT string kernel and the WASK outperformed the PSK (with statistical significance for p = 3), all kernels performed similarly for p = 4,
and the JT string kernel outperformed the WASK for p = 5; all other differences are not statiscallysignificant. In the second task, the JT string kernel outperformed both the WASK and the PSK(and the WASK outperformed the PSK), with statistical significance for p = 3, 4, 5. Furthermore,by comparing Fig. 3 and Fig. 5, we also observe that the 5-th order JT string kernel remarkably
outperforms all bags-of-words kernels for the stud-vs-fac task, even though it does not use or build
any sort of language model at the word level.

9Conclusions

In this paper we have introduced a new family of positive definite kernels between measures, whichcontain previous information-theoretic kernels on probability measures as particular cases. One of
the key features of the new kernels is that they are defined on unnormalized measures (not necessarily normalized probabilities). This is relevant, e.g., for kernels on empirical measures (such as
word counts, pixel intensity histograms); instead of the usual step of normalization [Hein et al.,2004], we may leave these empirical measures unnormalized, thus allowing objects of different
size (e.g., documents of different lengths, images with different sizes) to be weighted differently.
Another possibility is the explicit inclusion of weights: given two normalized measures, they canbe multiplied by arbitrary (positive) weights before being fed to the kernel function. In addition,33

tf−idf

tf
10
9

Average error rate (%)

Average error rate (%)

11
WJTK−qLinL2Heat (σCV)
WJTK (qCV)

8
7
6

10

WJTK (qCV)

9
8
7
6
5

0 0.25 0.5 0.75 1 1.25 1.5 1.75 2

WJTK−qLinL2Heat (σCV)

0 0.25 0.5 0.75 1 1.25 1.5 1.75 2

Entropic index q

Entropic index q

Figure 3: Results for stud-vs-fac.

we define positive definite kernels between stochastic processes that subsume well-known stringkernels.
The new kernels, and the proofs of positive definiteness, rely on other main contributions of
this paper: the new concept of q-convexity, for which we proved a Jensen q-inequality; the conceptof Jensen-Tsallis q-difference, a nonextensive generalization of the Jensen-Shannon divergence;
denormalization formulae for several entropies and divergences.
We have reported experiments in which these new kernels were used in support vector machines for text classification tasks. Although the reported experiments do not allow drawing strong
conclusions, they show that the new kernels are competitive with the state-of-the-art, in some cases
yielding a significant performance improvement.

A

Proof of Proposition 9

Proof: The case q = 1 corresponds to the Jensen difference and was proved by Burbea
and Rao [1982] (Theorem 1). Our proof extends that to q 6= 1. Let y = (y1 , . . . , ym ), whereyt = (yt1 , . . . , ytn ). Thus
π
Tq,Ψ
(y)

= Ψ
=

m
X

!

πt yt −

t=1
"m
n
X
X
i=1

m
X
q

πt Ψ(yt )t=1

πtq ϕ(yti ) − ϕ

t=1

m
X
t=1

34

!#

πt yti,showing that it suffices to consider n = 1, where each yt ∈ [0, 1], i.e.,πTq,Ψ
(y1 , . . . , ym ) =

m
X
q

m
X

t=1

t=1

πt ϕ(yt ) − ϕ!

πt yt ;

(103)

this function is convex on [0, 1]m if and only if, for every fixed a1 , . . . , am ∈ [0, 1], and b1 , . . . , bm ∈R, the functionπf (x) = Tq,Ψ(a1 + b1 x, . . . , am + bm x)(104)
is convex in {x ∈ R : at + bt x ∈ [0, 1], t = 1, . . . , m}. Since f is C 2 , it is convex if and only if
f 00 (t) ≥ 0.
π
We first show that convexity of f (equivalently of Tq,Ψ) implies convexity of ϕ. Letting ct =at + bt x,!
!
mX
f (x) =
π q b2 ϕ00 (c ) −
00

t

m
X

t

t

t=1

2

m
X

ϕ00

π t btt=1

πt ct .

By choosing x = 0, at = a ∈ [0, 1], for t = 1, ..., m, and b1 , . . . , bm satisfying(105), we get
f 00 (0) = ϕ00 (a)

(105)

t=1

P

t πt bt = 0 in

m
X
q 2

π t bt ,t=1

hence, if f is convex, ϕ00 (a) ≥ 0 thus ϕ is convex.
Next, we show that convexity of f also implies (2 − q)-convexity of −1/ϕ00 . By choosing
x = 0 (thus ct = at ) and bt = πt1−q (ϕ00 (at ))−1 , we get
m
X
πt2−q
πt2−q
f (0) =−
00
00
t=1 ϕ (at )t=1 ϕ (at )
m
X

00

"

=

!2

ϕ

πt2−q
−
P
00
ϕ00 ( mt=1 πt at )t=1 ϕ (at )
m
X

1

00

#

m
X

!

πt at

t=1
m
X

m
X
πt2−q
00
ϕ
πt at ,
00
t=1 ϕ (at )
t=1

!

!

where the expression inside the square brackets is the Jensen (2 − q)-difference of 1/ϕ00 (seeDefinition 8). Since ϕ00 (x) ≥ 0, the factor outside the square brackets is non-negative, thus theJensen (2 − q)-difference of 1/ϕ00 is also nonnegative and −1/ϕ00 is (2 − q)-convex.
π
Finally, we show that if ϕ is convex and −1/ϕ00 is (2 − q)-convex, then f 00 ≥ 0, thus Tq,Ψ
is
2−q
q 00
00
1/2
1/2
00
convex. Let rt = (qπt /ϕ (ct )) and st = bt (πt ϕ (ct )/q) ; then, non-negativity of f resultsfrom the following chain of inequalities/equalities:
0≤

m
X

!

rt2

m
X

m
X

!

s2t

!2

−
rt st
t=1
t=1
t=1
!2
m
m
m
X
X
πt2−q X
2 q 00=bt πi ϕ (ct ) −bt π t00
t=1 ϕ (ct ) t=1
t=1

≤
=

1
Pm

ϕ00 (

t=1 πt ct ) t=1

1
Pm

ϕ00 (

m
X

t=1 πt ct )b2t πtq ϕ00 (ct ) −

m
X

(106)
(107)
!2

bt π t(108)

t=1· f 00 (t),
35

(109)

where: (106) is the Cauchy-Schwarz inequality; equality (107) results from the definitions of rtand st and from the fact that rt st = bt πt ; inequality (108) states the (2 − q)-convexity of −1/ϕ00 ;equality (109) results from (105).

B

Proof of Proposition 13
Proof: The proof of (55), for q ≥ 0, results fromTqπ (p1 , . . . , pm ) =

m
X

n
X

1 
1−
q−1
j=1



n
m
X
X
p q 
−πtq 1 −!q

πt ptj

tj

t=1

t=1

j=1
!q #

m
m
n
X
X
1 X
(πt ptj )q −πt ptj= Sq (π) +q − 1 j=1 t=1
t=1"≤ Sq (π),(110)

where the inequality holds since, for yi ≥ 0: if q ≥ 1, then i yiq ≤ ( i yi )q ; if q ∈ [0, 1], thenPP qqi yi ≥ ( i yi ) .
The proof that Tqπ ≥ 0 for q ≥ 1, uses the notion of q-convexity. Since X is countable, theTsallis entropy is as in (4), thus Sq ≥ 0. Since −Sq is 1-convex, then, by Proposition 7, it is also
q-convex for q ≥ 1. Consequently, from the q-Jensen inequality (Proposition 6), for finite T , with|T | = m,!
PP

Tqπ (p1 , . . . , pm ) = SqmXπt pt −

t=1

m
X
q

πt Sq (pt ) ≥ 0.

t=1

Since Sq is continuous, so is Tqπ , thus the inequality is valid in the limit as m → ∞, which
proves the assertion for T countable. Finally, Tqπ (δ1 , . . . , δ1 , . . .) = 0, where δ1 is some degenerate
distribution.
Finally, to prove (57), for q ∈ [0, 1] and X finite,
Tqπ (p1 , . . . , pm )

m
X

= Sq

!

πt pt −

t=1

≥
=

m
X
t=1
m
X

πt Sq (pt ) −mXq

πt Sq (pt )

t=1
m
X

πtq Sq (pt )

(111)

t=1

(πt − πtq )Sq (pt )t=1≥ Sq (U )mX(πt − πtq )

(112)

t=1

= Sq (π)[1 − n1−q ].

(113)

where the inequality (111) results from Sq being concave, and the inequality 112 holds since πt −πtq ≤ 0, for q ∈ [0, 1], and the uniform distribution U maximizes Sq (Proposition 10), with Sq (U ) =(1 − n1−q )/(q − 1).
36

C

Proof of Proposition 44

Proof: We show a counterexample with q = 1 (theextensive qcase), π = (1/2, 1/2) andq
cond,(1/2,1/2)
k = 1, that discards both cases. It suffices to show that JS1cond , T1,1
violates thetriangle inequality for some choiceqof stochastic processes s1 , s2 , s3 and therefore is a not a squared
distance; this in turn implies that JS1cond is not nd and, from Proposition 21, that the above twokernels are not pd. We define s1 , s2 , s3 to be stationary first order Markov processes in a binaryalphabet A = {0, 1} defined by the following transition matrices, respectively:"1− 
1/4 3/4#

3/4 1/4
 1−

#

 1−
1/4 3/4#1
σ1 = lim
→0 1 + 4"1
σ2 = lim
→0 1 + 4"S1 = lim
→0"S2 = lim
→0

and

"

S3 = lim
→0

"

1
0
1/4 3/4#

3/4 1/4
0
1

#

#

=

0
1
1/4 3/4

1
4

#

"

4
1

#

=
"

=
"

,

(114)

,

(115)

,

(116)

whose stationary distributions are

and

"

=
"

=
#

1
0

#

0
1

#

"

,

(117)

,

(118)
#

1
1
1/5
=
.
(119)
σ3 = lim
→0 5 − 4
4 − 4
4/5
The matrix of first order conditional JT 1-differences (or first order conditional Jensen-Shannon
divergences) is




3
5
0 0
H(
)
0
0
0.390
5
6



9
8
2
1 
(120)
 ∗ 0 10 H( 9 ) − 5 H( 4 )  ≈  ∗ 0 0.128  ,
∗ ∗
0
∗ ∗
0
which fails to be negative definite, sinceq

JS1cond (s1 , s2 ) +q

JS1cond (s2 , s3 ) <q

JS1cond (s1 , s3 ),

(121)

q

which violates the triangle inequality required for JS1cond to be a metric.
Interestingly, the 0-th order conditional Jensen-Shannon divergence matrix (this one ensured tobe negative definite because it equals a standard Jensen-Shannon divergence matrix) is
0 1 H( 25 ) − 21 H( 15 )0 1 0.610



1
1
1 
 ∗ 0 H( 10 ) − 2 H( 5 )  ≈  ∗ 0 0.108  .
∗ ∗
0
∗ ∗
0








(122)

From the chain rule (68), we have that the sum of the matrices (120) and (122) is the second orderjoint Jensen-Shannon divergence, and therefore is also guaranteed to be negative definite.
37

References
S. Abe. Foundations of nonextensive statistical mechanics. In Chaos, Nonlinearity, Complexity.
Springer, 2006.
S. Amari and H. Nagaoka. Methods of Information Geometry. Oxford University Press, 2001.
A. Banerjee, S. Merugu, I. Dhillon, and J. Ghosh. Clustering with Bregman divergences. Journalof Machine Learning Research, 6:1705–1749, 2005.
A. Ben-Hamza. A nonextensive information-theoretic measure for image edge detection. Journalof Electronic Imaging, 15-1:13011.1–13011.8, 2006.
A. Ben-Hamza and H. Krim. Image registration and segmentation by maximizing the jensenrényi divergence. In Proceedings of International Workshop on Energy Minimization Methods
in Computer Vision and Pattern Recognition, pages 147–163. Springer, Lisbon, Portugal, 2003.
C. Berg, J. Christensen, and P. Ressel. Harmonic Analysis on Semigroups. Springer, Berlin, 1984.
J. Burbea and C. Rao. On the convexity of some divergence measures based on entropy functions.
IEEE Transactions on Information Theory, 28(3):489–495, 1982.
T. Cover and J. Thomas. Elements of Information Theory. Wiley, 1991.
I. Csiszar. I-divergence geometry of probability distributions and minimization problems. The
Annals of Probability, 3(1):146–158, 1975.
M. Cuturi and J.-P. Vert. Semigroup kernels on finite sets. In L. Saul, Y. Weiss, and L. Bottou,
editors, Advances in Neural Information Processing Systems 17, pages 329–336. MIT Press,
Cambridge, MA, 2005.
M. Cuturi, K. Fukumizu, and J.-P. Vert. Semigroup kernels on measures. Journal of Machine
Learning Research, 6:1169–1198, 2005.
Z. Daróczy. Generalized information functions. Information and Control, 16(1):36–51, 1970.
F. Desobry, M. Davy, and W. Fitzgerald. Density kernels on unordered sets for kernel-based signal
processing. In Proceedings of the IEEE International Conference on Acoustics, Speech, andSignal Processing – ICASSP’2007, 2007.
R. El-Yaniv, S. Fine, and N. Tishby. Agnostic classification of markovian sequences. In M. Jordan,
M. Kearns, and S. Solla, editors, Advances in Neural Information Processing Systems 10, pages
465–471. MIT Press, Cambridge, MA, 1998.
D. Endres and J. Schindelin. A new metric for probability distributions. IEEE Transactions on
Information Theory, 49(7):1858–1860, 2003.

38

B. Fuglede. Spirals in Hilbert space, with an application in information theory. Expositiones
Mathematicae, 25(1):23–46, 2005.
S. Furuichi. Information theoretical properties of Tsallis entropies. Journal of Mathematical
Physics, 47(2), 2006.
M. Gell-Mann and C. Tsallis. Nonextensive entropy: interdisciplinary applications. Oxford University Press, 2004.
I. Grosse, P. Bernaola-Galvan, P. Carpena, R. Roman-Roldan J. Oliver, and H. E. Stanley. Analysis
of symbolic sequences using the Jensen-Shannon divergence. Physical Review E, 65, 2002.
D. Gusfield. Algorithms on Strings, Trees, and Sequences. Cambridge University Press, 1997.
D. Haussler. Convolution kernels on discrete structures, 1999. URL citeseer.ist.psu.
edu/haussler99convolution.html.
M. Havrda and F. Charvát. Quantification method of classification processes: concept of structural
α-entropy. Kybernetika, 3:30–35, 1967.
Y. He, A. Ben-Hamza, and H. Krim. A generalized divergence measure for robust image registration. IEEE Transactions on Signal Processing, 51(5):1211–1220, 2003.
M. Hein and O. Bousquet. Hilbertian metrics and positive definite kernels on probability measures.
In Z. Ghahramani and R. Cowell, editors, Proceedings of the 10th International Workshop on
Artificial Intelligence and Statistics (AISTATS). 2005.
M. Hein, T. Lal, and O. Bousquet. Hilbertian metrics on probability measures and their applicationin SVMs. In Proceedings of the 26th DAGM Symposium, pages 270–277. Springer, 2004.
T. Jebara, R. Kondor, and A. Howard. Probability product kernels. Journal of Machine Learning
Research, 5:819–844, 2004.
J. Jensen. Sur les fonctions convexes et les inégalités entre les valeurs moyennes. Acta Mathematica, 30:175–193, 1906.
T. Joachims. Learning to Classify Text Using Support Vector Machines: Methods, Theory andAlgorithms. Kluwer Academic Publishers, 2002.
D. Karakos, S. Khudanpur, J. Eisner, and C. Priebe. Iterative denoising using Jensen-Rényi divergences with an application to unsupervised document categorization. In Proc. of IEEE International Conference on Acoustics, Speech and Signal Processing, volume II, pages 509–512,
Baltimore, MD, 2007.
A. Khinchin. Mathematical Foundations of Information Theory. Dover, New York, 1957.
J. Lafferty and G. Lebanon. Diffusion kernels on statistical manifolds. Journal of Machine Learning Research, 6:129–163, 2005.
39

P. Lamberti and A. Majtey. Non-logarithmic Jensen-Shannon divergence. Physica A Statistical
Mechanics and its Applications, 329:81–90, 2003.
C. Leslie, E. Eskin, and W. Noble. The spectrum kernel: A string kernel for svm protein classification. In Proceedings of the Pacific Symposium on Biocomputing 2002, pages 564–575,
2002.
Y. Li, X. Fan, and G. Li. Image segmentation based on Tsallis-entropy and Renyi-entropy andtheir comparison. In IEEE International Conference on Industrial Informatics, pages 943–948,
2006.
J. Lin. Divergence measures based on the Shannon entropy. IEEE Transactions on Information
Theory, 37(1):145–151, 1991.
J. Lin and S. Wong. A new directed divergence measure and its characterization. International
Journal of General Systems, 17:73–81, 1990.
J. Lindhard. On the theory of measurement and its consequences in statistical dynamics. Munksgaard, Copenhagen, 1974.
J. Lindhard and V. Nielsen. Studies in statistical dynamics. Munksgaard, Copenhagen, 1971.
H. Lodhi, C. Saunders, J. Shawe-Taylor, N. Cristianini, and C. Watkins. Text classification using
string kernels. Journal of Machine Learning Research, 2:419–444, 2002.
C. Manning and H. Schütze. Foundations of Statistical Natural Language Processing. MIT Press,
Cambridge, MA, 1999.
A. Martins, P. Aguiar, and M. Figueiredo. Tsallis kernels on measures. In Proceedings of the IEEE
Information Theory Workshop – ITW’08, Porto, Portugal, 2008a.
A. Martins, M. Figueiredo, P. Aguiar, N. Smith, and E. Xing. Nonextensive entropic kernels.
In Proceedings of the International Conference on Machine Learning – ICML’08, Helsinki,
Finland, 2008b.
P. Moreno, P. Ho, and N. Vasconcelos. A Kullback-Leibler divergence based kernel for SVM classification in multimedia applications. In S. Thrun, L. Saul, and B. Schölkopf, editors, Advancesin Neural Information Processing Systems 16. MIT Press, 2004.
A. Rényi. On measures of entropy and information. In Proceedings of the 4th Berkeley Symposium on Mathematics, Statistics, and Probability, volume 1, pages 547–561, Berkeley, 1961.
University of California Press.
B. Schölkopf and A. J. Smola. Learning with Kernels. The MIT Press, Cambridge, MA, 2002.
C. Shannon and W. Weaver. The Mathematical Theory of Communication. University of Illinois
Press, Urbana, Ill., 1949.
40

C. E. Shannon. A mathematical theory of communication. The Bell System Technical Journal, 27(3):379–423, 1948.
J. Shawe-Taylor and N. Cristianini. Kernel Methods for Pattern Analysis. Cambridge University
Press, 2004.
J. Steele. The Cauchy-Schwarz Master Class. Cambridge University Press, Cambridge, 2006.
H. Suyari. Generalization of shannon-khinchin axioms to nonextensive systems and the uniquenesstheorem for the nonextensive entropy. IEEE Transactions on Information Theory, 50(8):1783–
1787, 2004.
F. Topsøe. Some inequalities for information divergence and related measures of discrimination.
IEEE Transactions on Information Theory, 46(4):1602–1609, 2000.
C. Tsallis. Possible generalization of Boltzmann-Gibbs statistics. Journal of Statistical Physics,
52:479–487, 1988.
S. Vishwanathan and A. Smola. Fast kernels for string and tree matching. In K. Tsuda,
B. Schölkopf, and J.P. Vert, editors, Kernels and Bioinformatics, Cambridge, MA, 2003. MIT
Press.
D. Zhang, X. Chen, and W. Lee. Text classification with kernels on the multinomial manifold. In
Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 266–273, New York, NY, 2005. ACM Press.

41

p=4

p=3
2.6

3.5
WJTK−Str−q
PSK
WASK
WJTK−Str (qCV)

3

2.2

Average error rate (%)

Average error rate (%)

WJTK−Str−q
PSK
WASK
WJTK−Str (qCV)

2.4

2.5

2

2
1.8
1.6
1.4
1.2

1.5

1
1

0.8
0

0.25

0.5

0.75

1

1.25

1.5

1.75

2

0

0.25

0.5

Entropic index q

0.75

1

1.25

1.5

1.75

2

Entropic index q
p=5

2.2
WJTK−Str−q
PSK
WASK
WJTK−Str (qCV)

Average error rate (%)

2

1.8

1.6

1.4

1.2

1

0.8
0

0.25

0.5

0.75

1

1.25

1.5

1.75

2

Entropic index q

Figure 4: Results for earn-vs-acq using string kernels and p = 3, 4, 5. The error bars represent ±1
standard deviation on 15 runs. Training (resp. testing) with 200 (resp. 250) samples per class.

42

p=3

p=4

13

11
WJTK−Str−q
PSK
WASK
WJTK−Str (qCV)

Average error rate (%)

10

11

10

9

8

9

8

7

6

7

6

5
0

0.25

0.5

0.75

1

1.25

1.5

1.75

2

0

0.25

0.5

Entropic index q

0.75

1

1.25

Entropic index q
p=510
WJTK−Str−q
PSK
WASK
WJTK−Str (qCV)

9.5
9Average error rate (%)

Average error rate (%)

12

WJTK−Str−q
PSK
WASK
WJTK−Str (qCV)

8.5
8
7.5
7
6.5
6
5.5
5
0

0.25

0.5

0.75

1

1.25

1.5

1.75

2

Entropic index q

Figure 5: Results for stud-vs-fac using string kernels.

43

1.5

1.75

2