Ai Dictionary-part 1

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

outline • • • • • •

確率分布モデル(8) 確率密度分布の推定(6) 隠れマルコフモデル（HMM）(10) マルコフ確率場（Markov Random Field）(4) 識別の理論と手法(4) パターン認識とベイズ推定(1)

確率分布モデル • 何で確率？ – 不完全性を扱いたい、強力な道具となる – Noiseに強い – 環境の複雑性を緩和、知識の部分性を補う

確率分布モデル • ベイズ定理 – その前に： • Product rule P ( X, Y ) = P ( X | Y ) P( Y ) • Sum rule P(X ) = ΣYP(X, Y ) • そして上の二つからベイズの定理が導く P( Y | X ) P( X ) P( Y | X ) P( X ) P(X | Y) = = P( Y ) ΣxP(Y | X) P(X ) • P(X)は事前分布、P(Y｜X)は尤度関数(分布じゃない)、 P(X|Y)は事後分布、分母の部分は単に事後分布を正規化 するため。

確率分布モデル • ベイズ推論 – ベイズ定理 – 事前分布 – Parameterの推定方法：MAPー 最大事後分布

• それと異なる手法 – Parameterの推定方法：MLEー最大尤度推定

確率分布モデル • いろいろな確率分布モデル – P(X)は無限次元の関数自由度を持つとき、扱いが難し いため、それでいろんな制限をする必要がある： • たとえばある有限次元のパラメタの関数によって定める分布 p(X; θ )。 • これに対して、パラメタを仮定せず、関数空間での確率分布を 考える場合をノンパラメトリックなモデルという。

確率分布モデル • いろいろな確率分布モデル – 一番よく使われるのは正規分布あるいはGaussianという。 – Gaussianを含め、二項分布（Binomial）、beta分布などは統一の指 数分布の形で書ける。（Exponential Familyという） – 確率変数間の関係 • IIDつまり相互独立 • Markov chain たとえばFirst order Markov過程つまり時系列の場合、 一つの変数は隣変数以外の変数と独立 • 二次元以上の構造関係については、bayesian networkやmarkov random fieldなどのモデルがある • 続いてはFirst order Markov過程例を紹介

確率分布モデル • 例 まず： p( x1, x 3 | x 2) =

p( x1, x ,2, x 3) p( x1)p( x 2 | x1)p( x 3 | x 2) = = p( x1 | x 2)p( x 3 | x 2) p( x 2) p ( x 2)

同様に：p( x 2, x 4 | x 3) = p( x 2 | x 3) p( x 4 | x 3) p( x1, x 2, x 3, x 4) p( x1, x 2, x 4 | x 3) = p( x 3) p( x1)p( x 2 | x1) p( x 3 | x 2) p( x 4 | x 3) p( x1 | x 2) p( x 3 | x 2)p( x 2) p( x 4 | x 3) = = p( x 3) p( x 3) p( x1, x 3 | x 2) p( x 2) p( x 4 | x 3) = = p( x1, x 2 | x 3)p( x 4 | x 3) p( x 3)

確率分布モデル • 潜在変数モデル – 潜在変数(latent variable)は観測できない変数のこと(Z) – 観測される変数(Y) – 潜在変数の周辺化より、P(Y)を計算できる。但しこのときZは分 かる場合。{Y,Z}は全部分かる場合：completeデータと呼ばれる。 もし{Y}だけ分かる場合、多くの場合はEM アルゴリズムを使っ て、parameter 推定を行う。

• Parameterについても事前確率を立って、ベイズ推定を行 うとき、この事前確率のParameterをhyperparameterと呼ぶ。

確率分布モデル • 確率モデルの応用 – データの構造は未知であるため、ある確率モデルを当て はめて、そしてこの確率関数をそれらのデータを使って parameterを推定する。 – データの構造が既知な場合、ベイズ推論を用いた予測： kalman filter… – 情報理論 • Gaussianは平均と分散が与えられたときentropy最大の分布。 H[ x ] = −ΣxP(X) log P(X) 2

確率密度分布の推定 • Parameter推定 – MLE推定は相対エントロピーを最小にする推定 • カルバックダイバージェンス(K-L divergence)(iff p=q ,KL=0 else KL>0 なぜかをwikipediaのGibbs‘ inequality 参照してください)

q(X) KL(q || p) = ∫ q (X) log dX p(X | θ)

• 潜在変数があるとき、EMアルゴリズムを使う

– MAP • 事前分布を持ち込む – 事前分布の選び方法：conjugate prior（計算の便利がある） or 無情 報事前分布(たとえば一様分布)

確率密度分布の推定 • 例外値や外れ値があると き、robustの推定が必要 – 分布をGaussianから他の robustな分布に変えるー student`s t 分布,logistic分 布ーheavy tails性 – 赤い線はstudent`s t分布、 緑はGaussian(Gaussian は 右のずれた値に影響され ていることがわかる)

確率密度分布の推定 • Bayesian predictive distribution（ベイズ事後予測 分布） – 式は p(X | x ) = ∫ p(X | θ)ζ(θ | x )dθ – 意味は ζ (θ | x ) はデータxからのparameter θ の推定で、 p(X | θ) はもとの確率モデルに基づいたもので、θ について積 分すると、元のデータセットxからXを確率分布を計算で きる。

確率密度分布の推定 • Nonparameter推定 – Histogram法ーある区 きりをとる – kernel密度推定 • K(u)は|u|<=1/2のとき1 else 0 • Histogram法と同じ不連 続であるため、 Gaussian kernelを使う 1 1 || X − Xi || 2 P(X) = Σi exp{− } 2 1/ 2 2 Nh (2πh ) 2h

Histogram法の結果

Gaussian kernelの結果

確率密度分布の推定 • Nonparameter推定 – Histogram やkernel density estimation法につ いてはXの次元の増加につれて、近似の精度 が著しい悪くなる。 • 前提はXの次元が小さい場合 • 多変量解析の手法によって低次元化(Dimension reduction )の前処理を行う(PCAとか)

確率密度分布の推定 • 局所尤度推定 1 x − xi L( x; θ( x )) = Σ K( ) log p( xi; θ( x )) Nh h i

– hが大きくなるとwindowの領域は大きくなるため、 parameter推定に近づき。

隠れマルコフモデル • Outline – HMMの定義 – Message passing アルゴリズム • Forward-backward アルゴリズム • Viterbiアルゴリズム

– Parameter estimationアルゴリズム • Baum-Welchアルゴリズム(EMのHMMへの実装)

隠れマルコフモデル • HMMの定義 – ｛A,B,I、F｝ – Notationについては：Pr(st=Sj|st-1=Si)=aij Pr(xt=x|st=Si)=bi(x) Pr(s0=Si)= π i

– 例： • 出力分布(B)は正規混合分布の時、混合正規分布型HMMという。 • どの状態からどの状態へも遷移ことができる周期的でないHMM をエルゴディックHMMと呼ぶ • 後戻りは無いとき、left-to-right HMM( aji=0 if i<j)

隠れマルコフモデル • 問題

^ = arg max Pr( x | ωi) Pr(ωi) ω ωi

– ω^ を計算するには、Miから観測データ列xが生成す る確率の計算が必要となる：forward-backword アル ゴリズム＋Baum-Welchアルゴリズム（EM） – Pr(x)を最大にする遷移系列を求める方法：Viterbi ア ルゴリズム

隠れマルコフモデル • Forward backward アルゴリズム – Forward部分 • t-1ときのSkー＞Sｊ全部の状態遷移図中の可能性があるとこ ろ、ｋについて和をとる必要がある。

α( t , j) = Σ α( t − 1, k )a b ( x ) k

kj

Pr(X | M ) = Σα(T, k ) k ∈ F

j

t

隠れマルコフモデル • Forward backward アルゴリズム – Backward 部分：forward部分と同じ考え

β( t , j) = Σ a b ( x )β( t + 1, k ) k

•

jk

k

t + 1

Pr( X | M ) = Σβ(0, k ) k

β(T, j) = 1 はFの状態においては右からのmessageが無いから1に なると考えているが、検証したい場合は式13に式3の結果 Sj ∈ F 利用すればよい。

隠れマルコフモデル • Viterbiアルゴリズム – Forward backwardアルゴリズムと似ている、変わると ころは和をとるところに状態遷移の中確率の最大値を 取るようにする。

α( t , j) = arg max α( t − 1, k )a b ( x ) kj

k

j

t

隠れマルコフモデル • Viterbiアルゴリズム – 自然言語処理の簡単な例（Ralph Grishman） • http://cs.nyu.edu/courses/spring06/G22.2590001/Viterbi.ppt

隠れマルコフモデル • Baum-Welchアルゴリズム（EM） α( t − 1, i)a b ( x )β( t , j) Pr(s = S , s = S | x , M ) = Pr( x | M ) α( t , i)β( t , i) Pr(s = S | x , M ) = Pr( x | M ) ij

t − 1

t

i

t

j

j

t

(12) (13)

i

実際では式13は式12を jについて和をとって、そ して βの定義式を代入 するだけである。

隠れマルコフモデル • Baum-Welchアルゴリズム（EM） α( t − 1, i)a b ( x )β( t , j) ξ( t , i, j) = Pr( x | M ) α( t , i)β( t , i) ψ ( t , i) = Pr( x | M ) ij

j

t

(12’)

(13’)

• 上の式を利用してaijの推定値を計算できる：

Σ ξ( t , i, j) E[a ] = Σ ψ ( t , i) T t = 1

ij

T − 1 t = 0

(14)

隠れマルコフモデル • Baum-Welchアルゴリズム（EM） – MLEでparameter推定するため使う、Forwardbackwardアルゴリズムの結果を利用する。 – 式15,16はbi(x)はGaussianの時のparameter推 定値（状態ことで、b(x)の分布は変わらないと 仮定している） – EMアルゴリズムと同じ繰り返し計算である。

マルコフ確率場 • 条件(local Markov property)： – 式（１）は(x,y)においての確率は隣のnodeにしか依存し ない

Pr{F = f | F x, y

x, y

Ω \ (x, y)

=f

}

Ω \ (x, y)

= Pr{F = fx, y | F = f x, y

x' , y'

x' , y'

, ( x ' , y' ) ∈ c }

– No directed acyclic graph（向きなし）

• 画像処理への応用 – 画像修復、segementationなど。

x, y

マルコフ確率場 1 1 Pr( F = f ) = exp(− αΣ((f − f D 2 x, y

(x, y) ∈ Ω

x + 1, y

) + (f − f 2

x, y

x, y + 1

) )) (2) 2

この式で書けるときはこのMRFは Gaussian Markov Random Field（GMRF）とも呼べる。 fx,y=fx+1,yの時expの部分はじめの 項が消える。 α が大きくなると、各ノードがその近傍の ノードの状態と同じ状態をとるほうが確率的に得する傾向が ある。つまり、全体が同じ状態を取りやすい。

マルコフ確率場 • 画像修復の例 – fx,y∈ (+1,-1),gx,y ∈(+1,-1) – まず全部fx,yをgx,yに設定、そして各nodeにおいて+1,-1 から選べ、下の確率を大きい方(式5)をとる。

Pr( F = f | G = g ) 1 1 = exp(− Σ(β(f − g ) + α(f − f Z 2 2

x, y

x, y

x, y

(x, y) ∈ Ω

E[f ] = arg max P (f ) x, y

x, y

fx , y

x, y

x + 1, y

(3)

) + α (f − f 2

x, y

x, y + 1

) )) 2

(5)

マルコフ確率場 • 欠点 – 計算量が大きい。近似計算アルゴリズムは必 要: • Loopy Belief propagation • Monte Carlo methods

識別の論理と手法 • Classification：クラスへの分類 • ベイズ識別方式 – 先験確率P(Cj) – 条件つき確率p(x|Cj) – リスクの式：

R[d ] = Σ ∫ r (d ( x ) | C )P(C | x )p( x )dx j

j

j

– このリスクを最小にする決定関数d(x)を求めることは 決定論理である(decision theory)。

(1)

識別の論理と手法 • ベイズ識別方式

R[d ] = Σ ∫ r (d ( x ) | C )P(C | x )p( x )dx j

– 0-1損失は： else 0

j

j

r (C | C ) = 1 − δ i

j

ij

(1)

δ は1 if i=j ij

– 一般的にはこのようなベイズ識別方式を使う：

x ∈ Ci, if _ P(Ci | x ) ≥ P(Cj | x ) _ for _ j = 1...K

(2)

– このときの最小誤識別率は：

P * = 1 − ∫ max P(C | x )p( x )dx e

j

j

(4)

識別の論理と手法 • 識別関数 – 識別関数 if _ g ( x ) > g ( x ) _ for∀j ≠ i, then _ x ∈ C i

j

i

(7)

– 各類Cjの標本xは以下の正規分布の場合 1 1 p( x | C ) = exp(− ( x − µ ) Σ ( x − µ )) ( 2ω) | Σ | 2 t

j

j

N

− 1 j

j

j

(9)

– そして共分散行列は同じの場合（2類） φ( x ) は線形識別 関数と呼ぶ。（対数形式をとっている） φ( x ) = g ( x ) − g ( x ) = (µ − µ ) Σ x − θ (12) P ( C 2) 1 θ = log + (µ Σ µ − µ Σ µ ) (13) P(C1) 2 t

1

2

1

t 1

− 1

2

− 1

1

t 2

− 1

2

識別の論理と手法 • ノンパラメトリックな手法 – K-NN法（Kは奇数の場合は多く）

• 入力パターンと最近傍（Euclid距離）のK個パターン中一番数 多いクラスへ配属。 • Ｋが大きくなるとベイズ識別に近づく。

– パターンマッチング法

• 各類の標準パターン（通常は類の平均）、単位化して、そして 未知パターンとの内積が大きなクラスへ配属する。

– 部分空間法

• パターンマッチング法の拡張 • 各類において、ｍ個の線形独立な代表パターンを使って部 分空間を作る。そこへ未知パターンを射影し、長さが最大の 類へ配属。

パターン認識とベイズ推定 • パターン認識の過程はまず特徴抽出。この段階 では次元を減らすなどを行う。そして識別過程。 • 類別ー教師なし学習 • 識別ー教師あり • 統計的学習は構文手法より安定。 • Bayesian Networks-graphical modelの一種。この 前のMRF、HMMともgraphical modelである。

Reference • 図形の多くはPRML(C.M.Bishop)から • PRML • Wikipedia