ml-study-ninomi6

1
機械学習勉強会 2009年9月24日



P. Domingos and M. Richardson, Chap. 12
Markov Logic: A Unifying Framework for
Statistical Relational Learning in Introduction to
Statistical Relatinal Learning, eds, L. Getoor
and B. Taskar, MIT Press, 2007
H. Poon and P. Domingos (2009) Unsupervised
Semantic Parsing, in Proc. of EMNLP 2009 (best
paper award)
H. Poon, C. Cherry and K. Toutanova (2009)
Unsupervised Morphological Segmentation
with Log-Linear Models, in Proc. of NAACL/HLT
2009 (best paper award, IBM Best Student
Paper)
2

論理式をMarkov Network(=Markov
Random Field)において定式化した枠組
3

一階知識ベース (KB)
› 一階述語論理の論理式の集合
› 論理式は次の4つの構成素から成る
 定数 (constant) [Anna, Bob, Chrisなどのオブジェクト]
 変数 (variable) [x, y, zなど]
 関数 (function) [オブジェクトのタプルからオブジェクトを返す
関数。MotherOfなど。ここでは使わないことにする]
 述語 (predicate) [オブジェクトの関係や属性を表す。Friends,
Smokeなど。]
› 論理式F1, F2に対し次も論理式
 ￢F1 (negation)
 ∀F1 (universal quantification)
 ∃F1 (existential quantification)
 F1 ∧ F2 (conjunction)
 F1 ∨ F2 (disjunction)
 F1 ⇒ F2 (implication)
 F1 ⇔ F2 (equivalence)
4

項 (term): 定数、関数、変数からなる構造体
› Anna, Bob, MotherOf(Anna)など
› 変数付のデータ構造と考えれば良い
› 定数の集合が有限で、関数を使わなければ、項の集合は有限

アトム(atomic formula, or atom)
› 項が適用されている単一の述語から成る論理式をアトムと呼ぶ
 Friends(x, MotherOf(Anna))

グラウンド(ground)
› 基底項 (ground term):変数を含まない項
› ground atom/ground predicate: 全ての項が変数を含まないアトム

可能世界/エルブラン解釈
› 全ての可能なground predicateに対する真偽値の割り当て

充足
› ある論理式Fが充足可能⇔Fが真となる世界が一つ以上ある
5
English
First-order logic
Clausal form
Friends of friends are
friends.
∀x∀y∀z
Fr(x, y)∧Fr(y, z) ⇒ Fr(x,z)
￢Fr(x,y) ∨ ￢Fr(y,z) ∨
Fr(x,z)
Friendless people smoke.
∀x
(￢(∃y Fr(x, y))⇒ Sm(x))
Fr(x, g(x)) ∨ Sm(x)
Smoking causes cancer.
∀x Sm(x) ⇒ Ca(x)
￢Sm(x)∨ Ca(x)
If two people are friends,
either both smoke or
neither does.
∀x∀y
Fr(x,y)⇒(Sm(x)⇔Sm(y))
￢Fr(x,y)∨Sm(x)∨￢Sm(y),
￢Fr(x,y)∨￢Sm(x)∨Sm(y)
6

例
›
›
›
定数集合 = {Anna, Bob}
述語集合={Sm, Fr, Ca}
論理式
›
Fr(Anna, Bob)が真となる世界は？
 ￢Sm(x)∨ Ca(x)
 ￢Fr(x,y)∨Sm(x)∨￢Sm(y)
 ￢Fr(x,y)∨￢Sm(x)∨Sm(y)
ground predicate
値域
(真=1, 偽=0)
世界1～8
世界9～40
Sm(Anna)
1/0
1
0
Sm(Bob)
1/0
1
0
Ca(Anna)
1/0
1
1/0
Ca(Bob)
1/0
1
1/0
Fr(Anna, Anna)
1/0
1/0
1/0
Fr(Anna, Bob)
1/0
1
1
Fr(Bob, Anna)
1/0
1/0
1/0
Fr(Bob, Bob)
1/0
1/0
1/0
7
各論理式Fiに重みwiを付与
 この重み付き知識ベースをMLNと呼ぶ

English
First-order logic
Clausal form
重み
Friends of
friends are
friends.
∀x∀y∀z
Fr(x, y)∧Fr(y, z) ⇒ Fr(x,z)
￢Fr(x,y) ∨ ￢Fr(y,z) ∨ Fr(x,z)
0.7
∀x
Friendless
people smoke. (￢(∃y Fr(x, y))⇒ Sm(x))
Fr(x, g(x)) ∨ Sm(x)
2.3
∀x Sm(x) ⇒ Ca(x)
Smoking
causes cancer.
￢Sm(x)∨ Ca(x)
1.5
If two people
are friends,
either both
smoke or
neither does.
￢Fr(x,y)∨Sm(x)∨￢Sm(y),
￢Fr(x,y)∨￢Sm(x)∨Sm(y)
1.1
1.1
∀x∀y
Fr(x,y)⇒(Sm(x)⇔Sm(y))
8
Fr(Anna, Anna)
MLN
Clausal form
重み
￢Sm(x)∨ Ca(x)
1.5
￢Fr(x,y)∨Sm(x)∨￢Sm(y),
￢Fr(x,y)∨￢Sm(x)∨Sm(y)
1.1
1.1
Fr(Bob, Bob)
Fr(Anna, Bob)
Sm(Anna)
Ca(Anna)
Sm(Bob)
Ca(Bob)
Fr(Bob, Anna)
ground predicate 値域
(真=1, 偽=0)
Sm(Anna)
1/0
Sm(Bob)
1/0
Ca(Anna)
1/0
Ca(Bob)
1/0
Fr(Anna, Anna)
1/0
Fr(Anna, Bob)
1/0
Fr(Bob, Anna)
1/0
Fr(Bob, Bob)
91/0


MLN ⇔ 素性関数
Clausal form
重み
￢Sm(x)∨ Ca(x)
1.5
￢Fr(x,y)∨Sm(x)∨￢Sm(y),
￢Fr(x,y)∨￢Sm(x)∨Sm(y)
1.1
1.1
ground predicate ⇔ 入力ベクトルx=<x1, x2, x3, …, x8>
ground predicate
値域(真=1, 偽=0)
Sm(Anna)
1/0
⇔ x1
Sm(Bob)
1/0
Ca(Anna)
1/0
⇔ x2
⇔ x3
Ca(Bob)
1/0
Fr(Anna, Anna)
1/0
Fr(Anna, Bob)
1/0
Fr(Bob, Anna)
1/0
⇔ x4
⇔ x5
⇔ x6
⇔ x7
Fr(Bob, Bob)
1/0
⇔ x8
10

世界x(ground predicateに対して具体的に0/1を割り当て
たベクトル)に対する確率
P( X  x) 
1

 1
exp   wi ni ( x)    i ( x{i} ) ni ( x )
Z
 i
 Z i
ni(x) はxにおいてFiが真となる関係の個数
x{i}はFiに出現するアトムの真偽の状態
φi(x{i}) = exp(wi)
これで、例えば、AnndとBobの喫煙習慣によって、彼らが
友達であるかどうかの確率が求まる
11



MLN: ∀x R(x) ⇒ S(x) with weight w
定数集合: C={A}
可能世界とその確率
›
›
›
›
￢R(A), ￢S(A)
￢R(A), S(A)
R(A), ￢S(A)
R(A), S(A)
ew
P({R( A), S ( A)})  w
3e  1
ew
P({R( A), S ( A)})  w
3e  1
1
P({R( A), S ( A)})  w
3e  1
ew
P({R( A), S ( A)})  w
3e  1
P({R( A), S ( A)})
1
P( S ( A) | R( A)) 

P({R( A), S ( A)})  P({R( A), S ( A)}) 1  e  w
w→∞で、P→1
に注意
(wを大きくする
とハードな制約
に近づく）
12
P( F1 | F2 , L, C )  P( F1 | F2 , M )
P( F1  F2 | M L ,C )

P( F2 | M L ,C )
x F1  F2 P( X  x | M L,C )

x P( X  x | M L,C )
F2
 F はFiを満たす全ての世界
i
ものすごい計算量になる
・MCMCで計算
・実データ上でtrueのものは計算しない
・条件部を満たさない世界は計算をしない
・著者は2フェーズの効率的アルゴリズムを提案している
13


ground atomのデータベースがあると仮定
closed-world assumption
› データベースの中に無いground atomは全てfalseとする

可能なground atomがn個あるとすると、データベース
は一つのベクトルx=(x1,…,xn)と表現できる
› xj = 1 (データベースにxjが出現)
› xj = 0 (それ以外)

xの中にFiが満たされているアトムの出現回数をni(x)とす
る

log Pw ( X  x)  ni ( x)   Pw ( X  x' )ni ( x' )
wi
x'
・Monte Carlo maximum likelihood estimator (MC-MLE)
・マルコフブランケットによる近似→L-BFGS
14
15
H. Poon & P. Domingos
in Proc. of EMNLP-2009
スライドの大部分は下記URLからとってきています。
http://www.cs.washington.edu/homes/hoifung/talks/usp09.ppt
Natural language text  First-order logic
 First-order logic: Formal and detailed
meaning representation
 E.g.,

Microsoft buys Powerset.
BUY(MICROSOFT,POWERSET)
16
Manually construct a grammar
 Challenge: Same meaning can be
expressed in many different ways

Microsoft buys Powerset
Microsoft acquires semantic search engine Powerset
Powerset is acquired by Microsoft Corporation
The Redmond software giant buys Powerset
Microsoft’s purchase of Powerset, …
……

Manual encoding of variations?→NO!
17
buys

入力
nsubj
› 依存構造解析結果

Powerset
出力
› 意味構造

Microsoft
dobj
CBUY(n1)∧ABUYER(n1,n2)∧ABOUGHT(n1,n3)∧
CMICROSOFT(n2)∧ CPOWERSET(n3)
QLF の主要形式(動詞や述語に相当)のクラス
タリングと項形式(目的語や主語など)のクラ
スタリングをMLNの枠組みで学習
18
buys
nsubj
Microsoft
dobj
Powerset
Convert each node into an unary atom
19
buys(n1)
nsubj
Microsoft(n2)
dobj
Powerset(n3)
n1, n2, n3 are Skolem constants
20
buys(n1)
nsubj
Microsoft(n2)
dobj
Powerset(n3)
Convert each edge into a binary atom
21
buys(n1)
nsubj(n1,n2)
Microsoft(n2)
dobj(n1,n3)
Powerset(n3)
Convert each edge into a binary atom
22
buys(n1)
nsubj(n1,n2)
Microsoft(n2)
dobj(n1,n3)
Powerset(n3)
Partition QLF into subformulas
23
buys(n1)
nsubj(n1,n2)
Microsoft(n2)
dobj(n1,n3)
Powerset(n3)
Subformula  Lambda form:
Replace Skolem constant not in unary atom
with a unique lambda variable
24
buys(n1)
λx2.nsubj(n1,x2)
Microsoft(n2)
λx3.dobj(n1,x3)
Powerset(n3)
Subformula  Lambda form:
Replace Skolem constant not in unary atom
with a unique lambda variable
25
Core form
buys(n1)
Argument form
λx2.nsubj(n1,x2)
Microsoft(n2)
Argument form
λx3.dobj(n1,x3)
Powerset(n3)
Follow Davidsonian Semantics
Core form: No lambda variable
Argument form: One lambda variable
26
これをpartと呼ん
でいる
buys(n1)
λx2.nsubj(n1,x2) λx3.dobj(n1,x3)
 CBUYS
Microsoft(n2)
 CMICROSOFT
Powerset(n3)
 CPOWERSET
Assign subformula to lambda-form cluster
27
buys(n1)
CBUYS
0.1
acquires(n1) 0.2
……
One formula in MLN
Learn weights for each pair of
cluster and core form
Distribution over core forms
28
0.1
ABUYER
acquires(n1) 0.2
ABOUGHT
buys(n1)
CBUYS
……
APRICE
……
May contain variable number of
argument types
29
λx2.nsubj(n1,x2) 0.5
λx2.agent(n1,x2) 0.4
CMICROSOFT 0.2
CGOOGLE
0.1
None 0.1
One 0.8
……
……
……
Three MLN formulas
Distributions over
argument forms, clusters, and number
30
p∈+c∧Form(p, +f)
 ArgType(p, i, +a)∧ArgForm(p, i, +f)
 Arg(p, i, p’)∧ArgType(p, i, +a)∧p’∈+c’
 Number(p, +a, +n)

ただし、+のついた変数には実体が入っていて、異なる実体毎に重みが
ついている（つまり、論理式は４つではなくて、ものすごくたくさんあ
る）
31


クラスターとMLNの重みが学習済みとする
次のアルゴリズムで、依存構造→抽象化された意味構造を
出力
›
›
›
›
1. 依存構造→QLF(変換)
2. QLF→parts(分解)
3. 各partを最大確率のクラスターに割り当てる
4. 全てのparts pに対し、
 pがλ-reducibleならその結果を最大確率のクラスターに割り当
てる
 λ-reducible: pのλ式をreduceした結果がクラスターの要素と
して存在している
› 5. その中で最も確率を大きくする割り当てを選択
› 6. 確率が収束するまで4.5.を繰り返す。

技術: unordered subtree matching (Kilpelainen1992),
inverted indexex
32
Observed: Q (QLFs obtained from
dependency trees)
 Hidden: S (semantic parses)
 Maximizes log-likelihood of observing the QLFs

L(Q)  log  P(Q, S )
S
問題: クラスターの数、割り当て、λ-reduction
33

論理式のグループ化
› MLNのある論理式集合に対しては、以下の制約を課す
k
e
wi
1
i 1
 あるcに対して、p∈+c∧Form(p,+f)
 あるaに対して、残りの3つのMLN論理式

経験的相対頻度を使う
› p∈c∧Form(p,f)の重み=log(nc,f/nc)
 nc,fはp∈cとForm(p,f)を満たすpartの数
 ncはp∈cを満たすpartの数

これで、P(Q,S)はclosed formで計算できる。
34

可能な全てのsemantic parseの尤度や期待
値の計算
› MC-SAT(Poon&Domingos2006)でも厳しい
› sumをモードで近似
 そもそも各partが一つもしくは少数のクラスタに
しか属さないだろう
35

クラスターの生成
› 1. 次のオペレーションの結果をagendaに
 MERGE(C1, C2): Merge clusters C1, C2
E.g.: buys, acquires  buys, acquires
 COMPOSE(C1, C2): Create a new cluster resulting from
composing lambda forms in C1, C2
E.g.: Microsoft, Corporation  Microsoft Corporation
› 2.agendaの中で最も確率があがるオペレーションを(本当に)実
行
› 3. オペレーションの影響があるQLFについてのみ確率の計算
を再実行
› 4. 1.に戻って繰り返
36
37
GENIA dataset: 1999 Pubmed abstracts
 Questions

› Use simple questions in this paper, e.g.:
 What does anti-STAT1 inhibit?
 What regulates MIP-1 alpha?
› Sample 2000 questions according to frequency
38
Highest accuracy: 88%
300
200
100
0
KW-SYN
TextRunner
RESOLVER
DIRT
USP
39
USP resolves many nontrivial variations
 Argument forms that mean the same,
e.g.,

expression of X  X expression
X stimulates Y  Y is stimulated with X
Active vs. passive voices
 Synonymous expressions
 Etc.

40

Clusters in core forms
 investigate, examine, evaluate, analyze, study, assay 
 diminish, reduce, decrease, attenuate 
 synthesis, production, secretion, release 
 dramatically, substantially, significantly 
……

Compositions
amino acid, t cell, immune response, transcription factor,
initiation site, binding site …
41
Q: What does IL-13 enhance?
A: The 12-lipoxygenase activity of murine macrophages
Sentence:
The data presented here indicate that (1) the 12-lipoxygenase
activity of murine macrophages is upregulated in vitro and in
vivo by IL-4 and/or IL-13, (2) this upregulation requires
expression of the transcription factor STAT6, and (3) the
constitutive expression of the enzyme appears to be STAT6
independent.
42







USP: The first approach for
unsupervised semantic parsing
Based on Markov Logic
Learn target logical forms by recursively
clustering variations of same meaning
Novel form of relational clustering
Applicable to general domains
Substantially outperforms shallow methods
Markov Logic NetworkというよりはMarkov
Network(=Markov Random Fields)を使った述語、
項のクラスタリングという気がしました
43

Download Report