Generative kernels
André Martins
atm@priberam.pt

December 9, 2006

Abstract
Kernel methods are a field of intensive research in machine learning.
Lately, much attention has been dedicated to the problem of “kernel
learning”, i.e., choosing the kernel that best suits a particular task.
Many discriminative approaches avoid handling this problem directly,
ignoring the process of data generation to represent them as vectors ina suitable Euclidean space. By contrast, generative approaches propose
devising kernels directly by properly modeling the generation of data;
this way prior knowledge about their structure may be introduced. In
this framework, objects are modeled as outcomes of random processes,
for example HMMs for strings, or multinomials for text documents.
The aim of this report is providing a survey on generative kernels,
capturing the essential theoretical aspects on which they settle, andhighlighting the main geometrical ideas.

1

Introduction

Although the theoretical background of kernel methods has been established many decades ago, the support vector classifier, which is perhaps
the first “conscient” application of kernels in a learning algorithm, was introduced only in the early 90s [Vap00]. After that, kernel methods wereadopted for many other learning tasks besides classification, such as regression, principal component analysis, independent component analysis, etc.
(see [SS02, STC04]). Their great popularity derives from the fact that a(positive definite) kernel corresponds to an inner product in some feature
space. This allows extending the capacity of linear algorithms that depend
only on pairwise inner products among data to a nonlinear framework, by
replacing each inner product by a kernel evaluation.
Addressing a particular learning problem with a kernel-based approachrequires choosing a kernel function that properly captures the similarity
among data. The choice of the kernel should reflect our prior knowledge
about how data is generated. While classic approaches usually focus on
how to obtain easily computable kernels by representing data as vectors in1

a suitable Euclidean space, thus ignoring how their generation is governed,
this is sometimes a misleading perspective, specially for structured objects
that don’t naturally “live” in Euclidean spaces, such as strings or text documents. Although there has been some impressive results from nongenerative
approaches specially devised to handle this sort of data, like convolutional
kernels for discrete objects [Hau99], we concentrate here on generative approaches that prefer to model objects as outcomes of random processes, forexample HMMs for strings, or multinomials for text documents. The aimof this report is to give a general overview on recent generative strategies
to devise kernels, while clarifying the essential aspects of the backgroundtheory on which they settle.
In Section 2 we revise some basic notions of topology and measure theory
that form the background for the subsequent sections. We also define someconcepts from information theory that are later used, such as the JensenShannon divergence. Section 3 characterizes positive and negative kernels,
and highlights important relations between these two classes. We briefly
mention semigroup kernels, that are intensively studied in [BCR84] and applied in [CV05, CFV05]. This section culminates with the proof that entropy
is a negative definite function and that the Jensen-Shannon divergence is thesquare of a metric, something that only recently was taking into account bymachine learners [Top00, Top02, ES03]. Section 4 aims to introduce an information geometrical perspective, inspired by [AN01, MR93]. We shall seethat many generative kernels rely on intuitive reasonings underlying the geometry of probability distributions and measures. Section 5 illustrates all
this by mentioning some examples of generative kernels that were recently
devised, mainly for structured objects like images, text documents or strings.
Finally, Section 6 concludes the paper.

2

Topological spaces and measures

We begin by revising the basic notions of topology and measure theory thatare later used. Since we are going to deal with objects in structured domainsthat are not necessarily Euclidean, it makes sense to work in more general
topological spaces. Specifically we are going to work with Radon measures in
Hausdorff spaces; these are more general than the Lebesgue-Borel measure
traditionally used in Euclidean spaces with the product topology.

2.1

Topological spaces

Let X be a set and P(X) the collection of its parts. A topology on X is acollection T ⊆ P(X) that contains both ∅ and X, and that is closed underfinite intersections and arbitrary unions; the members of T are called open
sets. A set X together with its topology T is called a topological space anddenoted (X, T ), or simply X when the underlying topology is clear from the2context. A set S ⊆ X is called closed if its complement S c ≡ ∁X S is open.
Obviously ∅ and X are simultaneously open and closed for any topology.
Given a topological space (X, T ), a basis for the topology T is any
family of sets {Bi }i∈I that generates T by taking finite intersections andarbitrary unions of its elements. Any subset S ⊆ X becomes itself a topological space if we endow it with the induced topology, where V ⊆ S is declared
open if there is some U ∈ T such that V = U ∩ S.
A map f between two topological spaces (X, TX ) and (Y, TY ) is called
continuous if the inverse image of any open set in Y is open in X, i.e., if
f −1 (V ) ∈ TX for all V ∈ TY . Since f −1 (∁Y V ) = ∁X f −1 (V ) we can replace“open” by “closed” in this definition. If x ∈ X, any open set U containing
x is called a neighborhood of x.
A subset S of X is said to be compact if any open covering of S has S
a finitesubcovering, i.e. if for any family of open sets {Si }i∈I such that S ⊆ i∈I Si
there exists a finite subfamily {Si1 , . . . , Sin } such that S ⊆ Si1 ∪ . . . ∪ Sin .
An important fact is that the image of a compact set under a continuous
map is a compact set, i.e., continuous maps preserve compactness.
Example 2.1 (Discrete topology.) Given a set X, declare any of its subsets to be open. This leads to the “discrete topology”. The singletons of X
form a basis for this topology. In this topology, a set is compact if and only
if it is finite.
Example 2.2 (Ordinary topology in R.) Let X = R and define a set
S open if any point x ∈ S belongs to an open interval contained in S (asusual). This leads to the “ordinary topology”. Then, a set C ⊆ X is compact
if and only if it is closed and bounded.
Example 2.3 (Banach spaces.) Let V be a vector space over C (analogously, over R). A norm in V is a function k.k : V → R+ that satisfies, forall α ∈ C and u, v ∈ V :• kuk = 0 if and only if u = 0,
• kαuk = |α| · kxk,
• ku + vk ≤ kuk + kvk.
If V is endowed with a norm, we may define a family of open balls of theformBǫ (u) = {v ∈ V : kv − uk < ǫ},(2.1)
and this induces a topology, called the ordinary topology in V : declare a set
S open if any point in S is the center of some open ball contained in S.
If V is complete with respect to its norm, i.e., if any Cauchy sequence
in V converges to an element of V , then it is called a Banach space.
3

It turns out that a set S ⊆ V is compact if and only if it is complete andcovered by a finite number of balls of fixed radium1 .
Example 2.4 (Hilbert spaces.) Let V be a vector space over C. An innerproduct in V is a function h., .i : V × V → C satisfying for all u, v, w ∈ V
and all α, β ∈ C:
• hαu + βv, wi = α hu, wi + β hv, wi,• hu, vi = hv, ui,• hu, ui ≥ 0 with equality if and only if u = 0.
The first two properties mean that h., .i is sesquilinear (linear in the firstargument and conjugate linear in the second). The analogous definition forvector spaces over R skips the conjugate sign, hence implying bilinearity.
Any inner product induces a norm via kxk ≡ hx, xi1/2 . Hence we canalso define open balls and obtain the ordinary topology in V .
If V is complete with respect to the induced norm, it is called an Hilbert
space. Hence, Hilbert spaces are particular cases of Banach spaces.
Example 2.5 (Metric spaces.) A metric space is a set X endowed witha metric, i.e., a function d : X × X → R+ that satisfies, for all x, y, z ∈ X:
• d(x, y) = 0 if and only if x = y.
• d(x, y) = d(y, x) for all x, y ∈ X.
• d(x, z) ≤ d(x, y) + d(y, z) for all x, y, z ∈ X.
We may also define open balls in a metric space, throughBǫ (x) = {y ∈ X : d(x, y) < ǫ}

(2.2)

and obtain the ordinary topology in the usual way. Defining Cauchy sequences and completeness with respect to the metric allows characterizing
compact sets in X analogously.
Any normed vector space is a metric space, defining d(x, y) ≡ ky − xk.
Although metric spaces are more general than normed vector spaces, they do
not introduce a great “degree of generality”. In fact, every metric space canbe embedded in a normed vector space in the following way [Lan93]: define,for each x ∈ X, the function fx : X → R by fx (y) = d(x, y). Notice thatd(x, y) = kfx − fy kS , where k.kS is the sup-norm, kf kS ≡ supx∈X |f (x)|.
Fix an element a ∈ X and define gx = fx − fa . It turns out that the map
x 7→ gx is an isometry, i.e., a distance-preserving embedding of X into thenormed vector space of bounded functions on X.
1

An alternative characterization is: S is compact if and only if it has the BolzanoWeierstrass property (every sequence in S has a point of accumulation in S).

4

Example 2.6 (Hausdorff spaces.) An Hausdorff space is a topologicalspace (X, T ) where any pair of distinct points can be separated by open sets,that is, for any x, y ∈ X with x 6= y there exist U, V ∈ T with U ∩ V = ∅such that x ∈ U and y ∈ V (see Figure 1).
Hausdorff spaces generalize metric spaces: any metric space under theordinary topology is Hausdorff. An important fact is that, if X is Hausdorff,
then any compact subset C ⊆ X is necessarily closed. In particular, any
singleton is closed.

Figure 1: Hausdorff space: two points separated by open sets.

2.2

Measures

Let X be a set. A σ-algebra on X is a collection M ⊆ P(X) that contains∅ and that is closed under taking complements and countable unions (hence
it is also closed under taking countable intersections); the members of M
are called measurable sets, and (X, M ) is called a measurable space.
If X is endowed with a topology, a natural σ-algebra is the algebra B(X)of the Borel subsets of X, i.e., the algebra generated by the open subsets of
X. An element of B(X) is accordingly called Borel measurable.
A positive measure on a measurable space (X, M ) is a mapµ : M → [0, ∞](2.3)(possibly taking infinite
values)S
P∞which is countably additive, i.e., such thatµ(∅) = 0 and µ( ∞
A
)
=
i=1 i
i=1 µ(Ai ) for any sequence of mutually disjoint measurable sets {Ai }i∈N . A measurable space together with a measureµ is called a measured space and denoted (X, M , µ). A positive measuredefined on B(X) is called a Borel measure.
To define the integral in a measured space (X, M , µ), we first consider
step functions and then proceed to µ-measurable functions. A step function is a function ϕ : X → R that is step with respect to some partition{A1 , . . . , ArR} of someP
set A ⊆ X of finite measure. The integral of ϕ is thendefined as ϕ dµ = ri=1 µ(Ai )ϕ(Ai ). A function f : X → R is called µmeasurable if it is the pointwise limit of a sequence of step functions {ϕn }n∈Nalmost everywhere (i.e. in any point of X \ Z where RZ is some setR of nullmeasure). In that case, the integral of f is defined as f dµ = lim ϕn dµ.
5The case X = Rn endowed with the Lebesgue-Borel measure corresponds to
the Lebesgue integral.
We next proceed by introducing Radon measures on Hausdorff spaces,
following [BCR84]. This framework is generic enough for our purposes while
avoiding the “pathologies” that occur in the general measure theory in arbitrary sets.
Definition 2.7 (Radon measure.) Let X be an Hausdorff space. A Radon
measure on X is a Borel measure satisfying:• µ(C) < ∞ for each compact subset C ⊆ X,
• µ(B) = sup{µ(C) : C ⊆ B, C compact} for each B ∈ B(X).
We denote the set of all Radon measures on X by M+ (X).
Example 2.8 (Finite Radon measures.) A Radon measure is finite ifµ(X) < ∞; the set of finite Radon measures is denoted M+b (X). By considering the second requirement of Definition 2.7 on B c , we conclude that
finite Radon measures satisfyµ(B) = inf{µ(U ) : B ⊆ U, U open}(2.4)

for each B ∈ B(X) (this is stated without proof in [BCR84]). In fact, wehave thatµ(B) = µ(X) − µ(B c ) == µ(X) − sup{µ(C) : C ⊆ B c , C compact} == inf{µ(C c ) : B ⊆ C c , C compact}.

(2.5)

Since X is Hausdorff, the compactness of C implies that C c is open, andµ(B) = inf{µ(U ) : B ⊆ U, U open, U c compact}.

(2.6)

Let’s see that we may skip the “U c compact” restriction, i.e., that

∀

ǫ>0

∃

C compact

B ⊆ Ccandµ(C c ) < µ(U ) + ǫ.

(2.7)

In fact, by Def. 2.7 it exists C ⊆ U c compact such that µ(C) > µ(U c ) − ǫ
for an arbitrarily small ǫ. Hence µ(C c ) = µ(X) − µ(C) < µ(U ) + ǫ, andB ⊆ U ⊆ C c as wanted.
Definition 2.9 (Molecular measures.) The support of a Radon measure µ on X is defined assupp(µ) = {x ∈ X : µ(U ) > 0 for each neighborhood U of x}.

(2.8)

Radon measures with a finite support are called molecular measures; the setof all molecular measures on X is denoted Mol+ (X).
6

Example 2.10 The Lebesgue measure on the Euclidean space Rn equippedwith the ordinary topology is a Radon measure with support Rn . In fact,
although any countable set has zero measure, any neighborhood of a point in
Rn has strictly positive measure.
Example 2.11 Let X be an Hausdorff space equipped with the discrete
topology, and let x ∈ X. The Dirac measure εx : B(X) → [0, ∞] is defined as
1, if x ∈ A(2.9)
εx (A) =0, if x ∈/ A.
εx is a Radon measure and supp(εx ) = {x}. Thus any Dirac measure is amolecular measure. Conversely, it can be shown that any molecular measure is a finite convex combination of Dirac measures (this is omitted in[BCR84]): let µ ∈ Mol+ (X) have support {x1 , . . . , xn } for some n ∈ N. We
first prove that any set that does not intersect supp(µ) has null measure.
From the definition of Radon measure, it suffices to prove this for any compact set C. Since C ∩ supp(µ) = ∅, any y ∈ C must admit a neighborhood
Uy with null measure. The family of neighborhoods (Uy )y∈C covers C, hencefrom the compactness
of C there is a finite subcovering (Uyi )i=1,...,m implying
P
that µ(C) ≤ mµ(Uyi ) = 0, as we wanted to prove. Now, let ai = µ({xi })i=1
for i = 1, . . . , n, which are finite numbers since the sets {xi } are compact.
Then, for any set A, we haveµ(A) = µ(A ∩ supp(µ)) + µ(A ∩ (supp(µ))c ) == µ(A ∩ supp(µ)) =nXai εxi (A).
=

(2.10)i=1

A Radon probability measure on X is a Radon measure µ ∈ M+ (X) suchthat µ(X) = 1. The set of Radon probability measures on X is denoted
M+1 (X); it can be seen as the set of equivalence classes of finite Radon
measures by the equivalence relation in M+b (X)µ1 ≡ µ2

if there exists λ ∈ R such that µ1 = λµ2 .

(2.11)

which means that any finite Radon measure can be normalized to give rise
to a Radon probability measure.
Consider a measured space (X, M , ν) where X is Hausdorff, and ν is
σ-finite, i.e., is such that X can be written as the countable union of setsof finite measure2 . We say that a measure µ is ν-absolutely continuous(denoted µ ≪ ν) if µ vanishes wherever ν does, i.e., if ν(A) = 0 impliesµ(A) = 0 for any A ∈ M . If this happens, the Radon-Nikodym theorem
2E.g. the union of closed unit intervals in R with the Lebesgue-Borel measure.

7

guarantees the existence (and uniqueness up to equivalence within measurezero) of Ra density function f : X → R+ such that, for all A ∈ M , we haveµ(A) = A f dν.3 This density is called the Radon-Nikodym derivative anddenoted f = dµdν , since
Z
Z
f dν.
(2.12)dµ =µ(A) =AA

If g : X → R is an arbitrary function, we define its L1 (ν)-norm
ZZ|g(x)| dν(x)|g| dν =kgk1 ≡(2.13)

X

X

R
whenever the integral exists. If g is a density, we have kgk1 = X gdν, and
if in particular g is the density of a probability measure, then kgk1 = 1.
Suppose now that X is a countable set. In this particular case, thecounting measure (the measure that assigns to each finite set its number of
elements, and ∞ to each infinite set4 ) becomes
σ-finite,and may be takenRP
as the dominating measure ν. Then, X f dν = x∈X f (x), and we may
replace integrals by sums. If instead X ⊆ RRn , we mayR take ν to be theusual Lebesgue-Borel measure, resulting then X gdν = X g(x)dx. So, theusage of integrals with respect to a dominating measure provides us witha unified framework for dealing with measures in both the “discrete” and“continuous” scenarios.

2.3

Entropy and divergence measures

Let (X, M , ν) be a measured space where X is Hausdorff and ν is a σfinite Radon measure. Let M+h (X) ⊆ M+b (X) denote the set of finite
Radon ν-absolutely continuous measures whose density f : X → R+ satd
M+h (X) the set of densities5 of thoseisfies kf · log f k1 < ∞. Denote by dνdM+h (X) → R is defined bymeasures. The entropy function h : dνZh(f ) = −f log f dν,(2.14)
X

where 0 log 0 = 0 by convention.
Remark 2.12 This definition of entropy generalizes the traditional notionsof discrete and differential entropies presented for example in [CT91]. Denote by M+1,h (X) = M+h (X) ∩ M+1 (X) the set of Radon probability measures with finite entropy. If X ⊆ Rn , ν is the Lebesgue-Borel measure, and3

The σ-finiteness of ν is indeed necessary. For a counterexample take ν to be thecounting measure on R and µ the Lebesgue-Borel measure; the existence of a density fwould imply f = 0 and as consequence µ = 0.
P
4
When X is countable it may be seen as the sum of all Dirac measures on X, x∈X εx .
5More exactly, the set of equivalence classes of densities that are equal almost everywhere.

8P ∈ M+1,h (X) is a probability measure with density p = dPdν , then h(p) reduces
to the differential entropyZp(x) log p(x)dx.
(2.15)
h(p) = −X

If, instead, X is a countable set, ν is the counting measure, and P ∈M+1,h (X) is a probability measure with probability mass function x 7→ p(x) =P ({x}), then h(p) ≡ H(p) is the discrete entropyX
H(p) = −p(x) log p(x).
(2.16)x∈X

Let f and g be respectively the densities (with respect to the dominating
measure ν) of measures µf and µg in M+h (X), such that µf is µg -absolutely
continuous (i.e. µf ≪ µg ≪ ν). The Kullback-Leibler divergence between f
and g is defined byZff log dν =D(f kg) =g
XZf log gdν.
(2.17)= −h(f ) −X

If f and g are probability densities, the Kullback-Leibler divergence can beseen as a dissimilarity measure between the two distributions. It verifies
D(f kg) = 0 if and only if f = g almost everywhere. However, it is not a
metric (it is not symmetric and it does not satisfy the triangle inequality).
It is clear that M+ (X) and M+b (X) are convex cones, and that M+1 (X)is a convex set. By linearity of the integral, so are the respective sets ofdensities. So we can talk about “mixtures of densities”. These may becharacterized by the following divergence measure:
Definition 2.13 Let f1 , . . . , fn be densities of measures in M+h (X), andf = α1 f1 + . . . + αn fn a mixture defined by coefficients α1 , . . . , αn ∈ R+ .
The generalized Jensen-Shannon divergence of f1 , . . . , fn with respect to that
mixture is defined by
!
n
n
X
X
J(f1 , . . . , fn ; α1 , . . . , αn ) ≡ h
αi fi −
αi h(fi ),(2.18)
i=1

i=1

The
requiring
Pn restriction of J to probability densities is defined analogously
1i=1 αi = 1. The particular case where n = 2 and α1 = α2 = 2 is simply
called Jensen-Shannon divergence between f and g and denoted J(f kg):
f +g
h(f ) + h(g)J(f kg) ≡ h.
(2.19)−
22
9

It is straightforward that the Jensen-Shannon divergence relates to the
Kullback-Leibler divergence via




f +g
1
f +g
1
+ D g
.
(2.20)J(f kg) = D f2
2
2
2
From (2.20), one can see that J is symmetric and inherits from the KullbackLeibler divergence the property that J(f kg) = 0 if and only if f√= g almost
everywhere. A remarkable fact that will be shown later is that J satisfies
the triangle inequality, i.e., the Jensen-Shannon divergence is actually thesquare of a metric.

2.4

The Jensen-Shannon divergence as mutual information

In [GBGC+ 02] several interpretations of the Jensen-Shannon divergence are
given, namely in the fields of statistical physics, information theory andmathematical statistics. We reproduce here the interpretation concerning
information theory.
Let Σ = {σ1 , . . . , σk } be a finite alphabet and t1 , . . . , tm be m strings
emitted by different sources, with lengths |t1 |, . . . , |tm |. Consider the nlength
P string s = t1 . . . tm formed by concatenating the m strings, wheren= m
i=1 |ti |. Suppose that we choose a random position 1 ≤ p ≤ n with auniform probability distribution and define the random variablesσ ≡ “the symbol at position p”, σ = s[p]t ≡ “the string (among t1 , . . . , tm ) corresponding to position p”|t |Let p(σi ) = Pr{σ = σi } and p(tj ) = Pr{t = tj } = nj , and denote thecorresponding conditional and joint probabilities by p(σi |tj ) and p(σi , tj ). A
typical question in information theory is: “How much information I can we
obtain from learning the identity of the symbol σ about the identity of thesubstring t, provided the probability distribution p(σi , tj )?”. I is called themutual information in σ about t and is defined by
I≡

m
k X
X

p(σi , tj ) log

i=1 j=110p(σi , tj )p(σi )p(tj )(2.21)

From Bayes’ rule, p(σi , tj ) = p(σi |tj )p(tj ), and (2.21) may be rewritten as
I =

m
k X
X
i=1 j=1=mXp(σi |tj )p(tj ) log

p(tj )

j=1

k
X
i=1

p(σi |tj )=p(σi )p(σi |tj ) log p(σi |tj ) −

k
X
i=1




m
X
j=1

p(tj )p(σi |tj ) log p(σi ) =



m
m
X
X
p(tj )p(σi |tj ) =p(tj )H(p(.|tj )) + H 
= −
j=1



j=1

= J (p(.|t1 ), . . . , p(.|tm ); p(t1 ), . . . , p(tm )) ,(2.22)

i.e., the Jensen-Shannon divergence among the probability mass functionsof σ conditioned on each substring, with mixture coefficients the substring
probabilities p(ti ) = |tni | , equals the mutual information in σ about t. If, as
an extreme example, all these probability mass functions are equal, p(.|t1 ) =. . . = p(.|tm ), then the Jensen-Shannon divergence vanishes, meaning thatknowing the identity of σ does not give us any information about the substring where it was picked from.

3

Positive and negative definite kernels

In the last years, the machine learning community have dedicated great
attention to kernel methods [SS02, STC04]. The ability of these methods
to represent “nonlinearities” as “linearities in a feature space” enables extending the classic linear algorithms for classification, regression, and otherlearning tasks, to nonlinear scenarios. Perhaps support vector machines[Vap00] is the first historical example (in early 90s) where kernel methods
were applied in the field of statistical learning theory. More recently, it was
shown that for many learning tasks one could use a larger class of kernels
rather than the usual “positive kernels”. It happens that there are many
results concerning relations between classes of kernels, representation in feature spaces, connections with harmonic analysis, etc., that are known formany time but only recently began to be used in machine learning. We now
give a basic review of some of those results, following [BCR84].

3.1

Definition and properties

In order not to loose generality, we consider all functions to be complexvalued, unless otherwise stated. So, in what follows, if z is a complex number, we denote its conjugate by z. Also, z ≥ 0 means Re(z) ≥ 0 andIm(z) = 0. If A is a matrix, A∗ denotes its conjugate transpose.

11

A positive semidefinite matrix is a hermitian matrix K that, for any
choice of a column vector x, satisfies x∗ K x ≥ 0. A widely known fact isthat positive semidefinite matrices have real and nonnegative eigenvalues.
A squared matrix may be seen as a function defined on I × I, where I is
the finite set of indices. The following is a generalization of this concept tofunctions whose domain X × X is not necessarily finite.
In what follows, X is a nonempty set.
Definition 3.1 (Positive definite kernel.) A function ϕ : X × X → C
is called a positive definite kernel if and only ifn XnXi=1 j=1

ci cj ϕ(xi , xj ) ≥ 0(3.1)

for all n ∈ N, {xi , . . . , xn } ⊆ X and {ci , . . . , cn } ⊆ C. If, for any distinct
x1 , . . . , xn , the equality in (3.1) implies c1 = . . . = cn = 0, then the kernel ϕis called strictly positive definite.
Definition 3.2 (Negative definite kernel.) A function ψ : X × X → C
is called a negative definite kernel if and only if:• ψ is hermitian, i.e., ψ(y, x) = ψ(x, y) for all x, y ∈ X;
• For all n ∈ N, {xi , . . . , xn } ⊆ X and {ci , . . . , cn } ⊆ C with0, it holdsnn XXci cj ϕ(xi , xj ) ≤ 0

Pn

i=1 ci =(3.2)

i=1 j=1

If, for any distinct x1 , . . . , xn , the equality in (3.2) implies c1 = . . . = cn = 0,then the kernel ψ is called strictly negative definite. If ψ is (strictly) negative
definite, we call −ψ (strictly) conditionally positive definite.6
Remark 3.3 The analogous of Def. 3.2 for a real-valued ψ is obtained simply by replacing {ci , . . . , cn } ⊆ C by {ci , . . . , cn } ⊆ R, removing the conjugate
sign and replacing the word “hermitian” by “symmetric”.
In the case of Def 3.1, however, the analogous for real-valued functions has to additionally require ϕ to be symmetric. In fact, in the generalcomplex-valued case, it follows from the definition that any positive definite
kernel is hermitian; however, there are nonsymmetric real-valued functions
satisfying (3.1) for any {ci , . . . , cn } ⊆ R which, of course, are not positive
definite kernels.
6[SS02] goes further by mentioning the more general “conditionally positive definite
kernels of order k.”

12Immediate consequences of Defs. 3.1 and 3.2 are that ϕ is positive (resp.
negative) definite if and only if for any finite subset F ⊆ X the restriction
ϕ|F ×F is positive (resp. negative) definite. In particular, any positive definite kernel ϕ is nonnegative on the diagonal ∆ ≡ {(x, x) ∈ X × X}, i.e.
ϕ|∆ ≥ 0, as can be seen by setting F = {x} for all x ∈ X.
We now list some simple properties of positive and negative definite
kernels.
Property 3.4 If ϕ is positive definite, then for all x, y ∈ X:
|ϕ(x, y)|2 ≤ ϕ(x, x) · ϕ(y, y)(3.3)

Property 3.5 If ψ is negative definite, then for all x, y ∈ X:
ψ(x, x) + ψ(y, y) ≤ 2 Re ψ(x, y)(3.4)

Property 3.6 Any ϕ of the form ϕ(x, y) = f (x) · f (y), where f : X → C
is an arbitrary function, is positive definite. In particular, a constant kernel(x, y) 7→ c is positive definite if and only if c ≥ 0.
Property 3.7 Any ψ of the form ψ(x, y) = f (x) + f (y), where f : X → C
is an arbitrary function, is negative definite. In particular, a constant kernel(x, y) 7→ c is negative definite if and only if c ∈ R.
Proof: The first two properties are easily shown by taking the 2 × 2
hermitian matrix of the kernel restriction to {x, y}. The first follows fromthe nonnegativity of the determinant, and the second from the definition ofnegative definiteness setting c1 = 1 and c2 = −1. The third follows fromnX

ci cj ϕ(xi , xj ) =and the fourth from the fact that, if

i,j=1

2

ci f (xi )

i=1

i,j=1

n
X

n
X

≥ 0,

(3.5)

Pn

i=1 ci = 0, we have

n
n
n
n

 X
X
X
X
ci f (xi )ci = 0, (3.6)
cj +cj f (xj )ci cj f (xi ) + f (xj ) =
j=1

i=1

j=1

i=1

even with equality.
In what follows, K+ (X) and K− (X) denote respectively the sets of positive and negative definite kernels defined on X ×X. Their strict counterparts
will be accordingly denoted K++ (X) and K−− (X).
Property 3.8 K+ (X) and K− (X) are both convex cones, closed in the
topology of pointwise convergence.

13

This is easily verifiable from the definition by using the properties of sums.
It means that if ϕ1 and ϕ2 are positive (resp. negative) definite, so is
λ1 ϕ1 + λ2 ϕ2 for any nonnegative scalars λ1 and λ2 , and that if (ϕn )n∈N is asequence of positive (resp. negative) definite kernels converging pointwise toϕ, then ϕ is positive (resp. negative) definite. Regarding integrals as limits
of weighted sums, it also implies that K+ (X) and K− (X) are closed underpointwise integration, i.e., if (ϕθ )θ∈Θ is a family of positive (resp. negative)
definite kernels and µ is a positive measure on Θ such that ϕθ (x, y) is µintegrable for all x, y ∈ X, then ϕ : X × X → C defined byZϕθ (x, y)dµ(θ)(3.7)
ϕ(x, y) =Θis positive (resp. negative) definite.
The following property goes further by stating that K+ (X) is closed
under taking products.
Property 3.9 If ϕ1 and ϕ2 are positive definite, so is ϕ1 · ϕ2 .
Proof: We follow the proof given in [STC04]. It suffices to show that
the Schur product (i.e. the elementwise product) A ⊙ B of two positive
semidefinite n × n matrices A and B is a positive semidefinite matrix (thiswas proved by Schur in 1911). Consider first the tensor product A ⊗ B ,which results in a positive semidefinite n2 × n2 matrix whose eigenvalues
are the products of the pairs of eigenvalues of A and B , containing A ⊙ B
as a principal submatrix (i.e. [A ⊙ B ]ij = [A ⊗ B ]ki kj where k1 , . . . , kn issome set of n indices from 1, . . . , n2 ). Hence for any c = (c1 , . . . , cn ) there isa c′ = (c′1 , . . . , c′n2 ) filled with zeros except for the entries k1 , . . . , kn , wherec′ki = ci . It follows that c∗ (A ⊙ B )c = c′∗ (A ⊗ B )c′ ≥ 0.
The two latter results imply that the polynomial and Gaussian kernels(widely used in machine learning) are actually positive definite kernels:
Property 3.10 Let ϕ be a positive definite
kernel. Any polynomial combiP
nation with nonnegative coefficients, ni=0 λi ϕi with each λi ≥ 0, is positive
definite. Furthermore, if |ϕ(x, y)| < ρ ≤P∞, and nf : C → C is a holomorphic
function in {z ∈ C : |z| < ρ}, f (z) = ∞n=0 an z , where each an ≥ 0, thenf ◦ ϕ is positive definite. In particular, exp(ϕ) is positive definite.

3.2

Relations between positive and negative definite kernels

We next list some properties that relate positive and negative definite kernels. To get a picture, let us first say that if V is a vector space over C, it
is easy to show that every inner product in V is a positive definite kernel,
and any squared distance induced by an inner product is a negative definite kernel. Later we will see that both positive and negative kernels are
representable more or less like inner products and squared distances.
14

A trivial result is that positive definiteness implies conditional positive
definiteness, i.e., if ϕ ∈ K+ then −ϕ ∈ K− . The following properties, whose
proofs can be found in [BCR84] and are mainly due to Schoenberg, establish
equivalence conditions.
Property 3.11 Let ψ : X × X → C be an hermitian function, and x0 ∈ X.
Define ϕ0 , ϕ : X × X → C by:
ϕ0 (x, y) = ψ(x, x0 ) + ψ(y, x0 ) − ψ(x, y)(3.8)

ϕ(x, y) = ϕ0 (x, y) − ψ(x0 , x0 )

(3.9)

and
Then:
• ϕ is positive definite if and only if ψ is negative definite,• If ψ(x0 , x0 ) ≥ 0, then ϕ0 is positive definite if and only if ψ is negative
definite.
Property 3.12 The kernel ψ : X × X → C is negative definite if and only
if exp(−tψ) is positive definite for all t > 0.
Proof: We first prove the direction ‘⇒’. Let ψ ∈ K− (X). Since
negative definite kernels form a cone, we only need to prove the positive
definiteness of exp(−tψ) for t = 1. Using Property 3.11 and exponentiating
both sides of (3.9) we are led toexp(−ψ(x, y)) = exp(ϕ(x, y))·exp(−ψ(x, x0 ))·exp(−ψ(y, x0 ))·exp(ψ(x0 , x0 ))where ϕ ∈ K+ (X). Hence, by properties 3.6, 3.9 and 3.10 we conclude
that exp(−ψ) ∈ K+ (X). To prove ‘⇐’ we use Property 3.8. If exp(−tψ) ∈K+ (X), then 1 − exp(−tψ) is negative definite, and so is the pointwise limit
ψ = limt→0+

1(1 − exp(−tψ)).
t(3.10)

The following property (whose proof can be found in [BCR84]) uses theresult expressed in (3.7), and gives a first clue about how harmonic analysis
may be important in the study of positive or negative definiteness. We thengive two examples.
Property 3.13 Let µ be a probability
R ∞ measure on R+ with positive finite
first moment, i.e. such that 0 < 0 sdµ(s) < ∞, and let L µ denote its
Laplace transform, i.e.
Z ∞exp(−sz)dµ(s)(3.11)(L µ)(z) =015

for z ∈ C+ = {z ∈ C : Re z ≥ 0} (the complex right half-plane). Then
ψ : X × X → C+ is negative definite if and only if (L µ)(tψ) is positive
definite for all t > 0.
R∞
Example 3.14 The Dirac measure ε1 has first moment 0 sdε1 (s) = 1.
Its Laplace transform isZ ∞exp(−sz)dε1 (s) = exp(−z).
(3.12)(L ε1 )(z) =0Hence we have that a kernel ψ : X × X → C+ is negative definite if and only
if the composition (L ε1 )(tψ) = exp(−tψ) is positive definite for all t > 0,
which is a weaker version of Property 3.12 for a C+ -valued ψ.
ExampleR ∞ 3.15 Using instead the measure µ = exp(−t)dt, whose first moment 0 s exp(−s)ds = 1 is also positive and finite, we get
Z ∞Z ∞exp(−s(z + 1))ds =exp(−sz) exp(−s)ds =(L µ)(z) =
0

0

=

1
.
z+1

(3.13)

Hence we have that a kernel ψ : X × X → C+ is negative definite if andonly if the composition (L µ)(tψ) = (1 + tψ)−1 is positive definite for allt > 0. Replacing t′ = 1t (t′ > 0 ⇔ t > 0) we have that this is equivalent to
the positive definiteness of t′ · (t′ + ψ)−1 and hence of (t′ + ψ)−1 . So we may
restate this as:
Property 3.16 The kernel ψ : X × X → C+ is negative definite if and only
if (t + ψ)−1 is positive definite for all t > 0.
We now present an important class of positive definite kernels, the ind (X).
finitely divisibles, that we denote by K+
Definition 3.17 A positive definite kernel ϕ is called infinitely divisible iffor each n ∈ N there exists a positive definite kernel ϕn that is a n-th rootof ϕ, i.e., such that ϕ = (ϕn )n .
From Property 3.12 it is clear that if ψ is negative definite then ϕ =exp(−ψ) is infinitely divisible. The following property goes further andshows that any R++ -valued infinitely divisible kernel has this form.
Property 3.18 Let ϕ be a positive definite kernel with values in R+ . Then:d (X) if and only if ϕt ∈ K (X) for all t > 0.
• ϕ ∈ K++d (X) if and only if − log ϕ ∈ K (X).
• If ϕ is R++ -valued, then ϕ ∈ K+−

16

The following property allows to derive some important negative definite
kernels.
Property 3.19 Let ψ : X × X → C be a negative definite kernel, and letµ ∈ M+ (R++ ). Consider the function g : D(µ) → C defined byZ ∞(1 − exp(−λz))dµ(λ),(3.14)
g(z) =
0where D(µ) is the set of z ∈ C for which λ 7→ (1−exp(−λz)) is µ-integrable.
Then:• If ψ(X × X) ⊆ D(µ), then g ◦ ψ is negative definite;• A sufficient condition for ψ(X × X) ⊆ D(µ) isZ ∞ψ|∆ ≥ 0 andλ(1 + λ)−1 dµ(λ) < ∞.

(3.15)

0

Proof: The first statement is a consequence of the negative definitenessof 1 − exp(−λψ) for any λ > 0 and the “pointwise integration closure” ofK− (X) expressed in (3.7). The remaining proof is in [BCR84].
Using the formulaszα =αΓ(1 − α)andlog(1 + z) =

Z ∞
0

Z ∞
0

dλ
(1 − exp(−λz)) α+1
λ(1 − exp(−λz))exp(−λ)dλ
λwhere Γ : C+ → C denotes the Gamma functionZ ∞ts−1 exp(−t)dt
Γ(s) =(3.16)(3.17)(3.18)

0that are valid for Re z ≥ 0 and easily established by deriving both sides ofthe equations, we have the following very important result as a consequenceof Property 3.19.
Property 3.20 If ψ is negative definite and satisfies ψ|∆ ≥ 0 then so areψ α for 0 < α < 1 and log(1 + ψ).
Integrating both sides of 3.16 we can also conclude (see [BCR84]) that
Property 3.21 If f : X → C satisfies Re f ≥ 0 then for each α ∈ [1, 2] thekernel ψα (x, y) = −(f (x) + f (y))α is negative definite.
We will see soon how the two latter properties are used to deduce thenegative definiteness of the entropy function.
17

3.3

Hilbert space representation

We are now going to see that any positive or negative definite kernel is representable respectively as an inner product or a squared distance induced
from the inner product in a Hilbert space H (usually called the feature
space by machine learners) via a feature map Φ : X → H that maps eachdata point x ∈ X to its feature representation Φ(x). This is the great
motivation for using kernel methods in learning, since it allows to generalize algorithms that depend only on distances among data (for example,
translation-independent algorithms), or to build nonlinear versions of algorithms that depend uniquely on mutual inner products, by mapping thedata (that in general lies in a unstructured input set) to a well-structured
Hilbert space. This Hilbert space needs not be unique, and neither do webother to find the most “nice” Hilbert space in a general situation. The
idea is never to perform direct computations in H, which has often a very
high dimension, but instead use the kernel function in X to compute innerproducts or distances in H.
We start with the case of positive definite kernels.
Property 3.22 A function ϕ : X × X is a positive definite kernel if andonly if there is an Hilbert space H and a mapping Φ : X → H such thatϕ(x, y) = hΦ(x), Φ(y)i(3.19)

for all x, y ∈ X.
Proof: ‘⇐’: It is immediate, since we haveXXXX
ci cj ϕ(xi , xj ) =ci cj hΦ(xi ), Φ(xj )i =
i

j

i

=

j

*
X

ci Φ(xi ),

i

X

+

cj Φ(xj )j≥0(3.20)

from the “nonnegativity on the diagonal” property of the inner product.
‘⇒’: For each x ∈ X define the function ϕx : X → C by ϕx (y) = ϕ(x, y).
Let H0 denote the linear subspace of CX generated by the functions {ϕx :x ∈ X}. Let f,
P elements of H0 ; they can be written in
Pg : X → C be two
the form f = i ci ϕxi and g = j dj ϕyj for some, not necessarily unique,{ci }, {dj } ⊆ C and {xi }, {yj } ⊆ X. We are going to see that the functionh., .i : H0 × H0 → C defined byXX
hf, gi =ci dj ϕ(xi , yj ) =
i

=

X

j

dj f (yj ) =

X
i

j

18

ci g(xi )(3.21)

is an inner product in H0 . The second line of (3.21) shows that h., .i isindeed well defined (i.e. it does not depend on the choices of the representationsPofP
f and g). It also shows that h., .i is sesquilinear. Moreover,hf, f i = i j ci cj ϕ(xi , xj ) ≥ 0 from the positive definiteness of ϕ. The
sesquilinearity and positivity on the diagonal implies that h., .i is a positive definite kernel on H0 . We can also deduce from (3.21) the reproducing
propertyhf, ϕx i = f (x) for all f ∈ H0 and x ∈ X,
(3.22)
which implies hϕx , ϕy i = ϕ(x, y). Since h., .i is a kernel, from Prop. 3.4 wehave that |f (x)|2 ≤ hf, f i · ϕ(x, x). Hence hf, f i = 0 if and only if f = 0.
Therefore h., .i is an inner product, giving H0 the structure of a pre-Hilbert
space. Then H = H0 (the completion of H0 with the norm induced by h., .i)
is a Hilbert space that we call the reproducing kernel Hilbert space (RKHS)
associated with ϕ. Now define Φ to be the mapping x 7→ ϕx and the proof
is complete.
Although a bit more complicated, the negative definite case reduces tothe “squared Hilbertian distance” representation in the case of real kernels
that vanish on the diagonal (and nowhere else).
Property 3.23 A function ψ : X × X is a negative definite kernel if andonly if there is a Hilbert space H, a mapping Φ : X → H, and a function
f : X → C such that
ψ(x, y) = kΦ(x)k2 + kΦ(y)k2 − 2 hΦ(x), Φ(y)i + f (x) + f (y)(3.23)

for all x, y ∈ X. Moreover,• If there is some x0 ∈ X such that ψ(x, x0 ) ∈ R for all x ∈ X, and if
ψ vanishes on the diagonal, ψ|∆ = 0, then one can choose f = 0;
• If ψ is real-valued, H may be chosen as a real Hilbert space and equation (3.23) becomesψ(x, y) = kΦ(x) − Φ(y)k2 + f (x) + f (y)(3.24)• If ψ is real-valued and vanishes on the diagonal then in addition f = 0,i.e., ψ admits a representation
ψ(x, y) = kΦ(x) − Φ(y)k2(3.25)√
meaning that ψ is a semimetric on X such that Φ is an isometry.
If furthermore ψ is nonzero√ outside the diagonal, i.e., ψ(x, y) = 0 if
and only if x = y, then ψ is a metric.

19

Proof: Apply Proposition 3.22 to1
ϕ(x, y) =ψ(x, x0 ) + ψ(y, x0 ) − ψ(x, y) − ψ(x0 , x0 )2

(3.26)

which is positive definite if and only if ψ is negative definite by Prop. 3.11,
and use the fact thatku − vk2 = kuk2 + kvk2 − 2 Re hu, vi .

(3.27)

Remark 3.24 Notice that it is not true that any squared distance is a negative definite kernel (it is if and only if the distance is Hilbertian). Asa counterexample, consider the metric space X formed by the four points
x1 , x2 , x3 , x4 whose distances are represented below:

x2

x3

2

bc

bc

1

1

x1
bc

2

2
1

bc

x4

The matrix of squared distances,


0
 1
K=
 1
1

1
0
4
4

1
4
0
4


1
4 

4 
0

(3.28)

is not negative definite: take for example c = (−3, 1, 1, 1); then cT Kc =6 > 0. In this particular case it is easy to prove that X cannot be isometrically embedded in an Euclidean space. Assume that it could. Then, from20

d(x1 , x2 ) + d(x3 , x1 ) = d(x2 , x3 ) = 2, the points x1 , x2 and x3 would becollinear, and analogously for x1 , x2 and x4 . But then d(x3 , x4 ) = 0, which
is a contradiction.
According to [BCR84], [SS02], the first known approach to generalize thepositive semidefiniteness of matrices to nonfinite sets occurred in the context
of integral equations, leading to a famous theorem published by Mercer in
1909. Mercer’s theorem considers an alternative representation in a feature
space that is not the RKHS of Prop. 3.22:
Theorem 3.25 (Mercer) Let (X, M , µ) be a finite measure space and κ ∈L∞ (X × X) a symmetric real-valued function such that the integral operator
Tκ : L2 (X) → L2 (X) defined byZ
κ(x, y)f (y)dµ(y)(3.29)(Tκ f )(x) =X

is “Mercer positive definite”7 , that is:Zκ(x, y)f (x)f (y)dµ(x)dµ(y) ≥ 0(3.30)X×X

for all f ∈ L2 (X). Let (ψj )j∈N be the L2 (X)-valued sequence of normalized orthogonal eigenfunctions of Tκ and (λj )j∈N the respective sequence ofnonnegative eigenvalues sorted in non-increasing order. Then:• (λj )j ∈ ℓ1 ,P
• It holds κ(x, y) = ∞j=1 λj ψj (x)ψj (y) with absolute and uniform convergence almost everywhere in X × X.

Remark 3.26 From the second statement it follows that κ corresponds almost everywhereto the ordinary inner product in ℓ2 through the mappingpx 7→ ( λj ψj (x))j∈N . The feature space associated with this mapping is aspace of real-valued sequences and not a space of functions in X as the
RKHS; moreover, the inner product in the Mercer representation is the ordinary inner product for sequences, instead of the more “arbitrary” innerproduct devised in the RKHS. The uniform convergence property guarantees
that one can arbitrarily approximate the kernel function by a representation
in a Euclidean feature space (i.e. a feature space of finite dimension), bykeeping only the highest eigenvalues. All this would make the Mercer representation very appealing, if not for the fact that most kernel-based algorithms
in machine learning merely evaluate the kernel, rather than “working” explicitly in the feature space, and for this it suffices to guarantee the existenceof a representation rather than having to choose a particular one.
7

It turns out that Mercer’s definition of positive definiteness is equivalent to Def. 3.1.

21

3.4

Semigroup kernels

We now focus on a specific class of positive and negative definite kernels
which are called “semigroup kernels” and which are studied with some detailin [BCR84], and see some applications for example in [CFV05]. We will
see that semigroup kernels may be devised for probability distributions byconsidering them as elements in the semigroup of positive measures.
A semigroup (S, ◦) (or simply S) is a nonempty set S equipped with anassociative composition ◦ and a neutral element e. If ◦ is also commutative,
S is called an abelian semigroup. An involution ∗ in a semigroup S is amapping ∗ : S → S satisfying (s ◦ t)∗ = t∗ ◦ s∗ for all s, t ∈ S. This impliese∗ = e. A group is a semigroup where for each element x ∈ X there exists
an inverse x−1 ∈ X verifying x ◦ x−1 = x−1 ◦ x = e.
The motivation for studying kernels on semigroups in statistical learningtheory has to do with the fact that many interesting sets in this framework
lack the structure of group: this happens for example with the positive
measures M+ (X), that form an abelian semigroup under pointwise addition,
but not a group since the only invertible is the null measure.8
Though soon we will focus on abelian semigroups with the identicalinvolution, in what follows we consider the general scenario where (S, ◦, ∗)is a semigroup (possibly a group) with involution.
Definition 3.27 (Positive and negative definite functions.) Let S bea semigroup with involution. A function ϕ : S → C is called positive definite
if (s, t) 7→ ϕ(s∗ ◦t) is a positive definite kernel. Likewise, it is called negative
definite if (s, t) 7→ ϕ(s∗ ◦ t) is a negative definite kernel. These kernels areaccordingly called semigroup kernels.
We denote the set of positive and negative definite functions in S respectively by F+ (S) and F− (S). The entanglement of the semigroup structure with that of kernels induces some strong properties on such functions.
For example, if ϕ is a positive or negative definite function, the fact that(s, t) 7→ ϕ(s∗ ◦ t) is hermitian implies that ϕ(s∗ ) = ϕ(s) for all s ∈ S.
Proposition 3.28 Let ϕ ∈ F+ (S) and ψ ∈ F− (S). The basic properties of
positive and negative definite kernels imply, for all s, t ∈ S:
• ϕ(s∗ ) = ϕ(s), and analogously for ψ. So if we use the identical involution in S any positive or negative function must be real-valued.
• ϕ(s∗ ◦ s) ≥ 0. In particular, ϕ(e) ≥ 0.
• |ϕ(s∗ ◦ t)|2 ≤ ϕ(s∗ ◦ s) · ϕ(t∗ ◦ t). In particular, |ϕ(s)|2 ≤ ϕ(e) · ϕ(s∗ ◦ s).
8Another example of semigroup that may be of particular interest to us is the semigroupof strings under concatenation, which however is not abelian.

22• 2 Re ψ(s∗ ◦ t) ≥ ψ(s∗ ◦ s) + ψ(t∗ ◦ t). In particular, 2 Re ψ(t) ≥ ψ(e) +ψ(t∗ ◦ t).
• F+ (S) and F− (S) are convex cones in CS , and are closed in the topology of pointwise convergence. F+ (S) is stable under pointwise products.
[BCR84] studies in detail positive and negative definite functions. Someinteresting results have to do with the ability of representing a wide class ofthese functions as integrals of semicharacters. This goes beyond our scope, so
we conclude this section by deriving the negative definiteness of the entropy
function, and introducing the Jensen-Shannon kernel.
Example 3.29 (Entropy as a negative definite function.) We are going to show that the entropy function defined in (2.14) is negative definite.
Due to the pointwise integration closure expressed in (3.7), it suffices to showthat the function ψ : R+ → R defined by ψ(y) = −y log y is negative definite.
We reproduce here the proof given in [BCR84] (Example 6.5.16).
Note first that−y α + yα→1 α − 1

ψ(y) = −y log y = lim(3.31)α+yas can be seen by L’Hôpital’s rule. Then it suffices to prove that y 7→ −yα−1
is negative definite for any α ∈ ]1 − ǫ, 1 + ǫ[ \ {1}, with ǫ > 0 sufficiently
small. We are going to actually prove it for α ∈ ]0, 2[ \ {1}. The problem
clearly reduces to prove that ψα : R+ → R defined by αy ,0 < α ≤ 1,
(3.32)ψα (y) =−y α , 1 < α ≤ 2is negative definite for any α ∈ ]0, 2[ \ {1}, and this is ensured by Props. 3.20
and 3.21 from the negative definiteness of ψ1 , −ψ1 and ψ2 .
Example 3.30 (Jensen-Shannon divergence as a squared metric.)
The above result may be used to show that the Jensen-Shannon divergence,
as defined in (2.19), is the square of a metric. As pointed out in [Top02] thiswas only recently taken into account by information theoricists, with several
independent proofs being published (for example, in [ES03] a pure analytical
proof is given, without the insights provided by kernel theory).
By the previous example
h is a negative definite function on the semi
dhgroup dν M+ (X), + , so it follows that (f, g) 7→ h(f + g) is a semigroupddnegative definite kernel on dνM+h (X) × dνM+h (X), and so is the functionddJ˜ : dνM+h (X) × dνM+h (X) → R defined by˜ g) = h f + g
J(f,(3.33)
2
23





f +g
= h (Φ(f ) + Φ(g)) with f 7→ Φ(f ) = f2 . Since in addition
2(f, g) 7→ − h(f )+h(g)is trivially negative definite (see Prop. 3.7), we have2

since hthat J is a negative definite kernel, for being the sum of negative definite
kernels.
√ Since J(f, g) = 0 if and only if f = g, we have by property 3.23
that J is a metric.

Example 3.31 (Jensen-Shannon kernel.) Following [CV05, CFV05] we
now derive a positive definite kernel between measures. Divergence-based
kernels have also been devised in [HB04, MHV03].
˜ is, for any
First, notice that by Prop. 3.18 the kernel κJ˜ = exp(−tJ)
t > 0, positive definite and, in particular, infinitely divisible. Hence, its
normalized version
κJ˜(f, g)p=κJ˜(f, f )κJ˜(g, g)




f +g
h(f ) + h(g)= exp −th+t·=22
= exp (−tJ(f, g))

κJ (f, g) =(3.34)is also, for any t > 0, an infinitely divisible positive definite kernel9 , definedddM+h (X) × dνM+h (X), and satisfying κJ |∆ = 1. Notice however thaton dν
κJ is not a semigroup kernel, unlike κJ˜, although it may be regarded as thenormalization of a semigroup kernel.

4

Information geometry

We now describe some concepts from differential geometry that are usefulto characterize certain properties of parametric and non-parametric statistical models. There actually have been many approaches to reinterpret theclassical statistical and information theoretic methods through a differential
geometric perspective, leading to recent advances in the so-called field of“information geometry” [AN01, MR93]. We start by briefly reviewing somebasic concepts and terminology used in the field of differential geometry,
and then proceed to show how they apply in the geometry of “statisticalmanifolds”.

4.1

Basic concepts of differential geometry

Intuitively, a manifold M is a set that “behaves” locally like an Euclidean
space. We endow M successively with three layers of structure: a topologicallayer, which allows to handle notions as continuity, a differentiable layer,
9
It is easy to show that normalizing a R++ -valued kernel preserves infinitely divisible
positive definiteness.

24which introduces differentiability and smoothness, and a Riemannian layer,
which allows defining lengths, angles, and curvatures.
4.1.1

Topological manifolds

A homeomorphism between two topological spaces X and Y is a map ϕ :X → Y that is continuous, bijective, and whose inverse ϕ−1 is also continuous (this means that each open subset of X is mapped to an open subset
of Y and vice-versa).
Let M be a Hausdorff second countable set, i.e., a Hausdorff space witha countable basis for its topology10 . We say that M is a n-dimensional
topological manifold if it is locally homeomorphic to an Euclidean space
Rn , i.e., if each p ∈ M has a neighborhood U ⊆ M for which there is ahomeomorphism ϕ from U to an open subset of Rn . These homeomorphisms
are called the charts or local coordinate systems of the manifold. A set of
local coordinate systems whose domains cover M is called an atlas.
Not all manifolds admit a global coordinate system: consider for example the sphere or the torus, for which we can only define local coordinate
systems. However, the most addressed in the framework of “informationgeometry” either admit one, or we are only worried about local behaviors
that can be studied using a single coordinate system.
If p ∈ M is a point in the manifold, and ϕ : U ⊆ M → Rn is a local
coordinate system such that p ∈ U , we call ϕ(p) = [ξ 1 (p), . . . , ξ n (p)] ≡[ξ 1 , . . . , ξ n ] the local coordinates of p, and the n functions ξ i : U → R the
coordinate functions (cf. Fig. 2). We denote ϕ = [ξ i ]. If ψ : V ⊆ M → Rn ,
ψ = [ρi ] is another local coordinate system such that p ∈ V , then p hascoordinates [ξ i ] ∈ Rn with respect to ϕ and [ρi ] ∈ Rn with respect to ψ.
The latter may be obtained from the former by applying the coordinatetransformation or transition function ψ ◦ ϕ−1 : ϕ(U ∩ V ) ⊆ Rn → Rn .

Figure 2: Coordinate functions of a topological manifold.
10

This assumption excludes some pathological cases. It is not too strong for our purposes: any separable (i.e. that has a dense countable subset) metric space under the ordinary topology is Hausdorff second countable. This includes all the finite Hilbert spaces,
which are isomorphic to Rn .

25

By requiring these coordinate transformations to be smooth, we are led
to the notion of differentiable manifold.
4.1.2

Differentiable manifolds

Let U ⊆ Rm and V ⊆ Rn be open sets. A map f : U → V is said to besmooth or infinitely differentiable (denoted C ∞ ) if it has continuous partial
derivatives of all orders; the set of such maps is denoted C ∞ (U, V ). If
f ∈ C ∞ (U, V ) is bijective and f −1 ∈ C ∞ (V, U ), we say that f is a C ∞ diffeomorphism.
Let M be a n-dimensional topological manifold with atlas A. We saythat M is a differentiable manifold if for any pair of charts ϕ, ψ ∈ A withdomains respectively U ⊆ M and V ⊆ M , the transition function ψ ◦ ϕ−1 ,defined in ϕ(U ∩ V ), is a C ∞ -diffeomorphism with respect to its image.
The above notion of smoothness may be extended to maps between manifolds. If M, N are differentiable manifolds, we say that f : M → N is C ∞if for any pair of charts ϕ : U ⊆ M → Rm and ψ : V ⊆ N → Rn suchthat f (U ) ⊆ V we have ψ ◦ f ◦ ϕ−1 ∈ C ∞ (ϕ(U ), Rn ). Notice that the latteris simply the coordinated version of f . A C ∞ -diffeomorphism between two
manifolds M, N is a bijection f : M → N such that f ∈ C ∞ (M, N ) andf −1 ∈ C ∞ (N, M ).
In particular, a function f : M → R is C ∞ if f ◦ ϕ−1 ∈ C ∞ (ϕ(U ), R)
for any local chart ϕ. The set of C ∞ (M, R) functions is denoted F(M ). It
is straightforward that f is C ∞ (M, N ) if and only if g ◦ f ∈ F(M ) for allg ∈ F(N ).
4.1.3

Tangent spaces

When M is a n-dimensional surface in Rm parameterized as M = {x ∈ Rm :f (x) = 0}, where f : Rm → Rn is a differentiable map with component
functions f1 , . . . , fn , the tangent space at p ∈ M , denoted Tp M , is simply
the vector space orthogonal to span{∇x f1 |p , . . . , ∇x fn |p }. Tangent vectors
are elements of this space; they correspond to “local derivatives of functions
along a path”.
The definition of tangent space for a general manifold must be intrinsic,
and captures the intuitive notion of the tangent space Tp M as the vector
space obtained by “locally linearizing” M around p (see Fig. 3). The elements of Tp M , the tangent vectors, are defined as “equivalence classes ofcurves that have the same velocity vectors at p.” Let γ : I ⊆ R → M be
the parameterization of a curve such that γ(a) = p. If we take a smoothfunction f ∈ F(M ), we may take the composition f ◦γ : I → R and consider
its derivative, which is called the directional derivative of f along the curve
γ. Introducing local coordinates [ξ 1 , . . . , ξ n ] and defining γ i (t) ≡ ξ i (γ(t)) for26

t ∈ I, we may write this derivative as:n Xdγ i (t)∂fdf (γ(t)) ==dt∂ξ i γ(t) dt
i=1


∂f
dγ i (t)=.
∂ξ i γ(t) dt(4.1)

where in the last line we used the Einstein notation. The tangent vector γ̇(a)at p = γ(a) is defined as the operator that maps f ∈ F(M ) to its directional
derivative
p of the i-th coordinate
 at t = a. The tangent vectorat point∂f∂curve, ∂ξi: F(M ) → R maps f 7→ ∂ξi . Considering the set of allppcurves that pass through p, the set of all tangent vectors corresponding tothese curves forms a linear space, that we define to be the tangent space
1n
Tp M . Given system [ξ , . . . , ξ ] in a neighborhood of p, the  a coordinate

vectors

∂
∂ξ 1

p

,...,

∂
∂ξ n

p

form a basis for Tp M , which is called the natural

basis with respect to the coordinate system [ξ 1 , . . . , ξ n ].

Figure 3: Tangent space.

4.1.4

Submanifolds

Our first description of a tangent space considered a manifold as a surface
in Rn . Actually, we often represent a m-dimensional manifold M in an
ambient space as a submanifold of a n-dimensional manifold N , with n ≥ m.
Technically, we say that M is a submanifold of N if:• M is endowed with the induced topology of N ,• the embedding ι : M → N defined by ι(p) = p is C ∞ , and• for each p ∈ M and each coordinate systems [θj ] of M and [ξ i ] of N ,∂ξ i
has full rank.
the matrix ∂θjp27

An important property is that, if M is a submanifold of N , then for any
point p ∈ M , the tangent space Tp M is a linear subspace of Tp N . We next
see some examples (to be later used) of submanifolds of Euclidean spaces.
Example 4.1 (The n-sphere as submanifold of Rn+1 ) The n-sphere Sn
may be represented in the ambient space Rn+1 as
)
(
n+1
X
x2i = 1 .
(4.2)
Sn ≡ x ∈ Rn+1 :i=1A point p ∈ Sn may be represented in the Cartesian coordinate system [ξ i ]of Rn+1 as p ≡ (x1 , . . . , xn+1 ). The tangent space Tp Sn is a linear subspace  n+1∂
n+1
of theof Tp R
, and can be represented in the natural basis∂ξ ipembedding tangent space Tp Rn+1 as follows:
)
(
n+1
X
vi xi = 0 .
Tp Sn ≡ v ∈ Rn+1 :

i=1

(4.3)

i=1

This results from thefact that Tp Sn = (span{∇x f |p })⊥ , with f : Rn+1 → R
Pn+1
defined as f (x) = i=1 x2i − 1.

Example 4.2 (The open n-simplex as submanifold of Rn+1 ) Also then-dimensional open simplex Pn is a submanifold of Rn+1 and can be represented as
)
(
n+1
X
n
n+1
xi = 1 .
(4.4)
P ≡ x∈R: xi > 0,i=1

Analogously, Tp Pn can be represented in the natural basis of Tp Rn+1 as:
(
)
n+1
X
Tp Pn ≡ v ∈ Rn+1 :vi = 0 .
(4.5)
i=1

4.1.5

Tangent bundle, vector fields and tensor fields

The tangent bundle of M is the disjoint union of the tangent spaces of eachpoint in the manifold,
G
TM =
Tp M.
(4.6)
p∈M

Its position map is the surjective map π : T M → M that maps vp 7→ p forany vp ∈ Tp M , i.e., π −1 (p) = Tp M . A vector field is a map X : M → T M
that associates to each point p a tangent vector in Tp M , i.e., such thatπ ◦ X = IM .
28

From now on we assume that M has a global coordinate system, that
we denote by [ξ i ]. In this case we may define n vector
formed by the fields∂∂
natural basis, through the mappings ∂i ≡ ∂ξi : p 7→ ∂ξi , for i = 1, . . . , n.
p

The value of any vector field X at a point p may be written as a linear
combination Xp = Xpi ∂i with Xpi ∈ R. Doing this for all p ∈ M forms nfunctions X i : M → R that are the components of the vector field X withrespect to [ξ i ], so we may write X = X i ∂i . If each X i ∈ F(M ), we saythat X is a C ∞ -vector field. This definition does not depend on the choiceof the coordinate system: if we choose a different global coordinate system[ρj ], the same vector field is expressible as X = X̃ j ∂˜j , where ∂˜j ≡ ∂ρ∂ j , andit holds:∂ρjX̃ j = X i i .
(4.7)∂ξ
We denote by X (M ) the set of C ∞ -vector fields in M .
We now introduce the notion of tensor field. For each point p, let [Tp ]0r
and [Tp ]1r denote respectively the families of multilinear mappings of theform Tp M × . . . × Tp M → R and of the form Tp M × . . . × Tp M → Tp M . A
{z
}
{z
}
|
|
r timesr timesmap A : p 7→ Ap which associates at each point p a multilinear mapping
Ap ∈ [Tp ]qr is called a tensor field of type (q, r), for q = 0, 1, where r is called
the covariant degree and q the contravariant degree. If for any fixed r vector
fields X1 , . . . , Xr the mapping A(X1 , . . . , Xr ) is C ∞ , i.e. it is in F (resp. in
X ), we call A a C ∞ -tensor field. A (C ∞ -)vector field is a (C ∞ -)tensor fieldof type (1, 0). We will next introduce a C ∞ -tensor field of type (0, 2), theRiemannian metric.
4.1.6

Riemannian manifolds

Suppose that for each point p ∈ M , a local inner product is defined on
the tangent space Tp M , i.e., a real-valued function h, ip → R that satisfies
the axioms on Example 2.4. From the bilinearity of the inner product, wehave that the map g : p 7→ h, ip is a tensor field of type (0, 2). If it is inaddition a C ∞ -tensor field, we say that g is a Riemannian metric on M . A
manifold M endowed with a Riemannian metric g is called a Riemannian
manifold, and denoted (M, g). It is important to note that such a metric is
not naturally determined by the structure of M , i.e., it is possible to consider
an infinite number of Riemannian metrics on M . If we fix a coordinate
system [ξ i ], we may represent g by its component functions with respect to[ξ i ], namely gij = h∂i , ∂j i. From the bilinearity of the inner product, thesecomponent functions completely determine g, i.e., given any two tangent
vectors D, D′ ∈ Tp M written in terms of their coordinates as D = Di (∂i )pand D′ = D′i (∂i )p , their inner product is given by
D, D′ p = gij (p)Di D′j .
29

(4.8)

The matrix G(p) ≡ [gij (p)]1≤i,j≤n is obviously positive semidefinite for eachp ∈ M . If we choose a different coordinate system [ρk ] the new componentsg̃kl with respect to [ρk ] relate with gij via
 i  j
∂ξ
∂ξ
.
(4.9)
g̃kl = gijk∂ρ∂ρl
The Riemannian metric allows us to measure lengths and angles in the
manifold. The length kγk of a curve γ : [a, b] → M is defined as
Z bq
Z bgij γ̇ i γ̇ j dt
(4.10)
kγ̇k dt =
kγk =
a

a



d
where γ̇ i ≡ dt
ξ i ◦ γ . This allows defining the geodesic distance dg (x, y)
between two points in the manifold as

dg (x, y) =infγ∈Γ(x,y)kγk ,(4.11)

where Γ(x, y) denotes the set of piecewise differentiable curves connecting x
and y.
4.1.7

Tangent map, pull-back metric, and isometries

Consider now a diffeomorphism f : M → N between two diferentiable manifolds. In order to map velocity vectors of curves γ in M to velocity vectorsof curves f (γ) in N , we define the tangent map
f∗ : Tp M → Tf (p) N
v 7→ f∗ v(4.12)

with r 7→ (f∗ v) · r = v · (r ◦ f ) for all r ∈ F(N ). The coordinated version off∗ is simply the Jacobian matrix associated with the coordinated version off [Leb06]. Fig. 4 gives a geometric interpretation.

Figure 4: Tangent map.
Notice that a diffeomorphism as above, f : M → N , when (N, h) is a
Riemannian manifold, automatically endows M with a Riemannian structure, since the metric h in N induces a metric in f ∗ h in M , called the30pull-back metric, via the tangent map f∗ , as(f ∗ h)p : Tp M × Tp M → R(u, v) 7→ (f ∗ h)p (u, v)(4.13)

with (f ∗ h)p (u, v) = hf (p) (f∗ u, f∗ v). Intuitively, to calculate the inner product of two velocity vectors in Tp M we map them to velocity vectors in Tf (p) N
and let the metric in N do the job.
Two Riemannian manifolds (M, g) and (N, h) are said to be isometric
if there is a diffeomorphism f : M → N such that gp (u, v) = (f ∗ h)p (u, v)
for each p ∈ M , and u, v ∈ Tp M . In that case f is called an isometry.
Isometries preserve the geodesic distance function, i.e., it holds dg (x, y) =dh (f (x), f (y)) for all x, y ∈ M .

4.2

The geometry of probability models

We now give an important characterization of the geometry of the space of
probability distributions as an affine space, having the exponential families
as an affine subspace. For this, we follow [MR93]. Then we consider finite
dimensional statistical manifolds and show how the Fisher metric induces a
Riemannian atructure.
4.2.1

Affine spaces

An affine space is a set that becomes a vector space by selecting a point
to be the zero point. More formally, it is a set X together with a vector
space V , where each vector v ∈ V corresponds to a translation function
τv : X → X satisfying:
1. τv ◦ τu = τu+v for all u, v ∈ V ,2. For any x, y ∈ X there is a unique v ∈ V such that y = τv (x).
Let X be an affine space. If we declare a point x0 ∈ X as the origin,
there is a natural bijection f : X → V that identifies each point x ∈ Xwith the vector v ∈ V such that x = τv (x0 ); in particular f (x0 ) = 0, i.e.,the origin is identified with the zero vector. A simple example of affine
space is the Euclidean plane: once we choose an origin and fix a basis ofvectors each point receives a set of coordinates. Such a coordinate system iscalled an affine coordinate system. An important fact is that a set X witha collection of coordinate systems is an affine space if and only if any two
coordinate systems θ, ξ : X → R are affinely related, i.e., if and only if there
is a matrix A and a vector b such that θi (x) = Aij ξ j (x) + bi holds for eachx ∈ X. Another fundamental geometric property of affine spaces, as weshow below, is its flatness.

31

4.2.2

Positive measures as an affine space via the log-likelihood

We now show how positive measures on an event space X form an affine
space. To be able to work with measure densities, we restrain ourselves to aset M of measures that are absolutely continuous with respect to each other.
If we choose an origin ν for M , we may identify each measure µ ∈ M withits density with respect to ν, the Radon-Nikodym derivative p = dµdν , whichis unique up to equivalence within measure zero and satisfies p > 0 almost
everywhere. To turn M into an affine space, we have to define a translation
between measures (or, equivalently, densities). Pointwise multiplication by apositive function f would be a natural first candidate (in fact, any density p1
may be translated to p2 by a unique positive function f such that p2 = f p1 ),but this must be discarded since positive functions do not form a vector
space. This may be overcome by considering the vector space RX of the νmeasurable functions on X, i.e., the random variables, and let translation byf mean p 7→ exp(f )p, using the fact that exp(f ) > 0. In terms of measures,the translation function isτf : M → Mµ 7→ τf (µ) = exp(f )dµ,(4.14)and it is straightforward that this turns M into an affine space. If we choose
an origin ν for M , it becomes a vector space, where each measure µ ∈ M is
identified with the vector f ∈ RX that translates ν to µ; this corresponds
to the log-likelihood mapℓ : M → RXµ ≡ pdν 7→ ℓ(µ) = log p.

(4.15)

Obviously, ℓ(ν) = log 1 = 0, i.e., the base measure corresponds to the zerofunction.
Denote by M 1 = {µ ∈ M : µ(X) = 1} the space of all probability
measuresin M . M 1 cannot be seen as an affine subspace inside M , sinceR
X exp(f )pdν = 1 would require Ep (exp(f )) = 1 and the subset of RX for
which this holds is not a vector space. However, instead of regarding eachprobability measure as a point in M 1 , we may regard it as an equivalenceclass of finite measures in M up to scale (see Fig. 5). Two finite measures are
considered equivalent if they are rescalings of each other; in that case their
L1 -normalization reaches a unique probability measure. But “rescaling” inthe affine space M corresponds to translation by a constant function, i.e.,λp = exp(log λ)p = exp(C)p; hence, if a measure µ corresponds (via the loglikelihood) to a function f in RX , then the equivalence class of a measure up
to scale, say R++ ·µ, corresponds to that of a function up to the addition of aconstant, say f +R·1. The set of functions up to constants, i.e. the quotient
space RX /R · 1, is a vector space, hence it is straightforward that measures
up to scale define an affine space. The set of finite measures up to scale32

is a subset of this affine space; it corresponds to the set M 1 of probability
measures, and it is not affine.

Figure 5: Two ways of regarding a probability distribution: as a point in
M 1 , or as a “ray” in M .

4.2.3

Exponential families as an affine space

Unless the event space X is finite, the set of positive measures on X is
infinite-dimensional, and this poses theoretical problems in treating it asa statistical manifold. Instead, we often consider parametric families ofprobability distributions
S = {Pθ ∈ M+1 (X) : θ ∈ Θ},(4.16)

where the open set Θ ⊆ Rn is the space of parameters. We assume further
that for all x ∈ X the function θ 7→ p(x; θ), where p(.; θ) is the density ofPθ with respect to the base measure ν, is a C ∞ -diffeomorphism, and thatsupp(Pθ ) = X for all θ, which means that p(x, θ) > 0 for all θ ∈ Θ andx ∈ X.
We now show that a family of probability measures which forms a finitedimensional affine subspace of the set of measures up to scale corresponds toan exponential family. Indeed, let S be an r-dimensional affine subspace ofthe set of measures up to scale. Then S is spanned by linearly independent
non-constant random variables f1 , . . . , fr , and if ν is one of the measures(up to scale) taken as origin, any measure µ in S may be expressed asµ = exp(θ1 f1 + . . . + θr fr − K)dν

(4.17)

for some coordinates θ1 , . . . , θr ∈ R and where K ∈ R is a constant thatscales µ. The probability measures in this subspace correspond to thosewhich are finite, and may be obtained by properly setting K = K(θ) (called
the cumulant generating function) to turn µ into a probability measure:Z
exp(θ1 f1 + . . . + θr fr )dν.
(4.18)
K(θ) = log
X

33

The set Θ = {(θ1 , . . . , θr ) ≡ µ : µ(X) < ∞} corresponding to finite measures
up-to-scale (hence, probability measures) is a convex set of Rr , and suchfamilies of probability measures are called exponential families. A great
number of distributions widely used in statistics are exponential families: thenormal, gamma, Dirichlet, Bernoulli, multinomial, Poisson, and geometricare some examples.
Example 4.3 (Normal family) The normal family, usually parameterized as1−(x − µ)22exp
dP (x; µ, σ ) = √dx(4.19)
2σ 2
2πσwhere the sample space is R with the Lebesgue measure dx, and the parameters are µ ∈ R and σ > 0, is an exponential family. Indeed it can also be
parameterized asdP (x; θ1 , θ2 ) = exp(f1 (x)θ1 (x) + f2 (x)θ2 (x) − K(θ))dx(4.20)

with random variables f1 , f2 defined by f1 (x) = x2 , f2 (x) = x, parametersθ1 , θ2 given byµ1(4.21)
θ1 = − 2 and θ2 = 2
2σσcumulant generating function π  (θ2 )2
1
K(θ) = log − 1 −,(4.22)2
θ
4θ1

and the Lebesgue measure as base measure. The parameter θ = (θ1 , θ2 ) is
called the canonical parameter, and lies in the open subset of R2 defined byθ1 < 0. It follows that the normal family forms an affine subspace of thespace of measures up to scale. As an affine space, it holds that any othercanonical parameterization (η 1 , η 2 ) is affinely related with (θ1 , θ2 ).

Example 4.4 (Finite nonparametric spaces) Let X be a finite event
space with m events x1 , . . . , xm that occur respectively with probabilitiesξ 1 , . . . , ξ m . Notice that there are only P
m−1 degrees of freedom in the param1mieters ξ , . . . , ξ , since we must have m
i=1 ξ = 1. So, the family of m-sizednonparametric spaces may be parameterized by the open set Ξ ⊆ Rm−1
)
(
m−1
X
Ξ = (ξ 1 , . . . , ξ m−1 ) :ξ i < 1, ξ i > 0 for any i = 1, . . . , m ,i=1(4.23)
Pm−1 ii=1 ξ .
This is also an exponential family. It may be alternatively parameterizedwith canonical parameters θ = (θ1 , . . . , θm−1 ) as
!
m−1
X
i
dP (x; θ) = exp
fi (x)θ (x) − K(θ) dν(x)(4.24)
defining ξ m = 1 −

i=1

34

with random variables fi defined by
1, x = xi
fi (x) =0, x =
6 xi ,(4.25)

parameters θi given by
θi = log
cumulant generating function

ξi
ξi
Pm−1 i = log m ,ξ
1 − i=1 ξK(θ) = log 1 +

m−1
X

i

(4.26)!

exp(θ ) ,i=1

(4.27)and ν being the counting measure. The parameter space is Θ = Rm−1 .
Example 4.5 (Multinomial family) The multinomial family may be seen
as a generalization of the finite nonparametric space and yields a very similar expansion as an exponential family. Multinomials appear frequently incommunication theory. Suppose that a source emits symbols σ1 , . . . , σm ∈ Σwith emission probabilities ξ 1 , . . . , ξ m , and consider Bernoulli sequences ofn symbols. Let the random variables x1 , . . . , xm mean the number of times
each symbol occurs. This gives rise to a multinomial distribution,mdP (x1 , . . . , xm ; ξ 1 , . . . , ξ m ) =Yn!
(ξ i )xi .
x1 ! · . . . · xm !

(4.28)

i=1

Again, there are only m − 1 degrees of freedom, so, the family of m-sized
multinomials may be parameterized by the open set Ξ ⊆ Rm−1
)
(
m−1
X
i
i
1
m−1
ξ < 1, ξ > 0 for any i = 1, . . . , m ,Ξ = (ξ , . . . , ξ):
i=1(4.29)
Pm−1 i
ξ . Denote x = (x1 , . . . , xm ) and ξ = (ξ 1 , . . . , ξ m ).
defining ξ m = 1 − i=1
The log-likelihood of an element of this family is given byℓ(x; ξ) = log p(x; ξ) = C(x) +mXxi log ξ i ,(4.30)

i=1

P
where C(x) = log(n!) − m
i=1 log(xi !) is independent of ξ. The maximumblikelihood estimation ξ of the emission probabilities can be obtained by maximizing the previous expression (using a Lagrange multiplier to handle the
P i
bi
it is
restrictioni ξ = 1). As expected,  given by ξ = xi /n, for eachi = 1, . . . , n, and it is unbiased, i.e., E ξbi = E(xi /n) = ξ i .
35

The multinomial family is an exponential family; it may be alternatively
parameterized with canonical parameters θ = (θ1 , . . . , θm−1 ) as!
m−1XdP (x; θ) = exp
fi (x)θi (x) − K(θ) dν(x)(4.31)
i=1

with random variables fi defined by fi (x) = xi , parameters θi given by
θi = log
scale factor

ξiξi
Pm−1 i = log m ,ξ
1 − i=1 ξK(θ) = n log 1 +

m−1
X
i=1

and base measure ν with density

n!
x1 ! · . . . · xm !

i!

exp(θ ) ,(4.32)(4.33)(4.34)

with respect to the counting measure. The parameter space is Θ = Rm−1 .
4.2.4

The Fisher metric

We next endow statistical manifolds with an appropriate Riemannian metric.
This is proved to be, through Čencov’s theorem [MR93, AN01, Leb05], “theonly invariant metric under sufficient statistics transformations”.
Let ℓ(x; θ) = log p(x; θ) be the log-likelihood function of pθ . The wayℓ(x; θ) behaves under small perturbations of the parameters may be studied
via the score map s : X × Θ → Rn ,s(x; θ) = ∇θ ℓ(x; θ) = ∇θ log p(x; θ),(4.35)

i.e. [si (x; θ)] = ∂θ∂ i ℓ(x; θ) ≡ [∂i ℓ(x; θ)]. It is straightforward that the
expected value of the score is zero:Z∂iEθ [sθ ] =p(x; θ) i log p(x; θ)dν(x) =
∂θ
ZX
1
∂
p(x; θ)=p(x; θ)dν(x) =p(x; θ) ∂θiXZ∂p(x; θ)dν(x) =
=
∂θi X
∂
=
1 = 0.
(4.36)∂θi36

For each θ ∈ Θ, we define the Fisher information matrix G(θ) ≡ [gij (θ)]
as the covariance matrix of the scores,gij (θ) = Eθ [siθ sjθ ] = Eθ [∂i ℓθ ∂j ℓθ ] =



Z
∂
∂
log
p(x;
θ)
log
p(x;
θ)
dν(x) =
p(x; θ)=∂θi∂θjX= −Eθ [∂i ∂j ℓθ ],(4.37)
R
2
where the last equality may be obtained by adding 0 = ∂θ∂i ∂θj X p(x, θ)dν(x),interchanging the order of the integration and differentiation, and using therule for the derivative of products.
The Fisher information matrix G(θ) is positive semidefinite for all θ ∈ Θ,and positive definite if the scores {siθ } are linearly independent when seen asfunctions on X. If we further assume that each gij : Θ → R is C ∞ , we may
define the inner product of the natural basis of the coordinate system [θi ]by gij = h∂i , ∂j i, leading to a Riemannian metric g : pθ 7→ h, iθ in S whichis called the Fisher metric:hX, Y iθ =X i ∂i , Y j ∂j θ = X i Y j h∂i , ∂j iθ == X i Y j gij = X i Y j Eθ [(∂i · ℓ)(∂j · ℓ)],(4.38)

defined for any tangent vectors X, Y ∈ Tpθ S with coordinates X = X i ∂iand Y = Y i ∂i with respect to the natural basis. Another way to write theprevious equation is:
hX, Y iθ = Eθ [(X · ℓ)(Y · ℓ)](4.39)

which emphasizes the characterization of tangent vectors as derivative operators.
4.2.5

The embedding curvature

We now give some conditions for a parametric family of probability measures
S = {Pθ } to be an exponential family. Suppose that S is a submanifold of
the affine space of positive measures M . As seen above, if we choose an
origin ν for M , we may associate each measure to the loglikelihood of its
density, and M becomes a vector space. Moreover, for each point p ∈ S wemay identify the tangent space Tp S as an affine subspace of Tp M spannedby the score vectors∂ℓ(4.40)ℓi (p) ≡ i (p)∂θ
for i = 1, . . . , r (see [MR93] for more details). Then, a necessary and sufficient condition for S to be affine is that the partial derivatives of the scores(i.e. the second derivatives of the log-likelihood)ℓij (p) ≡∂2ℓ(p)∂θi ∂θj37(4.41)

lie in the span of the scores ℓ1 , . . . , ℓr and the constant random variables. If
we consider the family S̃ = {exp(λ)p : λ ∈ R, p ∈ S} obtainable from S byconsidering scalings of its measures, we may parametrize S̃ with the same
parameters as S, θ1 , . . . , θr , plus an extra parameter θr+1 = λ to account forthe scaling factors. Then the loglikelihoods of the measures in S̃ up-to-scale
are the same as the loglikelihoods of the distributions in S, up to the additionof a constant random variable, i.e., ℓ̃(exp(λ)p) = ℓ(p) + λ. Hence ℓ̃i = ℓi for
i = 1, . . . , r, and ℓ̃r+1 = 1. So the previous condition may be stated “S is anexponential family if and only if each ℓij (or ℓ˜ij ) lies in the span of the scoresℓ˜i .” If we introduce the Fisher metric g in S̃ to define the inner product in
Tp S̃, another way to state this result is that “S is an exponential family if
and only if the component of each ℓij normal to Tp S̃ vanishes;” this normalcomponent is denoted αij and called the second fundamental form [MR93]
or embedding curvature [AN01]; it is given by
αij = ℓij − g mn E(ℓij ℓm )ℓn − E(ℓij ),(4.42)

so we have that S is an exponential family if and only if αij = 0 for eachi, j = 1, . . . , r.

4.3

Finite non-parametric spaces

Let’s return to the scenario of the examples 4.4 and 4.5, where we assume
that the event space X = {x1 . . . , xn+1 } is a finite set. Then the set ofprobability distributions over X is the well-known probability simplex
Pn = {p : X → Rn+1 : p(xi ) ≡ θi ≥ 0,

n+1
Xθi = 1}.

(4.43)

i=1

This is not a manifold, but merely a manifold with corners [Leb05]. We
may however consider its interior Pn , whose points are the strictly positive
probability distributions over X, and that is called the open probability
simplex (cf. Example 4.2). We have seen above that Pn is actually a differentiable manifold. It can be characterized extrinsically as a submanifold of
Rn+1 through (4.4), or intrinsically through the parameter space expressedin (4.23). Such a probability model is called the finite non-parametric model.
It is often considered in nonparametric techniques of density estimation, forexample in the method of Parzen windows.
We now consider the extrinsic representation provided in Example 4.2.
The loglikelihood and its first and second derivatives are given byn+1
X

xi log θi ,(4.44)∂
xi
log p(x, θ) = i ,i∂θθ(4.45)ℓ(θ) = log p(x, θ) =i=1∂i ℓ(θ) =38

∂ij ℓ(θ) =∂2xilog p(x, θ) = − i 2 δij ,
i
j
∂θ ∂θ
(θ )

(4.46)and it follows that the Fisher information metric Jθ on Pn is given by:Jθ (u, v) = hu, viθ = −
=
=

n+1
X
X n+1

i j

u v Eθ

i=1 j=1

n+1
X

i=1
n+1
X
i=1

i i

u v Eθxi(θi )2∂2log p(x, θ) =∂θi ∂θj

=

ui v i,
θi(4.47)

where u, v ∈ Tp Pn are represented by their coordinates in the natural basisof the embedding tangent space Tp Rn+1 , and where we used the fact thatE(xi ) = θi .
Notice that this parameterization of the open simplex Pn represents also
the multinomial distribution, as shown in Example 4.5. The only differenceis that the latter includes an additive term in the loglikelihood that is constant in θ (cf. (4.30)), and hence it does not affect the subsequent derivatives
nor the expression for the Fisher metric. So, in what follows, we actually
may regard this manifold either as the space of all positive distributions in a
finite event space, or as the parametric space of the multinomial distribution.
Consider now the positive portion of the n-sphere of radius 2, whose
extrinsic representation as a submanifold of Rn+1 (cf. (4.2)) is
)
(
n+1
X
n+1
(θi )2 = 4, θi > 0 ,(4.48):
Sn,2++ = θ ∈ R
i=1

and the C ∞ map between manifolds, f : Pn → Sn,2++ , defined in terms of the
Euclidean coordinates of Rn+1 as:√√f (θ1 , . . . , θn+1 ) = (2 θ1 , . . . , 2 θn+1 ),(4.49)nwhose inverse is f −1 : Sn,2++ → P given by

f −1 (η 1 , . . . , η n+1 ) =(η 1 )2(η n+1 )2
,...,
4
4



.

(4.50)

Let p be an arbitrary point in Pn that is mapped to f (p) in Sn,2++ . The
n,2
n
−1
−1
tangent map of f
at f (p), f∗ : Tf (p) S++ → Tp P , may be obtained by
calculating the Jacobian matrix of the coordinated version of f −1 (cf. (4.12)),39

considering the two manifolds embedded in Rn+1 ; it yields:f∗−1 (u) = Ju =
=

n+1
X

n+1
X

uj

j=1

uj

j=1

∂fi−1
=
∂η j

ηi i
δ =
2 j


 1 1
un+1 η n+1
u η
,...,
.
=
2
2

(4.51)−1 ; it
We can now pullback the Fisher metric on Pn to Sn,2++ through fyields:hu, vif (p) = Jp (f∗−1 u, f∗−1 v) =!
 j j
 i iv ηuη,== J (θi )2
2 1≤i≤n+1
2
4
1≤i≤n+1
=
=

n+1
X

i=1
n+1
X

ui η i v i η i 4=
2 2 (θi )2
ui vi = δf (p) ,(4.52)

i=1

which is the Euclidean metric δ on Sn,2++ inherited from the embedding Eun+1
clidean space R. This makes f : (Pn , J ) → (Sn,2++ , δ) an isometry, i.e.,
Proposition 4.6 The probability simplex Pn endowed with the Fisher metric is isometric to the positive orthant of the sphere, Sn,2++ , endowed with theusual Euclidean metric.
This means that the geodesics in the Riemannian manifold (Pn , J ) corren,2nspond to arcs of great circles in Sn,2++ via the mapping f : P → S++ (seeFig. 6). Hence we are able to calculate the geodesic distance between two
finite nonparametric or multinomial distributions with probability vectorsθ = (θ1 , . . . , θn+1 ) and θ′ = ((θ′ )1 , . . . , (θ′ )n+1 ) via:!
n+1
Xq
dJ (θ, θ′ ) = dδ (f (θ), f (θ′ )) = 2 arccos
θi · (θ′ )i .
(4.53)
i=1

We will see in the next section how this geodesic distance induces generative kernels defined in the open simplex.

40

Figure 6: Illustration of Prop. 4.6.

5

Generative kernels

In this section we discuss an important class of kernels that have in common
the property of having been designed through some modeling on the data
generation; for this reason, they are termed “generative”. This is an informal designation that has more to do with the process by which the kernel isdevised than with the kernel function itself. In fact, we are going to see thatsome kernels derived in generative approaches reduce to the classic polynomial or Gaussian kernels that are typically addressed in “nongenerative”
approaches.
As a motivation, consider for example a binary classification problem,
where the data lies in a input space X and the label set is Y = {−1, +1}.
A pure generative approach starts by using the training data to estimate
the conditional densities p(x| − 1) and p(x| + 1), where x ∈ X, from which
it builds a classifier, for example using a “frequentist” point of view, via
the maximum likelihood, ŷML (x) = arg maxy∈Y p(x|y), or a “Bayesian” one,via the maximum a posteriori (MAP) ŷMAP (x) = arg maxy∈Y p(x|y)p(y),based on some prior belief (e.g. empirical) about the label distribution p(y).
By contrast, a kernel-based discriminative approach like a support vector
classifier starts by properly choosing a kernel, or equivalently a feature map
Φ : X → F , conceptually embeds the data in F and uses the training data
to find a linear discriminant in the feature space. Of course, the overall
performance will depend strongly on the choice of the kernel: this choiceshould reflect the prior knowledge about how the data was generated. Lately,
there have been many approaches to automatically learn the kernel fromdata (for instance, [LCB+ 04]). But even in those there is always a priorstep where at least a suitable family of kernels must be chosen.
Generative kernels try to combine the advantages of both generative anddiscriminative approaches by introducing generative models on data and use
them to devise a kernel. This can be done in many ways: (i) mapping data
to points in a probability space and devising a kernel between probability
distributions, (ii) considering a fixed probability distribution and study how
41does it “fit” each data point, (iii) assuming that there is some hidden modelthat governs the data generation and marginalizing with respect to thismodel, etc. We next present some generative kernels that make use of thesevarious possibilities.

5.1

Marginalization kernels

Marginalization kernels are described in some detail in [STC04], where some
applications to hidden Markov models (HMMs) and other graphical models
are devised. The idea is to consider a model class M , that we suppose to bediscrete (which is the typical scenario where marginalization kernels arise),albeit a generalization for the continuous case is straightforward. Assume
that there is a hidden model m ∈ M governing the generation of data, suchthat data are conditionally independent given the model, i.e., for x, y ∈ X,
p(x, y|m) = p(x|m)p(y|m). If we have a prior P (m) defined on the model
class, we can marginalize to obtain:Xp(x, y) =p(x|m)p(y|m)P (m)
(5.1)
m∈M

and this defines a (sort of naı̈ve Bayes) positive definite kernel on X, since
it is a convex combination of kernels of the form f (x) · f (y).
As an example, consider a finite alphabet Σ and let X = Σn (the set of
strings of characters in Σ with length n). If we assume that each string is generated by a HMM with hidden states h1 , . . . , hn ∈ H, we may consider M =H n , i.e., each model as a sequence of hidden states. The marginalizationis then carried over all possible sequences of hidden states,
and the Markov
Q
property implies that P (m) ≡ P (h1 , . . . , hn ) = P (h1 ) ni=2 P (hi |hi−1 ), sop(x, y) =n
X Yh∈H n i=1p(xi |hi )p(yi |hi )P (hi |hi−1 ),(5.2)

where by convention P (h1 |h0 ) ≡ P (h1 ). This reasoning may be generalized
for other graphical models, so we conclude that in those cases we can treat
the joint distribution p(x, y) as a positive definite kernel. This makes applicable a lot of discriminative learning techniques like the support vector
machines.
Notice that this kernel was devised from a generative perspective, constrasting to other kernels that are usually applied to discrete data, like thewhole class of convolution kernels described in [Hau99].

5.2

The Fisher kernel

The Fisher kernel was one of the earliest purposes of generative kernels, introduced in [JH98]. Consider a parametric family of µ-absolutely continuous
42

probability distributions on (X, M , µ),MΘ = {Pθ ∈ M+1 (X) : θ ∈ Θ},(5.3)

where Θ ⊆ Rn , which is supposed to be a differentiable manifold, and canbe given a Riemannian structure if we endow it with the Fisher metric J ,via the Fisher information matrix (recall (4.37))
G(θ) = [gij (θ)] = Eθ (sθ · sTθ ),(5.4)

where sθ = ∇θ ℓθ is the score vector, ℓθ = log pθ is the loglikelihood andθpθ = dPdµ is the density associated with the distribution Pθ .
Now fix a parameter setting θ ∈ Θ. This is the same as choosing a particular point Pθ in the statistical manifold. We may study how a data pointx ∈ X makes the loglikelihood function log pθ (x) vary in the neighborhoodof the parameter setting θ. Specifically, this can be done by computing thescore vector at θ,sθ (x) = ∇θ log pθ (x),(5.5)
which it is the gradient of the loglikelihood ℓθ (x) and so corresponds to its
steepest ascent direction at θ. Suppose now that we have two data points
x, y ∈ X whose kernel we wish to compute. We can calculate the two score
vectors sθ (x) and sθ (y) and compare them. Geometrically, these are the two
vectors in the tangent space TPθ MΘ that correspond to the steepest ascentdirections of the loglikelihood functions ℓθ (x) and ℓθ (y). However, MΘ is in
general a curved manifold, and so, as pointed out in [Ama98], the natural
basis of TPθ MΘ is not necessarily orthonormed. We should use instead of˜ θ , that depends on the local Riemannian metric∇θ the natural gradient ∇(in this case, given by the Fisher information) in the following way:˜ θ ℓθ = G(θ)−1 ∇θ ℓθ .
∇

(5.6)

˜ θ = ∇θ . Geometrically, theNotice that under the Euclidean metric, ∇natural gradient corresponds to the direction of steepest ascent along the
manifold, i.e. the direction that maximizes the loglikelihood function while
traversing the minimum distance in the manifold, being the distance givenby the Riemannian metric (cf. (4.11)). This is an intrinsic notion, i.e. it
does not depend on the chosen coordinate system. Next, to define a positive
kernel between x and y, we may consider the natural gradient mapping atθ,Φ : X → TPθ M Θ(5.7)
˜ θ ℓθ (x),x 7→ Φ(x) = ∇and, again, use the local inner product in TPθ MΘ given by Riemannian43metric. This yields the Fisher kernel :κ(x, y) = Jθ (Φ(x), Φ(y)) =˜ θ ℓθ (x))T G(θ)∇˜ θ ℓθ (y) == (∇= (∇θ ℓθ (x))T G(θ)−1 G(θ)G(θ)−1 ∇θ ℓθ (y) == (∇θ ℓθ (x))T G(θ)−1 ∇θ ℓθ (y) == (sθ (x))T G(θ)−1 sθ (y).

(5.8)

By construction, the Fisher kernel is independent of the choice of the coordinate system. Notice that the matrix G(θ) depends only on the parametersetting and not on the data points; however, albeit in particular cases it
admits a closed form expression, in general it is difficult to compute, andthis is a drawback for practical applications. It is immediate, however, that
we may define related kernels
κ(x, y) = (sθ (x))T Ksθ (y),(5.9)

where K is any positive definite matrix. They are still based in the natural
gradient, but unlike the actual Fisher kernel they depend on the parameterization of MΘ . A wide used version is the “practical Fisher kernel”, where
K is set to the identity matrix.
The choice of the parameter setting θ is a very important issue in thedesign of a Fisher kernel11 . For instance, typical points x ∈ X, i.e., points
with high likelihood ℓθ (x), will have a small norm κ(x, x) since their derivatives are small, while atypical points y ∈ X may have large derivatives andhence a high norm κ(y, y). This effect may be dangerous, since the kernel
between similar typical points may be lower than the kernel between very
different atypical points. This may be overcome by normalizing the kernel.
Applications of the Fisher kernel to HMMs are given in [STC04].

5.3

Probability product kernels

Although they have a “generative” inspiration, neither the marginalization
kernel or the Fisher kernel, described in the previous sections, are directly
defined in a probability space. In the case of the Fisher kernel, a particularprobability distribution is chosen and kept fixed. In the case of the marginalization kernels, the marginalization in (5.1) is performed making the hidden
model vary, but assigning at each time equal versions of the model to both x
and y. We now describe a different framework, where data points in X are
mapped to probability distributions in a parametric family MΘ as in (5.3),
and a “probability kernel” κM is devised in this space (or equivalently, inthe space of the corresponding densities).
11

Why not marginalizing over several values of θ, using a prior P (θ)?

44

So there are two separate problems: (i) choosing a map f : X → MΘ ,and (ii) devising a kernel in MΘ × MΘ . Let’s focus on the first problem, i.e.,
how to fit a density on an individual datum point? Notice that this is very
different from the usual density estimation problem, where we suppose thatmany data points are available. Although fitting a density to a single point
is not a very interesting approach for estimation purposes, here it is only anintermediate step to devise a kernel. It has the advantage over nongenerative
kernels that our choice of the parametric family MΘ is a good opportunity
to reflect our prior knowledge about the data generation. The most obvious
choice for the map f is the maximum likelihood estimation
x 7→ pθ̂(x) ,that leads toθ̂(x) ≡ θ̂ML (x) = arg max pθ (x)θ∈Θ(5.10)

κ(x, y) = κM pθ̂(x) , pθ̂(y) .

(5.11)

θ̂(x) ≡ θ̂MAP (x) = arg max pθ (x)π(θ).

(5.12)

If we consider a prior π(θ) on the parameter family, we may use instead the
maximum a posteriori estimateθ∈ΘAn alternative “Bayesian-like” strategy is considering the conditional density of the parameters on the datum,p(θ|x) =where Z(x) =posterior,R1pθ (x)π(θ),Z(x)(5.13)

Θ pθ (x)π(θ)dθ is a normalizing factor, and taking the true

x 7→ px (.) ≡
=
=

Z

ZΘ

pθ (.)p(θ|x)dθ =1pθ (x)π(θ)dθ =Z(x)ΘRΘRpθ (.)pθ (x)π(θ)dθ.
Θ pθ (x)π(θ)dθpθ (.)(5.14)

Yet another alternative (also “Bayesian”) to devise the kernel in X is toconsider the parameters as random variables with the conditional density(5.13) and take the posterior mean:ZκM (pθ , pξ )p(θ|x)p(ξ|y)dθdξ.
(5.15)
κ(x, y) =Θ×ΘThis and the subsequent sections explore several choices for the probability
kernels κM : MΘ × MΘ themselves.
45

The simplest way to define a probability kernel is to restrain ourselves2
to the set of densities that
R are L (X)-integrable and consider the standard
inner product hp, qi = X p(x)q(x)dµ(x). More generally, we may define afamily of probability product kernels [JKH04] parameterized by α > 0 asdMΘ ∩ L2α (X) defined bykernels in dµκα (p, q) = hpα , q α i =Zp(x)α q(x)α dµ(x).

(5.16)X

For α = 12 this is called the Bhattacharyya kernel, and for α = 1 thisis the expected likelihood kernel, since it becomes the expectation of one
distribution under the other. The Bhattacharyya kernel
Z pp
κ1/2 (p, q) =p(x) q(x)dµ(x)(5.17)
X

is known in the statistics literature as the “Bhattacharyya’s affinity” between
distributions, which relates to the Hellinger’s distance
Z p
2
p
1
H(p, q) =(5.18)
p(x) − q(x) dµ(x)2 X
qby H(p, q) = 2 − 2κ1/2 (p, q); there are also interesting relationships between the Hellinger’s distance and other divergence measures, as the KullbackLeibler or the Jensen-Shannon divergences (see [Top00] for more details). An
important property of the Bhattacharyya kernel is that the feature map associated to it maps densities to the unit sphere, i.e., κ1/2 |∆ = 1. As pointed
out in [JKH04], it turns out that the Bhattacharyya kernel can be computedin closed form for any exponential family (see (4.17)); in fact, ifpθ (x)dµ = exp(θT f (x) − K(θ))dν(5.19)pξ (x)dµ = exp(ξ T f (x) − K(ξ))dν(5.20)

andare two probability distributions belonging to an exponential family, we have
that
Z p
q
κ1/2 (pθ , pξ ) =pθ (x) pξ (x)dµ(x) =
X
!


Z
K(θ) + K(ξ)θ+ξ T
f (x) −
dν(x) =
exp
=
2
2
X


 
K(θ) + K(ξ)θ+ξ−,
(5.21)= exp K22
where the last step is due to (4.18).
46

Example 5.1 (Multivariate normal with variance σ 2 I.) For a multivariate normal N (µ, σ 2 I) we have


µ
1
θ=
,
(5.22),−
σ 2 2σ 2
f (x) = (x, kxk2 ),andK(θ) = log((2π)k/2 σ) +(5.23)kµk2.
2σ 2

So if pθ = N (µ1 , σ 2 I) and pξ = N (µ2 , σ 2 I), we have
 


θ+ξ
K(θ) + K(ξ)
κ1/2 (pθ , pξ ) = exp K
−
=
2
2
!
kµ1 + µ2 k2 kµ1 k2 + kµ2 k2
−
=
= exp
8σ 2
4σ 2
!
kµ1 − µ2 k2= exp −.
8σ 2

(5.24)(5.25)

If we use the maximum likelihood estimation to fit a density of this family toeach point x ∈ Rk , we get the map x 7→ N (x, σ 2 I), and the resulting kernel
κ in Rk obtained from the Bhattacharyya probability kernel is simply thekx−yk22
Gaussian kernel with variance 4σ , κ(x, y) = exp − 8σ2 . It is further
shown in [JKH04] that also the expected likelihood kernel κ1 yields, up to a
constant factor, a Gaussian kernel, with variance 2σ 2 instead.
Example 5.2 (Multinomial family.) Recall from (4.32)-(4.33) that them−1canonical parameters (θi )i=1
of the multinomial family relate to the symbolimprobabilities (β )i=1 via
θi = log

1−

ξi
Pm−1
i=1

βi

= log

βi
,
βm

(5.26)!

(5.27)and the cumulant generating function isK(θ) = n log 1 +

m−1
X
i=1

47

exp(θi ) ,Hence, the Bhattacharyya kernel between two multinomials pθ and pξ is K(θ) + K(ξ)θ+ξ−=
κ1/2 (pθ , pξ ) = exp K
2
2



n
Pm−1
i
i
1 + i=1
exp θ +ξ2
= n/2 
n/2 =
Pm−1
Pm−1
i
i
1 + i=1 exp(θ )1 + i=1 exp(ξ )!nm−1
X  β i γ i 1/2=
= (β m γ m )n/2 1 +
βmγm
i=1
!n
m
X

1/2
=
βiγi
,
(5.28)
i=1

i mwhere (β i )m
i=1 and (γ )i=1 are the respective symbol probabilities. If, again,
we use the MLE to fit densities on the points x and y of X = Σn , we getiiβ̂ML= xni and γ̂ML
= yni ; the Bhattacharyya kernel between the multinomials is thus equivalent to the homogeneousq n polynomial kernel of degree np xi  nyi
of square rooted symbol relative
between the vectors
n i=1 andni=1frequencies. When n is not constant, [JKH04] suggests summing over all its
possible values, leading to:κ(pθ , pξ ) =

∞
m
X
X

n=0

5.4

i=1



i i 1/2

βγ

!n

=

1−

m
X
i=1



i i 1/2

βγ

!−1

.

(5.29)

Kullback-Leibler kernel

The Kullback-Leibler kernel [MHV03] is one of the earliest generative kernels to be purposed that operate directly in the probability space. The
idea is similar to that of probability product kernels, i.e., fitting to eachdata point x ∈ X a µ-absolutely continuous probability distribution withddensity px ∈ dµ
M+1 (X), for example via the maximum likelihood estimation in a parametric family. The difference is that, instead of considering
Lp -inner products of densities, a kernel is devised that uses the more natural Kullback-Leibler divergence D(.||.) (cf. (2.17)). There are however someissues that need to be taken into account. Firstly, D(.||.) is not symmetric. This can be solved by using a symmetrized version D̃(.||.) defined byD̃(p||q) = D(p||q) + D(q||p). Secondly, even the symmetrized version fails
to be a metric, and no natural way seems to exist that allows devising a
positive kernel from it. The approach followed by [MHV03] is simply todefine the kernel
κ(x, y) = κp (px , py ) = exp(−αD̃(px ||py ) + β)48(5.30)

restricted to a finite set of data points in X, that by adjustment of theparameters α and β becomes positive definite.
For practical applications this is often harmless since many algorithms
work only with a kernel matrix, for example in unsupervised or transductive
learning. However, there are some “theoretical” problems when it is necessary to handle unseen data points, for example, in a inductive classifier.

5.5

The heat kernel

In [LL05, Leb05] a new class of kernels on statistical manifolds were introduced, called “information diffusion kernels”. This followed the idea of“diffusion kernel” that had already appeared applied to discrete spaces asgraphs [KL02]. These kernels have a strong physical interpretation that wesketch here. Again, we start by representing data as points in a statistical manifold (MΘ , J ), with MΘ as in (5.3) and J being the corresponding
Fisher metric. Then, a kernel is devised from a particular solution of theheat diffusion equation in the manifold. The idea is letting the value of thekernel κ(px , py ) express how information flows from px to py through the
manifold. Its construction is based on the notion of Laplacian in a Riemannian manifold (M, g).
We first define the (natural) gradient as a map that transforms smoothfunctions into vector fields
grad : F(M ) → X (M )(5.31)and satisfies gp (grad f |p , Xp ) = Xp (f ) for any f ∈ F(M ) and any p ∈ M .
Using local coordinates [θi ],X(grad f |p )i =g ij (p)∂j f (p),(5.32)jwhere g ij (p) denotes the (i, j)-entry of the matrix G−1 (p) and ∂j ≡ ∂θ∂ j .
Next, we define the divergence operator as a map that transforms vector
fields into smooth functions
div : X (M ) → F(M )(5.33)and is given in local coordinates byX p1
div Xp = p
det G(p)(Xp )i ,∂i
det G(p) i(5.34)

where det G(p) denotes the determinant of the Gram matrix G(p). Thesenotions of gradient and divergence operators generalize the usual notions
in Euclidean spaces, where the gradient may be interpreted as the steepest
ascent direction, and the divergence is a measure of outflow minus inflow. So
49

does the following notion of Laplacian operator in the Riemannian manifold(M, g),∆ : F(M ) → F(M ), ∆ = div ◦ grad,(5.35)
which can be used to model how heat diffuses through the manifold via theheat equation∂f− ∆f = 0(5.36)∂twith initial conditions f (x, 0) = f0 (x). Above f (x, t) denotes the flow atpoint x and time t; the initial conditions are the heat distribution at time
zero. The heat kernel κt (x, y) is defined as the solution to the heat equation
f (x, t) with initial condition given by Dirac’s delta function δy . By linearityof the heat equation, we have that the heat kernel generates the solution of
the heat equation with arbitrary initial conditions, according to:Zκt (x, y)f0 (y).
(5.37)f (x, t) =M

In the Euclidean case, (M, g) = (R, δ), the heat kernel reduces to the Gaus(x−y)21
sian kernel, κt (x, y) = √4πt exp − 4t
. In [Leb05] further properties of
the heat kernel are given. Unfortunately, for general manifolds there is no
closed form solution for the heat kernel; this is case, for example, for themultinomial family that is considered in [Leb05], where the problem of textclassification is addressed. The short time behaviour of the solutions canthough be studied via the parametrix expansion. This yields approximating
the heat kernel for the multinomial by
!!
n+1
Xq
n
1
κt (θ, θ′ ) = (4πt)− 2 exp − arccos2
θi · (θ′ )i(5.38)ti=1

which however (since it is a mere approximation) is not guaranteed to bepositive definite.

5.6

Negative geodesic distance kernel

In [ZCL05], a kernel that is very similar to (5.38) is proposed. Notice that it
is not clear if (5.38) is positive definite or not. From (4.53), we see that it has
the form of an exponentiated negative squared distance, where the distanceis the geodesic distance dJ on the positive orthant of the sphere. This
makes (5.38) a candidate, via Schoenberg’s theorem, to be positive definite
and even infinitely divisible. However, we have seen from Remark 3.24 that
not any squared distance yields a negative definite kernel. A necessary andsufficient condition for (5.38) to be positive definite is the ability to embed
the positive orthant of the sphere isometrically in some Hilbert space.
The kernel proposed in [ZCL05] derives from the “negative geodesic distance kernel”, which is proved to be conditionally positive definite. This is50

the same to say that the geodesic distance dJ itself (and not its square) is
negative definite. We refer to [ZCL05] for a proof of this fact. Hence, we can
exponentiate the negative geodesic distance and obtain a positive definite
kernel, namely
!!
n+1
Xq
′
θi · (θ′ )i,(5.39)κt (θ, θ ) = exp −t arccos
i=1

for t > 0. Notice the similarity with the heat kernel (5.38), the only difference being the squared arc-cosine.

5.7

Jensen-Shannon kernel

The Jensen-Shannon kernel or entropy kernel between measures was introduced in [CV05, CFV05]. It has been devised above (see (3.34)) when discussing semigroup kernels. There we saw that albeit not being a semigroup
kernel, it is semigroup-based, since it is the normalization of a semigroup
kernel. The proof that it is positive definite is a consequence of the negative
definiteness of the entropy function, and it puts in evidence a big amountof theoretic results on positive and negative kernels.
Unlike some other generative kernels that we have discussed, the JensenShannon kernel is defined between measure densities (with respect to somedominating measure ν), and so its domain is more general than those probability kernels that are defined only in the space of probability densities.
In [CV05, CFV05] the problem of defining a kernel between structured
objects (as images, text or sequences) that can be represented as “bags-ofcomponents” was addressed. Suppose first that the set S of basic components is finite (for example, in text objects, S may be the set of words of aclosed vocabulary). Assume that, given an object x ∈ X, we can calculate
the weight of each component s ∈ S on x, say ws (x). This could be, for example, the “number of times” that s appears in x. Then we can map x to amolecular measure µ ∈ Mol+ (S) (see Def. 2.9), by making each components ∈ S correspond to a Dirac measure centered in s, and give it a weightws (x), i.e.
Xµ=ws (x)εs .
(5.40)
s∈S

Using the counting measure as base measure, we may associate to eachmolecular measure its density, which is simply the function s 7→ ws (x). This
enables us to use the Jensen-Shannon kernel between the molecular measuresµ and µ′ associated respectively to the objects x and x′ . From the definitionof Jensen-Shannon divergence, this is done by considering the mixture of µ
and µ′ , which is a sort of “concatenation” of the components of x and x′ .
This emphasizes the “semigroup” formalism associated with this kernel.

51However, if S is an infinite set, this approach is not applicable in general. This happens because the counting measure is not guaranteed to be
σ-finite, and hence we cannot associate a density to each absolutely continuous measure. If we use other base measure instead (for example theLebesgue measure for S = Rn ) then molecular measures may not be absolutely continuous with respect to that base measure. In [CFV05] it issuggested to overcome this problem by smoothing the molecular measure µ
to a measure ϕ(µ) ∈ M+h (S) (see Sect. 2.3) via a smoothing kernel κ. Thisis done in a similar way as the Parzen window estimation procedure:
ϕ : Mol+ (S) → M+h (S) Pµ ≡ p dν 7→ ϕ(µ) = s∈supp µ p(s)κ(s, .) dν(5.41)For example, if S = Rn endowed with the Lebesgue measure, and κ is
the Gaussian kernel on S, then molecular measures on S are smoothed to
mixtures of Gaussians, and the resulting Jensen-Shannon kernel between
two objects x and y will compare the entropy of the Gaussian mixtures of
the components of x and y with the entropy of each individual Gaussian
mixture.

5.8

Multiresolution kernels

Multiresolution kernels were introduced in [CF05]. These kernels are adequate for structured data such as text, images, or sequences, that havesmaller components (resp. words, pixel intensity values, or characters). Typically these data are represented as “bags-of-components”; a more powerfulrepresentation considers a collection of nested bags (see Fig. 7) based on aprior knowledge on the data structure. This allows comparing two objects
both in detailed perspectives, stressing local matches between smaller bags,
or in a global one, using the entire bag.

Figure 7: Nested bags of components (extracted from [CF05]).

52

Suppose, as above, that each point x in the input space X may bed
M+1 (X), and let T be an arbitrary
mapped to a probability density px ∈ dν
set of conditioning events that can be directly observed in the object (unlike the hidden models considered in the marginalizing kernels). We may
decompose px asXX
px (.) =p(.|t)p(t) =µt ,(5.42)t∈Tt∈Tdwhere µt ≡ p(.|t)p(t) ∈ dνM+≤1 (X) is the density of a sub-probability measure on X (i.e. a measure whose total mass does not exceed 1). Objects canhence be represented as families of measures of M+≤1 (X) indexed by T , i.e.,
as elements µ ≡ (µt )t∈T inT
(5.43)MT (X) ≡ M+≤1 (X) .

For example, if the objects are images, each event t could correspond toa small region, and T could be a partition of the image in distinct regions.
Each image object would then be represented as a family of histograms, one
for each region. If, instead, the objects are strings, each event t could be a
nt -gram context, and T could be a context tree. Each string object could
then be represented as a family of histograms, one for each context, counting
the relative frequencies of the subsequent character.
To achieve the multiresolution kernel, we must first define a family(κt )t∈T of kernels that measure the object similarity with respect to each
event t,κt (µ, µ′ ) ≡ κ(µt , µ′t ),(5.44)

where κ is a predefined kernel. If the objects are “structured”, it seems reasonable to suppose that some events are similar while others are not. If two
events s and t are considered similar (for example two neighboring regions
in an image), we may consider a unique event {s, t} and a corresponding
kernel κ{s,t} (µ, µ′ ) ≡ κ(µs + µt , µ′s + µ′t ). More generally, if T0 ⊆ T is a setof similar events, we may defineXXκT0 (µ, µ′ ) ≡ κ µt ,µ′t  .
(5.45)t∈T0

t∈T0

Consider now a finite partition P of T , i.e., a set P = {T1 , . . . , Tn } of
disjoint subsets of T that cover T . We define the kernel κP induced by thepartition P asnY′
(5.46)
κP (µ, µ ) ≡κTi (µ, µ′ ).
i=1

Such a partition reflects a belief on how the events in T should be associated or dissociated to highlight component similarities or local dissimilarities. Instead of considering the set of all possible partitions of T , which53

would be computationally prohibitive, [CF05] suggests obtaining partitions
by assuming the existence of a prior hierarchical information on the eventsin T . This can be made through a “hierarchical” family H ≡ (Pd )D
d=0 ofpartitions
P0 = {T }, . . . , PD = {{t}t∈T }(5.47)
that has the property that any subset in a partition Pd is included in a
(unique by definition of partition) subset of the coarser partition Pd−1 (seeFig. 8). We assume further that this inclusion is strict. This means thateach set Ti ∈ Pd−1 is itself “partitioned” into more than one subset in Pd .
The multiresolution approach then considers partitions defined bySsets inthe different hierarchical levels of H. To do this, all the sets in D
d=0 Pdare taken into account to form the set PH of all the partitions that can bebuilt with them. The multiresolution kernel is then defined through a priormeasure π on PH as:Xκπ (µ, µ′ ) =π(P )κP (µ, µ′ ).
(5.48)P ∈PH

Tracing back to (5.44), we see that κπ is positive definite whenever thepredefined base kernel κ is. The latter may be any kernel that is definedin the space of subprobability measures, for example the Jensen-Shannon
kernel (3.34). In [CF05] a suggestion is given to generate the prior measure π through a branching process; further issues concerning the efficientcomputation of the multiresolution kernel are also provided in this reference.

Figure 8: A hierarchy of partitions, and an example of a multiresolution
partition (extracted from [CF05]).

5.9

Sequential document representations

We conclude this section by mentioning some recent work that concerns
document representation. There has been several approaches that extend
the traditional bag-of-words representation [SWY75], where each document
is represented as a sparse vector in a very large Euclidean space R|V | , with
V = {w1 , . . . , w|V | } being a vocabulary of words. A well-known approachfor text classification that uses the bag-of-words representation is latent semantic analysis. Basically, this method considers a document collection54C = {d1 , . . . , dn } represented as bags-of-words, and finds a linear subspace12of dimension k ≤ n where documents may be approximately represented bytheir projections. This can be done, for example, via a SVD decompositionof the words-by-documents matrix, and keeping only the k largest singularvalues.
More recent works [Gou99, HH00] generalize this geometrical idea to the
manifold of multinomial families: instead of finding a “linear subspace”, asin the Euclidean case, they learn a curved multinomial subfamily (i.e. asubmanifold of the multinomial family, which, unlike the latter, may be nolonger affine). Several approaches are considered: for example, if the probability simplex P|V |−1 is represented extrinsically in the ambient space R|V | wemay consider subfamilies formed by intersecting the simplex with an affine
subspace of R|V |13 ; alternatively, if we represent the Riemannian manifoldof the multinomial family endowed with the Fisher metric as the positive orthant of the |V |-sphere with the Euclidean metric, we may consider sphericalsubfamilies [Gou99] which are lower dimensional spheres embedded in the|V |-sphere. Otherwise, we may represent P|V |−1 intrinsically and consider
exponential subfamilies, i.e., subfamilies that are affine in the informationgeometric sense.
To illustrate this idea, [Gou99] splits a book (Machiavelli’s The Prince)in several text blocks, its numbered pages, considers each page as a pointin the multinomial simplex, learns a 2-dimensional subspace (an extreme
example of dimension reduction) and projects each page in this subspace.
The result is the representation of the book as a sequential path in R2 ,tracking the evolution of the subject matter of the book over the course of
its pages (see Fig. 9).
Inspired by this sort of document representations, more recent work
[Leb06] suggested a sequential representation of documents by simplicial
curves (i.e. curves in the probability simplex), that is denoted as the locallyweighted bag-of-words (lowbow) representation. According to this representation, a length-normalized document is a function x : [0, 1] × V → R+ suchthatX
x(t, wj ) = 1, for any t ∈ [0, 1].
(5.49)wj ∈V

The pure sequential representation of the n-length document (y1 , . . . , yn ) ∈V n may be written using the above formalism as
1, if wj = y⌈tn⌉x(t, wj ) = εwj (y⌈tn⌉ ) =(5.50)
0, if wj 6= y⌈tn⌉ ,12This procedure is known in machine learning as principal component analysis (PCA),
and may be generalized to find a nonlinear subspace by using kernel methods (kPCA)[STC04].
13
These are named “affine subfamilies” in [HH00] albeit this designation is misleading
since they are not affine in the information geometrical sense (they are not in general an
exponential family).

55

Figure 9: The 113 pages of The Prince projected onto a 2-dimensional space(extracted from [Gou99]).
where εy denotes the Dirac measure centered at y, and ⌈a⌉ denotes thesmallest integer greater than a. The global bag-of-words representation ofx corresponds to the point ρ(x) ∈ P|V −1| parameterized by:
Z 1jρ (x) =
x(t, wj )dt, j = 1, . . . , |V |.
(5.51)
0

The pure sequential representation in (5.50) may be smoothed via a function
fµ,σ : [0, 1] → R++ , where µ ∈ [0, 1] and σ ∈ R++ are respectively a location
and a scale parameter. An example of such a smoothing function is thetruncated Gaussian defined in [0, 1] and normalized. This allows defining
the lowbow representation at µ of the n-lenght document (y1 , . . . , yn ) ∈ V n
as the function x : [0, 1] × V → R+ such that:Z 1
εwj (y⌈tn⌉ )fµ,σ (t)dt,(5.52)
x(µ, wj ) =0which is proved [Leb06] to be a continuous and differentiable parameterized curve in the simplex. The scale of the smoothing kernel controls theamount of locality/globality in the document representation (see Fig. 10):when σ → ∞ the simplicial curve degenerates to a single point which is
the global bow representation (5.51); when σ → 0, the curve quickly moves
56

between the different corners of the simplex approaching the pure sequential representation (5.50). A distance between two documents may definedby integrating pointwise the geodesic distance between the corresponding
points in the simplex:
Z 1
dJ (x(µ, .), x′ (µ, .))dµ,(5.53)d(x, x′ ) =0with dJ defined in (4.53).

Figure 10: The lowbow representation of a document with |V | = 3, forseveral values of the scale parameter σ (extracted from [Leb06]).
Representing a document as a simplicial curve allows us to use geometric concepts to characterize properties of the document. For example, thetangent vector field along the curve describes sequential “topic trends” andtheir change; the curvature measures the amount of wigglyness or deviation from a geodesic path. This properties may be useful for tasks like text
segmentation or summarization.

6

Conclusions

Throughout this report, a survey was presented about generative techniques
to devise kernels on structured objects as strings, text or images. We studied57

several different perspectives, some of them making use of recent results on
information theory, as is the case with the Jensen-Shannon kernel, and others
inspired by the field of information geometry. We emphasized the theoreticalaspects and the geometrical insights that support either of these methods.
We opted to be as general as possible: for example when studying the theoryof positive and negative kernels, we did not choose the most direct path toprove that the Jensen-Shannon divergence is negative definite; instead someintermediate results were presented. Our belief is that while doing so, otherideas may come up.
Future work will concern making some experiments to compare severalof these kernels on practical applications, as well as devising other kernels
based on these insights, and best suited to particular tasks.

References[Ama98]Shun-Ichi Amari. Natural gradient works efficiently in learning.
Neural Computation, 10(2):251–276, 1998.

[AN01]

Shun-Ichi Amari and H. Nagaoka. Methods of Information Geometry (Translations of Mathematical Monographs). Oxford
University Press, 2001.

[BCR84]

C. Berg, J. P. R. Christensen, and P. Ressel. Harmonic Analysis on Semigroups. Springer, Berlin, 1984.

[CF05]

Marco Cuturi and Kenji Fukumizu. Multiresolution kernels,
2005.

[CFV05]

Marco Cuturi, Kenji Fukumizu, and Jean-Philippe Vert. Semigroup kernels on measures. J. Mach. Learn. Res., 6:1169–1198,
2005.

[CT91]

T. Cover and J. Thomas. Elements of Information Theory.
Wiley, 1991.

[CV05]

Marco Cuturi and Jean-Philippe Vert. Semigroup kernels on
finite sets. In Lawrence K. Saul, Yair Weiss, and Léon Bottou,
editors, Advances in Neural Information Processing Systems
17 (NIPS 2004), pages 329–336. MIT Press, Cambridge, MA,
2005.

[ES03]

Dominik M. Endres and Johannes E. Schindelin. A new metricfor probability distributions. IEEE Transactions on Information Theory, 49(7):1858–1860, 2003.

58

[GBGC+ 02] I. Grosse, P. Bernaola-Galvan, P. Carpena, R. RomanRoldan J. Oliver, and H. E. Stanley. Analysis of symbolic
sequences using the Jensen-Shannon divergence. Physical Review E, 65, 2002.
[Gou99]Alan Gous. Spherical subfamily models, November 10 1999.

[Hau99]

D. Haussler. Convolution kernels on discrete structures, 1999.

[HB04]

Matthias Hein and Olivier Bousquet. Hilbertian metrics andpositive definite kernels on probability measures, September 28
2004.

[HH00]Keith Hall and Thomas Hofmann. Learning curved multinomial subfamilies for natural language processing and information retrieval. In Proc. 17th International Conf. on Machine
Learning, pages 351–358. Morgan Kaufmann, San Francisco,CA, 2000.

[JH98]

T. Jaakkola and D. Haussler. Exploiting generative models in
discriminative classifiers. Technical report, Dept. of Computer
Science, Univ. of California, 1998.

[JKH04]

Tony Jebara, Risi Kondor, and Andrew Howard. Probability
product kernels. Journal of Machine Learning Research, 5:819–
844, 2004.

[KL02]

Risi Imre Kondor and John D. Lafferty. Diffusion kernels ongraphs and other discrete input spaces. In Claude Sammut and
Achim G. Hoffmann, editors, ICML, pages 315–322. Morgan
Kaufmann, 2002.

[Lan93]Serge Lang. Real and Functional Analysis. Springer-Verlag,
New York, NY, USA, 1993.

[LCB+ 04]

Gert R. G. Lanckriet, Nello Cristianini, Peter Bartlett, Laurent El Ghaoui, and Michael I. Jordan. Learning the kernel
matrix with semidefinite programming. Journal of Machine
Learning Research, 5:27–72, 2004.

[Leb05]

G. Lebanon. Riemannian Geometry and Statistical Machine
Learning. PhD thesis, CMU, January 2005.

[Leb06]

G. Lebanon. Sequential document representations and simplicial curves. In Proceedings of the 22nd Conference on Uncertainty in Artificial Intelligence, 2006.

59

[LL05]

John Lafferty and Guy Lebanon. Diffusion kernels on statisticalmanifolds. Journal of Machine Learning Research, 6:129–163,
2005.

[MHV03]

Pedro J. Moreno, Purdy Ho, and Nuno Vasconcelos. A
Kullback-Leibler divergence based kernel for SVM classificationin multimedia applications. In Sebastian Thrun, Lawrence K.
Saul, and Bernhard Schölkopf, editors, NIPS. MIT Press, 2003.

[MR93]

Michael Murray and John Rice. Differential Geometry andStatistics. Number 48 in Monographs on Statistics and Applied
Probability. Chapman and Hall, 1st edition, 1993.

[SS02]

B. Schölkopf and A. J. Smola. Learning with Kernels. The
MIT Press, Cambridge, MA, 2002.

[STC04]

John Shawe-Taylor and Nello Cristianini. Kernel Methods for
Pattern Analysis. CUP, jun 2004.

[SWY75]

G. Salton, A. Wong, and A. C. S. Yang. A vector space model
for automatic indexing. Communications of the ACM, 18:229–
237, 1975.

[Top00]Flemming Topsøe. Some inequalities for information divergenceand related measures of discrimination. IEEE Transactions on
Information Theory, 46(4):1602–1609, 2000.

[Top02]

Flemming Topsøe. Inequalities for the Jensen-Shannon divergence (draft version), 2002.

[Vap00]N. Vladimir Vapnik. The Nature of Statistical Learning Theory.
Springer-Verlag, New York., 2000.

[ZCL05]

Dell Zhang, Xi Chen, and Wee Sun Lee. Text classification withkernels on the multinomial manifold. In SIGIR ’05: Proceedings of the 28th annual international ACM SIGIR conference
on Research and development in information retrieval, pages
266–273, New York, NY, USA, 2005. ACM Press.

60