NLP-9

自然言語処理：第９回
１．N-gram言語モデルの確認
２．文法と有限状態オートマトン
言語モデル
どんな文が適切な文か
① 文法に合っている
② 意味が通じる
③ 良く使われる
言語モデル
どんな文が適切な文か
① 文法に合っている
② 意味が通じる
③ 良く使われる
今日の天気は晴れである  ○
の天気今日が晴れたある  ×
言語モデル
どんな文が適切な文か
① 文法に合っている
② 意味が通じる
③ 良く使われる
思い出そうと思っても忘れられない
言語モデル
どんな文が適切な文か
① 文法に合っている
② 意味が通じる
③ 良く使われる
はいそうです。
配送です
N-gram言語モデル
N-gram言語モデル
それぞれの文の使われやすさを統計を用いて
表すモデル
はいそうです
配送です
大量の文を集めてきて、その中で上の文が
それぞれ何回使われたかを数える
N-gram言語モデル
N-gram言語モデル
文の種類は事実上無限なので、いくら大量の
文を集めてきても、出てこない文がある
明日はどこへ遊びに行こうか
まず単語（形態素）にわける
明日はどこへ遊びに行こうか
N-gram言語モデル
N-gram言語モデル
明日はどこへ遊びに行こうか
この文があらわれるためには
(明日)
最初が「明日」で
(は|明日)
(どこ|明日は)
「明日」の次が「は」
「明日は」の次が「どこ」
(か|明日は … 行こう)
N-gram言語モデル
N-gram言語モデル
(か|明日は … 行こう)
「か」から遠い部分を省略
(か|行こう) 前２つしか見ない（3-gram）
(か|行こ)
前１つしか見ない（2-gram）
N-gram言語モデル
2-gramを例にとると
明日はどこへ遊びに行こうか
(明日)
最初が「明日」でよいか
(は|明日)
(どこ|は)
「明日」の次が「は」でよいか
「は」の次が「どこ」でよいか
(か|う)
「う」の次が「か」でよいか
N-gram言語モデル
2-gramを例にとると
(明日)
最初が「明日」でよいか
(は|明日)
(どこ|は)
「明日」の次が「は」でよいか
「は」の次が「どこ」でよいか
単語二つのつながりが尤もらしいかを調べる
ただし、近似した（直前の１単語しか見ていな
い）ため、文全体ではおかしいかもしれない
文法
どんな文が適切な文か
① 文法に合っている
② 意味が通じる
③ 良く使われる
今日の天気は晴れである  ○
の天気今日が晴れたある  ×
文法
文法の利用
問題点
文法の記述が大変（専門家が必要）
全ての文をカバーしきれない
文法が正しくても、意味のない文がある
文法が正しく、読みが同じ文がある
文法
文法が必ずしも必要がない場合
最終的に人間が出力を受け取る場合
・音声認識
・機械翻訳
文法に合っているより、全体的に正しい方が
重要
文法
文法の利用
構文解析
形態素どうしの関係を解析
意味解析の前段としては必須
コンピュータシステムからの問い合わせの
返答
システムが受け付けられる文だけを
受け入れる文法を書けば良い
文法
ネットワーク文法
ネットワーク表現
安藤
営業の
佐藤
さんお願いします
鈴木
正規表現
営業の（安藤｜佐藤｜鈴木）さんお願いします
正規文法
（書き換え規則）
＜文＞＝＜人名＞＋お願いします
＜人名＞＝＜営業＞＋安藤
＜人名＞＝＜営業＞＋佐藤
＜人名＞＝＜営業＞＋鈴木
＜営業＞＝営業の
文法
文法の複雑さ（パープレキシティ）
安藤
佐藤
営業
総務
さん
課長
の
さん
山本鈴木
吉田
の
お願いします
鈴木
総務
START
の
START
山本
吉田
課長お願いします
END
END
文法
文法の複雑さ（パープレキシティ）
安藤
佐藤
営業
総務
さん
課長
の
の
山本
鈴木
さん
吉田
生成される文の総数：２８文
お願いします
文法
文法の複雑さ
安藤
佐藤
鈴木
営業
さん
の
総務
START
山本
START
吉田
生成される文の総数：６０文
課長
お願いします
END
END
文法
平均分岐数
文法
文法の記述のしかた
ネットワーク文法は視覚化してしまえばわか
りやすいが
安藤
佐藤
営業
総務
さん
課長
の
の
山本
鈴木
さん
お願いします
吉田
人間が直接書こうとすると大変
文法
文脈自由文法
安藤
佐藤
営業
総務
さん
課長
の
の
山本
鈴木
さん
お願いします
吉田
文:=<営業部員>,<文末>
文:=<営業>,<営業部員>,<文末>
文法
文脈自由文法
安藤
佐藤
営業
総務
さん
課長
の
の
山本
鈴木
さん
お願いします
吉田
<営業部員>:=安藤,<課長>
<課長>:=さん
<課長>:=課長
文法
文脈自由文法
<営業部員>:=安藤,<課長>
<課長>:=さん
<課長>:=課長
右辺が出てきたら、左辺に置き換える。
最終的に<文>ができれば文法に合致
<XXX>  左辺にも、右辺にも現れる（非終端記号）
それ以外  終端記号（単語）
文法
先ほどのネットワーク文法は
<文>:=<営業>,<営業部員>
<文>:=<営業>,<営業部員>,<文末>
<文>:=<総務>,<総務部員>
<文>:=<総務>,<総務部員>,<文末>
<営業>:=営業,の
<営業部員>:=<営業平>
<営業部員>:=<営業課長>
<総務部員>:=<総務平>
<総務部員>:=<総務課長>
<営業平>:=<営業平名>,さん
<営業平名>:=佐藤
<営業平名>:=鈴木
<営業課長>:=<営業課長名>,<課長>
<営業課長名>:=安藤
<課長>:=さん
<課長>:=課長
<総務平>:=<総務平名>,さん
<総務平名>:=吉田
<総務課長><総務課長名>,<課長>
<総務課長名>:=山本
<文末>:=お願いします
文法
次の文を過不足なく受け付ける文脈自由文法を
考えてみる
犬は走る
猫は走る
アヒルは飛ぶ
ツバメは飛ぶ
犬は生き物だ
猫は生き物だ
アヒルは生き物だ
ツバメは生き物だ
文法
犬は
猫は
アヒル
ツバメ
犬は
猫は
アヒル
ツバメ
走る
走る
は飛ぶ
は飛ぶ
生き物だ
生き物だ
は生き物だ
は生き物だ
<文>:=<獣>,は,走る
<文>:=<鳥>,は,飛ぶ
<文>:=<生物>,は,生き物,だ
<獣>:=犬
<獣>:=猫
<鳥>:=アヒル
<鳥>:=ツバメ
<生物>:=<獣>
<生物>:=<鳥>
文法
ネットワーク文法にすると
は
犬,猫
走る
は
生き物
アヒル,
ツバメ
は
は
飛ぶ
だ
文法
文脈自由文法をネットワーク文法変換するのは
結構大変
当然自動で
しかし、できない場合がある
文法
ネットワーク文法（正規文法）
非終端記号が右端（左端）にしか現れない
文脈自由文法
非終端記号どこに現れても良い
文:= he is young
文:= that 文 is false
n
(that)
he is young (is false)
n
文法
決定性と非決定性
非決定性  ある記号が入力された時、遷移先が
一つ以上ある場合がある
B
C
A
A
D
先までいかないと、
どちらに遷移するの
が正しいかわからな
い
文法
決定性と非決定性
非決定性  ある記号が入力された時、遷移先が
一つ以上ある場合がある
B
C
C
A
D
決定性を持たせると
文法
0
q0,q1
q2
q2
q2,qF
q0,q1
q2,qF
q2,qF
q0,q1
0
q0,q1
q2
1
0
1
1
q2,qF
0
文法
最小化
受け付けられる文が全く同じであれば、ノードの
数は少ない程良い
B
A
C
D
C
D
文法
最小化
受け付けられる文が全く同じであれば、ノードの
数は少ない程良い
B
C
A
D
文法
ある２つのノードから受け付けられる記号列が
同じであれば、一つにまとめてよい
B
A
C
D
C
D
文法
同じ記号で同じノードに行くノードはまとめて良
い（後ろから順に行う）
B
A
C
C
D
D
文法
同じ記号で同じノードに行くノードはまとめて良
い（後ろから順に行う）
B
A
C
C
D
文法
同じ記号で同じノードに行くノードはまとめて良
い（後ろから順に行う）
B
C
A
D
質問＆スライド
[email protected]
http://www.info.kindai.ac.jp/ASR

Download Report