機械翻訳のための構文解析基礎 - kecl.ntt.co.jp ·...

機械翻訳のための構文解析基礎

†林克彦

NTTコミュニケーション科学基礎研究所†[email protected]

構文解析とはどんなタスク？

• 形式的な文法に基づいて自然言語文の構文構造を予測する

• 句構造文法 (文脈自由文法)，依存文法，(組み合わせ)範疇文法，主辞駆動句構造文法，など

• 句構造文法による構文解析の基本技術を解説

• 確率文脈自由文法• CKY構文解析• K-best構文解析の考え方• 確率文脈自由文法 + 品詞N-gram


• 形式的な文法に基づいて自然言語文の構文構造を予測する• 句構造文法 (文脈自由文法)，依存文法，(組み合わせ)範疇文法，主辞駆動句構造文法，など









• 句構造文法による構文解析の基本技術を解説• 確率文脈自由文法• CKY構文解析• K-best構文解析の考え方• 確率文脈自由文法 + 品詞N-gram

句構造木 (Phrase Structure Tree)

....S.....

..VP.....

..PP.....

..NP.....

..NN...

..telescope.

..

..DT...

..a.

..

..IN...

..with.

....

..NP.....

..NN...

..girl.

..

..DT...

..a.

..

..VBD...

..saw.

..

..NP...

..PRP...

..I

• 再帰的に句を構成していくことで木構造を形成


..

単語列

...S.....

..VP.....

..PP.....

..NP.....

..NN...

..telescope.

..

..DT...

..a.

..

..IN...

..with.

....

..NP.....

..NN...

..girl.

..

..DT...

..a.

..

..VBD...

..saw.

..

..NP...

..PRP...

..I



..

単語列

.

品詞列

...S.....

..VP.....

..PP.....

..NP.....

..NN...

..telescope.

..

..DT...

..a.

..

..IN...

..with.

....

..NP.....

..NN...

..girl.

..

..DT...

..a.

..

..VBD...

..saw.

..

..NP...

..PRP...

..I



..

句構造

.

単語列

.

品詞列

...S.....

..VP.....

..PP.....

..NP.....

..NN...

..telescope.

..

..DT...

..a.

..

..IN...

..with.

....

..NP.....

..NN...

..girl.

..

..DT...

..a.

..

..VBD...

..saw.

..

..NP...

..PRP...

..I


句構造木への主辞割当 (Head Annotation)

....S(saw).....

..VP(saw).....

..PP(with).....

..NP(tele.).....

..NN...

..tele..

..

..DT...

..a.

..

..IN...

..with.

....

..NP(girl).....

..NN...

..girl.

..

..DT...

..a.

..

..VBD...

..saw.

..

..NP(I)...

..PRP...

..I

• ある句の中で最も重要な単語を主辞 (head)と呼ぶ

• 句ラベルを取り除く• 主辞間の係り受け関係を作る

句構造木への主辞割当 (Head Annotation)....saw.....

..saw.....

..with.....

..tele......

..NN...

..tele..

..

..DT...

..a.

..

..IN...

..with.

....

..girl.....

..NN...

..girl.

..

..DT...

..a.

..

..VBD...

..saw.

..

..I...

..PRP...

..I

• ある句の中で最も重要な単語を主辞 (head)と呼ぶ• 句ラベルを取り除く

• 主辞間の係り受け関係を作る

句構造木への主辞割当 (Head Annotation)....saw.....

..saw.....

..with.....

..tele......

..NN...

..tele..

..

..DT...

..a.

..

..IN...

..with.

....

..girl.....

..NN...

..girl.

..

..DT...

..a.

..

..VBD...

..saw.

..

..I...

..PRP...

..I

• ある句の中で最も重要な単語を主辞 (head)と呼ぶ• 句ラベルを取り除く• 主辞間の係り受け関係を作る

依存構造木 (Dependency Tree)

....$ ..I ..saw ..a ..girl ..with ..a ..telescope.. .. .. .. .. .. .. ....$ ..PRP ..VBD ..DT ..NN ..IN ..DT ..NN

.......

• 単語間の関係を直接記述した構文木

依存構造木 (Dependency Tree)

....$ ..I ..saw ..a ..girl ..with ..a ..telescope.. .. .. .. .. .. .. ....$ ..PRP ..VBD ..DT ..NN ..IN ..DT ..NN

.......

• 単語間の関係を直接記述した構文木

構文木が付与されたコーパスデータ

句構造文法依存文法

英語 Penn Treebank *句構造木⇒依存構造木(Marcus, 93)

中国語 Chinese Penn Treebank *句構造木⇒依存構造木(Xue, 05)

日本語欅ツリーバンク京大テキストコーパス(Butler, 04) (黒橋, 97)

** Stanford大学の自動変換システムが有名

• 数万文規模のコーパスから構文解析モデルを統計的に学習• 未知の文でも柔軟に自動解析

構文木•構文解析は機械翻訳の何に役立つ？

• 入力側に構文木がある場合• 事前並べ替え (Collins, 07; Isozaki, 10; など) (須藤先生の講義)• 統語ベース翻訳 (Yamada, 01; Graehl, 04; など) (グラム先生の講義)

• 出力側に構文木がある場合• 統語言語モデル (Shen, 08; Schwartz, 10; など)

• 構文解析技術• 同期文脈自由文法による機械翻訳 (Chiang, 07) (林による次の講義)

確率文脈自由文法: 定義....S.....

..VP.....

..PP.....

..NP.....

..NN...

..telescope.

..

..DT...

..a.

..

..IN...

..with.

....

..NP.....

..NN...

..girl.

..

..DT...

..a.

..

..VBD...

..saw.

..

..NP...

..PRP...

..I

• 確率文脈自由文法 G = (VN ,VT ,P,S) (北, 1999)

• VN : 非終端記号の集合. 例: VP, NP, DT• VT : 終端記号の集合. 例: I, with• P: 確率生成規則の集合. 例: NP 0.8−→ DT NN• S: 開始記号. TOPなどの記号がよく使われるが, ここではSを使う.


..VP.....

..PP.....

..NP.....

..NN...

..telescope.

..

..DT...

..a.

..

..IN...

..with.

....

..NP.....

..NN...

..girl.

..

..DT...

..a.

..

..VBD...

..saw.

..

..NP...

..PRP...

..I

• 確率文脈自由文法 G = (VN ,VT ,P,S) (北, 1999)• VN : 非終端記号の集合. 例: VP, NP, DT

• VT : 終端記号の集合. 例: I, with• P: 確率生成規則の集合. 例: NP 0.8−→ DT NN• S: 開始記号. TOPなどの記号がよく使われるが, ここではSを使う.


..VP.....

..PP.....

..NP.....

..NN...

..telescope.

..

..DT...

..a.

..

..IN...

..with.

....

..NP.....

..NN...

..girl.

..

..DT...

..a.

..

..VBD...

..saw.

..

..NP...

..PRP...

..I

• 確率文脈自由文法 G = (VN ,VT ,P,S) (北, 1999)• VN : 非終端記号の集合. 例: VP, NP, DT• VT : 終端記号の集合. 例: I, with

• P: 確率生成規則の集合. 例: NP 0.8−→ DT NN• S: 開始記号. TOPなどの記号がよく使われるが, ここではSを使う.


..VP.....

..PP.....

..NP.....

..NN...

..telescope.

..

..DT...

..a.

..

..IN...

..with.

....

..NP.....

..NN...

..girl.

..

..DT...

..a.

..

..VBD...

..saw.

..

..NP...

..PRP...

..I

• 確率文脈自由文法 G = (VN ,VT ,P,S) (北, 1999)• VN : 非終端記号の集合. 例: VP, NP, DT• VT : 終端記号の集合. 例: I, with• P: 確率生成規則の集合. 例: NP 0.8−→ DT NN

• S: 開始記号. TOPなどの記号がよく使われるが, ここではSを使う.


..VP.....

..PP.....

..NP.....

..NN...

..telescope.

..

..DT...

..a.

..

..IN...

..with.

....

..NP.....

..NN...

..girl.

..

..DT...

..a.

..

..VBD...

..saw.

..

..NP...

..PRP...

..I

• 確率文脈自由文法 G = (VN ,VT ,P,S) (北, 1999)• VN : 非終端記号の集合. 例: VP, NP, DT• VT : 終端記号の集合. 例: I, with• P: 確率生成規則の集合. 例: NP 0.8−→ DT NN

• S: 開始記号. TOPなどの記号がよく使われるが, ここではSを使う.


..VP.....

..PP.....

..NP.....

..NN...

..telescope.

..

..DT...

..a.

..

..IN...

..with.

....

..NP.....

..NN...

..girl.

..

..DT...

..a.

..

..VBD...

..saw.

..

..NP...

..PRP...

..I

• 確率文脈自由文法 G = (VN ,VT ,P,S) (北, 1999)• VN : 非終端記号の集合. 例: VP, NP, DT• VT : 終端記号の集合. 例: I, with• P: 確率生成規則の集合. 例: NP 0.8−→ DT NN• S: 開始記号. TOPなどの記号がよく使われるが, ここではSを使う.

確率文脈自由文法による句構造木予測モデル

• 入力文xとその句構造木yがある

• xとyが同時に生成される確率モデルを仮定し,

*導出(x,y) = r1 ⇒ r2 ⇒ ·· · ⇒ rm

*規則の適用確率は前に適用された規則の影響を受けない

• 上式の最適化は動的計画法による効率的な解析が可能

• CKY法, アーリー法, 一般化LR法

確率文脈自由文法による句構造木予測モデル

• 入力文xとその句構造木yがある• xとyが同時に生成される確率モデルを仮定し,

y = argmaxy∈Y

p(x,y) = argmaxy∈Y

p(r1,r2, . . . ,rm)

= argmaxy∈Y

Πmi=1 p(ri)

*導出(x,y) = r1 ⇒ r2 ⇒ ·· · ⇒ rm

*規則の適用確率は前に適用された規則の影響を受けない• 上式の最適化は動的計画法による効率的な解析が可能

• CKY法, アーリー法, 一般化LR法

生成規則 = 演繹推論規則 (Shieber, 95)

前件部︷︸︸︷..i.

VBD

.k

.: p1

..k+1.

NP

.j

.: p2

..j+1.

PP

.ℓ

.: p3

..i.

VP

.ℓ

.: p1 × p2 × p3 × p

︸︷︷︸後件部

VP p−→ VBD NP PP

• 規則のアイテム (三角)は句構造木の部分木に対応• アイテムは単語スパン，ルートの非終端記号，累積確率を持つ• 規則が適用されると，前件部を後件部で置き換える

構文解析 = 演繹推論規則による導出過程

....S.....

..VP.....

..NN...

..girl

.0.9

.

..

..VBD...

..saw

.1.0

.0.7

.

..

..NP...

..PRP...

..I

.1.0

.0.7

.0.9

..0.I

.1

. 1.0

..0.PRP.

1. 1.0

PRP 1.0−−→ I

..0.NP.

1. 0.7

NP 0.7−−→ PRP

..1.saw.

2. 1.0

..1.VBD.

2. 1.0

VBD 1.0−−→ saw

..3.girl.

4. 1.0

..3.NN.

4. 0.9

NN 0.9−−→ girl

..1.VP.

4. 0.63

VP 0.7−−→ VBD NP

..0.S

.4

. 0.3969

S 0.9−−→ NP VP

• 単語 = 演繹推論の公理• 生成規則 = 推論規則• 解析完了 (終了記号) = 推論のゴール

構文解析の計算量

..i.

VBD

.k

.: p1

..k+1.

NP

.j

.: p2

..j+1.

PP

.ℓ

.: p3

..i.

VP

.ℓ

.: p1 × p2 × p3 × p


• 規則に出現する単語インデックスの数: i,k, j, ℓ

• 入力文の単語数n，規則に出現する単語インデックスの数x

• 動的計画法による計算量: O(nx) (上の場合O(n4)) (McAllester, 01)

• 解析効率を上げるため，一般には規則の二分化が必要

*アーリー法は解析時，動的に二分化を行う


..i.

VBD

.k

.: p1

..k+1.

NP

.j

.: p2

..j+1.

PP

.ℓ

.: p3

..i.

VP

.ℓ

.: p1 × p2 × p3 × p


• 規則に出現する単語インデックスの数: i,k, j, ℓ• 入力文の単語数n，規則に出現する単語インデックスの数x

• 動的計画法による計算量: O(nx) (上の場合O(n4)) (McAllester, 01)

• 解析効率を上げるため，一般には規則の二分化が必要



..i.

VBD

.k

.: p1

..k+1.

NP

.j

.: p2

..j+1.

PP

.ℓ

.: p3

..i.

VP

.ℓ

.: p1 × p2 × p3 × p



• 動的計画法による計算量: O(nx) (上の場合O(n4)) (McAllester, 01)• 解析効率を上げるため，一般には規則の二分化が必要



..i.

VBD

.k

.: p1

..k+1.

NP

.j

.: p2

..j+1.

PP

.ℓ

.: p3

..i.

VP

.ℓ

.: p1 × p2 × p3 × p



• 動的計画法による計算量: O(nx) (上の場合O(n4)) (McAllester, 01)• 解析効率を上げるため，一般には規則の二分化が必要


チョムスキー標準形

• チョムスキー標準形• 生成規則の形式は次の2つだけをとる

• A → B C (A, B, C∈VN)• A → a (A∈VN , a∈VT )

*実用上, A → B (A, B∈VN)のようなunary規則も残すことが多い• 生成規則の二分化 (Binarization)




*実用上, A → B (A, B∈VN)のようなunary規則も残すことが多い

• 生成規則の二分化 (Binarization)





....X p.....

..X4.

....

..X3.

....

..X2.

..

..X1





....X p.....

..X4.

....

..X3.

....

..X2.

..

..X1

....X p.....

..X2' 1.0.....

..X4.

....

..X3.

..

..X2

.

..

..X1





....X p.....

..X4.

....

..X3.

....

..X2.

..

..X1

....X p.....

..X2' 1.0.....

..X4.

....

..X3.

..

..X2

.

..

..X1

....X p.....

..X2' 1.0.....

..X3' 1.0.....

..X4.

..

..X3

.

..

..X2

.

..

..X1

CKY 構文解析: 三角表の初期化• 入力文xの長さがnとすると, nに対する三角表を構築

..0I1

.1saw2

.2a3

.3girl4

.

4with5

.5a6

.

6telescope

7

CKY 構文解析: 終端記号に対する規則の適用• 入力文xの単語に非終端記号を割り当てる

..0I1

.1saw2

.2a3

.3girl4

.

4with5

.5a6

.

6telescope

7.

0PRP1.

0NP1

.1VBD2

.2DT3

.3NN4

. 4IN5

.5DT6

.6NN7

CKY 構文解析: より大きなスパンの構築• 2単語スパンの構築 (生成規則NP → DT NN)

..0I1

.1saw2

.2a3

.3girl4

.

4with5

.5a6

.

6telescope

7.

0PRP1.

0NP1

.1VBD2

.2DT3

.3NN4

. 4IN5

.5DT6

.6NN7.

2NP4

.5NP7

CKY 構文解析: より大きなスパンの構築• 3単語スパンの構築 (生成規則VP → VBD NP, PP → IN NP)

..0I1

.1saw2

.2a3

.3girl4

.

4with5

.5a6

.

6telescope

7.

0PRP1.

0NP1

.1VBD2

.2DT3

.3NN4

. 4IN5

.5DT6

.6NN7.

2NP4

.5NP7

.

1VP4

.

4PP7

CKY 構文解析: より大きなスパンの構築• 4単語スパンの構築 (生成規則S → NP VP)

..0I1

.1saw2

.2a3

.3girl4

.

4with5

.5a6

.

6telescope

7.

0PRP1.

0NP1

.1VBD2

.2DT3

.3NN4

. 4IN5

.5DT6

.6NN7.

2NP4

.5NP7

.

1VP4

.

4PP7

.

0S4

CKY 構文解析: より大きなスパンの構築• 5単語スパンの構築 (生成規則NP → NP PP)

..0I1

.1saw2

.2a3

.3girl4

.

4with5

.5a6

.

6telescope

7.

0PRP1.

0NP1

.1VBD2

.2DT3

.3NN4

. 4IN5

.5DT6

.6NN7.

2NP4

.5NP7

.

1VP4

.

4PP7

.

0S4

.

2NP7

CKY 構文解析: より大きなスパンの構築• 6単語スパンの構築 (生成規則VP → VBD NP, VP → VP PP)

..0I1

.1saw2

.2a3

.3girl4

.

4with5

.5a6

.

6telescope

7.

0PRP1.

0NP1

.1VBD2

.2DT3

.3NN4

. 4IN5

.5DT6

.6NN7.

2NP4

.5NP7

.

1VP4

.

4PP7

.

0S4

.

2NP7

.

1VP7

.

1VP7

CKY 構文解析: より大きなスパンの構築• 6単語スパンの構築 (生成規則VP → VBD NP, VP → VP PP)

..0I1

.1saw2

.2a3

.3girl4

.

4with5

.5a6

.

6telescope

7.

0PRP1.

0NP1

.1VBD2

.2DT3

.3NN4

. 4IN5

.5DT6

.6NN7.

2NP4

.5NP7

.

1VP4

.

4PP7

.

0S4

.

2NP7

.

1VP7

.

1VP7

.

累積確率の高い方を残す!

CKY 構文解析: より大きなスパンの構築• 7単語スパンの構築 (生成規則S → NP VP)

..0I1

.1saw2

.2a3

.3girl4

.

4with5

.5a6

.

6telescope

7.

0PRP1.

0NP1

.1VBD2

.2DT3

.3NN4

. 4IN5

.5DT6

.6NN7.

2NP4

.5NP7

.

1VP4

.

4PP7

.

0S4

.

2NP7

.

1VP7

.

1VP7

.

0S7

CKY 構文解析: バックトレース• バックトレースして確率が最大となる構文木yを出力

..0I1

.1saw2

.2a3

.3girl4

.

4with5

.5a6

.

6telescope

7.

0PRP1.

0NP1

.1VBD2

.2DT3

.3NN4

. 4IN5

.5DT6

.6NN7.

2NP4

.5NP7

.

1VP4

.

4PP7

.

0S4

.

2NP7

.

1VP7

.

1VP7

.

0S7

CKY構文解析の計算量

• 規則は全て二分化されている = 前件部は1 or 2個のアイテム数

..i.

VBD

.k

.: p1

..k+1.

NP

.j

.: p2

..i.

VP

.j

.: p1 × p2 × p

VP p−→ VBD NP

• 規則に出現する単語インデックスの数: i,k, j• 入力文の単語数n

• 動的計画法による構文解析の計算量: O(n3)

K-best構文解析

• 複数の構文木が欲しい

....S.....

..VP.....

..PP.....

..NP.....

..NN...

..tele..

..

..DT...

..a.

..

..IN...

..with.

..

..VP.....

..NP.....

..NN...

..girl.

..

..DT...

..a.

..

..VBD...

..saw.

..

..NP...

..PRP...

..I

....S.....

..VP.....

..NP.....

..PP.....

..NP.....

..NN...

..tele..

..

..DT...

..a.

..

..IN...

..with.

..

..NP.....

..NN...

..girl.

..

..DT...

..a.

..

..VBD...

..saw.

..

..NP...

..PRP...

..I

K-best構文解析• K個の同一アイテムを残す

..0I1

.1saw2

.2a3

.3girl4

.

4with5

.5a6

.

6telescope

7.

0PRP1.

0NP1

.1VBD2

.2DT3

.3NN4

. 4IN5

.5DT6

.6NN7.

2NP4

.5NP7

.

1VP4

.

4PP7

.

0S4

.

2NP7

.

1VP7

.

1VP7

.

累積確率の高い方を残す!

K-best構文解析• K個の同一アイテムを残す

..0I1

.1saw2

.2a3

.3girl4

.

4with5

.5a6

.

6telescope

7.

0PRP1.

0NP1

.1VBD2

.2DT3

.3NN4

. 4IN5

.5DT6

.6NN7.

2NP4

.5NP7

.

1VP4

.

4PP7

.

0S4

.

2NP7

.

1VP7

.

1VP7

.

累積確率の高いK個を残す!

K-best構文解析

• 累積確率上位K個のアイテムを効率的に求める (Huang and Chiang, 05)

• 例: 1S7となる累積確率上位3個を求める (3×3+3×3 = 18通り)

4VP7S 0.5−−→ NP VP 0.6 0.4 0.3

0.91NP4 0.5

0.3

2PP7S 0.3−−→ NP PP 0.8 0.2 0.1

0.81NP2 0.4

0.2

priority queue:3-best:

K-best構文解析



4VP7S 0.5−−→ NP VP 0.6 0.4 0.3

0.9 0.271NP4 0.5

0.3

2PP7S 0.3−−→ NP PP 0.8 0.2 0.1

0.8 0.1921NP2 0.4

0.2

priority queue: 0.27 0.192

3-best:

K-best構文解析



4VP7S 0.5−−→ NP VP 0.6 0.4 0.3

0.9 0.18

1NP4 0.5 0.150.3

2PP7S 0.3−−→ NP PP 0.8 0.2 0.1

0.8 0.1921NP2 0.4

0.2

priority queue: 0.192 0.18 0.15

3-best: 0.27

K-best構文解析



4VP7S 0.5−−→ NP VP 0.6 0.4 0.3

0.9 0.18

1NP4 0.5 0.150.3

2PP7S 0.3−−→ NP PP 0.8 0.2 0.1

0.8 0.048

1NP2 0.4 0.0960.2

priority queue: 0.18 0.15 0.096 0.048

3-best: 0.27 0.192

K-best構文解析



4VP7S 0.5−−→ NP VP 0.6 0.4 0.3

0.9

1NP4 0.5 0.150.3

2PP7S 0.3−−→ NP PP 0.8 0.2 0.1

0.8 0.048

1NP2 0.4 0.0960.2

priority queue: 0.15 0.096 0.048

3-best: 0.27 0.192 0.18

系列ラベリングとしての品詞タグ付け

• 品詞タグ付けラティス: 単語列wn+10 と品詞列posn+1

0

..

t = 0

.

<s>/<s>

.

t = 1

.

I/VBD

.

I/PRP

.

I/NN

.

I/DT

.

t = 2

.

saw/VBD

.

saw/PRP

.

saw/NN

.

saw/DT

.

t = 3

.

a/VBD

.

a/PRP

.

a/NN

.

a/DT

.

t = 4

.

girl/VBD

.

girl/PRP

.

girl/NN

.

girl/DT

.

t = 5

.

</s>/</s>

• 隠れマルコフモデルによる系列ラベリング



0

..

t = 0

.

<s>/<s>

.

t = 1

.

I/VBD

.

I/PRP

.

I/NN

.

I/DT

.

t = 2

.

saw/VBD

.

saw/PRP

.

saw/NN

.

saw/DT

.

t = 3

.

a/VBD

.

a/PRP

.

a/NN

.

a/DT

.

t = 4

.

girl/VBD

.

girl/PRP

.

girl/NN

.

girl/DT

.

t = 5

.

</s>/</s>




0

..

t = 0

.

<s>/<s>

.

t = 1

.

I/VBD

.

I/PRP

.

I/NN

.

I/DT

.

t = 2

.

saw/VBD

.

saw/PRP

.

saw/NN

.

saw/DT

.

t = 3

.

a/VBD

.

a/PRP

.

a/NN

.

a/DT

.

t = 4

.

girl/VBD

.

girl/PRP

.

girl/NN

.

girl/DT

.

t = 5

.

</s>/</s>




0

..

t = 0

.

<s>/<s>

.

t = 1

.

I/VBD

.

I/PRP

.

I/NN

.

I/DT

.

t = 2

.

saw/VBD

.

saw/PRP

.

saw/NN

.

saw/DT

.

t = 3

.

a/VBD

.

a/PRP

.

a/NN

.

a/DT

.

t = 4

.

girl/VBD

.

girl/PRP

.

girl/NN

.

girl/DT

.

t = 5

.

</s>/</s>




0

..

t = 0

.

<s>/<s>

.

t = 1

.

I/VBD

.

I/PRP

.

I/NN

.

I/DT

.

t = 2

.

saw/VBD

.

saw/PRP

.

saw/NN

.

saw/DT

.

t = 3

.

a/VBD

.

a/PRP

.

a/NN

.

a/DT

.

t = 4

.

girl/VBD

.

girl/PRP

.

girl/NN

.

girl/DT

.

t = 5

.

</s>/</s>




0

..

t = 0

.

<s>/<s>

.

t = 1

.

I/VBD

.

I/PRP

.

I/NN

.

I/DT

.

t = 2

.

saw/VBD

.

saw/PRP

.

saw/NN

.

saw/DT

.

t = 3

.

a/VBD

.

a/PRP

.

a/NN

.

a/DT

.

t = 4

.

girl/VBD

.

girl/PRP

.

girl/NN

.

girl/DT

.

t = 5

.

</s>/</s>


系列ラベリングとしての品詞タグ付け• 品詞タグ付けラティス: 単語列wn+1

0 と品詞列posn+10

..

t = 0

.

<s>/<s>

.

t = 1

.

I/VBD

.

I/PRP

.

I/NN

.

I/DT

.

t = 2

.

saw/VBD

.

saw/PRP

.

saw/NN

.

saw/DT

.

t = 3

.

a/VBD

.

a/PRP

.

a/NN

.

a/DT

.

t = 4

.

girl/VBD

.

girl/PRP

.

girl/NN

.

girl/DT

.

t = 5

.

</s>/</s>


P(posn0|wn

0) =⇒ P(posn0)×P(wn

0|posn0)

≈ Πn+1t=1 P(post |post−1)×Πn

t=1P(wt |post)

品詞2-gramモデルとの結合

....S.....

..</s>...

..</s>.

....

..VP.....

..PP.....

..NP.....

..NN...

..telescope.

..

..DT...

..a.

..

..IN...

..with.

....

..NP.....

..NN...

..girl.

..

..DT...

..a.

..

..VBD...

..saw.

....

..NP...

..PRP...

..I.

..

..<s>...

..<s>

• 確率文脈自由文法と品詞2-gramの結合モデル


..P(PRP|<s>)

...S.....

..</s>...

..</s>.

....

..VP.....

..PP.....

..NP.....

..NN...

..telescope.

..

..DT...

..a.

..

..IN...

..with.

....

..NP.....

..NN...

..girl.

..

..DT...

..a.

..

..VBD...

..saw.

....

..NP...

..PRP...

..I.

..

..<s>...

..<s>



..P(PRP|<s>)

.

P(VBD|PRP)

...S.....

..</s>...

..</s>.

....

..VP.....

..PP.....

..NP.....

..NN...

..telescope.

..

..DT...

..a.

..

..IN...

..with.

....

..NP.....

..NN...

..girl.

..

..DT...

..a.

..

..VBD...

..saw.

....

..NP...

..PRP...

..I.

..

..<s>...

..<s>



..P(PRP|<s>)

.

P(VBD|PRP)

.

P(DT|VBD)

...S.....

..</s>...

..</s>.

....

..VP.....

..PP.....

..NP.....

..NN...

..telescope.

..

..DT...

..a.

..

..IN...

..with.

....

..NP.....

..NN...

..girl.

..

..DT...

..a.

..

..VBD...

..saw.

....

..NP...

..PRP...

..I.

..

..<s>...

..<s>



..P(PRP|<s>)

.

P(VBD|PRP)

.

P(DT|VBD)

.

P(NN|DT)

...S.....

..</s>...

..</s>.

....

..VP.....

..PP.....

..NP.....

..NN...

..telescope.

..

..DT...

..a.

..

..IN...

..with.

....

..NP.....

..NN...

..girl.

..

..DT...

..a.

..

..VBD...

..saw.

....

..NP...

..PRP...

..I.

..

..<s>...

..<s>



..P(PRP|<s>)

.

P(VBD|PRP)

.

P(DT|VBD)

.

P(NN|DT)

.

P(IN|NN)

...S.....

..</s>...

..</s>.

....

..VP.....

..PP.....

..NP.....

..NN...

..telescope.

..

..DT...

..a.

..

..IN...

..with.

....

..NP.....

..NN...

..girl.

..

..DT...

..a.

..

..VBD...

..saw.

....

..NP...

..PRP...

..I.

..

..<s>...

..<s>



..P(PRP|<s>)

.

P(VBD|PRP)

.

P(DT|VBD)

.

P(NN|DT)

.

P(IN|NN)

.

P(DT|IN)

...S.....

..</s>...

..</s>.

....

..VP.....

..PP.....

..NP.....

..NN...

..telescope.

..

..DT...

..a.

..

..IN...

..with.

....

..NP.....

..NN...

..girl.

..

..DT...

..a.

..

..VBD...

..saw.

....

..NP...

..PRP...

..I.

..

..<s>...

..<s>



..P(PRP|<s>)

.

P(VBD|PRP)

.

P(DT|VBD)

.

P(NN|DT)

.

P(IN|NN)

.

P(DT|IN)

.

P(NN|DT)

...S.....

..</s>...

..</s>.

....

..VP.....

..PP.....

..NP.....

..NN...

..telescope.

..

..DT...

..a.

..

..IN...

..with.

....

..NP.....

..NN...

..girl.

..

..DT...

..a.

..

..VBD...

..saw.

....

..NP...

..PRP...

..I.

..

..<s>...

..<s>



..P(PRP|<s>)

.

P(VBD|PRP)

.

P(DT|VBD)

.

P(NN|DT)

.

P(IN|NN)

.

P(DT|IN)

.

P(NN|DT)

.P(</s>|NN)

...S.....

..</s>...

..</s>.

....

..VP.....

..PP.....

..NP.....

..NN...

..telescope.

..

..DT...

..a.

..

..IN...

..with.

....

..NP.....

..NN...

..girl.

..

..DT...

..a.

..

..VBD...

..saw.

....

..NP...

..PRP...

..I.

..

..<s>...

..<s>


品詞2-gramモデルとの結合..

P(PRP|<s>).

P(VBD|PRP)

.

P(DT|VBD)

.

P(NN|DT)

.

P(IN|NN)

.

P(DT|IN)

.

P(NN|DT)

.P(</s>|NN)

...S.....

..</s>...

..</s>.

....

..VP.....

..PP.....

..NP.....

..NN...

..telescope.

..

..DT...

..a.

..

..IN...

..with.

....

..NP.....

..NN...

..girl.

..

..DT...

..a.

..

..VBD...

..saw.

....

..NP...

..PRP...

..I.

..

..<s>...

..<s>


y = argmaxy∈Y

Πmi=1 p(ri)×Πn+1

j=1 p(pos j|pos j−1)

結合モデルによるCKY構文解析の計算量

• 各アイテムは両端に品詞を記憶する必要がある

..i, posi.

VBD

.k, posk

.: p1

..k+1, posk+1

.

NP

.j, pos j

.: p2

..i, posi.

VP

.j, pos j

.: p1 × p2 × p×P(posk+1|posk)

VP p−→ VBD NP

• 単語インデックスの数と品詞タグの数: i,k, j, posi, posk, posk+1, pos j

• 入力文の単語数n，品詞タグ集合のサイズ|Vpos|

• CKY構文解析の計算量: O(n3|Vpos|4)



..i, posi.

VBD

.k, posk

.: p1

..k+1, posk+1

.

NP

.j, pos j

.: p2

..i, posi.

VP

.j, pos j


VP p−→ VBD NP


• 入力文の単語数n，品詞タグ集合のサイズ|Vpos|

• CKY構文解析の計算量: O(n3|Vpos|4)



..i, posi.

VBD

.k, posk

.: p1

..k+1, posk+1

.

NP

.j, pos j

.: p2

..i, posi.

VP

.j, pos j


VP p−→ VBD NP


• 入力文の単語数n，品詞タグ集合のサイズ|Vpos|• CKY構文解析の計算量: O(n3|Vpos|4)

Hookトリックによる計算量の削減 (Huang, 05)

..i, posi.

VBD

.k, posk

.: p1

..k+1, posk+1

.: 1.0

..i, posi.

k+1, posk+1

.

VP

.NP

.

: p1 × p×P(posk+1|posk)

VP p−→ VBD NP

..k+1, posk+1

.

NP

.j, pos j

.: p2

..i, posi.

VP

.j, pos j


• 2-gramを先に連結することでO(n3|Vpos|3)にできる

まとめ

• 確率文脈自由文法

• CKY構文解析• 品詞タグ付けとの結合モデル• K-best構文解析

まとめ

• 確率文脈自由文法 ⇒ 同期文脈自由文法による翻訳 (Chiang, 07)

• CKY構文解析• 品詞タグ付けとの結合モデル• K-best構文解析

まとめ


• CKY構文解析

• 品詞タグ付けとの結合モデル• K-best構文解析

まとめ


• CKY構文解析 ⇒ 同期文脈自由文法による翻訳のデコーダ (Chiang, 07)

• 品詞タグ付けとの結合モデル• K-best構文解析

まとめ



• 品詞タグ付けとの結合モデル

• K-best構文解析

まとめ



• 品詞タグ付けとの結合モデル ≈ 同期文脈自由文法による翻訳 +N-gram言語モデル (Chiang, 07)


まとめ





まとめ




• K-best構文解析 ⇒ Cube枝刈り (Chiang, 07)

有名な構文解析ツール

• 句構造解析Berkeley Parser: http://code.google.com/p/berkeleyparser/

Stanford Parser: http://nlp.stanford.edu/software/lex-parser.shtml

• 依存構造解析MST Parser: http://sourceforge.net/projects/mstparser/

Malt Parser: http://www.maltparser.org/

http://code.google.com/p/berkeleyparser/

http://nlp.stanford.edu/software/lex-parser.shtml

http://sourceforge.net/projects/mstparser/

http://www.maltparser.org/

参考文献• Marcus et. al., ``Building a large annotated corpus of English'', 1993.• Xue et. al., ``The Penn Chinese TreeBank: Phrase structure annotation of a largecorpus'', 2005.

• Butler et. al., ``Keyaki Treebank: phrase structure with functional information forJapanese'', 2004.

• 黒橋 and 長尾, ``京都大学テキストコーパス•プロジェクト'', 1997.• Collins et. al., ``Clause Restructuring for Statistical Machine Translation'', 2007.• Isozaki et. al., ``Head Finalization: A Simple Reordering Rule for SOV Languages'',2010.

• Yamada and Knight, `À Syntax-based Statistical Translation Model'', 2001.• Graehl and Knight, ``Training Tree Transducers'', 2004.• Shen et. al., `À New String-to-Dependency Machine Translation Algorithm with aTarget Dependency Language Model, 2008.

• Schwaltz et. al., `Ìncremental Syntactic Language Models for Phrase-basedTranslation'', 2010.

• Chiang, ``Hierarchical Phrase-based Translation'', 2007.• 北, ``言語と計算4 確率的言語モデル'', 1999.• Shieber et. al., ``Principles and Implementation of Deductive Parsing'', 1995.• McAllester, `Òn the Complexity Analysis of Static Analyses'', 2001.• Huang and Chiang, ``Better K-best Parsing'', 2005.• Huang et. al., ``Machine Translation as Lexicalized Parsing with Hooks'', 2005.

Date post:	05-Mar-2020
Category:	Documents
Upload:	others
View:	0 times
Download:	0 times

機械翻訳のための構文解析基礎 - kecl.ntt.co.jp ·...

Documents