【IT Text 自然言語処理の基礎】第9章：構文解析

⾃然⾔語処理の基礎 9章 構⽂解析の概要とその⼿法 京都⼤学⼯学研究科 栗林雷旗 1

構⽂解析の概要とその⼿法 構⽂解析 句構造解析 依存構造解析 ⽂脈⾃由⽂法 CKY法 シフト還元法 ⽂法・確率の学習⽅法を検討 CKY法 シフト還元法 最⼤全域⽊法 2

構⽂解析の概要とその⼿法 構⽂解析 本⽇の発表 句構造解析 依存構造解析 ⽂脈⾃由⽂法 CKY法 シフト還元法 ⽂法・確率の学習⽅法を検討 CKY法 シフト還元法 最⼤全域⽊法 3

構⽂解析と句構造解析 構⽂解析とは • 単語の構造(並び⽅や区切り⽅)による意味解釈の曖昧性にアプローチ →⽬的: ⼊⼒⽂(単語列) 𝒙 = 𝑥! , … , 𝑥" # に対して考えられるすべての 構⽂⽊の集合𝑭 𝒙 の中から最も⼈間の解釈に近いものを出⼒すること 句構造解析とは • 構⽂解析の⼿法のひとつ 句構造 依存構造 • 性質 • 性質 部分単語列のまとまりの階層関係を⽊構造で表現 単語間の関係(主語, ⽬的語など)を表現 • ⽊構造の特徴 • ⽊構造の特徴 葉ノードが単語, 中間ノードは句(単語列のまとまり) ⽊構造のすべてのノードが単語 4

確率⽂脈⾃由⽂法とCKY法 • 確率⽂脈⾃由⽂法: ⽂脈⾃由⽂法に確率を付与したもの。 • このとき構⽂⽊ 𝑇 の確率は 𝑃 𝑇 = $ 𝑃 𝐴→𝛼𝐴 ただし 𝐴 → 𝛼は⽣成規則 !→#∈𝑴 & • • • • 構⽂解析の⽬的は、この𝑃 𝑇 を最⼤にする構⽂ 𝑇 を選ぶことに相当 単純にすべての構⽂⽊を解析すると計算量が指数関数的に増⼤ 動的計画法を⽤いたCKY法により部分構⽂⽊を保存 計算済みの部分構⽂⽊(⼩)を利⽤, 部分構⽂⽊(⼤)も効率的に解析 応⽤ 5

シフト還元法 シフト還元法とは: ⼊⼒単語列を左から順に読み込み、 逐次的に構⽂⽊を構築するアルゴリズム • シフト還元法ではスタックとキューを⽤いる • 還元(Reduce) シフト 𝑆の後ろ⼆つの要素B, Cを取り出し, 𝑆上に⾮終端記号Aを置く 𝑄の先頭の単語xを読み込み, 𝑆上に⾮終端記号Aを置く 還元orシフトのうち実⾏するアクション𝑎は, ) 機械学習により決定 𝑎! = argmax 𝑠 𝑎, 𝑆, 𝑄 !∈𝑨 $,& $ 𝑠 𝑎, 𝑆, 𝑄 : アクション𝑎のスコア 𝑨 𝑆, 𝑄 : 選択可能なアクションの集合 7

確率と⽂法の学習⽅法を検討 • 構⽂解析精度を⾼めるためには, ⽣成規則だけでなく単語の意味 も考慮して⽣成規則の確率を決める必要がある 確率⽂脈⾃由⽂法 単語の意味を含めたモデル 確率パラメータは⽣成規則のみで規定 機械学習⼿法を⽤いて学習 →⼈間から⾒たらありえない解釈も →⾼精度な構⽂解析を実現 8