Boosting-based parse reranking with subtree features
Taku Kudo ∗ Jun Suzuki
Hideki Isozaki
NTT Communication Science Laboratories.
2-4 Hikaridai, Seika-cho, Soraku, Kyoto, Japan{taku,jun,isozaki}@cslab.kecl.ntt.co.jp

Abstract
This paper introduces a new application of boosting for parse reranking. Several parsers have been
proposed that utilize the all-subtrees representation (e.g., tree kernel and data oriented parsing).
This paper argues that such an all-subtrees representation is extremely redundant and a comparable accuracy can be achieved using just a small
set of subtrees. We show how the boosting algorithm can be applied to the all-subtrees representation and how it selects a small and relevant feature
set efficiently. Two experiments on parse reranking show that our method achieves comparable oreven better performance than kernel methods andalso improves the testing efficiency.

1

Introduction

and require careful design to create the optimal feature set for each task. Kernel methods offer an elegant solution to these problems. They can work on apotentially huge or even infinite number of features
without a loss of generalization. The best known
kernel for modeling a tree is the tree kernel (Collins
and Duffy, 2002), which argues that a feature vector is implicitly composed of the counts of subtrees.
Although kernel methods are general and can coveralmost all useful features, the set of subtrees that isused is extremely redundant. The main question addressed in this paper concerns whether it is possible
to achieve a comparable or even better accuracy using just a small and non-redundant set of subtrees.
In this paper, we present a new application of
boosting for parse reranking. While tree kernel
implicitly uses the all-subtrees representation, ourboosting algorithm uses it explicitly. Although thisset-up makes the feature space large, the l1 -norm
regularization achived by boosting automatically selects a small and relevant feature set. Such a smallfeature set is useful in practice, as it is interpretable
and makes the parsing (reranking) time faster. We
also incorporate a variant of the branch-and-boundtechnique to achieve efficient feature selection ineach boosting iteration.

Recent work on statistical natural language parsing and tagging has explored discriminative techniques. One of the novel discriminative approaches
is reranking, where discriminative machine learningalgorithms are used to rerank the n-best outputs ofgenerative or conditional parsers. The discriminative reranking methods allow us to incorporate various kinds of features to distinguish the correct parse 2 General setting of parse reranking
tree from all other candidates.
With such feature design flexibility, it is non- We describe the general setting of parse reranking.
trivial to employ an appropriate feature set that has • Training data T is a set of input/output pairs, e.g.,a good discriminative ability for parse reranking. In
T = {hx1 , y1 i, . . . , hxL , yL i}, where xi is an inearly studies, feature sets were given heuristically by
put sentence, and yi is a correct parse associatedsimply preparing task-dependent feature templateswith the sentence xi .
(Collins, 2000; Collins, 2002). These ad-hoc solutions might provide us with reasonable levels of per- • Let Y(x) be a function that returns a set of candidate parse trees for a particular sentence x.
formance. However, they are highly task dependent• We assume that Y(xi ) contains the correct parsetree yi , i.e., yi ∈ Y(xi ) ∗• Let Φ(y) ∈ Rd be a feature function that maps
the given parse tree y into Rd space. w ∈ Rd isa parameter vector of the model. The output parseŷ of this model on input sentence x is given as:ŷ = argmaxy∈Y(x) w · Φ(y).
There are two questions as regards this formulation. One is how to set the parameters w, and theother is how to design the feature function Φ(y). We
briefly describe the well-known solutions to thesetwo problems in the next subsections.
2.1 Parameter estimation
We usually adopt a general loss function Loss(w),and set the parameters w that minimize the loss,
i.e., ŵ = argminw∈Rd Loss(w). Generally, the loss
function has the following form:
Loss(w) =L
X

L(w, Φ(yi ), xi ),i=1

where L(w, Φ(yi ), xi ) is an arbitrary loss function.
We can design a variety of parameter estimation
methods by changing the loss function. The following three loss functions, LogLoss, HingeLoss, andBoostLoss, have been widely used in parse reranking tasks.

2.2 Definition of feature function
It is non-trivial to define an appropriate feature function Φ(y) that has a good ability to distinguish thecorrect parse yi from all other candidates
In early studies, the feature functions were given
heuristically by simply preparing feature templates(Collins, 2000; Collins, 2002). However, suchheuristic selections are task dependent and would
not cover all useful features that contribute to overall
accuracy.
When we select the special family of loss functions, the problem can be reduced to a dual form that
depends only on the inner products of two instances
Φ(y1 ) · Φ(y2 ). This property is important as we canuse a kernel trick and we do not need to provide an
explicit feature function. For example, tree kernel(Collins and Duffy, 2002), one of the convolution
kernels, implicitly maps the instance represented ina tree into all-subtrees space. Even though the feature space is large, inner products under this feature
space can be calculated efficiently using dynamic
programming. Tree kernel is more general than feature templates since it can use the all-subtrees representation without loss of efficiency.

3 RankBoost with subtree features

A simple question related to kernel-based parsereranking asks whether all subtrees are really needed
to construct the final parameters w. Suppose weţ Xűşť have two large trees t and t0 , where t0 is simply genLogLoss = − log
exp w · [Φ(yi ) − Φ(y)]erated by attaching a single node to t. In most cases,y∈Y(xi )these two trees yield an almost equivalent discrimiX
HingeLoss =max(0, 1 − w · [Φ(yi ) − Φ(y)])
native ability, since they are very similar and highlyy∈Y(xi )correlated with each other. Even when we exploit allşťX
BoostLos =exp − w · [Φ(yi ) − Φ(y)]subtrees, most of them are extremely redundant.
y∈Y(xi )The motivation of this paper is based on the above
LogLoss is based on the standard maximum like- observation. We think that only a small set of sublihood optimization, and is used with maximum en- trees is needed to express the final parameters. A
tropy models. HingeLoss captures the errors only compact, non-redundant, and highly relevant featurewhen w · [Φ(yi ) − Φ(y)]) < 1. This loss is closely set is useful in practice, as it is interpretable and inrelated to the maximum margin strategy in SVMs creases the parsing (reranking) speed.
To realize this goal, we propose a new boosting(Vapnik, 1998). BoostLoss is analogous to thebasedreranking algorithm based on the all-subtrees
boosting algorithm and is used in (Collins, 2000;
representation.
First, we describe the architecture ofCollins, 2002).
our reranking method. Second, we show a connec∗
In the real setting, we cannot assume this condition. In thistion between boosting and SVMs, and describe howcase, we select the parse tree ŷ that is the most similar to yi andthe algorithm realizes the sparse feature representatake ŷ as the correct parse tree yi .












  3.3 RankBoost algorithmFigure 1: Labeled ordered tree and subtree relation
tion described above.
3.1 Preliminaries
Let us introduce a labeled ordered tree (or simply’tree’), its definition and notations, first.
Definition 1 Labeled ordered tree (Tree)
A labeled ordered tree is a tree where each node isassociated with a label and is ordered among its siblings, that is, there is a first child, second child, thirdchild, etc.
Definition 2 Subtree
Let t and u be labeled ordered trees. We say that t
matches u, or t is a subtree of u (t ⊆ u), if there is a
one-to-one function ψ from nodes in t to u, satisfying
the conditions: (1) ψ preserves the parent-daughter
relation, (2) ψ preserves the sibling relation, (3) ψpreserves the labels.
We denote the number of nodes in t as |t|. Figure 1
shows an example of a labeled ordered tree and its
subtree and non-subtree.
3.2 Feature space given by subtrees
We first assume that a parse tree y is represented ina labeled ordered tree. Note that the outputs of partof-speech tagging, shallow parsing, and dependency
analysis can be modeled as labeled ordered trees.
The feature set F consists of all subtrees seen in
the training data, i.e.,F = ∪i,y∈Y(xi ) {t | t ⊆ y}.
The feature mapping Φ(y) is then given by letting
the existence of a tree t be a single dimension, i.e.,Φ(y) = {I(t1 ⊆ y), . . . , I(tm ⊆ y)} ∈ {0, 1}m ,where I(·) is the indicator function, m = |F|, and{t1 , . . . , tm } ∈ F. The feature space is essentiallythe same as that of tree kernel ††Strictly speaking, tree kernel uses the cardinality of each
subtree

The parameter estimation method we adopt is a variant of the RankBoost algorithm introduced in (Freund et al., 2003). Collins et al. used RankBoost toparse reranking tasks (Collins, 2000; Collins, 2002).
The algorithm proceeds for K iterations and tries tominimize the BoostLoss for given training data‡ .
At each iteration, a single feature (hypothesis) is
chosen, and its weight is updated.
Suppose we have current parameters:
w = {w1 , w2 , . . . , wm } ∈ Rm .
New parameters w∗ hk,δi ∈ Rm are then given by
selecting a single feature k and updating the weight
through an increment δ:w∗ hk,δi = {w1 , w2 , . . . , wk + δ, . . . , wm }.
After the update, the new loss is given:
Loss(w∗ hk,δi ) =

X

ş
exp

ť
∗
− whk,δi· [Φ(yi ) − Φ(y)] .

(1)i, y∈Y(xi )The RankBoost algorithm iteratively selects the optimal pair hk̂, δ̂i that minimizes the loss, i.e.,hk̂, δ̂i = argmin Loss(w∗ hk,δi ).
hk,δi

By setting the differential of (1) at 0, the following
optimal solutions are obtained:
ŕ
ŕq
q
W+
ŕ
ŕ
1
k̂ = argmax ŕŕ Wk+ − Wk− ŕŕ, and δ = log k̂− ,2W
k=1,...,m

(2)

k̂

P
where Wkb = i,y∈Y(xi ) D(yi , y) · I[I(tk ⊆ yi ) −I(tk ⊆ y) = b], b ∈ {+1, −1}, and D(yi , y) =exp ( − w · [Φ(yi ) − Φ(y)]).
Following (Freund et al., 2003; Collins, 2000), we
introduce smoothing to prevent the case when either
Wk+ or Wk− is 0 § :δ=X
W + + ²Z
1
log k̂−, where Z =D(yi , y) and ² ∈ R+ .
2
W + ²Zk̂

i,y∈Y(xi )The function Y(x) is usually performed by aprobabilistic history-based parser, which can output
not only a parse tree but the log probability of the‡

In our experiments, optimal settings for K were selectedby using development data.
§
For simplicity, we fix ² at 0.001 in all our experiments.

tree. We incorporate the log probability into thereranking by using it as a feature:Φ(y) = {L(y), I(t1 ⊆ y), . . . , I(tm ⊆ y)}, andw = {w0 , w1 , w2 , . . . , wm },where L(y) is the log probability of a tree y under the base parser and w0 is the parameter of L(y).
Note that the update algorithm (2) does not allow us
to calculate the parameter w0 , since (2) is restricted
to binary features. To prevent this problem, we use
the approximation technique introduced in (Freundet al., 2003).
3.4 Sparse feature representation
Recent studies (Schapire et al., 1997; Rätsch, 2001)
have shown that both boosting and SVMs (Vapnik,
1998) work according to similar strategies: constructing optimal parameters w that maximize thesmallest margin between positive and negative examples. The critical difference is the definition of
margin or the way they regularize the vector w.
(Rätsch, 2001) shows that the iterative feature selection performed in boosting asymptotically realizes
an l1 -norm ||w||1 regularization. In contrast, it iswell known that SVMs are reformulated as an l2 norm ||w||2 regularized algorithm.
The relationship between two regularizations has
been studied in the machine learning community.
(Perkins et al., 2003) reported that l1 -norm should
be chosen for a problem where most given features
are irrelevant. On the other hand, l2 -norm should bechosen when most given features are relevant. An
advantage of the l1 -norm regularizer is that it often
leads to sparse solutions where most wk are exactly
0. The features assigned zero weight are thought tobe irrelevant features as regards classifications.
The l1 -norm regularization is useful for our setting, since most features (subtrees) are redundantand irrelevant, and these redundant features are automatically eliminated.

4 Efficient Computation
In each boosting iteration, we have to solve the following optimization problem:k̂ = argmax gain(tk ),k=1,...,m

q
¯q
¯
¯
¯
where gain(tk ) = ¯ Wk+ − Wk− ¯.

It is non-trivial to find the optimal tree tk̂ that maximizes gain(tk ), since the number of subtrees is exponential to its size. In fact, the problem is known
to be NP-hard (Yang, 2004). However, in real applications, the problem is manageable, since the maximum number of subtrees is usually bounded by aconstant. To solve the problem efficiently, we now
adopt a variant of the branch-and-bound algorithm,
similar to that described in (Kudo and Matsumoto,2004)
4.1 Efficient Enumeration of Trees
Abe and Zaki independently proposed an efficientmethod, rightmost-extension, for enumerating all
subtrees from a given tree (Abe et al., 2002; Zaki,
2002). First, the algorithm starts with a set of trees
consisting of single nodes, and then expands a given
tree of size (n−1) by attaching a new node to it toobtain trees of size n. However, it would be inefficient to expand nodes at arbitrary positions of thetree, as duplicated enumeration is inevitable. The
algorithm, rightmost extension, avoids such duplicated enumerations by restricting the position of attachment. Here we give the definition of rightmost
extension to describe this restriction in detail.
Definition 3 Rightmost Extension (Abe et al., 2002;
Zaki, 2002)
Let t and t0 be labeled ordered trees. We say t0 is arightmost extension of t, if and only if t and t0 satisfy
the following three conditions:(1) t0 is created by adding a single node to t, (i.e.,t ⊂ t0 and |t| + 1 = |t0 |).
(2) A node is added to a node existing on the uniquepath from the root to the rightmost leaf (rightmostpath) in t.
(3) A node is added as the rightmost sibling.
Consider Figure 2, which illustrates example tree t
with labels drawn from the set L = {a, b, c}. For
the sake of convenience, each node in this figure has
its original number (depth-first enumeration). The
rightmost-path of the tree t is (a(c(b))), and it occurs at positions 1, 4 and 6 respectively. The set ofrightmost extended trees is then enumerated by simply adding a single node to a node on the rightmost
path. Since there are three nodes on the rightmost
path and the size of the label set is 3 (= |L|), a to-rightmost extension t’
1 a

t
1 a

rightmost- path

2 b

4

3 c

5 a

2 b

4

3 c

5 a

c

c

{a, b, c}
7

6 b

1 a

6 b

L = {a, b, c}

2 b

4

3 c

5 a

c
6 b 7

1 a
2 b

4

3 c

5 a

{a, b, c}c
6 b{a, b, c}7

Figure 2: Rightmost extension
tal of 9 trees are enumerated from the original treet. By repeating the rightmost-extension process recursively, we can create a search space in which alltrees drawn from the set L are enumerated.
4.2 Pruning
Rightmost extension defines a canonical search
space in which we can enumerate all subtrees froma given set of trees. Here we consider an upperbound of the gain that allows subspace pruning inthis canonical search space. The following observation provides a convenient way of computing an
upper bound of the gain(tk ) for any super-tree tk0
of tk .
Observation 1 Upper bound of the gain(tk )For any tk0 ⊇ tk , the gain of tk0 is bounded byµ(tk ):
gain(tk0 )

=
≤
≤

since

ŕ
ŕq
q
ŕ
ŕ
ŕ W +0 − W −0 ŕ
k
k
ŕ
ŕ
q
q
max( Wk+0 , Wk−0 )qqmax( Wk+ , Wk− ) = µ(tk ),tk0 ⊇ tk ⇒ Wkb0 ≤ Wkb , b ∈ {+1, −1}.

We can efficiently prune the search space spannedby the rightmost extension using the upper bound ofgain µ(t). During the traverse of the subtree lattice
built by the recursive process of rightmost extension,
we always maintain the temporally suboptimal gain
τ of all the previously calculated gains. If µ(t) < τ ,the gain of any super-tree t0 ⊇ t is no greater than τ ,and therefore we can safely prune the search spacespanned from the subtree t. In contrast, if µ(t) ≥ τ ,we cannot prune this space, since there might be asuper-tree t0 ⊇ t such that gain(t0 ) ≥ τ .
4.3

Ad-hoc techniques

In real applications, we also employ the following
practical methods to reduce the training costs.

• Size constraint
Larger trees are usually less effective to discrimination. Thus, we give a size threshold s, and use
subtrees whose size is no greater than s. This constraint is easily realized by controlling the rightmost extension according to the size of the trees.
• Frequency constraint
The frequency-based cut-off has been widely usedin feature selections. We employ a frequency
threshold f , and use subtrees seen on at least one
parse for at least f different sentences. Note thata similar branch-and-bound technique can also be
applied to the cut-off. When we find that the frequency of a tree t is no greater than f , we can safely
prune the space spanned from t as the frequencies
of any super-trees t0 ⊇ t are also no greater than f .
• Pseudo iterations
After several 5- or 10-iterations of boosting, we alternately perform 100- or 300 pseudo iterations, inwhich the optimal feature (subtree) is selected fromthe cache that maintains the features explored in theprevious iterations. The idea is based on our observation that a feature in the cache tends to be reused as the number of boosting iterations increases.
Pseudo iterations converge very fast, and help thebranch-and-bound algorithm find new features thatare not in the cache.

5

Experiments

5.1

Parsing Wall Street Journal Text

In our experiments, we used the same data set thatused in (Collins, 2000). Sections 2-21 of the Penn
Treebank were used as training data, and section
23 was used as test data. The training data contains about 40,000 sentences, each of which has anaverage of 27 distinct parses. Of the 40,000 training sentences, the first 36,000 sentences were used
to perform the RankBoost algorithm. The remaining 4,000 sentences were used as development data.
Model2 of (Collins, 1999) was used to parse boththe training and test data.
To capture the lexical information of the parsetrees, we did not use a standard CFG tree but alexicalized-CFG tree where each non-terminal node
has an extra lexical node labeled with the head wordof the constituent. Figure 3 shows an example of thelexicalized-CFG tree used in our experiments. The

TOP
S
(saw)

NP

VP

(I) PRP (saw) VBD
I≤ 40 Words (2245 sentences)LR
LP CBs 0 CBs 2 CBs
CO99 88.5% 88.7% 0.92 66.7% 87.1%
CH00 90.1% 90.1% 0.74 70.1% 89.6%
CO00 90.1% 90.4% 0.74 70.3% 89.6%
CO02 89.1% 89.4% 0.85 69.3% 88.2%
Boosting 89.9% 90.1% 0.77 70.5% 89.4%
MODEL≤ 100 Words (2416 sentences)LR
LP CBs 0 CBs 2 CBs
CO99 88.1% 88.3% 1.06 64.0% 85.1%
CH00 89.6% 89.5% 0.88 67.6% 87.7%
CO00 89.6% 89.9% 0.87 68.3% 87.7%
CO02 88.6% 88.9% 0.99 66.5% 86.3%
Boosting 89.3% 89.6% 0.90 67.9% 87.5%
MODEL

NP

saw (girl) DT NNagirl

Figure 3: Lexicalized CFG tree for WSJ parsing
head word, e.g., (saw), is put as a leftmost constituent

size parameter s and frequency parameter f were experimentally set at 6 and 10, respectively. As thedata set is very large, it is difficult to employ the experiments with more unrestricted parameters.
Table 1 lists results on test data for the Model2 of(Collins, 1999), for several previous studies, and forour best model. We achieve recall and precision of
89.3/%89.6% and 89.9%/90.1% for sentences with≤ 100 words and ≤ 40 words, respectively. The
method shows a 1.2% absolute improvement in average precision and recall (from 88.2% to 89.4% forsentences ≤ 100 words), a 10.1% relative reduction in error. (Collins, 2000) achieved 89.6%/89.9%
recall and precision for the same datasets (sentences ≤ 100 words) using boosting and manually constructed features. (Charniak, 2000) extends
PCFG and achieves similar performance to (Collins,
2000). The tree kernel method of (Collins andDuffy, 2002) uses the all-subtrees representation andachieves 88.6%/88.9% recall and precision, which
are slightly worse than the results obtained with ourmodel. (Bod, 2001) also uses the all-subtrees representation with a very different parameter estimation
method, and realizes 90.06%/90.08% recall and precision for sentences of ≤ 40 words.
5.2 Shallow Parsing
We used the same data set as the CoNLL 2000
shared task (Tjong Kim Sang and Buchholz, 2000).
Sections 15-18 of the Penn Treebank were used astraining data, and section 20 was used as test data.
As a baseline model, we used a shallow parser
based on Conditional Random Fields (CRFs), very
similar to that described in (Sha and Pereira, 2003).
CRFs have shown remarkable results in a numberof tagging and chunking tasks in NLP. n-best outputs were obtained by a combination of forward

Table 1: Results for section 23 of the WSJ Treebank
LR/LP = labeled recall/precision. CBs is the average numberof cross brackets per sentence. 0 CBs, and 2CBs are the percentage of sentences with 0 or ≤ 2 crossing brackets, respectively. COL99 = Model 2 of (Collins, 1999). CH00 = (Charniak, 2000), CO00=(Collins, 2000). CO02=(Collins and Duffy,2002).

Viterbi search and backward A* search. Note that
this search algorithm yields optimal n-best resultsin terms of the CRFs score. Each sentence has at
most 20 distinct parses. The log probability fromthe CRFs shallow parser was incorporated into thereranking. Following (Collins, 2000), the training
set was split into 5 portions, and the CRFs shallow
parser was trained on 4/5 of the data, then used to
decode the remaining 1/5. The outputs of the baseparser, which consist of base phrases, were converted into right-branching trees by assuming that
two adjacent base phrases are in a parent-child relationship. Figure 4 shows an example of the tree
for shallow parsing task. We also put two virtual
nodes, left/right boundaries, to capture local transitions. The size parameter s and frequency parameterf were experimentally set at 6 and 5, respectively.
Table 2 lists results on test data for the baseline
CRFs parser, for several previous studies, and forour best model. Our model achieves a 94.12 Fmeasure, and outperforms the baseline CRFs parser
and the SVMs parser (Kudo and Matsumoto, 2001).
(Zhang et al., 2002) reported a higher F-measurewith a generalized winnow using additional linguistic features. The accuracy of our model is very similar to that of (Zhang et al., 2002) without using such
additional features. Table 3 shows the results for ourbest model per chunk type.

TOP
ADJP
ADVP
CONJP
INTJ
LST
NP
PP
PRT
SBAR
VP
Overall

NP
PRP
(L)

I

VP
(R)

VBD
(L) saw (R)

NP
DT
(L)

NN

EOS

a girl (R)Figure 4: Tree representation for shallow parsing
Represented in a right-branching tree with two virtual nodes

MODEL
Fβ=1
CRFs (baseline)
93.76
8 SVMs-voting (Kudo and Matsumoto, 2001) 93.91
RW + linguistic features (Zhang et al., 2002) 94.17
Boosting (our model)
94.12
Table 2: Results of shallow parsing
Fβ=1 is the harmonic mean of precision and recall.

6

Discussion

6.1 Interpretablity and Efficiency
The numbers of active (non-zero) features selectedby boosting are around 8,000 and 3,000 in the WSJ
parsing and shallow parsing, respectively. Althoughalmost all the subtrees are used as feature candidates, boosting selects a small and highly relevant
subset of features. When we explicitly enumerate
the subtrees used in tree kernel, the number of active features might amount to millions or more. Notethat the accuracies under such sparse feature spaces
are still comparable to those obtained with tree kernel. This result supports our first intuition that we
do not always need all the subtrees to construct theparameters.
The sparse feature representations are useful inpractice as they allow us to analyze what kinds offeatures are relevant. Table 4 shows examples ofactive features along with their weights wk . In theshallow parsing tasks, subordinate phrases (SBAR)
are difficult to analyze without seeing long dependencies. Subordinate phrases usually precede a sentence (NP and VP). However, Markov-based shallow parsers, such as MEMM or CRFs, cannot capture such a long dependency. Our model automatically selects useful subtrees to obtain an improvement on subordinate phrases. It is interesting that thePrecision
80.35%
83.88%
42.86%
50.00%
0.00%
94.45%
97.24%
76.92%
90.70%
93.95%
94.11%

Recall73.41%
82.33%
66.67%
50.00%
0.00%
94.36%
98.07%
75.47%
89.35%
94.72%
94.13%

Fβ=1

76.72
83.10
52.17
50.00
0.00
94.41
97.65
76.19
90.02
94.33
94.12

Table 3: Results of shallow parsing per chunk type
tree (SBAR(IN(for))(NP(VP(TO)))) has a large positive
weight, while the tree (SBAR((IN(for))(NP(O)))) has anegative weight. The improvement on subordinatephrases is considerable. We achieve 19% of the relative error reduction for subordinate phrase (from87.68 to 90.02 in F-measure)
The testing speed of our model is much higher
than that of other models. The speeds of reranking for WSJ parsing and shallow parsing are 0.055
sec./sent. and 0.042 sec./sent. respectively, which
are fast enough for real applications ¶ .
6.2 Relationship to previous work
Tree kernel uses the all-subtrees representation not
explicitly but implicitly by reducing the problem tothe calculation of the inner-products of two trees.
The implicit calculation yields a practical computation in training. However, in testing, kernel methods require a number of kernel evaluations, which
are too heavy to allow us to realize real applications.
Moreover, tree kernel needs to incorporate a decay
factor to downweight the contribution of larger subtrees. It is non-trivial to set the optimal decay factor
as the accuracies are sensitive to its selection.
Similar to our model, data oriented parsing (DOP)
methods (Bod, 1998) deal with the all-subtrees representation explicitly. Since the exact computation of scores for DOP is NP-complete, several approximations are employed to perform an efficientparsing. The critical difference between our modeland DOP is that our model leads to an extremely
sparse solution and automatically eliminates redundant subtrees. With the DOP methods, (Bod, 2001)
also employs constraints (e.g., depth of subtrees) to¶

We ran these tests on a Linux PC with Pentium 4 3.2 Ghz.

WSJ parsingw
active trees that contain the word “in”
0.3864 (VP(NP(NNS(plants)))(PP(in)))
0.3326 (VP(VP(PP)(PP(in)))(VP))
0.2196 (NP(VP(VP(PP)(PP(in)))))
0.1748 (S(NP(NNP))(PP(in)(NP)))...
...
-1.1217 (PP(in)(NP(NP(effect))))-1.1634 (VP(yield)(PP(PP))(PP(in)))-1.3574 (NP(PP(in)(NP(NN(way)))))-1.8030 (NP(PP(in)(NP(trading)(JJ))))
shallow parsingw
active trees that contain the phrase “SBAR”
1.4500 (SBAR(IN(for))(NP(VP(TO))))
0.6177 (VP(SBAR(NP(VBD)))
0.6173 (SBAR(NP(VP(“))))
0.5644 (VP(SBAR(NP(VP(JJ)))))..
..
-0.9034 (SBAR(IN(for))(NP(O)))-0.9181 (SBAR(NP(O)))-1.0695 (ADVP(NP(SBAR(NP(VP)))))-1.1699 (SBAR(NP(NN)(NP)))
Table 4: Examples of active features (subtrees)
All trees are represented in S-expression. In the shallow parsing
task, O is a special phrase that means “out of chunk”.

select relevant subtrees and achieves the best resultsfor WSJ parsing. However, these techniques are notbased on the regularization framework focused on
this paper and do not always eliminate all the redundant subtrees. Even using the methods of (Bod,2001), millions of subtrees are still exploited, whichleads to inefficiency in real problems.

7

Conclusions

In this paper, we presented a new application of
boosting for parse reranking, in which all subtrees
are potentially used as distinct features. Although
this set-up greatly increases the feature space, thel1 -norm regularization performed by boosting selects a compact and relevant feature set. Our model
achieved a comparable or even better accuracy thankernel methods even with an extremely small number of features (subtrees).

References
Kenji Abe, Shinji Kawasoe, Tatsuya Asai, Hiroki Arimura, andSetsuo Arikawa. 2002. Optimized substructure discovery
for semi-structured data. In Proc. of PKDD, pages 1–14.
Rens Bod. 1998. Beyond Grammar: An Experience Based Theory of Language. CSLI Publications/Cambridge University
Press.

Rens Bod. 2001. What is the minimal set of fragments that
achieves maximal parse accuracy? In Proc. of ACL, pages
66–73.
Eugene Charniak. 2000. A maximum-entropy-inspired parser.
In Proc. of NAACL, pages 132–139.
Michael Collins and Nigel Duffy. 2002. New ranking algorithms for parsing and tagging: Kernels over discrete structures, and the voted perceptron. In Proc. of ACL.
Michael Collins. 1999. Head-Driven Statistical Models for
Natural Language Parsing. Ph.D. thesis, University ofPennsylvania.
Michael Collins. 2000. Discriminative reranking for natural
language parsing. In Proc. of ICML, pages 175–182.
Michael Collins. 2002. Ranking algorithms for named-entity
extraction: Boosting and the voted perceptron. In Proc. of
ACL, pages 489–496.
Yoav Freund, Raj D. Iyer, Robert E. Schapire, and Yoram
Singer. 2003. An efficient boosting algorithm for combining
preferences. Journal of Machine Learning Research, 4:933–
969.
Taku Kudo and Yuji Matsumoto. 2001. Chunking with support
vector machines. In Proc. of NAACL, pages 192–199.
Taku Kudo and Yuji Matsumoto. 2004. A boosting algorithm for classification of semi-structured text. In Proc. of
EMNLP, pages 301–308.
Simon Perkins, Kevin Lacker, and James Thiler. 2003. Grafting: Fast, incremental feature selection by gradient descentin function space. Journal of Machine Learning Research,
3:1333–1356.
Gunnar. Rätsch. 2001. Robust Boosting via Convex Optimization. Ph.D. thesis, Department of Computer Science, University of Potsdam.
Robert E. Schapire, Yoav Freund, Peter Bartlett, and Wee Sun
Lee. 1997. Boosting the margin: a new explanation for theeffectiveness of voting methods. In Proc. of ICML, pages
322–330.
Fei Sha and Fernando Pereira. 2003. Shallow parsing withconditional random fields. In Proc. of HLT-NAACL, pages
213–220.
Erik F. Tjong Kim Sang and Sabine Buchholz. 2000. Introduction to the CoNLL-2000 Shared Task: Chunking. In Proc.
of CoNLL-2000 and LLL-2000, pages 127–132.
Vladimir N. Vapnik. 1998. Statistical Learning Theory. WileyInterscience.
Guizhen Yang. 2004. The complexity of mining maximal frequent itemsets and maximal frequent patterns. In Proc. of
SIGKDD.
Mohammed Zaki. 2002. Efficiently mining frequent trees in aforest. In Proc. of SIGKDD, pages 71–80.
Tong Zhang, Fred Damerau, and David Johnson. 2002. Text
chunking based on a generalization of winnow. Journal of
Machine Learning Research, 2:615–637.