サマリー
ベイズ推定は、確率論的な視点からデータの解釈やモデルの学習を行う統計的な手法の一つとなる。ベイズ推定を用いた機械学習では、事前知識や経験をモデルに組み込み、データを通じてその知識を更新していくことが特徴で、データが少ない場合やモデルに不確実性がある場合に特に有効であり、過学習を抑制し、統計的な推定の不確実性を考慮することができるものとなる。ここではこのベイズ推定に関して、機械学習プロフェッショナルシリーズ「グラフィカルモデル」をベースに述べる。
ベイズ推定を行う具体的な手順は(1)事前知識や経験を確率分布として表現したモデルの事前分布の設定、(2)データがモデルに従って生成される確率(データの尤度)の設定、(3)データを観測した後のモデルの事後分布のベイズの定理による計算、(4)事後分布を用いたパラメータや予測値の推定、(5)推定結果を評価したモデルの修正や改善となる。この中でグラフィカルモデルは、モデルの構造を視覚化するために、確率的な変数やその関係性をグラフで表現するものとなる。
機械学習プロフェッショナルシリーズ「グラフィカルモデル」読書メモ
視点の転換がカギ！ 変数間の因果やつながりをグラフで表現、分析するメリットを理解して使おう。 各種グラフィカルモデルの紹介から、機械学習における使い方まで丁寧に解説する。 この手法が有効な問題の見分け方、グラフの扱い、推論・学習に活かす方法など、 必要なことをコンパクトにまとめた。
第1章 グラフィカルモデル入門
1.1 ベイジアンネットワークとは
概要
グラフィカルモデル
ベイジアンネットワーク(有向)
確率的な因果関係をモデル化
マルコフ確率場(無向)
確率的な依存関係をモデル化
Example
血液型(デフォルメしてAとOで考える)
遺伝子型の組み合わせ(AA, AO, OO)
1.1.1 自分一人の確率モデル
確率変数Xが自分の血液型
確率変数Zが自分の遺伝子型
自分の血液型も遺伝子も知らない時の、確率のモデル化
遺伝子型zのもとでの血液型xの確率P0(X = x |Z = z)
1 x = A, z = AA
1 x = A, z = AO
1 x = O, z = OO
0 それ以外の場合
X, Zの同時確率 P(X, Z) = P0(X|Z)Pg(Z)
Pg(z) : 遺伝子型zの確率
確率モデル
血液型(X =A)の時
P(Z|X = A) = P0(X = A|Z)(Pg(Z)/P(X = A)
ベイズの定理(Bayes’ theorem)
結果Xのもとでの、原因Zの確率の計算
自分の血液型がAの時、遺伝子型がAAの確率
例: Pg(AA| X = A) =pg(AA)/(pg(AA) + Pg(AO) =3/5
Pg(AA)=9/16, Pg(AO)=3/8, Pg(OO)=1/16
1.1.2 両親を入れた確率モデル
自分の(血液型の)遺伝子型は、 両親の血液の遺伝子型からある確率で決まる
父親の血液型(X1), 母親の血液型(X2)
3 x 3 x 3の条件付き確率のテーブル
Pi(Z0|Z1,Z2)
Z0 : 自分の遺伝子型
Z1 : 父親の遺伝子型
Z2 : 母親の遺伝子型
自分と両親の血液型、遺伝子型の同時確率
P(X0,Z0,X1,Z1,X2,Z2) = P0(X0|Z0)P0(X1|Z1)P0(X2|Z2)Pi(Z0|Z1,Z2)Pg(Z1)Pg(Z2)
確率モデル
自分の遺伝子型を推定する問題
P(Z0|X0,X1,X2) = P(Z0,X0,X1,X2) / P(X0,X1,X2)
自分と両親の血液型が全てA型である時、 自分の遺伝子型がAAである確率
P(Z0 = AA|X0 = A, X1 = A, X2 = A) = 8/13
両親の遺伝子型を知りたい
自分と両親の組み合わせのうち、 最も確率の高い組み合わせを求める問題となる
argmaxP(Z0,Z1,Z2|X0,X1,X2)
(与えられた条件づけのもとで)確率が最大になる値の組み合わせ
MAP割り当て (maximum a posteriori assignment)
自分と両親の血液型が全てA型である時
最も確率が高い組み合わせ
Z0=AA, Z1=AA, Z2=AA
1.1.3 配偶者と子を入れた確率モデル
配偶者と子を入れた確率モデル
配偶者の血液型(X3), 子供の血液型(X4)
モデル式
P(X0,Z0,X1,Z1,X2,Z2,X3,Z3,X4,Z4) = P0(X0|Z0)P0(X1|Z1)P0(X2|Z2)P0(X3|Z3)P0(X4|Z4) Pi(Z0|Z1,Z2)Pg(z1)pg(Z2)Pg(Z3)Pi(Z4|Z0,Z3)
ネットワークモデル
1.1.4 データからの学習
上記の議論は事前に確率P0や 条件付き確率Pg,Piがわかっている仮説
確率が事前に分かっていない場合 の方が事例としては多い
例
性格を確率変数として加えたモデル
「几帳面」「大雑把」
(条件付き)確率の値をデータから決める
グラフィカルモデルのパラメタ学習
1.1.5 データ枷の構造学習
関係が事前にわからない場合に 確率変数間の「矢印」を学習する
構造学習「structure learning」
1.2 マルコフ確率場とは
マルコフ確率場における確率変数は、 一方が他方を決めるのではなく、 相互に関連しあっているイメージ
最もシンプルな例
イジングモデル(Ising model)
格子状にスピン(±1)と呼ばれる量がある
格子点iのスピンxiは、その周辺のスピンの値によって確率的に決まる
全体の確率
Zは規格化定数
ギブス分布(Gibbs distribution)
Jij >0であればxiと様は同じ値をとる確率が高い
Jij < 0であれば異なる値をとる確率が高い
hi > 0であれば、xiが値1をとる確率が高くなる
式の変形
N(i)はIに隣接する格子点
xiの振る舞いは、その近傍の格子点の変数の値から決まる
確率の計算、MAP割り当ての計算、パラメータ計算、構造計算が必要となる
マルコフ確率場のパラメタ学習 (parameter learning)
{Jij}、{hi}をデータから推定する
1.3 グラフ構造を考える利点
少ない情報で確率を表現することが可能
グラフ構造を用いて確率やMAP割り当ての(近似)計算を効率化できる
第2章 確率論の基礎
2.1 確率論の基礎
2.1.1 確率の数学的定式化
定義2.1 (σ- 加法族)
集合Ωその部分集合族Fが 以下の3つの条件を満たす時 Σ-加法族(σ-algebra)という
1. Ω ∈ F
2. A ∈ FならばΩ\A ∈ Fが成り立つ
Ω\AはAの補集合
3. Fの加算個の元A1,A2…に対してUiAi ∈ Fが成り立つ
組(Ω, F)は可測空間(measurable space)、 Fの元は可測集合(measurable set)と呼ばれる
定義2.2 (確率空間)
集合Ωと、その部分集合族からなるσ-加法族Fが与えられているとする。 Fから実数への写像Pが確率(probability)であるとは 以下の3つの条件(コルモルゴフの公理)満たすことである
1. 任意のA ∈ Fに対して0 ≤ P(A) ≤ 1
2. P(Ω) =1
3. 互いに素な(disjoint)A1,A2,…に対してP(UiAi) =∑iP(Ai)
集合Ωは標本空間(sample space), 三つ組(Ω, F, P)は確率空間(probability space)と呼ばれる
確率変数
標本空間上で定義された関数
定義2.3 (離散的な確率変数)
写像X : Ω → ℤが確率変数(random variable)であるとは
任意のx ∈ ℤに対して逆像X-1({x})が可測集合であることをいう
例
6つの目の出方が均等でないサイコロ
このサイコロを1回振ることは 確率変数X:Ω → {1,2,3,4,5,6}を一つ考えることになる
値が1である事象は
A1 := {ω ∈ Ω | X(ω) = 1}というΩの部分集合で表される
P(A1)はサイコロの目が1に等しい確率
P(X=1)
コルモゴロフの公理1
サイコロの目の出る確率はどれも0から1の間
コルモゴロフの公理2
サイコロを振ってその目が1から6のどれかである確率が1である
コルモゴロフの公理3
1が出る確率+2が出る確率=1または2が出る確率
2.1.2 確率変数の分布関数
確率変数Xに対して、P(X=x)はXのとる値のバラツキ方を表す
xの関数として確率分布関数 (または、確率質量関数(probabilitymass function)と呼ばれる
2つの確率変数X,Yがあった時
確率分布関数P(X=x, Y=y)は x,yの2変数関数とみなす
同時確率分布関数 (または、同時確率質量関数(joint probability mass function))
Yに対して足しあげると
∑P(X=x, Y=y) =P(X=x)
同時確率分布をどれかの変数に関して足しあげる
周辺化(marginalization)
同時確率関数を周辺化すると、残りの変数に関する確率変数が得られる
3個以上の変数に対しても適用される
2.2 確率変数の独立性
2つのサイコロを投げた時、その目は互いに「無関係」にばらつく
確率変数の独立性
定義2.4(確率変数の独立性)
確率変数X1 : Ω → ℤが任意のB1,B2 ⊂ ℤに対して
P(X1 ∈ B1 , X2 ∈ B2) =P(X1 ∈ B1)P(X2 ∈ B2)
P(A∩B)=P(A,B)
を満たす時、X1,X2は独立(independent)であるといい以下のように表記する
X1 ⫫ X2
例
均等でないサイコロの場合
2つの確率変数Xi :Ω → {1,2,3,4,5,6} (i=1,2)
これらが独立であれば
P(サイコロ1の目が1 かつ サイコロ2の目が5) = P(サイコロ1の目が1)P(サイコロ2の目が5)
N個の確率変数に拡張可能
2.3 条件付き確率
確率変数間の依存関係
条件付き確率の概念で捉えることが可能
2.3.1 条件付き確率の定義
確率空間(Ω,F,P)とその上の確率変数X
条件
確率変数Xの値がBの中に入っている
Ωの部分集合X-1(B)={ω∈Ω|X(ω)∈B}の確率を1に規格化し、 それ以外の確率を全て0にする
条件付き確率 (conditional probability) QB
QB(A) = P({ω ∈ Ω| ω ∈ A, X(ω) ∈ B}) / P(X ∈ B) for all A ∈ F
分母は規格化
P(A|B)=P(A∩B)/P(B)
P(A∩B)=P(A|B)P(B)
X,Yが離散的な確率変数の時、 Y=yという事象が観測されたもとでの X=xの確率
P(X = x| Y = y) = P(X = x, Y = y) / P(Y = y)
例
サイコロを一つ投げる
Xがサイコロ目の値、Yがサイコロ目の値の奇数偶数
x=2,4,6でP(x|Y=偶数)=1/3
x=1,3,5でP(x|Y=偶数)=0
2.3.2 独立性と条件付き確率
XとYが独立であれば、Yを観測することによってXの確率分布は影響を受けない
独立性
P(A∩B)=P(A)P(B)の時
P(A|B)=P(A)
Aの周辺確率に等しい
P(B|A)=P(B)
Bの周辺確率に等しい
2.4 条件付き独立性
グラフィカルモデルでは条件付き独立性が重要になる
2.4.1 条件付き独立性の定義
定義2.5(条件付き独立)
確率変数X,Y,Zについて、 X,YがZの元で条件付き独立(conditionallyindependent)であるとは
P(X,Y|Z)=P(X|Z)P(Y|Z)が成立することをいう
この時X ⫫ Y | Zと書く
Zの値が観測されているという条件の元で、XとYが独立
Yについて知りたい時、 Zの値がわかればヒントとしては十分で、 Xの値は必要ない
2.4.2 条件付き独立性の性質
独立性の条件
P(X|Y,Z) = P(X|Z)
P(Y|X,Z) = P(Y|Z)
P(X,Y,Z)=Φ1(X,Z)Φ2(Y,Z)がある関数Φ1,Φ2に関して成立する
2.4.3 条件付き独立な確率変数の例
前提条件
手元にM枚の歪なコインがある
z番目のコインが出た時に表が出る確率をpz(z=1,2,…M)
確率変数Zをコイン1枚を無作為に選ぶ操作
選んだコインを2回投げる
確率変数X: そのコインを1回目に投げた時に表か裏か
確率変数Y: そのコインを2回目に投げた時に表か裏か
Z=zが固定されていればXの結果がなんであれYが表らなる確率はpz
X ⫫ Y | Z
X,Yは独立でない
Xが表だと選んだコインが表である確率が高まり、 Yも表である可能性が高まる
2.4.4 独立性と条件付き独立性の違い
X ⫫ Y | ZであってもX ⫫ Y である必要条件でも十分条件でもない
強く関係しているXとYがZの値で「層別」されて残りの変動が無関係になっただけ
2.5 連続的な確率変数の取り扱い
確率変数の値が連続的な集合の場合
2.5.1 確率密度関数 (probability density function)
特定のポイントで確率を表すのではなく、ある範囲での積分部表す
2.5.2 条件付き確率密度関数
第３章 ベイジアンネットワーク
3.1 有向グラフの用語
有向グラフ(directed graph)
有限集合Vとその直積集合の部分集合ベクトルE ⊂ V x Vの組(V, ベクトルE)
V: 頂点(vertes)集合
ベクトルE: 有向辺(directed edge)集合
(𝓊, 𝓋) ∈ ベクトルE
頂点𝓊から𝓋への有向辺
頂点の部分集合V0 ⊂ Vに対して
両辺がV0につながっている有向辺のみを取り出した辺集合ベクトルE0={(𝓊, 𝓋) ∈ E| 𝓊, 𝓋 ∈ V0}
グラフ(V0,ベクトルE0)を誘導する部分グラフ (induced subgraph)
有向グラフの路(walk)
頂点の列(𝓋0,𝓋1,…,𝓋L)
𝓋0=𝓋Lのとき閉路(closed walk)
閉路を持たない有向グラフ
有向非巡回グラフ (directed acyclic graph,DAG)
頂点𝓋に対して有向辺を伸ばしている頂点は、𝓋の「親」(parent)
pa(𝓋) := {𝓊 ∈ V | (𝓊, 𝓋) ∈ ベクトルE}
頂点𝓋から有向辺が伸美ている頂点は、𝓋の「子」(child)
ch(𝓋) := {𝓊 ∈ V | (𝓋, 𝓊 ) ∈ ベクトルE}
有向非巡回グラフの頂点で、特に親を持たないものを「始頂点」(source)
有向非巡回グラフの頂点で、特に子を持たないものを「終頂点」(sink)
有向非巡回グラフの頂点𝓋に対して、その「子孫」(descendant)とは𝓋からの路が存在する頂点の集合
des(𝓋)
V\({𝓋} ∪ des(𝓋))
非子孫(non-descendant)
ndes(𝓋)
3.2 有向非巡回グラフの特徴づけ
閉路を持たない有向グラフ
有向グラフのトポロジカルソート(topological sort)
頂点集合Vから{1,2,…,|V|}への全単射で
(𝓋0, 𝓋1) ∈ ベクトルE ⇒ n(𝓋0) < n(𝓋1)
各ノードを順序付けして、 どのノードもその出力辺の先のノードより前に くるように並べること
有向非巡回グラフは必ずトポロジカルソートすることができる
例
左のグラフには次のように複数の結果にトポロジカルソートできる 7, 5, 3, 11, 8, 2, 9, 10 (見た目において左から右、上から下への順) 3, 5, 7, 8, 11, 2, 9, 10 (数値的に小さなノードを前に持ってくる) 3, 7, 8, 5, 11, 10, 2, 9 5, 7, 3, 8, 11, 10, 9, 2 (辺の数が少ないノードを前に持ってくる) 7, 5, 11, 3, 10, 8, 9, 2 (辺の数が多いノードを前に持ってくる) 7, 5, 11, 2, 3, 8, 9, 10
作成のアルゴレリズム
カーン(Kahn)のアルゴリズム
定理3.1(有向非巡回グラフの特徴づけ)
閉路を持たない
任意の部分グラフに終頂点が存在する
任意の部分グラフに始頂点が存在する
トポロジカルソートが存在する
3.3 ベイジアンネットワークの定義
有向非巡回グラフの頂点が確率変数に対応、 有向辺が因果関係を記述
定義3.1(ベイジアンネットワーク)
有向非巡回グラフG=(V,ベクトルE)が与えられている
確率変数の有限集合X = {Xi}i∈Vが任意のi∈Vで
Xi ∐ Xndes(i) | Xpa(i)
を満たす時、 グラフ構造Gを持つベイジアンネットワーク(Bayesian network)であるという
Xiの値がXpa(i)から確率的に決まる
3.4 ベイジアンネットワークの因子分解
3.4.1 因子分解定理
定義3.2(ベイジアンネットワークの因数分解)
有向非巡回グラフG=(V,ベクトルE)上の 確率変数X={Xi}i∈Vが ベイジアンネットワークであるということは
確率分布関数Pが以下のような積に分かれることと同値
P(X) = ∏P(Xi|Xpa(i))
因果独立の仮説 (casual independence)
直接の親ノード以外は因果的に独立
例
グラフの子から因数分解
P(X)=P(X5|X1,X2,X3,X4)P(X4|X1,X2,X3)P(X3|X1,X2)P(X2|X1)P(X1)
置き換え
X5の直接の親はX3のみ
P(X5|X1,X2,X3,X4)=P(X5|X3)
P(X4|X1,X2,X3)=P(X4|X2,X3)
P(X3|X1,X2)=P(X3|X1)
P(X2|X1)=P(X2)
置き換え後
P(X)=P(X5|X3)P(X4|X2,X3)P(X3|X1)P(X2)P(X1)
3.4.2 ベイジアンネットワークの構成
局所的な条件付き確率のテーブルを 掛け算することでベイジアンネットワークが得られる
補題3.4(ベイジアンネットワークの構成)
3.5 ベイジアンネットワークの例
3.5.1 自明なベイジアンネットワークとマルコフ過程
確率変数族 X = {X1,X2,…Xn}が与えられた時
確率分布関数PはP(X1,X2,…,XN) = ∏ P(Xj|Xj-1,…,X1)
確率変数族 X = {X1,X2,…Xn}がマルコフ過程(Markov process)であるとは
Xt+1 ∐ (X1,…,Xt-1) | Xtが成立
3.5.2 3変数からなるベイジアンネットワーク
有効非巡回グラフとしての3つの分類
Head to tail
P(X1,X2,X3)=P(X3|X2)P(X2|X1)P(X1)
Tail to tail
P(X1,X2,X3)=P(X1|X2)P(X3|X2)P(X2)
Head to head
P(X1,X2,X3)=P(X2|X1,X3)P(X1)P(X3)
3.6 グラフと条件付き独立性
ベイジアンネットワーク上の確率変数は ある種の条件付き独立性を満たす
3.6.1 グラフ理論的準備
有効非巡回グラフにおいての無向路(trail)
頂点の列{𝓊i}において𝓊i → 𝓊i+1 及び 𝓊i ← 𝓊i+1が成り立つ
V構造(V-structure)
𝓊I-1 → 𝓊I ← 𝓊I+1(head to head)
定義3.2 (アクティブな無向路)
有効非巡回グラフの頂点𝓊と𝓋を結ぶ無向路が、 頂点集合Wのもとでアクティブ(active)であるとは
無向路(𝓊1,𝓊2,…,𝓊L)上の全ての頂点𝓊iに関して以下の(どちらか)を満たすこと
𝓊IがV構造であるとき、(𝓊i ⋃ des(𝑢i)) ⋂ W ≠ 0
𝓊IがV構造でない時、𝓊i ∉ W
頂点集合Wの元で条件付けた時に、𝑢と𝑣に「つながりが生きている」
つながりが切れると、アクティブでなくなる
アクティブでなくなる状況
V構造の頂点𝑢iとその子孫にWの頂点が含まれていない
頂点𝑢iがV構造でなくて、Wに含まれている
3.6.2 条件付き独立性とd分離
グラフィカルモデルから変数間の独立性を読み取り、事後分布をよりシンプルな積に分解する
有効分離
d-分離
より複雑なモデルに対するど確率変数の独立性をチェックする手法
定義3.3(d分離)
有効非巡回グラフと互いに素な頂点集合U,W,Sを考える
U,Wが頂点集合Sの元でd-分離(d-separation)であるとは
任意の頂点𝑢∈U, 𝑤∈Wに対して、 それらを結ぶような「頂点集合Sの元でアクティブな無向路」を持たないことをいう
定理3.4(d分離の導く条件付き独立性)
有効非巡回グラフの頂点集合U,T,Wが互いに素であるとする
U,TがWの元でd分離されているならば
確率変数Xu, XT,が確率変数XWの元で条件付き独立である
すなわち XU ⫫ XT|XW
第４章 マルコフ確率場
はじめに
相互的な依存関係を反映した確率構造
4.1 無向グラフの用語
無向グラフ(undirected graph)
有限集合Vを頂点集合とし、それらを向きのない辺で結んだもの
辺集合Eとしたとき、頂点𝑢と𝑣を結ぶ辺を𝑢𝑣 ∈ Eと書く
無向グラフの路(walk)
頂点の列(𝑣0,𝑣1,…,𝑣L)であって(𝑣i,𝑣i+1)∈Eを満たすもの
頂点集合Vの部分集合A,Bにおいて、SがAとBを分離するとは
任意の𝑎∈A,𝑏∈Bに関して𝑎と𝑏を結ぶ任意の路がSの頂点を通ること
頂点𝑣∈Vの近傍(neighbour)とは
N(𝑣) = {𝑢 ∈ V| 𝑢𝑣 ∈ E}
頂点𝑣∈Vの閉包(closure)とは
cl(𝑣) = {𝑣} ⋃ N(𝑣)で定義される
4.2 マルコフ確率場の定義
定義4.1(マルコフ性の3つの定義)
グラフG(V,E)上の確率変数(X𝑣)𝑣∈Vに関して、以下の3種類のマルコフ性を定義する
大域マルコフ(global Markov:G)
大域マルコフであるとは、Vの互いに素な部分集合S,A,BでSがAとBを分離するものについてXA⫫XB|XSが成立すること
局所マルコフ(local Markov:L)
局所マルコフであるとは、任意の𝑣∈Vに対してX𝑣⫫XV\cl(𝑣)|XN(𝑣)が成立すること
N(𝑣)は、頂点𝑣のマルコフブランケット(Markov blanket)
ペアワイズマルコフ(pairwise Markov:P)
ペアワイズマルコフとは、任意の𝑢,𝑣∈Vで、𝑢𝑣∉Eなるものに対してX𝑣⫫XV\{𝑣,𝑢}が成立する
定理4.1(マルコフ性条件の関係.1)
(G)⇒(L)⇒(P)が成立する
交差律の元で、(P)⇒(G)が成立する
確率分布関数が正の時は交差率が必ず成り立つ
3つの条件(G),(L),(P)は同値になる
4.3 マルコフ確率場の因子分解
前節では、マルコフ性を条件付き独立性の観点から議論
ベイジアンネットワークの場合と同様に、マルコフ確率場は関数の積への分解によって特徴つけられる
グラフ理論の用語を準備
グラフG=(V,E)の頂点部分集合Uが完全部分グラフとは
グラフG=(V,E)の頂点部分集合Cがクリーク(clique)であるとは
定義4.2(因子分解の性質 )
グラフ構造を持つ確率変数が、グラフGに関して因子分解(factorize)する(F)とは
その確率分布関数Pが上式のように書けること
Zは規格化定数
定理4.2(マルコフ性条件の関係.2)
(F)⇒(G)が成立する
定理4.3(Hammersley-Cllifordの定理)
確率分布について、P>0が成立する時、(F)と(P)は同値である
(G)⟹(F)が成立
4.4 ベイジアンネットワークとマルコフ確率場
確率変数X={X𝑣}𝑣∈Vが有効非巡回グラフ(V,ベクトルE)上のベイジアンネットワークであるとき
条件付き確率分布関数を用いて因子分解できる
各頂点𝑣∈Vで、𝑢,𝑢’∈pa(𝑣)同士を辺で結び、有向辺を無向辺としたグラフを考えると(F)の因子分解ができる
有効非巡回グラフから無向グラフを作る操作
例
左のベイジアンネットワークは、 右のようなグラフ構造を持つマルコフ確率場でもある
4.5 例: ガウス型のマルコフ確率場
多次元ガウス型確率変数の確率密度関数
正定値対称行列Jとベクトルμを用いる
確率密度関数の特徴として、指数関数の肩にxの3次式を含まない
上式は変形可能
I,j∈に関して上式のように書ける
A,B,Cはxi,xjによらない定数
この確率密度関数が積に分かれる条件
多次元ガウス分布をマルコフ確率場としてみた場合、 そのグラフはJij≠0となるi,jを辺で結んだものになる
第５章 因子グラフ表現
はじめに
ベイジアンネットワークとマルコフ確率場の確率分布関数は、 局所的な関数の積で表される
より直接的に関数の積表示をグラフ表現する方法について
ベイジアンネットワークとマルコフ確率場は双方とも超グラフで表現可能
無向グラフの拡張
矢印の情報は失われる
グラフ構造に対応した積構造を持つ確率分布関数(族)を総称して 「グラフィカルモデル(graphical model)」とよぶ
5.1 超グラフの用語
超グラフでは、1つの超辺が複数の頂点を結ぶ
普通のグラフでは、辺は2つの頂点を結ぶ
頂点集合をVとすると
Vの部分集合を超辺(ハイパーエッジ,hyper-edge)と呼ぶ
超辺からなる集合Fと頂点集合のペア(V,F)
V={v0,v1,…,v4}, F={{v0,v1,v4}, {v0,v3}, {v2,v3}}
超グラフは2種類の頂点からなる 通常のグラフとして図示することが可能
頂点i∈Vに対して、その近傍をN(i)={α|α∈F, i∈α}と定義
超辺α∈Fに対して、その近傍をN(α)={i|i∈V, α∈i}と定義
全ての超辺の次数が2である場合は、超グラフは通常のグラフと同じになる
5.2 因子グラフ型モデルの定義
定義5.1(因子グラフ型モデル)
前提条件
超グラフH=(V,F)が与えられている時
更に、頂点i∈Vに対して集合xiと 辺α∈Fに対して𝝍α:∏i∈αxi→ℝ≥0が与えられている時
p(x) = 1/Z ∏Ψα(xα)
因子グラフ型モデル(factor graph model)
Z:規格化定数
Z=∑∏Ψα(xα)
上式で定義される確率分布(族)を 因子グラフ型モデル(factor graph model)という
Zは規格化定数
超グラフH
超辺αに対応した関数Ψαの積の形に分かれる
超辺αは因子(factor)
関数Ψαは因子関数(factor function)
Zは計算して出すことが難しい
Zが具体的に計算できないと、与えせれたxに対して確率値p(x)を計算することができない
一部の条件付き確率は簡単に計算することができる
頂点iに対してその近傍に含まれる頂点を B(i)={j|j∈α, α∋i, j≠i}とすると常識が成り立つ
5.3 因子グラフ型モデルとマルコフ確率場
因子グラフ型モデルと マルコフ確率場モデルの違いについて
因子グラフ型モデルからマルコフ確率場を得るには?
ある頂点𝓊,𝓋が一つの因子に含まれていれば𝓊,𝓋を辺で結べば良い
マルコフ確率場から因子グラフ型モデルを得るには?
グラフのクリークを超辺とした超グラフを作れば良い
マルコフ確率場のグラフ表示は情報が少なくなる
異なる因子グラフがマルコフ確率場では同じグラフに表現される
例
p(x1,x2,x3)=Φ(x1,x2)Φ(x2,x3)Φ(x3,x1)の因子グラフ
p(x1,x2,x3)=Φ(x1,x2,x3)の因子グラフ
マルコフ確率場でのグラフ
マルコフ確率場のグラフ表現は条件付き独立性(マルコフ性)の観点からは自然だが、 因子グラフ表現の方がより詳細な積への分解構造を持つ
2つの因子グラフとそれに対応するマルコフ確率場のグラフ
マルコフ確率場の方が情報量が少なくなる
5.4 因子グラフ型モデルとベイジアンネットワーク
ベイジアンネットは条件付き確率の積で表せる
ベイジアンネットは因子グラフ型モデルとしても解釈可能
因子グラフによる確率分布関数の表示は計算を効率化する文脈で使われている
5.5 因子グラフ型モデルの例
5.5.1 2値ペアワイズモデル
全ての因子がちょうど2つの頂点を持つ時
マルコフ確率場と因子グラフは同じグラフとなる
全ての因子関数はΨ(xi, xj)と書ける
ペアワイズな因子グラフ型モデルの中で最も単純なもの
頂点上の変数は1か-1
因子関数は2×2=4つの引数をとる
因子関数は上式となる
確率pの多値への一般化は上式となる
Hi’をまとめたものをhiとする
規格化定数
5.5.2 組合せ最適問題
多くの組み合わせ最適化問題に現れる局所的な制約は、 「因子関数により表現できる」
例:SAT(真偽値充足問題)による説明
前提条件
変数xiは真偽値(0:謝, 1:真)を取るものとする
xiの否定はẋi=1-xiとする
節(clause)とは、xiやその否定をOR演算子∨で連結したもの
Clause例:(x1∨x2∨x3)
いくつかの節をAND演算子∧で連結して得られる論理式
CNF例:(x1∨x2∨x3)∧(x2∨x4∨x5)
与えられたCNFに対してそれを満たす変数の値{xi}を求める
全ての節がK個の変数からなる時
因子関数を上式とする
節αに含まれる変数をxαとして そのエネルギー関数Eαを以下のように定義する
0 xαが節αの条件を満たす時
1 xαが節αの条件を満たさないとき
Βは定数
与えられたCNFに対して、 満たさない節の個数が最小になる真偽値の割り当ては、 この確率分布の確率が最大の状態に対応
第６章 周辺確率分布の計算1 : 確率伝搬法
6.1 各推論の定式化
観測された確率変数たちY = (Y1,Y2,…,YL)に基づいて 観測されていない確率変数たちX = (X1,X2,….,XM)の確率を計算する
与えられた観測値{yi}の元で 各Xiの周辺確率分布(上式)を計算する
例
上図のような因子グラフ型モデルの場合
変数y1,y2が観測されている時
観測されていない変数x1,x2の確率分布は上式となる
元の因子関数にy1,y2を代入したものになる
確率変数XとYからなる因子グラフ型モデルが与えられ
観測Y=(Yj)のもとでの周辺確率分布を計算する問題
変形された因子グラフ上での(条件つけなしの) 周辺確率分布を計算する問題に帰結する
実際の計算は困難
近似が必要
木構造だと確率伝搬法を用いて効率的な計算が可能
6.2 木の上での確率伝搬
6.2.1 木の定義
任意の2頂点を始点と終点とするような路が存在する
全ての頂点の次数が2である
サイクルの例(太線)
サイクルを持たない連結なグラフ
木の例
2部グラフ表現が木である
木の頂点で次数が1のもの
6.2.2 直線型グラフ上での確率伝搬場
最も単純な例での考察(因子がペアワイズで、グラフが直線)
確率分布p(x) = 1/Z Φ12(x1,x2)Φ23(x2,x3)Φ34(x3,x4)Φ45(x4,x5)
x3での周辺確率の定義式
全てのx3でp3(x3)を求めるのに必要な計算の回数はK5
変数xiの状態の数をそれぞれKとする
P3(x3)の周辺確率の定義は上記のように変形可能
計算減のため
各x2についてx1の足し算を行うのでK2の計算
同様に他のものもK2なので最終的に「4K2」の計算となる
右から順番に計算していく
グラフの端から計算して量を送っていく方法で効率化
動的計画法(dynamic programming)での一般的計算手法の一部
動的計画法でのアルゴリズム例
CKY(Cocke-Younger-Kasamiアルゴリズム(自然言語処理の構文解析)
Viterbiアルゴリズム:隠れマルコフモデルの最適系列
Dynamic Time Wrapingアルゴリズム:系列間の類似度を比較
6.2.3 ペアワイズモデルでの確率伝搬法
前述の計算方法を木の場合に一般化
グラフの端から順に計算した量を送っていくのは同じ
木構造グラフG=(V,E)上のペアワイズである因子グラフ型モデルが上式で表される
木のグラフでの確率伝搬法のアルゴリズム
葉iに対して、mi→jのメッセージが定まる
その後メッセージは葉から順に全て決まっていく
確率伝搬法だと一度メッセージ(確率)を計算しておけば、全ての頂点(変数)に関して求められる
ペアワイズ(Pair-wise)法(all-pair法)では 直交表ベースのアプローチより大きなモデルを扱うことができる
テストケースの生成でペアワイズ法はよく使われる
パラメータの数を単純に組み合わせていくとテストケースが膨大になる
実際に影響があるのは2つのパラメータの値の組合せが多いので、 パラメータで組みを作ってその組みごとに全ての値をテストする
例
会員IDの欄とパスワードの欄がある
これに未入力か、正常に入力されているか、異常な値が入力されているかなどの状態があるとき
3*3=9通り必要となる
さらに会員登録時のフォームで、性別、都道府県、メールアドレスなどの項目があると
9*27=243通りとなる
6.2.4 因子グラフでの確率伝搬法
確率伝搬法は、木の因子グラフにも拡張される
メッセージの更新は複雑になる
因子グラフモデルが上式のように与えられたとする
木の因子グラフ上での確率伝搬法のアルゴリズム
メッセージmα→i(x)の更新式の模式図
6.3 通用例:隠れマルコフモデル(Hidden Markov Model : HMM)
HMMモデルでの確率伝搬法の計算
HMMモデルの式
HMMの概念図
観測値xの元で、 隠れ状態zの周辺確率分布を計算する
観測xのもとでのグラフィカルモデルは上式となる
Φt,t+1の定義
確率伝搬法のメッセージ関数(準方向と逆方向)
6.4 連続変数の場合
ガウス関数でも同様の議論ができる
ガウス分布を周辺化してもガウス分布になる
非ガウス型の連続変数では、近似を用いた確率伝搬法が必要
近似方法
十分変量の期待値の一致性で代用する方法
確率密度関数を表現する方法
パーティクルを用いる方法
ヒルベルト空間への埋め込みを行う方法
6.5 他の厳密計算方法
木でない超グラフであっても、 ジャンクションツリー(ジョインツリー)と呼ばれる木に変換して、 その上で確率伝搬法を実施
木幅(tree width)に関して指数オーダー
木幅が大きいと使えない
周辺化(=変数の消去)を順番に行う
因子関数を消していく
第７章 周辺確率分布の計算2 : ベーテ近似
はじめに
木以外にも確率伝搬法のアルゴリズムを適用して、近似的に周辺確率分布を計算する
変分法の観点からは、ベーテ近似
ベーテ近似の拡張法である菊池欣治から、一般化確率伝搬法を導く
7.1 サイクルのあるグラフ上での確率伝搬法
7.1.1 確率伝搬法のアルゴリズム
一般の因子グラフ上での確率伝搬法アルゴリズム
木の上でない確率伝搬法では、メッセージの更新は有限回で終了しない
全てのα→iで、mtα→i(xi)とmt+1α→i(xi)がほぼ等しくなるまで更新を続ける
収束しない場合がある
グラフ構造が木に近い場合や、確率変数間の従属性が弱い場合には、収束しやすくなる
周辺確率分布の近似解bi,bαは 局所整合条件(local consistency condition)と 呼ばれる上式の関係を満たす
7.1.2 例:サイクルを1つ持つグラフ上での確率伝搬法
木ではない最も簡単なグラフ:サイクル型のグラフ
確率分布関数の式
このグラフ上での確率伝搬法は、右回りのメッセージと左回りのメッセージを計算
適切な係数αのもとで上式が設立する
行列Φとベクトルm0,1を用いて上式のようになる
行列の固有値を解く問題になる
サイクルが一つしかない場合は、確率伝搬法の固定点は線形方程式により特徴づけられる
サイクルが2つ以上の場合は複雑な非線形方程式になり固定点がたくさん存在する
7.2 変分法による定式化
7.2.1 ギブス自由エネルギー関数
木の場合で真の周辺確率分布が ギブス自由エネルギー関数の変分法によって 特徴づけられることを説明
ギブス自由エネルギー関数(Gibbs free energy function)は、確率pの関数として上式で定義される
Pの関数として凸関数
上記の値で最小値-logZをとる
この因子関数簇{Ψα}の定める確率分布は、 ギブス自由エネルギー関数の変分問題により特徴づけられる
木の場合では、任意の確率分布pが、 その周辺分布{pi, pα}を用いて上式で表される
これをギブス自由エネルギーの計算式に入れると
7.2.2 ベーテ自由エネルギー関数
ベーテ自由エネルギー関数はギブス自由エネルギー関数を近似するもの
サイクルのある超グラフGに対して、凸集合𝕃(G)を上式で定義する
局所整合条件を満たすような周辺確率分布の候補の集まり
その元を疑周辺確率分布(pseudo marginal distribution)と呼ぶ
ベーテ自由エネルギー関数の定義は上式となる
この式の最小化問題を解くことで、 周辺確率の計算を近似的に行うアプーローチ
一般に問題の解を何らかの最小化(最大化)問題によって特徴づける方法
定理
自由エネルギー関数の傾きが0の点が解となる
関数の凹凸具合
式
超グラフが木またはただ1つのcの場合は凹関数となる
ベーテ自由エネルギー関数が凸となる
確率伝搬法の解が一意となる
グラフのゼータ関数と呼ばれる量と密接に関係
確率伝搬法の双対的な特徴
7.3 一般化確率伝搬法
はじめに
ベーテ自由エネルギー関数の一般化である聞く値自由エネルギー関数からの、一般化確率伝搬方について
梯子型のグラフ構造をもとに検討
7.3.1 交わりで閉じた部分集合族
部分集合簇とHasse図の例
7.3.2 木の場合の確率の分解公式
定理
7.3.3 菊池エントロピー関数の導出
定義:菊池エントロピー関数
7.3.4 菊池エントロピー関数とベーテエントロピー関数の関係
菊池エントロピー関数が、ベーテエントロピー関数の拡張になっている
7.3.5 一般化確率伝搬法の導出
一般化確率伝搬方アルゴリズム
7.3.6 一般化確率伝搬法の計算例
7.3.7 一般化確率伝搬法と菊池自由エネルギー関数
定理
第８章 周辺確率分布の計算3 : 平均場近似
はじめに
平均ば近似と呼ばれる変分問題からの周辺確率分布の近似計算
8.1 平均場近似
ギブス自由エネルギー関数を近似するのではなく、変分をとる範囲を狭める
ギブス自由エネルギー関数の引数に入れる確率分布を、 上式のように各変数ごとの確率分布の式に分解するものに限る
真の確率分布とのKLダイバージェンス(上式)を最小にするような{qi(xi)}i∈Vを探す
平均場近似のアルゴリズム
8.2 例: インジングモデルの場合
平均場近似はもともと物理で考案された近似手法
簡単な例としてインジングモデルがある
8.3 平均場近似と関連手法
ベーテ近似(確率伝搬法)と平均場近似は適している場面が異なる
ベーテ近似は器のアルゴリズムから派生した近似手法
サイクルの影響が少ない場合に近似の精度が良くなる
平均場近似は周辺からの影響がその平均の周りでバラつかないような場合に効果を発揮
グラフ構造としては、頂点の次数が高く、完全グラフに近いものが該当
8.4 周辺確率分布の計算 サンプリングによる方法
このほかの手法としてサンプリングを用いたものもある
因子モデルはギブスサンプリング
第９章 グラフィカルモデルの学習1 : 隠れ変数のないモデル
はじめに
データからグラフィカルモデルを求める方法について解説
背景にあるグラフの構造は既知とする
関数のパラメタを学習するタスク
データから確率モデルpθ(x)を学習する最も基本的な方法
観測データx(1),x(2),…,x(N)について、 対数尤度(上式)を最大にするθMLによってパラメータθを決定する
確率モデルに関する正則性条件のもとで、一致性(consistency)が成り立つ
グラフ自体も学習するタスク
9.1 ベイジアンネットワークの学習
はじめに
一般に米WHYの確率は、条件付き確率の積の形で表される
米WHYのパラメータ学習では、この条件付き確率をデータから求める
9.1.1 最尤法による学習
ベイジアンネットワークのパラメータ簇が 上式で与えられている時
各条件付き確率ごとにパラメータθiが割り当てられている
観測データ{x(n)}n=1,…,Nに対する 対数尤度関数は上式となる
足し算の順序を変えることにより、上式の和となる
最尤推定は各iについて、上式を最大にするθi,MLを求めることになる
各頂点iごとに、 教師データ{(xpa(i)(n), xi(n))}を モデルlog pθ(x|x’)で学習する
ケース
前提条件
ベイジアンネットワークの全ての頂点が離散確率変数
パラメータθiがその条件付き確率テーブルそのものである
最尤法で決まる確率値はデータの場合の数で決まる
Ny, Nx,yは上式
9.1.2 ベイズ法による学習
頂点iの親の頂点数に関して指数関数的に数が増える
最尤法ではなくベイズ推定を使うことで解決
ケース
頂点iの確率テーブルの事前分布として、 パラメータα=(α1,…,αK)のディリクレ分布(上式)を考える
Kは確率変数Xiの状態の数
上式は規格化変数
データ{x(n)}n=1,…,Nを観測した後での、θの確率分布(事後分布)は
事後分布の計算が簡単にできるみとで、ディリクレ分布を使う利点
事後分布の確率値を最大とするθMAPをとる場合は上式となる
MAP推定量(maximum a posterior estimation)
事後分布の期待値θEAPは上式となる
EAP推定量(expected a posterior estimation)
上記を用いることで、有向非巡回グラフの頂点iごとに、条件付き確率テーブルが学習される
事前分布のハイパーパラメータα
パラメータθを周辺化して、データの確率(上式)を最大とするように求める
9.2 因子グラフ型モデルの学習 基本
はじめに
因子グラフ型モデルのパラメータをデータから学習する
ベイジアンネットワークと違って、 マルコフ確率場のようなものでは、 最適化を各頂点個度に行うことができない
因子グラフ型モデルの各因子は 対数線形モデルとして上式のようにパラメータ付けられる
Tα(xα)は十分統計量と呼ばれる
<・,・>はベクトルの内積
離散状態の場合のパラメータ付け
Δx(x)はx=ẋの時1でそれ以外では0となる関数
ガウス型の場合のパラメータ付け
9.1.1 学習の定式化
学習データx(1),…,x(N)では、 グラフィカルモデル上の全ての変数が観測されているので、x(n)={xi(n)}i∈Vとなる
最尤推定法によるパラメータの学習
対数尤度関数の式
第二項があるためにθに対する依存性が各因子に分解できない
最適なθを出すことが困難
指数型分布族であれば、尤度関数は凹関数になるので、原理的には勾配法で計算できる
微分計算結果は上式となる
Tα(xα)の経験分布に関する期待値と、 モデル分布に対する期待値が一致するようにθを決める
9.1.2 IPFアルゴリズムによる最尤法
多変数関数f(θ1,…,θd)が与えられたとき
各座標についての最小化を繰り返す手法
順にiを選び、変数θjを固定した状態で、θiについて最小化する
離散状態変数のモデルの場合において、 対数尤度関数を各θごとに最大化していく方法
離散状態でない場合は、Generalized Iterative Scalingアルゴリズム
IPFアルゴリズム
経験分布とモデル分布のギャップがなくなるまで更新を繰り返す
9.3 因子グラフ型モデルの学習・変分法による近似
9.3.1 分配関数とエントロピー関数の上昇
9.3.2 分配関数のTRW上昇
9.3.3 ベーテ近似
9.4 最尤関数による学習
第１０章 グラフィカルモデルの学習2 : 隠れ変数のあるモデル
10.1 問題設定と定式化
10.1.1 対数尤度関数の微分
10.2 変分下界と変分的EMアルゴリズム
10.2.1 準備: KLダイバージェンス
10.2.2 変分下界の導出と最適化
10.2.3 変分的EMアルゴリズム
10.2.4 EMアルゴリズム
10.3 グラフィカルモデルによる変分的EMアルゴリズム
10.4 他の学習手法
10.4.1 サンプリングによる方法
10.4.2 Wake-sleepアルゴリズム
第１１章 グラフィカルモデルの学習3 : 具体例
11.1 ボルツマンマシン
はじめに
ボルツマンマシン(Boltsman machine)とは、 2値ペアワイズモデルで、グラフ構造が完全グラフであるもの
確率分布関数は上式になる
xi∈{1, -1}
観測データx(1)<…,x(N)から、モデルのパラメータθ=(J,h)を決定する
対数尤度関数は上式となる
ẋih,ṁiはそれぞれ経験分布のxixi,xiの平均
11.1.1 平均場近似
平均ば近似を用いて、モデルのパラメータθ=(J,h)を求める
最小化問題の式
qi(xi)=(1+mixi)/2とおくと、qiはmi∈[-1,1]によってパラメータ付け可能
Mに関する最大化問題
f(h,m)の式
𝛏(x)=-xlogxとする
Hiの式
パラメータJ,hの式
11.1.2 ベーテ近似
ベテ近似における、データからパラメータを決める方法
式
Jに関する式
11.2 隠れマルコフモデル
はじめに
隠れマルコフモデルのパラメータを学習する方法
ガウス型の観測モデル(上式)を仮定
隠れ変数zごとに平均μz, 分散σzを持つ
観測xはガウス分布に従って得られる
隠れ状態はK個あるとする
Σzは対角行列であるとする
隠れ状態のz’からzへの繊維確率をrz’,zとおくと
学習すべきパラメータは全部でθ=(τ, μ, σ)となる
11.2.1 EMアルゴリズムによる学習
EMアルゴリズムを使った学習
観測のもとでの隠れ変数の確率分布p(z|x,θ)ん゛効率的に計算できるため
M-stepが改正的に計算できるため
Q関数の式
M-stepでパラメータθ=(τ, μ, σ)を最大化する
Τに関する式
μ,σに関する式
11.2.2 ベイジアン隠れマルコフモデル
パラメータθに対して事前確率分布を仮定する
遷移確率パラメータτには、ディリクレ分布
μ,σには正規分布、ガンマ分布を使う
これらの超パラメータをΦ=(u,𝛒,α,β)とする
変分下界の式
確率分布qに関する最適化がそのままでは解けない
隠れ状態に関する分布と、 各パラメータに関する分布の積に分ける
(構造つき)平均場近似
q(z)の最適化はE-step
q(θ)の最適化はM-step
変分下界の中で超パラメータΦに 関する項を取り出すと上式となる
変分下界を最大化するようにΦを定める
第１２章 MAP割り当ての計算1 : 最大伝搬法
12.1 MAP推定とは
確率モデルp(x|θ)に置いて、 そのMAP割り当て(maximum a posteriori assignment)とは
MAP割り当てを求めること
グラフィカルモデルの撮りうる状態xが グラフの頂点数に対して指数的にたくさんある
単純な全探索によりMAP割り当てを求めることは通常不可能
グラフィカルモデルの変数の一部が観測された状態でMAP推定を行う
式(12.1)の問題に帰着できる
MAP割り当てに「似て非なる」量(周辺確率の最大を集めたx’=(x’i)i∈V
注意
確率分布関数p(x)に対する、 周辺確率分布は上式で表される
最大周辺分布(max marginal distribution)
Zi=xiと固定した時の最大の確率を表す
MAP割り当てがただ一つである場合、 MAP割り当てx*は最大州へな分布のMAP割り当てにより得られる
グラフィカルモデルのすべての頂点iで 最大周辺分布が分かれば、MAP割り当てが計算できる
12.2 メッセージ伝搬によるMAP推定
12.2.1 直鎖型構造の場合の計算
グラフィカルモデルが木構造を持つのであれば、 周辺確率分布を詳細に計算した時と類似のアルゴリズムにより、 MAP割り当てを厳密に計算することができる
最も単純なケースとして、5つの頂点が直線状に並んだグラフを考える
x3の最大周辺分布の定義式は上式となる
式の変形を上式とする
メッセージ関数を上式と定義する
これらを使って上式とする
足し算とmaxの間に代数的な共通な性質がある
同等な足し算の性質
12.2.2 木のグラフ上での最大伝搬法
メッセージ伝搬による最大周辺分布の計算
最大伝搬法のアルゴリズム
確率分布が上式の時
定理:木型グラフの最大伝搬法
12.2.3 サイクルのある因子グラフ上の最大伝搬法
最大伝搬法は木でないグラフにも適用可能
12.3 TRW最大伝搬法
TRW最大伝搬法(TRW max-product algorithm)
アルゴリズム TRW 最大伝搬法
因子グラフ型モデルの仮定
定理 STA条件とMAP割り当て
第１３章 MAP割り当ての計算2 : 線形緩和による方法
13.1 MAP推定問題の整形計画法としての定式化
MAP推定を行うためのアルゴリズムの説明
離散状態のグラフィカルモデルに関してはMAP推定は線形計画方として定式化可能
線形計画法の双対として新たなメッセージ伝搬アルゴリズムを導出する
G=(V,F)上の離散状態の因子グラフを考える
因子関数は対数線形型とする
指数型分布族をε、変数xiの撮りうる値の集合をXiと書く
MAP推定問題間の式
右の式を最大化するxを探す
線形計画問題への書き換え
周辺確率凸多胞体(marginal polytope)を用いて
端点は上式の個数の状態に対応
T(x)={Tα(xα)}は、十分統計量を並べたベクトル
cl(S)は集合Sの閉包
定理:MAP推定問題の線形計画法による定式化
13.2 緩和問題
MAP推定問題を近似的に解くためのアイデア
難しい最適化問題の制約条件を ゆめるためた「簡単な」問題を使う
擬周辺確率凸多胞体𝕃の利用
周辺確率分布は必ず、局所的な整合条件を満たす
LとMの模式図
𝕃の端点のうち、𝕄の端点であるもの
𝕃の端点のうち、𝕄の端点でないもの
𝕃と𝕄の包含関係からの式
変数ε∈{0,1}のバイナリペアワイズモデルでの例
𝕄(G)の端点は0,1ベクトルになる
分数端点は1/2を含む
13.3 緩和問題の切除平面法による改良
はじめに
緩和問題の最適解が元の問題の最適解よりずれる原因
解決するために、 必要に応じて𝕃を定める不等式集合に、 不等式を追加する
アルゴリズム:切除平面法
ステップ2の「bを満たさない不等式からCを選ぶ」ことが困難
これを実行するアルゴリズム
13.3.1 サイクル不等式
2値ふだがモデルのケースでのサイクル不等式集合Cを考えた場合の、分離アルゴリズを検討
値x=(xi)に対して、辺ijがカットであるとは、xi≠xjであることをいう
サイクル上ではカットの個数は必ず偶数子になる
サイクルCとその部分集合S⊂Cで、 |S|が奇数個である時、上式が成り立つ
辺のそれぞれの期待値をとると上式となる
C,Sから定まる不等式
𝕃にすべてのサイクル不等式の集合を加えても𝕄には到達しない
Gが平面グラフの場合は一致する
13.3.2 分離アルゴリズム
サイクル不等式の中で必要なものを選択
最小重み経路問題を解く
少し省略
13.4 双対分解とメッセージ伝搬による解法
13.4.1 緩和問題の双対
Lによる緩和問題の解き方のもう一つのアプローチ
双対分解
新たなメッセージ伝搬アルゴリズム
分散計算に向いている
主問題の式
緩和問題の双対問題の式
凸最適化問題の強双対性により
周辺化の制約
J(δ)として上式とする
目的関数Jは、各i,αについて分離してmaxをとる形に分解
主問題と双対問題の関係について
定理:相補性条件
MAPの近似解x
13.4.2 MPLPアルゴリズム
最適化問題を、因子αSparkの{δαi}に関して座標降下法を行う
目的関数からαに関数部分のみ取り出す
右を最小化する
補題:最小化条件
MLPLアルゴリズム
13.4.3 関連アルゴリズム
タイトな制約のもとで、MLPLと同様なメッセージ伝搬でとく手法
第１４章 グラフィカルモデルの構造学習
14.1 構造学習(structure learning)とは
はじめに
グラフの形そのものを学習するタスク
前提条件
集合Vによって添字付けられた変数X = { Xi } i∈V
独立分布に従うN個のサンプルx(1),x(2),…,x(n)
上記のサンプルが従う確率分布がどのようなグラフ構造を持つ グラフィカルモデルに属するか決定する
マルコフ確率場の場合
各頂点を辺で結ぶ場合と結ばない場合を考えると上式のグラフの作り方がある
各頂点の結び方の組み合わせは膨大になり学習が困難になる
14.2 マルコフ確率場の学習
14.2.1 独立条件を用いる方法 (Independence-based approach, Constraint-based approach)
マルコフ条件が成り立っているのかどうかを検証
ペアワイズマルコフ条件
2つの頂点i,jの間に辺があるかどうか?の条件
具体的な方法
ピアソンの条件付き独立性
カイ2乗検定
Xv\{I,j}の取りうる値は|V|-2に関して指数的にたくさんある
計算するには大量のデータが必要
上式を満たすN(i)を求める手法
各頂点i ∈ Vに対して 近傍N(i)を求めて構造学習を行う
二つのフェーズで計算
前半のgrowフェーズで式を満たすようにむN(i)を大きくする
後半のshrinkフェーズで不必要なものをN(i)から除去する
得られた近傍を用いて、j ∈ N(i)のとき、iとjを辺で結ぶ
擬似コード
14.2.2 スパース正則性を用いる方法
ボルツマンマシン(2値ペアワイズモデル)
マルコフ確率場としてiとjが結ばれていること
上式を最適化することで、 得られる結合の係数{Jij}が疎になれば、 実質的に構造計算を行うことになる
右式は尤度に対してL1正則化を加えたもの
ボルツマンマシンのような完全グラフでは計算が難しい
辺のないグラフから出発して、 目的関数の値を大きくする辺を段々と追加していく手法によるアプローチ
ガウス型マルコフ確率場の場合も同様に L1正則化により構造化学習を行うことができる
Iとjが変で結ばれている
Jij≠0
共分散行列の逆行列がxixjの係数行列のJになる
最適化問題の式
14.3 ベイジアンネットワークの構造学習
14.3.1 条件付き独立性を用いる方法
ベイジアンネットの構造学習のアプローチ
データの条件付き独立性から有向非巡回グラフ構造を決める
条件付き独立性を用いるアルゴリズムの中で最も素朴なもの
有向非巡回グラフの頂点の接続構造と d分離性に関する上記の結果を基礎としている
頂点u,vが有向辺で結ばれているかどうかがd分離性により特徴づけられる
有向辺の向きもデータから求める
SGSアルゴリズム
頂点数|V|がかなり小さくないと計算できない
ロバスト性が低い
改良されたアルゴリズム
PC(Peter Spirtes and Clark Clymour)アルゴリズム
GS(Grow-Shrink)アルゴリズム
14.3.2 スコア関数を最大化する方法
各グラフ構造に対してデータの当てはまりの良さを表すスコアを定義し、 このスコアを最大にするグラフを探す
データDのもとでの有向非巡回グラフGのスコアの式
局所的なスコアの和の形になっている
対数尤度関数
探索する有向非巡回グラフを木に限って、 対数尤度を最大化するアルゴリズム
木幅を制限した範囲での探索手法
スコアの値を増やすように辺の追加や削除、向きの反転を行う手法
付録A 公式集
A 1 条件付き独立性の公式
A 2 半順序集合とメビウス関数
A 2.1 半順序集合の基本性質
A 2.2 メビウス関数
付録B 凸解析入門
B 1 定義
B 1.1 凸集合
B 1.2 凸関数
B 2 Fenchel双対
B 2.1 Fenchel双対の定義
B 2.2 Fenchel双対の性質
B 2.3 Fenchel双対の例
B 3 凸最適化問題の双対性
B 3.1 凸最適化問題
B 3.2 強双対性
B 3.3 KKTベクトルと最適性条件
付録C 指数型分布族
C 1 指数型分布族の定義
C 2 指数型分布族のパラメタ変換
C 2.1 指数型分布族のパラメタ変換の導出
C 2.2 例1 平均0の多次元ガウス分布
C 2.3 例2 有限集合の場合
参考文献
コメント
[…] 機械学習プロフェッショナルシリーズ – グラフィカルモデル 読書メモ […]