MIT OCW, Machine Learning 16日目

Rohit Singh, Tommi Jaakkola, and Ali Mohammad. 6.867 Machine Learning. Fall 2006. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

• • Bayesian networks
    • Marginal independence and induced dependence
      • Explaining away
      • Bayesian networks and conditional independence
      • Graph and the probability distribution

Bayesian networks

Bayesian networkは確率的な情報を表現し,使うのに有用なモデルである. Bayesian networkは1. 有向グラフと,2. それに付随する確率分布からなる. グラフは確率変数たちの質的な関係(条件付き独立性)を表現し,確率分布は確率変数たちの量的な関係を記述する. HMMでforward-backward algorithmが効率的であったのはMarkov性ゆえであり,これをBayesian networkの場合にも一般化するため,確率変数同士の独立性,条件付き独立性,従属性を明確に記述するグラフは非常に重要である.
まずは単純なBayesian networkを挙げる(fig.1). 確率変数$x_1, x_2$は独立なコイントスの結果で,$0, 1$のどちらかの値を取る. また$x_3=\delta(x_1,x_2), \text{ Kronecker's delta}$で確率変数$x_3$を定義する. 状況設定から同時分布は
$$P(x_1, x_2, x_3) = P(x_1)P(x_2)P(x_3|x_1,x_2)\ \ \ \ (1)$$
とわかるが,同じ分布をfig.1のグラフだけから導ける. その前にいくつかの用語を定義する.
$x_1$から$x_3$への辺が有るから,$x_1$は$x_3$のparent(親)であり,$x_3$は$x_1$のchild(子)であるという. $x_2$もまた$x_3$の親であり,このとき$x_3$は$x_1$と$x_2$に従属する. グラフに合致した同時確率分布は必ず,それぞれの確率変数の親たちによって条件付けられた条件付き確立の積として書ける. よって(1)はfig.1のグラフと合致している.

Marginal independence and induced dependence

$$\begin{aligned} P(x_1, x_2) &= \sum_{x_3}P(x_1,x_2,x_3)=\sum_{x_3}P(x_1)P(x_2)P(x_3|x_1,x_2)\\ &=P(x_1)P(x_2)\sum_{x_3}P(x_3|x_1,x_2)=P(x_1)P(x_2) \end{aligned}$$
このように,他の確率変数を無視すると周辺分布が独立になるとき,marginary independentであるという. これはグラフからも見て取れる.

確率変数のもう一つの典型的な関係はinduced dependenceである. $x_1, x_2$の現れを与えられず,$x_3$の現れのみを与えられた場合を考える.$x_3=1$ならば$x_1=x_2=1$か$x_1=x_2=0$のどちらかに決まり,$x_3=0$ならば$x_2 = 1-x_1$に決まるから,$x_1$が決まれば$x_2$が決まるし,$x_2$が決まれば$x_1$が決まる. すなわち$x_3$が決定されると$x_1,x_2$はdependentな関係になる. これは後で述べる方法によってグラフから見て取れる.

marginal independence とinduced dependenceは現実のモデルでよく現れる.　fig.2cのfactorial Hidden Markov Modelはその例である. このモデルでは2つの周辺独立なMarkov chainが観測値を作り出している. 換言すれば,2つのMarkov chainが観測値によってのみ結び付けられているということである(induced dependence). このモデルからサンプリングするには,2つのMarkov modelから独立にサンプリングを行い,各時点において2つのstateから観測値をサンプリングする. fig.2cの同時分布は
$$P(x_1')P(x_1)P(y_1|x_1',x_1)P(x_2'|x_1')P(x_1|x_1)P(y_2|x_2,x_2')P(x_3'|x_2')P(x_3|x_2)P(y_3|x_3,x_3')$$
とfactorizationできる. このモデルは例えば二人が話しているのを1つのマイクで録音し,それぞれの人が何を話したか推測したり,2つのハプロタイプから生成された表現型からもとのハプロタイプを推測するのに利用できる.

Explaining away

また,Bayesian networkでうまく把握できる確立モデルにexplaning awayがある.Pearl, 1988による,強盗警報機の鳴る原因のモデル(fig.3)を例に見る. 4つの二値(0, 1)確率変数$A, B, E, R$があって,
$A$は警報機,$B$,$E$は地震,$R$はラジオで地震情報がなされていることを代表している.
$P(E=1)=P(B=1) \sim 0,P(A=1|E,B) \sim (E \lor B),P(R=1|E=1)\sim 1, P(R=1|E=0)=0$
を仮定する. fig.3で影のついた確率変数の情報のみを持っているとする.
$A=1$のみが解っているときを考える(fig.3.b).$E=1$か$B=1$の少なくとも一方が成立しているとわかるが,$E,B$ともに滅多に生じない事象だから,$B=E=1$は必ず起きないと仮定する. この仮定のもとで$R=1$の情報を得たら$E=1,B=0$を確信し,$B=1$を排除(explain away)できる. したがって
$$P(E=1|A=1,R=1) \sim 1, \ \ P(B=1|A=1,R=1)\sim 0$$
である. ここで$R,B$は$A=1$のもとで条件付き従属であることを使った.これもまたグラフから見て取れる性質である.

Bayesian networks and conditional independence

グラフはもともと変数の独立性をencodeしているから,その独立性をextractするための基準が必要である. Bayesian networkの場合,この基準をD-separtation criterionという.

例えば先程のモデルを拡張したfig.4aを考える.ここで$L$は,警報がなったので帰宅したという事象を代表する変数である. $R,B$は$A$のもとで独立か否かと言った問いに答えるための手順を考える.
1. 対象の変数のancestral graphを構成する. ここでは対象とは$R,B,A$であって,ancestral graphはこれらとともに,これらの変数に至る有向辺を何ステップでも辿って現れる変数全てを含む. 今の場合,ancestral graphはfig.4bである.
2. 得られたancestral graphにおいて,子ノードを共有するノード間に無向辺を加える. 3つ以上のノードが子ノードを共有する場合には,それらのつくる全てのペアについて辺を加える(fig.4c).これをmoralizeという.
3. 全ての有向辺を無向辺に置き換え,無向グラフ(fig.4d)を得る.

結果得られた無向グラフから,もとの問の答えを読み取れる. 得られた無向グラフから$A$とそれに結ばれた辺を取り去ったとき,$R$と$B$を結ぶpathが存在しなければ$R,B$は$A$によって条件付き独立であり,存在すれば条件付き独立であると言える. したがってfig.4dから,$R,B$は$A$によって条件付き従属である.

fig.1に立ち返り,D-separated criterionを使うと,fig.5によって$x_1,x_2$がmarginally independentであることが見て取れるし,fig.6から$x_1,x_2$が$x_3$によって条件付従属であることが見て取れる.

Graph and the probability distribution

以上の議論は,グラフとそれに対応付けられる確率分布がconsistentであるときにのみ成立する. consistentとは,グラフから見て取れる全ての(条件付き含む)独立性が,確率分布の上でも言えるということである. グラフから見て取れる独立性というのは数多く存在する.
$d$個のノードをもつ循環しないグラフ$G$が与えられたとき,
$$P(x_1,...,x_d)=\prod_{i=1}^d P(x_i| x_{{pa}_i})$$
はそのグラフとconsistentであることが知られている.ただし$pa_i$は$x_i$の親ノードの集合である.

MIT OCW, Machine Learning 15日目

Rohit Singh, Tommi Jaakkola, and Ali Mohammad. 6.867 Machine Learning. Fall 2006. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.
Lecture 19, 20.

• • Markov chains(cont’d)
    • State prediction
    • Estimation
  • Hidden Markov Models
    • Probability model
  • Three problems to solve
    • Problem 1.
    • Problem 2. most likely hidden state sequence (Viterbi)
      • Example
    • Problem 3: estimation
      • Multiple (partial) alignment

$q$は初期分布，$k$はstateの数とする.またMarkov chainの初期のstateは$X_1$である.

Markov chains(cont’d)

Markov chainを記述する方法には2つある． state transition diagramとgraphical modelである. transition diagramはstateたちをノードとし，遷移確率が0でないstateをつないだ有向グラフであって,例えばfig.1のようである． また，初期分布を,特別に設定したnull stateからの遷移とみてグラフに書き込むことも出来る.
graphical modelでは対照的に，確率変数たちの独立/従属関係に着目する. ある時刻におけるstate $X_t$は確率変数であって，$X_{t-1}$と独立でないことがMarkov chainの定義から言える. ある頂点(state)がほかのある頂点(state)に従属しているときに有向辺によってその従属関係を示して，graphical modelを構成する．つまり,
$X_{t-1} \rightarrow X_t \Leftrightarrow$ $X_t$は$_{t-1}$に従属する
という規則をグラフ化する. fig.2 がその例である.

State prediction

$$P(X_{t+m} = j|X_t = i) = [P^m]_{ij}$$
から，任意の$n$に
$$P(X_n = j) = \sum_{i=1}^k q(i) P(X_n = j| X_1 = i) = \sum_{i=1}^k q(i) [P^{n-1}]_{ij}$$
が成立する. $q^T P^{n-1}$は$j$番目の要素が$P(X_n=j)$であるような横ベクトルであって，
$$\alpha_t^T = q^T \underline{PP\cdots PP}_{t-1 \text{ times}}$$
と書くことにすると,
$$\begin{aligned} q^T &= \alpha_1^T \\ \alpha^T_{t-1}P &= \alpha_t^T, t>1 \\ \sum_{i=1}^k \alpha_{t-1}(i) P_{ij} &=\alpha_t (j) \end{aligned}$$
が成立する.

Estimation

sample pathの観測からMakov chainのtransition matrixを推測することが出来る.
$\{X_t\}$の現れ(sample path)の$x_1,....,x_n$が与えられたとき，そのlog-likelihoodは,
$\hat{n}(i,j)$を$x_1,...,x_n$においてみられた$i$から$j$への推移の回数とすると,
$$\begin{aligned} \log P(x_1,..,x_n) &= \log \left[ P(X_1 = x_1) \prod_{t=1}^{n-1}P(X_{t+1}=x_{t+1}|X_t=x_t) \right] \\ &= \log q(x_1)+\sum_{t=1}^{n-1} \log P_{x_t, x_{t+1}} \\ &= \log q(x_1) + \sum_{i,j} \hat{n}(i,j)\log P_{ij} \end{aligned}$$
であって，$\sum_j P_{ij} = 1$を考えれば，transition matrix $P$の最尤推定は
$$\hat{P}_{ij} = \frac{\hat{n}(i,j)}{\sum_{j'} \hat{n}(i, j')}$$
である. しかし，初期分布$q$を推測するには多くのsample path が必要不可欠である.

Hidden Markov Models

Hidden Markov Models (HMMs)は,観測している値が，直接観測されないMarkov chainが更に確率的に生成しているものであると仮定したモデルである. HMMモデルは広く利用され，例えば，あとで発話をphoneme(音素)のMarkov chainでHMM化し，また，アミノ基の列であるタンパク質をモデル化するのに，タンパク質分子をその構造的特徴のMarkov chainによってHMM化する．
HMMはMarkov chainとmixture modelによって理解できる. fig.3の単純な例を議論する. 時刻は$t=1,2,3,4$の４つだけで，fig.3.aは何度かの観測によって得られた値$y_1,..,y_4$の複数のプロットである． 一旦時刻の情報を捨て去って，$y$の値だけを基準にクラスタリングすると，two component mixture
$$P(y) = \sum_{j=1}^2 P(j) P(y|j)$$
でうまくモデル化出来る. 例えば$P(y|j)\sim N(y; \mu_j, \sigma_j^2)$などとできる. このmixture modelから(まだ時刻を無視しつつ)各時刻でsampleを生成すると，fig.3.bの楕円の中に収まるようになる． このとき，各時刻における観測値のサンプル$y_t$は,選ばれたコンポーネント$x_t$からのみ生成される(fig.4).
各時刻で正しい方の楕円でのみsampleを生成させるためにMarkov chainを使う． Markov chainによって正しい方のcomponentを選ぶようにするのである. すなわち，$t=2$でのcomponentを,$t=1$で選んだcomponentによって選ぶ(fig.5).

Probability model

HMMをgraphical modelで書くことによって，全ての確率変数に対する同時確率を簡単に書き下せる. グラフはどの変数がどの変数に依存しているかを明確にし，どの条件付き確率が同時確率のfactorであるかがわかる． fig.5では，
$$\begin{aligned} P(x_1,...,x_n,y_1,..,y_n) &= P(x_1)P(y_1|x_1)P(x_2|x_1)P(y_2|x_2)\cdots \\&=P(x_1)P(y_1|x_1)\prod_{t=1}^{n-1}[P(x_{t+1}|{x_t)P(y_{t+1}|x_{t+1})]} \\ &= q(x_1)P(y_1|x_1) \prod_{t=1}^{n-1} [P_{x_t, x_{t+1}} P(y_{t+1}|x_{t+1})]\end{aligned}$$
である.

Three problems to solve

1. 観測値の確率を評価する
   $$P(y_1,...,y_n) = \sum_{x_1,...,x_n} P(x_1,...,x_n,y_1,..,y_n)$$
2. 観測値$\{y_i\}$が与えられたとき，最もありそうな隠れたMarkov path $\{x_i^*\}$を推測する.
   $$\{x_1^*, ..., x_n^*\} = \arg \max_{x_1,...,x_n} P(x_1,..,x_n,y_1,..,y_n)$$
3. 時系列に沿った観測値の集合の集合 $\{\{y^{(l)}_i\}_{i=1}^{n_l}\}_{l=1}^L$から,モデルのパラメータを推測する．

Problem 1.

$\alpha_t(j) = P(y_1,...,y_t, X_t=j) ,\beta_t(i) = P(y_{t+1},...,t_n|X_t=i)$として，
$\alpha_t$を$t=1,2,...$と計算していくアルゴリズム(forward algorithm)と,$\beta_t$を$t=n, n-1, ...$と計算していくアルゴリズム(backward algorithm)があり，どちらか一方だけでも計算できるのだが，計算ステップ($t$)が多くなるほど計算量が幾何級数的に増大するので，前後から挟み撃ちして効率的に計算する．
以下はforward algorithmの導出だが，backwardの場合も殆ど同様である.

$$D_y = diag(P(y|1), ..., P(y|k))$$
によって
$$q^T D_{y_1} \mathbf{1} = \sum_{i=1}^k q(i) P(y_1|i)=P(y_1)$$
などと計算できる. 同様に
$$q^T D_{y_1} P D_{y_2} \mathbf{1} = \sum_{i=1}^k \left[q(i)P(y_1|i) \sum_{j=1}^k P_{ij} P(y_2|j)\right] = P(y_1,y_2)$$
これを繰り返して，
$$q^TD_{y_1}PD_{y_2}P \cdots PD_{y_n} \mathbf{1} = P(y_1,...,y_n)$$
が得られる. $\alpha_t(j) = P(y_1,...,y_t, X_t=j)$とすると,
$$\begin{aligned} q^T D_{y_1} &= \alpha_1^T \\ \alpha^T_{t-1}PD_{y_t} &= \alpha^T_t \text{ or equivalently} \\ \left(\sum_{i=1}^k \alpha_{t-1}(i) P_{ij} \right)P(y_t|j) &=\alpha_t(j) \end{aligned}$$

さらに$\beta_t(i) = P(y_{t+1},...,t_n|X_t=i)$とすると，
$$\begin{aligned} \beta_n &= \mathbf{1} \\ \beta_t &= PD_{y+1} \beta_{t+1} \text{ or equivalently} \\ \beta_t(i) &= \sum_{j=1}^k P_{ij}P(y_{t+1}|j)\beta_{t+1}(j) \end{aligned}$$
である.組み合わせて
$$P(y_1,..,y_n) = \alpha^T_t \beta_t = \sum_{i=1}^k \alpha_t(i)\beta_t(i)$$
が任意の$t$に成立する.
これは，
$$P(y_1,..,y_n) = \underline{q^T D_{y_1} P \cdots PD_{y_t}}_{\alpha_t^T} \underline{PD_{y_t+1}\cdots PD_{y_n} \mathbf{1}}_{\beta_t}$$
と理解でき，あるいはMarkov propertyによって
$$\begin{aligned}P(y_1,...,y_n) &= \sum_{i=1}^k \underline{P(y_1,...,y_t, X_t=i)}_{\alpha_t(i)} \underline{P(y_{t+1},...,y_n|X_t=i)}_{\beta_t(i)} \\ & = \sum_{i=1}^k P(y_1,...,y_t,X_t=i) = \sum_{i=1}^k \alpha_n(i) =P(y_1,..,y_n) \end{aligned}$$
からも理解できる.

Problem 2. most likely hidden state sequence (Viterbi)

目的は
$$\max_{x_1,...,x_n} P(y_1,..,y_n,x_1,...,x_n) = P(y_1,...,y_n,x_1^*,...,x_n^*)$$
なる$\{x_t^*\}$を求めることだった.
$$d_t(j) = \max_{x_1,...,x_{t-1}} P(y_1,...,y_t,x_1,..,x_{t-1},X_t=j)$$
とすると，
$$\begin{aligned} q(j) P(y_1|j) &= d_1(j) \\ (\max_i d_{t-1}(i)P_{ij})P(y_t|j) &= d_t(j) \end{aligned}$$
が計算できる. $\max_{x_1,...,x_n}P(y_1,....,y_n,x_1,...,x_n) = \max_j d_n(j)$であって，これによって
$$x_n^* = \arg \max_j d_n(j)$$
が得られて，これを起点として
$$x^*_t = \arg \max_i d_t(i) P_{i, x^*_{t+1}}$$
によって，$x^*_{n-1}, x^*_{n-2},...,x^*_1$を計算していく.
このように，forwad algorithmによって$d_t(j)=\max_{x_1,...,x_{t-1}}P(y_1,...,x_{t-1},X_t=j)$の最大値を$j\in \{1,...,k\}$ごとに計算し,さらにbackward algorithmによって,具体的に$P(y_1,..,x_n)$を最大化する$x_n^*,...,x_1^*$を求めていくアルゴリズムをViterbi Algorithmという.

Example

fig.1で表されるHMMを例に上のアルゴリズムを考察する．state $j=1,2$が選ばれると，，$P(y|j) = N(y, \mu_j, \sigma^2)$によって観測される値が確率的に決まるとし，$\mu_1=3, \mu_2=1$,$\sigma^2$は$j=1,2$で共通とする．観測点は$y_1,...,y_8$が与えられていて，$x_1^*,...,x_8^*$を推測する.
まず，$y_1,...,y_8$が,$\sigma^2$の変化によってどう振る舞うかを見る． $\sigma^2$が大きいとき，$P(y|1),P(y|2)$はほとんど同じ分布になり,観測値が役に立たなくなる．
$d_1(1)/d_1(2)=1, d_2(1)/d_2(2)=1/2, d_3(1)/d_3(2)=1/4,...$と近似できるから,$x_i^*=2$となる．
$\sigma^2$が非常に小さい時，今度はほとんど観測値と制約条件だけが推測に影響するようになる．というのは，
$$\frac{d_t(1)}{d_t(2)}=\underline{\frac{\max_i d_{t-1}(i)P_{i1}}{\max_i d_{t-1}(i)P_{i2} }}_{(1)}\cdot\underline{ \frac{P(y_t|j)}{P(y_t|2)}}_{(2)}$$
において，(2)の部分が極めて大きな，あるいは極めて小さな値を取るようになり，(1)の部分をほとんど無視できるからである.
$\sigma^2$が極端な値でない場合には,Markov chainのtransition matrixからstate 2へできるだけ早く移ろうとする性質と，観測値に合ったhidden pathを辿ろうとする性質のバランスを取ろうとする． 例えば$\sigma^2=1$なら，most likely state sequenceは1122222である．

Problem 3: estimation

Hidden statesを観測できず，そこから確率的に生成される値のみを観測できるというのは，モデルの全ての変数を知ることなくモデルを推測しようとしているという点でmixture modelと似ている． この問題はmixture modelと同様にEM algorithmを反復的に用いることで解ける． 普通は複数回行われる，すなわち$\{\{y_t\}_1^n\}_{p=1}^q$のように観測値が得られるのだが，簡単のために$q=1$すなわち観測値は１通りしか無いとする．
EM-algorithmを導く簡単な方法は，まずは全ての変数が観測されているとしてモデルを構成することである．
$$\begin{aligned} \delta(i|t) &= \begin{cases} 1 \ \ \ &(x_t=i) \\ 0 &otherwise \end{cases} \\ \delta(i,j|t) &= \begin{cases} 1 \ \ \ &(x_t=i, x_{t+1}=j) \\ 0 & otherwise \end{cases} \end{aligned}$$
とすると，complete log-likelihoodは
$$\begin{aligned} l(\{x_t\},\{y_t\}) = & \underline{\sum_{i=1}^k \delta(i|1)\log q(i)}_{(1)} + \underline{\sum_{i=1}^k \left(\sum_{t=1}^n \delta(i|t) \log P(y_t|i) \right)}_{(2)} \\ &+ \underline{\sum_{i=1}^k \sum_{j=1}^k \left(\underline{\sum_{t=1}^n \delta(i,j|t)}_{(3)}\right) \log P_{ij}}_{(4)}\end{aligned}$$
(1): 初期状態の確率
(2): 各state $i$における，$y$を生成する確率を$i \in \{1,...,k\}$での総和
(3): $x_1,...,x_n$で$i\rightarrow j$の遷移が起きる回数
(4): 全てのstateの組で，遷移がどれほど起こるかの総和

$\delta$を緩和させた”soft”なカウント$p$を
$$\begin{aligned} p(i|t) &= P(X_t = i|y_1,...,y_n) \\ p(i,j|t) &= P(x_t=i,X_{t+1}=j|y_1,...,y_n) \end{aligned}$$
と定める.
$$P(y_1,..,y_n,X_t=i) = P(y_1,...,y_t,X_t=i)P(y_{t+1},..,y_n|X_t=i)=\alpha_t(i)\beta_t(i)$$
だから，posteriorは
$$P(X_t=i|y_1,...,y_n) = \frac{\alpha_t(i)\beta_t(i)}{\sum_{i'=1}^k \alpha_t(i')\beta_t(i')}$$
という正規化で計算できて，同様に
$$\begin{aligned} P&(y_1,...,y_n,X_t=i,X_{t+1}=j) \\ &=P(y_1,...,y_t,X_t=i)P_{ij}P(y_{t+1}|j)P(y_{t+2},...,y_n|X_{t+1}=j) \\ &= \alpha_t(i) P_{ij} P(y_{t+1}|j)\beta_{t+1}(j) \end{aligned}$$

したがって
$$P(X_t=i, X_{t+1}=j|y_1,....,y_n) = \frac{\alpha_t(i)P_{ij}P(y_{t+1}|j)\beta_{t+1}(j)}{\sum_{i'=1}^k \sum_{j'=1}^k \alpha_t(i')P_{i'j'}P(y_{t+1}|j')\beta_{t+1}(j')}$$

Multiple (partial) alignment

複数の列が与えられるとき，その類似点をさがすのがalignment問題である. そのパターンは，全ての列に存在するということの他にはほとんど情報が得られていないとする． 簡単のため，そのパターンは長さ4であることは既知とする． この状況で考えられる最も簡単なHMMはfig.2である．$m_1,..,m_4$というstatesは”match states”といって，求めるべきパターンを生成したであろうstatesである． $I_1, I_2$は”insert states”であって，探しているパターン以外の列を生成する. それぞれのstateは$P(y|I_i), i=1,2, P(y|m_i) , i=1,...4$というoutput distributionをもつ.これらの分布と$p$の値を与えられた列たちから推測する.

このモデルは有限長の列を生成する. $I_1$に入って最初の要素を生成し，平均$1/p$ステップ$I_1$にとどまった後,$m_1$に遷移してパターンを生成し，$I_2$に遷移してまた平均$1/p$ステップとどまってから列を終わらせる.
複数の列が与えられたとき，このHMMのパラメータを,EM algorithmによって最尤推定する. ここではまだどこが生成されたパターンなのかは考えず，単にパラメータを最適化する. パラメータが見つかったら，Viterbi algorithmによってそれぞれの観測点がどのhidden stateによって生成されたかを推測する.例えば観測列$y_1,...,y_n$に
$$\begin{array}{} \text{hidden} &I_1 & I_1 & \cdots & I_1 & m_1 & m_2 & m_3 & m_4 & I_2 & I_2 & \cdots & I_2 \\ \text{observation} &y_1 & y_2 & \cdots & y_{t-1} & y_t & y_{t+1} & y_{t+2} & y_{t+3} & y_{t+4} & y_{t+5} & \cdots & y_n\end{array}$$
という対応の推測が得られたとき,hiddenの列とobesrvationの列には一対一の関係が有り，この例では，パターンは$t$において，すなわちmatch statesが始まったところで始まる．
それぞれの観測列でのパターンの部分列はfig.3のようにアラインされる．

figure 3

MIT OCW, Machine Learning 14日目

Rohit Singh, Tommi Jaakkola, and Ali Mohammad. 6.867 Machine Learning. Fall 2006. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.
Lecture 18.

• • Specral clustering
    • Graph construction
    • Graph partitioning and criteria
    • Spectral clustering, the eigenvalue problem
    • Spectral clustering, random walk
      • Definition

Specral clustering

データ点の近さの尺度を導入してそれぞれの点同士を頂点とし，辺をその近さの尺度によって重み付けしたグラフを構成できる. spectral clusteringはその重みづけグラフの分割を，固有値問題と考えるアルゴリズムのクラスである. 大きな正の重みで繋がれているノードたちは同じクラスターに入れられることが多い． グラフ表現を行うことで，そのアルゴリズムがノード間の近さだけを基準にして分類を行っていることを際立たせることができる.

Graph construction

ベクトル空間上で表現できる場合にも，グラフ構造での表現には有利な点が有る．例えばfig.1.aの点は2つの半円上の点に分類できるが，これを少数のGaussianの混合で表現することはできない一方，それぞれの点の最近傍の2点をつなげることで,fig.1.bの，非常によく特徴を捉えたグラフが構成できる. このような重み付けグラフを構成するより一般的な方法を議論する. これには多くの方法が有るが，もっとも典型的なのが，上で見たように,k-nearest neighborを使う方法である. すなわち，すべての点について，$k$個の最近傍の点をつなげる無向グラフを作成し，さらに
$$W_{ij} = \begin{cases} \exp(-\beta \|\mathbf{x_i - x_j}\|) \ \ &\text{if } i, j \text{ are connected} \\ 0 & \text{otherwise} \end{cases}$$
によって重みを計算する. $W_{ij} = W_{ji}$である. 対角成分は全て0とする.
$k, \beta$が選べるパラメータである. $k$は求めたいクラスターたちの次元によって適した値が決まってくる．例えば，クラスターが$d$次元の表面をもつとするなら，$k\geq d$が望ましい. 小さな$k$は疎なグラフを作りやすくし，よく似た点たちのみのクラスターが作られるようになる． これは,遠く離れた点ではユークリッド距離を使うのがナンセンスになるような場合に有利である ．例えば球面にのみ全てのデータ点が存在して，点たちの距離が球面に沿った距離で図られるべきときには，点が遠くなれば遠くなるほど，ユークリッド距離と球面上の距離が乖離してくることが想像できるだろう.
$\beta$も同様の役割を果たす．

Graph partitioning and criteria

$n$個の点を2つに分類する問題を定式化する. より多くの種類に分類するときには再帰的に二値分類を適用する. 対象は，重み付け行列$W$で表現されていて，$W$は非負の対称行列で対角成分は0である． $W$を近さの尺度として，ノードたちを$C^+, C^-$の二つに分類する. $y_i = \begin{cases} 1 \ \ & i \in C^+ \\ -1 & i \in C^-\end{cases}$という変数$y=\{y_i\}$を定義する.
$C^+, C^-$を決めれば分類は一意に定まり，その分類(cut)に対する重み
$$s(C^+,C^-)= \sum_{i \in C^+, j\in C^-} W_{ij} = \frac{1}{4}W_{ij} \sum_{i,j} (y_i-y_j)^2 = J(y)$$
を導入する. $i, j$が異なって分類されると$W_{ij}$分の重みが$s$につく． 全てが同じクラスタに分類されるとき$s=0$だから，どちらのクラスタにも同じくらいの数のノードが入るようにするため，minimum cut criterionを導入する. よく使われるcriterionにnormalized cut(Shi and Malik 2000)がある.
$$\text{Norm-cut}(C^+, C^-) = \frac{s(C^+, C^-)}{s(C^+,C^+)+s(C^+,C^-)}+\frac{s(C^+,C^-)}{s(C^-, C^-)+s(C^+,C^-)}$$
である．ただし$s(C^+, C^+)=\sum_{i \in C^+, C^+} W_{i,j}$とする.
この問題を厳密かつ効率的に解く方法は存在しないため，eigenvalue problemによって近似的に解く.

Spectral clustering, the eigenvalue problem

$y= (y_1,..,y_n)$でそれぞれは$\pm 1$のどちらかを取ったが,$z= (z_1,..,z_n)$で$z_i \in \mathbb{R}$に条件を緩和する．やはり$i \in C^+ \Rightarrow z_i >0, i \in C^- \Rightarrow z_i < 0$とする.このように二値分類問題を緩和し，eigenvalue問題に帰着させる．まずはcutの重みを改めて表現する.
$$\begin{aligned} J(z) &= \frac{1}{4} W_{ij}(z_i-z_j)^2 = \frac{1}{4}\sum_{i,j} (z_i^2-2z_iz_j+z_j^2)=\frac{1}{4}\sum_{i,j}W_{ij}(2z_i^2-2z_iz_j) \\ &= \frac{1}{2}\sum_i \underline{(\sum_j W_{ij})}_{D_{ii}}z^2_i + \frac{1}{2} \sum_{i,j} W_{ij}z_iz_j = \frac{1}{2}z^T (D-W)z \end{aligned}$$

$D_{ii}=\sum_j W_{ij}$という対角行列を使って表現した.
$L=D-W$はgraph Laplacianという名でしられ，半正定値行列である. $L$の最小固有値は必ず$0$であり，対応する固有ベクトルは$z=(1,...,1)$である. normalized cut criterionを考慮すると，最適化問題は
$$minimize \frac{1}{2} z^T (D-W)z \ \ \text{ subject to } z^TDz=1, z^TD1=0$$
となる. Lagrange multiplierを使うと,
$$(D-W)z = \lambda Dz$$
の2番目に小さい固有値を求めることと同じになる(らしい). $\hat{y_i} = sign(z_{2_i})$の符号が有るノードが入るクラスターになる.fig.2はあるspectral cluseringの近似解である.

Spectral clustering, random walk

normalized cut problemを緩和して近似的に解いた．全く異なったアプローチでこの近似方法を正当化する． 重み付きグラフの上でのrandom walkを考えるのである.
$$P_{ij} = \frac{W_{ij}}{\sum_{j'}W_{ij'}} = \frac{W_{ij}}{D_{ii}}$$
によって定義される行列$P=D^{-1}W$である. $\sum_j P_{ij} = 1$で,$P \mathbf{1}=\mathbf{1}$が成立する.よって$P$を重み付きグラフの上でのrandom walkのtransition matrixと考えることが出来る. すなわち,$X(t)$を時刻$t$(ここでは$t$回目の遷移とする)でのrandom walkのstateを表すとすると,
$$P(X(t+1)=j|X(t)=i)=P_{ij}$$
であって，homogeneous Markov chainと考えることが出来る. Markov chainのstateはこの場合グラフのnodeである. Markov chainのErgodic propertyを定義する.

Definition

Markov chain $\{X(t)\}$がergocid
$\Leftrightarrow \exists m \text{ s.t. } \forall t, i,j .\ P(X(t+m)=j|X(t)=i)>0$

erogodicであるとき，$\{X\}$はirreducible かつrecurrentかつstationary distributionをもつ.
stationary distribution $\pi$は$\pi_j = \lim_{m\rightarrow \infty} P(X(t+m)=j|X(t)=i)$である． これまで議論してきた重み付きグラフを上の方法でMarkov chainにするとergodicであり，したがってergodic theoremが成立する．

(以下，講義はもう少し続くが固有値とMarkov chainがどうつながるかわからないので飛ばす．そのうちいい教科書を見つけて読む)

MIT OCW, Machine Learning 13日目

Rohit Singh, Tommi Jaakkola, and Ali Mohammad. 6.867 Machine Learning. Fall 2006. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

停電でデータが消えるという悲しみ

• • • Mixture models and clustering
    • Mixtures and K-means
    • K-means
    • Distance and clustering

Mixture models and clustering

与えられたデータは暗黙的に複数の種類に分けられると仮定し，それを踏まえてより精度の高い推測をするというのがmixture modelの動機のひとつだった. 一方で，その暗黙の構造自体を明らかにすることも有用である. このような問題をclusteringという. つまり，データセットをいくつかのclusterに分類するのである.
mixture modelをgenerative modelとして扱うには，我々が分類しようとしているクラスターがどんなものなのか知らなければならない. 最も単純な例がspherical Gaussian clusterで，すなわち
$$P(\mathbf{x};\theta, m) = \sum_{j=1}^m P(j) N(\mathbf{x};\mu_j,\sigma^2_j I)$$
というmixture modelを推測する.
他にも様々なクラスタリングアルゴリズムがあり,あるものはネストしたクラスターを小さなクラスターをマージしていくことで生成し(hierarchical agglomerative clustering)，またあるものは$D$に最適なクラスターの数を推測してからクラスタリングを行う(k-means). などと期待問題によって適したアルゴリズムは異なる.

データセット$D$に対して$m$をどのように設定すればいいかとか,$D$が十分大きければEM-algorithmでよいクラスタリングが出来るのかとか,頑強なモデルであるのかとか，様々な疑問があり，その答えの一部を以下で与える.

Mixtures and K-means

Gaussian mixture modelを,全ての分散行列を同一のspherical(単位行列の定数倍)にし,さらに全てのcomponentの頻度を同一にすることで単純化する.すなわち
$$P(\mathbf{x};\theta)=\frac{1}{m} \sum_{j=1}^m N(\mathbf{x};\mu_m,\sigma^2 I)$$
を考える. これをEM-algorithmで最適化するとどうなるのかをみる.
まず,クラスター$i, j$の境界がどうなっているかをみる. つまり$P(i |\mathbf{x},\theta)=P(j|\mathbf{x},\theta)$をみたす$\mathbf{x}$をみる. 仮定より,この点で
$N(\mathbf{x}, \mu_i, \sigma^2I)=N(\mathbf{x};\mu_j,\sigma^2I)$が成立する.どちらのGaussianも同じsphericalな共分散行列を持つので, これが成立する$\mathbf{x}$では
$$\|\mathbf{x}-\mu_i\| = \|\mathbf{x}-\mu_j\| \text{ or } 2\mathbf{x}^T (\mu_j-\mu_i)=\|\mu_i\|^2 - \|\mu_j\|^2$$
が成立する.
すなわち境界は線形であり,fig.1のように，任意のクラスターの組に対してこのような境界を引ける. 組ごとの比較はVoronoi partitionを導く. Voronoi partitionのあるregionでは，例えば,全ての点が$\mu_1$に最も近い.このregionは同時に$P(1|\mathbf{x}, \theta)> P(j|\mathbf{x}, \theta)$が任意の$j \neq 1$で成立する.

K-means

上のような単純なモデルではEM-algorithmも単純化できて,それを特にK-meansという.
K-meansでは，E-stepで,$j_t = \arg\min_j \|\mathbf{x}_t-\mu_j\|$とし,M-stepで$\mu_j = average\{\mathbf{x}_t | j_t=j \}$とmeanを設定し直す．

K-meansは非常によく利用されるhard assignment(各点がどれかただ一つのクラスターに分類される)版EM-algorithmである. K-meansはEM-algoと同様初期値が結果に大きく影響するので,初期値を変更して何度も行うのが望ましい. また,ある一点を$\mu_1$に割り当て，$\mu_1$から最も遠い点を$\mu_2$,$\mu_1,\mu_2$から最も遠い点を$\mu_3$,…として初期の$\mu$を決める方法をgreedy packingという.

Distance and clustering

これまでの議論でEuclidean distanceを使ってきたことを正当化する. ところで，多くの場合，特徴データを特別な関数で$\mathbb{R}^n$空間に写像して，それからclusteringを考えたりする．
例えば文書をクラスタリングすることを考える. document $\mathbf{x}$を単語の入った袋と考えて,これを以下の写像によって扱いやすいベクトルにする.
$$\begin{aligned} n_w(\mathbf{x}) &= \text{ number of times world } w \text{ appears in } \mathbf{x} \\ f(w|\mathbf{x}) &= \frac{n_w(\mathbf{x})}{\sum_{w'} n_{w'}(\mathbf{x})} = \text{ term frequencey} \\ \phi_{w}(\mathbf{x}) &=f(w|\mathbf{x}) \cdot \underline{\log \left[ \frac{\text{ number of docs}}{\text{ numer of docw with word }w}\right]}_{IDF} \end{aligned}$$
$\phi(\mathbf{x})=(\phi_{w_1},...,\phi_{w_m})\mathbf{(x)}$をTFIDF(term frequency - inverse document frequency)写像という． IDFは,多くの文書に現れるためクラスタリングに役立たなそうなwordほど小さく(1に近く)なる. こうして文書を実数空間に写して，K-meansのようなアルゴリズムに掛けることができる.
クラスタリングを行う際には適切な距離関数を使うことが非常に重要で，適切な距離を使うためにクラスタリングアルゴリズムを選んでもよいほどである. ほとんどのアルゴリズムは任意の距離関数で使える． 適切な距離関数はモデル選択理論を使って選ぶことが出来る．

MIT OCW, Machine Learning 12日目

Rohit Singh, Tommi Jaakkola, and Ali Mohammad. 6.867 Machine Learning. Fall 2006. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

モデル選択理論難しすぎ

• • Mixture models
    • • Example: Student exam model: 1-year
      • Example: student exam model: K-years
  • Collaborative filtering
  • Estimating mixtures: the EM-algorithm (期待値最大化法)
    • Complete data
    • Imcomplete data
      • Algorithm (EM)
      • Example

Mixture models

mixture model(混合モデル)は与えられたデータの曖昧さを捉えるモデルで，データの背後に有る，観測できない要因についての仮定を行う. 観測された一つのexampleを$\mathbf{x}$というベクトルで表すとする. exampleは$m$個の要因($1,...m$とする)のどれかによって生成されている$m$をcomponentの数という． $j \in \{1,..m\}$その要因であるとすると,$\mathbf{x}$の事後確率は$P(\mathbf{x}|j)$である. また$j$の頻度を$P(j)$とすると,$P(\mathbf{x}, j)=P(j)P(\mathbf{x}|j)$. 実際の$j$が何であるかは一般にはわからず，全ての$\{1, ..., m\}$について混合して，$\mathbf{x}$の確率
$$P(\mathbf{x}) = \sum_{j=1}^m P(\mathbf{x}|j)P(j)$$
となる.

Example: Student exam model: 1-year

例えば,学生たち$\{1,...,n\}$の試験の結果$D_1=\{\mathbf{x}_1,...\mathbf{x}_n\}, \mathbf{x_i}=(\text{問1の点数, 問2の点数},...)$をモデル化することを考える. 学生たちは，例えば学士での専攻のような，$D$では与えられていない要因によってことなった正答/誤答の傾向が存在すると仮定する. そのような要因が合計で$m$個(この$m$を選ぶのはmodel selectionの問題である)あって，さらに個々の学生がどれに該当するかわからないときのモデリングを考える.
それぞれの学生の点数が独立とするなら
$$P(\mathbf{x_1,...,x_n}|\theta)=\prod_{t=1}^n \left[\sum_{j=1}^m P(\mathbf{x}_t|j)P(j) \right]$$ である.

Example: student exam model: K-years

上の例で,過去$K$年間のデータがあるとする. $k$年での学生数$n_k$で,$\mathbf{x}_{k,t}$は学生$t$の$k$年目の試験結果とする($t$はただのインデックスで,$t$が同じだからといって同じ学生であるというわけではない). $m$と$P(\mathbf{x}|j)$は変わらないと仮定する. しかし学生の数$n_k$は各年でことなって,$j$の頻度$P(j)$も一定でなく,$P(j|k)$と条件付きにする. この場合のmixture modelは
$$P(\mathbf{x}|k, \theta) = \sum_{j=1}^m P(\mathbf{x}|\theta_j)P(j|k)$$
そして全てのデータ$D=\{D_1, ..., D_k\}$を考えたときの尤度は
$$L(D;\theta)=\prod_{k=1}^K\prod_{t=1}^{n_k} P(\mathbf{x}_{k,t}|k,\theta)=\prod_{k=1}^K\prod_{t=1}^{n_k} \left(\sum_{j=1}^m P(\mathbf{x}_{k,t}|\theta_j)P(j|k) \right)$$
となる.ここでの$\theta$は$\{\theta_j\},\{P(j|k)\}$をも決定する.

Collaborative filtering

mixture modelは推薦システムにもよく使われる. $n$人のユーザに$m$本の映画を推薦する問題を考える. ユーザは$m$のうち極わずかだけに点数をつけているとして,つけていない映画たちをどう評価するかを推測するのが我々の課題である. このような問題をcollaborative filtering(協調フィルタリング)という.
点数は$r_{ij} \in \{1, ...,5\}$をつけられるとする. ただし$r_{ij}$はユーザ$i$の映画$j$に対する評価とする. ユーザたちが実際に与えた評価を$D$とする. $r_{ij}$が与えられているとき$r_{ij}\in I_D$と書く．
collaborative filteringでは,ユーザと映画の両方にいくつかの種類があって,それが評価に影響すると仮定する.すなわち，それぞれの映画が”movie types” $z_m \in \{1,..,K_m\}$の分布の上にあって,ユーザも”user types” $z_u\in \{1,...,K_u\}$の分布の上にあるとする. 有る映画が,すべてのユーザにとって同じタイプであるとは考えず,それぞれの映画が，その映画に対応した特徴のバッグをもっており，それぞれのユーザごとにそのバッグからタイプを取り出すと考える. この仮定はユーザにも適用される． すなわち点数を付けるたびに，そのユーザのタイプのバッグからタイプが取り出される.
$r_{ij}\notin I_D$を以下によって推測する.
$P(z_m|j)$から映画$j$のタイプをサンプルし,また$P(z_j|i)$からユーザ$i$のタイプをサンプルする. さらに$P(r_{ij}|z_u, z_m)$から$r_{ij}$をサンプルするのである. これを全ての$z_m, z_u$に足し合わせて
$$P(r_{ij}|i, j, \theta)=\sum_{z_u=1}^{K_j}\sum_{z_m=1}^{K_m}P(r_{ij}|z_u,z_m)P(z_u|i)P(z_m|j)$$
となる. $\theta$はタイプから評価への写像$\{P(r|z_u, z_m)\}$と$\{P(z_u|i)\}, \{P(z_m|j)\}$を決定する.
$D$を与えられたときの尤度は
$$L(D;\theta) = \prod_{(i,j)\in I_D} P(r_{ij}|i,j,\theta)$$
である.
さらに,ユーザの評価のスタイルもモデルに組み込める. 例えば$3,4,5$のような高評価に偏った評価をする人や,$1$と$5$のみのような極端な評価をする人を考えることが出来る.このような評価スタイルの集合を$\{1,...,K_s\}$とする.ユーザのスタイルは全ての映画に一貫しているが，個々のユーザにどうスタイルを割り当てるかは未知とする. ユーザがスタイル$s \in \{1,...,K_s\}$をもつ確率は$P(s)$と書ける. スタイルも$\{1,..,K_s\}$すべてを$PS(s)$を重みにして総和を考えて尤度を求めるとすると,尤度$L'$は,
$$L'(D;\theta) = \prod_{i=1}^n \left[\sum_{s=1}^{K_s} P(s) \underline{\prod_{j: (i,j)\in I_D} \left( \sum_{z_u=1}^{K_u} \sum_{z_m=1}^{K_m}P(r_{ij}|z_u,z_m,s)P(z_u|i)P(z_m|j) \right)}_{(1)} \right]$$
となる.(1): user $i$がスタイル$s$によって評価する尤度
このモデルは
$$\underline{ (K_s-1)}_{P(s)} + \underline{(5-1)K_uK_mK_s}_{P(r|z_u,z_m,s)}+\underline{n(K_u-1)}_{P(z_u|i)} + \underline{m(K_m-1)}_{P(z_m|j)}$$
個のパラメータを持つ.
さらに充実したモデルでは,”missing elements”のモデル，すなわちある映画の評価がなぜなされないかもモデル化するはずである.

Estimating mixtures: the EM-algorithm (期待値最大化法)

midture modelの例をいくつか見てきた. データによく合うようにパラメータを設定する方法を論じる. $\mathbf{x}$の要因$j$が不明なので，$\{1,..,m\}$で総和を取ってきたのだが,まずは要因がわかっているモデルを考える．

Complete data

$$P(\mathbf{x}; \theta) = \sum_{j=1}^m P(j)N(\mathbf{x};\mu_j,\Sigma_j)$$
それぞれの$\mathbf{x}_t$に対応する$j_t$が既知であると仮定して議論する. $\delta(j|t) =\begin{cases} 1 \ \ (j = j_t) \\ 0 \ \ (j \neq j_t) \end{cases}$を使うと便利である． log-likelihoddは
$$\begin{aligned} l(\mathbf{x_1,...,x_n},j_1,...,j_n;\theta) &= \sum_{t=1}^n \log [P(j_t)N(\mathbf{x}; \mu_{j_t},\Sigma_{j_t})] \\ &= \sum_{t=1}^n \sum_{j=1}^m \delta(j|t) \log [P(j)N(\mathbf{x}_t; \mu_j, \Sigma_j)] \\ &= \sum_{j=1}^m (\sum_{t=1}^n \delta(j|t)) \log P(j) + \sum_{j=1}^m (\sum_{t=1}^n \delta(j|t) \log N(\mathbf{x}_t; \mu_j, \Sigma_j)) \end{aligned}$$
尤度を最大とするパラメータをハットで表すと,
$\hat{P}(j) = \frac{\hat{n}(j)}{n}, \ \ \hat{n}(j) = \sum_{t=1}^n \delta(j|t)$
$\hat{\mu}_j = \frac{1}{\hat{n}(j)} \sum_{t=1}^n \delta(j|t)\mathbf{x}_t, \ \ \hat{\Sigma}_j = \frac{1}{\hat{n}(j)} \sum_{t=1}^n \delta(j|t)(\mathbf{x}_t-\hat{\mu_j})(\mathbf{x}_t-\hat{\mu}_j)^T$
となる.このように$\{j_t\}$が既知である場合には，最尤推定は簡単に行えるとわかる.

Imcomplete data

$j_t$がわかっていない場合を考える. $\theta^{(l)}$を初期のパラメータとする. このパラメータで,ある$\mathbf{x}_t$が$j$によって生成される確率は
$$P(j|\mathbf{x}_t,\theta^{(l)})= \frac{P^{(l)}(j)N(\mathbf{x}_t; \mu^{(l)}_j, \Sigma^{(l)}_j)}{\sum_{j'=1}^m P^{(l)}(j')N(\mathbf{x_t}; \mu^{(l)}_{j'}, \Sigma^{(l)}_{j'})}=\frac{P^{(l)}(j)N(\mathbf{x}_t;\mu_j^{(l)},\Sigma_j^{(l)})}{P(\mathbf{x}_t; \theta^{(l)})}$$
$\delta(j|t)$という二値の割当の代わりに,$p^{(l)}(j|t) = P(j|\mathbf{x}_t, \theta^{(l)})$という”soft”な割当を使うのである. この割当は$\theta^{(l)}$によっており,$\theta$を更新していくたびに変化していく.
これらの結果から,Expectation Maximization algorithm (EM)が導かれる. EMは全てのmixture modelと更に広範なモデルに適用できる. Gaussian mixtureでのEM-algorithmは以下の通り.

Algorithm (EM)

(step1)
$\theta^{(0)}$を定める. 例えば$P^{(0)}(j)=1/m$とし,$\mu^{(0)}_j$をランダムに選んだ$D$の点に,$\Sigma_j^{(0)}$を$D$の分散行列としたりなどする.
(E-step)
$p^{(l)}(j|t) = P(j|\mathbf{x}_t, \theta^{(l)})$を$\theta^{(l)}$によって評価する.
(M-step)
パラメータを，
$$\begin{aligned} P^{(l+1)}(j) &= \frac{\hat{n}(j)}{n}, \ \ \hat{n}(j)=\sum_{t=1}^n p^{(l)}(j|t) \\ \mu_j^{(l+1)} &= \frac{1}{\hat{n}(j)} \sum_{t=1}^n p^{(l)} (j|t) \mathbf{x}_t \\ \Sigma_j^{(l+1)} &= \frac{1}{\hat{n}(j)}\sum_{t=1}^n p^{(l)} (j|t) (\mathbf{x}_t - \mu^{(l+1)}_j)(\mathbf{x}_t - \mu_j^{(l+1)})^T \end{aligned}$$
によって更新する.

この更新則によってlog-likelihoodは増加し,またパラメータは収束することが証明されているが, その極限では$d/d\theta l(D;\theta)=0$が成立することしか保証されていない.

Example

2つのGaussianのmixture modelを考える. fig.2 はEM-algorithmのイテレーションの様子である.