Semantic Role Recognition using Kernels on Weighted Marked Ordered
Labeled Trees
Jun’ichi Kazama and Kentaro Torisawa
Japan Advanced Institute of Science and Technology (JAIST)
Asahidai 1-1, Nomi, Ishikawa, 923-1292 Japan{kazama, torisawa}@jaist.ac.jp
Abstract
We present a method for recognizing semantic role arguments using a kernel onweighted marked ordered labeled trees(the WMOLT kernel). We extend thekernels on marked ordered labeled trees(Kazama and Torisawa, 2005) so that themark can be weighted according to its importance. We improve the accuracy bygiving more weights on subtrees that contain the predicate and the argument nodes
with this ability. Although Kazama andTorisawa (2005) presented fast training
with tree kernels, the slow classiﬁcation
during runtime remained to be solved. In
this paper, we give a solution that uses an
efﬁcient DP updating procedure applicable in argument recognition. We demonstrate that the WMOLT kernel improves
the accuracy, and our speed-up method
makes the recognition more than 40 times
faster than the naive classiﬁcation.

1

Introduction

Semantic role labeling (SRL) is a task that recognizes the arguments of a predicate (verb) in a sentence and assigns the correct role to each argument.
As this task is recognized as an important step after(or the last step of) syntactic analysis, many studies have been conducted to achieve accurate semantic role labeling (Gildea and Jurafsky, 2002; Moschitti, 2004; Hacioglu et al., 2004; Punyakanok etal., 2004; Pradhan et al., 2005a; Pradhan et al.,2005b; Toutanova et al., 2005).
Most of the studies have focused on machinelearning because of the availability of standard
datasets, such as PropBank (Kingsbury and Palmer,
2002). Naturally, the usefulness of parse trees inthis task can be anticipated. For example, the recent
CoNLL 2005 shared task (Carreras and Màrquez,2005) provided parse trees for use and their usefulness was ensured. Most of the methods heuristicallyextract features from parse trees, and from othersources, and use them in machine learning methods
based on feature vector representation. As a result,these methods depend on feature engineering, which
is time-consuming.
Tree kernels (Collins and Duffy, 2001; Kashima
and Koyanagi, 2002) have been proposed to directly
handle trees in kernel-based methods, such as SVMs
(Vapnik, 1995). Tree kernels calculate the similarity between trees, taking into consideration all of thesubtrees, and, therefore there is no need for such feature engineering.
Moschitti and Bejan (2004) extensively studied
tree kernels for semantic role labeling. However,they reported that they could not successfully build
an accurate argument recognizer, although the roleassignment was improved. Although Moschitti et al.
(2005) reported on argument recognition using tree
kernels, it was a preliminary evaluation because theyused oracle parse trees.
Kazama and Torisawa (2005) proposed a new tree
kernel for node relation labeling, as which SRL canbe cast. This kernel is deﬁned on marked ordered labeled trees, where a node can have a mark to indicate
the existence of a relation. We refer to this kernel
as the MOLT kernel. Compared to (Moschitti and
Bejan, 2004) where tree fragments are heuristicallyextracted before applying tree kernels, the MOLT
kernel is general and desirable since it does not require such fragment extraction. However, the evaluation conducted by Kazama and Torisawa (2005)
was limited to preliminary experiments for role assignment. In this study, we ﬁrst evaluated the performance of the MOLT kernel for argument recognition, and found that the MOLT kernel cannot achievea high accuracy if used in its original form.

S
NP

S

(a)

VP

NP
PP

NP
PRP VBD

I

saw

S

(b)

VP

NP

(c)

VP

PP
NP

NP

DT

NN

IN DT

a

cat

in the parkNN

PRP VBD

I

saw

*1
PP

NP

NP

DT

NN

IN DT

a

cat

in the parkNN

PRP VBD

I

saw

S

NP

(a')

VP

PP
NP

NP

DT

NN

IN DT

a

cat

in the park

NN

NP

*0
PRP VBD
I

saw

DT

NN

IN DT

NN

a

cat

in

park

the

Figure 1: (a)-(c): Argument recognition as node relation recognition. (a’): relation (a) represented as marked
ordered tree.
Therefore, in this paper we propose a modiﬁcation of the MOLT kernel, which greatly improves
the accuracy. The problem with the original MOLT
kernel is that it treats subtrees with one mark, i.e.,
those including only the argument or the predicate
node, and subtrees with two marks, i.e., those including both the argument and the predicate nodes
equally, although the latter is likely to be more important for distinguishing difﬁcult arguments. Thus,
we modiﬁed the MOLT kernel so that the marks canbe weighted in order to give large weights to the subtrees with many marks. We call the modiﬁed kernel
the WMOLT kernel (the kernel on weighted marked
ordered labeled trees). We show that this modiﬁcation greatly improves the accuracy when the weights
for marks are properly tuned.
One of the issues that arises when using tree kernels is time complexity. In general, tree kernels canbe calculated in O(|T1 ||T2 |) time, where |Ti | is thenumber of nodes in tree Ti , using dynamic programming (DP) procedures (Collins and Duffy, 2001;
Kashima and Koyanagi, 2002). However, this cost
is not negligible in practice. Kazama and Torisawa(2005) proposed a method that drastically speeds up
the calculation during training by converting trees
into efﬁcient vectors using a tree mining algorithm.
However, the slow classiﬁcation during runtime remained an open problem.
We propose a method for speeding up the runtime
classiﬁcation for argument recognition. In argument
recognition, we determine whether a node is an argument or not for all the nodes in a tree . Thisrequires a series of calculations between a support
vector tree and a tree with slightly different marking. By exploiting this property, we can efﬁciently
update DP cells to obtain the kernel value with lesscomputational cost.
In the experiments, we demonstrated that theWMOLT kernel drastically improved the accuracy

and that our speed-up method enabled more than
40 times faster argument recognition. Despite thesesuccesses, the performance of our current system is
F1 = 78.22 on the CoNLL 2005 evaluation set whenusing the Charniak parse trees, which is far worse
than the state-of-the-art system. We will present
possible reasons and future directions.

2 Semantic Role Labeling
Semantic role labeling (SRL) recognizes the arguments of a given predicate and assigns the correctrole to each argument. For example, the sentence “Isaw a cat in the park” will be labeled as follows withrespect to the predicate “see”.
[A0 I] [V saw] [A1 a cat] [AM-LOC in the park]In the example, A0, A1, and AM-LOC are the roles
assigned to the arguments. In the CoNLL 2005
dataset, there are the numbered arguments (AX)whose semantics are predicate dependent, the adjuncts (AM-X), and the references (R-X) for relative clauses.
Many previous studies employed two-step SRL
methods, where (1) we ﬁrst recognize the arguments, and then (2) classify the argument to the correct role. We also assume this two-step processing
and focus on the argument recognition.
Given a parse tree, argument recognition can becast as the classiﬁcation of tree nodes into twoclasses, “ARG” and “NO-ARG”. Then, we consider
the words (a phrase) that are the descendants of an“ARG” node to be an argument. Since arguments
are deﬁned for a given predicate, this classiﬁcationis the recognition of a relation between the predicate
and tree nodes. Thus, we want to build a binary classiﬁer that returns a +1 for correct relations and a -1
for incorrect relations. For the above example, theclassiﬁer will output a +1 for the relations indicatedby (a), (b), and (c) in Figure 1 and a -1 for the relations between the predicate node and other nodes.

Since the task is the classiﬁcation of trees with
node relations, tree kernels for usual ordered labeled trees, such as those proposed by Collins andDuffy (2001) and Kashima and Koyanagi (2002),
are not useful. Kazama and Torisawa (2005) proposed to represent a node relation in a tree as amarked ordered labeled tree and presented a kernel
for it (MOLT kernel). We adopted the MOLT kerneland extend it for accurate argument recognition.

3

Table 1: Notations for MOLT kernel.
• ni denotes a node of a tree. In this paper, ni is an ID assigned in the
post-order traversal.
• |Ti | denotes the number of nodes in tree Ti .
• l(ni ) returns the label of node ni .
• m(ni ) returns the mark of node ni . If ni has no mark, m(ni )returns the special mark no-mark.
• marked(ni ) returns true iff m(ni ) is not no-mark.
• nc(ni ) is the number of children of node ni .
• chk (ni ) is the k-th child of node ni .
• pa(ni ) is the parent of node ni .

Kernels for Argument Recognition• root(Ti ) is the root node of Ti• ni ≽ nj means that ni is an elder sister of nj .

3.1 Kernel-based classiﬁcation
Kernel-based methods, such as support vector machines (SVMs) (Vapnik, 1995), consider a mapping
Φ(x) that maps the object x into a, (usually highdimensional), feature space and learn a classiﬁer inthis space. A kernel function K(xi , xj ) is a functionthat calculates the inner product 〈Φ(xi ), Φ(xj )〉 in
the feature space without explicitly computing Φ(x),which is sometimes intractable. Then, any classiﬁer
that is represented by using only the inner products
between the vectors in a feature space can be rewritten using the kernel function. For example, an
SVM classiﬁer has the form:∑f (x) =αi K(xi , x) + b,iwhere αi and b are the parameters learned in the
training. With kernel-based methods, we can construct a powerful classiﬁer in a high-dimensionalfeature space. In addition, objects x do not need
to be vectors as long as a kernel function is deﬁned(e.g., x can be strings, trees, or graphs).
3.2 MOLT kernel
A marked ordered labeled tree (Kazama and Torisawa, 2005) is an ordered labeled tree in which eachnode can have a mark in addition to a label. We canencode a k-node relation by using k distinct marks.
In this study, we determine an argument node without considering other arguments of the same predicate, i.e., we represent an argument relation as a
two-node relation using two marks. For example,
the relation (a) in Figure 1 can be represented as themarked ordered labeled tree (a’).1
1

Note that we use mark *0 for the predicate node and mark*1 for the argument node.

Kazama and Torisawa (2005) presented a kernel
on marked ordered trees (the MOLT kernel), which
is deﬁned as:2
K(T1 , T2 ) =E∑

W (Si ) · #Si (T1 ) · #Si (T2 ),i=1

where Si is a possible subtree and #Si (Tj ) is
the number of times Si is included in Tj . The
mapping
corresponding √to this kernel is Φ(T ) =√( W (S1 )#S1 (T ), · · · , W (SE )#SE (T )), whichmaps the tree into the feature space of all the possible subtrees.
The tree inclusion is deﬁned in many ways. For
example, Kashima and Koyanagi (2002) presented
the following type of inclusion.
1 D EFINITION S is included in T iff there exists a
one-to-one function ψ from a node of S to a nodeof T , such that (i) pa(ψ(ni )) = ψ(pa(ni )), (ii)
ψ(ni ) ≽ ψ(nj ) iff ni ≽ nj , , and (iii) l(ψ(ni )) =l(ni ) (and m(ψ(ni )) = m(ni ) in the MOLT kernel).
See Table 1 for the meaning of each function. Thisdeﬁnition means that any subtrees preserving theparent-child relation, the sibling relation, and labelmarks, are allowed. In this paper, we employ thisdeﬁnition, since Kazama and Torisawa (2005) reported that the MOLT kernel with this deﬁnition has
a higher accuracy than one with the deﬁnition presented by Collins and Duffy (2001).
W (Si ) is the weight of subtree Si . The weighting in Kazama and Torisawa (2005) is written as fol2

This notation is slightly different from (Kazama and Torisawa, 2005).

Table 2: Example of subtree inclusion and subtree weights. The last row shows the weights for
WMOLT kernel.
Tincluded subtrees

build plants”. For “say”, we have the following labeling.
[A0 He] [V said] [A1 industry should build plants]
On the other hand, for “build”, we haveW (Si )W (Si )

0
0

λ
λγ

λ
λγ

λ2
λ2 γ

λ2
λ2 γ 2

He said [A0 industry] [AM-MOD should] [V build][A1 plants].

λ3
λ3 γ 2lows.
{
λ|Si | if marked(Si ),W (Si ) =0
otherwise,(1)

where marked(Si ) returns true iff marked(ni ) =true for at least one node in tree Si . By this weighting, only the subtrees with at least one mark are considered. The idea behind this is that subtrees having
no marks are not useful for relation recognition orlabeling. λ (0 ≤ λ ≤ 1) is a factor to prevent the kernel values from becoming too large, which has beenused in previous studies (Collins and Duffy, 2001;
Kashima and Koyanagi, 2002).
Table 2 shows an example of subtree inclusion
and the weights given to each included subtree. Notethat the subtrees are treated differently when themarkings are different, even if the labels are thesame.
Although the dimension of the feature spaceis exponential, tree kernels can be calculated in
O(|T1 ||T2 |) time using dynamic programming (DP)procedures (Collins and Duffy, 2001; Kashima andKoyanagi, 2002). The MOLT kernel also has an
O(|T1 ||T2 |) DP procedure (Kazama and Torisawa,
2005).
3.3 WMOLT kernel
Although Kazama and Torisawa (2005) evaluatedthe MOLT kernel for SRL, the evaluation was only
on the role assignment task and was preliminary. We
evaluated the MOLT kernel for argument recognition, and found that the MOLT kernel cannot achievea high accuracy for argument recognition.
The problem is that the MOLT kernel treats subtrees with one mark and subtrees with two marks
equally, although the latter seems to be more important in distinguishing difﬁcult arguments.
Consider the sentence, “He said industry should

As can be seen, “he” is the A0 argument of “say”,
but not an argument of “build”. Thus, our classiﬁershould return a +1 for the tree where “he” is marked
when the predicate is “say”, and a -1 when the predicate is “build”. Although the subtrees around thenode for “say” and “build” are different, the subtrees
around the node for “he” are identical for both cases.
If “he” is often the A0 argument in the corpus, it islikely that the classiﬁer returns a +1 even for “build”.
Although the subtrees containing both the predicate
and the argument nodes are considered in the MOLT
kernel, they are given relatively small weights by Eq.
(1), since such subtrees are large.
Thus, we modify the MOLT kernel so that themark can be weighted according to its importanceand the more marks the subtrees contain, the moreweights they get. The modiﬁcation is simple. Wechange the deﬁnition of W (Si ) as follows.
{∏λ|Si | ni ∈Si γ(m(ni )) if marked(Si ),W (Si ) =0
otherwise,
where γ(m) (≥ 1) is the weight of mark m. We
call a kernel with this weight the WMOLT kernel.
In this study, we assume γ(no-mark) = 1 andγ(*0) = γ(*1) = γ. Then, the weight is simpliﬁed as follows.
{λ|Si | γ #m (Si ) if marked(Si ),W (Si ) =0
otherwise,
where #m (Si ) is the number of marked nodes in
Si . The last row in Table 2 shows how the subtree
weights change by introducing this mark weighting.
For the WMOLT kernel, we can deriveO(|T1 ||T2 |) DP procedure by slightly modifying the procedure presented by Kazama andTorisawa (2005). The method for speeding up
training described in Kazama and Torisawa (2005)
can also be applied with a slight modiﬁcation.

Algorithm 3.1: WMOLT-K ERNEL(T1 , T2 )for n1 ← 1 to |T1 | do // nodes are ordered by the post-order traversalm ← marked(n1 )for
8 n2 ← 1 to |T2 | do // actually iterate only on n2 with l(n1 ) = l(n2 )1 ) ̸= m(n2 ) then>>if l(n1 ) ̸= l(n2 ) or m(n>>C(n1 , n2 ) ← 0 C r (n1 , n2 ) ← 0>>>>
else if n1 and n2 are leaf nodes then>>>if m then C(n1 , n2 ) ← λ · γ; C r (n1 , n2 ) ← λ · γ else C(n1 , n2 ) ← λ; C r (n1 , n2 ) ← 0
>
>
>
>else
>
>
>
>
S(0, j) ← 1, S(i, 0) ← 1 (i ∈ [0, nc(n1 )], j ∈ [0, nc(n2 )])><if m then S r (0, j) ← 1, S r (i, 0) ← 1 else S r (0, j) ← 0, S r (i, 0) ← 0(A)> for i ← 1 to nc(n1 ) do>>>for j ← 1 to nc(n2 ) do>>>>
S(i, j) ← S(i−1, j) + S(i, j −1) − S(i−1, j −1) + S(i−1, j −1) · C(chi (n1 ), chj (n2 ))>>>S r (i, j) ← S r (i−1, j) + S r (i, j −1) − S r (i−1, j −1) + S r (i−1, j −1) · C(chi (n1 ), chj (n2 ))>>>>+S(i−1, j −1) · C r (chi (n1 ), chj (n2 )) − S r (i−1, j −1) · C r (chi (n1 ), chj (n2 ))>>>>if m then C(n1 , n2 ) ← λ · γ · S(nc(n1 ), nc(n2 )) else C(n1 , n2 ) ← λ · S(nc(n1 ), nc(n2 ))>:if m then C r (n1 , n2 ) ← λ · γ · S r (nc(n1 ), nc(n2 )) else C r (n1 , n2 ) ← λ · S r (nc(n1 ), nc(n2 ))P 1 | P|T2 |rreturn ( |T
n1 =1
n2 =1 C (n1 , n2 ))We describe this DP procedure in some detail.
The key is the use of two DP matrices of size
|T1 | × |T2 |. The ﬁrst is C(n1 , n2 ) deﬁned as:
C(n1 , n2 )≡P′
Si W (Si ) · #Si (T1 △ n1 ) · #Si (T2 △ n2 ),where #Si (Tj △ nk ) represents the number of times
subtree Si is included in tree Tj with ψ(root(Si )) =nk . W ′ (Si ) is deﬁned as W ′ (Si ) = λ|Si | γ #m (Si ) .
This means that this matrix records the values that
ignore whether marked(Si ) = true or not. The
second is C r (n1 , n2 ) deﬁned as:
C r (n1 , n2 )≡P

Si W (Si ) · #Si (T1 △ n1 ) · #Si (T2 △ n2 ).

With these matrices, the kernel is calculated as:∑ ∑K(T1 , T2 ) =C r (n1 , n2 ).
n1 ∈T1 n2 ∈T2

C r (n1 , n2 )C(n1 , n2 ) andare calculated recursively, starting from the leaves of the trees. The recursive procedure is shown in Algorithm 3.1. See
also Table 1 for the meaning of the functions used.

4 Fast Argument Recognition
We use the SVMs for the classiﬁers in argument
recognition in this study and describe the fast classiﬁcation method based on SVMs.3 We denote amarked ordered labeled tree where node nk of anordered labeled tree U is marked by mark X, nl by
Y , and so on, by U @{nk = X, nl = Y, . . . }.
3

The method can be applied to a wide range of kernel-based
methods that have the same structure as SVMs.

Algorithm 4.1: C ALCULATE -T(U, Tj )procedure FAST-U PDATE(nk )diﬀ ← 0, m(nk ) ← *1, U ← φ
for n2 ← 1 to |Tj | do change(n2 ) ← truen1 ← nk
while
8 n1 ̸= nil dofor n2 ← 1 to |Tj | do>>>>
> // actually iterate only on n2 with l(pa(n1 )) = l(n2 )>>nchange(n2 ) ← false
>
>
>
>
for
n2 ← 1 to |Tj | do>>>>// actually iterate only on n2 with l(n1 ) = l(n2 )><if change(n2 ) thenpre ← C r (n1 , n2 ), U ← U ∪ (n1 , n2 )>>>>update C(n1 , n2 ) and C r (n1 , n2 )>>>using (A) of Algorithm 3.1
>
>
>
>
diﬀ
+ = (C r (n1 , n2 ) − pre)
>
>
>
>
if
pa(n
2 ) ̸= nil then nchange(pa(n2 )) ← true>:n1 ← pa(n1 ), change ← nchangefor (n1 , n2 ) ∈ U do //restore DP cells
C(n1 , n2 ) ← C ′ (n1 , n2 ), C r (n1 , n2 ) ← C r ′ (n1 , n2 )m(nk ) ← no-markreturn (diﬀ )mainm(nv ) ← ∗0, k ← WMOLT-K ERNEL(U, Tj )C ′ (n1 , n2 ) ← C(n1 , n2 ), C r ′ (n1 , n2 ) ← C r (n1 , n2 )for nk ← 1 to |U | do (nk ̸= nv )diﬀ ← FAST-U PDATE(nk ), t(nk ) ← k + diﬀ

Given a sentence represented by tree U and thenode for the target predicate nv , the argument recognition requires the calculation of:∑s(nk ) =αj K(U @{nv = *0, nk = *1}, Tj )+b,
Tj ∈SV(2)
for all nk ∈ U (̸= nv ), where SV represents the
support vectors. Naively, this requires O(|U | ×|SV| × |U ||Tj |) time, which is rather costly in practice.

However, if we exploit the fact that U @{nv =*0, nk = *1} is different from U @{nv = *0} at one
node, we can greatly speed up the above calculation.
At ﬁrst, we calculate K(U @{nv = *0}, Tj ) using
the DP procedure presented in the previous section,and then calculate K(U @{nv = *0, nk = *1}, Tj )using a more efﬁcient DP that updates only the values of the necessary DP cells of the ﬁrst DP. Morespeciﬁcally, we only need to update the DP cells involving the ancestor nodes of nk .
Here we show the procedure for calculatingt(nk ) = K(U @{nv = *0, nk = *1}, Tj ) for all
nk for a given support vector Tj , which will sufﬁce for calculating s(nk ). Algorithm 4.1 shows theprocedure. For each nk , this procedure updates atmost (nk ’s depth) × |Tj | cells, which is much lessthan |U | × |Tj | cells. In addition, when updating
the cells for (n1 , n2 ), we only need to update themwhen the cells for any child of n2 have been updated
in the calculation of the cells for the children of n1 .
To achieve this, change(n2 ) in the algorithm stores
whether the cells of any child of n2 have been updated. This technique will also reduce the numberof updated cells.

5 Non-overlapping Constraint
Finally, in argument recognition, there is a strong
constraint that the arguments for a given predicate
do not overlap each other. To enforce this constraint,
we employ the approach presented by Toutanova
et al. (2005). Given the local classiﬁcation probability p(nk = Xk ) (Xk ∈ {ARG, NO-ARG}),
this∏ method ﬁnds the assignment that maximizes
k p(nk = Xk ) while satisfying the above nonoverlapping constraint, by using a dynamic programming procedure. Since the output of SVMs is
not a probability value, in this study we obtain theprobability value by converting the output from theSVM, s(nk ), using the sigmoid function:4p(nk = ARG) = 1/(1 + exp(−s(nk ))).

6 Evaluation
6.1 Setting
For our evaluation we used the dataset provided for the CoNLL 2005 SRL shared task
4

Parameter ﬁtting (Platt, 1999) is not performed.

(www.lsi.upc.edu/˜srlconll). We used only the training part and divided it into our training, development, and test sets (23,899, 7,966, and 7,967 sentences, respectively). We used the outputs of theCharniak parser provided with the dataset. We also
used POS tags, which were also provided, by inserting the nodes labeled by POS tags above the word
nodes. The words were downcased.
We used TinySVM5 as the implementation of theSVMs, adding the WMOLT√ kernel. We normalized
the kernel as: K(Ti , Tj )/ K(Ti , Ti ) × K(Tj , Tj ).
To train the classiﬁers, for a positive example weused the marked ordered labeled tree that encodes
an argument in the training set. Although nodes
other than the argument nodes were potentially negative examples, we used 1/5 of these nodes that wererandomly-sampled, since the number of such nodes
is so large that the training cannot be performed inpractice. Note that we ignored the arguments that
do not match any node in the tree (the rate of sucharguments was about 3.5% in the training set).
6.2 Effect of mark weighting
We ﬁrst evaluated the effect of the mark weighting of the WMOLT kernel. For several ﬁxed γ, we
tuned λ and the soft-margin constant of the SVM, C,
and evaluated the recognition accuracy. We tested
30 different values of C ∈ [0.1 . . . 500] for eachλ ∈ [0.05, 0.1, 0.15, 0.2, 0.25, 0.3]. The tuning was
performed using the method for speeding up thetraining with tree kernels described by Kazama andTorisawa (2005). We conducted the above experiment for several training sizes.
Table 3 shows the results. This table shows thebest setting of λ and C, the performance on the development set with the best setting, and the performance on the test set. The performance is shownin the F1 measure. Note that we treated the region
labeled C-k in the CoNLL 2005 dataset as an independent argument.
We can see that the mark weighting greatly improves the accuracy over the original MOLT kernel(i.e., γ = 1). In addition, we can see that the best
setting for γ is somewhere around γ = 4, 000. In
this experiment, we could only test up to 1,000 sentences due to the cost of SVM training, which were
5chasen.org/˜taku/software/TinySVM

Table 3: Effect of γ in mark weighting of WMOLT kernel.
250
γ
1
100
1,000
2,000
4,000
4,000 (w/o)

setting(λ,C)
0.15, 20.50
0.3, 12.04
0.2, 2.438
0.2, 2.438
0.2, 2.438

dev
(F1 )
63.66
80.13
82.65
83.43
83.87
80.81

test
(F1 )
65.13
80.85
83.36
84.12
84.50
81.41

training size (No. of sentences)
500
700
settingdev
test
settingdev(λ,C) (F1 ) (F1 )(λ,C) (F1 )0.2, 20.50 69.01 70.33 0.2, 20.50 72.11
0.3,500 82.25 82.98 0.3, 34.92 83.93
0.2, 2.438 84.80 85.45 0.2, 3.182 85.58
0.2, 2.438 85.56 86.24 0.2, 2.438 86.23
0.15, 4.15 84.94 85.61 0.15, 7.07 85.84
80.71 81.51
81.86

empirically O(L2 ) where L is the number of training examples, regardless of the use of the speed-up
method (Kazama and Torisawa, 2005), However, we
can observe that the WMOLT kernel achieves a highaccuracy even when the training data is very small.
6.3 Effect of non-overlapping constraint
Additionally, we observed how the accuracychanges when we do not use the method describedin Section 5 and instead consider the node to be anargument when s(nk ) > 0. The last row in Table 3 shows the accuracy for the model obtainedwith γ = 4, 000. We could observe that the nonoverlapping constraint also improves the accuracy.
6.4 Recognition speed-up
Next, we examined the method for fast argument
recognition described in Section 4. Using the classiﬁers with γ = 4, 000, we measured the time required for recognizing the arguments for 200 sentences with the naive classiﬁcation of Eq. (2) andwith the fast update procedure shown in Algorithm
4.1. The time was measured using a computer with
2.2-GHz dual-core Opterons and 8-GB of RAM.
Table 4 shows the results. We can see a constant
speed-up by a factor of more than 40, although thetime was increased for both methods as the size ofthe training data increases (due to the increase in thenumber of support vectors).
Table 4: Recognition time (sec.) with naive classiﬁcation and proposed fast update.
training size (No. of sentences)
250
500
750
1,000
naive
11,266 13,008 18,313 30,226
proposed
226
310
442
731
speed-up
49.84
41.96
41.43
41.34

test
(F1 )
73.57
84.72
86.20
86.80
86.32
82.33

1,000
settingdev(λ,C) (F1 )0.25, 12.04 75.38
0.3, 3.18 85.09
0.2, 7.071 86.40
0.2, 12.04 86.61
0.2, 12.04 86.82
84.27

test
(F1 )
76.25
85.85
86.80
87.18
87.31
84.63

6.5 Evaluation on CoNLL 2005 evaluation set
To compare the performance of our system withother systems, we conducted the evaluation on theofﬁcial evaluation set of the CoNLL 2005 sharedtask. We used a model trained using 2,000 sentences (57,547 examples) with (γ = 4, 000, λ =0.2, C = 12.04), the best setting in the previous experiments. This is the largest model we have successfully trained so far, and has F1 = 88.00 on thetest set in the previous experiments.
The accuracy of this model on the ofﬁcial evaluation set was F1 = 79.96 using the criterion from theprevious experiments where we treated a C-k argument as an independent argument. The ofﬁcial evaluation script returned F1 = 78.22. This differenceis caused because the ofﬁcial script takes C-k arguments into consideration, while our system cannot
output C-k labels since it is just an argument recognizer. Therefore, the performance will becomeslightly higher than F1 = 78.22 if we perform therole assignment step. However, our current system
is worse than the systems reported in the CoNLL
2005 shared task in any case, since it is reported thatthey had F1 = 79.92 to 83.78 argument recognition
accuracy (Carreras and Màrquez, 2005).

7 Discussion
Although we have improved the accuracy by introducing the WMOLT kernel, the accuracy for the ofﬁcial evaluation set was not satisfactory. One possible
reason is the accuracy of the parser. Since the Charniak parser is trained on the same set with the training set of the CoNLL 2005 shared task, the parsing accuracy is worse for the ofﬁcial evaluation set
than for the training set. For example, the rate of thearguments that do not match any node of the parsetree is 3.93% for the training set, but 8.16% for theevaluation set. This, to some extent, explains why
our system, which achieved F1 = 88.00 for our test
set, could only achieved F1 = 79.96. To achieve ahigher accuracy, we need to make the system morerobust to parsing errors. Some of the non-matchingarguments are caused by incorrect treatment of quotation marks and commas. These errors seem to besolved by using simple pre-processing. Other major
non-matching arguments are caused by PP attachment errors. To solve these errors, we need to explore more, such as using n-best parses and the useof several syntactic views (Pradhan et al., 2005b).
Another reason for the low accuracy is the size ofthe training data. In this study, we could train the
SVM with 2,000 sentences (this took more than 30hours including the conversion of trees), but this isa very small fraction of the entire training set. We
need to explore the methods for incorporating a large
training set within a reasonable training time. For
example, the combination of small SVMs (Shen etal., 2003) is a possible direction.
The contribution of this study is not the accuracy
achieved. The ﬁrst contribution is the demonstrationof the drastic effect of the mark weighting. We will
explore more accurate kernels based on the WMOLT
kernel. For example, we are planning to use different weights depending on the marks. The second contribution is the method of speeding-up argument recognition. This is of great importance, since
the proposed method can be applied to other tasks
where all nodes in a tree should be classiﬁed. In addition, this method became possible because of the
WMOLT kernel, and it is hard to apply to Moschitti
and Bejan (2004) where the tree structure changes
during recognition. Thus, the architecture that uses
the WMOLT kernel is promising, if we assume further progress is possible with the kernel design.

8 Conclusion
We proposed a method for recognizing semantic rolearguments using the WMOLT kernel. The markweighting introduced in the WMOLT kernel greatly
improved the accuracy. In addition, we presented
a method for speeding up the recognition, which resulted in more than a 40 times faster recognition. Although the accuracy of the current system is worse
than the state-of-the-art system, we expect to further
improve our system.

References
X. Carreras and L. Màrquez. 2005. Introduction to the
CoNLL-2005 shared task: Semantic role labeling. In
CoNLL 2005.
M. Collins and N. Duffy. 2001. Convolution kernels fornatural language. In NIPS 2001.
D. Gildea and D. Jurafsky. 2002. Automatic labeling of
semantic roles. Computational Linguistics, 28(3).
K. Hacioglu, S. Pradhan, W. Ward, J. H. Martin, and
D. Jurafsky. 2004. Semantic role labeling by tagging
syntactic chunks. In CoNLL 2004.
H. Kashima and T. Koyanagi. 2002. Kernels for semistructured data. In ICML 2002, pages 291–298.
J. Kazama and K. Torisawa. 2005. Speeding up training
with tree kernels for node relation labeling. In EMNLP
2005.
P. Kingsbury and M. Palmer. 2002. From treebank to
propbank. In LREC 02.
A. Moschitti and C. A. Bejan. 2004. A semantic kernels
for predicate argument classiﬁcation. In CoNLL 2004.
A. Moschitti, B. Coppola, D. Pighin, and B. Basili. 2005.
Engineering of syntactic features for shallow semantic
parsing. In ACL 2005 Workshop on Feature Enginnering for Machine Learning in Natural Language Processing.
A. Moschitti. 2004. A study on convolution kernels forshallow semantic parsing. In ACL 2004.
J. C. Platt. 1999. Probabilistic outputs for support vector
machines and comparisons to regularized likelihood
methods. Advances in Large Margin Classiﬁers.
S. Pradhan, K. Hacioglu, W. Ward, D. Jurafsky, and J. H.
Martin. 2005a. Support vector learning for semantic
argument classiﬁcation. Machine Learning, 60(1).
S. Pradhan, W. Ward, K. Hacioglu, J. H. Martin, and
D. Jurafsky. 2005b. Semantic role labeling using different syntactic views. In ACL 2005.
V. Punyakanok, D. Roth, W. Yih, and D. Zimak. 2004.
Semantic role labeling via integer linear programming
inference. In COLING 2004.
L. Shen, A. Sarkar, and A. K. Joshi. 2003. Using LTAG
based features in parse reranking. In EMNLP 2003.
K. Toutanova, A. Haghighi, and C. D. Manning. 2005.
Joint learning improves semantic role labeling. In ACL
2005.
V. Vapnik. 1995. The Nature of Statistical Learning Theory. Springer Verlag.