HPSG ( 前半 ) 二宮崇
今日の講義の予定 型付素性構造 (Typed Feature Structures) HPSG (Head-driven Phrase Structure Grammar, 主辞駆動句構造文法 ) 2
型付素性構造 3
型付素性構造 : 導入 非終端記号よりリッチなデータ構造 HPSGでは 辞書も 句構造規則も 句構造も木構造も全て型付素性構造で記述 表現 SYNSEM: synsem LOCAL: local CAT: noun NP sign NONLOCAL: nonlocal PHON: HD: an cons HD: apple TL: cons TL: nil 4
型付素性構造 : 導入 型付素性構造 (Carpenter 990, 992) 根付ラベル付有向グラフ グラフの各ノードに型が付与 グラフ間に包摂関係 2 つのグラフの単一化 ここでは Carpenter (992) The Logic of Typed Feature Structures, Cambridge University Press をベースに解説 5
型付素性構造 : 例 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
型付素性構造 : グラフ表記と グラフ表記 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
型付素性構造 : グラフ表記と 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
型付素性構造 : グラフ表記と 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
型付素性構造 : 形式的定義 TYPE: 型の有限集合 FEAT: 素性の有限集合 素性構造 F (=<Q, q 0, δ, θ>) Q: グラフを構成するノードの集合 q 0 : ルートノード (q 0 Q) δ: グラフのアークを表現する部分関数 (partial function Q FEAT Q) θ: ノードの型を返す全関数 (total function Q TYPE) 0
型付素性構造 : 形式的定義の例 素性構造 <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:
型階層 ( 型の定義 ) 型階層の例 円筒 正方形 verb adj perp 特殊 円 長方形 菱形 subst func 丸 四角 plus minus head 図形 bool 一般 ( ボトム ) 2
型の包摂関係 (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
型単一化 (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
t4 の上界 t6 型の単一化の例 t3 t8 t2 t9 の上界 特殊 t3 t5 t7 t0 t UB(t4,t9) t2 t4 t9 t4 t9 t ( ボトム ) 一般 5
型階層の問題と制限 解が一つに定まらない場合 単一化の結果が複数解になって計算機的に扱いづらい 予想しなかった解が複数出現する 例 : t t2=t3 or t4 対策 型階層の定義を与える際に単一化の結果が複数になるような型階層を禁止する 単一化の結果を disjunction と して処理する ここでは型単一化の結果は定義なしか ひとつしかないと仮定する t t3 ( ボトム ) t4 t2 6
型階層と素性の導入 名簿の例 名簿項目郵便番号 :integer 住所 :string 電話番号 :integer 姓 :string 旧姓 :string 名 :string 特殊 昔の名前旧姓 :string 名 :string 名前姓 :string 名 :string 住所郵便番号 :integer 住所 :string 電話番号電話番号 :integer 名名 :string ( ボトム ) より特殊な型はより一般な型の素性を全て持つことに注意! 一般 7
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
Appropriateness: Feature Introduction だめな例 良い例 t3 F: t2 F: t3 F: t F: t2 F: t F: ( ボトム ) F: を持つ最も一般な型が二つある ( ボトム ) F: を持つ最も一般な型が唯一存在 9
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
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
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
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
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
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
素性構造の包摂関係 (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
包摂関係 ( 構造共有 ) 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
包摂関係 ( サイクル ) F F t t F: F: F: F: t t F: F: t F: t 28
包摂関係の考え方 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
例の前に 例中では簡略のために well-typedness にはこだわらないようにします 型も 以外とは単一化できないとします グラフのリーフ以外では型の表記を省略します AVM 表記にします 30
包摂関係の例 例 F: F: a F: F: a G: b G: F: c H: a G: F: c G: I: a J: b H: a 3
包摂関係の例 例 2 F: F: a F: F: a H: c G: H: c G: 32
包摂関係の例 例 3 どっちがより特殊か? F: a G:a F: a G: G: a F: a G: F: a 33
素性構造の単一化 素性構造 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
単一化の考え方 二つの素性構造 F, G の両方に含まれる情報が全て保存されている (F, G の情報をマージした構造 ) 制約 構造共有を通して情報を伝達 サイクルを含む場合も大丈夫だけど 特に難しく考える必要はない 35
単一化の例 例 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
素性構造単一化の例 例 2 構造共有を含む場合 F: F: a G: G: G: G: G: b = F: G: G: F: a G: b 37
素性構造単一化の例 例 3 構造共有を含む場合 2 2 3 3 F: a G: H: I: J: K: G: H: 4 4 I: 5 = J: K: L: 5 6 6 7 7 7 7 7 7 7 F: a G: H: I: J: K: L: L: の値も a であることに注意! 構造共有を通して F:a の a が L: まで伝搬している 38
素性構造単一化の例 例 4 サイクルを含む場合 F:F:F:F:F:F: 2 F:F:F:F: 2 = 3 F:F: 3 39
素性構造の 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
素性構造の alternatives Feature Algebra (Smolka 988, 989) 記述に対応する全ての可能な素性構造集合 包摂関係 : 素性構造集合の包含関係 単一化 : 素性構造集合の積集合 記述と意味が一体化 パスの値の記述 パス等式 単一化が全て素性構造集合のドメインから素性構造のドメインへの関数として定義 Attribute-Value Logic (Johnson988) 4
HPSG (HEAD-DRIVEN PHRASE STRUCTURE GRAMMAR, 主辞駆動句構造文法 ) 42
HPSG: 導入 Head-driven Phrase Structure Grammar (Pollard & Sag 985, 994) 主辞が中心的な役割を果たす文法枠組 辞書の情報を増やすことにより 句構造規則をできる限り減らす辞書指向 素性構造 単一化に基づく単一化文法の一つ ここでは Pollard & Sag (994) Head-driven Phrase Structure Grammar, University of Chicago Press に基づいて解説 43
HPSG: 導入 主辞 句構造の中心的役割を果たす語 句のこと 例 : 美しい花 花 例 : 彼は美しい花を見た 見た 直感的には 最も重要そうな要素 他に修飾先がない要素のことを指すと考えればとりあえず差し支えない 44
HPSG: 導入 語彙化文法 CFG では些細な方針変更の結果 ほとんどの句構造規則を書きなおさなくてはいけなくなってしまったり 例 :S NP VP, VP V NP とあったとき 主語の NP と目的語の NP はどのような名詞がくるのか その分布が異なるので NP-SUBJ と NP-OBJ にわけたい しかし そうすると NP N,... とある規則も全て書き直し しかも N taro などの規則も二重に書かなくてはいけない! 単語ごとに例外的 固有の振舞いが多い 結果 単語を付与した非終端記号になり そのための句構造規則を追加しなくてはいけない 45
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
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
句構造規則 HEAD-COMPLEMENT-SCHEMA SUBJ: COMPS: SPR: 4 3 HEAD COMP VAL: SUBJ: COMPS: < 2 3 > SPR: 4 2 48
句構造規則 HEAD-SUBJECT-SCHEMA VAL: SUBJ:<> COMPS:<> SPR:<> SUBJ HEAD VAL: SUBJ: COMPS: <> SPR:<> 49
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
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
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
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
まとめ 型付素性構造 HPSG の導入 54