SVMを用いた 統計的日本語係り受け解析

Support Vector Machine
による日本語係り受け解析
奈良先端科学技術大学院大学
情報科学研究科 自然言語処理学講座
工藤 拓
松本裕治
係り受け解析



日本語の統語解析の基本技術の1つ
二文節間の係りやすさを数値化した行列
を作成し,文全体を最適化する係り受け関
係を導出
人手による手法から、解析済みコーパスか
ら統計的に求める手法へ
統計的係り受け解析
B  {B1 ,, Bm }

入力文節列

係り先パターン列
D  {Dep(1),, Dep(m  1)}
Dbest  arg max P( D | B)
D
文節 i, j の言語的特徴を示すn次元素性ベクトル
F  {f12 ,, fij ,, fm1m} fij  { f1 ,, f n } Rn


係り関係がすべて独立だと仮定
m 1
P( D | B)   P( Dep(i)  j | fij )
i 1
従来手法の問題点(1)

慎重な素性選択が必要


多くの素性を使用すると過学習してしまう
最適な素性集合の選択は試行錯誤や人手に
頼っている
従来手法の問題点(2)

各素性の組み合わせ(共起,依存関係)を効率よく
学習できない


例
共起選択の方法はさまざま,人手により発見的に選択
細かな依存関係を見ると…
データスパースネス,計算量増加,過学習
P( Dep(i)  j | lex(i), pos(i), lex( j ), pos( j ))
?  P(| lex(i))P(| lex( j ))P(| pos(i))P(| pos( j ))
?  P(| lex(i), lex( j ))P(| pos(i), pos( j ))
?  P(| lex(i), lex( j ), pos( j ))P(| pos(i), lex( j ), pos( j ))...
Support Vector Machine(1)



V.Vapnik 95
入力素性数に依存しない汎化能力を持ち
過学習しにくい
計算量をほとんど変えることなく,素性どう
しの組み合わせ(共起,依存関係)を含め
た学習が可能
SVM(2)
線形2値(正例,負例)分類器,Euclid空間上の平面で分離
(x1 y1 ),(xi yi ),, (xl yl ) xi  R n yi {1,1}
( w  x)  b  0 w  R n , b  R
正例,負例,その他(マージン領域),の3つの領域に分割
(w  xi )  b  1 if yi  1
(w  xi )  b  1 if yi  1
yi [(w  xi )  b]  1
SVM(3)
yi  1
d
d
d
d
w  x  b  1
yi  1
w  x  b  1
wx b  0
マージンdが最大となる識別平面
| w  xi  b |
| w  xi  b |
2
 min

xi yi  1
xi yi  1
|| w ||
|| w ||
|| w ||
d  min
マージン d を最大にするためには ||w|| を最小にすればよい
SVM(4)
以下の制約付き多項式の最適化問題に帰着
最小化: L(w)  || w ||2
制約条件: yi [(w  xi )  b]  1
Lagrange乗数 αを導入して双対問題に変換
l
1 l
最大化: L( )   i   i j yi y j (xi  x j )
2 i , j 1
i 1 l
制約条件:  i  0,  i yi  0
i 1
最終的な識別関数
 l

f (x)  sgn(w  x  b)  sgn  i yi (xi  x)  b
 i 1

Kernel関数(1)
線形分離できない場合
各素性をの組み合わせを展開し,より高次元の素性ベクトル
空間に射影すれば線形分離しやすくなる
1 2 3 4 5 6 7
Inputspace x R n

1 2 4 5 6 7
1,2 1,3 1,4 1,5 1,6 1,7 2,3 2,4 2,5
Featurespace
(x)  R n' n'  n
Kernel関数(2)
l
学習:
1 l
L( )   i   i j yi y j (x
i (xxi j)) (x j ))
2 i , j 1
i 1
 ll


識別関数: ff ((x
x)) 
 sgn
sgn

ii yyii((
xi(xxi ) 
b(x))  b

ii11


学習、識別は素性ベクトルの内積のみに依存した形
Φを経由せずに簡単な演算で直接内積を計算できれば
計算量を大幅に減らすことが可能
K (xi , x j )  (xi )  (x j )
K: Kernel関数
Kernel関数(3)
例 K (xi , x j )  (xi  x j 1)d
d次のPolynomial関数
d  2 x i  (a1 , a2 )  R 2 , x j  (b1 , b2 )  R 2
K (x i , x j )  (x i  x j  1) 2  (a1b1  a2b2  1) 2
 a12b12  a22b22  2a1b1  2a2b2  2a1a2b1b2  1
 (a12 , a22 , 2a1 , 2a2 , 2a1a2 ,1)  (b12 , b22 , 2b1 , 2b2 , 2b1b2 ,1)T
  : ( z1 , z 2 )  ( z12 , z 22 , 2 z1 , 2 z 2 , 2 z1 z 2 ,1)
2次元を6次元の空間へ写像,組み合わせの項も追加される
d次のPolynomial関数はd個までの組み合わせを含めた学習
SVM(まとめ)

入力素性数に依存しない汎化能力を持ち
過学習しにくい


計算量をほとんど変えることなく素性どうし
の組み合わせを含めた学習が可能


マージン最大化
Kernel関数
d個までの素性の組み合わせを考慮しなが
らその中で汎化能力を最大にする戦略

Smoothingの効果が期待できる
SVMによる係り受け解析(1)

正例,負例の与え方
学習データ中の
全係り受け候補
係った事例
→ 正例
係らなかった事例 → 負例
SVMによる係り受け解析(2)

係り受け確率


P( Dep(i)  j | f 'ij )  tanh kl ykl K (f kl  f 'ij )  b
k ,l


1
0  tanh(x)  1 (Sigmoid関数)
tanh(x) 
1  exp( x)



厳密には確率値ではない,距離を確率値に正規化,
Sigmoid関数は確率へのよい近似を与えることが実験的
に示されている (J.Platt 99)
従来からある確率モデルの枠組で解析
関根99の文末からビームサーチを行う解析手法を採用
静的素性と動的素性

静的素性


2文節の主辞の語彙,品詞,2文節間距離など
文節まとめあげの段階で決定される
?
私は |この本を | 持っている| 女性を | 探している。

動的素性


「探している」の素性として「女性を」を追加
二重 を格 の可能性が取り除かれる
係り関係そのもの,解析しながら動的に追加
動的素性も含めてビームサーチ
実験環境,設定(1)

京都大学テキストコーパスVersion2.0の一部






学習データ 1月1日-8日 7958文
テストデータ 1月9日 1246文
内元98と同じ学習データ,テストデータ
Kernel関数は,Polynomial関数,次元数 d=3
Beam幅 k=5
評価方法

係り受け正解率


文末から2番目の評価含める (A) デフォルト, 含めない(B)
文正解率
実験環境,設定(2)
静的 係り元/
素性 係り先
文節
主辞(見出し,品詞,品詞細分類,
活用,活用形)
語形(見出し,品詞,品詞細分類,
活用,活用形)
括弧,句読点,文節位置
文節間
距離(1,2-5,6),助詞,括弧,
句読点
動的 2文節間にある文節で,後ろの文節に
素性 係る文節の語形見出し
文節正解率(A/B)(%)
実験結果(1)(d=3,k=5)
89.5
89
88.5
88
87.5
87
86.5
86
85.5
85
84.5
84
学習文数
88.66
88.34
88.77 89.09
87.67
87.21
86.52
86.9
87.26
87.38
87.74
86.14
85.62
84.86
1172
1917
3032
4318
5540
6756
7956
実験結果(2)(d=3,k=5)
文正解率(%)
46
45.2
45.36
46.17
44.07
44
42.94
42
40
39.31
40.06
38
学習文数
1172
1917
3032
4318
5540
6756
7956
動的素性の効果(d=3,k=5)
文節正解率(A) (%)
89.5
89
88.66
89.09
88.34
88.5
88
88.33
87.67
87.5
87
88.77
88.55
87.62
87.21
86.52
88.4
88.77
86.81
86.5
86
学習文数
86.12
1172
1917
3032
4318
5540
6756
7956
Kernel関数と解析精度
文節正解率(A)(%)
88
87.67
87.72
87.5
87
86.87
86.5
2
次元数
3
(3032文,k=5)
4
ビーム幅と解析精度
文節正解率(A)(%)
88.7
88.66
88.64
88.6
88.63
88.59
88.55
88.56
88.55
88.5
1
3
Beam幅
5
7
10
15
(5540文,d=3)
25
関連研究との比較

内元98との比較




最大エントロピー法に基づくモデル
87.2%の精度 (本手法は89.1%)
素性の組み合わせ(共起,依存関係)の重要性を
指摘しているが,組み合わせは,人手により発見
的に 選択,有効な組み合わせを網羅できない
本手法はKernel関数の変更のみ,
網羅性, 一貫性という意味で優位
今後の課題
全係り受け関係を用いるため,多くの計算量が必要
すべての候補から分類に必要な事例を選択
学習の効率化,解析の高速化



明らかに係らない制約を(人手により)導入
他の計算コストの少ないモデルとの融合
誤り駆動型による素性選択
まとめ



7958文という非常に少量のデータにもかかわ
らず,89.1%の高い精度を示す
SVMの持つ,高次元の入力に対して過学習し
にくいという性質を裏付ける結果
係り受け解析は各素性の組み合わせ(共起,
依存関係)が重要,SVMはKern el関数を使う
ことで効率性,網羅性,一貫性で優位