Document

機械学習勉強会
２０１０・６・３
松島慎
1
第一部
グラフィカルモデルとグラフ理論
2
論文のための予備知識＋α
• グラフィカルモデル
– 無向グラフ(Markov network, Markov random field,
Markov random network)
• グラフ理論
– ジャンクションツリー。ジャンクションツリーアルゴ
リズム
– 全域木。重みつき最小（大）全域木
3
有向グラフ※
• 有効閉路が存在しない
X1
X2
X3
X4
P(x) = Pp(xi|x{pa(i)})
P(x) = p(x1) p(x2|x1) p(x3|x1) p(x4| x2,x3) p(x5| x3,x4)
X5
4
5
無向グラフ
• Markov network, Markov random field
X1
X2
P(x) = PfC(xC)
独立性高い
Cは全部の極大クリークを動く
X3
X4
特殊
疎
P(x) = f12(x1,x2) f13(x1,x3) f24(x2,x4) f345(x3,x4,x5
P(x) = f123(x1,x2,x3) f234(x2, x3,x4) f345(x3,x4,x5)
X5
P(x) = f1234(x1,x2,x3,x4) f345(x3,x4,x5)
低い
一般
密
因子グラフ
f1
• Belief Propagation（信
念伝播）に有用
f2
X2
X1
f23 P(x) = f1 (x1) f2 (x2) f3 (x3) f13 (x1,x3) f12 (x1,x2)
f13
X3
f3
6
因子グラフvs無向グラフ
f1
P( x1 , x2 , x3 )   ( x1 , x2 ) ( x2 , x3 )
f2
X2
X1
X2
f23
f13
X1
X3
f3
X3
P(x1,x2,x3) = f1 (x1) f2 (x2) f3 (x3) f13 (x1,x3) f12 (x1,x2)
7
グラフィカルモデル
• 有向グラフ
– 直感的にわかりやすい
– “閉路がない”独立性
• 無向グラフ(Markov network, Markov random field)
– 複雑な変数間の独立性（依存性）がある時
• 因子グラフ
– 無向グラフより詳しい記述が可能
どれも一長一短。
8
ジャンクションツリー
• ジャンクションツリー
→クリークたちが少なくとも一つのノードしか共有し
ないようなグラフ
• ジャンクションツリーアルゴリズム
– ジャンクションツリーを構成して、一般のMarkov
Networkの一般の周辺確率を計算する方法
9
ジャンクションツリーの構成
X1,X2,X3
X1
X2
X3
X4
クリーク
セパレータ
X2,X3
X2,X3,X4
X3,X4
X5
X3,X4,X5
10
重みつき最大（小）全域木
• クラスカル法とよばれ、効率はO(E log E)
11
第二部
NIPS 2009’Outstanding Student Paper Awards
An LP View of M-MAP Problem
Menachem Fromer, Amir Globerson
12
概要
離散の台における確率モデルを扱う。
• M-best MAP問題
– 最尤点だけでなく、M番目までの尤もらしい点
（assignment）をすべて探したい
– いろいろ応用ある
• MAP問題
– 一般にはNP-Hard.
– 緩和LPを定式化、効率的に解く[Yanover+06JMLR]
• LP View of M-MAP
– MAPのLPに不等式線形制約を一つ加えると2nd
MAPのLPになる。
13
論文の貢献
• 2nd bestのLPによる定式化
– Markov networkが木の場合
• 線形不等式制約を一つ加える厳密な方法
– Markov Networkが木でない場合
• ジャンクションツリーを用いた厳密な方法
• 全域木＋cutting plane methodを用いた近似法
STRIPES
• 2nd best solver を用いたM bestの取り方※
14
15
考える確率モデル
• 確率∝１項の関数＋２項間の関数
→Markov NetworkがG=(V,E)で表わされる


p(x)  exp f θ (x)  exp  i ( xi )  ij ( xi , x j ) 
( i , j )E
 iV

例.)
 各Xiは0,1変数
 f θ (x)  1 ( x1 )   2 ( x2 )  3 ( x3 )  12 ( x1 , x2 )  13 ( x1 , x3 )
2
3
X2
X2
1
X3
1
3
X1
2
1
X3
X1
x
０
１
 1(x)
0.7
0.3
 2(x)
0.9
0.3
 3(x)
0.5
0.3
(x, x’)
(０、０)
(１、０)
(０、１)
(１、１)
 12(x, x’)
0.5
0.1
0.7
0.3
 13(x, x’)
0.6
0.6
0.7
0.3
• まずはMAPをLPとして書き下そう。
• 次に2nd bestの定式化をしよう
16
18
LP緩和の考え方
max f θ (x)  max   i ( xi )    ij ( xi , x j )
x
x
i
i, j
 max θ  v (x) 
x
X2
X3
X1
LP緩和
→連続に広げた場所
で最適化する
→M(G)だと等価な問
題になる
max
μconvv ( x )
 1 ( 0 )   1 

  

(
1
)
 1
 0
  ( 0)   
 2
 1 
 2 (1)   0 

  

(
0
)
3

 1 
 3 (1)   0 

  

(
0
,
0
)
 12
 1 
 (0,1)    0 
 12
  
12 (1,0)   0 
 (1,1)   0 
 12
  
13 (0,0)  1 

  
13 (0,1)   0 
 (1,0)   0 
 13
  

(
1
,
1
)
 13
 0
θμ
0
 
v  0  
0
 
 [[ x1  0]]



 [[ x1  1]]

vx   




 [[ x  1]][[ x  1]] 
n
 n

M(G)という概念
M(G)=


μ
|

p
(
x
)
s
.
t
.

x
,
0

p
(
x
)

1
,
p
(
x
)

m
(
x
,
x
),
m
(
x
,
x
)

m
(
x
),
m
(
x
,
x
)

m
(
x
),
m
(
x
)

1



ij i
j  ij i
j
j
j  ij i
j
i
i  i
i


xa :a  i , j
xi
xj
xi
= v(x)やと同じ型のベクトルm iaに対応する次元の値がpXi=aとなり, ijaに対
{
|
応する次元の値がpXi=a, Xj=bとなるような確率分布が存在する。
}= conv{v(x)}
m120,0
• Marginal polytope
X1
m10
m11
m20
X2
19
• まずはMAPをLPとして書き下そう。
→ max f θ (x)  max θ  μ
x
mM (G )
 

μ| p(x) s.t. x, 0  p(x)  1,  p(x)  mij ( xi , x j ),  mij ( xi , x j )  m j ( x j ),  mij ( xi , x j )  mi ( xi ),  mi ( xi )  1


xa :a  i , j
xi
xj
xi
– 木の場合、 M(G)はML (G)に制約を緩めても等価。


M L (G )  μ  0  mij ( xi , x j )  mi ( xi ),  mij ( xi , x j )  m j ( x j ),  mi ( xi )  1


jV
iV
iV
• 次に2nd bestの定式化をしよう
20
2nd Bestはどうなるか
• 制約をいじれば、2nd bestになる。
best
2nd best
m∈ML (G)
(or M (G))
m ∈ M(G,z) = {m | m ∈M(G), mに対応するp
で、pz0となるものがある}
• 木の場合、
M(G,z) = {m | m ∈M(G), I(m,z)< 0}
21
I(m,z)とは
I (μ, z )   (1  d i ) mi ( zi ) 
iV
•
•
•
•
m
( i , j )E
ij
( zi , z j )
木にはエッジがn-1個ある
I(v(z), z) = 1
z=z’ or I(v(z’),z)<0
証明はtreeのノード数に対する帰納法。
22
論文の貢献
• 2nd bestのLPによる定式化
– Markov networkが木の場合
• 線形不等式制約を一つ加える厳密な方法
– Markov Networkが木でない場合
• ジャンクションツリーを用いた厳密な方法
• 全域木＋cutting plane methodを用いた近似法
STRIPES
• 2nd best solver を用いたM bestの取り方※
23
木でない場合
• Ｇのジャンクションツリーのクリークc、セパ
レータs
I (μ, z)   (1  d c ) mc ( zc )   m s ( z s )
cC
sS
M(G,z) = {m | m ∈M(G), I(m,z)<0}
• triplet以上の変数を持たなければならない、
制約も増える。
 m (x , x , x )  m (x , x )
m123x1, x2, x3
123
1
2
3
13
1
3
x2

24
例
X1,X2,X3
X1
X2
X2,X3
X3
X4
X2,X3,X4
X3,X4
X5
X3,X4,X5
I (μ, z)  m234 ( z1 , z2 , z3 )  m23 ( z2 , z3 )  m34 ( z3 , z4 )  0
25
論文の貢献
• 2nd bestのLPによる定式化
– Markov networkが木の場合
• 線形不等式制約を一つ加える厳密な方法
– Markov Networkが木でない場合
• ジャンクションツリーを用いた厳密な方法
• 全域木＋cutting plane methodを用いた近似法
STRIPES
• 2nd best solver を用いたM bestの取り方※
26
全域木を使った方法
T  E なる全域木 T に対し
I (μ, z )   (1  d ) mi ( zi ) 
T
iV
T
i
m
( i , j )T '
ij
( zi , z j )
と定義する。そして
T

μ

M
(
G
)
|

tree
T

G
,
I
(μ, z)  0
MST
(G,z)
=
L
L
と定義する。
27
MLST (G,z)という概念
MST
L (G,z)
 {μ | μ  M (G), T , I (μ, z)  0}
T
• M(G,z) ⊂ MST
L (G,z) ⊂ ML(G)
• 大きい場所で最適化しても答えが実行可能
ならばよい
– 実際かなりの割合でintegralな解が得られる
• ML(G)から出発して、だんだんに制約をつけ
たしていく（平面切除法）
28
平面切除法
• 制約0からスタート
– 今の場合、ML(G)の制約
• 緩和問題を解く
• 満足しなければ制約を加えてもう一度
• どの制約を加えるか？
I T (μ, z )   (1  d iT ) mi ( zi ) 
• どのtreeか？
– 今のm
iV
m
( i , j )T '
が最も乱している制約
ij
( zi , z j )
29
arg max I T (μ, z )   (1  d iT ) mi ( zi ) 
T
iV
  m i ( zi ) 
iV
 m
( i , j )T
ij
m
( i , j )T
ij
( zi , z j )
( zi , z j )  m i ( zi )  m j ( z j )
• クラスカル法を使う
30

from 2nd to M-best
• 問題を分断する。
1
3
4
2
5




max μ  θ | μ  M (G ), mi1 (0)  1
max μ  θ | μ  M (G ), mi1 (1)  1

max μ  θ | μ  M (G ), m

(0)  1
max μ  θ | μ  M (G ), mi1 (1)  1, mi2 (1)  1
i1
(1)  1, mi2
31
論文の貢献
• 2nd bestのLPによる定式化
– Markov networkが木の場合
• 線形不等式制約を一つ加える厳密な方法
– Markov Networkが木でない場合
• ジャンクションツリーを用いた厳密な方法
• 全域木＋cutting plane methodを用いた近似法
STRIPES
• 2nd best solver を用いたM bestの取り方※
32
実験1
• binary grid graphs of size 10 × 10 ～1030states
– attractive (submodular) potentials, a setting in
which the pairwise LP relaxation is exact
– For each grid edge ij, we randomly chose Jij ∈ [0,
0.5], and local potentials were randomized in the
range ±0.5.
– ～２minites (19 columns(MSTs) are generated)
– vs. 13 minites by Nilson algorithm
– vs. 10 second by Loopy BF (not exact )
33
実験2
• Jij and the local potentials randomly chosen in
[−0.5, 0.5]
• all three algorithms were not able to
successfully find the top solutions.
• we added regions of triplets to tighten the LP
relaxation (for STRIPES and Nilsson) and to
perform GBP instead of BP (for BMMF).
• STRIPES and Nilsson always provably finding
the optimal solutions and BMMF mostly
finding these solutions
34
実験2
• STRIPES was the fastest of the algorithms,
taking 0.5 - 5 minutes.
– vs. 18 minutes by Nilsson
– vs. 2.5 -7 minutes by BMMF
• Up to 23 MST
35
36
実験3
• The protein side-chain prediction (SCP) problem
– corresponds to finding a MAP assignment for a
pairwise MRF
– up to 45 states per variable, mean approximate treewidth 50)
• STRIPES provably found the top 50 solutions for
369 of the 370
• 146 of the 315 problems was the Nilsson method
able to complete within five days
37
38
Conclusion
• In this work, we present a novel combinatorial
object M(G, z) and show its utility in obtaining
the M best MAP assignments.
• We provide a simple characterization of it for
tree structured graphs, and show how it can
be used for approximations in non-tree graphs.
39
• Here we studied the polytope that results
from excluding one assignment. An intriguing
question is to characterize the polytope that
excludes M assignments.
• We have found that it does not simply
correspond to adding M constraints I(μ, zi) ≤ 0
for i = 1, . . . ,M, so its geometry is apparently
more complicated than that of ˆM(G, z)
40
• Here we used LP solvers to solve for μ. Such
generic solvers could be slow for large-scale
problems. However, in recent years,
specialized algorithms have been suggested
for solving MAP-LP relaxations.
• These use the special form of the constraints
to obtain local-updates and more scalable
algorithms. We intend to apply these schemes
to our method.
41
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
1
0.2
0.4
0.5
0.6
0.8
1
0
42
• M(G)＜ML(G)
M(G)
ML(G)
• 定式化に要する変
数の数はM(G)のほ
うが多い
43
LP緩和とは
• 実際に解きたい問題は組み合わせ最適化
• これを連続に拡張→Marginal Polytope
• 連続だとLPの手法を使って解ける
– CPLEX
– Tree-reweighted belief propagation (TRBP)
• しかし近似になる
• いかに解を厳密にするか→いかにtightに緩
和するか
44
• MAP problem
X2
X3
X1
max f (x) s. t. xi  Di
P(X1,X2,X3)
x1
０
１
(X1,X2,X3)
P(X1=x1)
0.7
0.3
(0,0,0)
0.2
x1
０
１
(0,0,1)
0.2
P(X1＝x1,X2=0)
0.4
0.25
(0,1,0)
0.15
P(X1＝x1,X2=1)
0.3
0.05
(0,1,1)
0.15
x3
０
１
(1,0,0)
0.25
P(X1＝x1,X3=0)
0.35
0.3
(1,0,1)
0
P(X1＝x1,X3=1)
0.35
0
(1,1,0)
0.05
(1,1,1)
0
45
• MAP problem （ここでは尤度最大化と同じ）
x3
X2
fa
X3
fb
X1
fb
X1
１
P(X1=x1)
0.7
0.3
０
１
x3
０
P(X2＝0,X3=x3) 0.35 0
P(X2＝0,X3=x3) 0.35 0
０
１
x3
０
１
P(X2＝１,X3=x3)0.35 0.3
P(X2＝１,X3=x3)0.35 0.3
P(X2＝0,X3=x3) 0.35 0
P(X2＝0,X3=x3) 0.35 0
０
１
x3
０
１
P(X2＝１,X3=x3)0.35 0.3
P(X2＝１,X3=x3)0.35 0.3
P(X2＝0,X3=x3) 0.35 0
P(X2＝0,X3=x3) 0.35 0
2M-1
(X1,X2,X3,X4,X5,X6)
P(X1,X2,X3,X4,X5,X6)
(0,0,0,0,0,0)
0.15
(0,0,0,0,0,1)
0
(0,0,0,0,1,0)
0.15
１
P(X2＝１,X3=x3)0.35 0.3
x3
fb
０
P(X2＝１,X3=x3)0.35 0.3
x3
X1
x1
2M
・
・
・
・
・
・
・
・
・
・
・
・
・
・
(1,1,1,1,1,0,0)
0.2
(1,1,1,1,1,0,1)
0
(1,1,1,1,1,1,0)
0.2
(1,1,1,1,1,1,1)
0.05
47
所感
• 筆者らはM-best MAP問題を解くためのLPの
定式化を新しく提案した。
• Gが木の場合のM-best MAP問題は、積和ア
ルゴリズム＋beam search(HMMでやられて
いるようなk-best)でも解ける。そしてLPを解く
よりはきっとそっちの方が早いだろう。
• 基本的にはMAPさえintractableな時の提案法
と考えた方がよい。最適性の保証がある？の
がよいと筆者は主張しているようだ。
49
木の場合は効率的にできるはず・・・
• 木でない場合このような問題の計算量は爆
発するので、厳密に解くのはMAP問題でさえ
困難
• M-bestを近似する方法としてLBPの拡張など
が考えられている
– しかし、なんの保証もない近似法である
• 本手法は近似ではあるが最適性の保証が得
られる
50
例
• 各Xiは0,1変数
f θ (x)  1 ( x1 )   2 ( x2 )  3 ( x3 )  12 ( x1 , x2 )  13 ( x1 , x3 )
x
０
１
 1(x)
0.7
0.3
 2(x)
0.9
0.3
 3(x)
0.5
0.3
(x, x’)
(０、０)
(１、０)
(０、１)
(１、１)
 12(x, x’)
0.5
0.1
0.7
0.3
 13(x, x’)
0.6
0.6
0.7
0.3
51

Download Report