数理言語

Size: px

Start display at page:

Download "数理言語"

ありさゆのもと
6 years ago
Views:

1 HPSG ( 前半 ) 二宮崇

2 今日の講義の予定型付素性構造 (Typed Feature Structures) HPSG (Head-driven Phrase Structure Grammar, 主辞駆動句構造文法 ) 2

3 型付素性構造 3

4 型付素性構造 : 導入非終端記号よりリッチなデータ構造 HPSGでは辞書も句構造規則も句構造も木構造も全て型付素性構造で記述表現 SYNSEM: synsem LOCAL: local CAT: noun NP sign NONLOCAL: nonlocal PHON: HD: an cons HD: apple TL: cons TL: nil 4

5 型付素性構造 : 導入型付素性構造 (Carpenter 990, 992) 根付ラベル付有向グラフグラフの各ノードに型が付与グラフ間に包摂関係 2 つのグラフの単一化ここでは Carpenter (992) The Logic of Typed Feature Structures, Cambridge University Press をベースに解説 5

6 型付素性構造 : 例 HPSGでの she に対する素性構造 cons TL: PHON: word BACKGROUND: nil HD: cons SYNSEM: HD: context TL: synsem she nil LOCAL: CONTEXT: RELN: psoa female local ppro CAT: HEAD: cat CONTENT: INDEX: RESTR: nil INSTANCE: CASE: noun valence VALENCE: ref PERS: nom nil SUBJ: COMPS: SPR: GEND: NUM: nil nil fem sing 3rd 6

7 型付素性構造 : グラフ表記とグラフ表記 HEAD: cat noun 型 (type) CASE: VALENCE: nom SUBJ: valence AVM 表記 COMPS: SPR: nil nil nil AVM 表記 cat HEAD: 型 (type) VALENCE: noun CASE: nom 素性 (feature) valence SUBJ: <> COMPS: <> SPR: <> 素性 (feature) 7

8 型付素性構造 : グラフ表記と AVM 表記 ( 構造共有 ) グラフ表記 cat noun CASE: HEAD: SPR: SUBJ: VALENCE: valence COMPS: nil nom AVM 表記 cat HEAD: VALENCE: 構造共有 (reentrancy, structure-sharing) noun CASE: 2 nom valence SUBJ: COMPS: <> SPR: 2 8

9 型付素性構造 : グラフ表記と AVM 表記 ( サイクル ) グラフ表記 AVM 表記 CASE: nom HEAD: cat VALENCE: noun SUBJ: COMPS: valence SPR: nil nil cat HEAD: VALENCE: noun CASE: nom valence SUBJ: COMPS: <> SPR: <> 9

10 型付素性構造 : 形式的定義 TYPE: 型の有限集合 FEAT: 素性の有限集合素性構造 F (=<Q, q 0, δ, θ>) Q: グラフを構成するノードの集合 q 0 : ルートノード (q 0 Q) δ: グラフのアークを表現する部分関数 (partial function Q FEAT Q) θ: ノードの型を返す全関数 (total function Q TYPE) 0

11 型付素性構造 : 形式的定義の例素性構造 <Q, q 0, θ, δ> Q = {q 0, q, q 2, q 3, q 4, q 5 } δ(q 0, CAT:)=q δ(q 0, AGR:)=q 2 δ(q 0, SUBJ:)=q 3 δ(q 2, NUM:)=q 4 δ(q 2, PERS:)=q 5 δ(q 3, AGR:)=q 2 θ(q 0 ) = sign θ(q ) = S θ(q 2 ) = agr θ(q 3 ) = sign θ(q 4 ) = sing θ(q 5 ) = 3rd sign CAT: S AGR: SUBJ: agr NUM: sing PERS: 3rd sign AGR:

12 型階層 ( 型の定義 ) 型階層の例円筒正方形 verb adj perp 特殊円長方形菱形 subst func 丸四角 plus minus head 図形 bool 一般 ( ボトム ) 2

13 型の包摂関係 (type subsumption relation) t6 t8 t3 t2 t9 より特殊な型 t9 t0 t9 t t9 t2 t9 t3 特殊 t3 t5 t7 t0 t t4より特殊な型 t2 t4 t5 t4 t6 t4 t7 t4 t8 t4 t2 t4 t3 t t4 ( ボトム ) t9 一般 3

14 型単一化 (type unification) t, u TYPE が与えられた時 UB(t, u) = {v TYPE t v u v} t u is v TYPE s.t. v UB(t, u) and w UB(t, u).v w t u: 単一化の結果 join least upper bound と呼ばれる解がない場合は定義なし unification failure inconsistent ( トップ ) と書いたり呼んだりする 4

15 t4 の上界 t6 型の単一化の例 t3 t8 t2 t9 の上界特殊 t3 t5 t7 t0 t UB(t4,t9) t2 t4 t9 t4 t9 t ( ボトム ) 一般 5

16 型階層の問題と制限解が一つに定まらない場合単一化の結果が複数解になって計算機的に扱いづらい予想しなかった解が複数出現する例 : t t2=t3 or t4 対策型階層の定義を与える際に単一化の結果が複数になるような型階層を禁止する単一化の結果を disjunction として処理するここでは型単一化の結果は定義なしかひとつしかないと仮定する t t3 ( ボトム ) t4 t2 6

名前姓 :string 名 :string 住所郵便番号 :integer 住所 :string 電話番号電話番号

17 型階層と素性の導入名簿の例名簿項目郵便番号 :integer 住所 :string 電話番号 :integer 姓 :string 旧姓 :string 名 :string 特殊昔の名前旧姓 :string 名 :string 名前姓 :string 名 :string 住所郵便番号 :integer 住所 :string 電話番号電話番号 :integer 名名 :string ( ボトム ) より特殊な型はより一般な型の素性を全て持つことに注意! 一般 7

18 Appropriateness Approp: FEAT TYPE TYPE Feature Introduction For every feature f FEAT, there is a most general type Intro(f) TYPE s.t. Approp(f, Intro(f)) is defined Upward Closure / Right Monotonicity If Approp(f, t) is defined and t u, then Approp(f, u) is also defined and Approp(f, t) Approp(f, u) 8

19 Appropriateness: Feature Introduction だめな例良い例 t3 F: t2 F: t3 F: t F: t2 F: t F: ( ボトム ) F: を持つ最も一般な型が二つある ( ボトム ) F: を持つ最も一般な型が唯一存在 9

20 Appropriateness: Upward Closure / Right Monotonicity t6 F: t4 F: t5 F:string Approp(F:, t3) Approp(F:, t7) t7 F:integer t2 F: t3 F: t F: ( ボトム ) ある型に F: が一度導入されるとそれより特殊な型は全て F: を持たなければならない 20

21 Well-Typed Feature Structures Well-Typedness 素性構造 F=<Q, q 0, θ, δ> は下記の条件を満たすとき well-typed と呼ばれる δ(f, q) が定義されている時には常に Approp(f, θ(q)) が定義されておりかつ Approp(f, θ(q)) θ(δ(f, q)) 2 つの Well-typed feature structures の単一化の結果も well-typed feature structure になる 2

22 Well-Typed Feature Structures 例 Appropriate な型よりもインスタンスの型は必ず特殊でなければならない HD: HOGE: cons TL: cons TL: HD: cons 2 HD: cons HD:integer TL: list nil 3 TL: nil list 各ノードに対しそのノードの型に定義されていない素性が存在してはいけない ( ボトム ) 22

23 Totally Well-Typed Feature Structures Total Well-Typedness 素性構造 F=<Q, q 0, θ, δ> は下記の条件を満たすとき totally well-typed と呼ばれる F は well-typed 各ノード q に対し Approp(f, θ(q)) が定義されている全ての素性 f に対し δ(f, q) が定義されていなければならない Approp が loop-free であるとき 2 つの totally well-typed feature structures の単一化の結果も totally well-typed feature structures である 23

24 Totally Well-Typed Feature Structures Totally well-typed feature structures でない例 Totally well-typed feature structure の例 HD: HD: cons TL: cons HD: cons TL: cons HD: 2 TL: nil cons HD:integer TL: list nil TL: nil list 24

25 Totally Well-Typed Feature Structures 無限ループに陥ってしまうケース cons TL: HD: cons TL: HD: cons TL: 2 HD: cons integer HD: このような型階層を作らないようにするか実装の段階で delayed evaluation をすれば良い c.f. LiLFeS では delayed evalution で実現されている integer cons HD:integer TL: cons nil TL:... list 25

26 素性構造の包摂関係 (subsumption relation) 2 つの素性構造 F=<Q, q 0, θ, δ>, F =<Q, q 0, θ, δ > は次の条件を満たす全域関数 (total function) h:q Q が存在するとき F は F を包摂するという (F F ) h(q 0 ) = q 0 θ(q) θ(h(q)) for every q Q h(δ(f, q)) = δ (f, h(q)) for every q Q and feature f such that δ(f, q) is defined 26

27 包摂関係 ( 構造共有 ) F F F F d d d F: G: G: F: G: F: F: b c G: F: d G: b F: c G: e a e a a a 27

28 包摂関係 ( サイクル ) F F t t F: F: F: F: t t F: F: t F: t 28

29 包摂関係の考え方 F F であるということは F にある情報は全て F にあるということである F より F の全てのパス値がより特殊パス p とは素性 f の列のこと p = f, f 2,.., f n であるとき δ(p, q) = δ(f n,...δ(f 2, δ(f, q))...) と δ を拡張する F の全てのパス p に対し θ(δ(p, q 0 )) θ(δ(p, q 0 )) F に含まれる全ての構造共有は F にも含まれている 29

30 例の前に例中では簡略のために well-typedness にはこだわらないようにします型も以外とは単一化できないとしますグラフのリーフ以外では型の表記を省略します AVM 表記にします 30

31 包摂関係の例例 F: F: a F: F: a G: b G: F: c H: a G: F: c G: I: a J: b H: a 3

32 包摂関係の例例 2 F: F: a F: F: a H: c G: H: c G: 32

33 包摂関係の例例 3 どっちがより特殊か? F: a G:a F: a G: G: a F: a G: F: a 33

34 素性構造の単一化素性構造 F, G F が与えられた時 UB(F, G) = {H F F H G H} F G is H F s.t. H UB(F, G) and I UB(F, G).H I つまり F,G より特殊な素性構造のうちもっとも一般な素性構造が単一化の結果 34

35 単一化の考え方二つの素性構造 F, G の両方に含まれる情報が全て保存されている (F, G の情報をマージした構造 ) 制約構造共有を通して情報を伝達サイクルを含む場合も大丈夫だけど特に難しく考える必要はない 35

36 単一化の例例 F: G: F: a F: c H: a F: G: F: a G: b G: I: a J: b = F: G: F: a G: b F: c G: I: a J: b H: a 異なる型の場合は型単一化を行う型単一化に失敗すると全体の単一化も失敗 36

37 素性構造単一化の例例 2 構造共有を含む場合 F: F: a G: G: G: G: G: b = F: G: G: F: a G: b 37

38 素性構造単一化の例例 3 構造共有を含む場合 F: a G: H: I: J: K: G: H: 4 4 I: 5 = J: K: L: F: a G: H: I: J: K: L: L: の値も a であることに注意! 構造共有を通して F:a の a が L: まで伝搬している 38

39 素性構造単一化の例例 4 サイクルを含む場合 F:F:F:F:F:F: 2 F:F:F:F: 2 = 3 F:F: 3 39

40 素性構造の alternatives Denotational Model of Descriptions (Pereira & Shieber 984) p=a ( パスと値の等式の集合 ) p=q( パスとパスの等式の集合 ) ε=ε pq=x p = p x=y y=x p=x, x = q p = q Deductive Closure: 上記の式で展開されうるすべての等式集合包摂関係 : deductive closure の包含関係単一化 : deductive closure の和集合 p=q, pr=x qr=x 40

41 素性構造の alternatives Feature Algebra (Smolka 988, 989) 記述に対応する全ての可能な素性構造集合包摂関係 : 素性構造集合の包含関係単一化 : 素性構造集合の積集合記述と意味が一体化パスの値の記述パス等式単一化が全て素性構造集合のドメインから素性構造のドメインへの関数として定義 Attribute-Value Logic (Johnson988) 4

42 HPSG (HEAD-DRIVEN PHRASE STRUCTURE GRAMMAR, 主辞駆動句構造文法 ) 42

43 HPSG: 導入 Head-driven Phrase Structure Grammar (Pollard & Sag 985, 994) 主辞が中心的な役割を果たす文法枠組辞書の情報を増やすことにより句構造規則をできる限り減らす辞書指向素性構造単一化に基づく単一化文法の一つここでは Pollard & Sag (994) Head-driven Phrase Structure Grammar, University of Chicago Press に基づいて解説 43

44 HPSG: 導入主辞句構造の中心的役割を果たす語句のこと例 : 美しい花花例 : 彼は美しい花を見た見た直感的には最も重要そうな要素他に修飾先がない要素のことを指すと考えればとりあえず差し支えない 44

45 HPSG: 導入語彙化文法 CFG では些細な方針変更の結果ほとんどの句構造規則を書きなおさなくてはいけなくなってしまったり例 :S NP VP, VP V NP とあったとき主語の NP と目的語の NP はどのような名詞がくるのかその分布が異なるので NP-SUBJ と NP-OBJ にわけたいしかしそうすると NP N,... とある規則も全て書き直ししかも N taro などの規則も二重に書かなくてはいけない! 単語ごとに例外的固有の振舞いが多い結果単語を付与した非終端記号になりそのための句構造規則を追加しなくてはいけない 45

46 HPSG: 辞書項目辞書項目 she に対する素性構造 word synsem local she PHON: SYNSEM: LOCAL: cons nil HD: TL: cat CAT: noun nom CASE: HEAD: valence nil nil nil SUBJ: COMPS: SPR: VALENCE: context CONTEXT: ppro CONTENT: nil RESTR: ref INDEX: fem sing 3rd NUM: PERS: GEND: cons BACKGROUND: nil TL: psoa female RELN: HD: INSTANCE: 46

47 HPSG: 辞書項目 she に対応する素性構造 (AVM 表記 ) word PHON: <she> synsem SYNSEM: LOCAL: local CAT: cat HEAD: VALENCE: noun CASE: num valence SUBJ:<> COMPS:<> SPR:<> CONTENT: CONTEXT: ppro INDEX: RESTR: <> ref PER: 3rd NUM: sing GEND: fem context psoa BACKGR: < RELN: female > INST: 47

48 句構造規則 HEAD-COMPLEMENT-SCHEMA SUBJ: COMPS: SPR: 4 3 HEAD COMP VAL: SUBJ: COMPS: < 2 3 > SPR:

49 句構造規則 HEAD-SUBJECT-SCHEMA VAL: SUBJ:<> COMPS:<> SPR:<> SUBJ HEAD VAL: SUBJ: COMPS: <> SPR:<> 49

50 PHON: <gives> NP[3rd, sing] VAL: SUBJ: <NP[nom, 3 rd, sing]> COMPS: <NP[acc], NP[acc]> SPR: <> NP NP he gives her a present

51 PHON: <gives, her> VAL: SUBJ:< COMPS:< SPR:<> 3 NP[nom]> NP[acc]> NP[3rd, sing] PHON: <gives> VAL: SUBJ: < > COMPS: < 2, 3 > SPR: <> 2 NP[acc] NP he gives her a present

52 PHON: <gives, her, a present> VAL: SUBJ: < COMPS: <> SPR:<> NP[nom]> PHON: <gives, her> VAL: SUBJ:< > COMPS:< 3 > SPR:<> NP[3rd, sing] PHON: <gives> VAL: SUBJ: < > COMPS: < 2, 3 > SPR: <> 2 NP[acc] 3 NP[acc] he gives her a present

53 PHON: <he, gives, her, a present> VAL: SUBJ: <> COMPS: <> SPR: <> PHON: <gives, her, a present> VAL: SUBJ: < > COMPS: <> SPR:<> PHON: <gives, her> VAL: SUBJ:< > COMPS:< 3 > SPR:<> NP[nom, 3rd, sing] PHON: <gives> VAL: SUBJ: < > COMPS: < 2, 3 > SPR: <> 2 NP[acc] 3 NP[acc] he gives her a present

54 まとめ型付素性構造 HPSG の導入 54

数理言語

数理言語情報論第 5 回 2009 年月 4 日数理言語情報学研究室講師二宮崇今日の講義の予定 HPSG (HEAD-DRIVEN PHRASE STRUCTURE GRAMMAR, 主辞駆動句構造文法 ) 2 HPSG: 導入 Head-driven Phrase Structure Grammar (Pollard & Sag 985, 994) 主辞が中心的な役割を果たす文法枠組辞書の情報を増やすことにより