EMNLP/VLC 2000

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

Dependency Structure Analysis(1/3)• Basic technique in Japanese sentence analysis– Analysis of relationship between phrasal units called“bunsetsu” (“chunks”).
– Each chunk modifies one of the right-side chunks– Dependencies do not cross each other• 1. Building dependency matrix– Each element represents the probability of a dependency2. Finding the optimal combination of dependencies from thematrix• Rule based approached → Corpus based statistical approachDependency Structure Analysis(2/3)

Problems of Conventional Frameworks(1/2)• Must select “effective” features carefully– Trade off between over-fitting and over-generalization– The selection usually depends on heuristics

Problems of Conventional Frameworks(2/2)• Difficulty in acquisition of an efficient combination of features– “Effective” selection of combinations usually decided byheuristics– The more specfic combinations we select, the largercomputational overhead is required

Overview of the Talk
• Brief introduction to Support Vector Machines– How can SVMs cope with the problems of conventionalframeworks?
• How do we apply SVMs to dependency analysis?
• Experiments and Evaluation• SummarySupport Vector Machines (1/4)• V.Vapnik 1995
• Two strong properties– High generalization performance independent of givenfeature dimension– Training with combinations (dependencies, co-occurrence)of more than one features without increasing computationaloverheadSupport Vector Machines (2/4)• Separating positive and negative (binary) examples by
Linear Hyperplane: (w · x + b, w, x ∈ Rn , b ∈ R)
• Finding optimal hyperplane (parameter w, b) with Maximal
Margin Strategy

Support Vector Machines (3/4)
Two dashed lines (separating hyperplanes):
w · x + b = ±1w ∈ Rn , b ∈ R

Margin:2|w · xi + b − 1| |w · xi + b + 1|
+=
d=kwk
kwk
kwk
Maximize Margin d ↔ Minimize kwk

Support Vector Machines (4/4)
Solving the following Optimizaion Problems:
L(w) = 12 kwk2

Minimize :Subject to : yi [(w · xi ) + b] ≥ 1 (i = 1, . . . , l)Rewritten into dual form:
Minimize :Subject to :PlPl
1L(α) = i=1 αi − 2 i,j=1 αi αj yi yj (xi · xj )Plαi ≥ 0,(i = 1, . . . , l)i=1 αi yi = 0

Decision Function:lX
f (x) = sgn(w · x + b) = sgn(αi yi (xi · x) + b)i=1

Kernel Function (1/3)
The case we cannot separate the training data linearly⇓Projecting training data onto a higher-dimensional space
Φ(x) : {x1 , x2 } 7→ {x1 , x2 , x1 x2 }

Kernel Function (2/3)

Training :Classify :PlPl
1L(α) = i=1 αi − 2 i,j=1 αi αj yi yj (Φ(xi ) · Φ(xj ))Pl
y = sgn( i=1 αi yi (Φ(xi ) · Φ(x)) + b)
⇓SVMs depend only on the evaluation of dot products
Need not to project training data if we can find the K that satisfies:Φ(x1 ) · Φ(x2 ) = K(x1 , x2 ) K : Kernel F unction
Can reduce the computational overhead considerablyKernel Function (3/3)
2nd Polynomial Function
K(xi , xj ) = (xi · xj + 1)2 = Φ(xi ) · Φ(xj ) x ∈ R2 = {x1 , x2 }x21√
 2x1 x2  x2 

Φ(x) =  √ 2 
2x  √ 1 
2x2 1• 2 dimensional feature is projected onto 6 dimensional space• Training with combination (co-occurance) of features• The computational overhead dose not increaseSupport Vector Machines (Summary)• High generalization performance independent of given featuredimension– Maximal Margin Strategy• Training with combinations (dependencies, co-occurence) of
more than one features without increasing computationaloverhead– Use of Kernel function⇓
Effects of smoothing between all given features

How do we apply SVMs? (1/2)
What do we set as Positive and Negative examples?
⇓
All candidates of two chunks which have ...
dependency relation → Positive examples
no dependency relation → Negative examples

How do we apply SVMs? (2/2)• Dependency Probability
XP (Dep(i) = j|fij ) = tanh(αkl ykl K(fkl · f 0 ij ) + b)k,l1tanh(x) =(Sigmoid f untion)
1 + exp(−x)• This conversion dose not give us a true probability,Normalizing distance (−∞ − +∞) to probability value (0 − 1)
• We easily apply conventional probability-based parsing
techniques• We adopted backward beam search method introduced by[Sekine 2000]

Static Features vs. Dynamic Features(1/2)• Static Features– Features (Lexicon, POS, distance, postion ...) of two chunks– Solely defined by the pair of chunks

Static Features vs. Dynamic Features(2/2)• Dynamic Features– Dependency relation themselves, added dynamicaly– Applying beam search to reduce the computational overheadExperiments(1/2)• Kyoto University Text Corpus Version 2.0– Training data: Articles on Jan. 1st - 7th (7958 sentences)– Test data: Articles on Jan. 9th (1246 sentences)∗ Same training and test data as [Uchimoto 98]– Kernel function: 3rd polynomial (d=3)– Beam width: k=5• Evaluation method– Dependency accuracy– Sentence accuracy

Experiments(2/2)

StaticFeatures

Left/
RightChunks

Head/Type(surfaceform, POS, POS-subcategory, inflectiontype, inflection-form), brackets, quotationmarks, punctuation-marks, position in sentence (beginning, end)

distance(1,2-5,6-),
Betweencase-particles,
brackets,
Chunksquotation-marks, punctuation-marks
DynamicFeatures

Form of functional words or inflection thatmodifies the right chunk• The static features are basically taken from Uchimoto’s 98 list
• No cut-off (frequency filter.. etc) for selecting features

Results• Degree of Kernel Function: d = 3• Beam-Width: k = 5# of training sentences

Dependency Acc.

Sentence Acc.

117286.52%

39.31%

1917

87.21%

40.06%

3032

87.67%

42.94%

4318

88.34%

44.07%

5540

88.66%

45.20%

6756

88.77%

45.36%

7958

89.09 %

46.17%

Effects of Dynamic Features• Degree of Kernel Function: d = 3• Beam-Width: k = 5# of training sentences

Dynamic

without Dynamic

1172

86.52%

86.12%

1917

87.21%

86.81%

3032

87.67%

87.62%

4318

88.34%

87.33%

5540

88.66%

88.40%

6756

88.77%

88.55%

7958

89.09%

88.77%

Kernel Function vs. Accuracy
3,032 sentences, Beam Width: K=5
Dimension(d)Dependency Acc.

Sentence Acc.

1N/A

N/A

286.87%40.60%

387.67%42.94%

487.72%42.78%• d-th polynomial kernel →training with all combinations of features up to d
• This results support our institution —The consideration of combination (dependency, co-occurance)of features is quite important for Japanese dependency analysis

Comparison with Related Work
Uchimoto 98• Based on Maximal Entropy Model• 87.2% (our method achieves 89.1%)• He also pointed out the importance of considering combination(dependency, co-occurance), however these combinations are
selected heuristically
These manual selection dose not always cover all effectivecombinations• The Kernel Principle allow us to build a separating hyperplaneconsidering the any combinations of features without increasing
the computational overheadFuture Works
Great amount of computational overhead is required since our
proposed method uses all candidates of dependency relations⇓
Selecting only the effective portion of examples• Introduction of (hand-crafted) constraint on non-dependency• Integration with other simple models• Error-driven data selection

Summary• By applying SVMs, we can achieve a high accuracy even with asmall training data (7958 sentences)• We can show the high generalization performance and highfeature selection abilities of SVMs
• The consideration of combinations (dependency, co-occurance)of features is important for Japanese dependency analysis.
Use of Kernel functions enables feature selection more
efficiently than conventional frameworks