自然言語処理システム特論

今日の内容
自然言語処理システム特論
構文解析
• 構文解析とは？
Natural Language Processing Systems
第５回
• 句構造解析
• 係り受け解析
2016/5/18
– 文節区切り決定のアルゴリズム
芝浦工業大学工学部情報工学科
杉本徹
[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）
• 句構造が言語表現を「全体－部分」の関係を基に
構造化するのに対して，
依存構造は言語表現の部分間の依存関係を基に
構造を考える
• 参考：英文の場合
I read a book yesterday .
• 係り受け構造／依存構造（Dependency Structure）
– 文中の要素間の相互依存関係（係り受け関係）に着目
• 日本語の場合は，文節を単位として依存関係
（係り受け関係）を考えるのが一般的
– 文節の係り受け関係の向きは，必ず「左 → 右」
係り受け構造
参考：オープンソース構文解析器 SyntaxNet
• Google が今年5月に発表．TensorFlow上で動作
• ニューラルネットワークを利用して，自然言語文の
依存構造解析を高精度で実行する
• 依存構造解析の精度
– ニュース記事 94% （参考：人間の専門家は 96～97%）
– Webにある文 90%
• 文節
– 文を意味に沿って区切った時の最小単位で，
１つの自立語といくつかの付属語から構成される
• 文節の係り受け（依存）関係
僕は昨日図書館で借りた分厚い本を読んだ．
参考文献： “Globally Normalized Transition-Based
Neural Networks”, Daniel Andor et al.,
arXiv:1603.06042v1, May 2016.
4
係り受け構造（続き）
係り受け構造（続き）
• 別の解釈
• 不可能な解釈
僕は昨日図書館で借りた分厚い本を読んだ．
僕は昨日図書館で借りた分厚い本を読んだ．
僕は昨日図書館で借りた分厚い本を読んだ．
• 非交差性の条件
– 文節の係り受け関係どうしが交差してはならない
係り受け解析の流れ
（形態素解析 ⇒）単語列
駅
で
彼女
係り受け解析ツールの例
を
名詞
助詞代名詞助詞
駅
で
見
た
動詞助動詞
(1) 文節区切りの決定
• CaboCha （工藤拓，2002～）
– 条件付き確率場（CRF）を用いた文節区切り
– Support Vector Machine (SVM) を用いた係り受け判定
– 局所的な係り受け判定の繰り返しによる効率的な解析（O(n)）
• KNP（京都大，1993～）
文節列
名詞助詞
彼女
を
代名詞助詞
見
た
動詞助動詞
(2)係り受け関係の決定
係り受け構造
– Web から自動構築した大規模格フレームを用いた，統合的確率
モデルにより解析を行う
– CaboCha より解析速度が遅いが，述語項構造解析など高度な
解析の結果を出力できる
• Yahoo! 日本語係り受け解析API
駅
で
名詞助詞
彼女
を
代名詞助詞
見
た
– Web 上で係り受け解析を実行できる Web サービス
動詞助動詞
CaboCha の使い方
• CaboCha を起動し，解析したい文を標準入力から入力する
入力文
文節番号
% cabocha –f1
駅で彼女を見た。
* 0 2D 0/1 -1.946565
駅
で
名詞,一般,*,*,*,*,駅,エキ,エキ
助詞,格助詞,一般,*,*,*,で,デ,デ
* 1 2D 0/1 -1.946565
文節
彼女
を
(1) 文節区切り決定の
アルゴリズム
名詞,代名詞,一般,*,*,*,彼女,カノジョ,カノジョ
助詞,格助詞,一般,*,*,*,を,ヲ,ヲ
* 2 -1D 0/1 0.000000
係り先の
文節番号
見
た
。
動詞,自立,*,*,一段,連用形,見る,ミ,ミ
助動詞,*,*,*,特殊・タ,基本形,た,タ,タ
記号,句点,*,*,*,*,。,。,。
CaboCha は条件付き確率場（CRF）を使用
EOS
• または，解析したい文章を１文ずつ行に区切ってテキストファイ
ルに保存し，そのファイル名を引数としてCaboChaを実行する
5
分類器（classifier）
• 入力データを（あらかじめ決めておいた）複数のカテ
ゴリの中のどれかに分類する
y = f(x)
x: 入力データ y: 出力（カテゴリ）
分類器の学習とテスト
学習用データ
（正解ラベル付き）
（田村正和，俳優）
（山中伸弥，研究）
‥ ‥
①学習
（パラメタ
値決定）
分類モデル
• 例：入力された人名を俳優か研究者に分類する
入力データ
田村正和
山中伸弥
松田龍平
‥
出力
俳優
研究者
俳優
‥
（NB, maxent，
CRF, SVM，..）
x: 入力データ y: 出力（カテゴリ）
• 入力データ x は通常，実数値（または整数値）ベク
トル．入力に含まれる様々な側面の値を並べたもの
＋
パラメータ
テストデータ
（正解ラベルなし）
②テスト
（利根川進，？）
（萩原健一，？）
‥ ‥
分類器（続き）
y = f(x)
分類器
（分類）
線形分類器
• 素性関数 φ(x, y)
– 入力値（ベクトル） x と出力値 y の組に対して様々な値を
与える関数（例： x と y が特定の関係にある場合に 1，
その他の場合に 0 を返す関数）
• 線形分類器
• 出力カテゴリが 2種類に限定される場合，2値分類
（よくあるのは yes/no 判定），3種類以上ある場合
多値分類という
– 多値分類問題は，複数の 2値分類問題の組み合わせ
に変換できる（one-vs-rest法，pairwise法など）
– n 個の素性関数の重み付き和に基づいて出力を決定する
n
f (x)  arg max  ( wi  i (x, y ))
y
– 重み wi の値を学習によって決定する
分類器の応用
• 形態素・構文解析
– 品詞タグ付け（系列ラベリング）
– 係り受け解析（係り先文節の決定）
• 意味解析
– 語義曖昧性解消
– 意味役割付与
• 様々な言語処理
– 機械翻訳（単語対応の決定）
– 文書分類（カテゴリ分類，肯定／否定，スパム判別）
など
i 1
系列ラベリング
• 入力列に対して，それと同じ長さのラベル系列
を出力する問題
• 例：品詞タグ付け
– 入力列
Time flies like an arrow.
– 出力列
名詞動詞前置冠詞名詞
• 前後の関係も考慮に入れる必要がある
6
条件付き確率場（Conditional Random Fields, CRF）
• 線形分類器において，直前のラベルとの組み合わせ
を考慮に入れた関数値を最大化する問題を解く
f (x)  arg max  ( wi  i (x, yt , yt 1 ))
y
t
文節区切り決定のアルゴリズム
• 単語列が与えられた時に文節区切りの位置を決定
する問題を，単語に対するタグ付与の問題の一種と
とらえる
• 例：
<S>タグ：
駅
で
彼女
を
見
た
文節の最初の単語
i
– 重み wi の値を学習によって決定する
• 形態素解析と同様に，動的計画法に基づく最短経路
探索アルゴリズムを適用することができる
名詞
助詞代名詞助詞
動詞助動詞
<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 )
j
注） K は Kernel関数，αj は Lagrange乗数
• 高次の Kernel を使うことで，素性の組み合わせ
（共起関係）を考慮できるようになる
– 例：多項式 Kernel
K (x, x' )  (x  x'r ) d
d = 2, 3, …
7
係り受け関係決定のアルゴリズム
• アルゴリズムの基本となる部分：
隣り合う２つの文節（または複数の文節からなる
グループ）が係り受けの関係にあるかどうかを
自動判定するような SVM を作る
？
駅
で
名詞助詞
係り受け関係の決定（続き）
• 全体のアルゴリズム
– 入力文節列に含まれる全ての隣接文節ペアに対
して，係り受け関係の有無を SVM で判定する
？
×
？
彼女
を
代名詞助詞
見
駅
た
動詞助動詞
• 学習用の素性・・・主辞見出し，主辞品詞，
助詞の種類，句読点の有無，文節間距離など
？
• 解析実験
–
–
–
–
解析テスト用データ：京大コーパスの別の部分
解析時間： 0.5秒／文
係り受け正解率： 89.29%
文正解率： 47.53%
参考文献：「チャンキングの段階適用による日本語係り受け
解析」，工藤拓＆松本裕治，情報処理学会論
文誌 43(6)，2002
を
見
た
で
○
彼女
を
見
た
今日のまとめ
実験結果
– 学習用サンプルデータ：京大コーパス（毎日新聞記事＋
人手によるタグ）８日分（約8,000文）
– 学習時間：約10時間
彼女
– 係り受け関係があると分かった部分から順に考
慮の対象から外していき，まだ係り先が決まって
いない文節に対して残りの可能性を試していく
駅
• SVM による学習
で
？
○
係り受け解析の精
度を高めるために，
人手で作成した教
師データを基に分
類器のパラメータ
調整（学習）を行う
入力文
形態素解析
品詞情報付き単語リスト
構文解析
句構造解析
係り受け解析
構文木
係り受け構造
日程
• 第2回参加アンケート（済）
• 第3回グループ分け，話し合い（済）
実験課題：今後の日程
• 第4回実験の構想発表（プレゼン）（済）
• 第8～10回実験の結果報告（プレゼン）
– 実験の目的，システムの機能，アルゴリズムの説明，
使用したデータ，使用したツール，実験結果，考察，
分担，参考文献
• 6月7日（月） 23:59 までに，全グループ，プレゼ
ンのファイル（PowerPointなど）と作成したプログ
ラム一式を杉本へ提出すること（詳細は後日）
8

Download Report