機率統計教學錄影數學符號數學基礎排列組合機率統計簡介機率機率公理隨機變數連續測度單一分布條件機率聯合分布貝氏定理動差生成函數特徵函數機率法則匯總離散分布二項分布多項分布負二項分布幾何分布超幾何分布布瓦松分布連續分布均勻分布常態分布Gamma 分布指數分布卡方分布柯西分布Weibull 分布T 分布F 分布Beta 分布多維分布統計抽樣敘述統計推論統計中央極限定理估計方法單組樣本估計兩組樣本估計檢定方法單組樣本檢定兩組樣本檢定平均値的推論變異數的推論無母數推論迴歸分析變異數分析實驗設計因子實驗品質管制時間序列數據分類統計定理匯總統計情況分類計算統計蒙地卡羅法最大似然法則假說與學習EM 算法簡單貝氏分類貝氏網路隨機過程馬可夫鏈蒙地卡羅馬可夫資源範例投影片教學錄影練習題考題解答訊息相關網站參考文獻最新修改簡體版English |
E-M是使用高斯分配(Gaussian Distribution，也就是常態分配)來描述該案例隸屬於某群集的機率密度，利用此機率函數來來取代剛性群集的距離函數 E 步驟：(期望) 計算似然函數，使用 x 相對於 z 的條件機率分布。 (1)\begin{align} Q(\theta|\theta^{(t)}) = E_{Z|x,\theta^{(t)}}\left[ \log L (\theta;x,Z) \right] \end{align}
M 步驟：(最大化) 找出最佳化的參數 (2)\begin{align} \theta^{(t+1)} =\arg\max \ Q(\theta|\theta^{(t)}) \end{align}
其中m是平均值，而s表示標準差。 (3)\begin{align} F(q,\theta) =E_q [ \log L (\theta ; x,Z) ] + H(q) = -D_{\text{KL}}\big(q \big\| p_{Z|X}(\cdot|x;\theta ) \big) + \log L(\theta;x) \end{align}
Then the steps in the EM algorithm may be viewed as: :'''Expectation step''': Choose ''q'' to maximize ''F'': (4)\begin{align} q^{(t)} = \arg\max \ F(q,\theta^{(t)}) \end{align}
:'''Maximization step''': Choose ''θ'' to maximize ''F'': (5)\begin{align} \theta^{(t+1)} = \arg\max \ F(q^{(t)},\theta) \end{align}
最佳化EM 演算法其實求取的最佳化，事實上就是最大似然法則 (也就是最大商法則) 的結果，以下是 EM 最佳化的算式之基本推導方法。 (6)\begin{eqnarray} && \sum_z P(Z=z|x,h) L(x,Z=z|h) \\ &=& \sum_z \frac{P(x,Z=z,h)}{P(x,h)} \log P(x,Z=z|h) \\ &=& \frac{1}{P(x,h)} \sum_z P(x,Z=z,h) \log P(x,Z=z|h) \\ &=& \frac{1}{P(x,h)} H(x,Z|h) \\ \end{eqnarray}
EM 演算法EM 演算法 (Expectation-maximization Algorithm) 可以總結成下列公式 (7)\begin{align} h^{t+1} = \arg\max_h \; \sum_z P(Z=z | x, h^t) L(x,Z=z|h^t) \end{align}
說明：h : 機率模型, Z : 隱變數, x : 觀察值 E-step 計算隱變數 z 的條件熵期望值，因此稱為 Expectation，這也就是算式 $\sum_z P(Z=z | x, h^t) L(x,Z=z|h^t)$ 意義。 M-step 則是尋找一個讓條件熵最大化的機率模型 h，因此稱為 Maximization，也就是 $\arg\max_h(...)$ 的步驟。 EM 演算法的應用非常廣泛，特別是在人工智慧領域中的分群 (Clustering) ，貝氏網路的學習 (Bayesian Network)，以及隱馬可夫模型 (Hidden Markov Model) 的學習上，都有強大的應用，以下分別介紹之。 EM 學習法與最大商法則(8)\begin{eqnarray} h^{t+1} &=& \arg\max_h \; \sum_z P(Z=z | x, h^t) L(x,Z=z|h^t) &=& \arg\max_h \; \sum_z P(Z=z | x, h^t) L(x,Z=z|h^t) &=& \arg\max_h \; \sum_z P(Z=z | x, h^t) L(x,Z=z|h^t) \end{eqnarray}
一個簡單的範例假如有一個機率源 h 會產生二進位的亂數 (0 or 1)，已知此機率源產生 0 的機率為(h1,…h5) = (0,0.3,0.5,0.7,1.0) 等五種情況之ㄧ，假如我們觀察該機率源所產生的隨機亂數序列為 x[1..n] = (0,1,1,1,0,1,1,1,1,0,….)，那麼我們在每個時間點應該假設該機率源的分布 h 為何種分布最好呢？ 說明：假如這是一場賭局，我們只能從 (h1,…h5) 當中選擇一個機率源模型，當第 n 個觀察值進來時，我們應該將賭金押在哪一個機率源才對呢？ 在這樣的模型下，沒有任何隱變數存在，因此 z 為空集合，不需考慮。於是 EM 目標函數退化成下列公式。 (9)\begin{eqnarray} h^{t+1} &=& \arg\max_h \; \sum_z P(z|x,h^t) L(x,z|h^t) \\ &=& \arg\max_h \; \frac{P(\emptyset,x,h^t)}{P(x,h^t)} L(x|h^t) \\ &=& \arg\max_h \; L(x|h^t) \\ &=& \arg\max_h \; \log \frac{P(x,h^t)}{P(h)} \\ &=& \arg\max_h \; (\log P(x,h^t) - \log P(h)) \\ &=& \arg\max_h \; \log P(x,h^t) \\ &=& \arg\max_h \; \log (P(x_i=0,h)^{N(0)} P(x_i=1,h)^{N(1)}) \\ &=& \arg\max_h \; N(0) \log P(x_i=0,h) + N(1) \log P(x_i=1,h) \\ &=& \arg\max_h \; \sum_{x_i} P(x_i) \log P(x_i,h) \\ \end{eqnarray}
於是，EM 的目標是尋找產生 x 序列機率最大的假設 h，也就是讓 $\sum_{x_i} P(x_i) \log P(x_i,h)$ 最大的 h，在這個問題上，$\arg\max_h(...)$ 的程序很容易做，以下是一個範例。 首先，我們可以列出每個機率源產生該序列的機率， 當 x[1] 進來時，我們應該押 h1, P(h|x)=P(x,h)/P(x) P(x|h)=P(x,h)/P(h) 那麼在此範例中，P(x), P(h), P(x,h) 各為多少呢？ P(h) 可以直接根據最大商法則設定為平均分布，也就是 P(h1)=P(h2)=P(h3)=P(h4)=P(h5)=0.2。 P(x,h) = P(x[1..n], h) = p(h,x=0)^{N_x[0]} p(h,x=1)^{N_x[1]} 使用 EM 進行分群 (Clustering)E-M是使用高斯分配(Gaussian Distribution，也就是常態分配)來描述該案例隸屬於某群集的機率密度，利用此機率函數來來取代剛性群集的距離函數 E 步驟：(期望) 計算似然函數，使用 x 相對於 z 的條件機率分布。 (10)\begin{align} Q(\theta|\theta^{(t)}) = E_{Z|x,\theta^{(t)}}\left[ \log L (\theta;x,Z) \right] \end{align}
M 步驟：(最大化) 找出最佳化的參數 (11)\begin{align} \theta^{(t+1)} =\arg\max \ Q(\theta|\theta^{(t)}) \end{align}
其中m是平均值，而s表示標準差。 (12)\begin{align} F(q,\theta) =E_q [ \log L (\theta ; x,Z) ] + H(q) = -D_{\text{KL}}\big(q \big\| p_{Z|X}(\cdot|x;\theta ) \big) + \log L(\theta;x) \end{align}
Then the steps in the EM algorithm may be viewed as: :'''Expectation step''': Choose ''q'' to maximize ''F'': (13)\begin{align} q^{(t)} = \arg \max \ F(q,\theta^{(t)}) \end{align}
:'''Maximization step''': Choose ''θ'' to maximize ''F'': (14)\begin{align} \theta^{(t+1)} = \arg \max \ F(q^{(t)},\theta) \end{align}
參考文獻
|
EM 演算法 (Estimation Maximization)
page revision: 10, last edited: 03 Dec 2010 09:01
Post preview:
Close preview