今日の内容 自然言語処理 • 構文解析（２） 係り受け解析 – 係り受け解析の概要 Natural Language Processing 第７回 – 係り受け構造 – 係り受け解析アルゴリズム 2016/11/9 – 係り受け解析ツールの紹介 芝浦工業大学 工学部 情報工学科 杉本 徹 復習： 自然言語の解析処理の流れ 入力文 「太郎は本を読んだ。」 太郎 は 本 を 読ん だ 第4,5回 ① 形態素解析 第6,7回 ② 構文解析 第8,9回 ③ 意味解析 名 助 名 助 動 助動 太郎 は 本 を 読ん だ agent taro 第10回 ④ 文脈解析 read 復習： 構文解析 （ Parsing） • 与えられた文に含まれる，単語のまとまり（句）や 単語間の修飾関係などの構文構造を求める • ２種類の解析方法 1. 句構造解析 ・・・ 文の句構造を求める 2. 係り受け解析 ・・・ 文の係り受け構造を求める • 構文解析を行うことにより， object book 複数の文に またがる処理 構文解析の応用例 • 映画のレビュー文からの評価表現抽出，情報検索 – 文の主語と述語がわかる – 修飾語と被修飾語の関係がわかる – 省略された要素の有無がわかる 文の理解 に不可欠 復習： 構文構造 （Syntactic Structure） • 句構造／構成素構造 （Phrase/Constituent Structure） – 隣り合う複数の構文要素が形成するまとまり（句）に着目 例： ヒュー・ジャックマンのミュージカルで鍛えた歌唱 力は見事でしたし，ラッセル・クロウは声が渋く て、演技も完璧でした。アン・ハサウェイは名曲 「夢破れて」を歌う歌声が素晴らしかったです。 問： 演技が完璧だったのは誰？ 文章を単に形態素解析して単語の集合（bag of words） を作る手法では，正しい答えが得られない – 構文規則の例 構文木 文 → 後置詞句 動詞句 後置詞句 → 名詞句 助詞 • 係り受け構造／依存構造 （Dependency Structure） – 文中の要素間の相互依存関係（係り受け関係）に着目 ⇒ 構文解析（係り受け解析）が必要 1 依存構造 （Dependency Structure） 係り受け構造 • 句構造が言語表現を「全体－部分」の関係を基に 構造化するのに対して， 依存構造は言語表現の部分間の依存関係を基に 構造を考える • 参考： 英文の場合 I read a book yesterday . • 日本語の場合は，文節を単位として依存関係 （係り受け関係）を考えるのが一般的 – 文節の係り受け関係の向きは，必ず「左 → 右」 復習： 文節 • 文を読むとき，区切っても不自然にならないような 最小の単位 – 自立語（原則として1個）＋付属語（0個, 1個 または複数個） – 自立語（内容語） ・・・ 具体的意味内容をもつ語 • 名詞，副詞，連体詞，接続詞，感動詞 • 動詞，形容詞，形容動詞 係り受け構造 • 文節の係り受け（依存）関係 – 文中の各文節は，自分より右側にある１つの文節に 係って（修飾して）いる – 係って（修飾して）いる文節を係り側，係られて（修飾 されて）いる文節を受け側と呼ぶ 僕は 昨日 図書館で 借りた 分厚い 本を 読んだ． – 付属語（機能語） ・・・ 文法的機能を表す語 • 助詞 • 助動詞 係り受け構造（続き） 係り受け構造（続き） • 別の解釈 • 不可能な解釈 僕は 昨日 図書館で 借りた 分厚い 本を 読んだ． 僕は 昨日 図書館で 借りた 分厚い 本を 読んだ． 僕は 昨日 図書館で 借りた 分厚い 本を 読んだ． • 非交差性の条件 – 文節の係り受け関係どうしが交差してはならない 2 句構造木（構文木）と係り受け木 係り受け木 • 係り受け構造は，右端の文節を根とする木である と考えることもできる 僕は 僕は 本を 借りた 後置詞句 本を 図書館で 昨日 読んだ 名詞句 助詞 動詞句 太郎が 分厚い本 を 読んだ 図書館で 太郎が 文 分厚い 後置詞句 昨日 係り受け木 動詞句 後置詞句 借りた 分厚い 文 句構造木 読んだ 読んだ • 句構造木と異なり，係り受け木は，文の語順が変わった ときでも木の形が変わらない．そのため，語順の自由度 が高い日本語の構文構造表現に適している． 動詞句 本を 分厚い 名詞句 助詞 後置詞句 動詞句 分厚い本 を 太郎が 読んだ 係り受け解析の流れ （形態素解析 ⇒） 単語列 係り受け解析アルゴリズム 駅 で 彼女 を 名詞 助詞 名詞 助詞 駅 で 見 た 動詞 助動詞 １．文節区切りの決定 文節列 名詞 助詞 彼女 を 名詞 助詞 見 た 動詞 助動詞 ２．係り受け関係の決定 係り受け構造 １．文節区切りの決定 • 文の単語列において，自立語の直前で区切る． ただし下記の場合は区切らない – 名詞の直前が名詞である場合（複合名詞とみなす）※1 – 動詞の直前が動詞である場合（複合動詞とみなす） – 動詞「する」の直前がサ変接続名詞(例：勉強＋する） 駅 で 名詞 助詞 彼女 を 名詞 助詞 見 た 動詞 助動詞 ２．係り受け関係の決定 • 係り受け構造の表現形式 • コスト最小法（共起コスト＋距離コスト） • 探索アルゴリズム • 統計的手法に基づく係り受け解析 ※1 ただし，副詞的名詞＋名詞（例：今日＋私）， または接尾辞＋サ変接続名詞の場合は区切る 3 コスト最小法 係り受け構造の表現形式 • 各係り受け関係にコストを課す． • 制約条件を満たす係り受け構造のうち合計コストが 最小のものを求めるのが目標 • 文節列 b1, b2, …, bm に対する係り受け構造 (Dep(1), Dep(2), …, Dep(m-1)) 文 S = b1 b2 … bm （bi: 文節） 係り受け構造 (Dep(1), Dep(2), …, Dep(m-1)) ここで Dep(i) は，文節 bi の係り先文節の番号 b1 b2 ・・・ bDep(2) ・・ bDep(1) ・・・ m-1 bm cost(Dep(1), Dep(2), …, Dep(m-1)) = Σ cost(bi, bDep(i)) i=1 • 係り受け関係 b→b’ のコスト cost(b, b’) は， 次の2種類のコストの和 • 制約条件 – i < Dep(i) ≦ m （自分より右側の文節に係る） – どんな i, j の組に対しても， i < j < Dep(i) < Dep(j) となることはない（非交差性） 1) 共起コスト： b, b’ それぞれの文法的（または意味的）特徴 が合っていないときに大きい値とする 2) 距離コスト： b と b’ が位置的に離れているほど大きい値 共起コストの設定例 距離コストの設定例 • 係り受け関係 b→b’ の共起コスト b’ の主辞 用言 bの （動詞，形容詞， 係りタイプ 形容動詞） • 係り受け関係 b→b’ の距離コスト 体言 その他 （名詞） （副詞，連体詞， 接続詞，感動詞） 連用接続 0 10 10 連体接続 10 0 10 b と b’ の間にある 0個 1個 2個 3個 文節の数 • ここで，文節の主辞とはその文節中の自立語の中で最も 重要な（後に現れる）語であり，文節の係りタイプは次の 判断ルールを上から順に適用して求められる 1. 2. 3. 4. 5. 0 1 2 3 4 5 b の直後に読点が ある場合のコスト 5 4 3 2 1 0 • これらのコストは，下記の直感に対応している 文節の末尾が助詞「の」 ⇒ 連体接続 文節の末尾が（その他の）助詞 ⇒ 連用接続 文節の末尾が活用語の連用形 ⇒ 連用接続 文節の主辞が名詞，副詞，接続詞，感動詞 ⇒ 連用接続 文節の主辞が動詞，形容詞，形容動詞，連体詞 ⇒ 連体接続 – 文節は，遠くにある文節より近くにある文節に係りやすい – 読点の直前の文節は直後の文節に係りにくい 例２ 例１ 昨日 図書館で 借りた 本を 読んだ 駅で 彼女を 見た 4個 5個 b の直後に読点が ない場合のコスト 昨日 図書館で 借りた 本を 読んだ 駅で 彼女を 見た 文節 係り先 共起 コスト 距離 コスト 1 昨日 読んだ 0 3 0 図書館で 借りた 0 0 0 0 借りた 本を 0 0 読んだ 0 0 本を 読んだ 0 0 ― ― ― 読んだ ― ― ― 文節 係り先 距離 コスト 文節 係り先 共起 コスト 距離 コスト 距離 コスト 係り先 共起 コスト 共起 コスト 文節 昨日 借りた 0 駅で 彼女を 10 0 駅で 見た 0 1 図書館で 借りた 0 借りた 本を 本を 読んだ 彼女を 見た 0 0 彼女を 見た 0 0 見た ― ― ― 見た ― ― ― 合計コスト = 10 ＞ 合計コスト = 1 合計コスト = 1 ＜ 合計コスト = 3 • 「昨日、図書館で借りた本を読んだ」 だとどうなるか？ 4 復習（第３回 文章作成の技術） 長い修飾語は前に，短い修飾語は後に コスト最小の係り受け構造を求める アルゴリズム • どの文が分かりやすいか考えてみよう 1. 太郎が駅前の店で花子が読んだ本を見つけた． • CYK（Cocke-Younger-Kasami）法を使う 2. 太郎が花子が読んだ本を駅前の店で見つけた． • 入力データ 文節列 b1, b2, …, bm 3. 駅前の店で太郎が花子が読んだ本を見つけた． • データ構造 m行m列の三角行列 (Ti,j) 4. 駅前の店で花子が読んだ本を太郎が見つけた． 5. 花子が読んだ本を太郎が駅前の店で見つけた． – 部分文節列 bi, …, bj に対応する最良の係り受け構造 とその構造のコストを Ti,j に格納 6. 花子が読んだ本を駅前の店で太郎が見つけた． 係り受けコストの和が小さい語順にすると，読みやすい アルゴリズムの説明 係り受け解析の例 • 解析手順 １．主対角線上の要素を求める Ti,i （1≦i≦m）に空の構造（コスト 0）を格納する ２．2番目以降の対角線上の要素を求める for k = 1 to m - 1 for i = 1 to m - k bi+1 ・・・・・・ bi+j ・・・・・・ 図書館で 借りた 本を 読んだ ( ):0 ２．図書館で bi が bi+j に係るとしたときの bi, …, bi+k の合計コスト cost(bi, bi+j) + cost(Ti+1,i+j) + cost(T i+j,i+k) を 1≦j≦k の 範囲の ｊ に対してそれぞれ求め，コスト最小となる j に対する係り受け構造とそのコストを Ti,i+k に格納する bi 昨日 １．昨日 ( ):0 ３．借りた ( ):0 ４．本を ( ):0 ５．読んだ ( ):0 bi+k 凡例： 最良の構造:コスト cost(bi, bi+j) Ti+1,i+j Ti+j,i+k 続き（１） １．昨日 ２．図書館で ３．借りた ４．本を ５．読んだ 昨日 図書館で ( ):0 (2):10 ( ):0 借りた 続き（２） 本を 読んだ １．昨日 ２．図書館で (3):0 ( ):0 ３．借りた (4):0 ( ):0 (5):0 ４．本を ( ):0 ５．読んだ 昨日 図書館で 借りた ( ):0 (2):10 (23):10 (33):1 本を 読んだ ( ):0 (3):0 (34):0 (44):11 ( ):0 (4):0 (45):0 (55):11 ( ):0 (5):0 ( ):0 5 続き（３） 昨日 １．昨日 ２．図書館で ( ):0 図書館で (2):10 ( ):0 ３．借りた 続き（４） 借りた 本を (33):1 (234):10 (334):1 (434):12 読んだ 昨日 １．昨日 (3):0 (34):0 (345):0 (445):11 (545):2 ( ):0 (4):0 (45):0 ( ):0 (5):0 ４．本を ( ):0 ５．読んだ ４．本を ５．読んだ 図書館で ( ):0 ２．図書館で 借りた (2):10 (33):1 ( ):0 (3):0 ( ):0 ３．借りた 本を 読んだ (2345):10 (3345):1 (334):1 (4345):12 (5345):3 (34):0 (345):0 (4):0 (45):0 ( ):0 (5):0 ( ):0 計算量は O(n3) 統計的手法に基づく係り受け解析 • 係り受け構造 (Dep(1), Dep(2), …, Dep(m-1)) の 出現確率 m-1 P(Dep(1), …, Dep(m-1)) = Π P(Bi→BDep(i)) 係り受け解析ツールの紹介 i=1 – それぞれの係り受けの確率をコーパスから推定する – 推定の際，文節がもつ様々な文法的・意味的特徴を 機械学習の素性（そせい）として用いる • 形態素解析と同様に，確率の -log をコストと見なす ことによりコスト最小法と対応づけることができる CaboCha の解析精度 係り受け解析ツールの例 • CaboCha （工藤拓，2002～） – 条件付き確率場（CRF） を用いた文節区切り – Support Vector Machine (SVM) を用いた係り受け判定 – 局所的な係り受け判定の繰り返しによる効率的な解析（O(n)） • KNP（京都大，1993～） – Web から自動構築した大規模格フレームを用いた，統合的確 率モデルにより解析を行う – CaboCha より解析速度が遅いが，述語項構造解析など高度な 解析の結果を出力できる • Yahoo! 日本語係り受け解析API – Web 上で係り受け解析を実行できる Web サービス • SVM による学習 – 学習用サンプルデータ： 京大コーパス（毎日新聞記事＋ 人手によるタグ） ８日分（約8,000文） – 学習時間：約10時間 • 解析実験 – – – – 解析テスト用データ： 京大コーパスの別の部分 解析時間： 0.5秒／文 係り受け正解率： 89.29% 文正解率： 47.53% 参考文献：「チャンキングの段階適用による日本語係り受け解析」 工藤拓＆松本裕治，情報処理学会論文誌 43(6)，2002 6 学情UNIXサーバでのインストール手順 CaboCha のインストール方法 詳しくは，CaboCha のホームページ参照 • Windows – CaboCha のホームページから自己解凍インストーラ（～.exe）を ダウンロードしてインストール – 学情の環境では不可 • ここでも自分のホームディレクトリ下の usr という名前のディレクトリ にインストールすると想定して説明する 手順１ CRF++-0.58.tar.gz を適当なディレクトリへダウンロードし，以下の コ マンドを順に実行する （注： CRF++のダウンロードサイトは検索エンジンにて「CRF++」で検索すると 見つかります） • UNIX – CRF++ と CaboCha のソースコードをダウンロードし，ホームペ ージの説明を参考に，それぞれコンパイル，インストール – インストール時の設定により，学情のUNIXサーバにもインスト ール可能（次ページ以降で説明） tar zxvf CRF++-0.58.tar.gz cd CRF++-0.58 ./configure --prefix=$HOME/usr --with-charset=utf8 make make install 続き 手順２ 次に，CaboChaをインストールする． cabocha-0.69.tar.bz2 をダウ ンロードし，以下のコマンドを順に実行する tar jxvf cabocha-0.69.tar.bz2 cd cabocha-0.69 ./configure --prefix=$HOME/usr （次の行に続く） --with-charset=utf8 （次の行に続く） --with-mecab-config=$HOME/usr/bin/mecab-config LDFLAGS="-L$HOME/usr/lib" （次の行に続く） CPPFLAGS="-I$HOME/usr/include" make make check make install 手順３ インストールが終わったら，CaboCha を起動する ～/usr/bin/cabocha （または単に cabocha） 今日のまとめ • 構文解析（２） 係り受け解析 – 係り受け解析の概要 – 係り受け構造 CaboCha の使い方 • CaboCha を起動し，解析したい文を標準入力から入力する 入力文 文節番号 % cabocha –f1 駅で彼女を見た。 * 0 2D 0/1 -1.946565 駅 で 名詞,一般,*,*,*,*,駅,エキ,エキ 助詞,格助詞,一般,*,*,*,で,デ,デ * 1 2D 0/1 -1.946565 文節 彼女 を 名詞,代名詞,一般,*,*,*,彼女,カノジョ,カノジョ 助詞,格助詞,一般,*,*,*,を,ヲ,ヲ * 2 -1D 0/1 0.000000 係り先の 文節番号 見 た 。 動詞,自立,*,*,一段,連用形,見る,ミ,ミ 助動詞,*,*,*,特殊・タ,基本形,た,タ,タ 記号,句点,*,*,*,*,。,。,。 EOS • または，解析したい文章を１文ずつ行に区切ってテキストファイ ルに保存し，そのファイル名を引数としてCaboChaを実行する 宿題 （提出不要，解答は次回） １．「黒い目の大きな猫」という句の係り受け構造を 考えて図示しなさい．文法的に正しい解釈が複数 考えられる場合は，そのすべてを図示すること． – 係り受け解析アルゴリズム – 係り受け解析ツールの紹介 ２．図示した係り受け構造のそれぞれが，この句の どのような意味の解釈に対応するか説明しなさい． 7 お知らせ： 杉本研のプレゼミ １） 本日 11月 9日（水） 5限： 研究分野・研究室紹介 ２） 11月16日（水） 5限： 研究分野・テーマ紹介 場所： 405教室 ☆ 自然言語処理の研究に興味のある人は ぜひご参加ください！ 大学院進学希望者歓迎！ 8
© Copyright 2024 ExpyDoc
