自然言語対話特論後期水曜日 2時限後半

12月08日
構文解析

入力文（記号列）が与えられたとき，文法
によってその文を解析し，その構造を明ら
かにする
構文木
（一郎が速いボールを軽々と投げた）
文
動詞句
後置詞句
後置詞句
名詞句
名詞助詞形容詞名詞
一郎
が
速い
ボール
動詞句
助詞副詞
を
軽々と
動詞
投げた
CYKアルゴリズム


チョムスキーの標準形の文脈自由文法を
対象とした構文解析法
チョムスキーの標準形


A→BC （A,B,C∈Vn)
A→a (A∈Vn, a∈Vｔ）
X→aBはチョムスキーの標準形ではないが
X→AB, A→aに分解できる
X→ABCはチョムスキーの標準形ではないが
X→AY, Y→BCに分解できる
チョムスキーの標準形の例
「急いで走る一郎を見る」








(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
s→pp v
s→adv vp
vp→pp v
vp→adv v
np→vp n
np→v n
np→np p
pp→n p





(9) adv→急いで
(10) n→一郎
(11) p→を
(12) v→走る
(13) v→見る
CYK構文解析の概要
T2,5: 走る一郎を見た
T2,2: 走る| T3,5: 一郎を見た
T2,3: 走る一郎| T4,5 を見た
T2,4: 走る一郎を| T5,5 見た
１．急いで２．走る３．一郎４．を５．見た
１．急いで
２．走る
３．一郎
４．を
５．見た
T1,5
T2,2
T2,3
T2,4
T2,5
T1,4
T1,3
T3,5
T4,5
T1,2
T1,1
T5,5 急いで
T2,4
T2,3
T2,2
走る
T2,5
T3,5
T4,5
T3,4
T3,3
T4,4
一郎
を
T5,5
見た
T1,5
T1,2
T1,1
急いで
T2,4
T2,3
T2,2
走る
T1,5
T2,5
T1,4
T1,3
T2,5までの部分木
T2,5: 走る一郎を見た
T1,4
T1,3
T3,5
T1,2
T4,5
T3,4
T3,3
T4,4
一郎
を
T5,5
見た
T2,2
急いで
走る
T1,5
T2,2: 走る| T3,5: 一郎を見た
T1,4
T1,3
T1,2
T1,1
T2,2
急いで
走る
T3,5
T4,5
T3,4
T3,3
T4,4
一郎
を
T5,5
見た
T2,3: 走る一郎| T4,5 を見た
T2,5
T2,4
T2,3
T2,4
T2,3
T1,1
T2,5
T3,5
T4,5
T3,4
T3,3
T4,4
一郎
を
T5,5
見た
T2,4: 走る一郎を| T5,5 見た
CYKアルゴリズム
A→aの形の規則を用いて主対角線上の要素を求める．
1.

for i=1 to N

Ti,i={A|A→wi}
A→BCの形の規則を用いて２番目以降の対角線上の
要素を求める
2.

for k=1 to N-1

for i=1 to N-k
k
Ti ,i k  {A | A  BC, B  Ti ,i  j 1, C  Ti  j ,i k }
j 1
3.
S T1,N であれば，w1 wn は開始記号Sから導出可能
CYK構文解析表
１．急いで２．走る
１．急いで
２．走る
３．一郎
４．を
５．見た
adv→急いで vp→adv v
v→走る
３．一郎４．を
np→vp n
pp→np p
np→v n
pp→np p
n→一郎
pp→n p
５．見た
vp→pp v
s→pp v
s→adv vp
vp→pp v
s→pp v
vp→pp v
s→pp v
p→を
v→見た
文脈自由文法に基づく構文木
s
s
pp
vp
np
pp
vp
adv
np
v
n
p
v
急いで走る一郎を見た
adv
v
n
p
v
急いで走る一郎を見た
意味解析

与えられた文から，妥当な語の意味と意味
関係を明らかにし，意味構造を生成する

意味構造
意味解析に用いる知識

意味解析手法

コーパスによる訳語選択

意味構造

格構造


格：文を構成する要素（語や句）が述語に対して果た
す役割
表層格（構文的）



構文木から表層的に決まる格
ガ格，ヲ格，ニ格
深層格（意味的）


表層だけでは決まらない
Fillmoreの深層格

動作主格，経験者格，道具格，対象格，源泉格，目標格，場所格，
時間格
格構造の例
open
open
動作主格
対象格
対象格
John
the door
the door
John opened the door.
open
道具格
対象格
the key
The key opened the door.
open
the door
The door opened.
open
動作主格
対象格
John
the door
The door was opened by John.
動作主格
John
対象格
the door
道具格
the key
John opened the door with the key.
述語論理式

一階述語論理

John opened the door.
x(open(John, x)  door( x))
概念依存構造
John gave the man a book.
過去時制
John
P
対象
ATRANS
O
抽象的なものの移動
受益者の関係
book
R
man
John
意味解析に用いる知識



選択制限
スクリプト
電子化辞書
選択制限


文の意味的妥当性を規定するため辞書中に記
述された，単語間の共起関係に関する意味的制
約
例：目の下にくまが出来た．
「くま」の意味→動物の熊，目の下の陰
動物は目の下には出来ないので
目の下に「熊」が出来たわけではない
スクリプト


典型的な事象例を一つの枠の中にまとめた記憶構造．
人間が日常行っている定型化された行動を，時間の流
れに沿った事象の連鎖で表現したもの
例：レストランスクリプト


客がレストランに入り，料理を注文し，食事をし，支払いをし
て，レストランをでる間の行動を記述する
レストランで「誤って皿を割ってしまった」の皿はひざの皿で
はなくて料理を盛り付ける皿であると推測できる
電子化辞書


意味解析には体系的かつ網羅的に語彙の上位・下位関
係や制約を記述した知識ベースが必要
既存の辞書を電子化



対訳辞書，英英辞書，シソーラス，類語辞典，分類語彙表
利用例：語釈文中に現れる単語を利用する語の曖昧性解消法
言語処理用に構築された辞書


EDRの辞書，オントロジー辞書，WordNet
利用例：語と語の関係（上位・下位関係などを利用）
意味解析手法
コーパスによる訳語選択




ある言語における単語を別の言語のどの
単語で表現するか
例：paper→紙，新聞，論文
DMAX訳語選択法
GDMAX訳語選択法
訳語選択用コーパス

パラレルコーパス




ある言語の文（原文）と他言語の対訳文から
構成されるコーパス
例：Unixのman page，天声人語とその対訳
大量収集：困難
コンパラブルコーパス



分野やトピックを共有しているある言語のコー
パスと他言語のコーパス
例：各国の新聞記事
大量収集：比較的容易
コンパラブルコーパスを用いた
訳語選択


DMAX訳語選択法（Double MAXimize法）
GDMAX訳語選択法（Generalized Double
MAXimize法）
DMAX訳語選択法
（Double MAXimize法）

アイディア：ある言語コーパスにおいて最大の
共起頻度をもつ二つの単語に着目し，その二
つの単語の訳語候補が複数ある場合，正しい
訳語はコンパラブルなコーパスにおいても最大
の共起頻度を有する
訳語選択
例：裁判官のコートとネクタイ
日英対訳辞書
50
10
ネクタイ
tie
コート
coat
court
10
裁判官
日本語コーパス
単語共起頻度
50 10
80
judge
英語コーパス
単語共起頻度
10
10
GDMAX訳語選択法
（Generalized Double MAXimize法）

クロス言語情報検索で検索要求の単語か
ら適切な訳語を得るための手法
第2回レポート
締め切り 12月15日10:30
CYKアルゴリズムを使って
「急いで走る一郎を見た」を構文解析するプ
ログラムを作成せよ




説明つきプログラム
結果
考察

Download Report