Tsallis Kernels on Measures
André F. T. Martins∗†

Pedro M. Q. Aguiar‡Mário A. T. Figueiredo†∗ Language Technologies Institute‡ Instituto de Sistemas e Robótica† Instituto de Telecomunicações

Carnegie Mellon University
Pittsburgh, PA, USA

Instituto Superior Técnico
Lisboa, Portugal

Instituto Superior Técnico
Lisboa, Portugal

Abstract—Recent approaches to classification of text, images,
and other types of structured data, launched the quest for positive
definite (p.d.) kernels on probability measures. In particular,kernels based on the Jensen-Shannon (JS) divergence and otherinformation-theoretic quantities have been proposed. We introduce new JS-type divergences, by extending its two building
blocks: convexity and Shannon’s entropy. These divergences
are then used to define new information-theoretic kernels on
measures. In particular, we introduce a new concept of qconvexity, for which a Jensen q-inequality is proved. Based on
this inequality, we introduce the Jensen-Tsallis q-difference, anonextensive generalization of the Jensen-Shannon divergence.
Furthermore, we provide denormalization formulae for entropies
and divergences, which we use to define a family of nonextensive
information-theoretic kernels on measures. This family, grounded
in nonextensive entropies, extends Jensen-Shannon divergencekernels, and allows assigning weights to its arguments.
Index Terms—Positive definite kernels, nonextensive entropy,
Tsallis entropy, Jensen-Shannon divergence, convexity.

I. I NTRODUCTION
In the field of kernel-based machine learning [1], there has
been recent interest in defining positive definite kernels on
probability measures, with applications in classification of text,
images, and other types of structured data [2], [3], [4]. In
particular, kernels based on the Jensen-Shannon divergence(JSD [5]) and other (Shannon) information-theoretic quantities
have been considered by several authors [2], [3].
Over the years, several generalizations of the Shannon
entropy have been proposed [6], [7], [8]. Rényi entropies arearguably the best known of these, with several applications(e.g., [9], [10]). The Rényi and Shannon entropies are both
additive: the joint entropy of independent variables is thesum of the individual entropies. In the so-called nonextensive(namely Tsallis) entropies [7], [8], [11], the additivity property
is abandoned. Tsallis entropies have been used to formulate
nonextensive statistical mechanics [12], [13] and, recently, insignal/image processing [14], [15], [16].
Convexity is a key concept in information theory, namely
via the ubiquitous Jensen’s inequality (JI) [17], [18]. The JI
underlies the concept of JSD, which has been used in statistics,
machine learning, image and signal processing, and physics.
In this paper, we introduce new JSD-type divergences, byextending its two building blocks: convexity and Shannon’s
Partially supported by the Portuguese Fundação para a Ciência e Tecnologia (grant PTDC/EEA-TEL/72572/2006 and the CMU-Portugal program) andby the EU FP7 project SIMBAD.

entropy. These divergences are then used to define new (andrecover previous) information-theoretic kernels on measures.
More specifically, our main contributions are:
• A new concept of q-convexity, for which a Jensen qinequality (JqI) is proved. Based on the JqI, we introduce
a the Jensen-Tsallis q-difference, (JTqD) a nonextensive
generalization of the JSD.
• Characterization of the JTqD, with respect to convexityand extrema, extending the work in [19], [5] for the JSD.
• Denormalization formulae for entropies and divergences,which we use to define a family of nonextensive
information-theoretic kernels on measures. This family(which contains JSD kernels [2] as particulars cases)
is novel in two ways: it is grounded in nonextensive
entropies; it allows assigning weights to its arguments.
All the proofs omitted in this paper can be found in [20].
II. T SALLIS E NTROPIESLet ∆n−1 be the simplex in Rn . The Tsallis entropy Sq :∆n−1 → R, defined asPnX(1 − i=1 pqi )Sq (p1 , . . . , pn ) ==−p(x)q lnq p(x) (1)
q−1
x∈X

1−q

where lnq (x) := (x −1)/(1−q) is the q-logarithm, satisfies
the axioms for nonextensive entropies introduced in [21].
Tsallis joint and conditional entropies are defined asX
Sq (X, Y ) := −p(x, y)q lnq p(x, y)x,ySq (X|Y ) :=−X

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

x,yand the chain rule Sq (X, Y ) = Sq (X) + Sq (Y |X) holds [22].
For two pmfs pX , pY ∈ ∆n , the Tsallis relative entropy,
generalizing the KLD, is defined as
X
pX (x) lnq (pY (x)/pX (x)). (2)Dq (pX kpY ) := −xIII. E NTROPIES OF UNNORMALIZED MEASURES
We consider functionals that extend the domain of the
Shannon and Tsallis entropies to unnormalized measures.
Although they are completely characterized by their restriction
to the normalized counterparts, these denormalizations will be
used in Section VI to derive novel positive definite kernels.

Let (X , M , ν) be a measured space, where X is Hausdorffand ν a σ-finite Radon measure (usually the Lebesgue-Borel
measure, if X ⊆ Rn and intX 6= ∅, or the counting measure, if
X is countable). We denote by M+ (X ) the set of finite Radon1
ν-absolutely continuous measures on X , and by M+(X ) thesubset of those which are probability measures. For simplicity,1
we often identify each measure in M+ (X ) or M+(X ) with thecorresponding nonnegative density.
Inthesequel,LebesgueR
Stieltjes
integrals
of
the
form
f
(x)dν(x)areoftenwrittenARR
as A f , or simply f, if A = X .
GFor some functional G : M+ (X ) → R, let M+(X ) := {f ∈1,GG1
M+ (X ) : |G(f )| < ∞} and M+ (X ) := M+ (X ) ∩ M+
(X ).
The following functional [23], extends the SBG entropy from1,H
H
M+
to unnormalized measures in M+(with 0 log 0 := 0)
Z
Z
H(f ) = −k f log f = ϕH ◦ f,(3)
where k ∈ R++ , and ϕH : R++ → R is defined as
ϕH (y) = −k y log y.

(4)

The generalized KLD is a directed divergence between two
Hmeasures µf , µg ∈ M+
(X ), such that µf is µg -absolutely
continuous (µf ¿ µg ). In terms of densities,¶
Z µf
D(f, g) = k
g − f + f log.
(5)gBoth H and D are completely determined by their restriction to the normalized measures, as the next proposition shows.
Proposition 1: The following equalities hold for any c ∈H
R++ and f, g ∈ M+
(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|,R
where |f | := f = µf (X ).
Proof: Straightforward from (3) and (5).
S
For q ≥ 0, let M+q (X ) := {f ∈ M+ (X ) : f q ∈ M+ (X )}.
SThe Tsallis counterpart of (3), defined on M+q (X ), isZ
Sq (f ) = ϕq ◦ f,(6)
where ϕq : R++ → R is given by½
ϕH (y)
if q = 1,
ϕq (y) =kqq−1 (y − y ) if q 6= 1.
Similarly, a nonextensive version of (5) isZ¡¢kDq (f, g) = −qf + (1 − q)g − f q g 1−q ,
q−1

(7)

(8)

for q 6= 1, and D1 (f, g) := limq→1 Dq (f, g) = D(f, g).
Proposition 2: The following equalities hold for any c ∈S
R++ and f, g ∈ M+q (X ), with µf ¿ µg :Sq (cf ) = cq Sq (f ) + |f |ϕq (c),Dq (cf, cg) = cDq (f, g),

(9)
(10)

Dq (cf, g) = cq Dq (f, g) − qϕq (c)|f | + k(1 − cq )|g|.(11)Proof: Straightforward from (6) and (8).
Naturally, all the equalities in Prop. 1 are obtained by taking
the limit q → 1 in those of Prop. 2.
IV. J ENSEN D IFFERENCES AND D IVERGENCES
Definition 3 (Jensen difference (JD)): Consider
two measured sets (X , M , ν) and (T , T , τ ). Letµ := {µt }t∈T ∈ [M+ (X )]T be a set of measures in
M+ (X ) indexed by T , and let ω ∈ M+ (T ) be a measure in
T . The JD is defined asµZ¶ Zωω(t)Ψ(µt ) dτ (t) (12)JΨ(µ) := Ψω(t) µt dτ (t) −T

T

where: (i) Ψ is a concave functional such that dom Ψ ⊆M
R + (X ); (ii) ω(t)µt (x) is τ -integrable, for all x ∈ X ; (iii)ω(t)µt dτ (t) ∈ dom Ψ; (iv) µt ∈ dom Ψ, for all t ∈ T ; (v)T
ω(t)Ψ(µt ) is τ -integrable.
In the following subsections, we consider several instancesof Definition 3, leading to several Jensen-type divergences.
A. The Jensen-Shannon Divergence
Let P be a random probability distribution with values in
1{pt }t∈T following a distribution π ∈ M+
(T ). Then,πJΨ({pt }t∈T ) = Ψ (E[P ]) − E[Ψ(P )],(13)

where the expectations are with respect to π. Letting Ψ = H,π
the Shannon entropy, we have J π := JH.
π
If X and T are finite with |T | = m, JH(p1 , . . . , pm ) is
the JSD of p1 , . . . , pm , with weights π1 , . . . , πm [19], [5]. For
1 1|T | = 2 and π = ( 21 , 12 ), we have J ( 2 , 2 ) (P ) = JS(p1 , p2 ),JS(p1 , p2 ) = H((p1 + p2 )/2) − (H(p1 ) + H(p2 ))/2 (14)√as introduced in [5]. It has been shown that JS satisfies thetriangle inequality and that it is an Hilbertian metric [24], [25].
B. The Jensen-Tsallis Divergence
Divergences of the form (13), based on the Tsallis entropy
have been studied in [19]. Letting Ψ = Sq , (13) becomes
JSπq ({pt }t∈T ) = Sq (E[P ]) − E[Sq (P )].

(15)

For finite X and T , JSπq is called the Jensen-Tsallis divergence (JTD) and it has been applied in image processing [26].
V. q-C ONVEXITY AND J ENSEN q-D IFFERENCES
A. Introduction and Definitions
Definition 4: The unnormalized q-expectation of a randomvariable X, with probability density p, isZ
Eq [X] := x pq (x) dx.
(16)
For q 6= 1, the q-expectation does not correspond to theintuitive meaning of expectation. Nonetheless, it has been usedin the construction of nonextensive information theory; e.g.,
the Tsallis entropy can be written as Sq (X) = −Eq [lnq p(X)].
We now introduce q-convexity and derive several related
results, namely the Jensen q-inequality (JqI).

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).

(17)

Naturally, f is q-concave if −f is q-convex, and 1-convexity
is simply standard convexity.
Proposition 6 (The Jensen q-Inequality): If f : X → R
is q-convex, then for any n ∈ N, x1 , . . . , xn ∈ X and π =(π1 , . . . , πn ) ∈ ∆n−1 ,³X´ Xfπi xi ≤
πiq f (xi ).
(18)
Proof: By induction, as in the proof of the JI [18].
0Proposition 7: Let f ≥ 0 and q ≥ q ≥ 0; then, qconvexity implies q 0 -convexity.
Definition 8 (Jensen q-Differences (JqD)): Letµ := {µt }t∈T ∈ [M+ (X )]T be a class of measures in
X indexed by T , and let ω ∈ M+ (T ) be a measure in T .
For q ≥ 0, defineµZ¶ ZωTq,Ψ (µ) := Ψω(t) µt dτ (t) −ω q (t)Ψ(µt ) dτ (t)
T

T

(19)
where: (i) Ψ is a concave functional such that dom Ψ ⊆RM+ (X ); (ii) ω(t)µt (x) is τ -integrable for all x ∈ X ; (iii)ω(t)µt dτ (t) ∈ dom Ψ; (iv) µt ∈ dom Ψ, for all t ∈ T ; (v)Tω q (t)Ψ(µt ) is τ -integrable.
Conditions for the Jensen difference to be convex were
given in [19]. The following proposition generalizes that result,extending it to JqD.
Proposition 9: Let T and X be finite sets, with |T | = m
1(T ). Let ϕ : [0, 1] → R be aand |X | = n, and let π ∈ M+
function of class C 2 and consider the (ϕ-entropy[19]) functionPnΨ : [0, 1]n → R defined by Ψ(z) := − i=1 ϕ(zi ). Then, theπq-difference Tq,Ψ: [0, 1]nm → R is convex if and only if ϕ isconvex and −1/ϕ00 is (2 − q)-convex.
B. The Jensen-Tsallis q-Difference

Proposition 11: Let T and X be finite sets with cardinalities m and n, respectively. For q ∈ [0, 1], the JTqD is a jointly
1,S
convex function on (M+ q (X ))T .
Proposition 12: Let T and X be countable sets. The JTqD
is convex in each argument, for q ∈ [0, 2], and concave in eachargument, for q ≥ 2.
Proposition 13: Let T and X be countable sets. For q ≥ 0,
Tqπ (p1 , . . . , pm ) ≤ Sq (π), with the bound reached for a set of
disjoint degenerate distributions. For q ≥ 1, Tqπ (p1 , . . . , pm ) ≥0, with the minimum attained in the pure deterministic case,i.e., when all distributions are equal to the same degenerateone. For q ∈ [0, 1] and X a finite set with |X | = n,Tqπ (p1 , . . . , pm ) ≥ Sq (π)[1 − n1−q ]. This lower bound (which
can be negative) is attained when all distributions are uniform.
VI. T SALLIS K ERNELS
A. Positive and negative definite kernels
We start by recalling basic concepts from kernel theory [1];in the following, X denotes a nonempty set.
Definition 14: Let ϕ : X × X → R be a symmetricfunction, i.e., satisfying ϕ(y, x) = ϕ(x, y), for all x, y ∈ X .
ϕ is called a positive definite (p.d.) kernel if and only ifn XnXci cj ϕ(xi , xj ) ≥ 0(21)

i=1 j=1

Definition 10 (Jensen-Tsallis q-Difference (JTqD)): In
the conditions of Definition 8, the JTqD, denoted Tqπ , isπdefined as Tqπ := Tq,S.
q
1/2,1/2

When |T | = 2 and π = (1/2, 1/2), define Tq := Tq.
Notable cases arise for particular values of q:• For q = 0, S0 (p) = −1 + kpk0 , where kpk0 denotes theso-called 0-norm (although it’s not a norm) of vector p,i.e., its number of nonzero components. The JT0D is thus
T0 (p1 , p2 ) = 1 − kp1 ¯ p2 k0 ,We now present results regarding convexity and extrema of
the JTqD, extending known properties of the JSD (q = 1),
some of which are lost in the transition to nonextensivity. For
example, while the JSD is nonnegative and vanishes iff all the
distributions are identical, this is not true in general for the
JTqD. Nonnegativity of the JTqD is only guaranteed if q ≥ 1,
explaining why some authors (e.g., [22]) only consider q ≥ 1,
when developing nonextensive information theories.
The following propositions establish convexity properties of
the JTqD (complementing the joint convexity of the JTD, forq ∈ [1, 2], proved in [19]) and provide upper and lower bounds
for the JTqD.

(20)

where ¯ denotes the Hadamard-Schur (i.e., elementwise)
product. We call T0 the Boolean difference.
• For q = 1, since S1 (p) = H(p), T1 is the standard JSD.
• For q = 2, S2 (p) = 1 − hp, pi, where hx, yi =P
i xi yi denotes inner product. Consequently, the JT2D
is T2 (p1 , p2 ) = (1−hp1 , p2 i)/2, we call linear difference.

for all n ∈ N, xi , . . . , xn ∈ X and ci , . . . , cn ∈ R.
Definition 15: Let ψ : X × X → R be symmetric. ψ iscalled a negative definite (n.d.) kernel if and only ifn XnXci cj ψ(xi , xj ) ≤ 0(22)

i=1 j=1

for all n ∈ N, xi , . . . , xn ∈ X and ci , . . . , cn ∈ R, such thatc1 + . . . + cn = 0. In this case, −ψ is called conditionally p.d.
Both the sets of p.d. and n.d. kernels are convex cones(closed under pointwise sums and integrations), the former
being closed under pointwise products; moreover, both setsare closed under pointwise convergence. Proofs of these facts
and of the following propositions can be found in [27].
Proposition 16: Let ψ : X × X → R be a symmetricfunction, and x0 ∈ X . Let ϕ : X × X → R be given byϕ(x, y) = ψ(x, x0 ) + ψ(y, x0 ) − ψ(x, y) − ψ(x0 , x0 ). Then,
ϕ is p.d. if and only if ψ is n.d.
Proposition 17: The function ψ : X × X → R is a n.d.
kernel if and only if exp(−tψ) is p.d. for all t > 0.
Proposition 18: The function ψ : X × X → R+ is a n.d.
kernel if and only if (t + ψ)−1 is p.d. for all t > 0.
Proposition 19: If ψ is n.d. and nonnegative on the diagonal, i.e., ψ(x, x) ≥ 0 for all x ∈ X , then so are ψ α , forα ∈ [0, 1], and log(1 + ψ).
Proposition 20: Let f : X → R with f ≥ 0; then, forα ∈ [1, 2], ψα (x, y) = −(f (x) + f (y))α is a n.d. kernel.
The following definition has been used in a machine learning context [23], following [27].
Definition 21 (Semigroup Kernels): Let (X , +) be asemigroup. A function ϕ : X → R is called p.d. (in the semigroup sense) if k : X ×X → R, defined as k(x, y) = ϕ(x+y),
is a p.d. kernel. Likewise, ϕ is called n.d. if k is a n.d. kernel.
B. Jensen-Shannon and Tsallis kernels
The basic result underlying JSD- and JTqD-based p.d.
kernels is the fact, shown in the following proposition, thatthe denormalized Tsallis q-entropies (6) are n.d. functions
S
on M+q (X ), for q ∈ [0, 2]. Of course, this includes thedenormalized Shannon entropy (3) as a particular case (forq = 1). Although, for the Shannon entropy case, part of theproof is in [27], [25], [23], we present a general proof here.
Proposition 22: For q ∈ [0, 2], the denormalized TsallisS
q-entropy Sq is a n.d. function on M+q (X ).
Proof: Since n.d. kernels are closed under pointwise integration, it suffices to prove that ϕq (see (7)) is n.d. on R+ . For
q 6= 1, ϕq (y) = (q−1)−1 (y−y q ), thus ϕq = |q−1|−1 (ξq +γq ),where ξq (y) = y sign(q − 1) and γq (y) = y q sign(1 − q), bothdefined on R+ . Since the set of n.d. functions is closed undersums and multiplications by non-negative scalars, this reduces
to showing that both ξq and γq are n.d. Function ξq is both n.d.
and p.d. for any q. For q ∈ [0, 1[, γq = ξaq , for any a > 1; sinceξa is n.d. and nonnegative, Prop. 19 guarantees that γq is also
n.d. For q ∈]1, 2], Prop. 20 guarantees that k(x, y) = −(x+y)q
is n.d., thus so is γq .
For q = 1, we use the fact that,x − xq= lim ϕq (x),ϕ1 (x) = ϕH (x) = −x log x = lim
q→1q→1 q − 1
where the limit is obtained by L’Hôpital’s rule; since the setof n.d. functions is closed under limits, ϕ1 (x) is n.d.
We are now in a position to present the main contributionof this section, which is a family of weighted Jensen-Tsallis
kernels, generalizing the JSD-based (and other) kernels inthree ways
• they allow using unnormalized measures;• they allow using different weights for each of the twoarguments;• they extend the mutual information feature of the JSD
kernel to the nonextensive scenario.

Definition 23 (weighted Jensen-Tsallis kernels (WJSK)):SSThe kernel ϕ
eq : M+q (X ) × M+q (X ) → R is defined as¡¢ϕeq (µ1 , µ2 ) = 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 )).
³´2SThe kernel ϕq : M+q (X ) \ {0} → R is defined asϕq (µ1 , µ2 ) = Sq (π) − Tqπ (p1 , p2 ).
Proposition 24: The kernel ϕeq is p.d., for q ∈ [0, 2].
Proof: Writing µ1 = ω1 p1 and µ2 = ω2 p2 and using thedenormalization formulae of Prop. 2, we obtain, after algebra,
(1,1)
(1,1)
ϕ
eq (µ1 , µ2 ) = −Tq,Sq (µ1 , µ2 ). Since −Tq,Sq (µ1 , µ2 ) =−Sq (µ1 + µ2 ) + Sq (µ1 ) + Sq (µ2 ) = −Sq (µ1 + µ2 ) + Sq (µ1 +µ0 ) + Sq (µ2 + µ0 ) − Sq (µ0 + µ0 ), with µ0 = 0, and Sq is n.d.
(1,1)(Prop. 22), Prop. 16 guarantees that −Tq,Sq is p.d.
Proposition 25: The kernel ϕq is p.d., for q ∈ [0, 1].
Proof: Observe that ϕq (µ1 , µ2 ) = ϕeq (µ1 , µ2 )(ω1 +ω2 )−q . The result follows from the fact that the product of
two p.d. kernels is a p.d. kernel and (ω1 + ω2 )−q is a p.d.
kernel, for q ∈ [0, 1] (see [27]).
The following are particular cases of WJTK, for q = 1.
Definition 26 (weighted JS kernel (WJSK)): The kernelHϕe : (M+(X ))2 → R is defined as ϕe=ϕe1 , i.e.,ϕ(µe 1 , µ2 ) = (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 )).
¡ H¢2Analogously, the kernel ϕ : M+
(X ) \ {0}→ R issimply ϕ = ϕ1 , i.e.,ϕ(µ1 , µ2 ) = H(π) − J π (p1 , p2 ).
e and ϕ are p.d.
Corollary 27: The WJSK ϕ
Proof: Invoke Props. 24 and 25 with q = 1.
The JS kernel (JSK), introduced and shown to be p.d. in[2], is now simply a particular case of the WJSK in Def. 26.
1
Definition 28 (JSK): The kernel kJS : (M+(X ))2 → R is
defined as kJS (p1 , p2 ) = 1 − JS(p1 , p2 ).

Corollary 29: The kernel kJS is p.d.
1
Proof: kJS is the restriction of ϕ to (M+(X ))2 .
The so-called exponentiated JSK (EJSK), next defined, hasbeen used (and shown to be p.d.) by several authors [23].
thekernelDefinition 30 (EJSK): Let
1(M+(X ))2→ R be defined (for t
k EJS (p1 , p2 ) = exp [−t JS (p1 , p2 )] .

k EJS:> 0) asCorollary 31: The EJSK is p.d.
Proof: Invoke Prop. 17 and the fact that kJS is n.d.
Next, we introduce a weighted generalization of the EJS
kernel, which allows unnormalized measures as its arguments.

Definition 32 (Weighted EJSK (WEJSK): DefineHHkernel kWEJS : M+
(X ) × M+(X ) → R, for t > 0, as
π

kWEJS (µ1 , µ2 ) = exp(t H(π)) exp [−tJ (p1 , p2 )] .

the
(23)

Corollary 33: The kernel k WEJS is p.d.
Proof: From Prop. 17 and Cor. 27. Notice that although
kWEJS is p.d., none of its exponential factors in (23) is p.d.
Finally, we study two particular (nonextensive) members
cases of the family of Tsallis kernels.
Definition 34 (Boolean kernel): Let the kernel kBoole :S0
S0
M+(X ) × M+(X ) → R be defined as kBoole = ϕ
e0 , i.e.,kBoole (µ1 , µ2 ) = (card(π) − 1) card(µ1 ¯ µ2 ).

(24)

Definition 35 (Linear kernel): Let the kernel klin
11
M+(X ) × M+(X ) → R be defined as
klin (p1 , p2 ) =1
hp1 , p2 i.
2

:

(25)

Corollary 36: The kernel kBoole is p.d.
Proof: Invoke Prop. 24, with q = 0.
Corollary 37: The kernel klin is p.d.
Proof: This well-known property of the inner productkernel [1], also results from Prop. 24, since klin (p1 , p2 ) =ϕ2 (p1 , p2 ) = ϕe2 (p1 , p2 )/4.
In conclusion, the Boolean kernel, the JSK, and the linear
kernel, are simply particular elements of the much wider family of Tsallis kernels, continuously parameterized by q ∈ [0, 2].
Furthermore, the Tsallis kernels are a particular subfamily ofthe even wider set of weighted Tsallis kernels.
VII. C ONCLUSION
In this paper we have introduced a new family of positive
definite kernels between measures, which contain previous
information-theoretic kernels on probability measures as particular cases. One of the key features of the new kernels is thatthey are defined on non-normalized 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 [2],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 can be multiplied by arbitrary(positive) weights before being fed to the kernel function.
Technically, the new kernels, and the proofs of positive
definiteness, are supported on other contributions of this paper:
the new concept of q-convexity, for which we proved aJensen q-inequality; the concept of Jensen-Tsallis q-difference,a nonextensive generalization of the JSD; denormalization
formulae for several entropies and divergences.
We are currently experimentally assessing the performanceof these new kernels, namely on text classification problems.

R EFERENCES[1] B. Schölkopf and A. J. Smola, Learning with Kernels, MIT Press, 2002.
[2] M. Hein and O. Bousquet, “Hilbertian metrics and positive definite
kernels on probability measures,” in Proc. 10th Intern. Workshop on
Artificial Intelligence and Stats., 2005.
[3] M. Cuturi, K. Fukumizu, and J.-P. Vert, “Semigroup kernels on measures,” J. Mach. Learn. Res., vol. 6, pp. 1169–1198, 2005.
[4] J. Lafferty and G. Lebanon, “Diffusion kernels on statistical manifolds,”
J. Mach. Learn. Res., vol. 6, pp. 129–163, 2005.
[5] J. Lin, “Divergence measures based on the Shannon entropy,” IEEE
Trans. Inf. Th., vol. 37, pp. 145–151, 1991.
[6] A. Rényi, “On measures of entropy and information,” in Proc. 4thBerkeley Symp. Math. Statist. and Prob., vol. 1. Berkely: Univ. Calif.
Press, 1961, pp. 547–561.
[7] M. E. Havrda and F. Charvát, “Quantification method of classification
processes: concept of structural α-entropy,” Kybernetika, vol. 3, pp. 30–
35, 1967.
[8] Z. Daróczy, “Generalized information functions,” Information and Control, vol. 16, pp. 36–51, Mar. 1970.
[9] J. Costa and A. O. Hero, “Geodesic entropic graphs for dimension andentropy estimation in manifold learning,” IEEE Trans. Signal Proc.,vol. 52, pp. 2210–2221, 2004.
[10] Neemuchwala, A. O. Hero, and P. Carson, “Image matching using
α-entropy measures and entropic graphs,” Signal Processing, vol. 85,
pp. 277–296, 2005.
[11] C. Tsallis, “Possible generalization of Boltzmann-Gibbs statistics,” J.
Stat. Physics, vol. 52, pp. 479–487, 1988.
[12] S. Abe, “Foundations of nonextensive statistical mechanics,” in Chaos,Nonlinearity, Complexity, Springer, 2006.
[13] S. Abe and Y. Okamoto, Nonextensive Statistical Mechanics and Its
Applications, Springer, 2001.
[14] J. Hu, W. Tung, and J. Gao, “Modeling sea clutter as a nonstationary andnonextensive random process,” in IEEE Int. Conf. Radar, Gainesville,FL, 2006.
[15] Y. Li, X. Fan, and G. Li, “Image segmentation based on Tsallis-entropy
and Renyi-entropy and their comparison,” in IEEE Int. Conf. Indust.
Informatics, 2006.
[16] S. Martin, G. Morison, W. Nailon, and T. Durrani, “Fast and accurate
image registration using Tsallis entropy and simultaneous perturbation
stochastic approximation,” Electronics Letters, vol. 40, pp. 595–597,
2004.
[17] J. Jensen, “Sur les fonctions convexes et les inégalités entre les valeursmoyennes,” Acta Mathematica, vol. 30, pp. 175–193, 1906.
[18] T. Cover and J. Thomas, Elements of Information Theory, Wiley, 1991.
[19] J. Burbea and C. R. Rao, “On the convexity of some divergence measures
based on entropy functions,” IEEE Trans. Inf. Th., vol. 28, pp. 489–495,
1982.
[20] A. Martins, M. Figueiredo, and P. Aguiar, “On nonextensive entropies
and divergences and their application to kernels on measures,” 2008, tobe submitted.
[21] H. Suyari, “Generalization of Shannon-Khinchin axioms to nonextensive
systems and the uniqueness theorem for the nonextensive entropy,” IEEE
Trans. Inf. Th., vol. 50, pp. 1783–1787, 2004.
[22] S. Furuichi, “Information theoretical properties of Tsallis entropies,” J.
Math. Phy., vol. 47, 2006.
[23] M. Cuturi and J.-P. Vert, “Semigroup kernels on finite sets,” in Advancesin Neural Information Processing Systems 17, pp. 329–336, MIT Press,
2005.
[24] D. M. Endres and J. E. Schindelin, “A new metric for probability
distributions,” IEEE Trans. Inf. Th., vol. 49, pp. 1858–1860, 2003.
[25] F. Topsøe, “Some inequalities for information divergence and related
measures of discrimination,” IEEE Trans. Inf. Th., vol. 46, pp. 1602–
1609, 2000.
[26] A. B. Hamza, “A nonextensive information-theoretic measure for image
edge detection,” Journal of Electronic Imaging, vol. 15-1, pp. 13 011.1–
13 011.8, 2006.
[27] C. Berg, J. Christensen, and P. Ressel, Harmonic Analysis on Semigroups, Springer, 1984.