パワーポイント2007(推奨)

数理言語情報論第11回
2009年12月16日
数理言語情報学研究室講師二宮崇
1
今日の講義の予定




単一化アルゴリズム
HPSGのフルパージング
生成モデルと識別モデル
教科書



北研二(著) 辻井潤一(編) 言語と計算4 確率的言語モ
デル東大出版会
C. D. Manning & Hinrich Schütze
“FOUNDATIONS OF STATISTICAL NATURAL
LANGUAGE PROCESSING” MIT Press, 1999
Christopher M. Bishop “PATTERN
RECOGNITION AND MACHINE LEARNING”
Springer, 2006
2
型付素性構造の単一化アルゴリ
ズム

データ構造
型テーブル
 ヒープ
 ポインタ


アルゴリズム

Unify(F, G)
 破壊的単一化アルゴリズム
G: ポインタ
 出力: F, Gのポインタは同じデータを指し、その
データがF, Gの単一化の結果
 F,
3
型テーブル：型定義

（復習）型階層
円筒
円
丸
verb
正方形
長方形
菱形
四角
plus
特殊
adj
perp
subst
func
minus
head
bool
図形
⊥
(ボトム)
一般
4
型テーブル:型の包摂関係
t13
t8
t6
t5
t3
t4より特殊な型
t4 ⊏ t5
t4 ⊏ t6
t4 ⊏ t7
t4 ⊏ t8
t4 ⊏ t12
t4 ⊏ t13
特殊
t12
t7
t4
t2
t9より特殊な型
t9 ⊏ t10
t9 ⊏ t11
t9 ⊏ t12
t9 ⊏ t13
t10
t11
t9
t1
⊥
(ボトム)
t4 ⊔ t9=t12
型単一化の結果: 共
通の特殊な型のうち
最も一般な型
一般
5
型テーブル


型定義は単一化実行前に与えられていると仮定
静的に全ての型の組み合わせに対する単一化を計算


t ⊔u=u ⊔tなので、表の半分だけ計算すれば良い
スパースになるケースが多いのでハッシュで実装することが多い
⊥
t1
t2
t3
t4
t5
t6
t7
t8
t9
t10
t11
t12
t13
⊥
t1
t2
t3
t4
t5
t6
t7
t8
t9
t10
t11
t12
t13
⊥
t1
t2
t3
t4
t5
t6
t7
t8
t9
t10
t11
t12
t13
t1
t2
t3
t4
t5
t6
t7
t8
t12
t12
-
t12
t13
t2
t3
t6
t6
t6
-
-
-
-
-
-
-
t3
t6
t6
t6
-
-
-
-
-
-
-
t4
t5
t6
t7
t8
t12
t12
-
t12
t13
t5
t6
t8
t8
t13
t13
-
t13
t13
t6
-
-
-
-
-
-
-
t7
t8
t12
t12
-
t12
t13
t8
t13
t13
-
t13
t13
t9
t10
t11
t12
t13
t10
-
t12
t13
t11
-
-
t12
t13
t13
6
ヒープとセル

ヒープ


セルの列
セル

タグとデータ
のペア
アドレス
タグ
データ
0x00000000
VAR
a
0x00000001
STR
e
0x00000002
VAR
a
0x00000003
INT
15
0x00000004
FLO
0.335
0x00000005
STR
f
0x00000006
PTR
0x00000003
0x00000007
STG
“Taro”
...
...
...
7
ヒープとヒープポインタ

ヒープには使用領域と
未使用領域の二つがあ
る


0x00000000
0x00000001
.....
used
新しいデータは未使用
領域に追加される
ヒープポインタ

未使用領域の先頭アド
レス（＝使用領域の末
尾アドレス＋１）を格
納した変数
ヒープポインタ
unused
0xffffffff
8
タグの種類

重要なタグ
VAR: 枝をまだ持っていないノード。データ部
は整数の型ID。
 STR: 枝を持つノード。データ部は整数の型ID。
 PTR: ポインタ。データ部はアドレス。


特殊なデータのためのタグ
INT: 整数(integer)
 FLO: 浮動小数
 STG: 文字列

9
ヒープ上の素性構造
F
d
G:
F:
d
F:
G:
F
アドレス
タグ
データ
0x00010000
STR
d
0x00010001
VAR
e
0x00010002
VAR
a
0x00010003
STR
d
0x00010004
PTR
0x00010000
0x00010005
PTR
0x00010000
...
...
0x00010006
e
a
0x00010007
...
10
VAR



もしかしたら今後、
枝(素性)を持つよ
うになるかもしれ
ないけど今は持っ
ていないノード
データ部にはノー
ドの型のID (整数
値)を格納
枝を持つように
なったら、ポイン
タで上書きして、
ポインタの先に新
しい枝つきのデー
タを作成
HP
アドレス
タグ
データ
....
...
...
0x00010001
VAR
e
...
...
...
アドレス
タグ
データ
....
...
...
0x00010001
PTR
0x0020002e
...
...
...
0x0020002e
STR
e
0x0020002f
VAR
g
11
STR

枝(素性)つきノード



後続するアドレスのセルにはそのノードが持つ素性の値が入る
素性の順番はSTRタグを持ったノードの型と素性によって静的
に決定しておく Index(f, t)=1, 2, 3,...,nt


データ部にはノードの型のID(整数)
例えば、素性にIDをつけて、型tがもつ素性集合のうちIDの昇順
に並べる、など。型tが素性fを持たない時は0を返すようにすると
便利
新しくSTRタグのデータをつくるときは、その素性値にはデ
フォルト値として、appropriateな型を格納する Approp(f, t)
アドレス
タグ
データ
....
...
...
0x00010001
STR
e
0x00010002
VAR
g
0x00010003
PTR
0x0001023f
....
...
...
12
PTR


実データを指すポインタ
ポインタはチェーンになっていても構わない

手続き型言語でよくあるポインタのポインタといった複雑
な構造ではないので注意！
矢印が指すアドレ
スの素性構造は全
部同じ
(0x00010007の
データ)
アドレス
タグ
データ
....
...
...
0x00010001
PTR
0x00010005
0x00010002
STR
f
0x00010003
VAR
g
0x00010004
PTR
0x00010006
0x00010005
PTR
0x00010004
0x00010006
PTR
0x00010007
0x00010007
VAR
h
....
...
...
13
Deref

ポインタを辿って実データのアドレスを得
る操作
Deref( p )
## アドレス p
while(Heap[p].tag = PTR ) ## タグがPTR
p := Heap[p].data
## pをアドレスpのセルのデー
タで置き換える
return p
0x00010001
PTR
0x00010005
Deref(0x00010001)
= 0x00010007
0x00010002
STR
f
0x00010003
VAR
g
0x00010004
PTR
0x00010006
0x00010005
PTR
0x00010004
0x00010006
PTR
0x00010007
0x00010007
VAR
h
14
ポインタに対する考え方

同じノードを指すポインタの集合
CAT:
CAT:
local
local
foo
HOGE:
cat
nom
CASE:
noun
VALENCE:
valence
COMPS:
SPR:
nil
nil
15
ポインタに対する考え方

どこから指されているのか気にせず実デー
タの書き換えを簡単に行える
goo
LOCAL:
goo
今ここを書
き変えたい
LOCAL:
local
CAT:
CAT:
local
DEE:
dee
cat
cat
16
単一化アルゴリズム(1/8)

Unify(p, q): アドレス pとアドレス qの素性構造を単一化
p
tp
F:
G:
q
tq
G:
H:
I:
H:
もしp=qなら終了
17
単一化アルゴリズム(2/8)

Unify(p, q): アドレス pとアドレス qの素性構造を単一化
r
p
tp
tr
F:
G:
G:
H:
q
tq
I:
H:
新しいノードを生成
ノードの型trはtr = tp ⊔ tq
18
単一化アルゴリズム(3/8)
Unify(p, q): アドレス pとアドレス qの素性構造を単一化

r
p
F:
q
tr
G:
G:
H:
I:
H:
pとqをrを指すポインタに書換
19
単一化アルゴリズム(4/8)

Unify(p, q): アドレス pとアドレス qの素性構造を単一化
r
p
F:
q
tr
G:
H:
G:
F:
G:
H: I:
J:
I:
H:
新しいノードの型trが持つ素性に対する
枝を作る
20
単一化アルゴリズム(5/8)

Unify(p, q): アドレス pとアドレス qの素性構造を単一化
r
p
F:
q
tr
G:
H:
G:
F:
G:
H: I:
J:
I:
H:
共通でない素性には単純にポインタをは
る
21
単一化アルゴリズム(6/8)

Unify(p, q): アドレス pとアドレス qの素性構造を単一化
r
p
q
tr
G:
H:
G:
F:
G:
H: I:
J:
H:
tpにもtqにもない新しい素性J:には
Appropriateな型(trと素性J:に対して定義
されるデフォルトの型）のノードを生成
22
単一化アルゴリズム(7/8)

Unify(p, q): アドレス pとアドレス qの素性構造を単一化
r
p
q
tr
G:
H:
G:
F:
G:
H: I:
J:
H:
共通の素性G: H: に対しては、とりあえず、
pかqのどちらかの素性G:H:が指すノードに
対し、ポインタを貼る
23
単一化アルゴリズム(8/8)

Unify(p, q): アドレス pとアドレス qの素性構造を単一化
r
p
q
tr
p’’
p’
q’
G:
H:
G:
F:
G:
H: I:
J:
H:
Unify(p’, q’)とUnify(p’’, q’’)を再帰呼び
出し
q’’
24
単一化アルゴリズム: まとめ
Unify(p, q) # pとqはヒープ上のアドレス
p := Deref(p); q := Deref(q);
if( p = q ) return true;
r := HP; HP := HP + 1;
tagp := Heap[p].tag; tp := Heap[p].data;
tagq: = Heap[q].tag; tq := Heap[q].data;
tr :=Type-Unify(tp, tq); if (tr is not defined ) return false;
Heap[p].tag := PTR; Heap[p].data := r;
Heap[q].tag := PTR; Heap[q].data := r;
Heap[r].tag := STR; Heap[r].data := tr;
HP := HP + |Features(tr)|;
foreach f ∈ Features(tr)
if( f ∈ Features(tp) ∧ tagp = STR )
Heap[r + index(f, tr)].tag := PTR; Heap[r + index(f, tr)].data := p + index(f, tp)
else if( f ∈ Features(tq) ∧ tagq = STR )
Heap[r + index(f, tr)].tag := PTR; Heap[r + index(f, tr)].data := q + index(f, tq)
else
Heap[r + index(f, tr)].tag := VAR; Heap[r + index(f, tr)].data := Approp(f, tr)
foreach f ∈ (Features(tp) ∩ Features(tq))
if( ￢Unify(p + index(f, tp), q + index(f, tq)) ) return false;
return true;
25
単一化アルゴリズムの特徴


素性構造にサイクルがあってもok
必ず終了する

Unifyが再帰呼び出しされる度に実体ノード（ポイン
タ以外のノード）が一つずつ減る


appropriateな型のノードが生成される時のみVARノードが増
えるが、このノードを無視すれば、各ステップでノードが一
つずつ減る
VARノードを無視しても良い大雑把な説明


アルゴリズムを改良して、タグの組み合わせで処理を分類すると、
各ステップでSTRノードの数が増えないようにすることができる
 VARとVAR→VAR (STRノード数は減らない)
 VARとSTR→STR (STRノード数は減らない)
 STRとSTR→STR( STRノード数がひとつ減る)
各STRノードが持つことができるVARノードは全ての型に対する最
大素性数で抑えられるため、実ノード数をSTRノード数×最大素性
数と考えれば、この数は各ステップごとに一つずつ減るので、必ず
終了する
26
単一化の例 (1)
F:
G:
F: a
F: c
H: a
F:
⊔
G:
F: a
G: b
I: a
G: J: b
F:
=
F: a
G: b
F: c
G:
G:
I: a
J: b
H: a
異なる型の場合は、型単一化を行う。型単
一化に失敗すると、全体の単一化も失敗
27
単一化の例 (1)
Unify(p, q)

q
p
G:
F:
F:
G:
G:
F:
a
F:
c
F:
H:
a
G:
J:
I:
a
b
a
b
28
単一化の例 (1)
Unify(p, q)

p
q
G:
F:
F:
G:
G:
F:
a
F:
c
F:
H:
a
G:
J:
I:
a
b
a
b
29
単一化の例 (1)
Unify(p, q)

p
q
F:
G:
G:
F:
a
F:
c
F:
H:
a
G:
J:
I:
a
b
a
b
30
単一化の例 (1)

Unify(p, q)
q
p
G:
F:
G:
F:
G:
F:
H:
a
a
b
c
I:
a
J:
b
31
単一化の例 (2)
F:
G:
F: a
F: c
H: a
⊔
F:
G:
1
1
F: a
G: b
=
F:
G:
1
F: d
G: b
H:a
1
(a⊔c=dとする)
32
単一化の例 (2)
Unify(p, q)

q
p
F:
G:
F:
G:
F:
a
F:
c
H:
a
F:
G:
a
b
33
単一化の例 (2)
Unify(p, q)

q
p
F:
G:
F:
G:
F:
a
F:
c
H:
a
F:
G:
a
b
34
単一化の例 (2)
Unify(p, q)

q
p
G:
F:
G:
F:
a
F:
c
H:
a
F:
G:
a
b
35
単一化の例 (2)

Unify(p, q)
q
p
F:
G:
G:
G:
F:
F:
H:
a
c
a
b
36
単一化の例 (2)

Unify(p, q)
q
p
F:
G:
G:
F:
F:
H:
a
c
a
b
37
単一化の例 (2)

Unify(p, q)
q
p
F:
G:
F:
G:
F:
a
c
H:
b
a
38
単一化の例 (2)

Unify(p, q)
q
p
F:
G:
F:
H:
G:
d
b
a
39
HPSGのスキーマの単一化
dtrs:
left-dtr:
synsem:
right-dtr:
スキーマ
（＝句構造規則）
40
HPSGのスキーマの単一化
ここが新しい親
になる
synsem:
スキーマ
（＝句構造規則）
dtrs:
left-dtr:
right-dtr:
right daughter
left daughter
単一化
単一化
41
Reduce Sign
ここが新しい親
になる
synsem:
dtrs:
left-dtr:
right-dtr:
子供の部分はいらないので切ってしまう
42
Reduce Sign

子供(daughters)の部分をカット
子供がまるまる残っていると、構文木のルー
トノードに全ての展開された構文木集合が格
納されてしまう（簡単に数百億以上の構文木
になってしまう）
 そこで、子供の部分をカットしてCKYチャー
トに格納してやればよい

43
CKYアルゴリズム

CFGのCKYアルゴリズムとの違い




非終端記号のかわりに素性構造が格納される
子供をカットする操作 (reduce sign)が必要
単一化は破壊的操作なので、実行前にコピーをし
て元の素性構造を残しておく
ルール規則の適用
CFG: 非終端記号X, Yに対し、G(X, Y)は親の非終端記号
集合を返す
 HPSG: 素性構造X, Yに対し、G(X, Y)は親の素性構造集合
を返す


ファクタリング
CFG: 等価な非終端記号
 HPSG: 等価な素性構造 (X = Y iff X ⊑Y and X ⊒ Y)


デコーディングの時も同様
⊑⊏⊒⊔⊐
44
CKY法 for HPSG
for j = 1 to n
Sj-1,j := L(wj) ## Lは単語wに対する素性構造の集合を返す関数
for l = 2 to n
for i = 0 to n – l
j := i + l;
for k = i+1 to j - 1
forall X∈Si,k
forall Y∈Sk,j
forall b ∈ BS
# BSはバイナリースキーマの集合
X’ := copy(X); Y’ := copy(Y); b’ := copy(b)
Si,j := Si,j ∪ Reduce(b’(X’, Y’))
Si,j := Si,j ∪ U(Si,j) ## Uはユーナリールールの適用手続き
45
等価性チェックとコピー

構造共有があるため素性構造の等価性
チェックやコピーはそんなに簡単ではない

破壊的でない操作
 すでに辿ったセルのアドレスをハッシュにいれてお
いて構造共有をチェック

破壊的操作＋バックトラック
 すでに辿ったセル上にマーキングタグと対応する相
手側のアドレスを書き込む
 変更履歴をたどることによって元のデータに戻す
（バックトラック）
46
不完全ながら高速な等価性
チェック

セルの列とセルの列を単純なforループで簡
単にチェック
コピーする際に、ポインタの作り方や部分構
造の作り方を工夫すれば、等価な素性構造は
まったく同じセルの列になる
 ただし、VARタグを展開していない場合と
VARタグが展開されてSTRになっている場合
では正しいチェックができないので注意

47
HPSGの確率モデル？
PCFGは各書換
規則に対応す
るパラメータ
を用意すれば
良かった
 HPSGでは？？
S
構文木 t

VP1
SUBJ
NP
OBJ1
が
香織
NP
S
SUBJ
NP
が
V
を
読んだ
NP
V
電子メール
送った
恵
P(t) = θS → SUBJ VP1 × θSUBJ → NP が × θNP → 香織 ×
θVP1 → OBJ1 V × θOBJ1 → NP を × θNP → S NP ×
θS → SUBJ V × θSUBJ → NP が × θNP → 恵×
θV → 送った× θNP → 電子メール × θV → 読んだ
48
PHON: <he, gives, her, a present>
SUBJ: <>
COMPS: <>
SPR: <>
VAL:
PHON: <gives, her, a present>
VAL:
SUBJ: < 1 >
COMPS: <>
SPR:<>
PHON: <gives, her>
VAL:
SUBJ:< 1 >
COMPS:< 3 >
SPR:<>
PHON: <gives>
1
NP[nom][3rd, sing]
he
VAL:
SUBJ: < 1 >
COMPS: < 2 , 3 >
SPR: <>
gives
2 NP[acc]
her
3
NP[acc]
a present
生成モデルから識別モデルへ

生成モデル

CFGによる生成のステップ（書換規則の適用
A → B C）の確率をp(B C| A)とする
C |A)=θA→B Cとおき、これらパラメータの集合
をθとおく
 p(B
CFGによる生成の過程の確率を、独立な事象
の(条件付き)確率の積とする
 全ての文sと構文木tに対する同時確率p(s, t)を
計算できる

50
生成モデルの改良の先に

構文木の分岐の外の情報を条件部に導入

マルコフ文法
 M→L...H...Rの確率
p( Ln1 (ln1 ),..., L1 (l1 ), H (h), R1 (r1 ),..., Rm1 (rm1 ) | M , h)

素性（特徴）という考え方
条件部をどんどんリッチにして線形補間をとれ
ばよいのでは？→構文木のノードxの確率
p(x)=p(x|x周辺の状況)
51
生成モデルの問題点

生成モデルの問題点

独立性の仮定
PCFGでは、各構文木ノードは独立な(条件付き）試行に
より生成されていると仮定している
 例えば、(S (NP John) (VP eats (NP apples)))という構文
木は、以下の独立な（条件付き）事象に分解されている






SからNP VPを生成
NPからJohnを生成
VPからeats NPを生成
NPからapplesを生成
結果、上記のNPの文脈(S→NP VP)から導出されたNPか
(VP→eats NP)から導出されたNPかわからなくなってい
る→主語のNPなのか目的語のNPなのかわからない。
52
生成モデルの問題点

生成モデル
~
t  arg max p(t | s; )  arg max p( s, t; )
t

t
しかし、
p( s, t ; )  p(t | s; ) p( s; )
であるからp (s;θ) が計算できてしまう分、冗
長なモデルになっている。間接的に分類問題
を解いている。
 独立性を仮定した事象に分解しないと同時確
率を計算することができない
53
識別モデル

識別モデル
直接
~
t  arg max p(t | s; )
t
を解く
 独立な事象を仮定しない
 「条件部の確率」をモデルにいれない
54
生成モデルと識別モデル
(イメージ)
生成モデル
識別モデル
GOOD
BAD
生成モデルと識別モデル
（イメージ２）

生成モデル
絵を描いて全体像の比較

識別モデル
それぞれの特徴を比較




鼻の位置
耳の形
体の大きさ
舌の表面
56
識別するための訓練

教師付学習

良い例と悪い例を与えて、どこに注目すれば
より良く識別出来るのか学習
good examples
bad examples
57
識別モデル
p (t | s )
素性ベクトル
(特徴ベクトル)
(0,0,1,0)
t1
s = “A blue eye girl with white hair and skin walked”
(1,0,1,0)
(1,1,1,0)
t2
t3
(0,0,1,1)
t4
(1,0,0,0)
…
tn
文法Gによりsから導出出来る全ての構文木集合
p(t3|s) はt1,t2,t3,..,tnからt3を選択する確率
生成モデルと識別モデル
生成モデル
識別モデル
p( x, y2 )
p( x, y1 )
1.0
p ( y2 | x )
p( y1 | x)
どちらが優秀なのか？
Tom Minka (2005) Discriminative models, not
discriminative training, MSR-TR-2005-144, 1 p.
xを入力(文)、yを出力(構文木)としたときのパラメー
タ推定
 生成モデル
p ( x, y ;  )  p ( x | y;  ) p ( y;  )

識別モデル
p ( y | x; )

θ = θ’
一般モデル
p( x, y; ,  )  p( y | x; ) p( x; )
60
まとめ
単一化アルゴリズム
 HPSGフルパージング
 生成モデルと識別モデル
 次回は、1/13(水) 16:30～ロジスティック回
帰と確率的HPSGとCRF
 講義資料


http://www.r.dl.itc.u-tokyo.ac.jp/~ninomi/mistH21w/cl/
61
レポート課題

課題（いずれかのうち一つ）

言語学、パージングもしくは機械学習に関する論文を一つ以上
読んで内容をまとめ、考察を加えよ。ただし、論文は次の国際
会議から選ぶこととする。





授業内容でよくわからなかった箇所を教科書やスライドを頼り
に例題を作りつつ内容をまとめ、考察せよ




NLP系の国際会議: ACL, NAACL, EACL, COLING, EMNLP
機械学習系の国際会議: ICML, NIPS, COLT, UAI, AIStats
人工知能系の国際会議: IJCAI, AAAI
データマイニング系の国際会議: KDD, SDM, ICDM
例: CCGやHPSGで簡単な文法を紙の上に書き、紙の上で構文解析
例: 正規分布の混合分布に対するEMの導出
例: エントロピー最大化によるパラメータ推定とパラメトリック形式
の最尤法によるパラメータ推定が一致することを確認
授業内容に関連する内容を発展させた内容を調査もしくは考察


例: 最大エントロピー法のスムージングのための正規分布の事前分布
例: 準ニュートン法について調べる
62
レポート課題
A4で4ページ以上
 日本語か英語
 締切: 2010年2月17日(水曜)
 提出先



工学部6号館 1F 計数教務室
レポートには所属、学籍番号、名前を記入
63

Download Report