人工知能特論II 第3回
二宮 崇
1
今日の講義の予定
TAG (Tree Adjoining Grammar)
 Dependency Grammar (依存文法)

2
TAG
3
TAG (Tree Adjoining Grammar,
木接合文法)

TAG
A. K. Joshiによって提案
 複雑な形をした句構造木そのものが文法の基
本要素 (基本木, elementary trees)

 初期木(initial
trees)
 補助木(auxiliary trees)

2種類の操作で構文解析
代入(substitution)
 接合 (adjoining)

4
TAG:代入 (substitution)
α1
X↓
X
α2
Y↓
Y
代入
X
Y
α3
5
TAG:接合 (adjoining)
β1
α1
X
補助木 (auxiliary tree)
X*
X
接合
Y
X
X*
6
TAG: 例
α2
β1
NP
α1
S
John
NP
α3 NP
VP
RB
VP
VBZ
NP
VP*
always
eats
apples
7
TAG: 例
α2
β1
NP
α1
S
John
NP
α3 NP
VP
RB
VP
VBZ
NP
VP*
always
eats
apples
8
TAG: 例
α2
β1
NP
α1
S
John
NP
α3 NP
VP
RB
VP
VBZ
NP
VP*
always
eats
apples
9
TAG: 例
β1
α2
α1
VP
S
NP
α3
John
RB
VP
VBZ
NP
VP*
always
eats apples
10
TAG: 例
β1
α2
α1
VP
S
NP
α3
John
RB
VP
VBZ
NP
VP*
always
eats apples
11
TAG: 例
β1
α2
α1
VP
S
NP
α3
John
RB
VP
VBZ
NP
VP*
always
eats apples
12
TAG: 例
β1
α2
α1
S
VP
NP
α3
John
RB
always
VP
VBZ
NP
eats apples
13
TAG

TAGは形式的に(∑, NT, I, A, S)の5つ組
∑ … 終端記号の集合
 NT … 非終端記号の集合
 I … 初期木の集合
 A … 補助木の集合
 S … S ⊂NT, 文を表す非終端記号
 接合可能なノードを指定しても良い

弱文脈依存文法 (mildly context sensitive
grammar)
 導出過程木が依存構造に対応

14
TAGの生成能力

CFGでは表現できないがTAGでは表現でき
る言語

… 接合可能なノード
L={anbncn|n∈N}
S
S
S
a
b
S*
c
ε
15
TAG: 初期木と接合木
接合木 脊柱?
β1 (spine)
初期木
α1
幹
(trunk)
S
NP
VP
VP
VBZ
NP
RB
VP*
always
eats
アンカー(anchor)
足 (foot)
16
TAG: 導出過程木 (derivation
tree)
α2
NP
α1
S
John
NP
α3 NP
VP
VBZ
eats
NP
Derivation tree
α1 (eats)
apples
α2 (John)
α3 (apples)
17
TAG: 導出過程木 (derivation
tree)
β1
α1
VP
S
NP
John
VP
VBZ
RB
NP
VP*
Derivation tree
always
eats apples
α2
(John)
α1
(eats)
α3
β1
(apples) (always)
CFG v.s. TAG
S
VP
NP
John
CFGだと、eatsの主語が
Johnであることがわかり
にくい
RB
always
VP
VBZ
Derivation tree
NP
eats apples
TAGだと、eatsの主語が
Johnであることがすぐわ
かる
α2
(John)
α1
(eats)
α3
β1
(apples) (always)
Non-local Dependencies
α2
NP
α1
S
NP
VP
VBZ
likes
S
NP(i)
NP
VP
NP
VB
likes
他動詞
NP
ε(i)
目的語が外置された他動詞
20
Non-local Dependencies
NP
β1
NP(i)
S
VP
NP
VB
know
α2
S
S
Sandy
S*
NP
VP
接合
Kim
VB
NP
likes ε(i)
21
Non-local Dependencies
NP
S
NP(i)
Sandy
we
VP
NP
S
VB
know
Kim
NP
VB
VP
NP
likes ε(i)
22
言語学的考察

R. Frank ``Phrase Structure Composition
and Syntactic Dependencies’’ MIT Press
2002
23
Extensions

LTAG (Lexicalized Tree Adjoining
Grammar)


全ての基本木は必ず一つ以上のアンカーをも
つ
FB-LTAG (Feature-Based LTAG)
構文木ノードに素性構造を追加したもの
 数や人称の制約を容易にいれられる
 XTAG (Doran+1994, 1997)が有名

24
計算量

TAGの計算量は一般にO(n6)
nは文の単語長
 C.f. CFGはO(n3)


Tree Insertion Grammar (TIG)
補助木の足が左端あるいは右端にあらわれる
ことだけを要求
 O(n3)

25
依存文法
26
依存文法: 導入

日本語の場合
語順が比較的自由
 格要素の省略が可能


日本語だけではなく比較的自由な語順の言
語は多い(語順が入れ替わる現象はスクラ
ンブリングと呼ばれる)
チェコ語(依存文法の研究で有名)
 ドイツ語(句構造のスクランブリングの研究
で有名)
…

27
依存文法: 導入

英語の例
I put a pen on the table (ok)
 *A pen put I on the table (NG)
 * I put a pen (NG)


日本語の例
私は机の上にペンを置いた。(ok)
 ペンを私は机の上に置いた。(ok)
 私はペンを置いた。(ok)

28
句構造と依存文法

文法を大きくわけると二種類ある

句構造文法
 CFG
 TAG
 CCG
 HPSG
 LFG

依存文法 (Hays 1964; Robinson 1970)
 特別な句構造を持たず、単語間の依存関係を記述す
る形態の文法
29
句構造と依存構造
S
NP
私は
句構造
VP
PP
机の上に
NP
VP
ペンを
私は
依存構造
置いた
机の
上に
ペンを
置いた
30
依存構造の文法

二つの依存可能な「係り元」「係り先」を
記述

簡単な日本語文法の例
係り元
係り先
名詞+格助詞「が」
ガ格を持つ動詞
名詞+格助詞「を」
ヲ格を持つ動詞
動詞
連用形
動詞、形容詞、形容動詞
動詞
連体形
名詞
動詞+述語接続助詞
動詞、形容詞、形容動詞
副詞
動詞、形容詞、形容動詞
連体詞
名詞
31
依存文法の長所
係り元と係り先の関係は個々に調べられる
ため、省略や語順に関係なく解析可能
 格解析も同時解析可能
 句構造解析でも語彙化の流れがあるが、依
存文法はもともと単語を中心に考えられた
文法である

32
機械学習による解析

単語と単語の依存構造を機械学習で判定





陽に文法をもたない
動的に生成されるデータ構造に強く依存しないた
めコンピュータ上で処理しやすい⇔句構造解析
エントロピー最大化法による日本語係り受け解析
(内元1998)
Support Vector Machine (SVM)による日本語係り
受け解析 (工藤+2000)
ツリーバンク(正解データの集合)の出現

正解データがあれば手でルールを書くより機械学習の素
性(特徴ベクトル)を用意するほうが簡単でかつ高性能
33
ツリーバンクの例

プラハ依存構造ツリーバンク
34
Projective or Non-projective

非交差条件
太郎は
Good!
花子が 使った
ペンを
盗んだ
Bad!
花子が
太郎は
使った
ペンを
盗んだ
35
Projective or Non-projective

非交差条件の例外
これが
僕は
正しいと
思う
36
Projective or Non-projective

Projective dependency parsing: 係り受けが交差
することを想定しない解析


句構造解析と同様の動的計画法が使えるため効率的
c.f. Eisner Algorithm O(n3) (Eisner 1996)
Non-Projective dependency parsing: 係り受け
が交差することを想定した解析



単語対の全ての組み合わせに対し解析するため非効
率的(だと思われていた)
単語=頂点、係り受けの重み=枝の重みとみなすと、
maximum spanning treeの問題に帰着可
(McDonald+2005)
Chu-Liu-Edmond algorithm O(n2) (Chu and Liu
1965; Edmond 1967; Tarjan 1977)
37
まとめ
TAG
 依存文法


資料
http://aiweb.cs.ehime-u.ac.jp/~ninomiya/ai2/
38
ダウンロード

TAG