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) s→pp v (2) s→adv vp (3) vp→pp v (4) vp→adv v (5) np→vp n (6) np→v n (7) np→np p (8) 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,5 T1,4 T1,3 T2,4 T3,5 T1,2 T2,3 T3,4 T4,5 T1,1 T2,2 T3,3 T4,4 T5,5 急いで 走る 一郎 を 見た ２．走る T2,2 T2,3 T2,4 T2,5 ３．一郎 T3,5 ４．を T4,5 ５．見た T5,5

T2,5までの部分木 T2,5: 走る一郎を見た T1,5 T1,5 T1,4 T2,5 T1,4 T2,5 T1,3 T2,4 T1,3 急いで 走る 一郎 を 見た 急いで 走る 一郎 を 見た T2,2: 走る| T3,5: 一郎を見た T1,5 T2,3: 走る一郎| T4,5 を見た T1,4 T2,5 T1,3 T2,4 T3,5 T1,2 T2,3 T4,5 T3,4 T1,1 T2,2 T3,3 T4,4 T5,5 急いで 走る 一郎 を 見た T2,4: 走る一郎を| T5,5 見た

CYKアルゴリズム A→aの形の規則を用いて主対角線上の要素を求める． A→BCの形の規則を用いて２番目以降の対角線上の要素を求める for i=1 to N Ti,i={A|A→wi} A→BCの形の規則を用いて２番目以降の対角線上の要素を求める for k=1 to N-1 for i=1 to N-k であれば， は開始記号Sから導出可能

CYK構文解析表 １．急いで ２．走る ３．一郎 ４．を ５．見た １．急いで ２．走る ３．一郎 ４．を ５．見た vp→pp v １．急いで ２．走る　　３．一郎　４．を　　５．見た vp→pp v s→pp v s→adv vp adv→急いで vp→adv v np→vp n pp→np p １．急いで v→走る np→v n pp→np p vp→pp v s→pp v ２．走る n→一郎 pp→n p vp→pp v s→pp v ３．一郎 p→を ４．を v→見た ５．見た

文脈自由文法に基づく構文木 s s pp vp np pp vp np adv v n p v adv v n p v 急いで　走る　一郎　を　見た　　急いで　走る　一郎　を　見た

意味解析 与えられた文から，妥当な語の意味と意味関係を明らかにし，意味構造を生成する 意味構造 意味解析に用いる知識 意味解析手法 コーパスによる訳語選択

意味構造 格構造 格：文を構成する要素（語や句）が述語に対して果たす役割 表層格（構文的） 深層格（意味的） 構文木から表層的に決まる格 ガ格，ヲ格，ニ格 深層格（意味的） 表層だけでは決まらない Fillmoreの深層格 動作主格，経験者格，道具格，対象格，源泉格，目標格，場所格，時間格

格構造の例 open open open 動作主格 対象格 対象格 道具格 対象格 John the door the door the key the door John opened the door. The key opened the door. The door opened. open open 動作主格 対象格 動作主格 道具格 対象格 John the door John the door the key The door was opened by John. John opened the door with the key.

述語論理式 一階述語論理 John opened the door.

概念依存構造 John gave the man a book. man P O R John ATRANS book John 過去時制 対象 受益者の関係 man P O R John ATRANS book 抽象的なものの移動 John

意味解析に用いる知識 選択制限 スクリプト 電子化辞書

選択制限 文の意味的妥当性を規定するため辞書中に記述された，単語間の共起関係に関する意味的制約 例：目の下にくまが出来た． 　　　　「くま」の意味→動物の熊，目の下の陰 　　　　動物は目の下には出来ないので 　　　　目の下に「熊」が出来たわけではない

スクリプト 典型的な事象例を一つの枠の中にまとめた記憶構造．人間が日常行っている定型化された行動を，時間の流れに沿った事象の連鎖で表現したもの 例：レストランスクリプト 客がレストランに入り，料理を注文し，食事をし，支払いをして，レストランをでる間の行動を記述する レストランで　「誤って皿を割ってしまった」の皿はひざの皿ではなくて料理を盛り付ける皿であると推測できる

電子化辞書 意味解析には体系的かつ網羅的に語彙の上位・下位関係や制約を記述した知識ベースが必要 既存の辞書を電子化 対訳辞書，英英辞書，シソーラス，類語辞典，分類語彙表 利用例：語釈文中に現れる単語を利用する語の曖昧性解消法 言語処理用に構築された辞書 EDRの辞書，オントロジー辞書，WordNet 利用例：語と語の関係（上位・下位関係などを利用）

意味解析手法

コーパスによる訳語選択 ある言語における単語を別の言語のどの単語で表現するか 例：paper→紙，新聞，論文 DMAX訳語選択法 GDMAX訳語選択法

訳語選択用コーパス パラレルコーパス コンパラブルコーパス ある言語の文（原文）と他言語の対訳文から構成されるコーパス 例：Unixのman page，天声人語とその対訳 大量収集：困難 コンパラブルコーパス 分野やトピックを共有しているある言語のコーパスと他言語のコーパス 例：各国の新聞記事 大量収集：比較的容易

コンパラブルコーパスを用いた訳語選択 DMAX訳語選択法（Double MAXimize法） GDMAX訳語選択法（Generalized Double MAXimize法）

DMAX訳語選択法 （Double MAXimize法） アイディア：ある言語コーパスにおいて最大の共起頻度をもつ二つの単語に着目し，その二つの単語の訳語候補が複数ある場合，正しい訳語はコンパラブルなコーパスにおいても最大の共起頻度を有する

訳語選択 例：裁判官のコートとネクタイ 日英対訳辞書 ネクタイ コート 裁判官 tie coat court judge 50 50 10 80 10 10 日本語コーパス 単語共起頻度 英語コーパス 単語共起頻度

GDMAX訳語選択法 （Generalized Double MAXimize法） クロス言語情報検索で検索要求の単語から適切な訳語を得るための手法

第2回 レポート 締め切り 12月15日10:30 CYKアルゴリズムを使って 「急いで走る一郎を見た」を構文解析するプログラムを作成せよ 第2回　レポート 締め切り　12月15日10:30 CYKアルゴリズムを使って 「急いで走る一郎を見た」を構文解析するプログラムを作成せよ 説明つきプログラム 結果 考察