miyao

Contents
• On the complexity of non-projective datadriven dependency parsing.
Ryan McDonald and Giorgio Satta.
In Proceedings of IWPT 2007.
• Perceptron training for a wide-coverage
lexicalized-grammar parser.
Stephen Clark and James Curran.
In Proceedings of the Workshop on Deep
Linguistic Processing. 2007.
On the complexity of non-projective
data-driven dependency parsing
• Non-projective dependency parsing の計算量
についての理論的研究
• Argmax, partition function, edge expectation
の計算量解析
• 主な結果：
– Edge-factored model については，モデル学習，最
適解探索とも多項式時間
– Arity の制約や親・兄弟による条件付けを入れる
と intractable
Non-projective dependency parsing
• 構文解析の一種
• ノード＝単語，エッジ＝単語間の依存関係
• Dependency tree = 単一ノードを根とする木構
造，を見つける問題
• Non-projective: エッジが交差してもよい
Edge-factored model
•
•
•
•
V = { 0, 1, …, n }
E = { (i, j) | i, j ∈ V }
w(T): dependency tree T の重み
Edge-factored モデル： w(T )   wij
( i , j )ET
0
1
2
3
root He runs fast
w(T )  w02 w21w23
既存のモデル
• Projective
– 決定的アルゴリズム [Yamada & Matsumoto 2003; Nivre
& Scholz 2004]
– 動的計画法 [Eisner 1996; McDonald et al. 2005]
• Non-projective
– 決定的アルゴリズム [Nivre & Nilsson 2005]
– Maximum Spanning Tree [McDonald et al. 2005]
主要な問題
• Argmax: 重み最大の木を探索
– 最適解の探索
– Perceptron, MIRA などのパラメタ推定
• Partition function: 全ての木の重みの総和
– Log-linear model の学習
– 確率的言語モデル
• Edge expectation: エッジの重みの期待値
– Log-linear model の学習
– Min-risk decoding
– EM アルゴリズム
Argmax
• Tˆ  arg max w(T )を求める
• Maximum Spanning Tree アルゴリズムを適用
[McDonald et al. 2005]
– まず各ノードについて，入ってくるエッジのうち重
み最大のものを選択
– サイクルがあったら，それを一つのノードだと思っ
てまた重み最大のエッジを選択
– 木になるまで繰り返す
• 計算量： O(n2)
Partition function

w(T ) を計算
• Z
• Matrix Tree Theorem [Tutte 1984] を適用
–
–
–
–
元々は spanning tree の個数を求める問題
Laplacian matrix Q jj  (i , j )E wij Qij   wij
Qi: Q から i 行，i 列を取り除いた行列
根がノード i の木の重みの総和 = | Qi |
• 計算量： O(n3)
Edge expectation
• E[(i, j )] 
 w(T )I ((i, j), T ) を求める
Indicator function
• グラフから (i, j )  (i, j ) を取り除き，partition
function を計算する
• 計算量： O(n5)
• O(n3) のアルゴリズムが同時期に発表され
ている [Koo et al. 2007; Smith & Smith 2007]
Non-edge-factored model への拡張
• もっと制約・情報を入れたい [McDonald & Pereira 2006]
• Arity: ノードから出るエッジの最大数を制限
• Horizontal/Vertical Markovization: 重みが親・兄
弟の dependency に依存
Arity の制約
• グラフ G=<V, E> の各ノード i∈V の arity （出て行
くエッジの数）を φ(i) 以下に制限
• Hamiltonian path を求める問題に帰着
– Hamiltonian path: グラフの全ての点をちょうど一回ず
つ通るパス
– NP-hard であることが分かっている
• 方針：グラフ G の MST を求めれば G’ の
Hamiltonian path が求まるようにする
– G’ に存在するエッジに対応する重みを1，それ以外を
0に設定
– φ(i) を１に設定
Vertical Markovization
• 結合価，選択制限などを表現
• Horizontal Markovization は NP-hard [McDonald &
Pereira 2006]
• Vertical Markovization は 3DM 問題に帰着
– サイズ m の集合 A, B, C について，S⊆A×B×C の
部分集合で各要素が一度ずつ現れるものがあるか
– NP-complete であることが分かっている
• 方針：V=A∪B∪C のグラフで，MST の各パスが
必ず 0→a→b→c となるようにグラフを構成
Projective model との比較
Argmax
Partition function
Projective
O(n3+|L|n2)
O(n3+|L|n2)
Non-projective
O(|L|n2)
O(n3+|L|n2)
Edge expectation
O(n3+|L|n2)
O(n3+|L|n2)
• Projective model では，Arity の制約，
horizontal/vertical Markovization を入れて
も多項式時間
まとめ
• Non-projective edge-factored model におい
て，モデル学習，最適解探索の効率的な
アルゴリズムが存在
• Edge-factored model を拡張すると，
intractable
• 今後の課題
– 効率的アルゴリズムが存在する拡張
– 近似アルゴリズム
Perceptron training for a wide-coverage
lexicalized-grammar parser
• CCG parsing に averaged perceptron を適用
• 主な結果：
– オンライン学習かつ iteration が少ないため，
学習データをメモリ上に置く必要がない
→ メモリ使用量が劇的に改善
– 精度は log-linear model とあまり変わらない
CCG parsing
• CCG: Combinatory Categorial Grammar
[Steedman 2000]
S
合成規則：
X Y＼X → Y
S＼NP
NP
S＼NP (S＼NP)＼(S＼NP)
語彙カテゴリ
He
runs
fast
• LTAG, HPSG もほとんど同じ
既存の曖昧性解消モデル
• Supertagging: sequence model ではじめに語彙
カテゴリを決める [Clark & Curran 2004]
• 文 w=<w1,…,wn>，語彙カテゴリ l=<l1,…,ln> が
与えられた時，
1
p(T | w, l )  exp λΦ(T , w, l ) 
Z
(log-linear model)
• パラメタ λ は inside-outside algorithm 風の動的
計画法で推定 [Miyao & Tsujii 2002; Clark & Curran 2004]
Averaged perceptron モデル
• Log-linear model を
averaged perceptron
に置き換える
 (T , w, l )  αΦ(T , w, l)
（右図はただの perceptron）
• Inside-outside algorithm の代わりに，
Viterbi algorithm を使う（argmax の部分）
Perceptron モデルの利点
• オンライン学習
• 収束が早い（だいたい 10 iteration 程度）
→ 学習データをメモリ上に置かなくてよい
• 実装が簡単
実験結果
• 学習コスト
メモリ
iteration
時間（分）
Perceptron
β=0.004
20 MB
10
312
Log-linear
β=0.004
19 GB
475
91
• Predicate-argument relation の精度
Precision
Recall
F-score
Perceptron
β=0.002
87.50
86.62
87.06
Log-linear
β=0.004
87.39
86.51
86.95
まとめ
• CCG parsing に averaged perceptron を適用
– 学習時のメモリ使用量が 1/1000
– 精度はあまり変わらない
• その他の結果
– Perceptron の学習は 4 iteration でほぼ収束
– 学習サンプルの順番を変えても結果はあまり変
わらない（ランダム，短い文から，長い文から）

Download Report