隠れマルコフモデル

隠れマルコフモデルではznは一対K符号化を用いると便利であり、その遷移確率はAjk≡p(znk= 1|zn−1,j=1)によってあらわされる。すなわち

p(zn|zn−1,A)=

∏K k=1

∏K j=1

A^z_jk^n−1,jznk (13.7)

が成り立つ。最初のノードは確率のベクトルπで表される周辺分布 p(z1|π)=

∏K k=1

π^z_k^1k (13.8)

を持つ。また、znが与えられた場合のxnの分布を支配するパラメータをϕとする。具体的には p(x_n|z_n,ϕ)=

∏K k=1

p(x_n|ϕ_k)^znk (13.9)

とあらわされる。

均一なモデルとはAおよびϕがnに依存しないモデルのことであり、

p(X,Z|θ)=p(z1|π)





∏N n=2

p(zn|zn−1,A)





∏N m=1

p(xm|zm,ϕ) (13.10)

と書くことができる。ここでθ={π,A,ϕ}はモデルを支配するパラメータである。

また、Aのk≤ jとなるAjkの成分をゼロとして得られるモデルをleft-to-rightHMMという。

13.2.1 HMM の最尤推定

データ集合X ={x₁,· · ·,x_N}が観測された場合のHMMのパラメータを最尤推定で決定するこ とを考える。そのためにEM法を用いることにする。この場合

Q(θ,θ^old) = ∑

Z

p(Z|X,θ^old) ln p(X,Z|θ)

= ∑

Z

p(Z|X,θ^old)



ln p(z1|π)+

∑N n=2

ln p(zn|zn−1,A)+

∑N n=1

ln p(xn|zn,ϕ)



 (13.11) となるが、

γ(zn) = p(zn|X,θ^old)

ξ(zn−1,zn) = p(zn−1,zn|X,θ^old) (13.12) と表記し、さらに

γ(z_nk) = p(z_nk=1|X,θ^old)

ξ(z_n−1,j,z_nk) = p(z_n−1,j=z_nk=1|X,θ^old) (13.13)

と書くことにすると、

Q(θ,θ^old) =

∑K k=1

γ(z1k) lnπk+

∑N n=2

∑K j=1

∑K k=1

ξ(zn−1,j,znk) ln Ajk

+

∑N n=1

∑K k=1

γ(z_nk) ln p(x_n|ϕ_k) (13.14)

を得る。Mステップではγ(z_n)とξ(z_n−1,z_n)を定数とみなし、パラメータθ={π,A,ϕ}に関して Q(θ,θ^old)を最大化するが、これはラグランジュ未定乗数法を使って

πk = γ(z1k)

∑K j=1γ(z1 j) A_jk =

∑N

n=2ξ(z_n−1,jz_nk)

∑K l=1

∑N

n=2ξ(zn−1,jznl) (13.15) を得る。

13.2.2 フォワードバックワードアルゴリズム

次にEMアルゴリズムのＥステップに対応するγ(znk)とξ(zn−1,j,znk)を求める方法について検討 する。そのために、条件付き独立性を以下に書き下すと

p(X|z_n) = p(x₁,· · · ,x_n|z_n)p(x_n+1,· · ·,x_N|z_n) p(x₁,· · ·,x_n−1|x_n,z_n) = p(x₁,· · · ,x_n−1|z_n)

p(x₁,· · ·,x_n−1|z_n−1,z_n) = p(x₁,· · · ,x_n−1|z_n−1) p(x_n+1,· · ·,x_N|z_nz_n+1) = p(z_n+1,· · ·,x_N|z_n+1) p(xn+2,· · ·,xN|zn+1xn+1) = p(zn+2,· · ·,xN|zn+1)

p(X|zn−1xn) = p(x1,· · · ,xn−1|zn−1)p(xn|zn)p(xn+1,· · ·,xN|zn) p(xN+1|X,zN+1 = p(xN+1|zN+1)

p(zN+1|zN,X) = p(zN+1|zN) (13.16)

となる。そしてγ(zn)については、ベイズの定理と条件付き独立性より γ(zn) = p(zn|X)= p(X|zn)p(zn)

p(X)

= p(x₁,· · · ,x_n,z_n)p(x_n+1,· · ·,x_N)

p(X) = α(z_n)β(z_n)

p(X) (13.17)

を得る。ただし

α(z_n)≡p(x₁,· · · ,x_n,z_n)

β(zn)≡p(xn+1,· · ·,xN|zn) (13.18)

である。そして、α, βは再帰的に求めることができて、

α(z_n) = p(x₁,· · · ,x_n,z_n)

= p(x₁,· · · ,x_n|z_n)p(z_n)

= p(x_n|z_n)p(x₁,· · ·,x_n−1|z_n)p(z_n)

= p(x_n|z_n)∑

z_n−1

p(x₁,· · ·,x_n−1,z_n−1,z_n)

= p(xn|zn)∑

z_n−1

p(x1,· · ·,xn−1,zn|zn−1)p(zn−1)

= p(xn|zn)∑

z_n−1

p(x1,· · ·,xn−1|zn−1)p(zn|zn−1)p(zn−1)

= p(xn|zn)∑

z_n−1

p(x1,· · ·,xn−1,zn−1)p(zn|zn−1)

= p(xn|zn)∑

z_n−1

α(zn−1)p(zn|zn−1) (13.19)

この初期条件は

α(z₁)=p(x₁,z₁)=p(z₁)p(x₁|z₁)=

∏K k=1

{πkp(x₁|ϕ_k)}^z1k (13.20) で与えられる。

同様にβ(zn)についても

β(z_n) = p(x_n+1,· · ·,x_N|z_n)

= ∑

z_n+1

p(x_n+1,· · ·,x_N,z_n+1|z_n)

= ∑

z_n+1

p(x_n+1,· · ·,x_N|z_n,z_n+1)p(z_n+1|z_n)

= ∑

z_n+1

p(x_n+1,· · ·,x_N|z_n+1)p(z_n+1|z_n)

= ∑

z_n+1

p(xn+1,· · ·,xN|zn+1)p(xn+1|zn+1)p(zn+1|zn)

= ∑

z_n+1

β(zn+1)p(xn+1|zn+1)p(zn+1|zn) (13.21) を得る。初期値については本文(13.33)においてn=Nとおき、αの定義で置き換えると、

p(zN|X)= p(X,zN)β(zN)

p(X) (13.22)

となることからβ(z_N)=1とすればよいことがわかる。

また本文(13..33)の両辺においてznについて和を取ると

p(X) = ∑

z_n

α(z_n)β(z_n)

= ∑

z_N

α(z_N) (13.23)

を得る。

次にξ(z_n−1,z_n)については

ξ(z_n−1,z_n) = p(z_n−1,z|X)

= p(X|z_n−1,z_n)p(z_n−1,z_n) p(X)

= p(x,· · ·,x_n−1|z_n−1)p(x_n|z_n)p(x_n+1,· · ·,x_N|z_n)p(z_n|z_n−1)p(z_n−1) p(X)

= α(zn−1p(xn|zn)p(zn|zn−1)β(zn)

p(X) (13.24)

を得る。

最後に予測分布については

p(x_N+1|X) = ∑

z_N+1

p(x_N+1,z_N+1|X)

= ∑

z_N+1

p(x_N+1|z_N+1)p(z_N+1|X)

= ∑

z_N+1

p(x_N+1|z_N+1)∑

z_N

p(z_N+1,z_N|X)

= ∑

z_N+1

p(x_N+1|z_N+1)∑

z_N

p(z_N+1|z_N)p(z_N|X)

= ∑

z_N+1

p(x_N+1|z_N+1)∑

z_N

p(z_N+1|z_N)p(z_N,X) p(X)

= 1 p(X)

∑

z_N+1

p(x_N+1|z_N+1)∑

z_N

p(z_N+1|z_N)α(z_N) (13.25)

13.2.3 HMM の積和アルゴリズム

省略

13.2.4 スケーリング係数

実際にフォワードバックワードアルゴリズムを利用する場合、値が指数関数的に小さくなってし まう場合がある。そこでα(z_n)の規格化された表式

αˆ(z_n)=p(z_n|x₁,· · ·,x_n)= α(zn)

p(x₁,· · ·,x_n) (13.26)

を導入する。さらに

cn=p(xn|x1,· · ·,xn−1) (13.27) を定義すると、乗法定理により

p(x₁,· · · ,x_n)=

∏n m=1

c_m (13.28)

を得る。これより

α(z_n)=p(z_n|x₁,· · ·,x_n)p(x₁,· · ·,x_n)=





∏n m=1

cm



αˆ(z_n) (13.29)

が得られるため、αの再帰式に代入することで cnαˆ(zn)=p(xn|zn)∑

z_n−1

αˆ(zn−1)p(zn|zn−1) (13.30) を得る。同様にしてβについても

βˆ(zn)= β(zn)

∏N m=n+1cm

= p(xn+1,· · ·,xN|zn)

p(xn+1,· · ·,xN|x1,· · ·,xn) (13.31) と定義すると再帰式は

cn+1βˆ(zn)=∑

z_n+1

βˆ(zn+1)p(xn+1|zn+1)p(zn+1|zn) (13.32) となり、尤度関数と周辺確率は

p(X) =

∏N n=1

c_n γ(zn) = αˆ(zn) ˆβ(zn)

ξ(zn−1,zn) = (cn)⁻¹αˆ(zn−1)p(xn|zn)p(zn|zn−1) ˆβ(zn) (13.33) となる。

13.2.5 Viterbi アルゴリズム

ここでは観測データ{x₁,· · ·,x_N}が与えられた場合に、最も確からしいz_nの系列を求めること を考える。そこで

w(zn)= max

z1,···,z_n−1ln p(x1,· · ·,xn,z1,· · ·,zn) (13.34) と定義すると

w(z_n+1) = max

z1,···,zn

ln p(x₁,· · · ,x_n+1,z₁,· · ·,z_n+1)

= max

z₁,···,z_n

[ln p(x1,· · · ,xn,z1,· · ·,zn)+ln p(zn+1|zn)+ln p(xn+1|zn+1)]

= ln p(x_n+1|z_n+1)+max

z_n {ln p(z_n+1|z_n)+w(z_n)} (13.35) を得る。また、

w(z₁)=ln p(z₁)+ln p(x₁|z₁) (13.36) であるため、n=1から順番に求めていけば最終的に求めたい量である

maxz_n w(z_n)=max

Z p(X,Z) (13.37)

を求めることが可能になる。

13.2.6 隠れマルコフモデルの拡張

省略

ドキュメント内 PRML pdf PRML ( N x t y(x, w) = w 0 + w 1 x + w 2 x w M x m = M w j x j (1.1) j=0 E(w) = 1 {y(x n, w) t n } 2 (ページ 99-104)