Kernel-based Discriminative Learning Algorithms
for Labeling Sequences, Trees, and Graphs

Hisashi Kashimahkashima@jp.ibm.com
Yuta Tsuboi
yutat@jp.ibm.com
IBM Tokyo Research Laboratory, 1623-14 Shimotsuruma, Yamato-shi, 242-8502 Kanagawa, Japan

Abstract
We introduce a new perceptron-based discriminative learning algorithm for labelingstructured data such as sequences, trees, andgraphs. Since it is fully kernelized and uses
pointwise label prediction, large features, including arbitrary number of hidden variables,
can be incorporated with polynomial timecomplexity. This is in contrast to existing labelers that can handle only features of a small
number of hidden variables, such as Maximum Entropy Markov Models and Conditional Random Fields. We also introduce several kernel functions for labeling sequences,
trees, and graphs and efficient algorithms forthem.

1. Introduction
Sequence labeling is one of the important problems
widely seen in the areas of natural language processing(NLP), bioinformatics and Web data analysis. Labeling problems generalize supervised classification problems, since not only the label of one hidden variable,
but the labels of a set of hidden variables are predicted. Labeling problems for sequences have been
extensively studied for years. However, there has been
almost no significant work on labeling more general
structured data such as trees and graphs. In this paper, we consider kernel-based approaches for labelingproblems with general structured data.
Conventionally, in sequence labeling problems, generative models such as Hidden Markov Models (HMMs)
have been used. However, they tend to need a lot ofdata since they target the more difficult problems of estimating joint probabilities of observable variables andhidden variables. Also, they can not handle overlapping features naturally, since observable variables must
Appearing in Proceedings of the 21 st International Conference on Machine Learning, Banff, Canada, 2004. Copyright2004 by the authors.

be independent of each other given the labels of thehidden variables. Recently, conditional models such
as Maximum Entropy Markov Models (MEMMs) (McCallum et al., 2000) and Conditional Random Fields(CRFs) (Lafferty et al., 2001) are attracting considerable attention, since they are more suitable for the
purpose of predicting the labels of hidden variables
given the labels of observable variables. Recently,
Collins (2002) proposed the Hidden Markov (HM) Perceptron, a more efficient sequence labeling algorithm
based on perceptrons as an alternative to CRFs andMEMMs. SVM-based algorithms (Altun et al., 2003c)
and boosting-based algorithms (Altun et al., 2003a)
have also been proposed.
In some labeling problems, combinations of local features such as bi-grams are not sufficient for modelinglong-distance dependencies such as idioms in NLP, or
motifs in bioinformatics. However, in all of the methods proposed so far, there is a fundamental problem
that they can handle only local features considering
small numbers of hidden variables. Label prediction isbased on the Viterbi decoding using dynamic programming, which requires exponential time with respect
to the maximum number of hidden variables included
in one feature. Although HM-Perceptrons and HMSVMs have dual form representations, features must
be explicitly considered in label prediction. Of special
interest here, Kakade et al. (2002) proposed a pointwise log-loss objective function for CRFs and MEMMs
that aims to maximize the number of individually correct labels. The important point of their objectivefunction is that it does not need to predict the labels for the entire sequence all at once. In this paper,
inspired by the idea of a pointwise log-loss function,
we propose marginalized labeling perceptrons that solve
the label prediction problem by using the marginalizedfeature vectors. Marginalized labeling perceptrons realize point-wise label prediction, and are fully kernelized by using marginalized kernel functions (Tsudaet al., 2002) with long-distance dependencies among
hidden variables.
Also, in this paper, we propose several marginalized kernels used in the kernel marginalized labelingperceptron for labeling various structured data suchas sequences, trees, and graphs. Recently, kernelbased methods for classification of structured data
have been extensively studied1 , for instance, stringkernels (Lodhi et al., 2002; Leslie et al., 2002), tree
kernels (Collins & Duffy, 2002; Kashima & Koyanagi, 2002), and graph kernels (Kashima et al., 2003;
Gärtner et al., 2003). Most of them are based on feature vectors composed of the counts of the substructures such as subsequences, subtrees, or subgraphs,
to incorporate long-distance dependencies. As the dimensionality of feature vectors is typically very high(possibly infinite), they adopt efficient procedures suchas suffix trees, dynamic programming, or matrix computation to avoid explicit enumeration of the features. By extending these kernels, we propose several
marginalized kernels for labeling sequences, trees, andgraphs, and efficient algorithms for computing them.
Finally, we show some promising results for experiments on sequence labeling and tree labeling for realworld tasks which require structure information.
Our contributions in this paper are twofold: (i) A fullykernelized labeling learning algorithm that solves the
problem in label prediction for handling features of arbitrary size. (ii) Fast marginalized kernels for labelingsequences, trees and graphs.

Figure 1. (a) Graphical model representation of a labeledsequence under a first-order Markov assumption. Shadowed nodes indicate observable variables, and white nodes
indicate hidden variables. The sentence “the, man, saw,· · · , glasses.” is the label sequence x of the observable variables. The part of speech tag sequence “DT, NN, VBD,
. . ., NNS” is the label sequence y of the hidden variables.
(b) A pair of an observable variable and a hidden variable.
(c) A pair of two hidden variables.

2. Hidden Markov Perceptrons

Figure 2. Features for labeling sequences (of length 3). Bigram features are not sufficient for disambiguation of thelabel of ”marked”.

The labeling problem is defined to be the problemof learning a function that maps the observable variables x = (x1 , x2 , . . . , xT ) to the hidden variables y =(y1 , y2 , . . . , yT ), where each xt ∈ Σx and each yt ∈ Σy .
For instance, in part-of-speech tagging, xt represents
the t-th word, and yt represents the part-of-speech tagof the t-th word (Figure 1). The learner may exploit
a set of training examples E = (e(1) , e(2) , . . . , e(|E|) ),where e(i) = (x(i) , y (i) ) is the i-th example, and|x(i) | = |y (i) | = T (i) .
Collins (2002) introduced the HM-Perceptron, a discriminative learning algorithm for sequence labelingas an alternative to CRFs and MEMMs. It can betrained efficiently by processing the training examples
one by one. Its ability was shown to be comparable
to CRFs (Altun et al., 2003b). The key idea of the
HM-Perceptron is to interpret the mapping as a binary classification, i.e. Σx T × Σy T → {+1, −1}. Let F
be a set of features for vector representation of (x, y).
Let φf (x, y) be the number of times a feature f ∈ F
appears in (x, y), and Φ(x, y) be their vector form.
Given x, the HM-Perceptron outputs the prediction ŷ
according to the current weights of the features:ŷ=argmax
y∈Σy

=

T

X
f ∈F

y∈Σy T
1

An extensive survey is found in Gärtner (2003)

wnew = wold + Φ(x(i) , y (i) ) − Φ(x(i) , ŷ (i) ),(2)

when the prediction for e(i) is wrong, i.e. ŷ (i) 6= y (i) .
Equation (1) is also written in a dual form as follows
by using the weights of the examples α.
ŷ = argmax

|E|
X
X

y∈Σy T j=1ỹ∈Σy T­®
αj (ỹ) Φ(x(j) , ỹ), Φ(x, y) (3)Starting with α = 0, the updating rules are rewrittenas• αinew (y (i) ) = αiold (y (i) ) + 1• αinew (ŷ (i) ) = αiold (ŷ (i) ) − 1,

wf φf (x, y)­®
argmax w, Φ(x, y) ,where wf is the weight of a feature f , and w is the vector form of the weights. Under a first-order Markov
assumption, two types of features, such as pairs ofan observable variable and a hidden variable (Figure1(b)), and pairs of two hidden variables (Figure 1(c))
are used.
Starting at w = 0, the weights are updated by using(1)

when ŷ (i) 6= y (i) . (x(i) , ŷ (i) ) is called a pseudonegative example since it acts like an negative example.
Now, we discuss using features that consider long-distance dependencies in the HM-Perceptron. Sometimes, bi-gram features (Figure 1(b)(c)) are not sufficient for modeling long-distance dependencies such as
idioms in NLP, or motifs in bioinformatics. What if
we employ longer features such as in Figure 2? Let
us assume that we allow features of lengths up to d.
Let xtt21 be the subset of the observable variables fromposition t1 to position t2 of x, and y tt21 is defined accordingly. Taking into account that all features dependon at most d consecutive hidden variables, Φ(x, y) is
decomposed asΦ(x, y)=Φ(xd1 , y d1 ) − Φ(xd2 , y d2 )+Φ(xd+1, y d+1) − Φ(xd+1, y d+1
)
2
2
3
3
···

(4)

T −1
T −1
T −1
+Φ(xTT −1−d , y T −d ) − Φ(xT −d+1 , y T −d+1 )+Φ(xTT −d+1 , y TT −d+1 ).

Substituting Equation (4) into Equation (1), theargmax operation in Equation (1) is performed via thefollowing dynamic programming.
­®
max w, Φ(x, y) = max s(y1 , . . . , yd )yy1 ,...,yds(yt , . . . , yt+d−1 ) = max s(yt+1 , . . . , yt+d )
yt+d
­
®
t+d−1
t+d−1
t+d−1
+ w, Φ(xt, y t+d−1) − Φ(xt+1, y t+1)t­®
s(yT −d+1 , . . . , yT ) = w, Φ(xTT −d+1 , y TT −d+1 )However, the computation time in each step of the recursion grows exponentially with respect to the maximum feature length d. Even the dual form (3) still has
the same problem, because we have to evaluate all of
the features explicitly when predicting labels. This is aserious problem when we want to employ kernels with
arbitrarily long features (possibly of infinite length).
Also, CRFs have the same problem since they employ
dynamic programming procedures based on the same
decomposition in learning and prediction. In addition,even the decomposition (4) is not applicable to kernels
enumerating the occurrences of features when allowing
gaps (Lodhi et al., 2002), since a feature of length ofd can occur over an interval of length longer than d.
Collins (2000) avoids this problem by a reranking approach where a pre-trained labeler using local featuresgenerates an affordable number of candidates for y,and the candidates are reranked by using global features. However, the correct answer is not guaranteed
to be contained in the candidates based on the local
features.

label an entire sequence correctly. On the other hand,
Kakade et al. (2002) noticed that it suffices to maximize the number of individually correct labels in manylabeling tasks. They proposed to use the marginalized
Ps (y|x) over all possible assignments of labels for thehidden variables with the t-th hidden variable fixed asyˆt ∈ Σy .
X(i)

Pp (yt = yt |x(i) ) =Ps (y (i) |x(i) )(i)y:yt =yt

P P
The pointwise objective functionit log Pp (yt =(i) (i)yt |x ) is shown to be comparable to the original
sequential log-loss function (Altun et al., 2003b). The
important point is that label prediction is performed
in a pointwise manner since Pp depends only on yt .
We combine this idea with perceptron-based labelers.
We propose a marginalized labeling perceptron defined
as follows.
X­®
ŷt = argmax
P (y|x) w, Φ(x, y) . (5)ỹt ∈Σyy:yt =ỹt

Note that the pointwise label prediction works since
the argmax operation depends only on ỹt . The mainidea is that, when yt is predicted, the original output hw, Φ(x, y)i is marginalized over all possible assignments of labels for the hidden variables with thet-th hidden variable fixed as yˆt . P (y|x) is someprior distribution over hidden variables that might
be pre-trained probabilistic models such as MEMMs
or
P CRFs, or might be designed manually. Since
y:yt =ỹt P (y|x)Φ(x, y) can be considered as a newfeature vector, the weight vector w is updated byXX
P (y|x)Φ(x, y),(6)P (y|x)Φ(x, y) −wnew= wold +
(i)

(i)

y:yt =ŷt

y:yt =yt

when the prediction for the t-th position of e(i) is(i)(i)
wrong, i.e. ŷt 6= yt .
Next, we derive a dual form of the marginalized labeling perceptron, and obtain a fully-kernelized labeler.
Let φf (x, y; t) be the number of times a feature f
appears in (x, y) with including the t-th position of(x, y), and Φf (x, y; t) be the vector form. First, werewrite the primal form (5) as follows by adding terms
that do not depend on ỹt .
X­®
ŷt = argmax
P (y|x) w, Φ(x, y)ỹt ∈Σy

3. Marginalized Labeling Perceptrons+

We now propose a new kernel-based labeler thatsolves the problems of the previous section. Usually, in MEMMs and CRFs, model Ps (y|x) istrainedby maximizing the sum of the log-likelihood
P(i) (i)log
Ps (y |x ). This objective function aims toi−X

y:yt =ỹt

X­®
P (y|x) w, Φ(x, y; t)ỹt ∈Σy y:yt =ỹtXy∈Σy T= argmaxỹt ∈Σy­®
P (y|x) w, Φ(x, y)Xy:yt =ỹt­®
P (y|x) w, Φ(x, y; t) . (7)// Initialization¸ := 0// Training
for round = 1, . . . , max round,for i = 1, . . . , |E|,// kernel computation
for j = 1, . . . , |E|,for t = 1, . . . , T (i) , and τ = 1, . . . , T (j) ,for y̆τ ∈ Σy , and ỹτ ∈ Σy ,compute K(x(j) , x(i) , τ, t, y̆τ , ỹt )end forend forend for// prediction & update
for t = 1, . . . , T (i) ,(i)predict ŷt by using Equation (9)(i)(i)
if ŷt 6= yt ,(i)(i)αit (yt ) := αit (yt ) + 1(i)(i)αit (ŷt ) := αit (ŷt ) − 1
end ifend forend forend forFigure 3. Kernel Marginalized Labeling Perceptron

kernels for structured data such as sequences, trees,and graphs have been studied actively (Gärtner, 2003).
We extend these kernels for labeling problems. In all
kernels, for the sake of simplicity, we suppose that theprior P (y|x) can be decomposed as
P (y|x) =TYP (yt |xt ).

t=1

However, the following discussion can be generalized
to exploit more general models like CRFs. In the remainder of this section, we use K(τ, t, y̆τ , ỹt ) to refer
the kernel function given i and j. The important pointin computing our kernels is that all features can be constructed by combining smaller features. For instance,in Figure 4, suppose that the feature (b) appears with
its rightmost position at t, and the feature (c) appears with its leftmost position at t. Then, the feature (a), the combination of the two features, appears
with its second variable at t. All the marginalized kernels that we propose in this paper are decomposed into
the upstream kernels KU (τ, t), the downstream kernels
KD (τ, t), and the pointwise kernels KP (τ, t, y̆τ , ỹt ) as
follows.

K(τ, t, y̆τ , ỹt ) = KU (τ, t) · KP (τ, t, y̆τ , ỹt ) · KD (τ, t)
X X
(j)
(i)
The update rule is then rewritten as
KU (τ, t) =P (y U (τ )|xU (τ ))P (y 0U (t)|xU (t))
XXy U (τ ) y 0U (t)P (y|x)Φ(x, y; t).
P (y|x)Φ(x, y; t) −wnew = wold +
­
®
(j)
(i)
(i)
(i)
· Φ(xU (τ ), y U (τ ); τ ), Φ(xU (t), y 0U (t); t)(11)
y:yt =ŷt
y:yt =yt
X X
(j)
(i)
KD (τ, t) =P (y D (τ )|xD (τ ))P (y 0D (t)|xD (t))
By introducing example weights α, w is rewritten as
0
a linear combination,y D (τ ) y D (t)
­
®
(j)
(i)
(j)
|E| T
· Φ(xD (τ ), y D (τ ); τ ), Φ(xD (t), y 0D (t); t)
(12)
X
X X
X
w=
αjτ (y̆τ )P (y|x)Φ(x(j) , y; τ ). (8)j=1 τ =1 y̆τ ∈Σyy:yτ =y̆τ

KP (τ, t, y̆τ , ỹt ) =

®
(i)
(i) ­
(j)
(j)
Finally, substituting Equation (8) into Equation (7),P (y̆τ |xτ )P (ỹt |xt ) Φ(xτ , y̆τ ; τ ), Φ(xt , ỹt ; t)
we obtain the kernel marginalized labeling perceptron, ¡ P P
®¢2
(i)
(i) ­
(j)
(j)
P (y̆τ |xτ )P (ỹt |xt ) Φ(xτ , y̆τ ; τ ), Φ(xt , ỹt ; t)
(j)
|E| T
y̆τ ỹtX
X X
ŷt = argmax
αjτ (y̆τ )K(x(j) , x, τ, t, y̆τ , ỹt ), (9)(13)
ỹt ∈Σy j=1 τ =1y̆τ ∈Σywhere y U (τ ) is the set of the hidden variables lying
upstream of τ , y D (τ ) is the set of the hidden variables(j)
K(x , x, τ, t, y̆τ , ỹt ) =(10) lying downstream of τ , and y U (τ )∩y D (τ ) = {yτ }. The
X
X­® denominator of KP (τ, t, y̆τ , ỹt ) cancels the overlap of
P (y|x(j) )P (y 0 |x) Φ(x(j) , y; τ ), Φ(x, y 0 ; t) KU (τ, t) and KD (τ, t). Although explicit computation
y:yτ =y̆τ y 0 :yt0 =ỹtof the marginalization in KU and KD is prohibitive,
we can efficiently compute them by using dynamic prois called the marginalized kernel since the kernel isgramming in many cases. The major advantage of themarginalized over all possible assignments of labels fordecomposition is that, given the i-th example and thehidden variables with fixed labels at τ and t. The alj-th examples, marginalized kernels for all possible valgorithm is described in Figure 3.
ues of (τ, t, y̆τ , ỹt ) can be computed at the same time.
where

4. Kernel Computation
In this section, we propose several instances of themarginalized kernel (10) for labeling sequences, ordered trees, and directed acyclic graphs. Recently,

4.1. Sequence Labeling
Now we introduce kernels for sequence labeling. To
consider the long-distance dependencies in sequences,

4.2. Tree Labeling

Figure 4. Combining upstream features and downstream
features to make larger features. Appearance of the feature (a) with its second variable at t is guaranteed by theappearances of the feature (b) with its rightmost position
at t and the feature (c) with its leftmost position at t.

we define each feature as a consecutive pair of a hidden
variable and an observable variable of arbitrary length,
as in Figure 2. Since the lengths of the features are not
restricted, and features of various lengths are mixed,
we vary the weight φf according to the length of thefeature f by using the parameter c > 0. If the lengthof the feature is d, and if we observe the feature N
times in (x, y), φf (x, y) is defined as N · cd .
KU (τ, t) for labeling sequences is the kernel that considers only the appearances of features with their rightmost positions at τ and t, and which is marginalized
over all possible assignments for y U (τ ) and y U (t).
Similarly, KD (τ, t) is the kernel that considers only
the appearances of features with their leftmost positions at τ and t, and which is marginalized over all
possible assignments for y D (τ ) and y D (t).
The algorithm consists of two dynamic programming
loops, one for KU , and the other for KD , just like theforward-backward algorithm.
(i)

KU (τ, t) = c2 k(x(j)τ , xt )(KU (τ − 1, t − 1) + 1) (14)(i)

KD (τ, t) = c2 k(x(j)τ , xt )(KD (τ + 1, t + 1) + 1), (15)
where
(i)

k(x(j)
τ , xt ) =

X

X

(i)

P (y̆τ |x(j)τ )P (ỹt |xt )y̆τ ∈Σy ỹt ∈Σy(i)·ky (y̆τ , ỹt )kx (x(j)τ , xt )Note that KU (τ, 0) = KU (0, t) = KD (τ, |T (i) | + 1) =KD (|T (j) | + 1, t) = 0. KP is computed as follows.
KP (τ, t, y̆τ , ỹt )
(j)

(i)

(j)

(i)

c2 P (y̆τ |xτ )P (ỹt |xt )ky (y̆τ , ỹt )kx (xτ , xt ), (16)¡(j)(i) ¢2c2 k(xτ , xt )=where kx and ky are functions that return 1 when thearguments are identical, and return 0 elsewhere. However, we can replace them with kernels between the twovariables. Apparently, the time complexity of computing the kernels is O(T (i) T (j) ).22

Gappy matching as in Lodhi et al. (2002) is allowed
by introducing a penalty parameter 0 ≤ λ ≤ 1. An appear-

The kernel for labeling ordered trees (Figure 5) isbased on the labeled ordered tree kernel (Kashima &Koyanagi, 2002). We allow arbitrary tree-structured
features such as in Figure 5. By using the mixing
parameter c as in the sequence labeling, φf (x, y) isdefined to be N · cd where N is the number of times
the feature f appears as subgraphs in (x, y), and d isthe size of f . KU (τ, t) for labeling trees is the kernelthat considers only the appearances of features with
their leaf positions at τ and t, and that is marginalized over all possible assignments for y U (τ ) and y U (t).
Similarly, KD (τ, t) is the kernel that considers only
appearances of features with their root positions at τand t, and that is marginalized over all possible assignments for y D (τ ) and y D (t).
The algorithm consists of two dynamic programming
loops, one for KU , and the other for KD , just as in
the inside-outside algorithm. Let ch(τ, υ) be the index
of the υ-th child node of the τ -th node, pa(τ ) be theindex of the parent node of the τ -th node, #ch(τ ) be
the number of the child nodes of the τ -th node, andchID(τ ) be the index that means the τ -th node is thechID(τ )-th child of its parent node.
Similar to the recursive computation of the labeled ordered tree kernel (Kashima & Koyanagi, 2002), KD
is computed by dynamic programming in a post-order
traversal by using(i)

KD (τ, t) = c2 k(x(j)τ , xt )SF (τ, t, #ch(τ ), #ch(t)),
where SF is also defined recursively as follows,
SF (τ, t, υ, u) = KD (ch(τ, υ), ch(t, u))SF (τ, t, υ − 1, u − 1)
+SF (τ, t, υ − 1, u) + SF (τ, t, υ, u − 1)
−SF (τ, t, υ − 1, u − 1),
where SF (τ, t, 0, u) = SF (τ, t, υ, 0) = 1. Intuitively,
SF (τ, t, υ, u) is the sum of the contributions of all
the way of matching between the nodes indexed fromch(τ, 1) to ch(τ, υ) and the nodes indexed from ch(t, 1)
to ch(t, u).
At the same time, for the sake of the computation of
KU , we also define SB (τ, t, υ, u), the sum of the contributions of all the way of matching between the nodes
indexed from ch(τ, υ) to ch(τ, #ch(τ )) and the nodes
indexed from ch(t, u) to ch(t, #ch(t)), asSB (τ, t, υ, u) = KD (ch(τ, υ), ch(t, u))SB (τ, t, υ + 1, u + 1)
+SB (τ, t, υ + 1, u) + SB (τ, t, υ, u + 1)
−SB (τ, t, υ + 1, u + 1),
ance of a feature is counted as λg if g gaps are inserted.
The recursive equation (14) is modified by using the accumulated upstream kernel SF as follows.
KU (τ, t)
SU (τ, t)

=
=

(i)

c2 k(xτ(j) , xt )(SU (τ − 1, t − 1) + 1)
KU (τ, t) + λSU (τ, t − 1)+λSU (τ − 1, t) + λ2 SU (τ − 1, t − 1)

The downstream kernel (15) is modified accordingly.

Figure 5. Ordered trees: shadowed nodes indicate observable variables, and white nodes indicate hidden variables.

Figure 7. Directed acyclic graphs: shadowed nodes indicate observable variables, and white nodes indicate hidden
variables.

possible assignments for y U (τ ) and y U (t). Similarly,
KD (τ, t) is the kernel that considers only the appearances of features with their start positions at τ and t,
and which is marginalized over all possible assignments
for y D (τ ) and y D (t). As in the kernels for sequencelabeling, we can write KU and KD recursively,
Ã
!
X
X
(i)
2
(j)
KU (τ, t) = c k(xτ , xt ) 1 +KU (υ, u)Ã(i)
KD (τ, t) = c k(x(j)τ , xt )2

υ∈P a(τ ) u∈P a(t)

1+

X

X

!

KD (υ, u) ,υ∈Ch(τ ) u∈Ch(t)Figure 6. Intuitive image for computing KU (τ, t).

where SB (τ, t, #ch(τ ) + 1, u) = SB (τ, t, υ, #ch(t) +1) = 1.
KU is computed by dynamic programming in a preorder traversal. KU (τ, t) is computed by combining
the upstream kernel of the parents and the downstream kernels of the siblings (Figure 6),³(i)
KU (τ, t) = c2 k(x(j)τ , xt ) 1 + KU (pa(τ ), pa(t))·SF (pa(τ ), pa(t), chID(τ ) − 1, chID(t) − 1)´
·SB (pa(τ ), pa(t), chID(τ ) + 1, chID(t) + 1) ,Note that the pointwise kernel KP is the same as inEquation (16). A similar analysis to that of Kashima
and Koyanagi (2002) can show that the time complexity of computing the kernel is O(T (i) T (j) ).
4.3. Graph Labeling
Finally, we propose a kernel for labeling directed
acyclic graphs (DAGs) (Figure 7). Unfortunately, it
has been shown to be NP-hard to use arbitrary graphstructured features (Gärtner et al., 2003). Therefore, we propose a marginalized kernel using directed
path features like Figure 2, based on the DAG kernel (Schölkopf et al., 2004).
KU (τ, t) for labeling DAGs is the kernel that considers
only the appearances of features with their end positions at τ and t, and which is marginalized over all

where P a(τ ) and Ch(τ ) are the set of indices of the parent nodes and the child nodesof the τ -th node, respectively.
Note thatthe pointwise kernel KP is the same as Equation (16).
The¡ time complexity of computing
this kernel is O |T (i)¢||T (j) |(maxτ,t |P a(τ )||P a(t)| +maxτ,t |Ch(τ )||Ch(t)|) .

5. Experiments
Finally, we will show the result for experiments on
NLP data to assess the importance of large structuralfeatures in a real-life situation. We conducted two experiments on Named Entity Recognition (NER) and
Product Usage Information Extraction tasks. We compared the performance of the kernel marginalized labeling perceptron with the HM-Perceptrons, which islimited to smaller features in nature.
5.1. Named Entity Recognition
NER is a kind of information extraction task that deals
with identifying proper names such as person names
and organization names in sentences. We used a subcorpus consisting of the first 300 sentences (8,541 tokens) from the Spanish corpus provided for the Special
Session of CoNLL2002 on NER. The task is to label
each word with one of the nine labels, i.e. |Σy | = 9,that represents the types and boundaries of named entities, including a dummy label for non-named entities.
The kernel between two observable labels is designed
by using words and their spelling features, which aredescribed in Altun et al. (2003b) as the S2 features.

Table 1. Named Entity Recognition task result

Accuracy

Precision

RecallTable 2. Product Usage Information Extraction task result

F1

Sequence Kernel 88.4% (3.9) 52.3% (17.5) 19.3% (2.2) 27.9 (5.1)
HM-Perceptron
82.9% (7.4)
21.8% (9) 15.6%(4.5)
17.2 (4)Figure 8. An example of lexicalized dependency trees forthe sentence “They ported their server to a linux cluster
for its availability” where the hidden variable label “D-p”
is for the name of products which a customer uses, “D-r”
is for the reason of use, and “O” is dummy label.

In both algorithms, it is combined with a second degree polynomial kernel. A window of size 3 is also usedin HM-Perceptrons according to (Altun et al., 2003c).
For the proposed perceptron algorithm, we used the sequence kernel withthe mixing parameter c = 1 which,
was determined in preliminary experiments. The priorover hidden variables is modeled as a uniformed distribution, i.e. P (yt |xt ) = 1/|Σy |. The performances
are evaluated according to the labeling accuracies (including correct answers for dummy labels), precisionand recall of named entity labels, and the F1 measure
which is the harmonic mean of the precision and recall.
Table 1 shows the results of the NER task in a 3-foldcross-validation. The values in parentheses represent
the standard deviations on each cross-validation. The
proposed perceptron algorithm with the sequence kernel outperforms the other method. Note that the F1
measure score is a more suitable measure for evaluating
NER tasks than the labeling accuracy because the majority of the annotated labels are dummy labels. The
good performance of the proposed sequence kernel isdue to the nature of NER tasks. NER tasks are known
as one of the NLP problems which require considering
a wide context. For instance, the same phrase “White
house” can be a location or an organization entity indifferent contexts. This empirical result supports theadvantages of the fully-kernelized labeler that can handle rich contextual information efficiently without any
manual selection of an appropriate feature size.
5.2. Product Usage Information Extraction
Product Usage Information Extraction is a special caseof NER tasks which deals with extracting information
about the usage of products from a sales log written by

Accuracy

Precision

RecallF1

Sequence Kernel 88.4% (1.4) 45.7% (10) 35.2% (17.7)
36.7 (5.8)
Tree Kernel
89.8% (1.2) 51.5% (5.2) 32.3% (17.4) 37.9 (12.1)
HM-Perceptron
87.7%(2.0)
40%(16.5)
29%(11.4)
30.7(9.3)

sales representatives. We used 184 sentences (3,570 tokens) from an annotated sales log written in Japanese.
This task aims to identify the product name (p), its
vendor (v), the number of products bought (n), andthe reason for buying (r) linked to a classification of
the customer state that indicates whether the costomer
is already using (D), wishes to use (P), or rejects (R)using the products. In total, there are |Σy | = 12 different labels including a dummy label (O).
All of the Japanese sentences were previously segmented into words, and these words were annotatedwith the part-of-speech and base form. In all of the algorithms, we designed the kernel between two observable labels by using words, part-of-speech tags, baseforms, and character type features. We used it bycombining with the second degree polynomial kernel.
In this task, we use not only the sequence kernel forthe proposed perceptron, but also the tree kernel. For
the tree kernel, we used (lexicalized) dependency treesthat represent linguistic structures of the sentences interms of the dependencies between words. Figure 8
shows an example of a dependency tree in English. To
build the dependency trees for the data set, we used aJapanese statistical parser (Kanayama et al., 2000).3
For both kernels, the mixing parameter is c = 0.8.
Table 2 shows the result of the Product Usage Information Extraction task in 3-fold cross-validation. The parameter settings and the evaluation measures are thesame as in the NER task. Again, we can see the advantage of the proposed perceptron algorithm against the
HM-Perceptrons. Furthermore, the tree kernel utilizing dependency trees shows higher performance than
the sequence kernel, which elaborates the advantage ofusing structured information.

6. Conclusion
In this paper, we introduced an efficient fullykernelized learning algorithm for labeling structured
data such as sequences, trees, and graphs. Our approach can handle large features including arbitrary
numbers of variables by using the pointwise label prediction inspired by Kakade et al. (2002), and themarginalized kernels. We also proposed several instances of the marginalized kernels for labeling sequences, ordered trees and directed acyclic graphs. In
the preliminary experiments on information extraction
3

The accuracy of the parser is 88%.

tasks using real-world data, our approach was shown
to be promising.
As a related work, Weston et al. (2003) have proposed
another general framework that aims at learning thedirect mapping from Φx (x) to Φy (y) with arbitrary
kernels. However, features depending on both x andy are not used. Also, they provide no efficient way to
decode Φy (y) into y.
One possible extension of this research is to incorporate more complicated prior distributions such as
MEMMs and CRFs in the marginalized kernels, although we employed a very simple form of prior distribution in this paper. It is an interesting question
whether our approach boosts such probabilistic models.
Another extension might be an SVM version of our approach. Since HM-SVMs (Altun et al., 2003c) consider
an entire label sequence as an example, maximizationof the margin between correct label sequences and thesecond best label sequences is not always acceptablein problems where each sequence has some difficult labels. On the other hand, our approach avoids thisproblem by considering a label at each position as anindividual example.

References
Altun, Y., Hofmann, T., & Johnson, M. (2003a). Discriminative learning for label sequences via boosting. Advances in Neural Information Processing Systems 15. Cambridge, MA: MIT Press.
Altun, Y., Johnson, M., & Hofmann, T. (2003b). Investigating loss functions and optimization methods
for discriminative learning of label sequences. Proceedings of the Conference on Empirical Methods in
Natural Language Processing.
Altun, Y., Tsochantaridis, I., & Hofmann, T. (2003c).
Hidden Markov support vector machines. Proceedings of the Twentieth International Conference on
Machine Learning.
Collins, M. (2000). Discriminative reranking for natural language parsing. Proceedings of the SeventeenthInternational Conference on Machine Learning (pp.
175–182). San Francisco, CA: Morgan Kaufmann.
Collins, M. (2002). Discriminative training methods
for hidden Markov models: Theory and experimentswith perceptron algorithms. Proceedings of the Conference on Empirical Methods in Natural Language
Processing.
Collins, M., & Duffy, N. (2002). Convolution kernels
for natural language. Advances in Neural Information Processing Systems 14. Cambridge, MA: MIT
Press.
Gärtner, T. (2003). A survey of kernels for structured
data. SIGKDD Explorations, 5, S268–S275.

Gärtner, T., Flach, P., & Wrobel, S. (2003). On graphkernels: Hardness results and efficient alternatives.
Proceedings of the Sixteenth Annual Conference on
Computational Learning Theory.
Kakade, S., Teh, Y. W., & Roweis, S. (2002). An alternative objective function for Markovian fields. Proceedings of the Nineteenth International Conference
on Machine Learning (pp. 275–282). San Francisco,
CA: Morgan Kaufmann.
Kanayama, H., Torisawa, K., Mitsuishi, Y., & Tsujii, J. (2000). A hybrid Japanese parser with handcrafted grammar and statistics. Proceedings ofthe 18th International Conference on Computational
Linguistics (pp. 411–417).
Kashima, H., & Koyanagi, T. (2002). Kernels for semistructured date. Proceedings of the Nineteenth International Conference on Machine Learning (pp.
291–298). San Francisco, CA: Morgan Kaufmann.
Kashima, H., Tsuda, K., & Inokuchi, A. (2003).
Marginalized kernels between labeled graphs. Proceedings of the Twentieth International Conference
on Machine Learning. San Francisco, CA: Morgan
Kaufmann.
Lafferty, J., McCallum, A., & Pereira, F. (2001). Conditional random fields: Probabilistic models for segmenting and labeling sequence data. Proceedings ofthe Eighteenth International Conference on Machine
Learning (pp. 282–289). San Francisco, CA: Morgan
Kaufmann.
Leslie, C., Eskin, E., & Noble, W. S. (2002). The
spectrum kernel: A string kernel for SVM proteinclassification. Proceedings of the Pacific Symposium
on Biocomputing (pp. 566–575). World Scientific.
Lodhi, H., Saunders, C., Shawe-Taylor, J., Cristianini, N., & Watkins, C. (2002). Text classification
using string kernels. Journal of Machine Learning
Research, 2, 419–444.
McCallum, A., D.Freitag, & Pereira, F. (2000). Maximum entropy Markov models for information extraction and segmentation.
Proceedings of theSeventeenth International Conference on Machine
Learning (pp. 591–598). San Francisco, CA: Morgan Kaufmann.
Schölkopf, B., Tsuda, K., & Vert, J.-P. (Eds.). (2004).
Kernel Methods in Bioinformatics. Cambridge, MA:
MIT Press, to appear.
Tsuda, K., Kin, T., & Asai, K. (2002). Marginalized
kernels for biological sequences. Bioinformatics, 18,
S268–S275.
Weston, J., Chapelle, O., Elisseeff, A., Schölkopf, B.,& Vapnik, V. (2003). Kernel dependency estimation.
Advances in Neural Information Processing Systems
15. Cambridge, MA: MIT Press.