The Path Kernel
Andrea Baisero, Florian T. Pokorny, Danica Kragic and Carl Henrik Ek
KTH Royal Institute of Technology{baisero,fpokorny,danik,chek}@kth.se

Keywords:

Kernel methods, Sequential modelling

Abstract:

Kernel methods have been used very successfully to classify data in various application domains. Traditionally,kernels have been constructed mainly for vectorial data defined on a specific vector space. Much less work has
been addressing the development of kernel functions for non-vectorial data. In this paper, we present a newkernel for encoding sequential data. We present our results comparing the proposed kernel to the state of theart, showing a significant improvement in classification and a much improved robustness and interpretability.

1

INTRODUCTION

Machine learning methods have had an enormous
impact on a large range of fields such as computer
vision, robotics and computational biology. Thesemethods have allowed researchers to exploit evidence
from data to learn models in a principled manner. Oneof the most important developments has been that ofkernel methods (Cristianini and Shawe-Taylor, 2006)
which embed the input data in a potentially highdimensional vector space with the intention of achieving improved robustness of classification and regression techniques. The main benefit of kernel methods is that, rather than defining an explicit feature
space that has the desired properties, the embedding
is characterised implicitly through the choice of a kernel function which models the inner product in an induced space. This creates a very natural paradigm forrecovering the desired characteristics of a representation. Kernel functions based on a stationary distances(usually an L p − norm) have been particularly successful in this context (Buhmann and Martin, 2003).
However, for many application domains, the data does
not naturally lend itself to a finite dimensional vectorial representation. Symbolic sequences and graphs,
for example, pose a problem for such kernels.
For non-vectorial data, the techniques used forlearning and inference are generally much less developed. A desirable approach is hence to first place
the data in a vector space where the whole range ofpowerful machine learning algorithms can be applied.
Simple approaches such as the Bag-of-Words model,
which creates a vectorial representation based on occurrence counts of specific representative “words”,

have had a big impact on computer vision (Sivic andZisserman, 2009). These methods incorporate the factthat a distance in the observed space of image features
does not necessarily reflect a similarity. Another approach, where strings are transformed into a vectorial representation before a kernel method is applied,
has been the development of string kernels (Lodhi
et al., 2002; Saunders et al., 2002). Such kernels open
up a whole range of powerful techniques for nonvectorial data and have been been applied successfully to robotics (Luo et al., 2011), computer vision(Li and Zhu, 2006) and biology (Leslie and Kuang,
2004). Other related works are based on convolution
kernels (Haussler, 1999), which recover a vectorial
representation that respects the structure of a graph.
Another approach to define an inner product between
sequences is to search for a space where similarity
is reflected by “how well” sequences align (Watkins,
1999; Cuturi et al., 2007; Cuturi, 2010).
In this paper, we present a new kernel for representing sequences of symbols which extends and further develops the concept of sequence alignment. Our
kernel is based on a ground space which encodes similarities between the symbols in a sequence. We showthat our kernel is a significant improvement comparedto the state of the art both in terms of computational
complexity and in terms of its ability to represent thedata.
The paper is organised as follows: In Sec. 2, weoutline the problem scenario and provide a structure
for the remaining discussion. Sec. 3 introduces ourapproach and Sec. 4 provides the experimental results. Finally, we conclude with Sec. 5.

2

KERNELS AND SEQUENCES

M is a map γ : {1, . . . , |γ|} → Z>0 × Z>0 such that

Before we proceed with describing previous work forcreating kernel induced feature spaces for sequences,
we will clarify our notation and our notion of kernels. When discussing kernels in the context of machine learning, we have to distinguish between several uses of the word kernel. In this paper, a kernel denotes any symmetric function k : X × X → R,
where X is a non-empty set (Haasdonk and Burkhardt,
2007). A positive semi-definite (psd) kernel is a kernel k : X × X → R such that ∑ni, j ci c j k(xi , x j ) > 0 for
any {x1 , . . . , xn } ⊂ X, n ∈ N and c1 , . . . cn ∈ R. If theprevious inequality is strict when ci 6= 0 for at least
one i ∈ {1, . . . , n}, the kernel is called positive definite(pd). Further specialisations, such as negative definite(nd) kernels, exist and are of independent interest.

γ(1) = (1, 1),γ(i + 1) = γ(i) + δi ,for 1 6 i < |γ| , with δi ∈ S,
γ(|γ|) = (m, n).

While strong theoretical results on the existenceof embeddings corresponding to psd kernels exist(Berlinet and Thomas-Agnan, 2004, p.22), non-psd
kernel functions can still be useful in applications.
Examples of kernels that are known to be neither pd
nor psd, but which are still successfully used in classification include (Haasdonk, 2005). On another note,
there are also kernels which are conjectured to be psd,
and which have been shown to be psd in experiments,
but for which there currently is no proof for the corresponding positiveness (Bahlmann et al., 2002).
In this work, we consider finite sequences ofsymbols belonging to an alphabet set Σ, i.e. s =(s1 , s2 , . . . , s|s| ) denotes such a sequence, with si ∈ Σ,
and where |s| ∈ N0 denotes the length of the sequence.
We denote a subsequence (sa , . . . , sb ), for 1 6 a < b 6|s|, by sa:b . When the indices a or b are omitted, they
implicitly refer to 1 or |s| respectively. The inverse ofa sequence s is defined by inv (s)i = s|s|−(i−1) .
In this work, we assume that we are given a psd
kernel function kΣ : Σ × Σ → R describing the similarity between elements of the alphabet Σ and will referto kΣ as the ground kernel.
Given kΣ , we can now define the path matrix.
Definition 1 (Path Matrix). Given two finite sequences s,t with elements in an alphabet set Σ anda kernel kΣ : Σ × Σ → R, we define the path matrix
G(s,t) ∈ R|s|×|t| by [G(s,t)]i j = kΣ (si ,t j ).
def

def

def

We denote δ00 = (0, 0), δ10 = (1, 0), δ01 = (0, 1),
def

def

δ11 = (1, 1) and S = {δ10 , δ01 , δ11 }. S is called the setof admissible steps. A sequence of admissible steps
starting from (1, 1) defines the notion of a path:
Definition 2 (Path). A path over a m × n path-matrix

(1)
(2)
(3)

|γ| and δi denote the path’s length and ith step respectively. Furthermore, we adopt the notation γ(i) =(γX (i), γY (i)). A path defines stretches, or alignments, on the input sequences according to sγX =(sγX (1) , . . . , sγX (|γ|) ) and tγY = (tγY (1) , . . . ,tγY (|γ|) ).
We denote the set of all paths on a m × n matrixas Γ(m, n). Its cardinality is equal to the Delannoy
number Del(m, n).

2.1

Sequence similarity measures

A popular similarity measure between time-series is
Dynamic Time Warping (DTW) (Sakoe and Chiba,
1978; Gudmundsson et al., 2008), which determines
the distance between two sequences s and t as theminimal score obtained by all paths, i.e.
dDTW (s,t) = min Ds,t (γ),

(4)

γ∈Γ

where Ds,t represents the score of a path γ defined by|γ|

Ds,t (γ) = ∑ ϕ(sγX (i) ,tγY (i) ),

(5)

i=1

where ϕ is some given similarity measure. However,
DTW lacks a geometrical interpretation in the sensethat it does not necessarily respect the triangle inequality (Cuturi et al., 2007). Furthermore, this similarity measure is not likely to be robust as it only uses
information from the minimal cost alignment.
Taking the above into consideration, Cuturi suggests a kernel referred to as the Global Alignment
Kernel (Cuturi et al., 2007). Instead of considering
the minimum over all paths, the Global Alignment
Kernel combines all possible path scores. The kernel
makes use of an exponentiated soft-minimum of allscores, generating a more robust result which reflects
the contents of all possible paths:
kGA (s,t) = ∑ e−Ds,t (γ) .

(6)

γ∈Γ

By taking the ground kernel to be kΣ (α, β) = e−ϕ(α,β) ,kGA can be described using the path matrix as|γ|

kGA (s,t) = ∑ ∏ G(s,t)γ(i) .

(7)γ∈Γ i=1

The leading principle in this approach is hence a combination of kernels on the level of symbols over all

B A N A N AANNA

B A N A N A
A 0 1 0 1 0 1
N 0 0 1 0 1 0
N 0 0 1 0 1 0
A 0 1 0 1 0 1

B A N A N A
A
1
1
1
N
1
1
N
1
1
A
1
1
1

(b)
(a)
(c)
Figure 1: Illustration of the concept of paths and the contents of G(s,t) for s = “ANNA” and t = “BANANA”. On the left,
we illustrate a small number of paths which traverse G. The path kernel makes use of these, together with all the otherpaths, to collect data from the matrix and to extract a final score. In the center, we display the contents of G(s,t), assumingkΣ (α, β) = δαβ , i.e. Kroenecker’s delta function. On the right, we highlight the corresponding diagonals whose number,
length and position relate to the similarity between the subsequences of s and t.

paths along G(s,t). Cuturi shows that incorporating
all the elements of G(s,t) into the final results canvastly improve classification compared to using only
the minimal cost path. Furthermore, kGA is proven tokΣ
be psd under the condition that both kΣ and 1+kareΣ
psd (Cuturi et al., 2007), giving foundation to its geometrical interpretation.
However, Cuturi’s kernel makes use of products
between ground kernel evaluations along a path. Thisimplies that the score for a complete path will be verysmall if ϕ(si ,t j ) is sufficiently large, which leads tothe problem of diagonally dominant kernel matrices(Gudmundsson et al., 2008; Cuturi, 2010) from which
the global alignment kernel suffers. The issue is particularly troubling when occurring at positions near
the top-left or bottom-right corners of the path matrix because it will affect many of the paths. Furthermore, paths contribute with equal weight to thevalue of the kernel. To reduce this effect it is suggested in (Cuturi et al., 2007) to rescale the kernel
values and use its logarithm instead. We argue thatpaths which travel closest to the main diagonal of thepath matrix should be considered as more important
than others, as they minimise the distortion imposedon the input sequences, i.e. sγX and tγY are then mostsimilar to s and t. To rectify this and to include a preference towards diagonal paths, a generalisation called
the Triangular Global Alignment Kernel was developed, which considers only a subset of the paths (Cuturi, 2010). This generalisation imposes a crude preference for paths which do not drift far away from themain diagonal.
In this paper, we develop a different approachby introducing a weighting of the paths in Γ basedon the number of diagonal and off-diagonal steps
taken. We manipulate the weights to encode a preference towards consecutive diagonal steps while at thesame time accumulating information about all possible paths. Furthermore, by replacing the accumulation of symbol kernel responses along the path using

a summation rather than a product, the kernel’s evaluation reflects more gracefully the structure of the sequences and avoids abrupt changes in value.

3

THE PATH KERNELIn this section, we will describe our proposed kernel
which we will refer to as the path kernel.
Fig. 1 illustrates the contents of a path matrix in a
simplified example, showing the emergence of diagonal patterns when the two sequences are in good correspondence. Table 1 shows the resulting alignments
associated with the paths shown in Figure 1. We argue
that the values, the length and the location of these diagonals positively reflect the relation between the inputs and should thus be considered in the formulationof a good kernel. High values imply a good match on
the ground kernel level, while their length encodes theextent of the match. On the other hand, the position
relative to the main diagonal reflects how much the
input sequences had to be “stretched” in order for thematch to be encountered. We wish to have a feature
space where a smaller stretch implies a better correspondence between the sequences.
Let us now define a new kernel that incorporates
different weightings depending on the steps used totravel along a path.
Definition 3 (Path Kernel). For any sequences s,t, we
definek (s ,t ) Σ 1 1 +CHV kPAT H (s2: ,t) |s| > 1|t| > 1,
def
kPAT H (s,t) =+CHV kPAT H (s,t2: ) +CD kPAT H (s2: ,t2: )0otherwise,(8)
where CHV and CD represent weights assigned to vertical or horizontal steps and diagonal steps respectively. By enforcing the constraints CHV > 0 and
CD > CHV , we aim to increase the relative importanceof paths with many diagonal steps.

γ1
γ3

stretches
ANNAAAAAAANNNNAγ2
BBBBANANA
BANANA
ANNNNAAAAAAANNA
γ4
BANANABANANAAAA

Table 1: Stretches associated to the paths in Fig. 1a withthe underlined substrings denoting a repeated symbol. Note
that, even though γ2 and γ3 produce the same stretches, they
traverse the matrix differently and should thus be considered separately.

The symmetry of the kernel is easily verifiable.
On the other hand, positive definiteness remains tobe proven, although all our experimental results haveyielded psd kernel matrices in practice.

3.1

Efficient Computation

Kernel methods often require the computation of akernel function on a large dataset, where the number of kernel evaluations will grow quadratic with
the number of data-points. It is hence essential thatthe kernel evaluations themselves are efficiently computable.
Not only can the path kernel be evaluated using a Dynamic Programming algorithm which avoids
the expensive recursion in (8) and which achieves acomputational complexity comparable with DTW andkGA , but it can also be computed very efficiently using
the following alternative formulation:
kPAT H (s,t) = ∑ G(s,t)i j ωPAT H i j ,(9)[ωPAT H ]i j =

(10)

(a)

(b)
Figure 2: On the left, a precomputed 15 × 15 weightmatrix with CHV = .3 and CD = .34 is used to select a
10 × 12 weight matrix which can then be used to evaluate kPAT H (s,t) for input sizes |s| = 10 and |t| = 12. On
the right, the inversion invariant ω̃PAT H corresponding tok̃PAT H for the same input sizes is displayed.

We call a kernel satisfying k(s,t) =k(inv (s) , inv (t)) inversion invariant. If a kernelk does not naturally have this property, it can be
enforced by replacing k withk̃(s,t) =∑i+ j−2−2d d
CD (d, i − 1 − d, j − 1 − d)!.

CHV

d=0

The usefulness of (9) comes from the fact that thecontents of the weight matrix ωPAT H do not really depend on s,t since ωPAT H can in fact be pre-computed
up to an adequate size1 (see Figure 2). After this, theevaluation of the kernel for input of sizes m and n isachieved by simply selecting the sub-matrix ranging
from (1, 1) to (m, n); the remaining matrix multiplication can then be efficiently carried out. By taking advantage of this, one can evaluate the kernel at speeds
depending only on the speed of the evaluation of G
and the speed of a simple matrix multiplication (withthe initial overhead consisting of the pre-computationof ωPAT H ). The weight matrix can also be computed
through an efficient and very simple Dynamic Programming algorithm similar to the one which can beused to evaluate the kernel itself.
1 For any specific dataset, that would be the length of thelongest sequence.

(11)

The path kernel is not originally inversion invariant,but invariance can be enforced without the need for a
double computation of the kernel for each evaluation.
This is done by modifying the selected sub-matrix of
ωPAT H as follows: for any two inputs with lengths mand n, we replace the weight matrix ωPAT H by[ω̃PAT H ]i j =

ij

min (i, j)−1k(s,t) + k(inv (s) , inv (t)).
2

ωPAT H i j + ωPAT H m−i+1,n− j+1
,
2

(12)

and then proceed using this weight matrix.

3.2

Ground Kernel Choice

The path kernel is based on a ground kernel which,apart from being a psd function, is not constrained inany other way. However, we show in this paragraphthat an arbitrarily kΣ may lead to undesirable results.
Assume an alphabet and a ground kernel such thatα, β ∈ Σ, kΣ (α, α) = kΣ (β, β) = 1 and kΣ (α, β) = −1.
Given the input sequences s = (α, β, . . . , α, β) andt = (β, α, . . . , β, α), one may be inclined to say thats and t are very similar because each can be obtained from the other by cyclically shifting the symbols by one position. However, the contents of G(s,t)
show a collection of ones and negative ones organised in a chessboard-like disposition. This obviously
leads to heavy fluctuations during the computation ofkPAT H (s,t) and to potentially very small values. Furthermore, the issue is present even in the computationof kPAT H (s, s) and kPAT H (t,t) which is not desirable
under any circumstance.
This problem is however easily rectifiable by considering only ground kernels that yield non-negative
results on elements of Σ.

1

1

0.5

0.5

0.5

0.5

0

−0.5
−1
−1.5

0

20

40

60

t

80

100 120 140

0

20

40

60

1.5

t

0

−0.5
−1
−1.5

80 100 120 140

0

20

40

60

t

1.5

0

−0.5
−1
−1.5

80 100 120 140

1

1

0.5

0.5

0

0

20 40 60 80 100 120 140
t

0

−0.5
−1
−1.5

0

20

40

60

80 100 120 140

t

f(t)

1
0.5
f(t)

1

−0.5
−1
−1.5

0

−0.5
−1
−1.5

0

20

40

60

t

0

20 40 60 80 100 120 140

0

20

t

1.5

0.5
f(t)

f(t)

1.5

0

−0.5
−1
−1.5

1.5

f(t)

1.5

1

f(t)

1.5

1

f(t)

f(t)

1.5

80 100 120 140

0

−0.5
−1
−1.5

40

60

t

80 100 120 140

Figure 3: The figure above shows the eight different waveforms used for the classification for a noise level corresponding toσ{l,i,o} = 5. The golden curve depicts the base waveform without noise while the blue and red curves show the shortest andthe longest noisy example respectively. The black curves display the remaining examples in the database.

4

EXPERIMENTS

In this section, we present the results of experiments performed with the proposed kernel. In particular, we perform two separate quantitative experiments that, in addition to our qualitative results, shedsome light on the behaviour of the proposed method
in comparison to previous work. In the first experiment, we generate eight different classes of univariate sequences. Each class consists of a periodic
waveform namely ±sine, ±cosine, ±sawtooth and±square. From these, we generate noisy versions byperforming three different operations:• The length of the sequence is generated by sampling from a normal distribution N (100, σ2l ),rounding the result and rejecting non-positive
lengths.
• We obtain an input sequence as |s| equidistantnumbers spanning 2 periods of the wave; we then
add to each element an input noise which follows
a normal distribution N (0, σ2i ).
• We feed the noisy input sequence to the generating waveform and get an output sequence, towhich we add output noise which follows a normal distribution N (0, σ2o ),Figure 3 shows the sequences for the parametersetting σ{l,i,o} = 5. This corresponds to the setting
which we will use to present our main results.
We will compare our approach to kGA as well as
the non-psd kernel obtained by using the negative exponential of the DTW distance,
kDTW (s,t) = e−dDTW (s,t) .

(13)

The path kernel has two different sets of parameters:
the ground kernel and the weights associated withsteps in the path matrix. In our experiments, we use a
simple zero mean Gaussian kernel with standard deviation 0.1 as ground kernel. The step weights CHV
and CD are set to 0.3 and 0.34 respectively. We use
the same setting throughout the experiments. The behaviour of the kernel will change with the value ofthese parameters. A complete analysis of this is however beyond the scope of this paper. Here, we focus on
the general characteristics of our kernel which summarises all possible paths using step weights satisfying CHV < CD – implying a preference for diagonalpaths.
In order to get an understanding of the geometric configuration of the data that our kernel matrices
corresponds to, we project the three different kernels
onto their first two principal directions in Figure 4. It
is important to note that, as the DTW kernel has negative eigenvalues, it does not imply a geometricallyvalid configuration of datapoints in a feature space.
From Figure 4, we get a qualitative understanding of
how the induced feature spaces looks like. However,a representation is simply the means to an end andto be able to make a valuable assessment of its useability, we need to use it to achieve a task. We do sothrough two different experimental setups: The firstis meant to test the discriminative capabilities of therepresentation; the second evaluates how well the representation is suited for generalisation.
In order to test the discriminability of the feature
space generated by the path kernel, we perform a classification experiment using the same data as explained
above, and where the task is to predict the generating class of a waveform. We feed the kernel matrix
into an SVM classifier (Chang and Lin, 2001), usea 2-fold cross-validation, and report the average over

3 1e3

8 1e2
6
4
2
0
−2
−4
−6
−8
−6 −4 −2

2
1
0
−1
−2
−3
−5 −4 −3 −2 −1 0
2.5 1e3
2.0
1.5
1.0
0.5
0.0
−0.5
−1.0
−1.5
−2.0
−3 −2

−1

0

1

2

1

3

2

4

1e3

6 1e1
4
2
0
−2
−4
0

2

4

6

1e2

4
3
2
1
0
−1
−2
−3
−4
−5
−5 −4 −3 −2 −1 0

3

1e3

1

2

3

8

−6
−8 −6 −4 −2 0

2

4

6

4

2.5 1e1
2.0
1.5
1.0
0.5
0.0
−0.5
−1.0
−1.5
−2.0
−4 −3 −2 −1 0

1

2

3

1e2

1e2

8

1e1

4

1e1

Figure 4: The above figure displays the two dimensional principal subspace for the Global Alignment Kernel (left), Dynamic
Time Warping (middle) and the Path Kernel (right). The first row has a generating noise with σ{l,i,o} = 2, while, in the bottomrow, the noise is increased to σ{l,i,o} = 5, corresponding to the waveforms in Figure 3. The different waveforms are displayed
as follows: sine and -sine as a magenta circle and a green square, cosine and -cosine as a pink pentagon and a yellow star,
sawtooth and -sawtooth as a light-blue hexagon and an orange diamond and square and -square as a blue and a red triangle
respectively.

Performance %

100
90
80
70
60
50
40
30
20
10
0

log(kGA)

kPATH

0.51

2

3

5

Noise σ

6

7

8

9

Figure 5: We display the classification rate for predicting
the waveform type using an SVM classifier in the feature
space defined by the global alignment kernel (blue) andthe path kernel (green). The x-axis depicts the noise levelparametrized by σ{l,i,o} .

50 runs. Due to the negative eigenvalues, the classification fails for the DTW kernel. For this reason,
we only present results for the remaining two kernels.
In Figure 5, the results for the classification with increasing noise levels are shown. For moderate noiselevels (up to σ{l,i,o} = 5), the global alignment and thepath kernel are comparable in performance, while –at a higher noise level – the performance of the globalalignment rapidly deteriorates and at σ{l,i,o} = 9 its
performance is about chance, while the path kernel
still achieves a classification rate of over 80%.

The classification experiment shows that the pathkernel significantly outperformed the global alignment kernel when noise in the sequence became significant. Looking at the feature space, depicted in
Figure 4, we see that the path kernel encodes a feature space having more clearly defined clusters corresponding to the different waveforms. Additionally,
the clusters also have a simpler structure. This signifies that the path kernel should be better suited forgeneralisation purposes, where it is beneficial to havea large continuous region of support which gracefully
describes the variations in the data – rather than working in a space that barely separates the classes. We
now generate a new dataset consisting of 100 noisysine-waves (σ{l,i,o} = 5) shifted in phase between 0and π. The data is split uniformly into two halves andthe first is used for training and the second for testing. We want to evaluate how well the kernel is capable of generalising over the training data. To that end
we regress from the proportion of the training data
to the test data and evaluate how the prediction error
changes by altering this proportion. The prediction is
performed using simple least-square regression overthe kernel induced feature space. In Figure 6, theresults are shown using different sizes of the training data. As shown, the path kernel performs significantly better compared to the global alignment kernel and the results improve with the size of the train-50
log(kGA)40

RMS Error

kPATH

30
20
10
0

5

10 15 20 25 30 35 40 45 50# Training examples

Figure 6: The above figure depicts the RMS error when predicting the phase shift from a noisy sine waveform by a regression over the feature space induced by the kernels. The
red bars correspond to the global alignment kernel and thegreen bars to the path kernel. The y-axis shows the error
in percentage of phase, while the x-axis indicates the size ofthe training dataset.

ing dataset. Interestingly, the global alignment kernel produces very different results dependent on thesize of the training dataset indicating that it is severely
over-fitting the data.

5

CONCLUSIONSIn this paper, we have presented a novel kernel
for encoding sequences. Our kernel reflects and encodes all possible alignments between two sequencesby associating a cost to each. This cost encodes apreference towards specific paths. The kernel is applicable to any kind of symbolic or numerical data as
it requires only the existence of a kernel between symbols. We have presented both qualitative and quantitative experiments exemplifying the benefits of the pathkernel compared to competing methods. We showthat the proposed method significantly improves results both with respect to discrimination and generalisation especially in noisy scenarios. The computational cost associated with the kernel is considerably
lower than competing methods, making it applicable
to data-sets that could previously not be investigatedusing kernels.
Our experimental results indicate that the kernel
we propose is positive semi-definite. In future we
intend to investigate proving this property. Furthermore, in this paper, we have chosen a very simplistic dataset in order to evaluate our kernel. Given
our encouraging results, we are currently working on
applying our kernel to more challenging real-world
datasets.

REFERENCES
Bahlmann, C., Haasdonk, B., and Burkhardt, H. (2002).
Online handwriting recognition with support vector

machines - a kernel approach. In 8th International
Workshop on Frontiers in Handwriting Recognition.
Berlinet, A. and Thomas-Agnan, C. (2004). Reproducing
kernel Hilbert spaces in probability and.
Buhmann, M. D. and Martin, D. (2003). Radial basis functions: theory and implementations.
Chang, C. C. and Lin, C. J. (2001). LIBSVM: a library forsupport vector machines.
Cristianini, N. and Shawe-Taylor, J. (2006). An introduction
to support Vector Machines: and other kernel-basedlearning methods.
Cuturi, M. (2010). Fast Global Alignment Kernels. In International Conference on Machine Learning.
Cuturi, M., Vert, J.-P., Birkenes, O., and Matsui, T. (2007).
A Kernel for Time Series Based on Global Alighments. In IEEE International Conference on Acoustics, Speech and Signal Processing, pages 413–416.
Gudmundsson, S., Runarsson, T. P., and Sigurdsson, S.
(2008). Support vector machines and dynamic time
warping for time series. IEEE International Joint
Conference on Neural Networks, pages 2772–2776.
Haasdonk, B. (2005). Feature space interpretation of SVMs
with indefinite kernels. IEEE Transactions on PatternAnalysis and Machine Intelligence, 27(4):482–492.
Haasdonk, B. and Burkhardt, H. (2007). Invariant kernel
functions for pattern analysis and machine learning.
Machine learning, 68(1):35–61.
Haussler, D. (1999). Convolution kernels on discrete structures. Technical report.
Leslie, C. and Kuang, R. (2004). Fast String Kernels using
Inexact Matching for Protein Sequences. The Journalof Machine Learning Research, 5:1435–1455.
Li, M. and Zhu, Y. (2006). Image classification via LZ78
based string kernel: a comparative study. Advances inknowledge discovery and data mining.
Lodhi, H., Saunders, C., Shawe-Taylor, J., Cristianini, N.,
and Watkins, C. (2002). Text classification using
string kernels. The Journal of Machine Learning Research, 2:419–444.
Luo, G., Bergström, N., Ek, C. H., and Kragic, D. (2011).
Representing actions with Kernels. In IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 2028–2035.
Sakoe, H. and Chiba, S. (1978). Dynamic programmingalgorithm optimization for spoken word recognition.
IEEE Transactions on Acoustics, Speech and Signal
Processing, 26(1):43–49.
Saunders, C., Tschach, H., and Shawe-Taylor, J. (2002).
Syllables and other string kernel extensions. Proceedings of the Nineteenth International Conference on
Machine Learning (ICML’02).
Sivic, J. and Zisserman, A. (2009). Efficient Visual Searchof Videos Cast as Text Retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence,
31(4):591–606.
Watkins, C. (1999). Dynamic alignment kernels. In Advances in Neural Information Processing Systems.