Ai Dictionary-part 2

確率分布モデルーーパターン認識 とベイズ推定 (人工知能辞典chapter14-2) song

outline • 単結合Bayesian Networkによる確率計算 (5) • 複結合Bayesian Networkによる確率計算 (7) • Bayesian Networkの学習(1) • 独立成分分析(3) • Neural Network アーキテクチャ(3) • 単純・多層Perceptron(2)

単結合Bayesian Networkによる確率計算 • Bayesian Networkの定義： – まずは非循環有向graph

p(X = x ,..., X = x ) = Π p( X = x | π( X ) = y ) 1

def

1

N s = 1

N

s

N

s

s

s

例： p( x1, x 2, x3, x 4, x 5) = p( x1)p( x 2)p( x 3 | x1, x 2)p( x 4 | x 2)p( x5 | x 3, x 4)

単結合Bayesian Networkによる確率計算 • Inference in BN – 観測可能な点Eの観測値(証拠と呼ぶ)eが与えられたとき に、確率変数の事後分布p(x|e)を計算する。 • 一般的に計算はNP困難

– 計算を可能化するにはモデルを簡単化する必要がある： 単結合BN。

単結合Bayesian Networkによる確率計算 • Belief propagation (Pearl 1988)

Kevin B. Korb etc. Bayesian Artificial Intelligence (figure 3.1 )

単結合Bayesian Networkによる確率計算 • Belief propagation (Pearl 1988)

単結合Bayesian Networkによる確率計算 • BPの実行 – 各点においては非同期的に値が収束される ので、受け取ったmessageを使って右辺の値を 計算し、左辺に代入することを繰り返せばよい – BPの計算量はグラフのサイズに比例する。

複結合Bayesian Networkによる確率計算 • Junction Tree アルゴリズム – 無向グラフでしたとき、loopが含めた場合においては普 通のBPは適用できないー＞Junction tree algorithm。

複結合 Bayesian Network による確 率計算 Junction Tree algorithm

複結合Bayesian Networkによる確率計算 • Junction Tree アルゴリズム – 注意点：グラフ変換した後に、無向グラフになるので、 そのままBPを使えない。 – 無向グラフにおいての確率計算ーポテンシャルを使っ て定義できる。Cliqueとは内部の任意二つ変数が結ん でいる。

ϕ( x ) = Π φ ( x ) = p( x | x , x )p( x | x , x ) 3

c

c

c

3

1

2

3

2

4

複結合Bayesian Networkによる確率計算 • Junction Tree アルゴリズム – gJ の各ノードについてポテンシャルを定義する。 – 任意のノードをRとして、Rをrootとして新しい gJ’を作る。 – gJ’の葉からRへmessage passingを行う。

複結合Bayesian Networkによる確率計算 • Junction Tree アルゴリズム – gJ’の葉から根Rへのmessage passingを行う

u0は葉で はない時：

ｖが葉の時：

m = Σ ϕ u v

def

v \ u

v

ϕ' = ϕ Π def

u0

u0

K i = 1

m

u0 ui

複結合Bayesian Networkによる確率計算 • Junction Tree アルゴリズム – gJ’の根Rから葉へのmessage passingを行う def • Rのポテンシャルをϕ' ' R = ϕRΠjL = 1 • ノードu0については、u0はuiへmessage

m = (Σ ui u0

def

ui \ u 0

変更する。

使って更新する。

ui u0

u0 ui

u0

ϕ' ' = m ϕ' ui

uj

ϕ' ' ) / m

を送り、u0とuiを結ぶ辺のポテンシャルを またuiはポテンシャル ϕ' ui から def

m

ui

m

u0 ui

から mu 0に更新する。 ui

複結合Bayesian Networkによる確率計算 • P(x1,x2,…,xN)の計算 – 最新のポテンシャル ϕ' はvの周辺分布pvと一致してい る。 v

– 辺eの最新ポテンシャルをmeとするとmeはeの周辺分 布peと一致している。 – さらに

Π p( x ,..., x ) = Π によって計算できる。

ν ∈ V(g' J)

1

N

e ∈ E(g' J)

p p

ν

e

複結合Bayesian Networkによる確率計算 • Junction Tree algorithmの欠点 – Treewidthを最大のcliqueのノードの数とする と： • Treewidthは大きな時junction tree algorithmが応用 できない • 最悪な場合、junction tree algorithmの計算量は treewidth のexponetial次元で増大する。 （PRML）

複結合Bayesian Networkによる確率計 算 • まとめ： – 有効グラフを無方向グラフに変換して(junction tree )ー＞Run BP • 計算量は非常に大きい

– 他の近似アルゴリズムが必要となる • Monte carlo methods( e.g. Gibbs sampling ) • Variational Inference(Mean-field) approach • Loopy BP

Bayesian Networkの学習 • 条件つき確率表CPT • MDL（minimum description length principle ）情報量基準（model selectionする時 に根拠となる判断基準、他にはAIC,BICなどがある） • 事前に親ノードになれる候補を制限するなど方法ーK2 アルゴリズム。 Wikipedia.org

(bayesian network)からの一つCPTに関する例：

P(R , S, G ) = P(R ) P(S | R ) P(G | S, R )

式(1)

G = Grass wet, S = Sprinkler, and R = Rain と標示すると

(1)

独立成分分析（ICA） • ICAは1980年代から研究された多変量解 析手法である。 • ICAはPCA, projection pursuit（射影追跡 法） ,factor analysisなどと関連が深い。 • 90年代後半に理論的な基礎が確立した手 法。

独立成分分析（ICA） • ICAの問題(定義) – 信号源はお互いに独立である(no-Gaussian)：

S( t ) = (S ( t ),..., S ( t )) 1

T

n

p(S( t )) = Π p(S ( t )) i

i

– 観測値と信号源の間では線形関係（Aはm*nの行列）

X( t ) = (X ( t ),..., X ( t )) X( t ) = AS( t ) 1

T

m

– n ≤ m ならばn*mの行列Wが存在する：

Y( t ) = WX( t ) により各成分が独立な信号を再構築できる。

独立成分分析（ICA） • ICAの解法 – 代表的なのはWを繰り返し演算によって更新し、収束したWtを分 離のための行列とするものである。

W

t + 1

= W + η(I − ϕ(Y )Y ) W T

t

t

Y = WX ϕ(Y ) = (ϕ( y ),..., ϕ( y )) t

1

T

n

ϕ(.)についてはtanhなどの非線形関数がよい。 • ICAの応用 –

– 音声信号の分離…

– http://visl.technion.ac.il/demos/bss/

Neural Network アーキテクチャ • ニューロンの情報処理方式、ニューロンの結合方式(結合の 仕方)、ニューロン(あるいは結合)の学習方式。以上の三つ をneural network アーキテクチャという。 • ニューロンの情報処理方式

y = f (Σ ω x ) j

i

i

From wikipedia

i

シグモイド型ニューロン。その以外球形基底関数(RBF),非単調 関数、高次元ニューロン、確率的に動作するニューロンモデ ル,etc。

Neural Network アーキテクチャ • ニューロンの結合形式： – 階層的network

Multilayer perceptron

ー相互結合型network

Hopfield net

Neural Network アーキテクチャ • Neural networkの学習(次の部分に詳しく説明す る) – Hebbian 学習則 – Error Back-propagation （主にMLPの学習）

• Neural networkのmodel selection – 異なるnetworkを比較するにはAIC,MDLのような情報 量基準やcross-validationなどの手法を用いることがで きる。 – 基本的にNeural networkはに非線形、そして係数が多 いため、学習が難しい点がある。

単純・多層Perceptron 単純perceptron:

I

z = f (η) = f (Σ a x + a ) i

i

0

i = 1

評価基準を望みの出力とnetworkの 出力との差の2乗和とする。 P

ε = Σ (u − z ) 2 emp

p = 1

p

2

p

これを最小にする結合重みを求め るには：最急降下法。そしてこれを Widrow-Hoff学習則ともいう。 P

a ⇐ a + α Σ (u − z ) x i

i

p = 1

αは学習係数という、常 に正である

p

p

pi

単純・多層Perceptron • Multilayer perceptron(中間層1層)

Error back-propagation アルゴリズム：

Reference • Wikipedia • Kevin B. KorbAnn, E. Nicholson : Bayesian Artificial Intelligence • PRML