Japanese Dependency Structure Analysis
Based on Support Vector Machines
Taku Kudo and Yuji Matsumoto
Graduate School of Information Science,
Nara Institute of Science and Technology{taku-ku, matsu}@is.aist-nara.ac.jp

Abstract
This paper presents a method of Japanese
dependency structure analysis based on Support Vector Machines (SVMs). Conventional
parsing techniques based on Machine Learning framework, such as Decision Trees andMaximum Entropy Models, have difficulty
in selecting useful features as well as finding appropriate combination of selected features. On the other hand, it is well-known
that SVMs achieve high generalization performance even with input data of very highdimensional feature space. Furthermore, byintroducing the Kernel principle, SVMs can
carry out the training in high-dimensional
spaces with a smaller computational cost independent of their dimensionality. We apply
SVMs to Japanese dependency structure identification problem. Experimental results on
Kyoto University corpus show that our system achieves the accuracy of 89.09% even withsmall training data (7958 sentences).

1

Introduction

Dependency structure analysis has been recognized as a basic technique in Japanese
sentence analysis, and a number of studies have been proposed for years. Japanese
dependency structure is usually defined interms of the relationship between phrasal
units called ’bunsetsu’ segments (hereafter“chunks”). Generally, dependency structure
analysis consists of two steps. In the firststep, dependency matrix is constructed, inwhich each element corresponds to a pair ofchunks and represents the probability of a dependency relation between them. The second
step is to find the optimal combination of dependencies to form the entire sentence.
In previous approaches, these probabilites
of dependencies are given by manually constructed rules.
However, rule-based approaches have problems in coverage and con-sistency, since there are a number of featuresthat affect the accuracy of the final results,
and these features usually relate to one another.
On the other hand, as large-scale tagged
corpora have become available these days,
a number of statistical parsing techniques
which estimate the dependency probabilities
using such tagged corpora have been developed(Collins, 1996; Fujio and Matsumoto,1998). These approaches have overcome thesystems based on the rule-based approaches.
Decision Trees(Haruno et al., 1998) and Maximum Entropy models(Ratnaparkhi, 1997;
Uchimoto et al., 1999; Charniak, 2000) havebeen applied to dependency or syntactic structure analysis. However, these models require
an appropriate feature selection in order toachieve a high performance. In addition, acquisition of an efficient combination of features is difficult in these models.
In recent years, new statistical learningtechniques such as Support Vector Machines(SVMs) (Cortes and Vapnik, 1995; Vapnik, 1998) and Boosting(Freund and Schapire,1996) are proposed. These techniques take astrategy that maximize the margin between
critical examples and the separating hyperplane. In particular, compared with otherconventional statistical learning algorithms,
SVMs achieve high generalization even withtraining data of a very high dimension. Furthermore, by optimizing the Kernel function,
SVMs can handle non-linear feature spaces,
and carry out the training with considering
combinations of more than one feature.
Thanks to such predominant nature, SVMs
deliver state-of-the-art performance in realworld applications such as recognition ofhand-written letters, or of three dimensional
images. In the field of natural language processing, SVMs are also applied to text categorization, and are reported to have achievedhigh accuracy without falling into over-fitting
even with a large number of words taken as thefeatures (Joachims, 1998; Taira and Haruno,1999).
In this paper, we propose an applicationof SVMs to Japanese dependency structure
analysis. We use the features that have beenstudied in conventional statistical dependency
analysis with a little modification on them.

2

Support Vector Machines

2.1 Optimal Hyperplane
Let us define the training data which belong
either to positive or negative class as follows.
(x1 , y1 ), . . . , (xi , yi ), . . . , (xl , yl )xi ∈ Rn , yi ∈ {+1, −1}
xi is a feature vector of i-th sample, which isrepresented by an n dimensional vector (xi =(f1 , . . . , fn ) ∈ Rn ). yi is a scalar value thatspecifies the class (positive(+1) or negative(1) class) of i-th data. Formally, we can define
the pattern recognition problem as a learningand building process of the decision function
f : Rn → {±1}.
In basic SVMs framework, we try to separate the positive and negative examples in the
training data by a linear hyperplane writtenas:(w · x) + b = 0

w ∈ Rn , b ∈ R.

(1)

It is supposed that the farther the positive
and negative examples are separated by thediscrimination function, the more accurately
we could separate unseen test examples withhigh generalization performance. Let us consider two hyperplanes called separating hyperplanes:(w · xi ) + b ≥ 1(w · xi ) + b ≤ −1

if (yi = 1) (2)if (yi = −1). (3)(i = 1, . . . , l).

|w · xi + b|.
kwk

Thus, the margin between two separating hyperplanes can be written as:
min d(w, b; xi ) +xi ;yi =1

min d(w, b; xi )xi ;yi =−1

To maximize this margin, we should minimize
kwk. In other words, this problem becomes
equivalent to solving the following optimization problem:
Minimize :L(w) = 12 kwk2
Subject to : yi [(w · xi ) + b] ≥ 1 (i = 1, . . . , l).
Furthermore, this optimization problem canbe rewritten into the dual form problem: Find
the Lagrange multipliers αi ≥ 0(i = 1, . . . , l)so that:Maximize:l
1 X
αi αj yi yj (xi · xj )L(α) =
αi −2 i,j=1
i=1
l
X

(5)

Subject to:αi ≥ 0,lX

αi yi = 0(i = 1, . . . , l)i=1

In this dual form problem, xi with non-zero αiis called a Support Vector. For the Support
Vectors, w and b can thus be expressed asfollowsw=X

αi yi xib = w · xi − yi .

i;xi ∈SV s

The elements of the set SV s are the Support
Vectors that lie on the separating hyperplanes.
Finally, the decision function f : Rn → {±1}can be written as:

f (x) = sgn X

αi yi (xi · x) + b(6)= sgn (w · x + b) .
(4)

Distance from the separating hyperplane tothe point xi can be written as:d(w, b; xi ) =mini;xi ∈SV s(2) (3) can be written in one formula as:yi [(w · xi ) + b] ≥ 1|w · xi + b|
|w · xi + b|
+ min
xi ;yi =1
xi ;yi =−1
kwk
kwk
2
=
.
kwk
=

2.2 Soft Margin
In the case where we cannot separate training examples linearly, “Soft Margin” method
forgives some classification errors that may becaused by some noise in the training examples.
First, we introduce non-negative slack variables, and (2),(3) are rewritten as:(w · xi ) + b ≥ 1 − ξi(w · xi ) + b ≥ −1 + ξiif (yi = 1)
if (yi = −1).

In this case, we minimize the following value
instead of 12 kwk2 .
lX1
kwk2 + C
ξi
2
i=1

(7)

The first term in (7) specifies the size of margin and the second term evaluates how far the
training data are away from the optimal separating hyperplane. C is the parameter thatdefines the balance of two quantities. If wemake C larger, the more classification errors
are neglected.
Though we omit the details here, minimization of (7) is reduced to the problem to minimize the objective function (5) under the following constraints.
0 ≤ αi ≤ C,lX

αi yi = 0(i = 1, . . . , l)i=1

Usually, the value of C is estimated experimentally.
2.3 Kernel Function
In general classification problems, there arecases in which it is unable to separate thetraining data linearly. In such cases, the training data could be separated linearly by expanding all combinations of features as newones, and projecting them onto a higherdimensional space. However, such a naive approach requires enormous computational overhead.
Let us consider the case where we project
the training data x onto a higher-dimensional
space by using projection function Φ 1 . As
we pay attention to the objective function (5)and the decision function (6), these functions
depend only on the dot products of the input training vectors. If we could calculate thedot products from x1 and x2 directly without
considering the vectors Φ(x1 ) and Φ(x2 ) projected onto the higher-dimensional space, we
can reduce the computational complexity considerably. Namely, we can reduce the computational overhead if we could find the function
K that satisfies:Φ(x1 ) · Φ(x2 ) = K(x1 , x2 ).

(8)

On the other hand, since we do not need
Φ itself for actual learning and classification,
1

In general, Φ(x) is a mapping into Hilbert space.

all we have to do is to prove the existence ofΦ that satisfies (8) provided the function K is
selected properly. It is known that (8) holds if
and only if the function K satisfies the Mercer
condition (Vapnik, 1998).
In this way, instead of projecting the training data onto the high-dimensional space, we
can decrease the computational overhead byreplacing the dot products, which is calculated
in optimization and classification steps, withthe function K.
Such a function K is called a Kernel function. Among the many kinds of Kernel functions available, we will focus on the d-th polynomial kernel:
K(x1 , x2 ) = (x1 · x2 + 1)d .

(9)

Use of d-th polynomial kernel function allows
us to build an optimal separating hyperplane
which takes into account all combination offeatures up to d.
Using a Kernel function, we can rewrite thedecision function as:

y = sgn X

αi yi K(xi , x) + b .

(10)i;xi ∈SV s

3

Dependency Analysis using
SVMs

3.1

The Probability Model

This section describes a general formulation of
the probability model and parsing techniques
for Japanese statistical dependency analysis.
First of all, we let a sequence ofchunks be {b1 , b2 . . . , bm } by B, andthe sequence dependency pattern be{Dep(1), Dep(2), . . . , Dep(m − 1)} by D,
where Dep(i) = j means that the chunk bi
depends on (modifies) the chunk bj .
In this framework, we suppose that the dependency sequence D satisfies the following
constraints.
1. Except for the rightmost one, each chunkdepends on (modifies) exactly one of the
chunks appearing to the right.
2. Dependencies do not cross each other.
Statistical dependency structure analysis
is defined as a searching problem for the
dependency pattern D that maximizes theconditional probability P (D|B) of the in-put sequence under the above-mentioned constraints.
Dbest = argmax P (D|B)
D

If we assume that the dependency probabilities are mutually independent, P (D|B) could
be rewritten as:
P (D|B) =m−1
YP (Dep(i) = j | fij )

3.3

i=1
n

fij = {f1 , . . . , fn } ∈ R .
P (Dep(i) = j | fij ) represents the probability
that bi depends on (modifies) bj . fij is an n dimensional feature vector that represents various kinds of linguistic features related withthe chunks bi and bj .
We obtain Dbest taking into all the combination of these probabilities. Generally, the optimal solution Dbest can be identified by using
bottom-up algorithm such as CYK algorithm.
Sekine suggests an efficient parsing techniquefor Japanese sentences that parses from theend of a sentence(Sekine et al., 2000). We apply Sekine’s technique in our experiments.
3.2

Training with SVMs

In order to use SVMs for dependency analysis,
we need to prepare positive and negative examples since SVMs is a binary classifier. We
adopt a simple and effective method for our
purpose: Out of all combination of two chunks
in the training data, we take a pair of chunks
that are in a dependency relation as a positive
example, and two chunks that appear in a sentence but are not in a dependency relation asa negative example.
[(fij , yij ) = {(f12 , y12 ), (f23 , y23 ),1≤i≤m−1i+1≤j≤m. . . , (fm−1 m , ym−1 m )}fij = {f1 , . . . , fn } ∈ Rn
yij ∈ {Depend(+1), Not−Depend(−1)}
Then, we define the dependency probability
P (Dep(i) = j | f 0 ij ):P (Dep(i) = j | f 0 ij ) =tanh 

X

k,l;fkl ∈SV s0(11) shows that the distance between test dataf 0 ij and the separating hyperplane is put into
the sigmoid function, assuming it represents
the probability value of the dependency relation.
We adopt this method in our experiment
to transform the distance measure obtainedin SVMs into a probability function and analyze dependency structure with a frameworkof conventional probability model 2 .

αkl ykl K(fkl , f ij ) + b (11)

Static and Dynamic Features

Features that are supposed to be effectivein Japanese dependency analysis are: headwords and their parts-of-speech, particles andinflection forms of the words that appear
at the end of chunks, distance between two
chunks, existence of punctuation marks. As
those are solely defined by the pair of chunks,
we refer to them as static features.
Japanese dependency relations are heavily
constrained by such static features since theinflection forms and postpositional particles
constrain the dependency relation. However,when a sentence is long and there are morethan one possible dependents, static features,by themselves cannot determine the correct
dependency. Let us look at the following example.

?
watashi-ha kono-hon-wo
I-top,
this book-acc,motteiru
have,josei-wolady-acc,

sagasiteiru
be looking for

In this example, “kono-hon-wo(this bookacc)” may modify either of “motteiru(have)”or “sagasiteiru(be looking for)” and cannot
be determined only with the static features.
However, “josei-wo (lady-acc)” can modify
the only the verb “sagasiteiru,”. Knowing
such information is quite useful for resolving syntactic ambiguity, since two accusative
noun phrses hardly modify the same verb. It
is possible to use such information if we add
new features related to other modifiers. In
the above case, the chunk “sagasiteiru” canreceive a new feature of accusative modification (by “josei-wo”) during the parsing process, which precludes the chunk “kono-honwo” from modifying “sagasiteiru” since there
is a strict constraint about double-accusative
2

Experimentally, it is shown that the sigmoid function gives a good approximation of probability function from the decision function of SVMs(Platt, 1999).

modification that will be learned from training examples. We decided to take into consideration all such modification information byusing functional words or inflection forms ofmodifiers.
Using such information about modifiers in
the training phase has no difficulty since they
are clearly available in a tree-bank. On theother hand, they are not known in the parsing
phase of the test data. This problem can beeasily solved if we adopt a bottom-up parsing
algorithm and attach the modification information dynamically to the newly constructedphrases (the chunks that become the head of
the phrases). As we describe later we apply abeam search for parsing, and it is possible tokeep several intermediate solutions while suppressing the combinatorial explosion.
We refer to the features that are added incrementally during the parsing process as dynamic features.

4

Experiments and Discussion

4.1 Experiments Setting
We use Kyoto University text corpus (Version 2.0) consisting of articles of Mainichi
newspaper annotated with dependency structure(Kurohashi and Nagao, 1997). 7,958 sentences from the articles on January 1st to January 7th are used for the training data, and1,246 sentences from the articles on January
9th are used for the test data. For the kernel
function, we used the polynomial function (9).
We set the soft margin parameter C to be 1.
The feature set used in the experiments areshown in Table 1. The static features are basically taken from Uchimoto’s list(Uchimoto
et al., 1999) with little modification. In Table
1, ‘Head’ means the rightmost content word
in a chunk whose part-of-speech is not a functional category. ‘Type’ means the rightmost
functional word or the inflectional form of therightmost predicate if there is no functional
word in the chunk. The static features include the information on existence of brackets, question marks and punctuation marks
etc. Besides, there are features that show
the relative relation of two chunks, such as
distance, and existence of brackets, quotation
marks and punctuation marks between them.
For dynamic features, we selected functional words or inflection forms of the rightmost predicates in the chunks that appear between two chunks and depend on the modifiee. Considering data sparseness problem, we

StaticFeaturesDynamic
FeaturesHead(surface-form, POS,
POS-subcategory,inflection-type,inflection-form),Type(surface-form, POS,
Left/
Right
POS-subcategory,
Chunks inflection-type,inflection-form),
brackets,
quotation-marks,
punctuation-marks,
position in sentence(beginning, end)
distance(1,2-5,6-),case-particles,
Betweenbrackets,
Chunksquotation-marks,
punctuation-marks
Form of functional words or inflection that modifies the rightchunk

Table 1: Features used in experiments

apply a simple filtering based on the part-ofspeech of functional words: We use the lexical
form if the word’s POS is particle, adverb, adnominal or conjunction. We use the inflection
form if the word has inflection. We use the
POS tags for others.
4.2

Results of Experiments

Table 2 shows the result of parsing accuracy
under the condition k = 5 (beam width), andd = 3 (dimension of the polynomial functions
used for the kernel function).
This table shows two types of dependency
accuracy, A and B. The training data size ismeasured by the number of sentences. The accuracy A means the accuracy of the entire dependency relations. Since Japanese is a headfinal language, the second chunk from the endof a sentence always modifies the last chunk.
The accuracy B is calculated by excluding thisdependency relation. Hereafter, we use the accuracy A, if it is not explicitly specified, since
this measure is usually used in other literature.
4.3

Effects of Dynamic Features

Table3 shows the accuracy when only staticfeatures are used. Generally, the results with

Training
data
1172
1917
3032
4318
5540
6756
7958

Dependency Accuracy

A
86.52%
87.21%
87.67%
88.35%
88.66%
88.77%
89.09%

B
84.86%
85.62%
86.14%
86.91%
87.26%
87.38%
87.74%

Sentence
Accuracy
39.31%
40.06%
42.94%
44.15%
45.20%
45.36%
46.17%

Dimensionof Kernel
12
34

Dependency
Accuracy
N/A
86.87%
87.67%
87.72%

Sentence
Accuracy
N/A
40.60%
42.94%
42.78%

Table 4: Dimension vs. Accuracy (3032 sentences, k = 5)

Table 2: Result (d = 3, k = 5)
Training
data
1172
1917
3032
4318
5540
6756
7958

Dependency Accuracy

A
86.12%
86.81%
87.62%
88.33%
88.40%
88.55%
88.77%

B
84.41%
85.18%
86.10%
86.89%
86.96%
87.13%
87.38%

Sentence
Accuracy
38.50%
39.80%
42.45%
44.47%
43.66%
45.04%
45.04%

Table 3: Result without dynamic features(d = 3, k = 5)dynamic feature set is better than the results
without them. The results with dynamic features constantly outperform that with staticfeatures only. In most of cases, the improvements is significant. In the experiments, we
restrict the features only from the chunks thatappear between two chunks being in consideration, however, dynamic features could be also
taken from the chunks that appear not between the two chunks. For example, we could
also take into consideration the chunk that is
modified by the right chunk, or the chunks
89.5’dynamic’’static’89

Dependency Accuracy (%)

88.5

88

87.5

87

86.5

86
1000

2000

3000

4000

5000

6000

7000

Number of Training Data (sentences)

Figure 1: Training Data vs Accuracy

8000

that modify the left chunk. We leave experiment in such a setting for the future work.
4.4

Training data vs. Accuracy

Figure 1 shows the relationship between thesize of the training data and the parsing accuracy. This figure shows the accuracy of withand without the dynamic features.
The parser achieves 86.52% accuracy fortest data even with small training data (1172sentences). This is due to a good characteristic of SVMs to cope with the data sparseness problem. Furthermore, it achieves almost
100% accuracy for the training data, showingthat the training data are completely separated by appropriate combination of features.
Generally, selecting those specific features of
the training data tends to cause overfitting,and accuracy for test data may fall. However,the SVMs method achieve a high accuracy not
only on the training data but also on the test
data. We claim that this is due to the highgeneralization ability of SVMs. In addition,observing at the learning curve, further improvement will be possible if we increase thesize of the training data.
4.5

Kernel Function vs. Accuracy

Table 4 shows the relationship between the dimension of the kernel function and the parsing
accuracy under the condition k = 5.
As a result, the case of d = 4 gives the best
accuracy. We could not carry out the training
in realistic time for the case of d = 1.
This result supports our intuition that weneed a combination of at least two features.
In other words, it will be hard to confirm adependency relation with only the features ofthe modifier or the modfiee. It is natural thata dependency relation is decided by at least
the information from both of two chunks. In
addition, further improvement has been possible by considering combinations of three ormore features.

Beam
Width
1
3
5
7
10
15

Dependency
Accuracy
88.66%
88.74%
88.77%
88.76%
88.67%
88.65%

Sentence
Accuracy
45.76%
45.20%
45.36%
45.36%
45.28%
45.28%

Table 5: Beam width vs. Accuracy (6756 sentences, d = 3)

viding all training data (7958 sentences) by
4, the final dependency score is given by aweighted average of each scores. This simple
voting approach is shown to achieve the accuracy of 88.66%, which is nearly the sameaccuracy achieved 5540 training sentences.
In this experiment, we simply give an equal
weight to each classifier. However, if we optimized the voting weight more carefully, thefurther improvements would be achieved (Inuiand Inui, 2000).
4.8

4.6 Beam width vs. Accuracy
Sekine (Sekine et al., 2000) gives an interesting report about the relationship between the
beam width and the parsing accuracy. Generally, high parsing accuracy is expected whena large beam width is employed in the dependency structure analysis. However, the resultis against our intuition. They report that abeam width between 3 and 10 gives the best
parsing accuracy, and parsing accuracy falls
down with a width larger than 10. This result
suggests that Japanese dependency structures
may consist of a series of local optimization
processes.
We evaluate the relationship between the
beam width and the parsing accuracy. Table 5shows their relationships under the conditiond = 3, along with the changes of the beamwidth from k = 1 to 15. The best parsing
accuracy is achieved at k = 5 and the best
sentence accuracy is achieved at k = 5 andk = 7.
We have to consider how we should set thebeam width that gives the best parsing accuracy. We believe that the beam width thatgives the best parsing accuracy is related not
only with the length of the sentence, but alsowith the lexical entries and parts-of-speechthat comprise the chunks.
4.7 Committee based approach
Instead of learning a single classifier using all
training data, we can make n classifiers dividing all training data by n, and the final
result is decided by their voting. This approach would reduce computational overhead.
The use of multi-processing computer would
help to reduce their training time considerably
since all individual training can be carried out
in parallel.
To investigate the effectiveness of thismethod, we perform a simple experiment: Di-

Comparison with Related Work

Uchimoto (Uchimoto et al., 1999) and Sekine(Sekine et al., 2000) report that using Kyoto
University Corpus for their training and testing, they achieve around 87.2% accuracy bybuilding statistical model based on Maximum
Entropy framework. For the training data, weused exactly the same data that they used inorder to make a fair comparison. In our experiments, the accuracy of 89.09% is achieved
using same training data. Our model outperforms Uchimoto’s model as far as the accuracies are compared.
Although Uchimoto suggests that the importance of considering combination of features, in ME framework we must expand
these combination by introducing new feature set. Uchimoto heuristically selects “effective” combination of features. However, sucha manual selection does not always cover all
relevant combinations that are important in
the determination of dependency relation.
We believe that our model is better thanothers from the viewpoints of coverage andconsistency, since our model learns the combination of features without increasing the computational complexity. If we want to reconsider them, all we have to do is just to change
the Kernel function. The computational complexity depends on the number of support vectors not on the dimension of the Kernel function.
4.9

Future Work

The simplest and most effective way to achieve
better accuracy is to increase the training
data. However, the proposed method thatuses all candidates that form dependency relation requires a great amount of time to compute the separating hyperplane as the size ofthe training data increases. The experiments
given in this paper have actually taken longtraining time 3 .
To handle large size of training data, wehave to select only the related portion of examples that are effective for the analysis. This
will reduce the training overhead as well as
the analysis time. The committee-based approach discussed section 4.7 is one method of
coping with this problem. For future research,
to reduce the computational overhead, we will
work on methods for sample selection as follows:• Introduction of constraints on nondependency
Some pairs of chunks need not consider
since there is no possibility of dependency between them from grammaticalconstraints. Such pairs of chunks are notnecessary to use as negative examples inthe training phase. For example, a chunkwithin quotation marks may not modify
a chunk that locates outside of the quotation marks. Of course, we have to becareful in introducing such constraints,
and they should be learned from existing
corpus.
• Integration with other simple models
Suppose that a computationally light andmoderately accuracy learning model isobtainable (there are actually such systems based on probabilistic parsing models). We can use the system to output
some redundant parsing results and use
only those results for the positive andnegative examples. This is another way
to reduce the size of training data.
• Error-driven data selection
We can start with a small size of training data with a small size of feature
set. Then, by analyzing held-out training
data and selecting the features that affectthe parsing accuracy. This kind of gradual increase of training data and feature
set will be another method for reducing
the computational overhead.

5

SummaryThis paper proposes Japanese dependency
analysis based on Support Vector Machines.
Through the experiments with Japanesebracketed corpus, the proposed method
achieves a high accuracy even with a small
3With AlphaServer 8400 (617Mhz), it took 15 days
to train with 7958 sentences.

training data and outperforms existing methods based on Maximum Entropy Models. The
result shows that Japanese dependency analysis can be effectively performed by use of
SVMs due to its good generalization and nonoverfitting characteristics.

References
Eugene Charniak. 2000. A maximum-entropyinspired parser. In Processing of the NAACL
2000, pages 132–139.
Michael Collins. 1996. A new statistical parser
based on bigram lexical dependencies. In Proceedings of the ACL ’96, pages 184–191.
C. Cortes and Vladimir N. Vapnik. 1995. Support
Vector Networks. Machine Learning, 20:273–
297.
Y. Freund and Schapire. 1996. Experiments witha new Boosting algoritm. In 13th International
Conference on Machine Learning.
Masakazu Fujio and Yuji Matsumoto. 1998.
Japanese Dependency Structure Analysis basedon Lexicalized Statistics. In Proceedings of
EMNLP ’98, pages 87–96.
Msahiko Haruno, Satoshi Shirai, and Yoshifumi
Ooyama. 1998. Using Decision Trees to Construct a Partial Parser. In Proceedings of the
COLING ’98, pages 505–511.
Takashi Inui and Kentaro Inui. 2000. Committebased Decision Making in Probabilistic Partial
Parsing. In Proceedings of the COLING 2000,
pages 348–354.
Thorsten Joachims. 1998. Text Categorization
with Support Vector Machines: Learning with
Many Relevant Features. In European Conference on Machine Learning (ECML).
Sadao Kurohashi and Makoto Nagao. 1997. Kyoto
University text corpus project. In Proceedingsof the ANLP, Japan, pages 115–118.
John C. Platt. 1999. Probabilistic Outputs for
Support Vector Machines and Comparisons toRegularized Likelihood Methods. In Advancesin Large Margin Classifiers. MIT Press.
Adwait Ratnaparkhi. 1997. A Liner ObservedTime Statistical Parser Based on Maximum Entropy Models. In Proceedings of EMNLP ’97.
Satoshi Sekine, Kiyotaka Uchimoto, and Hitoshi
Isahara. 2000. Backward Beam Search Algorithm for Dependency Analysis of Japanese. In
Proceedings of the COLING 2000, pages 754–
760.
Hirotoshi Taira and Masahiko Haruno. 1999. Feature Selection in SVM Text Categorization. In
AAAI-99.
Kiyotaka Uchimoto, Satoshi Sekine, and Hitoshi
Isahara. 1999. Japanese Dependency Structure
Analysis Based on Maximum Entropy Models.
In Proceedings of the EACL, pages 196–203.
Vladimir N. Vapnik. 1998. Statistical Learning
Theory. Wiley-Interscience.