狠狠撸

PRML titech 8.1 - 8.2
榊原隆文 (@saka bar)
March 13, 2015
1 / 59

自己紹介 (前回とほぼ変化なし)
? 榊原隆文 (twitter:@saka bar さかばー)
? すずかけ台の奥村研に所属
? 専門は自然言語処理
? テキスト集合からの知識獲得
? 好きなもの
? 唐揚げ
? 凌駕
? Haskell
? IIDX DP
? 漢直 (漢字直接入力)
? 紹介スライド
http://www.slideshare.net/takafumisakakibara75/tutcode
2 / 59

このスライドの特徴 (前回とほぼ変化なし)
? スライド作成のために LATEX の Beamer パッケージを利用
? PowerPoint を使いたくない
? 前の発表の時に Beamer で痛い目見たけど、今回は大丈夫だろうか…
? git でバージョン管理
? このスライドはタグの v1.1 と対応
? ソースを github で公開
? https://github.com/sakabar/prml_titech_8-1_8-2
? PDF を狠狠撸Share で公開
? http:
//www.slideshare.net/takafumisakakibara75/slide-44207685
3 / 59

もくじ
..1 8.1 ベイジアンネットワーク
..2 8.1.1 例:多項式曲線フィッティング
..3 8.1.2 生成モデル
..4 8.1.3 離散変数
..5 8.1.4 線形ガウスモデル
..6 8.2 条件付き独立性
..7 8.2.1 3 つのグラフの例
..8 8.2.2 有向分離 (D 分離)
4 / 59

もくじ
..3 8.1.2 生成モデル
..4 8.1.3 離散変数
..7 8.2.1 3 つのグラフの例
..8 8.2.2 有向分離 (D 分離)
5 / 59

この章の気持ち
? 確率論は 2 つの単純な等式から成り立っている
? 加法定理
? 乗法定理
p(X) =
Y
p(X, Y)
p(X, Y) = p(Y|X)p(X)
? → どんなに複雑な確率的推論?学習方法も、これらによって分解す
ることができる
? そこでグラフィカルモデルですよ
..1 確率モデル構造を視覚化できるので、新しいモデルの設計方針を決め
るのに役立つ
..2 グラフの構造を調べることにより、条件付き独立性 (8.2 章) などのモ
デルの性質に関する知見が得られる
..3 学習や推論のための計算をグラフ上の操作として表現できる
6 / 59

ことば
? リンク
? ノード
? ベイジアンネットワーク (有向グラフィカルモデル)
a
b
c
? マルコフ確率場 (無向グラフィカルモデル)
A
C
B
7 / 59

ベイジアンネットワーク
? グラフィカルモデル: 広い確率分布のクラスをグラフで記述できる
p(a, b, c) = p(c|a, b)p(a, b)
= p(c|a, b)p(b|a)p(a)
? このような分解は、任意の同時分布に対して常に可能
? 左辺は a, b, c 対称だが、右辺は対称でないことに注意
a
b
c
8 / 59

K 変数の場合
p(x1, ..., xK) = p(xK|x1, ..., xK?1) . . . p(x2|x1)p(x1) (1)
? K の値を決めれば、この同時分布は K 個のノードを持つ有向グラフ
として表現される
? 各ノードは式 (1) の右辺の因子のうちの 1 つの条件付き分布に対応
? 各ノードは自分よりも小さい番号が振られたすべてのノードから向
かってくるリンクを持つ
? 全結合
? グラフはリンクが存在しないことを通して、分布のクラスに関する
情報を表現する
9 / 59

説明
p(x1)p(x2)p(x3)p(x4|x1, x2, x3)p(x5|x1, x3)p(x6|x4)p(x7|x4, x5)
x1
x2 x3
x4 x5
x6 x7
? ここでの有向グラフは有向閉路を持たないという制約を満たす (有向
非循環グラフ, DAG)
? 有向閉路を持たないことと、大きい番号を持つノードから小さい番
号を持つノードへのリンクが存在しないへのリンクが存在しないよ
うにノードを順序付けられることは等価
? (演習 8.2) → 次スライドで軽く説明
11 / 59

演習 8.2 解
? 問: 「有向グラフにおいて、すべてのノードについて、自分より小さ
い番号を持つノードに向かうリンクが存在しないようにノードを順
序を付けることができるなら、有向閉路は存在しない」ことを示せ
? 対偶をとると、「有向グラフにおいて有向閉路が存在するならば、あ
るのノードについて、自分より小さい番号を持つノードに向かうリ
ンクが存在するようにノードを順序を付けられている」
? 有向閉路に注目すると、初めのノードに戻ってくるときに「自分よ
り小さい番号を持つノードに向かうリンク」を通ることになる
12 / 59

もくじ
..3 8.1.2 生成モデル
..4 8.1.3 離散変数
..7 8.2.1 3 つのグラフの例
..8 8.2.2 有向分離 (D 分離)
13 / 59

8.1.1 例: 多項式曲線フィッティング
? 1.2.6 節で紹介したベイズ多項式回帰モデルをグラフィカルモデルで
表すと、図のようになる
w
t1 tN
? ここで、複数のノードをコンパクトに表現するために、
プレートを導入する
tn
N
w
14 / 59

決定的パラメータ?観測変数?潜在変数
? 確率的な変数と同様に、モデルのパラメータも陽に書いた方が便利
な場合もある
? 値が確定しているパラメータに関するノードは小さな塗りつぶされ
た円で表現する
? 機械学習やパターン認識問題では、多くの場合、確率変数のうちい
くつかを特定の観測値に対応させる。観測した確率変数は、グラフ
上では塗りつぶされた円で表現する
? 一方、観測されていないノードを潜在変数と呼ぶ
tn
xn
N
w
α
σ2
tn
xn
N
w
α
σ2
15 / 59

複雑な例
p(?t, t, w|?x, x, α, σ2
) =
?
???????
N
n=1
p(tn|xn, w, σ2
)
?
??????? p(w|α)p(?t|?x, w, σ2
)
tn
xn
N
w
α
t
σ2
x
? グラフィカルモデルと見くらべると、たしかに依存関係を簡潔に表
すことができている
? ただし、モデルの具体的な中身は、式を見ないとわからない
16 / 59

もくじ
..3 8.1.2 生成モデル
..4 8.1.3 離散変数
..7 8.2.1 3 つのグラフの例
..8 8.2.2 有向分離 (D 分離)
17 / 59

伝承サンプリング
? 与えられた確率分布に対して、それに従うサンプルを発生させたい
場合が多くある
? サンプリング法については 11 章
? ここでは、伝承サンプリングのみ紹介
? 伝承サンプリングとは、番号の最も小さいノードから順にサンプル
を発生させていき、最終的に同時分布 p(x) を求める方法である
18 / 59

生成モデル
? 確率モデルの実際のアプリケーションでは、通常グラフの末端ノー
ドに対応する大きい番号が振られた変数が観測値を表し、小さい番
号が振られたノードが潜在変数に対応する
? このようなモデルが観測データを発生する過程を表現していると解
釈することもできる
19 / 59

生成モデルの例: 物体認識問題
? この問題では、物体の像が各観測データ点に対応し、この観測デー
タから物体の種類を推論することが目的
? この問題では、例えば物体の位置?向きを隠れ変数とみなすことが
できる
? このグラフィカルモデルでは、全てのノードに関して確率分布が与
えられているため、「架空」のデータを発生させることができる。
? このようなモデルを生成モデルと呼ぶ
Image
Object OrientationPosition
20 / 59

もくじ
..3 8.1.2 生成モデル
..4 8.1.3 離散変数
..7 8.2.1 3 つのグラフの例
..8 8.2.2 有向分離 (D 分離)
21 / 59

8.1.3 と 8.1.4 の概要
? 指数型分布族 (2.4 節) は複雑な確率分布を構築するための基本構成
要素として利用される
? グラフィカルモデルは、これらの構成要素がどのように接続されて
いるかを表現するための便利な枠組みを提供する
? 有向グラフの親子対が共役関係 (同じような分布) になるように分布
を選べば、そのモデルは非常に良い性質を持つ
? 親ノードと子ノードが共に離散変数 (8.1.3)
? 親ノードと子ノードが共にガウス変数 (8.1.4)
22 / 59

離散変数
? K 状態離散変数 x を 1-of-K 表現を用いて表現する
? 確率分布 p(x|?) は
p(x|?) =
K
k=1
?xk
k
で与えられ、パラメータ ? = (?1, ..., ?K)T によって支配される
? 次に、2 つの K 状態離散変数 x1, x2 があるとし、これらの同時分布
をモデル化することを考える
p(x1, x2|?) =
K
k=1
K
l=1
?x1k x2l
kl
? この分布は K2 ? 1 個のパラメータに支配される
? 変数が 2 でなく M 個のときは、KM ? 1 個のパラメータ
? 指数オーダー orz
23 / 59

どうするのか?
? グラフに制約を加えることで、パラメータ数を減らす
? 独立の仮定→このスライド
? 連鎖表現
? パラメータ共有 (結合)
? パラメトリックモデルの利用
? 変数 x1, x2 が独立であると仮定すると、全パラメータ数は 2(K ? 1)
である
? この場合、x1 と x2 を結ぶリンクが除去されたことになる
? 一般に、M 個の独立な K 状態離散変数上の分布の場合、全パラメー
タ数は M(K ? 1)
? 線形オーダになった!
? ただし、この操作によって表現可能な分布のクラスは制限される
x1 x2
x1 x2
24 / 59

連鎖表現
? 全結合グラフと、リンクが全く無いグラフの中間的な結合度合いを
持つグラフは、全く一般的な同時分布よりは指定すべきパラメータ
数が少なく、また完全に因数分解可能なものよりは一般的な分布を
表現できる
x1 x2 xM
? パラメータ数は、
K ? 1 + (M ? 1)K(K ? 1)
K に対して 2 次的、連鎖の長さ M に関して (指数的ではなく) 線形に
増加
25 / 59

パラメータの共有 (結合)
x1 x2 xM
?1 ?2 ?M
? 図において、すべての条件付き分布 p(xi|xi?1) が同一のパラメータに
支配されると仮定すると、
x1 x2 xM
?1 ?
26 / 59

パラメトリックモデルの利用
y
x1 xM
? 親ノードの持つパラメータ数は M
? 条件付き分布 p(y = 1|x1, ..., xM) については、必要なパラメータ数は
2M
? 親変数の線形結合を入力とするロジスティックシグモイド関数を用
いれば、効率的に条件付き分布を記述できる
p(y = 1|x1, ..., xM) = σ
?
???????w0 +
M
i=1
wixi
?
??????? = σ(wT
x)
27 / 59

もくじ
..3 8.1.2 生成モデル
..4 8.1.3 離散変数
..7 8.2.1 3 つのグラフの例
..8 8.2.2 有向分離 (D 分離)
28 / 59

線形ガウスモデル
? この節では、要素変数上の線形ガウスモデルに対応する有向グラフ
によって、多変量ガウス分布を表現する方法を示す
? 対角共分散を持つガウス分布と一般のガウス分布とを両極端とする
ような興味ある構造を分布に持たせる
? 線形ガウスモデルの利用例
? 確率主成分分析
? 因子分析
? 線形動的システム
29 / 59

同時分布
? D 個の変数上の任意の有向非循環グラフを考える
? 線形ガウスモデルでは、分布の平均はノード i の親ノード pai 状態の
線形結合
p(xi|pai) = N
?
????????xi
j∈pai
wijxj + bi, vi
?
????????
? 同時分布の対数は、グラフに含まれるすべてのノード上の条件付き
分布の積の対数
ln p(x) =
D
i=1
ln p(xi|pai)
= ?
D
i=1
1
2vi
(xi ?
j∈pai
wijxj ? bi)2
+ const
? この式は x の成分に関する 2 次関数→同時分布 p(x) は多変量ガウス
分布
30 / 59

平均と分散
? この同時分布の平均と分散は再帰的に決められる
? 各変数 xi は以下のように書ける
xi =
j∈pai
wijxj + bi +
√
vi i
? この期待値を取ると
E[xi] =
j∈pai
wi jE[xj] + bi
? この式をグラフ上の最も小さいノードから順番に再帰的に計算する
ことで、E[[x]] = (E[x1], ..., E[xD])T の全成分の値が得られる
31 / 59

共分散
? 求めた E[xi] を利用する
xi =
j∈pai
wijxj + bi +
√
vi i
E[xi] =
j∈pai
wijE[xj] + bi
cov[xi, xj] = E[(xi ? E[xi])(xj ? E[xj])]
= E
?
????????(xi ? E[xi])
?
????
????k∈paj
wjk(xk ? E[xk]) +
√
vj j
?
????
????
?
????????
=
k∈paj
wjkcov[xi, xk] + Iijvj
32 / 59

もくじ
..3 8.1.2 生成モデル
..4 8.1.3 離散変数
..7 8.2.1 3 つのグラフの例
..8 8.2.2 有向分離 (D 分離)
33 / 59

条件付き独立性
? 3 変数 a, b, c に対し、b および c が与えられたとき、a の条件付き分
布が b の値に依存しないとする。すなわち、
p(a|b, c) = p(a|c)
? このとき、c が与えられた下で、a は b に対して条件付き独立である
? c で条件付けられた a および b の同時分布について考えると、条件付
き独立性は次のように表現される
p(a, b|c) = p(a|b, c)p(b|c)
= p(a|c)p(b|c)
34 / 59

注意
? 条件付き独立性の定義は、c がある特定の値をとったときだけでな
く、c の取り得るすべての可能な値に対して前述の式が成り立つこと
である
? 条件付き独立は次のように表すこともある
a b | c
? c が与えられたとき、a が b に対して条件付き独立
35 / 59

もくじ
..3 8.1.2 生成モデル
..4 8.1.3 離散変数
..7 8.2.1 3 つのグラフの例
..8 8.2.2 有向分離 (D 分離)
36 / 59

3 つのグラフの例
? 有向グラフの条件付き独立性を考えるため、ノードを 3 つだけ持つ
簡単な 3 種類のグラフについて考える
? tail-to-tail 型
c
a b
? head-to-tail 型
a c b
? head-to-head 型
c
a b
37 / 59

tail-to-tail 型
c
a b
? このグラフに対応する同時分布は以下の式で表される
p(a, b, c) = p(a|c)p(b|c)p(c)
? どの変数も観測されていないとすると、a と b が独立かどうかは両
辺を c に関して周辺化すれば調べられる
p(a, b) =
c
p(a|c)p(b|c)p(c)
? この式は一般には積 p(a)p(b) には分解できないので、
a / b | ?
38 / 59

tail-to-tail 型
c
a b
? 一方、変数 c で条件付けてみると、
p(a, b|c) =
p(a, b, c)
p(c)
= p(a|c)p(b|c)
これより、条件付き独立性
a b | c
が導出された
39 / 59

head-to-head 型
c
a b
? 最後に、第 3 の例について考える
p(a, b, c) = p(a)p(b)p(c|a, b)
c に関して周辺化すると、
p(a, b) =
c
p(a)p(b)p(c|a, b)
p(a)p(b)
を得る。よって先の 2 例とは異なり、どの変数も観測されていない
とき a と b とが独立であることがわかる。この結果を a b|? と書く
42 / 59

まとめ
? tail-to-tail または head-to-tail: 観測されていないときには経路を遮断
せず、観測されると遮断する
? head-to-head ノードは観測されていないとき経路を遮断し、その
ノードかあるいはその子孫のうち少なくとも 1 つが観測されたとき
経路の遮断が解かれる
44 / 59

弁明現象
G
B F
? 車の燃料タンクモデルを考える
? バッテリの状態 B{1,0}
? 燃料タンクの状態 F{1,0}
? 電動燃料計の状態 G {1,0}
? 何も観測していない時、p(F = 0) = 0.1
45 / 59

弁明現象
G
B F
? G が 0 であることを観測した後、p(F = 0|G = 0) 0.257
(確率が上がった)
46 / 59

弁明現象
G
B F
? G が 0 であることを観測した後、p(F = 0|G = 0) 0.257
? さらに、B が 0 であることを観測すると、
p(F = 0|G = 0, B = 0) 0.111
(確率が下がった)
? バッテリが切れているという事実が、燃料計が空を指していること
を「弁明」している
? 「燃料が切れている可能性は低い。なぜなら、すでにバッテリが切れ
ているということが電動燃料計がゼロになっていることの理由になっ
ているから」
47 / 59

もくじ
..3 8.1.2 生成モデル
..4 8.1.3 離散変数
..7 8.2.1 3 つのグラフの例
..8 8.2.2 有向分離 (D 分離)
48 / 59

有向分離
? グラフの有向分離
? A, B,C それぞれを重複しない任意のノード集合とする
? 条件付き独立性 A B | C を調べたい
? A に属する任意のノードから B に属する任意のノードへの全ての可
能な経路を考える必要がある
49 / 59

経路の遮断
? 以下の条件のうちいずれかを満たすノードを含む経路は遮断されて
いると言う
..1 集合 C に含まれるノードであって、経路に含まれる矢印がそこで
head-to-tail あるいは tail-to-tail である
..2 経路に含まれる矢印がそのノードで head-to-head であり、自身ある
いはそのすべての子孫のいずれも集合 C に含まれない
? すべての経路が遮断されていれば、A は C によって B から有向分離
されていると言い、グラフの全変数上の同時分布は A B | C を満
たす
50 / 59

例 1
f
e b
a
c
? 遮断する条件
? a から b への経路はノード f によって遮断されない
? f は tail-to-tail
? e によっても遮断されない
? head-to-head だが子孫 c が観測されている
? 以上より、条件付き独立性 a b | c はこのグラフからは導けない
51 / 59

例 2
f
e b
a
c
? a から b への経路はノード f によって遮断される
? ノード f は tail-to-tail であり、かつ観測されている
? 条件付き独立性 a b | f が成立
52 / 59

独立同分布データの場合
?
x1 xN
? 1 変量ガウス分布の平均事後分布を得る問題
p(?, x) = p(x|?)p(?)
? ? を条件付け変数と見なすと、任意の xi から xj i への経路が
tail-to-tail の観測済みノード ? によって遮断される
? ? が与えられた下で、観測値 D = (x1, ..., xN) は独立
p(D|?) =
N
n=1
p(xn|?)
53 / 59

独立同分布データの場合
?
x1 xN
? 次に、? を消去した場合には観測値は独立ではない
p(D) =
∞
∞
p(D|?)p(?)d?
N
n=1
p(xn|?)
? 遮断する条件
54 / 59

図 8.7 の例
tn
xn
N
w
α
t
σ2
x
? ?t から tn に対する任意の経路において、w は tail-to-tail であるため、
以下の条件付き独立性が成立
?t tn | W
? 一旦訓練データを利用して係数 w 上の事後分布を決めてしまえば、
訓練データ tn を捨ててしまってよい
55 / 59

ナイーブベイズモデル
z
x1 xD
? ナイーブベイズモデルのグラフ構造
? 観測変数 x = (x1, ..., xD)T
? クラスベクトル z = (z1, ..., zK)
? z を観測すると、xi と xj i との間の経路が遮断される (= 条件付き
独立)
.
ナイーブベイズ仮説
..
...... ? クラス z で条件付けると入力変数 x1, ..., xD が互いに独立
? z を観測せずに z について周辺化すると、xi から xj i への経路の遮
断が解かれる
56 / 59

有向分離定理
? 以下の 2 つの方法によって得られる分布の集合は等価
..1 同時分布の因数分解から得られる分布の集合
p(x) =
K
k=1
p(xk|pak)
..2 グラフの経路遮断を調べて得られる分布の集合
p(x) DF
57 / 59

マルコフブランケット
? D 個のノードを持つグラフで表現される同時分布と、変数 xi に対応
するノード上の、他ノード xj i で条件付けられた条件付き分布を考
える
p(xi|x{ j i}) =
p(x1, ..., xD)
p(x1, ..., xD)dxi
= k p(xk|pak)
k p(xk|pak)dxi
? 関数として xi に依存しない任意の因子 p(xk|pak) は xi に関する積分
の外に出てキャンセル
? 残るのは…
? ノード xi 自身の条件付き分布 p(xi|pai) : ノード xi の親に依存
? xi を親に持つノード xk の条件付き分布 p(xk|pak) : ノード xi の子とそ
の共同親に依存
58 / 59

マルコフブランケット
? 次の図のような、あるノードの親、子、および共同親からなるノー
ド集合をマルコフブランケットと呼ぶ
? ノード xi のマルコフブランケットは、xi を残りのグラフから孤立さ
せるためのノードの最小集合
xi
59 / 59

狠狠撸

PRML_titech 8.1 - 8.2

Recommended

More Related Content

What's hot (19)

Similar to PRML_titech 8.1 - 8.2 (20)

PRML_titech 8.1 - 8.2