EM演算法

1、背景

2、理論

2.1、Jensen不等式

優化理論中，假設 \(f\) 是定義域為實數的函式，如果對于所有的實數 \(x\) ，且二階導數\(f''(x)\geq 0\) ，則 \(f\) 是凸函式，當 \(x\) 是向量時，如果其Hessian矩陣H是半正定的 （\(H \geq 0\)），那么 \(f\) 是凸函式，且當 \(f''(x)>0\) 或者 \(H>0\) ，那么稱 \(f\) 是嚴格凸函式，

Jensen不等式定義如下：

如果 \(f\) 是任一凸函式，則 \(E\left[f(x)\right]\geq f(\left[x\right])\) ，特別的，如果 \(f\) 是嚴格的凸函式，那么\(E\left[f(x)\right]=f(\left[x\right])\) 當且僅當 \(p(x=E\left[x\right])=1\) ，即使說 \(x\) 是常量，

如果 \(f\) 是（嚴格）凹函式當且僅當 \(-f\) 是嚴格）凸函式時，其Jensen不等式與凸函式反號，即 \(E\left[f(x)\right]\leq f(\left[x\right])\) 成立，

2.2、EM演算法

給定資料樣本 \(\left\{x^{1},x^{2},...,x^{m}\right\}\) ，且樣本間獨立，我們的目的是找到每個樣本的隱含類別 \(z\) ，使得概率密度 \(p(x,z)\) 最大，\(p(x,z)\) 的最大似然估計如下：

\[
\begin{align}
l(\theta) &= \sum_{i=1}^{m} log{p(x;\theta)}\\
&= \sum_{i=1}^{m} log{\sum_{z}p(x,z;\theta)}
\end{align}
\]

上式中，第一步是對極大似然函式取對數，第二步是對每個樣例可能的類別 \(z\) 求聯合概率分布概率的和，因為有隱藏變數 \(z\) 的存在，所以通過上式直接通過最大似然求 \(\theta\) 是比較困難的，但是如果確定 \(z\) 后，求解就比較容易了，

而通過EM演算法求解存在隱藏變數 \(z\) 的優化問題比較有效的，其思想是不斷地建立 \(l\) 的下界 (E步)，然后優化下界 (M步)，具體程序是這樣的：

對于每一個樣例 \(i\) ， \(Q_{i}\) 表示該樣例 \(i\) 的隱含變數 \(z\) 的某種分布，\(Q_{i}\) 滿足的條件是 \(\sum_{z}Q_{i}(z)=1 ，Q_{i}(z)\geq0\) (如果 \(z\) 是連續的，那么 \(Q_{i}\) 是概率密度函式，需要將求和符號\(\sum\)換成積分符號\(\int\))，比如將教室里學生分類，如果隱藏變數 \(z\) 是身高，那么就是連續的高斯分布，若隱藏變數是性別，那么就是伯努利分布，根據描述內容得到下面的公式：

\[
\begin{align}
\sum_{i}log{p(x^{(i)};\theta})
&=\sum_{i}log\sum_{z^{(i)}}p(x^{(i)},z^{(i)};\theta)\\
&=\sum_{i}log\sum_{z^{(i)}}Q_{i}(z^{(i)})\frac{p(x^{(i)},z^{(i)};\theta)}{Q_{i}(z^{(i)})}\\
&\geqslant \sum_{i}\sum_{z^{(i)}}Q_{i}(z^{(i)}) log \frac{p(x^{(i)},z^{(i)};\theta)}{Q_{i}(z^{(i)})}
\end{align}
\]

上式(3)到(4)比較直接，分子分母同時乘以一個相同的函式 \(Q_{i}(z^{(i)})\) ，從(4)到(5)利用了Jensen不等式，因為 \(log(x)''<0\) ，所以 \(log(x)\) 是凹函式，并且有期望如下，

\[
\begin{align}
\sum_{z^{(i)}} Q_{i}(z^{(i)})
\left[
\frac{p(x^{(i)},z^{(i)};\theta)}{Q_{i}(z^{(i)})}
\right]
\end{align}
\]

(6)式即為 \(\left[p(x^{(i)},z^{(i)};\theta)/Q_{i}(z^{(i)})\right]\) 的期望，

期望回顧

假設 \(Y\) 是隨機變數是 \(X\) 的函式，\(Y=g(X)\)（\(g\) 是連續函式），則：

• \(X\) 是離散型隨機變數，它的分布律為 \(P(X=x_{k})=p_{k}\)，\(K=1,2,...\) ，若 \(\sum_{k=1}^{+\infty}g(x_{k}p_{k})\) 絕對收斂，則有期望

\[
\begin{align}
E(Y)=E\left[g(X)\right]=\sum_{k=1}^{+\infty}g(x_{k})p_{k}
\end{align}
\]

• \(X\) 是連續型隨機變數，它的概率密度為 \(f(x)\)，若 \(\int_{-\infty}^{+\infty}g(x)f(x)dx\) 絕對收斂，則有期望

\[
\begin{align}
E(Y)=E[g(X)]=\int_{-\infty}^{+\infty}g(x)f(x)dx
\end{align}
\]

結合上述問題，\(Y\) 是 \(\left[\frac{p(x^{(i)},z^{(i)};\theta)}{Q_{i}(z^{(i)})}\right]\) ，\(X\) 是 \(z^{(i)}\) ，\(Q_{i}(z^{(i)})\) 是 \(p_{k}\)，\(g\) 是 \(z^{(i)}\) 到 \(\left[\frac{p(x^{(i)},z^{(i)};\theta)}{Q_{i}(z^{(i)})}\right]\) 的映射，這樣子解釋中的期望，再根據凹函式的Jensen不等式：

\[
\begin{align}
f\left(E_{z^{(i)}\sim{Q_{i}}}\left[\frac{p(x^{(i)},z^{(i)};\theta)}{Q_{i}(z^{(i)})}\right] \right) \geqslant E_{z^{(i)}\sim{Q_{i}}} \left[f\left(\frac{p(x^{(i)},z^{(i)};\theta)}{Q_{i}(z^{(i)})}\right)\right]
\end{align}
\]

就可以得到式子(5)，

這個程序看作是對 \(l(\theta)\) 求下界，對于 \(Q_{i}\) 的選擇有多種可能，但是我們要如何選擇最好的？

假設 \(\theta\) 已經給定，那么 \(l(\theta)\) 的值就決定于 \(Q_{i} (z^{(i)})\) 和 \(p(x^{(i)},z^{(i)})\) 了，通過不斷調整這兩個概率使得下界不斷上升，以逼近 \(l(\theta)\) 的真實值，當不等式變成等式的時候，說明我們調整后的概率就能等價于 \(l(\theta)\) 了，按照這個思路，我們就找到等式成立的條件，根據Jensen不等式，要想等式成立，需要讓隨機變數變成常數值，這里得到：

\[
\begin{align}
\frac{p(x^{(i)},z^{(i)};\theta)}{Q_{i}(z^{(i)})}=c
\end{align}
\]

上式中 \(c\) 為常數，不依賴于 \(z^{(i)}\) ，對于式子進一步推導，我們知道 \(\sum_{z}Q_{i}(z^{(i)})=1\) ，那么也就有 \(\sum_{z}p(x^{(i)},z^{(i)};\theta)=c\) ，(多個等式分子分母相加不變，這個認為每個樣例的兩個概率比值都是 \(c\))，那么有下面式子：

\[
\begin{align}
Q_{i}(z^{(i)})
&=\frac{p(x^{(i)},z^{(i)};\theta)}{\sum_{z}p(x^{i},z;\theta)}\\
&=\frac{p(x^{(i)},z^{(i)};\theta)}{p(x^{i};\theta)}\\
&=p(z^{(i)};\theta)
\end{align}
\]

到這里，我們推匯出了在固定其他引數 \(\theta\) 后，\( Q_{i}(z^{(i)})\) 的計算公式就是后驗概率，解決了\( Q_{i}(z^{(i)})\) 如何選擇的問題，這一步就是E步，建立了 \(l(\theta)\) 的下界，接下來是M步，就是在給定\( Q_{i}(z^{(i)})\) 后，調整 \(\theta\) ，去極大化\(l(\theta)\) 的下界 (在固定\( Q_{i}(z^{(i)})\)后，下界還可以調整得更大)，那么一般的EM演算法步驟如下:

EM演算法

回圈重復直到收斂 {

•   (E步) 對于每一個 \(i\) ，計算

\[
\begin{align}
Q_{i}(z^{(i)}):=p(z^{(i)}|x^{(i)};\theta)
\end{align}
\]

•   (M步) 計算

\[
\begin{align}
\theta :=\arg\max_{\theta} \sum_{i}\sum_{z^{(i)}}Q_{i}(z^{(i)})\log\frac{p(x^{(i)},z^{(i)};\theta)}{Q_{i}(z^{(i)})}
\end{align}
\]

}

那么如何確保EM收斂？，假定 \(\theta^{(t)}\) 和 \(\theta^{(t+1)}\) 是EM演算法第 \(t\) 和 \(t+1\) 次迭代后的結果，如果能夠證明 \(l(\theta^{(t)})\leqslant l(\theta^{(t+1)})\) ，也就是說極大似然估計單調遞增，那么最終我們會達到最大似然估計的最大值，證明如下：

• 選定 \(\theta^{(t)}\) 后，我們得到E步：

\[
\begin{align}
Q_{i}^{(t)}(z^{(i)}):=p(z^{(i)}|x^{(i)};\theta^{(t)})
\end{align}
\]

      這一步保證了在給定 \(\theta^{(t)}\) 時，Jensen不等式中的等式成立，即使說
\[
\begin{align}
l(\theta^{(t)})=\sum_{i}\sum_{z^{(i)}}Q_{i}(z^{(i)}) log \frac{p(x^{(i)},z^{(i)};\theta)}{Q_{i}(z^{(i)})}
\end{align}
\]

• 然后進行M步，固定 \(Q_{i}^{(t)}(z^{(i)})\) ，并將 \(\theta^{(t)}\) 作為變數，對上面的 \(l(\theta^{(t)})\) 求導后，得到 \(\theta^{(t+1)}\) ，經過一些推導后會有以下公式成立
  \[
  \begin{align}
  l(\theta^{(t+1)})
  &\geqslant \sum_{i}\sum_{z^{(i)}}Q_{i}(z^{(i)}) log \frac{p(x^{(i)},z^{(i)};\theta^{(t+1)})}{Q_{i}(z^{(i)})}\\
  & \geqslant \sum_{i}\sum_{z^{(i)}}Q_{i}(z^{(i)}) log \frac{p(x^{(i)},z^{(i)};\theta^{(t)})}{Q_{i}(z^{(i)})}\\
  &=l(\theta^{(t)})
  \end{align}
  \]
   公式(18)，得到 \(\theta^(t+1)\) 時，只是最大化 \(l(\theta^{(t)})\) ，也就是 \(l(\theta^{(t+1)})\) 的下界，而沒有使等式成立，等式成立只有是在固定 \(\theta\) ，并按照E步得到 \(Q_{i}\) 時才能成立，況且，根據我們上面得到的\(l(\theta)
  \geqslant \sum_{i}\sum_{z^{(i)}}Q_{i}(z^{(i)})\times log \times\frac{p(x^{(i)},z^{(i)};\theta)}{Q_{i}(z^{(i)})} \) 對于所有的 \(Q_{i}\) 和 \(\theta\) 都成立；

公式11.2利用了M步的定義，即是將 \(\theta^{(t)}\) 調整到 \(\theta^{(t+1)}\) ，使下界最大化，因此(19)成立，(20)是前面的結果，

• 這樣就證明了 \(l^{(\theta)}\) 會單調增加，一種收斂方法是 \(l^{(\theta)}\)不再變化，還有一種情況是變化幅度很小，

再次解釋一下M，首先(18)對所有的引數都滿足，而其等式成立條件只是在固定 \(\theta\)，并調整好 \(Q\) 時成立，而第(18)步只是固定 \(Q\)，調整 \(\theta\) ，不能保證等式一定成立，(18)到(19)就是M步的定義，(19)到(20)是前面E步所保證等式成立條件，也就是說E步會將下界拉到與 \(l(\theta)\) 一個特定值（這里 \(\theta^{(t)}\)）一樣的高度，而此時發現下界仍然可以上升，因此經過M步后，下界又被拉升，但達不到與另 \(l(\theta)\) 外一個特定值一樣的高度，之后E步又將下界拉到與這個特定值一樣的高度，重復下去，直到最大值，

如果我們定義

\[
\begin{align}
J(Q,\theta)=\sum_{i}\sum_{z^{(i)}}Q_{i}(z^{(i)}) log \frac{p(x^{(i)},z^{(i)};\theta)}{Q_{i}(z^{(i)})}
\end{align}
\]

從前面的推導中我們知道 \(l(\theta) \geqslant J(Q,\theta)\) ，EM可以看作是 \(J\) 的坐標上升法，E步固定 \(\theta\) ，優化 \(Q\) ，M步固定 \(Q\) 優化 \(\theta\) ，

3、高斯混合模型

• 1、參考文獻1:（EM演算法）The EM Algorithm

• 2、參考文獻2: 13_EM

• 3、代碼實作：lihang-code/第09章 EM演算法及其推廣/9.Expectation_Maximization.ipynb

標籤：其他

上一篇：【tf.keras】使用手冊

下一篇：Neo4j集群容器化部署