Document

June 10, 2003
静岡大学情報学部
Support Vector Machineを用いた
自然言語解析
松本裕治
Graduate School of Information Science
Nara Institute of Science and Technology
(NAIST)
概要
機械学習による言語解析

Support Vector Machinesの紹介
日本語の係り受け解析


擬似確率に基づく構文解析
Cascaded chunking モデル
形態素解析（品詞タグ付け）

修正学習モデル
自然言語処理のために必要な機械学習法の
性質
1. 大規模な属性（基本情報）を扱うことができるこ
と

個々の単語を属性として扱う必要が生じる
2. 効果的なスムージング (例：単語と品詞の頻度
/出現確率の間のスムージング)


単語の出現頻度の偏り
データ過疎問題(Data sparseness problem)
3. 基本属性の組み合わせ属性を扱うことが必要
Support Vector Machinesの概要
２値分類，ユークリッド・ベクトル空間内の線形分離:
事例は、ベクトル空間内の点とその所属クラス
(正例: +1, 負例:-1)よりなる
(x1 y1 ), (xi yi ), , (xl yl ) xi  R n yi {1,1}
( w  x)  b  0 w  R n , b  R
正例と負例の分離を、分離（超）平面から例までの距離
(margin)が最大になるようにして行う:
(w  x i )  b  1 if yi  1
(w  x i )  b  1 if yi  1
yi [( w  xi )  b]  1
分離超平面
yi  1
d
d
yi  1
d
d
w  x  b  1
w  x  b  1 w  x  b  0
マージンdが最大の平面
| w  xi  b |
| w  xi  b |
2
d  min
 min

xi yi  1
x
y


1
i i
|| w ||
|| w ||
|| w ||
最大マージンdを得るためには ||w|| を最小化すればよい
最適化問題
最大マージンの平面は次の最適化問題を解くのと同じ:
最小化：
条件：
L(w)  || w ||2
yi [( w  xi )  b]  1
ラクランジュ定数 α を導入し、双対問題に変換する:
l
1 l
最大化： L( )   i   i j yi y j (x i  x j )
2 i , j 1
i 1
条件：
 i  0,
最終的な分離関数:
l

i 1
i
yi  0
 l

f (x)  sgn( w  x  b)  sgn   i yi (x i  x)  b
 i 1

Kernel関数の導入
線形分離が難しい問題
元の属性に基づくベクトル空間をより高次元な属性をもつ
高次元空間に写像する
1 2 3 4 5 6 7
Input space 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
Feature space
 ( x)  R n ' n'  n
Kernel関数を用いる場合の学習
l
学習：
1 l
L( )   i   i j yi y j (
xi (xxi )j ) (x j ))
2 i , j 1
i 1
 ll


分離関数: ff ((x
x)) 
 sgn
sgn

iiyyii((
x i(xxi ) b(x))  b

ii11


学習も分類も属性空間の内積にのみ依存する
Φ で写像された空間における内積が実際にΦを計算すること
なく求める方法があれば、計算による手間を激減させることが
できる:
K (x i , x j )  (x i )  (x j )
K : Kernel function
例: 多項式Kernel
例: K (xi , x j )  (xi  x j  1) d
d次元の多項式Kernel
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)
この例は、２次の空間を６次の空間に写像することと等しい
(ｄ次元の多項式カーネルは、元の空間の属性のｄ個の組み
合わせ属性を考慮することに相当する）
日本語の係り受け解析
文節の係り受け関係の基づく文の構文解析
二種類の制約:


各文節は（最後の文節を除いて）、常に右側の
文節に係る
文節係り受けは互いに交差しない
日本語の係り受け解析の例
入力文
私は彼女と京都に行きます
形態素解析と文節まとめ上げ
私は / 彼女と / 京都に / 行きます
係り受け解析
私は / 彼女と / 京都に / 行きます
単純なモデル (確率モデル)
Input
私は
1
1.
/ 彼女と
/ 京都に
2
/ 行きます
3
4
係り受け確率を求めて以下
のような行列を作る。
(学習モデルは確率を求め
るものなら何でもよい)
被修飾文節
2. 最大確率を与える木構造を CYK あるい
は Chart 法を用いて求める
修 1
飾
文 2
節 3
Output
2
3
4
0.1
0.2
0.7
0.2
0.8
1.0
係りうけ行列
私は
1
/ 彼女と
2
/ 京都に
3
/ 行きます
4
Model 2: Cascaded Chunking Model
各文節が右側の文節に係ることができる
かどうかを決定的に決めながら、文節のま
とめあげを行う
学習データは、実際に係りうけ解析を実行
する過程を模倣することによって得られる
例: 学習の過程
解析済みの学習文
彼は1
彼女の2
??
彼は
彼は111
D
O
O
彼女の
彼女の22
O
D
属性（２つの文節の内容）と
タグ (D or O) のペアが
SVMのための学習事例とし
て蓄積される
温かい3
?
??
真心に4
?
?
感動した。5
???
温かい3 真心に44 感動した。
感動した。55
D
D
D
学習
データ
蓄積された学習事例
によるSVM学習
SVMs
例: 解析の実行
入力文
彼は1
彼女の2
??
彼は
彼は11111
彼は
彼は
D
O
O
彼女の22
O
D
学習過程で得られた
SVMによって係り受け
関係が決定される
温かい3
?
??
真心に4
感動した。5
?
???
?
感動した。5555
温かい3 真心に44 感動した。
感動した。
D
D
D
SVMs
学習に用いた属性情報
Modify or not?
B
A
この本を3
彼の1 友人は2
His
friend-top
this book-acc
修飾文節
C
持っている4 女性を5 探している6
have
lady-acc
被修飾文節
 静的な属性
 修飾文節/被修飾文節
 中心語/機能語:
表層形, 品詞, 品詞細分類,
活用型, 活用形, 括弧の有無, 引用符の有無, 句読点の有無,…
 文節間属性:
距離, 格助詞の存在情報, 括弧の存在情報,
引用符, 句読点
 動的な属性 [Kudo, Matsumoto 2000]
 A,B: 機能語の情報を被修飾文節に与える
 C:
中心語の情報を修飾文節に与える
be looking for
実験の設定
京都大学コーパス 2.0/3.0

標準データセット
 学習データ: 7,958 文 / 評価データ: 1,246 文
 過去の研究と同一 [Uchimoto et al. 98], [Kudo, Matsumoto 00]

大規模データセット
 38,383 文による２分割交差検定
Kernel関数: ３次の多項式カーネル
評価尺度


係り受け関係の精度
文正解精度
実験結果
データセット
標準
大規模
モデル
Cascaded
Chunking
Probabilistic
Cascaded
Chunking
Probabilistic
係り受け精度
(%)
89.29
89.09
90.45
N/A
文正解精度
(%)
47.53
46.17
53.16
N/A
学習データの
文数
7,956
7,956
19,191
19,191
110,355
459,105
251,254
1,074,316
8
336
48
N/A
0.5
2.1
0.7
N/A
学習事例数
学習時間
(時間)
解析時間
(秒/文)
機械学習に基づく他の日本語係り受け
解析法との比較
学習モデル
学習データ
(文数)
精度
(%)
Fujio & Matsumoto Word cooccurence
[1998]
+ smoothing
EDR corpus(190,000)
86.7
Haruno [1999]
Decision tree +
Boosting
EDR coupus(50,000)
85.0
Uchimoto [1999]
MaxEnt +
probabilities
Kyoto-U corpus(7,956)
87.9
Kanayama [2000]
MaxEnt+constraint EDR corpus(192,778)
Grammar + prob.
Kudo &
Matsumoto [2000]
SVM +
probabilities
Kyoto-U corpus(7,956)
89.1
Kudo &
Matsumoto [2002]
SVM + cascaded
chunking
Kyoto-U corpus(7,956)
89.3
Kyoto-U corpus(19,191)
90.5
88.6
II. ＳＶＭを利用した修正学習法
と品詞タグ付け問題への応用
学習アルゴリズムの能力と計算量のト
レード・オフ
学習モデルの能力と計算量
学習モデル
HMM
SVM
計算量
小
大
能力
低
高
制限
大規模な属性空大規模データに
間の扱いが困難対する計算量
修正学習法の考え方
問題の大部分は能力が低いが効率のよいモデ
ルで処理が可能 (例えば、HMMによる品詞タグ
付け精度: 95%)
処理のすべてを、能力が高いが効率の悪いモデ
ルで行うのは無駄が多い
２つのモデルの混合:
• 効率よいモデルでデータの大半を処理
• 能力の高いモデルで前者の処理の誤り箇所を推
定して修正する
修正学習法による形態素解析
•HMMモデルによる解析結果の誤りを指摘する分類器を
構成
•効率がよいが能力の低い学習モデルと効率に難点があ
るが能力の高い学習モデルとの組み合わせの一方法
低能力
高効率
Example
Stochastic
Model
高能力
低効率
Binary
Classifier
Revise
Result
修正学習法の例
学習
実行
Stochastic
Model
Class Rank
Training
example
x
A
B
C
D
E
Class Rank
4 Training Data
1 B:x–X
5 E:x–X
D:x–O
3
2
Label: O (Positive)
X (Negative)
Test
example
z
Binary
Classifiers
ABCDE
A
B
C
D
E
4
5
2 O
1 X
3
英語の品詞タグ付け
コーパス:
Penn Treebank WSJ (50 POS tags)
 訓練データ: 41,000 文
 テストデータ: 12,000 文
統計モデル:
ICOPOST T3 (Second order HMMs) [Schröder,2001]
修正モデル:
SVMs (2nd order polynomial kernel & linear kernel)
英語のPOS tagging（結果）
System
学習事例数
T3 /
Original
T3 / RL(2次 1,027,840
多項式)
T3 / RL
1,027,840
(線形)
Full SVM
49,999,200
学習
実行
精度
時間
時間
0.004 0.0076 96.59%
16
0.18 96.98%
2
0.011 96.94%
625
4.7 97.11%
(時間)
(秒/文)
日本語形態素解析
コーパス:
RWCPコーパス (89 POS tags)
 訓練データ: 34,000 文
 テストデータ: 3,800 文
統計モデル:


HMM
茶筌 (可変長HMM)
修正学習モデル:
SVMs (2nd order polynomial kernel)
日本語形態素解析（結果）
システム
HMMs / Original
HMMs / 修正学習
茶筌 / Original
茶筌 / 修正学習
分かち書き精度分かち書き+
品詞付け
98.42%
95.96%
99.16%
98.23%
99.13%
97.74%
99.28%
98.32%
(F-measure)
まとめ
機械学習に基づく自然言語解析


確率モデル（隠れマルコフモデル、ＨＭＭ）
Support Vector Machines
品詞タグ付け問題


ＨＭＭに基づく手法（茶筌）
修正学習モデルの提案
日本語係り受け解析


擬似確率による手法
Cascaded chunking モデル（南瓜）

Download Report