Use of SVM for NLP

July 5, 2004
at 慶応大学
機械学習に基づく
自然言語処理システム
松本裕治
奈良先端科学技術大学院大学
情報科学研究科
(NAIST)
概要
機械学習に基づく言語処理システム






日本語形態素解析システム「茶筌」
Support Vector Machinesの紹介
修正学習モデル：形態素解析への応用
日本語の係り受け解析システム「南瓜」
未知語同定（中国語）
中国語の係り受け解析
日本語形態素解析システム「茶筌」
ー開発の履歴ー
システム
アルゴリズム
辞書検索方式・辞書サイズ
Juman 1.0
接続コスト
(1989～1993) （人手作成）
B-tree ・５万語～１２万語
Juman 2.0
接続コスト
(1994～1996) （人手作成）
NDBM(ハッシュデータベース）・
１２万語
茶筌 1.0
接続コスト
(1997～1998) （人手作成）
パトリシア木・
１２万語～２３万語
茶筌 2.0
可変長n-gram
(1998～2002) （統計学習）
パトリシア木 / Suffix array・
２３万語
茶筌 2.3
(2003～ )
ダブル配列によるTRIE・
２３万語
可変長n-gram /
品詞グルーピング
統計情報に基づく形態素解析
品詞付与された解析済みコーパスから、単語の出現のしやすさ、
品詞(単語)のつながりやすさを確率値として求める。
文を構成する単語の出現確率が直前のn-1語にのみ依存すると仮
定して言語の文をモデル化する
n=3 のとき，tri-gram model, n=2のとき，bi-gram modelとい
う。
「茶筌」は可変長のマルコフモデルを実装しており、 bi-gram
と tri-gram の混合を用いている。
文として単語列が与えられた際に最大の出現確率をもつ品詞列
を求めることが目的
そのために、単語の出現確率や品詞の連接確率の積が最大にな
るような品詞列を求める
形態素解析の例
4200
3200
くるま
700
名詞
２５００
3150
文頭
2700
1300
で
格助詞
０
4500
で
くる
動詞
カ変（基本）
４５０
2700
1000
1400
助動詞
（連用）
０
5700
4550
くる
まで
動詞
五段（基本）
３０００
1400
格助詞
０
7100
形態素解析の例
4200
3200
くるま
700
名詞
２５００
3150
文頭
2700
1300
1400
800
4500
1500
助動詞
（連用）
０
5700
4550
くる
まで
動詞
五段（基本）
３０００
1400
6900
格助詞
０
で
くる
動詞
カ変（基本）
４５０
2700
1000
で
格助詞
０
800
まつ
動詞
7900
五段（基本）
１９００
7250
形態素解析の例
4200
3200
くるま
700
名詞
２５００
3150
文頭
2700
1300
1400
5700
800
まつ
4500
1500
動詞
五段（基本）
１９００
助動詞
（連用） 1200 600
０
800
4550
くる
まで
動詞
五段（基本）
３０００
格助詞
０
1400
6900
格助詞
０
で
くる
動詞
カ変（基本）
４５０
2700
1000
で
600
7300
まつ
名詞 8200
２５００
7650
形態素解析の例
4200
3200
くるま
700
名詞
２５００
3150
文頭
2700
1300
1400
5700
800
まつ
4500
1500
動詞
五段（基本）
１９００
助動詞
（連用） 1200 600
０
800
4550
くる
まで
動詞
五段（基本）
３０００
格助詞
０
1400
6900
格助詞
０
で
くる
動詞
カ変（基本）
４５０
2700
1000
で
600
500
7400
文末
7300
まつ
名詞
２５００
960
8260
形態素解析の例
4200
3200
くるま
700
名詞
２５００
3150
文頭
2700
1300
1400
5700
800
まつ
4500
1500
動詞
五段（基本）
１９００
助動詞
（連用） 1200 600
０
800
4550
くる
まで
動詞
五段（基本）
３０００
格助詞
０
1400
6900
格助詞
０
で
くる
動詞
カ変（基本）
４５０
2700
1000
で
600
500
7400
文末
7300
まつ
名詞
２５００
960
形態素解析の例
4200
3200
くるま
700
名詞
２５００
3150
文頭
2700
1300
1400
5700
800
まつ
4500
1500
動詞
五段（基本）
１９００
助動詞
（連用） 1200 600
０
800
4550
くる
まで
動詞
五段（基本）
３０００
格助詞
０
1400
6900
格助詞
０
で
くる
動詞
カ変（基本）
４５０
2700
1000
で
600
500
7400
文末
7300
まつ
名詞
２５００
960
自然言語処理の２大問題
曖昧性 (Ambiguity)
I.
II.
言語処理のあらゆるレベルで曖昧性が生じるため、
一意の解釈を得ることが困難
曖昧性を解消するために必要な知識が何である
かを知ることが困難
頑健性 (Robustness, Coverage)
I.
II.
III.
文法設計者/言語処理システム設計者が事前に予
測することが困難な新しい言語現象が常に存在す
る
単純に規則を列挙するだけでは、すべての現象を
カバーすることができない
未知の言語現象に対応するだけの柔軟性を言語
処理システムが備えている必要がある
言語処理のための対極的アプローチ
1.統計（機械学習）に基づく言語処理


統計的手法、機械学習の進歩による
頑健性 / 曖昧性解消の能力
2.制約に基づく文法理論（語彙化文法）


詳細な文法制約の語彙レベルにおける記述
制約違反を許容しない脆弱性
 制約違反の緩和を実現したい→曖昧性の増加
統計的言語処理の頑健性と曖昧性解消力を活かしすため、
これを処理のためのコントロール情報として制約文法による
解析を行う
言語解析における言語知識とコーパスの利用（統
計学習と制約処理の融合）
言語解析
コーパスに基づく
言語解析
規則に基づく
言語解析
統計・学習
コーパス構築
文法知識・語彙知識
の獲得
言語知識
（文法、語彙）
データ
コーパス
統計学習と
制約処理の融合
自然言語処理のために必要な機械学習
法の性質
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 ×
x i )  b]  1
分離超平面
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
d  min
 min

xi yi  1
x
y


1
i
i
|| w ||
|| w ||
|| w ||
最大マージンdを得るためには ||w|| を最小化すればよい
最適化問題
最大マージンの平面は次の最適化問題を解くのと同じ:
最小化：
条件：
L(w)  || w ||
yi [(w  xi )  b]  1
2
ラクランジュ定数 α を導入し、双対問題に変換する:
l
1 l
最大化： L( )   i   i j yi y j (xi  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 (xi  x)  b
 i 1

Kernel関数の導入
線形分離が難しい問題
元の属性に基づくベクトル空間をより高次元な属性をもつ
高次元空間に写像する
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関数を用いる場合の学習
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 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)
この例は、２次の空間を６次の空間に写像することと等しい
(ｄ次元の多項式カーネルは、元の空間の属性のｄ個の組み
合わせ属性を考慮することに相当する）
学習アルゴリズムの能力と計算量のト
レード・オフ
学習モデルの能力と計算量
学習モデル
確率モデル
SVM
計算量
小
大
能力
低
高
制限
大規模な素性空大規模データに
間の扱いが困難対する計算量
修正学習法[Nakagawa & Matsumoto 02]
問題の大部分は能力が低いが効率のよいモデ
ルで処理が可能 (例えば、確率モデルによる品
詞タグ付け精度: 95%)
処理のすべてを、能力が高いが効率の悪いモデ
ルで行うのは無駄が多い
２つのモデルの混合:
• 効率よいモデルでデータの大半を処理
• 能力の高いモデルで前者の処理の誤り箇所を推
定して修正する
修正学習法による形態素解析
•確率モデルによる解析結果の誤りを指摘する分類器を構
成
•効率がよいが能力の低い学習モデルと効率に難点があ
るが能力の高い学習モデルとの組み合わせの一方法
低能力
高効率
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 Markov model)
[Schröder,2001]
修正モデル:
SVM (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 文
確率モデル:


bi-gram Markov model
茶筌 (可変長Markov model)
修正学習モデル:
SVM (2nd order polynomial kernel)
日本語形態素解析（結果）
システム
bi-gram / Original
bi-gram / 修正学習
茶筌 / Original
茶筌 / 修正学習
分かち書き精度分かち書き+
品詞付け
98.42%
95.96%
99.16%
98.23%
99.13%
97.74%
99.28%
98.32%
(F-measure)
日本語の係り受け解析
文節の係り受け関係の基づく文の構文解析
二種類の制約:


各文節は（最後の文節を除いて）、常に右側の
文節に係る
文節係り受けは互いに交差しない
日本語の係り受け解析の例
入力文
私は彼女と京都に行きます
形態素解析と文節まとめ上げ
私は / 彼女と / 京都に / 行きます
係り受け解析
私は / 彼女と / 京都に / 行きます
単純なモデル (確率モデル)
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
日本語係り受け解析システム「南瓜」
（Cascaded Chunking Model）[Kudo & Matsumoto02]
各文節が右側の文節に係ることができる
かどうかを決定的に決めながら、文節のま
とめあげを行う
学習データは、実際に係りうけ解析を実行
する過程を模倣することによって得られる
例: 学習の過程
解析済みの学習文
彼は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
SVMでは何が学習されているか?
負事例
正事例
P1
P2
…
…
Pn
w1
分類すべき
データ
w2
sim
wn
S
事例とデータ間の
類似度
w’1
w’2
sim
w’m
N1
N2
…
…
Nm
分類の決定: (事例による重み付き投票)
W1×sim(P1,S)+W2×sim(P2,S)+...+Wn×sim(Pn,S)
- [W’1×sim(N1,S)+…+W’m×sim(Nm,S)]
アルゴリズムが学習するのは事例の重み
機械学習問題において設計すべき事項
何を決めなければならないか
1.
2.
類似度 “sim”: モデル (kernel function) と
素性集合の決定
事例の重み: ＳＶＭによって学習される。
多くの事例が０重みを得る。一部の事例
(support vectors)が分離関数を決める。
設計者が行うのは、よい素性集合と適切
なKernel関数の選定
未知語処理
未知語の問題



辞書に登録されていない単語
辞書にすべての単語が登録されていることは
ありえない (e.g., 地名、人名、組織名、専門
用語など)
日本語や中国語では未知語と他の単語の境
界を同定することが難しい
中国語（日本語）の未知語抽出
[Goh, Asahara & Matsumoto 03, 04]
1. 確率モデルによる形態素解析 (単語分
かち書きと品詞付与)
2. 文字列に分割 (文字素性付与)
3. ＳＶＭに基づくchunkingによる未知語抽
出
Chunking (基本句チャンキングの例)
He reckons the current account deficit will narrow to only 1.8 billion in September.
chunk tag annotation
He reckons the current account deficit will narrow to only 1.8 billion in September.
NP-B
VP-B
NP-B
NP-I
NP-I
phrase tag
NP-I VP-B VP-I PP-B NP-B NP-I NP-I PP-B
position tag
NP-B
B : 開始位置
I : チャンクの内部
Chunking の結果
He reckons the current account deficit will narrow to only 1.8 billion in September.
NP VP
NP
VP
PP
NP
PP
NP
Chunking (名詞句チャンキング)
He reckons the current account deficit will narrow to only 1.8 billion in September.
chunk tag annotation
He reckons the current account deficit will narrow to only 1.8 billion in September.
B
O
B
I
I
I
O
O
O B
I
I O
B
position tag
B : チャンクの開始位置
I : チャンクの内部
O : チャンクの外部
Chunkingの結果
He reckons the current account deficit will narrow to only 1.8 billion in September.
NP
NP
NP
NP
ステップ1: 分かち書き＋品詞付与
Input：由于长江泥沙的冲积，江海潮流、…
Because of the accumulation of mud from Changjiang, the current of river and sea, …
由于
长江
泥
沙
的
冲
积
，
江
海
潮流
、
c
ns
unk
nr
u
v
unk
w
nr
nr
n
w
確率モデルによ
る形態素解析の
出力
ステップ2: 文字毎の情報付与
Input：由于长江泥沙的冲积，江海潮流、…
由于
长江
泥
沙
的
冲
积
，
江
海
潮流
、
c
ns
unk
nr
u
v
unk
w
nr
nr
n
w
品詞タグ
由
于
长
江
泥
沙
的
冲
积
，
江
海
潮
流
、
c-B
c-E
ns-B
ns-E
unk-S
nr-S
u-S
v-S
unk-S
w-S
nr-S
nr-S
n-B
n-E
w-S
文字素性の付与
位置タグ
ステップ3: 未知語 chunking
Input：由于长江泥沙的冲积，江海潮流、…
由于
长江
泥
沙
的
冲
积
，
江
海
潮流
、
c
ns
unk
nr
u
v
unk
w
nr
nr
n
w
チャンキングに
使用される素性
由
于
长
江
泥
沙
的
冲
积
，
江
海
潮
流
、
c-B
c-E
ns-B
ns-E
unk-S
nr-S
u-S
v-S
unk-S
w-S
nr-S
nr-S
n-B
n-E
w-S
由
于
长
江
泥
沙
的
冲
积
，
江
海
潮
流
、
c-B
c-E
ns-B
ns-E
unk-S
nr-S
u-S
v-S
unk-S
w-S
nr-S
nr-S
n-B
n-E
w-S
O
O
O
O
?
ステップ3: 未知語 chunking
Input：由于长江泥沙的冲积，江海潮流、…
由于
长江
泥
沙
的
冲
积
，
江
海
潮流
、
c
ns
unk
nr
u
v
unk
w
nr
nr
n
w
チャンキングに
使用される素性
由
于
长
江
泥
沙
的
冲
积
，
江
海
潮
流
、
c-B
c-E
ns-B
ns-E
unk-S
nr-S
u-S
v-S
unk-S
w-S
nr-S
nr-S
n-B
n-E
w-S
由
于
长
江
泥
沙
的
冲
积
，
江
海
潮
流
、
c-B
c-E
ns-B
ns-E
unk-S
nr-S
u-S
v-S
unk-S
w-S
nr-S
nr-S
n-B
n-E
w-S
O
O
O
O
unk-B
?
ステップ3: 未知語 chunking
Input：由于长江泥沙的冲积，江海潮流、…
由于
长江
泥
沙
的
冲
积
，
江
海
潮流
、
c
ns
unk
nr
u
v
unk
w
nr
nr
n
w
SVMに基づくチャン
キングの結果
由
于
长
江
泥
沙
的
冲
积
，
江
海
潮
流
、
c-B
c-E
ns-B
ns-E
unk-S
nr-S
u-S
v-S
unk-S
w-S
nr-S
nr-S
n-B
n-E
w-S
由
于
长
江
泥
沙
的
冲
积
，
江
海
潮
流
、
c-B
c-E
ns-B
ns-E
unk-S
nr-S
u-S
v-S
unk-S
w-S
nr-S
nr-S
n-B
n-E
w-S
O
O
O
O
unk-B
unk-I
O
unk-B
unk-I
O
unk-B
unk-I
O
O
O
未知語抽出実験の結果
結果のＦ値
未知語全体
61.00
人名
86.78
組織名
70.40
中国語依存構造解析器
解析アルゴリズム(1/2)
SVMを用いた依存構造解析[Yamada 2003]
初期化：
T={(w1,p1),(w2,p2),…,(wn,pn)};
i=1; all_shift=true;
解析：
While |T| >= 1 do
if i==|T| then
if all_shift == true then break;
i=1; all_shift=true;
else
x = get_feature(T,i);
y = estimate_action(model, x);
construction(T,I,y);
if y != “SHIFT” then
all_shift = false
end;
end;
end;
解析アルゴリズム(1/2)
SVMを用いた依存構造解析[Yamada 2003]
初期化：
T={(w1,p1),(w2,p2),…,(wn,pn)};
i=1; all_shift=true;
解析：
鄭成功
Name
收復
Verb
臺灣
Noun
的
Prep.
偉大
Adj.
功業
Noun
While |T| >= 1 do
if i==|T| then
if all_shift == true then break;
i=1; all_shift=true;
初期化
else
入力文はトークン列
x = get_feature(T,i);
y = estimate_action(model, x);
トークンは単語と品詞から
construction(T,I,y);
なる
if y != “SHIFT” then
all_shift = false

i ：現在注目しているトークンの
end;
ID
end;

all_shift ：停止条件
end;
解析アルゴリズム(1/2)
SVMを用いた依存構造解析[Yamada 2003]
初期化：
前後５単語
T={(w1,p1),(w2,p2),…,(wn,pn)};
臺灣
的
偉大
BOS
nil
BOS
nil all_shift=true;
nil
nil
nil
鄭成功收復
i=1;
BOS
nil
BOS
nil
nil
nil
nil
Name Verb Noun Prep.
Adj.
解析：
While |T| >= 1 do
if i==|T| then
前後５単語の子
if all_shift == true then break;
i=1; all_shift=true;
素性展開：
else
x = get_feature(T,i);
前後5単語について
y = estimate_action(model, x);
 単語
construction(T,I,y);
if y != “SHIFT” then
 品詞
all_shift = false
 子の単語
end;
 子の品詞
end;
end;
功業
Noun
解析アルゴリズム(1/2)
SVMを用いた依存構造解析[Yamada 2003]
RIGHT
素性
初期化：
BOS 鄭成功
收復
T={(w1,p1),(w2,p2),…,(wn,pn)};
BOS
Name
Verb
i=1; all_shift=true;
解析：
BOS
BOS
BOS
BOS
鄭成功
Name
收復
Verb
臺灣
Noun
While |T| >= 1 do
nil
nil
nil
nil
nil
if i==|T| then
nil
nil
nil
nil
nil
if all_shift == true then break;
LEFT
i=1; all_shift=true;
BOS 鄭成功收復
else
係り先の同定
BOS
Name
Verb
x = get_feature(T,i);
y = estimate_action(model, x); 素性を基に以下の３つの
construction(T,I,y);
いづれかを選択
if y != “SHIFT” then
SHIFT
all_shift = false

RIGHT 右に係る
end;
收復
BOS 鄭成功

LEFT 左に係る
end;
BOS
Name
Verb
end;

SHIFT 今は係らない
決定はSVMによる
解析アルゴリズム(1/2)
SVMを用いた依存構造解析[Yamada 2003]
初期化：
T={(w1,p1),(w2,p2),…,(wn,pn)};
i=1; all_shift=true;
解析：
鄭成功
Name
While |T| >= 1 do
if i==|T| then
if all_shift == true then break;
i=1; all_shift=true;
else
x = get_feature(T,i);
y = estimate_action(model, x);
construction(T,I,y);
if y != “SHIFT” then
all_shift = false
end;
end;
end;
收復
Verb
臺灣
Noun
的
Prep.
偉大
Adj.
功業
Noun
左から右へと各単語
についてくりかえす
解析アルゴリズム(1/2)
SVMを用いた依存構造解析[Yamada 2003]
初期化：
T={(w1,p1),(w2,p2),…,(wn,pn)};
i=1; all_shift=true;
解析：
While |T| >= 1 do
if i==|T| then
if all_shift == true then break;
i=1; all_shift=true;
else
x = get_feature(T,i);
y = estimate_action(model, x);
construction(T,I,y);
if y != “SHIFT” then
all_shift = false
end;
end;
end;
收復
Verb
鄭成功
Name
臺灣
Noun
的
Prep.
功業
Noun
偉大
Adj.
最初から再度やりなおし
解析アルゴリズム(1/2)
SVMを用いた依存構造解析[Yamada 2003]
初期化：
T={(w1,p1),(w2,p2),…,(wn,pn)};
i=1; all_shift=true;
解析：
While |T| >= 1 do
if i==|T| then
if all_shift == true then break;
i=1; all_shift=true;
else
x = get_feature(T,i);
y = estimate_action(model, x);
construction(T,I,y);
if y != “SHIFT” then
all_shift = false
end;
end;
end;
收復
Verb
鄭成功
Name
臺灣
Noun
的
Prep.
功業
Noun
偉大
Adj.
最初から再度やりなおし
解析アルゴリズム(1/2)
SVMを用いた依存構造解析[Yamada 2003]
初期化：
T={(w1,p1),(w2,p2),…,(wn,pn)};
i=1; all_shift=true;
解析：
收復
Verb
While |T| >= 1 do
鄭成功臺灣
if i==|T| then
if all_shift == true then break; Name Noun
i=1; all_shift=true;
else
x = get_feature(T,i);
y = estimate_action(model, x);
construction(T,I,y);
if y != “SHIFT” then
all_shift = false
end;
end;
end;
的
Prep.
功業
Noun
偉大
Adj.
最初から再度やりなおし
解析アルゴリズム(1/2)
SVMを用いた依存構造解析[Yamada 2003]
初期化：
T={(w1,p1),(w2,p2),…,(wn,pn)};
i=1; all_shift=true;
收復
Verb
解析：
While |T| >= 1 do
if i==|T| then
if all_shift == true then break;
i=1; all_shift=true;
else
x = get_feature(T,i);
y = estimate_action(model, x);
construction(T,I,y);
if y != “SHIFT” then
all_shift = false
end;
end;
end;
鄭成功
Name
臺灣
Noun
的
Prep.
功業
Noun
偉大
Adj.
“SHIFT”ばかりになったら（係
り先がなくなったら）おわり
SVM実験
各カテゴリの訓練事例とテストデータ
Category
Example clause
(The anthology of Cheng Chou Yu)
Antholog
我不知如何回答
y
I don’t know how to answer it
(Textbooks of elementary school)
Textbook 春天來了, 春天在哪兒
Spring is coming! Where the spring is?
Magazin
e
( Travel magazines )
在易北河河岸的小山丘上
On the hill which in the streamside of Elbe
( Newspaper )
News
將使市公所的財政赤字擴大
It will raise the deficit financing of
municipality
Training
data
Testing data
for
3117/
20400
774/
3957
3770/
17782
1728/
8046
4177/
25220
3629/
23844
3793/
21220
2426/
15083
# of clauses/# of words
SVM実験ー実験結果(2/3)
(訓練事例は各カテゴリ)
Testing data
Experiment (1)
Anthology
Root
Acc.
Clause
Acc.
Training data
Dep.
Acc.
Textbook
Magazine
News
Anthology
Textbook
Magazine
News
88.44
94.59
74.72
87.61
94.81
72.29
86.92
94.26
73.50
86.20
94.15
70.75
88.01
93.19
74.72
88.75
94.19
76.42
87.10
93.84
73.25
87.63
93.07
74.31
77.78
88.99
50.47
75.62
87.10
46.95
77.78
89.08
52.17
76.34
87.55
48.76
76.30
87.38
51.59
73.54
87.03
47.83
76.80
89.95
50.97
77.39
88.98
52.87
SVMの実験結果
(訓練事例の大きさによる変化)
Training
data
Part(3)=
KO10,11,12
sentences/ Anthology Textbook Magazine News
Words
(test)
(test)
(test)
(test)
87.03
88.25
74.84
71.66
3770/
94.44
93.81
86.21
86.04
17782
69.12
76.00
46.28
45.43
89.25
89.85
76.37
72.88
Part(4)=
9920/
94.70
95.14
87.77
85.75
All textbook 44032
75.19
78.89
49.51
49.00
Part(5)=
91.39
90.60
78.97
75.25
13036/
Part(4)+anth
95.60
95.31
89.19
87.64
64431
ology
78.68
80.00
52.60
51.57
Part(6)=
92.07
91.14
81.01
78.64
17863/
Part(5)+mag
96.02
95.54
90.43
89.24
92839
azine 1.1
80.68
81.29
56.32
55.53
SVM実験
(訓練事例の大きさによる変化)
Dep.
Acc.
anthology
textbook
newspaper
magazine
95
90
85
80
75
70
65
0
20000
40000
60000
80000
100000
# of word
学習に基づく手法の何がよいか?
頑健性 / 曖昧性解消能力
機械学習による解析が常に正しいわけではない
が,


簡単な学習モデルによって解析可能な問題とそれが
困難な問題を明確にしてくれる
現在の問題を解くためにどのような情報が必要かの
示唆を与えてくれる
support vectorsからの有効素性の
マイニング [Kudo 03]
現在進行中のプロジェクト
Corpus Tools



タグ付きコーパスのための検索
タグ付きコーパスの修正
辞書とタグ付きコーパスの整合性維持
機械学習による手法と制約文法に基づく手法の
融合による自然言語処理


統計的言語処理システムを制御情報とする日本語
HPSG (Head-driven Phrase Structure Grammar)の
パージング
制約の緩和による頑健な文法解析
機械学習による手法と制約文法に
基づく手法の融合
機械学習によるパージング
頑健: どのような入力文に対しても解を出す
○ 曖昧性解消: 単一の結果 or 順序付の結果
× Information poor: 文法的説明の欠如
○
制約に基づく文法
Information rich: 文法性の説明
× 脆弱: 低いカバレージ
× 曖昧: 多数の可能な解
○
統計的手法の利点と限界
利点


簡単な問題はデータと機械学習が解いてくれる
（例外）規則を列挙するなど無意味な作業からの
解放
統計的手法の限界



最終的な姿ではない．すべてが解ける訳ではな
い．
文法性／非文法性の説明
深い意味理解
なぜ文法研究が必要か
本を読んだのは誰？


a. 私は太郎に本を読ませた．
b. 私は太郎に本を読ませられた．
（太郎）
（私）
太郎は本を読んだでしょうか？


a. 太郎は本を読み直した．
b. 太郎は本を読みそびれた．
（yes）
（no）
なぜ，「本が読みそびれられた」と言えない
のか？
「直す」の構文木
V
V
N
健が
N
V
N
本を
本が
V
V
読み
V
V
N
V
V
健に
V
V
V
読み
直さ
直す
れる
「そびれる」の構文木
V
N
V
V
健が
V
N
V
本を
読み
そびれる
•「れる／られる」はガ格とヲ格
を持つ動詞に結合する
•「そびれる」はガ格のみを残し
た動詞句と結合する
•こう考えるべき別の理由
•「健が本を読みそびれた」
•○「僕もそうしそびれた」
•「健が本を読み直した」
•×「僕もそうし直した」
References
[Kudo 2001] Taku Kudo and Yuji Matsumoto, “Chunking with Support
Vector Machines,” NAACL 2001.
[Kudo 2002] Taku Kudo and Yuji Matsumoto, “Japanese dependency
analysis using cascaded chunking,” CoNLL 2002.
[Nakagawa 2002] Tetsuji Nakagawa, Taku Kudo and Yuji Matumoto,
“Revision learning and its application to POS tagging,” ACL2002.
[Yamada 2003] Hiroyasu Yamada and Yuji Matsumoto, “Statistical
dependency analysis with Support Vector Machines,” 8th International
Workshop on Parsing Technologies (IWPT), pp.195-206, April 2003.
[Asahara 2003] Masayuki Asahara and Yuji Matsumoto, “Japanese
named entity extraction with redundant morphological analysis,” HLTNAACL 2003.
[Kudo 2003] Taku Kudo and Yuji Matsumoto, “Fast methods for kernelbased text analysis,” ACL 2003.
[Goh 2003] Chooi Ling Goh, Masayuki Asahara and Yuji Matsumoto,
“Chinese unknown word identification using character-based tagging
and chunking,” poster/demo paper, ACL 2003.
[Yuchang 2004] Yuchang Cheng, Masayuki Asahara, Yuji Matsumoto,
“Deterministic dependency structure analyzer for Chinese,” 1st
International Joint Conference on Natural Language Processing,
pp.135-140, March 2004.

Download Report