機械翻訳のための構文解析基礎 †林 克彦 NTTコミュニケーション科学基礎研究所 †[email protected] 構文解析とはどんなタスク？ • 形式的な文法に基づいて自然言語文の構文構造を予測する 構文解析とはどんなタスク？ • 形式的な文法に基づいて自然言語文の構文構造を予測する • 句構造文法 (文脈自由文法)， 依存文法， (組み合わせ)範疇文法， 主辞駆動句構造文法， など 構文解析とはどんなタスク？ • 形式的な文法に基づいて自然言語文の構文構造を予測する • 句構造文法 (文脈自由文法)， 依存文法， (組み合わせ)範疇文法， 主辞駆動句構造文法， など • 句構造文法による構文解析の基本技術を解説 構文解析とはどんなタスク？ • 形式的な文法に基づいて自然言語文の構文構造を予測する • 句構造文法 (文脈自由文法)， 依存文法， (組み合わせ)範疇文法， 主辞駆動句構造文法， など • 句構造文法による構文解析の基本技術を解説 • 確率文脈自由文法 • CKY構文解析 • K-best構文解析の考え方 • 確率文脈自由文法 + 品詞N-gram 句構造木 (Phrase Structure Tree) . S. NP . . PRP . VBD . VP . . . NP DT . NN . . PP . IN . . DT . . I. saw . .. . a. . girl . . with . a. • 再帰的に句を構成していくことで木構造を形成 NP . NN . telescope . 句構造木 (Phrase Structure Tree) . S. NP . . PRP . VBD . VP . . . NP DT . NN . . PP . IN . . DT . 単語列 . I. . .. saw . a. girl . . with . . a. • 再帰的に句を構成していくことで木構造を形成 NP . NN . telescope . 句構造木 (Phrase Structure Tree) . 品詞列 S. NP . . PRP . VBD . VP . . . NP DT . NN . . PP . IN . . DT . 単語列 . I. . .. saw . a. girl . . with . . a. • 再帰的に句を構成していくことで木構造を形成 NP . NN . telescope . 句構造木 (Phrase Structure Tree) . S. 句構造 NP . . 品詞列 PRP . VBD . VP . . . NP DT . NN . . PP . IN . . DT . 単語列 . I. . .. saw . a. . girl . . with . a. • 再帰的に句を構成していくことで木構造を形成 NP . NN . telescope . 句構造木への主辞割当 (Head Annotation) . S(saw) . NP(I) . . PRP . VBD . VP(saw) . NP(girl) . . DT . NN . . .PP(with) IN . NP(tele.) . . DT . . I. saw . .. . a. girl . . with . . a. • ある句の中で最も重要な単語を主辞 (head)と呼ぶ NN . tele. . 句構造木への主辞割当 (Head Annotation) . . saw I.. . PRP . VBD . saw . . . girl DT . NN . . with . IN . . tele. . DT . . I. . .. saw . a. . girl . . with . a. • ある句の中で最も重要な単語を主辞 (head)と呼ぶ • 句ラベルを取り除く NN . tele. . 句構造木への主辞割当 (Head Annotation) . . saw I.. . PRP . VBD . saw . . . girl DT . NN . . with . IN . . tele. . DT . . I. . .. saw . a. . girl . . with . a. • ある句の中で最も重要な単語を主辞 (head)と呼ぶ • 句ラベルを取り除く • 主辞間の係り受け関係を作る NN . tele. . 依存構造木 (Dependency Tree) $. . $. I. . PRP . saw . . VBD . a. . DT . girl . .. NN . with . . IN . a. . DT . telescope . . NN . 依存構造木 (Dependency Tree) $. . $. I. . PRP . saw . . VBD . a. . DT . girl . .. NN . • 単語間の関係を直接記述した構文木 with . . IN . a. . DT . telescope . . 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. . NP . . PRP . VBD . VP . . . NP DT . NN . . PP . IN . . DT . . I. saw . .. . a. . girl . . with . a. • 確率文脈自由文法 G = (VN ,VT , P, S) (北, 1999) NP . NN . telescope . 確率文脈自由文法: 定義 S. . NP . . PRP . VBD . VP . . . NP DT . NN . . PP . IN . . DT . . I. saw . .. . a. . girl . . with . a. • 確率文脈自由文法 G = (VN ,VT , P, S) (北, 1999) • VN : 非終端記号の集合. 例: VP, NP, DT NP . NN . telescope . 確率文脈自由文法: 定義 S. . NP . . PRP . VBD . VP . . . NP DT . NN . . PP . IN . . DT . . I. saw . .. . a. . girl . . with . a. • 確率文脈自由文法 G = (VN ,VT , P, S) (北, 1999) • VN : 非終端記号の集合. 例: VP, NP, DT • VT : 終端記号の集合. 例: I, with NP . NN . telescope . 確率文脈自由文法: 定義 S. . NP . . PRP . VBD . VP . . . NP DT . NN . . PP . IN . . NP . DT . . I. saw . .. . a. . girl . . with . a. NN . telescope . • 確率文脈自由文法 G = (VN ,VT , P, S) (北, 1999) • VN : 非終端記号の集合. 例: VP, NP, DT • VT : 終端記号の集合. 例: I, with 0.8 • P: 確率生成規則の集合. 例: NP −→ DT NN 確率文脈自由文法: 定義 S. . NP . . PRP . VBD . VP . . . NP DT . NN . . PP . IN . . NP . DT . . I. saw . .. . a. . girl . . with . a. NN . telescope . • 確率文脈自由文法 G = (VN ,VT , P, S) (北, 1999) • VN : 非終端記号の集合. 例: VP, NP, DT • VT : 終端記号の集合. 例: I, with 0.8 • P: 確率生成規則の集合. 例: NP −→ DT NN 確率文脈自由文法: 定義 S. . NP . . PRP . VBD . VP . . . NP DT . NN . . PP . IN . . DT . . I. saw . .. . a. . girl . . with . a. NP . NN . telescope . • 確率文脈自由文法 G = (VN ,VT , P, S) (北, 1999) • VN : 非終端記号の集合. 例: VP, NP, DT • VT : 終端記号の集合. 例: I, with 0.8 • P: 確率生成規則の集合. 例: NP −→ DT NN • S: 開始記号. TOPなどの記号がよく使われるが, ここではSを使う. 確率文脈自由文法による句構造木予測モデル • 入力文xとその句構造木yがある *導出(x, y) = r1 ⇒ r2 ⇒ · · · ⇒ rm *規則の適用確率は前に適用された規則の影響を受けない 確率文脈自由文法による句構造木予測モデル • 入力文xとその句構造木yがある • xとyが同時に生成される確率モデルを仮定し, ŷ = argmax p(x, y) = argmax p(r1 , r2 , . . . , rm ) y∈Y y∈Y = argmax Πm i=1 p(ri ) y∈Y *導出(x, y) = r1 ⇒ r2 ⇒ · · · ⇒ rm *規則の適用確率は前に適用された規則の影響を受けない • 上式の最適化は動的計画法による効率的な解析が可能 • CKY法, アーリー法, 一般化LR法 生成規則 = 演繹推論規則 前件部 z }| { PP NP VBD : p3 : p2 : p1 . i (Shieber, 95) . k+1 k j . j+1 ℓ p VP − → VBD NP PP VP : p1 × p2 × p3 × p . i | ℓ {z } 後件部 • 規則のアイテム (三角)は句構造木の部分木に対応 • アイテムは単語スパン，ルートの非終端記号，累積確率を持つ • 規則が適用されると， 前件部を後件部で置き換える 構文解析 = 演繹推論規則による導出過程 . 0.9 NP . 0.7 1.0 1.0 VBD . . . saw 4 0.9 1.0 VBD −−→ saw VBD 1.0 . 0 . VP . 0.7 1.0 . 3 2 1.0 PRP −−→ I PRP 1.0 I. 1.0 . 1 1 . 1 1 1.0 0.9 . 3 2 NN −−→ girl NN 4 0.7 NN . 0.9 . 0 0.7 NP −−→ PRP NP PRP . . S. girl saw I . 0 0.7 . 1 1 girl . VP −−→ VBD NP VP 0.63 4 0.9 S −−→ NP VP S . 0 0.3969 4 • 単語 = 演繹推論の公理 • 生成規則 = 推論規則 • 解析完了 (終了記号) = 推論のゴール 構文解析の計算量 : p3 : p2 : p1 . i PP NP VBD . k+1 k j . j+1 p → VBD NP PP VP − VP : p1 × p2 × p3 × p . i ℓ ℓ • 規則に出現する単語インデックスの数: i, k, j, ℓ 構文解析の計算量 : p3 : p2 : p1 . i PP NP VBD . k+1 k j . j+1 ℓ p → VBD NP PP VP − VP : p1 × p2 × p3 × p . i ℓ • 規則に出現する単語インデックスの数: i, k, j, ℓ • 入力文の単語数n， 規則に出現する単語インデックスの数x • 動的計画法による計算量: O(nx ) (上の場合O(n4 )) (McAllester, 01) 構文解析の計算量 : p3 : p2 : p1 . i PP NP VBD . k+1 k j . j+1 ℓ p → VBD NP PP VP − VP : p1 × p2 × p3 × p . i ℓ • 規則に出現する単語インデックスの数: i, k, j, ℓ • 入力文の単語数n， 規則に出現する単語インデックスの数x • 動的計画法による計算量: O(nx ) (上の場合O(n4 )) (McAllester, 01) • 解析効率を上げるため， 一般には規則の二分化が必要 構文解析の計算量 : p3 : p2 : p1 . i PP NP VBD . k+1 k j . j+1 ℓ p → VBD NP PP VP − VP : p1 × p2 × p3 × p . i ℓ • 規則に出現する単語インデックスの数: i, k, j, ℓ • 入力文の単語数n， 規則に出現する単語インデックスの数x • 動的計画法による計算量: O(nx ) (上の場合O(n4 )) (McAllester, 01) • 解析効率を上げるため， 一般には規則の二分化が必要 *アーリー法は解析時， 動的に二分化を行う チョムスキー標準形 • チョムスキー標準形 • 生成規則の形式は次の2つだけをとる • A → B C (A, B, C∈ VN ) • A → a (A∈ VN , a∈ VT ) チョムスキー標準形 • チョムスキー標準形 • 生成規則の形式は次の2つだけをとる • A → B C (A, B, C∈ VN ) • A → a (A∈ VN , a∈ VT ) *実用上, A → B (A, B∈ VN )のようなunary規則も残すことが多い チョムスキー標準形 • チョムスキー標準形 • 生成規則の形式は次の2つだけをとる • A → B C (A, B, C∈ VN ) • A → a (A∈ VN , a∈ VT ) *実用上, A → B (A, B∈ VN )のようなunary規則も残すことが多い • 生成規則の二分化 (Binarization) . . . X1 X.p X2 . X3 . X4 . チョムスキー標準形 • チョムスキー標準形 • 生成規則の形式は次の2つだけをとる • A → B C (A, B, C∈ VN ) • A → a (A∈ VN , a∈ VT ) *実用上, A → B (A, B∈ VN )のようなunary規則も残すことが多い • 生成規則の二分化 (Binarization) . . . . X1 X.p X.p X2 . X3 . X4 . . . X1 . X2'. 1.0 . . X2 X3 . X4 . チョムスキー標準形 • チョムスキー標準形 • 生成規則の形式は次の2つだけをとる • A → B C (A, B, C∈ VN ) • A → a (A∈ VN , a∈ VT ) *実用上, A → B (A, B∈ VN )のようなunary規則も残すことが多い • 生成規則の二分化 (Binarization) . . . . . X1 . . X1 X.p X2 . X3 . X4 . . . X1 X.p X.p . X2'. 1.0 . . X2 X3 . X4 . .X2'. 1.0 . . X2 X3' . . 1.0 . . X3 X4 . CKY 構文解析: 三角表の初期化 • 入力文xの長さがnとすると, nに対する三角表を構築 . 0I 1 2 aw 1s 2a 3 ir 3g l4 ith 5 4w 5a e7 6 p co es tel 6 CKY 構文解析: 終端記号に対する規則の適用 • 入力文xの単語に非終端記号を割り当てる 0 NP1 . 0 PRP1 0I 1 1 VBD2 w2 sa 1 2 DT3 3 2a 3 NN4 irl 4 3g 4 IN5 ith 5 4w 6 NN7 5 DT6 6 5a es tel 6 p co e7 CKY 構文解析: より大きなスパンの構築 • 2単語スパンの構築 (生成規則NP → DT NN) . 0 PRP1 0I 1 5 NP7 2 NP4 0 NP1 1 VBD2 w2 sa 1 2 DT3 3 2a 3 NN4 irl 4 3g 4 IN5 ith 5 4w 6 NN7 5 DT6 6 5a 6t s ele p co e7 CKY 構文解析: より大きなスパンの構築 • 3単語スパンの構築 (生成規則VP → VBD NP, PP → IN NP) 4 PP7 1 VP4 . 0 PRP1 0I 1 5 NP7 2 NP4 0 NP1 1 VBD2 w2 sa 1 2 DT3 3 2a 3 NN4 irl 4 3g 4 IN5 ith 5 4w 6 NN7 5 DT6 6 5a 6t s ele p co e7 CKY 構文解析: より大きなスパンの構築 • 4単語スパンの構築 (生成規則S → NP VP) 0 S4 4 PP7 1 VP4 . 0 PRP1 0I 1 5 NP7 2 NP4 0 NP1 1 VBD2 w2 sa 1 2 DT3 3 2a 3 NN4 irl 4 3g 4 IN5 ith 5 4w 6 NN7 5 DT6 6 5a 6t s ele p co e7 CKY 構文解析: より大きなスパンの構築 • 5単語スパンの構築 (生成規則NP → NP PP) 2 NP7 0 S4 4 PP7 1 VP4 . 0 PRP1 0I 1 5 NP7 2 NP4 0 NP1 1 VBD2 w2 sa 1 2 DT3 3 2a 3 NN4 irl 4 3g 4 IN5 ith 5 4w 6 NN7 5 DT6 6 5a 6t s ele p co e7 CKY 構文解析: より大きなスパンの構築 • 6単語スパンの構築 (生成規則VP → VBD NP, VP → VP PP) 1 VP7 1 VP7 2 NP7 0 S4 4 PP7 1 VP4 . 0 PRP1 0I 1 5 NP7 2 NP4 0 NP1 1 VBD2 w2 sa 1 2 DT3 3 2a 3 NN4 irl 4 3g 4 IN5 ith 5 4w 6 NN7 5 DT6 6 5a 6t s ele p co e7 CKY 構文解析: より大きなスパンの構築 • 6単語スパンの構築 (生成規則VP → VBD NP, VP → VP PP) 累積確率の高い方を残す! 1 VP7 1 VP7 2 NP7 0 S4 4 PP7 1 VP4 . 0 PRP1 0I 1 5 NP7 2 NP4 0 NP1 1 VBD2 w2 sa 1 2 DT3 3 2a 3 NN4 irl 4 3g 4 IN5 ith 5 4w 6 NN7 5 DT6 6 5a 6t s ele p co e7 CKY 構文解析: より大きなスパンの構築 • 7単語スパンの構築 (生成規則S → NP VP) 0 S7 1 VP7 1 VP7 2 NP7 0 S4 4 PP7 1 VP4 . 0 PRP1 0I 1 5 NP7 2 NP4 0 NP1 1 VBD2 w2 sa 1 2 DT3 3 2a 3 NN4 irl 4 3g 4 IN5 ith 5 4w 6 NN7 5 DT6 6 5a 6t s ele p co e7 CKY 構文解析: バックトレース • バックトレースして確率が最大となる構文木ŷを出力 0 S7 1 VP7 1 VP7 2 NP7 0 S4 4 PP7 1 VP4 . 0 PRP1 0I 1 5 NP7 2 NP4 0 NP1 1 VBD2 w2 sa 1 2 DT3 3 2a 3 NN4 irl 4 3g 4 IN5 th 5 wi 4 6 NN7 5 DT6 6 5a pe 7 co es tel 6 CKY構文解析の計算量 • 規則は全て二分化されている = 前件部は1 or 2個のアイテム数 NP VBD : p2 : p1 . i . k+1 k j p → VBD NP VP − VP : p1 × p2 × p . i j • 規則に出現する単語インデックスの数: i, k, j • 入力文の単語数n • 動的計画法による構文解析の計算量: O(n3 ) K-best構文解析 • 複数の構文木が欲しい . S. . NP . PRP . VP . . VP . VBD . . DT . NN IN . S. NP . . . . NP DT . VP . . VBD . PRP . . PP . . NP . . NN . NP . . . NP . DT . NN . . PP IN . . NP . DT . . I. . . a. .. saw girl . . with . . a. tele. . . I. . . a. . saw . girl . . with . . a. NN . tele. . K-best構文解析 • K個の同一アイテムを残す 累積確率の高い方を残す! 1 VP7 1 VP7 2 NP7 0 S4 4 PP7 1 VP4 . 0 PRP1 0I 1 5 NP7 2 NP4 0 NP1 1 VBD2 w2 sa 1 2 DT3 3 2a 3 NN4 irl 4 3g 4 IN5 ith 5 4w 6 NN7 5 DT6 6 5a es tel 6 p co e7 K-best構文解析 • K個の同一アイテムを残す 累積確率の高いK個を残す! 1 VP7 1 VP7 2 NP7 0 S4 4 PP7 1 VP4 . 0 PRP1 0I 1 5 NP7 2 NP4 0 NP1 1 VBD2 w2 sa 1 2 DT3 3 2a 3 NN4 irl 4 3g 4 IN5 ith 5 4w 6 NN7 5 DT6 6 5a es tel 6 p co e7 K-best構文解析 • 累積確率上位K個のアイテムを効率的に求める (Huang and Chiang, 05) • 例: 1 S7となる累積確率上位3個を求める (3 × 3 + 3 × 3 = 18通り) 4 VP7 0.5 S −−→ NP VP 1 NP4 0.6 0.9 0.5 0.3 priority queue: 3-best: 0.4 2 PP7 0.3 0.3 S −−→ NP PP 1 NP2 0.8 0.4 0.2 0.8 0.2 0.1 K-best構文解析 • 累積確率上位K個のアイテムを効率的に求める (Huang and Chiang, 05) • 例: 1 S7となる累積確率上位3個を求める (3 × 3 + 3 × 3 = 18通り) 4 VP7 0.5 S −−→ NP VP 1 NP4 0.9 0.5 0.3 0.6 0.4 0.3 S −−→ NP PP 0.27 priority queue: 0.27 0.192 3-best: 2 PP7 0.3 1 NP2 0.8 0.4 0.2 0.8 0.192 0.2 0.1 K-best構文解析 • 累積確率上位K個のアイテムを効率的に求める (Huang and Chiang, 05) • 例: 1 S7となる累積確率上位3個を求める (3 × 3 + 3 × 3 = 18通り) 4 VP7 0.5 S −−→ NP VP 1 NP4 0.9 0.5 0.3 0.6 0.4 2 PP7 0.3 0.18 0.15 priority queue: 0.192 0.18 0.15 3-best: 0.27 0.3 S −−→ NP PP 1 NP2 0.8 0.4 0.2 0.8 0.192 0.2 0.1 K-best構文解析 • 累積確率上位K個のアイテムを効率的に求める (Huang and Chiang, 05) • 例: 1 S7となる累積確率上位3個を求める (3 × 3 + 3 × 3 = 18通り) 4 VP7 0.5 S −−→ NP VP 1 NP4 0.9 0.5 0.3 0.6 0.4 2 PP7 0.3 0.3 S −−→ NP PP 0.18 0.15 priority queue: 3-best: 0.27 0.192 1 NP2 0.18 0.15 0.096 0.048 0.8 0.4 0.2 0.8 0.2 0.048 0.096 0.1 K-best構文解析 • 累積確率上位K個のアイテムを効率的に求める (Huang and Chiang, 05) • 例: 1 S7となる累積確率上位3個を求める (3 × 3 + 3 × 3 = 18通り) 2 PP7 4 VP7 0.5 S −−→ NP VP 1 NP4 0.9 0.5 0.3 0.6 0.4 0.3 S −−→ NP PP 1 NP2 0.15 priority queue: 0.3 0.15 0.096 0.048 3-best: 0.27 0.192 0.18 0.8 0.4 0.2 0.8 0.2 0.048 0.096 0.1 系列ラベリングとしての品詞タグ付け n+1 • 品詞タグ付けラティス: 単語列wn+1 0 と品詞列pos0 t =0 t =1 t =2 t =3 t =4 I/VBD saw/VBD a/VBD girl/VBD I/PRP saw/PRP a/PRP girl/PRP <s>/<s> t =5 </s>/</s> I/NN saw/NN a/NN girl/NN I/DT saw/DT a/DT girl/DT . 系列ラベリングとしての品詞タグ付け n+1 • 品詞タグ付けラティス: 単語列wn+1 0 と品詞列pos0 t =0 t =1 t =2 t =3 t =4 I/VBD saw/VBD a/VBD girl/VBD I/PRP saw/PRP a/PRP girl/PRP <s>/<s> t =5 </s>/</s> I/NN saw/NN a/NN girl/NN I/DT saw/DT a/DT girl/DT . 系列ラベリングとしての品詞タグ付け n+1 • 品詞タグ付けラティス: 単語列wn+1 0 と品詞列pos0 t =0 t =1 t =2 t =3 t =4 I/VBD saw/VBD a/VBD girl/VBD I/PRP saw/PRP a/PRP girl/PRP <s>/<s> t =5 </s>/</s> I/NN saw/NN a/NN girl/NN I/DT saw/DT a/DT girl/DT . 系列ラベリングとしての品詞タグ付け n+1 • 品詞タグ付けラティス: 単語列wn+1 0 と品詞列pos0 t =0 t =1 t =2 t =3 t =4 I/VBD saw/VBD a/VBD girl/VBD I/PRP saw/PRP a/PRP girl/PRP <s>/<s> t =5 </s>/</s> I/NN saw/NN a/NN girl/NN I/DT saw/DT a/DT girl/DT . 系列ラベリングとしての品詞タグ付け n+1 • 品詞タグ付けラティス: 単語列wn+1 0 と品詞列pos0 t =0 t =1 t =2 t =3 t =4 I/VBD saw/VBD a/VBD girl/VBD I/PRP saw/PRP a/PRP girl/PRP <s>/<s> t =5 </s>/</s> I/NN saw/NN a/NN girl/NN I/DT saw/DT a/DT girl/DT . 系列ラベリングとしての品詞タグ付け n+1 • 品詞タグ付けラティス: 単語列wn+1 0 と品詞列pos0 t =0 t =1 t =2 t =3 t =4 I/VBD saw/VBD a/VBD girl/VBD I/PRP saw/PRP a/PRP girl/PRP <s>/<s> t =5 </s>/</s> I/NN saw/NN a/NN girl/NN I/DT saw/DT a/DT girl/DT . 系列ラベリングとしての品詞タグ付け n+1 • 品詞タグ付けラティス: 単語列wn+1 0 と品詞列pos0 t =0 t =1 t =2 t =3 t =4 I/VBD saw/VBD a/VBD girl/VBD I/PRP saw/PRP a/PRP girl/PRP <s>/<s> t =5 </s>/</s> I/NN saw/NN a/NN girl/NN I/DT saw/DT a/DT girl/DT • 隠れマルコフモデルによる系列ラベリング P(posn0 |w. n0 ) ⇒ = P(posn0 ) × P(wn0 |posn0 ) ≈ n+1 n Πt=1 P(post |post−1 ) × Πt=1 P(wt |post ) 品詞2-gramモデルとの結合 . <s> . S. NP . . PRP . VBD . </s> . VP . . . NP DT . NN . . PP . IN . . DT . . .. <s> I. . .. saw . a. girl . . with . . a. NP . NN . telescope . </s> . 品詞2-gramモデルとの結合 . S. P(PRP¦<s>) <s> . NP . . PRP . VBD . </s> . VP . . . NP DT . NN . . PP . IN . . DT . . .. <s> I. . .. saw . a. girl . . with . . a. NP . NN . telescope . </s> . 品詞2-gramモデルとの結合 . S. P(PRP¦<s>) <s> . NP . PRP . . VBD . </s> . VP . P(VBD¦PRP) . . NP DT . NN . . PP . IN . . DT . . .. <s> I. . .. saw . a. girl . . with . . a. NP . NN . telescope . </s> . 品詞2-gramモデルとの結合 . S. P(PRP¦<s>) <s> . NP . PRP . . VBD . </s> . VP . P(VBD¦PRP) P(DT¦VBD) . . NP DT . NN . . PP . IN . . DT . . .. <s> I. . .. saw . a. girl . . with . . a. NP . NN . telescope . </s> . 品詞2-gramモデルとの結合 . S. P(PRP¦<s>) <s> . NP . PRP . . VBD . </s> . VP . P(VBD¦PRP) P(DT¦VBD) . . NP . PP . IN . . P(NN¦DT) DT . NN . DT . . .. <s> I. . .. saw . a. girl . . with . . a. NP . NN . telescope . </s> . 品詞2-gramモデルとの結合 . S. P(PRP¦<s>) <s> . NP . PRP . . VBD . </s> . VP . P(VBD¦PRP) P(DT¦VBD) . . NP . PP . P(NN¦DT) P(IN¦NN) DT . NN . IN . . DT . . .. <s> I. . .. saw . a. girl . . with . . a. NP . NN . telescope . </s> . 品詞2-gramモデルとの結合 . S. P(PRP¦<s>) <s> . NP . PRP . . VBD . </s> . VP . P(VBD¦PRP) P(DT¦VBD) . . NP . PP . P(NN¦DT) P(IN¦NN) DT . NN . IN . . P(DT¦IN) DT . . .. <s> I. . .. saw . a. girl . . with . . a. NP . NN . telescope . </s> . 品詞2-gramモデルとの結合 . S. P(PRP¦<s>) <s> . NP . PRP . . VBD . </s> . VP . P(VBD¦PRP) P(DT¦VBD) . . NP . PP . P(NN¦DT) P(IN¦NN) DT . NN . IN . . P(DT¦IN) DT . . .. <s> I. . .. saw . a. girl . . with . . a. NP . P(NN¦DT) NN . telescope . </s> . 品詞2-gramモデルとの結合 . S. P(</s>¦NN) P(PRP¦<s>) <s> . NP . PRP . . VBD . </s> . VP . P(VBD¦PRP) P(DT¦VBD) . . NP . PP . P(NN¦DT) P(IN¦NN) DT . NN . IN . . P(DT¦IN) DT . . .. <s> I. . .. saw . a. girl . . with . . a. NP . P(NN¦DT) NN . telescope . </s> . 品詞2-gramモデルとの結合 . S. P(</s>¦NN) P(PRP¦<s>) <s> . . NP . PRP . VBD . </s> . VP . P(VBD¦PRP) P(DT¦VBD) . . NP . PP . P(NN¦DT) P(IN¦NN) DT . NN . IN . . P(DT¦IN) DT . . .. <s> I. . .. saw . a. . girl . . with . a. NP . P(NN¦DT) NN . telescope . • 確率文脈自由文法と品詞2-gramの結合モデル n+1 ŷ = argmax Πm i=1 p(ri )×Π j=1 p(pos j |pos j−1 ) y∈Y </s> . 結合モデルによるCKY構文解析の計算量 • 各アイテムは両端に品詞を記憶する必要がある NP VBD : p2 : p1 . i, posi k, posk . k + 1, posk+1 j, pos j p VP − → VBD NP VP . i, posi : p1 × p2 × p × P(posk+1 |posk ) j, pos j 結合モデルによるCKY構文解析の計算量 • 各アイテムは両端に品詞を記憶する必要がある NP VBD : p2 : p1 . i, posi k, posk . k + 1, posk+1 j, pos j p VP − → VBD NP VP . i, posi : p1 × p2 × p × P(posk+1 |posk ) j, pos j • 単語インデックスの数と品詞タグの数: i, k, j, posi , posk , posk+1 , pos j 結合モデルによるCKY構文解析の計算量 • 各アイテムは両端に品詞を記憶する必要がある NP VBD : p2 : p1 . i, posi k, posk . k + 1, posk+1 j, pos j p VP − → VBD NP VP . i, posi : p1 × p2 × p × P(posk+1 |posk ) j, pos j • 単語インデックスの数と品詞タグの数: i, k, j, posi , posk , posk+1 , pos j • 入力文の単語数n， 品詞タグ集合のサイズ|Vpos | • CKY構文解析の計算量: O(n3 |Vpos |4 ) Hookトリックによる計算量の削減 (Huang, 05) VBD : p1 . i, posi . k + 1, posk+1 k, posk : 1.0 NP . i, posi p VP − → VBD NP VP NP : p1 × p × P(posk+1 |posk ) : p2 . k + 1, posk+1 k + 1, posk+1 VP . i, posi : p1 × p2 × p × P(posk+1 |posk ) j, pos j • 2-gramを先に連結することでO(n3 |Vpos |3 )にできる j, pos j まとめ • 確率文脈自由文法 まとめ • 確率文脈自由文法 ⇒ 同期文脈自由文法による翻訳 (Chiang, 07) まとめ • 確率文脈自由文法 ⇒ 同期文脈自由文法による翻訳 • CKY構文解析 (Chiang, 07) まとめ • 確率文脈自由文法 ⇒ 同期文脈自由文法による翻訳 (Chiang, 07) • CKY構文解析 ⇒ 同期文脈自由文法による翻訳のデコーダ (Chiang, 07) まとめ • 確率文脈自由文法 ⇒ 同期文脈自由文法による翻訳 (Chiang, 07) • CKY構文解析 ⇒ 同期文脈自由文法による翻訳のデコーダ • 品詞タグ付けとの結合モデル (Chiang, 07) まとめ • 確率文脈自由文法 ⇒ 同期文脈自由文法による翻訳 (Chiang, 07) • CKY構文解析 ⇒ 同期文脈自由文法による翻訳のデコーダ (Chiang, 07) • 品詞タグ付けとの結合モデル ≈ 同期文脈自由文法による翻訳 + N-gram言語モデル (Chiang, 07) まとめ • 確率文脈自由文法 ⇒ 同期文脈自由文法による翻訳 (Chiang, 07) • CKY構文解析 ⇒ 同期文脈自由文法による翻訳のデコーダ (Chiang, 07) • 品詞タグ付けとの結合モデル ≈ 同期文脈自由文法による翻訳 + N-gram言語モデル • K-best構文解析 (Chiang, 07) まとめ • 確率文脈自由文法 ⇒ 同期文脈自由文法による翻訳 (Chiang, 07) • CKY構文解析 ⇒ 同期文脈自由文法による翻訳のデコーダ (Chiang, 07) • 品詞タグ付けとの結合モデル ≈ 同期文脈自由文法による翻訳 + 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/ 参考文献 • Marcus et. al., ``Building a large annotated corpus of English'', 1993. • Xue et. al., ``The Penn Chinese TreeBank: Phrase structure annotation of a large corpus'', 2005. • Butler et. al., ``Keyaki Treebank: phrase structure with functional information for Japanese'', 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, ``A Syntax-based Statistical Translation Model'', 2001. • Graehl and Knight, ``Training Tree Transducers'', 2004. • Shen et. al., ``A New String-to-Dependency Machine Translation Algorithm with a Target Dependency Language Model, 2008. • Schwaltz et. al., ``Incremental Syntactic Language Models for Phrase-based Translation'', 2010. • Chiang, ``Hierarchical Phrase-based Translation'', 2007. • 北, ``言語と計算4 確率的言語モデル'', 1999. • Shieber et. al., ``Principles and Implementation of Deductive Parsing'', 1995. • McAllester, ``On 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.
© Copyright 2024 ExpyDoc
