数理言語情報論 第 2 回 数理言語情報学研究室 講師 二宮 崇 2009 年 10 月 14 日 1.

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

1 数理言語情報論 第 2 回 数理言語情報学研究室 講師 二宮 崇 2009 年 10 月 14 日 1

2 今日の講義の予定 CFG (Context Free Grammar, 文脈自由文 法 ) 言語学での発展 TAG (Tree Adjoining Grammar) Dependency Grammar ( 依存文法 ) 2

3 ＣＦＧ 3

4 CFG ( 文脈自由文法 ): 導入 正規言語と正規文法（有限オートマトンが受理 する表現とその文法； c.f. regular expression ） (“a” + “b”) ＊ は ”a“ と ”b“ の任意の組み合わせの文字列 を受理する。 E.g., aabababbab… 正規文法の限界 a n b n を受理することができない 入れ子表現「（太郎は（花子が使っていた）ペンを借り た）」など チョムスキーが言語を扱うために次の文法階層 を規定 文脈依存文法 (Context Sensitive Grammar) 文脈自由文法 (Context Free Grammar) 4

5 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 ⇒ 香織 が 恵 が 送った 電子メール を 読んだ * 5

6 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 が OBJ1 V 香織 読んだ を NP S 電子メール SUBJ V NP が 恵 送った 6

7 CFG: 再帰的 NP → S NP 太郎が好きな花子が好きな次郎 が好きな恵が好きな香織が好き な ……….. 簡単な 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 A B xx’yy’ 7

8 形式文法 G (= ) V N : 非終端記号の集合 V T : 終端記号の集合 P: 書換規則の集合 σ : 開始記号 ( σ ∈ N) P は次の形 α→β α ∊ V +, β ∊ V *, V = V N ∪ V T 開始記号 σ から書換規則を順次適用して生 成される言語 L(G) を 0 型言語と呼ぶ 8

9 チョムスキーの階層 0 型文法（チューリング機械） もっとも制約のない形式文法 1 型文法（文脈依存文法） α→β （ |α| ≦ |β| ） 2 型文法（文脈自由文法） A →β （ A ∊ V N, β ∊ V ＋ ） 3 型文法（正規文法） A→aB A→a (A, B ∊ V N, a ∊ V T ) 9

10 CFG の例 G (= ) V N = {S, NP, NP1, SUBJ, OBJ1, V, VP1} V T ={ 香織, 恵, 電子メール, プレゼント, と, が, を, 送った, 読んだ } P = { 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 10

11 CFG の限界 uv i wx i y (i = 0, 1, 2, …) 正規文法では表現できない CFG は表現できる {a n b n c n | ( n = 0, 1, 2, …)} CFG は表現できない 文脈依存文法は表現できる 11

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

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

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

15 言語学での発展 15

16 言語学 ソシュールの構造主義 言語をばらばらな要素の羅列と考えず、要素 の関係による構造または体系として捉える 個々の要素をより大きな構造全体の中で位置 づける 各要素の具体的な特徴ではなく、他の要素の 相対的な関係（差異）から規定される 特定の言語の時間にそった変化（通時態）を 追うのではなく、特定の言語の一時期の状態 （共時態）を追う 16

17 構造主義 誤解をおそれずにたとえると、、、 ハンバーガーとは、「 αβ*α 」である ハンバーガーの「意味」 を考えるのではなくその 「関係」だけを考える α α β ββ 17

18 構造主義といえば、、、 レヴィストロース 「『構造』とは要素と要素間の 関係とからなる全体であって、 この関係は一連の変形過程を通 じて不変の特性を保持する」 顔 目、口、鼻、耳などのパーツから なるが、個々のパーツの関係で顔 が構成される 世の中にある多種多様な顔は 「顔」という関係の変形 18

19 「アリストテレスが死ぬ」とはどういうこ とですか？ 死ぬ ( アリストテレス ) 同義語 ( 死ぬ, 亡くなる ), 同義語 ( 死ぬ, 死亡する ), ……. つまり、構造主義とは、、、 これだけ？！ 19

20 構造言語学 構造言語学 ブルームフィールド以後の言語学 発話の資料体（コーパス）を構成する要素の 帰納的・分類的研究 コーパスを構成する要素 音素 形態素 20

21 チョムスキーの変形生成文法 構造言語学への批判 帰納的・分類的から演繹的・説明的 コーパスに直接みえる構造ではなく、人間の言語を 生成する能力に注目 言語の構造や体系を重視・優先 CFG による文法の記述 CFG への批判 自然言語を記述するには不足 CFG ＋変形操作の文法 ( ＝変形生成文法 ) 21

22 チョムスキーの変形生成文法 CFG ＋変形 d －構造 S NP VP INFL V PAST NP Mary V fired VP be 22

23 チョムスキーの変形生成文法 CFG ＋変形 s －構造 S NP VP INFL V PAST NP εiεi V fired VP be Mary i 23

24 チョムスキーの変形生成文法 普遍文法 (Universal Grammar) 個々の言語は普遍文法のパラメータの設定に より得られる Ｘバー理論 名詞が形容詞や冠詞と結びつき名詞句となる θ 理論 下位範疇化 適格文 / 非文 適格文、非文の区別により、正しい文法を模 索する ⇔ Meaning-Text Theory 24

25 チョムスキーという人 チョムスキー？？？ 構造主義的認知科学的 政治的にも有名？ 25

26 チョムスキー以後 様々な文法理論 GPSG HPSG LFG TAG …. しかし、基本的な考え方はチョムスキーと同じ 26

27 TAG 27

28 TAG (Tree Adjoining Grammar, 木接合文法 ) TAG A. K. Joshi が提案 複雑な形をした句構造木そのものが文法の基 本要素 ( 基本木, elementary trees) 初期木 (initial trees) 補助木 (auxiliary trees) 2 種類の操作で構文解析 代入 (substitution) 接合 (adjoining) 28

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

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

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

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

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

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

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

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

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

38 TAG TAG は形式的に (∑, NT, I, A, S) の 5 つ組 ∑ … 終端記号の集合 NT … 非終端記号の集合 I … 初期木の集合 A … 補助木の集合 S … S ⊂ NT, 文を表す非終端記号 弱文脈依存文法 (mildly context sensitive grammar) 導出過程木が依存構造に対応 38

39 TAG: 初期木と接合木 初期木 α1 S eats VBZ NP VP NP VP VP* RB always 接合木 β1 足 (foot) 脊柱？ (spine) アンカー (anchor) 幹 (trunk) 39

40 TAG: 導出過程木 (derivation tree) α1 α2 α3 NP John NP apples S eats VBZ NP VP NP α1 (eats) α2 (John)α3 (apples) Derivation tree 40

41 TAG: 導出過程木 (derivation tree) α1 β1 John S eats VBZ NP VP NP VP VP* RB always apples α1 (eats) α2 (John) α3 (apples) Derivation tree β1 (always)

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

43 Non-local Dependencies α1 S likes VBZ NP VP NP α2 VP NP VB likes S NP NP(i) ε(i) 他動詞 目的語が外置された他動詞 43

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

45 Non-local Dependencies S know VB S VP NP VP NP VB likes NP NP(i) ε(i) Sandy Kim we 45

46 言語学的考察 R. Frank ``Phrase Structure Composition and Syntactic Dependencies’’ MIT Press 2002 46

47 Extensions LTAG (Lexicalized Tree Adjoining Grammar) 全ての基本木は必ず一つ以上のアンカーをも つ FB-LTAG (Feature-Based LTAG) 構文木ノードに素性構造を追加したもの 素性構造については後の講義で説明 数や人称の制約を容易にいれられる XTAG (Doran+1994, 1997) が有名 47

48 計算量 TAG の計算量は一般に O(n 6 ) n は文の単語長 C.f. CFG は O( n 3 ) Tree Insertion Grammar (TIG) 補助木の足が左端あるいは右端にあらわれる ことだけを要求 O( n 3 ) 48

49 依存文法 49

50 依存文法 : 導入 日本語の場合 語順が比較的自由 格要素の省略が可能 日本語だけではなく比較的自由な語順の言 語は多い（語順が入れ替わる現象はスクラ ンブリングと呼ばれる） チェコ語（依存文法の研究で有名） ドイツ語（句構造のスクランブリングの研究 で有名） … 50

51 依存文法 : 導入 英語の例 I put a pen on the table (ok) *A pen put I on the table (NG) * I put a pen (NG) 日本語の例 私は机の上にペンを置いた。 (ok) ペンを私は机の上に置いた。 (ok) 私はペンを置いた。 (ok) 51

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

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

54 依存構造の文法 二つの依存可能な「係り元」「係り先」を 記述 簡単な日本語文法の例 係り元係り先 名詞＋格助詞「が」ガ格を持つ動詞 名詞＋格助詞「を」ヲ格を持つ動詞 動詞 連用形動詞、形容詞、形容動詞 動詞 連体形名詞 動詞＋述語接続助詞動詞、形容詞、形容動詞 副詞動詞、形容詞、形容動詞 連体詞名詞 54

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

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

57 ツリーバンクの例 プラハ依存構造ツリーバンク 57

58 Projective or Non-projective 非交差条件 使った 盗んだ 太郎は花子がペンを 使った花子がペンを盗んだ太郎は Good! Bad! 58

59 Projective or Non-projective 非交差条件の例外 正しいとこれが思う僕は 59

60 Projective or Non-projective Projective dependency parsing: 係り受けが交差 することを想定しない解析 句構造解析と同様の動的計画法が使えるため効率的 c.f. Eisner Algorithm O( n 3 ) (Eisner 1996) Non-Projective dependency parsing: 係り受け が交差することを想定した解析 単語対の全ての組み合わせに対し解析するため非効 率的（だと思われていた） 単語＝頂点、係り受けの重み＝枝の重みとみなすと、 maximum spanning tree の問題に帰着可 (McDonald+2005) Chu-Liu-Edmond algorithm O( n 2 ) (Chu and Liu 1965; Edmond 1967; Tarjan 1977) 60

61 まとめ 文法枠組 CFG TAG 依存文法 次回は 10 月 21 日（水） 16 ： 30 から 講義スライド http://www.r.dl.itc.u-tokyo.ac.jp/~ninomi/mistH21w/cl/ 61