数理言語情報論　第3回 2007年10月22日 数理言語情報学研究室　講師　二宮　崇.

Presentation on theme: "数理言語情報論　第3回 2007年10月22日 数理言語情報学研究室　講師　二宮　崇."— Presentation transcript:

1 数理言語情報論　第3回 2007年10月22日 数理言語情報学研究室　講師　二宮　崇

2 今日の講義の予定 前回の復習 CCG (Combinatory Categorial Grammar , 組合せ範疇文法)
CFG (Context Free Grammar, 文脈自由文法) TAG (Tree Adjoining Grammar) Dependency Grammar (依存文法) CCG (Combinatory Categorial Grammar , 組合せ範疇文法)

3 CFG: 生成 簡単なCFGの例 S → SUBJ VP1 S → SUBJ V SUBJ → NP が VP1 → OBJ1 V
OBJ1 → NP を NP → S NP V → 送った V → 読んだ NP → 香織 NP → 恵 NP → 電子メール NP → プレゼント NP → 香織 NP1 NP → 恵 NP1 NP1 → と NP S ⇒ SUBJ VP1 ⇒ NP が VP1 ⇒ 香織 が VP1 ⇒ 香織 が OBJ1 V ⇒ 香織 が NP を V ⇒ 香織 が S NP を V ⇒ 香織 が SUBJ V NP を V ⇒ 香織 が NP が V NP を V ⇒ 香織 が 恵 が V NP を V ⇒ 香織 が 恵 が 送った NP を V ⇒ 香織 が 恵 が 送った 電子メール を V ⇒ 香織 が 恵 が 送った 電子メール を 読んだ * S ⇒ 香織 が 恵 が 送った 電子メール を 読んだ

4 CFG: 構文木 S VP1 SUBJ OBJ1 NP V が を NP 香織 読んだ S NP V SUBJ 電子メール NP が 送った
S → SUBJ VP1 S → SUBJ V SUBJ → NP が VP1 → OBJ1 V OBJ1 → NP を NP → S NP V → 送った V → 読んだ NP → 香織 NP → 恵 NP → 電子メール NP → プレゼント NP → 香織 NP1 NP → 恵 NP1 NP1 → と NP S VP1 SUBJ OBJ1 NP V が を NP 香織 読んだ S NP V SUBJ 電子メール NP が 送った 恵

5 ＣＦＧの限界 文法機能の解析不足 S → SUBJ VP VP → RB VP VP → V OBJ VP → V
NP → NP which S eats の主語、目的語が何かわからない

6 ＣＦＧの限界 文法機能の解析不足 S → SUBJ V OBJ というルールにすれば 直接の関係はわかるけど、 助動詞などが間にはいると、
S → SUBJ always V OBJ と助動詞の数だけ規則が増え ていってしまう eats の主語、目的語が何かわからない

7 ＣＦＧの限界 長距離依存 S → SUBJ VP VP → RB VP VP → V OBJ VP → V NP → NP which S
eats の目的語がapplesということがわからない

8 補足: チョムスキー標準形 チョムスキー標準形 書換規則が次の２種類からのみなる つまり、２分木を生成する
A → B C A → a つまり、２分木を生成する 任意のＣＦＧはチョムスキー標準形で記述可 A → a B をA → C B と C → a に直す A → B1 B Bn を A → B1 C1, C1 → B2 C2, ..., Cn-2 → Bn-1 Bn に直す

9 補足: グライバッハ標準形 グライバッハ標準形 書換規則が次の２種類からのみなる チョムスキー標準形から機械的に導ける
A → a B C E A → a チョムスキー標準形から機械的に導ける 長たらしい規則群になるが、一つの入力記号が与えられれば、適用できる書換規則が絞り込める点で効率的認識に役立つ

10 TAG：代入 (substitution)
α1 X↓ Y↓ 代入 X Y Y X α3 α2

11 TAG：接合 (adjoining) X β1 補助木 (auxiliary tree) α1 X* X X 接合 Y X*

12 TAG: 例 β1 α2 NP α1 VP S John VP* RB VP NP NP VBZ always α3 NP eats
tapas

13 TAG: 例 β1 α2 NP α1 VP S John VP* RB VP NP NP VBZ always α3 NP eats
tapas

14 TAG: 例 β1 α2 α1 VP S VP* RB VP NP NP VBZ always John α3 eats tapas

15 TAG: 例 β1 α2 α1 S VP NP eats VBZ NP VP tapas John RB α3 always

16 CFG v.s. TAG S VP NP eats VBZ NP VP tapas John RB always α1 (eats) α2
CFGだと、eatsの主語がJohnであることがわかりにくい VP NP eats VBZ NP VP tapas John RB Derivation tree always α1 (eats) TAGだと、eatsの主語がJohnであることがすぐわかる α2 (John) α3 (tapas) β1 (always)

17 Non-local Dependencies
NP α2 β1 S NP(i) S S VP Sandy NP S* VB NP VP 接合 know VB NP Kim likes ε(i)

18 句構造と依存文法 文法を大きくわけると二種類ある 句構造文法 依存文法 (Hays 1964; Robinson 1970) CFG TAG
CCG HPSG LFG 依存文法 (Hays 1964; Robinson 1970) 特別な句構造を持たず、単語間の依存関係を記述する形態の文法

19 句構造と依存構造 S 句構造 NP VP 私は PP NP VP 依存構造 ペンを 置いた 机の上に 私は 机の 上に ペンを 置いた

20 依存文法の長所 係り元と係り先の関係は個々に調べられるため、省略や語順に関係なく解析可能 格解析も同時解析可能
句構造解析でも語彙化の流れがあるが、依存文法はもともと単語を中心に考えられた文法である

21 機械学習による解析 単語と単語の依存構造を機械学習で判定 ツリーバンク（正解データの集合）の出現
動的に生成されるデータ構造に強く依存しないためコンピュータ上で処理しやすい⇔句構造解析 エントロピー最大化法による日本語係り受け解析 (内元1998) Support Vector Machine (SVM)による日本語係り受け解析 (工藤+2000) ツリーバンク（正解データの集合）の出現 正解データがあれば手でルールを書くより機械学習の素性（特徴ベクトル）を用意するほうが簡単でかつ高性能

22 CCG (Combinatorial categorial grammar)

23 CCG: 導入 長い歴史 範疇文法は、古くは Ajdukievicz (1935) や Bar-Hillel (1953)までさかのぼる Mark Steedman (1996, 2000) によるCCGが有名 講義内容 Mark Steedman (2000) The Syntactic Processから 語彙化文法 文法がなすべき役割を句構造規則ではなく、辞書に書き込むべき、という立場の文法 最新の文法理論はほとんどが語彙化文法

24 CCG: 導入 仕組 意味論 等位接続構造をうまく説明 カテゴリに対する関数適用を繰り返すことによって文を構成する
ラムダ式により語の意味を記述し、統語構造に対応したラムダ関数適用により文の意味表現を導出 M. Steedman は、可能な意味構造をすべて導出できれば、それに対応する統語構造はどれか一つだけあれば構わない、とする 等位接続構造をうまく説明

25 CCG: 形式 カテゴリ 原始カテゴリ (atomic category) 複合カテゴリ (complex category)
N (名詞) や S (文) など 複合カテゴリ (complex category) 他の二つのカテゴリから合成 数学的には、一方を定義域、片方を値域とする関数 X, Yがカテゴリなら、X／Y と X＼Y は複合カテゴリ。どちらもYを引数とし、Xを値とする関数 X／Yは、右側のYと結びついて、Xの記号となるという意味 X＼Yは、左側のYと結びついて、Xの記号となるという意味

26 CCG: カテゴリの例 カテゴリの例 married := (S＼NP)／NP 自動詞: S＼NP 他動詞(TV): (S＼NP)／NP
ditransitive verb(DTV): ((S＼NP)／NP)／NP 目的語 主語

27 CCG: ``pure’’ categorial grammar
関数適用規則 (functional application rules) X／Y Y ⇒ X (>) Y X＼Y ⇒ X (<) 例 Anna married Manny NP (S＼NP)／NP NP S＼NP S Anna married Manny V NP VP S > <

28 CCG: カテゴリの補足 カテゴリに付随する素性 演算は素性の値は単一化により計算される（HPSGの講義の時に詳しく述べる）
NP3s, NP3sfなど 例 Anna married Manny NP3sf (S＼NP3s)／NP NP S＼NP3s S 演算は素性の値は単一化により計算される（HPSGの講義の時に詳しく述べる） > <

29 CCG: 意味論 (1/3) CCGの規則に付随するラムダ式により述語項構造 (predicate-argument structures)を計算 ラムダ計算 λx.λy. marry’ x y ((λx.λy. marry’ x y) manny’) anna’ = (λy. marry’ manny’ y) anna’ =marry’ manny’ anna’ λf.λx. f xという風に関数も引数にとることができることに注意！ λf.λx. f xとλg.λy g y はまったく同じラムダ式であることに注意！

30 CCG: 意味論 (2/3) CCGの規則に付随するラムダ式により述語項構造 (predicate-argument structures)を計算 関数適用規則 (functional application) X／Y:f Y:a ⇒ X:f a (>) Y:a X＼Y:f ⇒ X:f a (<)

31 CCG:意味論(3/3) 例 Anna married Manny
NP3sf : anna’ (S＼NP3s)／NP: λx.λy.marry’ x y NP: manny’ S＼NP3s: λy. marry’ manny’ y S: marry’ manny’ anna’ > <

32 CCG: 等位接続構造 等位接続構造 等位接続規則（簡略版） 太郎と花子が歩いた 太郎が花子に会って、説明した
太郎は花子に、次郎は恵に話した 等位接続規則（簡略版） X CONJ X’ ⇒ X’’ (Φ)

33 CCG: 等位接続構造 例 Anna met and married Manny
NP (S＼NP)／NP CONJ (S＼NP)／NP NP (S＼NP)／NP S＼NP S Φ > <

34 CCG: 等位接続規則の意味論 等位接続規則 例 X :g CONJ:b X:f ⇒ X：λ...b(f...)(g...) (Φn)
Anna met and married Manny NP (S＼NP)／NP CONJ (S＼NP)／NP NP :anna’ :meet’ :and’ :marry’ :manny’ (S＼NP)／NP: λx.λy.and’(meet’ x y)(marry’ x y) S＼NP: λy.and’(meet’ manny’ y) (marry’ manny’ y) S: and’(meet’ manny’ anna’) (marry’ manny’ anna’) Φ > <

35 The Bluebird (ルリツグミ)

36 The Bluebird: 導入 Anna met and might marry Mannyの解析
met := (S＼NP)／NP marry := (S＼NP)／NP might := (S＼NP) ／(S＼NP) Anna might marry Mannyの解析 (S＼NP) metがMannyを目的語としてとれない！ mightがなければmetとmarryを等位接続できたのに…。 > >

37 The Bluebird 合成規則 (composition rule) 例 X/Y Y/Z ⇒ X/Z (>B)
Anna met and might marry Manny NP (S＼NP)／NP CONJ (S＼NP)／(S＼NP) (S＼NP)／NP NP (S＼NP)／NP S＼NP S >B Φ > <

38 Bluebirdの意味論 合成規則 (composition rule) 例
X／Y: f Y／Z: g ⇒ X／Z: λx.f(g x) (>B) 例 Anna met and might marry Manny NP (S＼NP)／NP CONJ (S＼NP)／(S＼NP) (S＼NP)／NP NP :anna’ :meet’ :and’ :might’ :marry’ :manny’ (S＼NP)／NP ：λx.λy.might’(marry’ x) y (S＼NP)／NP: λx.λy.and’(might’(marry’x) y)(meet’ x y) S＼NP: λy.and’(might’(marry’manny) y)(meet’ manny’ y) S: and’(might’(marry’manny’) anna’)(meet’ manny’ anna’) >B Φ > <

39 Bluebirdの心とは？ 目的語をまだとっていない大きな動詞句を先につくっていることに相当
目的語をとってから、主語をとる、といった関数適用による順番を変える 後から取るべきカテゴリを先にとって、先に取るべきカテゴリを遅延評価として取る

40 The thrush (ツグミ)

41 The Thrush : 導入 Anna married and I detest Mannyの解析
Anna, I, Manny := NP married, detest := (S＼NP)／NP Bluebirdを使って目的語をとらずに大きな動詞句を作りたいが、、、 先に主語＋動詞をくっつけることができない！

42 The Thrush 型繰り上げ (Type-Raising) 例 NP ⇒ S／(S＼NP) (>T)
Anna married and I detest Manny NP (S＼NP)／NP CONJ NP (S＼NP)／NP NP S／(S＼NP) S／(S＼NP) S／NP S／NP S／NP S >T >T >B >B Φ >

43 Thrushの意味論 型繰り上げ (Type-Raising) 例 X: a ⇒ T／(T＼X): λf. f a (>T)
Anna married and I detest Manny T／(T＼NP) (S＼NP)／NP CONJ T／(T＼NP) (S＼NP)／NP NP :λf.f anna’ :λx.λy.marry’ x y :and’ :λ‘f.f i’ :λx.λy.detest’ x y :manny’ S／NP: λx.marry’ x anna’ S／NP: λx.detest’ x i’ S／NP: λx.and’(detest’x i’)(marry’ x anna’) S: and’(detest’ manny’ i’)(marry’ manny’ anna’) >B >B Φ >

44 Thrushの意味論 Anna married and I detest Manny これがどうやってでてきたのか？bluebirdの規則が
T／(T＼NP) (S＼NP)／NP CONJ T／(T＼NP) (S＼NP)／NP NP :λf.f anna’ :λx.λy.marry’ x y :and’ :λ‘f.f i’ :λx.λy.detest’ x y :manny’ S／NP: λx.marry’ x anna’ S／NP: λx.detest’ x i’ S／NP: λx.and’(detest’x i’)(marry’ x anna’) S: and’(detest’ manny’ i’)(marry’ manny’ anna’) >B >B Φ > これがどうやってでてきたのか？bluebirdの規則が X／Y: f Y／Z: g ⇒ X／Z: λx.f(g x) (>B) なので、出力される意味構造は、 λz.f(g z) s.t. f＝λf.f anna’, g＝λx.λy.marry’ x y = λz.(λf.f anna’)((λx.λy.marry’ x y) z) ＝λz.(λf.f anna’)(λy.marry’ z y) = λz.((λy.marry’ z y) anna’) ＝λz.(marry’ z anna’)

45 Backward BluebirdとThrush
Y＼Z X＼Y ⇒ X＼Z (<B) 例 give a teacher an apple and a policeman a flower (VP／NP)／NP NP NP CONJ NP NP a teacher, a policeman NP ⇒<T (VP／NP)＼((VP／NP)／NP) an apple, a flower NP ⇒ <T (VP＼(VP／NP)) a teacher an apple, a policeman a flower (VP／NP)＼((VP／NP)／NP) (VP＼(VP／NP))⇒<B VP＼((VP／NP)／NP)

46 関係節もできる！ 例 (N＼N)／(S／NP) S／(S＼NP) (S＼NP)／NP (the man) that Anna married
>B >

47 Thrushの心とは？ 動詞が主語をとって文になるのではなく、名詞が動詞句をとって文になる、という解釈 anna := S／(S＼NP)
選択する側、される側が反転していることに注意！

48 STARLING (ムクドリ)

49 The Starling: 導入 Parasitic Gap 関係節の目的語と動名詞の目的語が共有される場合
articles whichi I will filei without readingi

50 The Starling 後ろ向き交差代入 (backward crossed substitution) 例
Y／Z (X＼Y)／Z ⇒ X／Z (<Sx) 例 (articles) which I will file without reading (N＼N)／(S／NP) S／VP VP／NP (VP＼VP)／VPing VPing／NP (VP＼VP)／NP VP／NP S／NP N＼N >B <Sx >B >

51 Starlingの意味論 後ろ向き交差代入 (backward crossed substitution)
Y／Z:g (X＼Y)／Z:f ⇒ X／Z: λx.fx(gx) (<Sx)

52 bird一覧 合成 (functional composition) 型繰り上げ(type-raising)
X／Y Y／Z ⇒ X／Z (>B) X／Y Y＼Z ⇒ X＼Z (>Bx) Y＼Z X＼Y ⇒ X＼Z (<B) Y／Z X＼Y ⇒ X／Z (<Bx) 型繰り上げ(type-raising) X ⇒ T／(T＼X) (>T) X ⇒ T＼(T／X) (<T) 代入(functional substitution) (X／Y)／Z Y／Z ⇒ X／Z (>S) (X／Y)＼Z Y＼Z ⇒ X＼Z (>Sx) Y＼Z (X＼Y)＼Z ⇒ X＼Z (<S) Y／Z (X＼Y)／Z ⇒ X／Z (<Sx)

53 擬似的曖昧性 擬似的曖昧性 (spurious ambiguity)
このような統語構造の順番を無視するような構造をつくると、同じ文に対して可能な解析が爆発的に増えてしまう 特に型繰り上げを使うと、無限に生成できてしまう

54 擬似的曖昧性 Anna married Mannyに対する普通の解析 Anna married Manny
NP: anna’ (S＼NP)／NP: λx.λy.marry’ x y NP: manny’ S＼NP: λy.marry’ manny’ y S: marry’ manny’ anna’ > <

55 擬似的曖昧性 その他の解析1 Anna married Manny
NP: anna’ (S＼NP)／NP: λx.λy.marry’ x y NP: manny’ T／(T＼NP) T＼(T／NP) ：λp.p anna’ :λq.q manny’ S＼NP: λy.marry’ manny’ y S: marry’ manny’ anna’ <T <T < >

56 擬似的曖昧性 その他の解析2 Anna married Manny
NP: anna’ (S＼NP)／NP: λx.λy.marry’ x y NP: manny’ T／(T＼NP) T＼(T／NP) ：λp.p anna’ :λq.q manny’ S／NP: λx.marry’ x anna’ S: marry’ manny’ anna’ <T <T >B <

57 擬似的曖昧性 解析過程や統語構造が異なっていても意味構造は同じ
パーザー(構文解析器）は、与えられた文に対する全ての意味構造に対し、それに対応するいくつかの統語構造さえ出力できれば良い⇦反論: 全ての統語構造を列挙しないと、全ての意味構造を列挙することは難しい⇦反論：普通の句構造解析でも同じようにたくさんの曖昧性はある⇦さらに言えば、実テキストを解析できるシステムが存在する

58 CCGのすごいところ (1/2) どちらが”良い“統語構造か？という長年の言語学的疑問に一つのエレガントな解を与えた⇒意味構造が同じならどちらでも良い 文節文法vs句構造文法 (NP-を (WH 花子が作った)(NP 弁当を)) (PP (NP (WH 花子が作った) 弁当) を) 句構造の曖昧性 Manny might watch Anna with a telescope. 動詞は目的語と結びついた後に助動詞と結びつくか、動詞と助動詞が結びついた後に目的語と結びつくか？ with a telescopeは``watch Anna’‘に結びつくのか、それとも、``might watch Anna’‘に結びつくのか？ もんちぇ

59 CCGのすごいところ (2/2) ほとんどの文法理論で失敗している等位接続構造をエレガントに説明できた ?
おじいさんは　山へ芝刈りに　おばあさんは　川へ洗濯に　いきました ?

60 まとめ CCG 次回は、10/29 (月) 16:30～ 型付素性構造と単一化とHPSGについて 講義資料 関数適用 bluebird
thrush starling 長所 次回は、10/29 (月) 16:30～ 型付素性構造と単一化とHPSGについて 講義資料