今日の内容自然言語処理システム特論構文解析 • 構文解析とは？ Natural Language Processing Systems 第５回 • 句構造解析 • 係り受け解析 2015/5/12 – 文節区切り決定のアルゴリズム芝浦工業大学工学部情報工学科杉本徹 [email protected] – 係り受け関係決定のアルゴリズム実験課題：今後の日程復習：自然言語の解析処理の流れ構文解析とは？入力文「太郎は本を読んだ。」 ① 形態素解析太郎は本を読んだ ② 構文解析名助名助動助動太郎は本を読んだ ③ 意味解析 agent taro ④ 文脈解析構文解析（Syntactic Analysis / Parsing） • 与えられた文に含まれる，単語のまとまり（句）や単語間の修飾関係などの構文構造を求める 1. 句構造解析・・・文の句構造を求める 2. 係り受け解析・・・文の係り受け構造を求める • 構文解析を行うことにより， – 文の主語と述語がわかる – 修飾語と被修飾語の関係がわかる – 省略された要素の有無がわかる object book 複数の文にまたがる処理構文構造（Syntactic Structure） • 句構造／構成素構造（Phrase/Constituent Structure） – 隣り合う複数の構文要素が形成するまとまり（句）に着目 – 構文規則の例 • ２種類の解析方法 read 構文木文 → 後置詞句動詞句後置詞句 → 名詞句助詞 • 係り受け構造／依存構造（Dependency Structure）文の理解に不可欠 – 文中の要素間の相互依存関係（係り受け関係）に着目 1 構文構造（Syntactic Structure） • 句構造／構成素構造（Phrase/Constituent Structure） – 隣り合う複数の構文要素が形成するまとまり（句）に着目１．句構造解析 – 構文規則の例構文木文 → 後置詞句動詞句後置詞句 → 名詞句助詞 • 係り受け構造／依存構造（Dependency Structure） – 文中の要素間の相互依存関係（係り受け関係）に着目簡単な文脈自由文法の例句構造文法（Chomsky, 1956） • 言語の構文パターンを，言語表現や言語表現の範疇（category）の列の書き換え規則 Α1 A2 … An → B1 B2 … Bm • 構文規則（syntax rules）文名詞 → 動詞 → 助詞 → 助動詞 → → 後置詞句動詞句後置詞句 → 名詞助詞動詞句 → 動詞助動詞の集合によって記述する • 構文木（parse tree） • 句構造文法の種類 – 文脈自由文法（Context Free Grammar）文後置詞句 • 上記の書き換え規則において，n = 1 に限定名詞 – 他に O型文法，文脈依存文法，正則文法（正規表現）などがある赤ちゃん笑う（笑っ）がた動詞句助詞動詞助動詞赤ちゃんが笑った。構文木（parse tree）もう少し複雑な文脈自由文法の例文動詞句文 → 後置詞句動詞句後置詞句 → 名詞句助詞名詞 → 僕｜本｜図書館名詞句 → 名詞動詞 → 読む｜借りる名詞句 → 形容詞名詞句形容詞 → 分厚い名詞句 → 動詞句名詞句副詞 → 昨日（注）動詞句 → 動詞助動詞助詞 → は｜を｜で動詞句 → 後置詞句動詞句助動詞 → た｜だ動詞句 → 副詞動詞句（注）「昨日」は本来名詞であるが，副詞的に使うことができるので，ここでは便宜上副詞に分類する後置詞句名詞句動詞句動詞句後置詞句名詞句後置詞句名詞句名詞句動詞句名詞句動詞句名詞助詞副詞名詞助詞動詞助動詞形容詞名詞助詞動詞助動詞僕は昨日図書館で借りた分厚い本を読んだ． 2 構文木（別の解釈）構文木（さらに別の解釈）文文動詞句動詞句動詞句動詞句動詞句後置詞句後置詞句名詞句名詞句動詞句後置詞句名詞句後置詞句名詞句名詞句動詞句後置詞句動詞句名詞句名詞句後置詞句名詞句名詞句動詞句動詞句名詞句名詞助詞副詞名詞助詞動詞助動詞形容詞名詞助詞動詞助動詞名詞助詞副詞名詞助詞動詞助動詞形容詞名詞助詞動詞助動詞僕は昨日図書館で借りた分厚い本を読んだ．僕は昨日図書館で借りた分厚い本を読んだ．句構造文法に基づく構文解析 • 与えられた文に対して，その構文木を求める • ボトムアップ解析（BU） vs トップダウン解析（TD） • 非決定性に配慮が必要（自然言語処理では，一般の文脈自由文法に対する効率的な構文解析アルゴリズムが必要） – チャート解析（BU/TD），CYK法（BU），Early法（TD），一般化LR法（BU）など – いずれも解析の途中結果（部分解析木）を記録することにより（動的計画法），計算量 O(n3)で解析できる • 参考：プログラミング言語に対するLL／LR解析文脈自由文法における課題 • 一致（数，性など）の扱い例（英語）：名詞句 → 冠詞名詞 “a boy” はＯＫだが，“a boys” はＮＧ • 動詞の格構造，語順の任意性 – 例：「私が本を読む」，「本を私が読む」はＯＫ – 「私が本が読む」，「私を本を読む」はNG – 「私が本を笑う」，「私で本を読む」はＮＧ – 人工言語の場合，文法設計時の工夫により，決定的に構文解析できるようにできる（計算量 O(n)）文脈自由文法の拡張単一化文法（Unification Grammar） • 品詞記号を素性構造（feature structure）に拡張品詞＝名詞人称＝3人称数＝単数品詞＝名詞 "boys" 人称＝3人称数＝複数品詞＝冠詞 "a" 人称＝3人称数＝単数 • 構文規則の例品詞＝名詞句人称＝Ｘ数＝Ｙ • 語彙項目の例品詞＝動詞「読む」必須格＝{が,を} • 語彙項目の例 "boy" 動詞の格構造の扱い品詞＝冠詞人称＝Ｘ数＝Ｙ品詞＝名詞人称＝Ｘ数＝Ｙ「笑う」品詞＝動詞必須格＝{が} 「が」品詞＝助詞格＝が • 構文規則の例品詞＝後置詞句格＝ X 品詞＝動詞句必須格＝S – {X} 品詞＝名詞品詞＝後置詞句格＝ X 品詞＝助詞格＝ X 品詞＝動詞（句）必須格＝ S ただし，X ∈ S 3 単一化文法の例 • HPSG （Head-driven Phrase Structure Grammar） [Pollard & Sag 1987] ２．係り受け解析 • LFG （Lexical Functional Grammar） [Kaplan & Bresnan 1982] • 特徴 – 素性構造の単一化（unification）に基づく計算の仕組み – 語彙（単語）に文法的な情報をなるべく多く埋め込む構文構造（Syntactic Structure） • 句構造／構成素構造（Phrase/Constituent Structure） – 隣り合う複数の構文要素が形成するまとまり（句）に着目 – 構文規則の例構文木文 → 後置詞句動詞句後置詞句 → 名詞句助詞 • 係り受け構造／依存構造（Dependency Structure） – 文中の要素間の相互依存関係（係り受け関係）に着目依存構造（dependency structure） • 句構造が言語表現を「全体－部分」の関係を基に構造化するのに対して，依存構造は言語表現の部分間の依存関係を基に構造を考える • 参考：英文の場合 I read a book yesterday . • 日本語の場合は，文節を単位として依存関係（係り受け関係）を考えるのが一般的 – 文節の係り受け関係の向きは，必ず「左 → 右」係り受け構造 • 文節 – 文を意味に沿って区切った時の最小単位で，１つの自立語といくつかの付属語から構成される係り受け構造（続き） • 別の解釈僕は昨日図書館で借りた分厚い本を読んだ． • 文節の係り受け（依存）関係僕は昨日図書館で借りた分厚い本を読んだ．僕は昨日図書館で借りた分厚い本を読んだ． 4 係り受け構造（続き） • 不可能な解釈係り受け解析の流れ駅（形態素解析 ⇒）単語列僕は昨日図書館で借りた分厚い本を読んだ．で彼女を名詞助詞代名詞助詞駅で見た動詞助動詞 (1) 文節区切りの決定文節列名詞助詞彼女を代名詞助詞見た動詞助動詞 • 非交差性の条件 (2)係り受け関係の決定 – 文節の係り受け関係どうしが交差してはならない係り受け構造駅で名詞助詞彼女を代名詞助詞見た動詞助動詞 CaboCha の使い方係り受け解析ツールの例 • CaboCha を起動し，解析したい文を標準入力から入力する • CaboCha （工藤拓，2002～） – 条件付き確率場（CRF）を用いた文節区切り – Support Vector Machine (SVM) を用いた係り受け判定 – 局所的な係り受け判定の繰り返しによる効率的な解析（O(n)） • KNP（京都大，1993～） – Web から自動構築した大規模格フレームを用いた，統合的確率モデルにより解析を行う – CaboCha より解析速度が遅いが，述語項構造解析など高度な解析の結果を出力できる • Yahoo! 日本語係り受け解析API – Web 上で係り受け解析を実行できる Web サービス入力文文節番号 % cabocha –f1 駅で彼女を見た。 * 0 2D 0/1 -1.946565 駅で名詞,一般,*,*,*,*,駅,エキ,エキ助詞,格助詞,一般,*,*,*,で,デ,デ * 1 2D 0/1 -1.946565 文節彼女を名詞,代名詞,一般,*,*,*,彼女,カノジョ,カノジョ助詞,格助詞,一般,*,*,*,を,ヲ,ヲ * 2 -1D 0/1 0.000000 係り先の文節番号見た。動詞,自立,*,*,一段,連用形,見る,ミ,ミ助動詞,*,*,*,特殊・タ,基本形,た,タ,タ記号,句点,*,*,*,*,。,。,。 EOS • または，解析したい文章を１文ずつ行に区切ってテキストファイルに保存し，そのファイル名を引数としてCaboChaを実行する分類器（classifier） (1) 文節区切り決定のアルゴリズム • 入力データを（あらかじめ決めておいた）複数のカテゴリの中のどれかに分類する y = f(x) x: 入力データ y: 出力（カテゴリ） • 例：入力された人名を俳優か研究者に分類する CaboCha は条件付き確率場（CRF）を使用入力データ田村正和山中伸弥出力俳優研究者松田龍平 ‥ 俳優 ‥ 5 分類器の学習とテスト学習用データ（正解ラベル付き）（田村正和，俳優）（山中伸弥，研究） ‥ ‥ 分類器（続き） y = f(x) ①学習（パラメタ値決定）分類器 x: 入力データ y: 出力（カテゴリ） • 入力データ x は通常，実数値（または整数値）ベクトル．入力に含まれる様々な側面の値を並べたもの分類モデル（NB, maxent， CRF, SVM，..）＋パラメータテストデータ（正解ラベルなし） • 出力カテゴリが 2種類に限定される場合，2値分類（よくあるのは yes/no 判定），3種類以上ある場合多値分類という（分類） – 多値分類問題は，複数の 2値分類問題の組み合わせに変換できる（one-vs-rest法，pairwise法など）線形分類器分類器の応用 ②テスト（利根川進，？）（萩原健一，？） ‥ ‥ • 素性関数 φ(x, y) • 形態素・構文解析 – 入力値（ベクトル） x と出力値 y の組に対して様々な値を与える関数（例： x と y が特定の関係にある場合に 1，その他の場合に 0 を返す関数） • 線形分類器 – n 個の素性関数の重み付き和に基づいて出力を決定する n f (x)  arg max  ( wi  i (x, y )) y i 1 – 重み wi の値を学習によって決定する系列ラベリング • 入力列に対して，それと同じ長さのラベル系列を出力する問題 • 例：品詞タグ付け – 入力列 Time flies like an arrow. – 出力列名詞動詞前置冠詞名詞 – 品詞タグ付け（系列ラベリング） – 係り受け解析（係り先文節の決定） • 意味解析 – 語義曖昧性解消 – 意味役割付与 • 様々な言語処理 – 機械翻訳（単語対応の決定） – 文書分類（カテゴリ分類，肯定／否定，スパム判別）など条件付き確率場（Conditional Random Fields, CRF） • 線形分類器において，直前のラベルとの組み合わせを考慮に入れた関数値を最大化する問題を解く f (x)  arg max  ( wi  i (x, yt , yt 1 )) y t i – 重み wi の値を学習によって決定する • 前後の関係も考慮に入れる必要がある • 形態素解析と同様に，動的計画法に基づく最短経路探索アルゴリズムを適用することができる 6 文節区切り決定のアルゴリズム • 単語列が与えられた時に文節区切りの位置を決定する問題を，単語に対するタグ付与の問題の一種ととらえる • 例： <S>タグ：駅で彼女を見た名詞助詞代名詞助詞動詞助動詞 <S> <E> <S> <S> <E> 文節の最初の単語 <E>タグ：文節の最後の単語 <E> • 個々の単語に対して，Ｓおよび E のタグを付与するかどうかを２値分類問題ととらえ，条件付き確率場を使って，その分類器をタグ付きコーパスデータ（例：手作業で解析済みの新聞記事）から学習する．学習用の素性・・・単語，品詞 Support Vector Machine (SVM) • （２値）分類問題を解く学習アルゴリズムの一種マージン (2) 係り受け関係決定のアルゴリズム各点は正例または負例の標本データを表し， N次元数ベクトルとして表現される CaboCha はSupport Vector Machine（SVM）を使用 Support Vector Machine の特徴 • 線形分類器 f (x)  sign(  wi xi  w0 ) i – この式で教師データを正しく分類するという条件の下で ||w|| が最小となるような wi を求める • 大規模な素性集合に対応可能で，分類精度が高い分離マージンを最大化するような超平面を求める • 多値分類への拡張 – one-vs-rest法，pairwise法など係り受け関係決定のアルゴリズム Kernel method • 教師データが線形分離できない場合でも，Kernel 関数を用いてデータを高次元に射影することで，線形分離できる場合がある f (x)  sign(  j y j  K (x, x j )  w0 ) • アルゴリズムの基本となる部分：隣り合う２つの文節（または複数の文節からなるグループ）が係り受けの関係にあるかどうかを自動判定するような SVM を作る？ j 注） K は Kernel関数，αj は Lagrange乗数 • 高次の Kernel を使うことで，素性の組み合わせ（共起関係）を考慮できるようになる – 例：多項式 Kernel K (x, x' )  (x  x'r ) d 駅で名詞助詞？彼女を代名詞助詞見た動詞助動詞 • 学習用の素性・・・主辞見出し，主辞品詞，助詞の種類，句読点の有無，文節間距離など d = 2, 3, … 7 係り受け関係の決定（続き） • SVM による学習 • 全体のアルゴリズム – 入力文節列に含まれる全ての隣接文節ペアに対して，係り受け関係の有無を SVM で判定する？ × 駅で？ ○ 彼女を駅でた ○ 彼女を – 学習用サンプルデータ：京大コーパス（毎日新聞記事＋人手によるタグ）８日分（約8,000文） – 学習時間：約10時間 • 解析実験見 – 係り受け関係があると分かった部分から順に考慮の対象から外していき，まだ係り先が決まっていない文節に対して残りの可能性を試していく？実験結果見た – – – – 解析テスト用データ：京大コーパスの別の部分解析時間： 0.5秒／文係り受け正解率： 89.29% 文正解率： 47.53% 参考文献：「チャンキングの段階適用による日本語係り受け解析」，工藤拓＆松本裕治，情報処理学会論文誌 43(6)，2002 今日のまとめ係り受け解析の精度を高めるために，人手で作成した教師データを基に分類器のパラメータ調整（学習）を行う入力文形態素解析実験課題：今後の日程品詞情報付き単語リスト構文解析句構造解析係り受け解析構文木係り受け構造日程 • 第2回参加アンケート（済） • 第3回グループ分け，話し合い（済） • 第4回実験の構想発表（プレゼン）（済） • 第8～10回実験の結果報告（プレゼン） – 実験の目的，システムの機能，アルゴリズムの説明，使用したデータ，使用したツール，実験結果，考察，分担，参考文献 • 6月8日（月） 23:59 までに，全グループ，プレゼンのファイル（PowerPointなど）と作成したプログラム一式を杉本へ提出すること（詳細は後日） 8