實際上EM算法的思想常常出現在我們的日常生活中，我們在日常中也一定使用過EM算法。
舉個例子，剛來到一個公司，你希望知道哪些行為（參數），可以最大化你的工資（目标函數），但是又因為你是新人是以有很多東西跟你工資的關系都不知道（比如員工，上司之間的關系，公司的文化等等），你唯一知道的就是在表明上的東西（觀測變量），比如公司的規章制度等等，那麼這時候你會怎麼辦呢？你或許會采取一種政策，先根據過去的經驗來猜測這些隐藏因素對你工資的影響（E步），然後根據這些猜測來決定你采取什麼行動（M步），當你采取完行動後，你又獲得了一些經驗，重新整理了你對這些隐藏因素的看法，于是你修正你的想法（E步），再去優化你的行動（M步）直到最後收斂到一個最優值。
是以，形式化來講，EM算法就是要最大化似然度來求得一個參數$\theta $的最優值。但是，很多時候，當我們的模型中存在隐變量的時候（比如，一個詞所屬的主題，聚類問題中樣本的類别, etc.），我們的似然度是很難求的。下面是該似然度的式子，其中z表示不可觀測的變量，x表示可觀測的變量，由于z是不可觀測的，是以，要求似然度，我們必須要對z求和或求積分(連續的時候求積分，離散的時候求和)。
L ( θ ) = ∑ i = 1 N log p ( x i ∣ θ ) = ∑ i = 1 N log [ ∑ z i p ( x i , z i ∣ θ ) ] \mathcal{L}( \theta ) =\sum ^{N}_{i=1}\log p( x_{i} |\theta ) =\sum ^{N}_{i=1}\log\left[\sum _{z_{i}} p( x_{i} ,z_{i} |\theta )\right] L(θ)=i=1∑Nlogp(xi∣θ)=i=1∑Nlog[zi∑p(xi,zi∣θ)]
可以看到上面的這個式子，如果不存在隐變量的話，那麼那個log是直接作用與p的，如果p恰好是指數族分布，那麼這個似然度就非常好求，但是有隐變量的時候，log被一個 ∑ z \sum _{z} ∑z給截斷的，這就使得這個式子變得很難優化。
這個問題的關鍵在于， log p ( x i ∣ θ ) \log p( x_{i} |\theta ) logp(xi∣θ)很難優化，但是 p ( x i , z i ∣ θ ) p( x_{i} ,z_{i} |\theta ) p(xi,zi∣θ)卻很好優化,比如說聚類的時候，你提前知道所有樣本的類别了，那你計算每個類别的中心距離就太簡單了，但是要優化 p ( x i , z i ∣ θ ) p( x_{i} ,z_{i} |\theta ) p(xi,zi∣θ)的前提是，你要看得到隐變量的取值才行啊，然而隐變量是看不到的。EM算法通過一個巧妙的構造，讓 p ( x i , z i ∣ θ ) p( x_{i} ,z_{i} |\theta ) p(xi,zi∣θ)和似然度 p ( x i ∣ θ ) p( x_{i} |\theta ) p(xi∣θ)的下界聯系起來，這是我們隻要優化下界就能代替優化似然度本身。
接下來我們看一下對于單個樣本 p ( x i ) p( x_{i}) p(xi)似然度的下界是什麼東西。在這裡我們引入了 z i z_{i} zi的分布 q i ( z i ) q_{i}( z_{i}) qi(zi)
log p ( x i ∣ θ ) = log p ( x i , z i ) − log p ( z i ∣ x i ) = log ( p ( x i , z i ) q i ( z i ) ) − log ( p ( z i ∣ x i ) q i ( z i ) ) = log p ( x i , z i ) − log q i ( z i ) − log ( p ( z i ∣ x i ) q i ( z i ) ) = ∫ q i ( z i ) log p ( x i , z i ) d z − ∫ q i ( z i ) log q ( z i ) d z − ∫ q i ( z i ) log ( p ( z i ∣ x i ) q i ( z i ) ) d z ( 兩 邊 同 時 對 z 求 期 望 ) = E z i ( log p ( x i , z i ) ) − H ( q i ) ⎵ E L B O i + K L ( q i ( z i ) ∣ ∣ p ( z i ∣ x i ) ) \begin{aligned} \log p( x_{i} |\theta ) & =\log p( x_{i} ,z_{i}) -\log p( z_{i} |x_{i})\\ & =\log\left(\frac{p( x_{i} ,z_{i})}{q_{i}( z_{i})}\right) -\log\left(\frac{p( z_{i} |x_{i})}{q_{i}( z_{i})}\right)\\ & =\log p( x_{i} ,z_{i}) -\log q_{i}( z_{i}) -\log\left(\frac{p( z_{i} |x_{i})}{q_{i}( z_{i})}\right)\\ & =\int q_{i}( z_{i})\log p( x_{i} ,z_{i}) dz-\int q_{i}( z_{i})\log q( z_{i}) dz-\int q_{i}( z_{i})\log\left(\frac{p( z_{i} |x_{i})}{q_{i}( z_{i})}\right) dz( 兩邊同時對z求期望)\\ & =\underbrace{E_{z_{i}}(\log p( x_{i} ,z_{i})) -H( q_{i})}_{ELBO_{i}} +KL( q_{i}( z_{i}) ||p( z_{i} |x_{i})) \end{aligned} logp(xi∣θ)=logp(xi,zi)−logp(zi∣xi)=log(qi(zi)p(xi,zi))−log(qi(zi)p(zi∣xi))=logp(xi,zi)−logqi(zi)−log(qi(zi)p(zi∣xi))=∫qi(zi)logp(xi,zi)dz−∫qi(zi)logq(zi)dz−∫qi(zi)log(qi(zi)p(zi∣xi))dz(兩邊同時對z求期望)=ELBOi
Ezi(logp(xi,zi))−H(qi)+KL(qi(zi)∣∣p(zi∣xi))
我們知道 K L ( q ( z i ) ∣ ∣ p ( z i ∣ x i ) ) ⩾ 0 KL( q( z_{i}) ||p( z_{i} |x_{i})) \geqslant 0 KL(q(zi)∣∣p(zi∣xi))⩾0，是以這個似然度一定有
log p ( x i ) ⩾ E z i ( log p ( x i , z i ) ) − H ( q i ) \log p( x_{i}) \geqslant E_{z_{i}}(\log p( x_{i} ,z_{i})) -H( q_{i}) logp(xi)⩾Ezi(logp(xi,zi))−H(qi)
可以看到對數似然度被分解成了兩部分，一個是evidence lower bound(ELBO)，似然度的下界，另一個是KL距離，不管q是什麼分布，這兩部分加起來肯定是一樣的。
圖中的L是我們的ELBO。
也就是說，隻要我們令KL距離為0，此時 q ( z ) = p ( z ∣ x ) q( z) =p( z|x) q(z)=p(z∣x)，那麼ELBO就等于似然度的值了。這就意味着我們最大化 θ \theta θ的時候，不再需要對 log p ( x ∣ θ ) \log p( x|\theta ) logp(x∣θ)做，隻需要找到 θ \theta θ使得這個ELBO最大不就相當于在“最大化我們的似然度”嗎。而最大化這個ELBO太簡單了，在這裡 H ( q ) H( q) H(q)是q的熵，與 θ \theta θ無關隻與分布q有關，是以不用管。于是我們把 q ( z ) = p ( z ∣ x ) q( z) =p( z|x) q(z)=p(z∣x)代入到ELBO中得到
E L B O i = E z i ( log p ( x i , z i ) ) + c o n s t = ∫ q i ( z i ) log p ( x i , z i ) d z + c o n s t = ∫ p ( z i ∣ x i ) log p ( x i , z i ) d z + c o n s t = ∑ z i p ( z i ∣ x i ) log p ( x i , z i ) + c o n s t ( 如 果 z 是 離 散 的 ) \begin{aligned} ELBO_{i} & =E_{z_{i}}(\log p( x_{i} ,z_{i})) +const\\ & =\int q_{i}( z_{i})\log p( x_{i} ,z_{i}) dz+const\\ & =\int p( z_{i} |x_{i})\log p( x_{i} ,z_{i}) dz+const\\ & =\sum _{z_{i}} p( z_{i} |x_{i})\log p( x_{i} ,z_{i}) +const( 如果z是離散的) \end{aligned} ELBOi=Ezi(logp(xi,zi))+const=∫qi(zi)logp(xi,zi)dz+const=∫p(zi∣xi)logp(xi,zi)dz+const=zi∑p(zi∣xi)logp(xi,zi)+const(如果z是離散的)
EM算法，示意圖，E步，把KL設為0，藍色的線往上移，使得ELBO=似然度，M步，最大化ELBO，使得似然度增大，紅色的線往上移，然後我們不斷重複直到收斂。
考慮所有樣本，正式的EM架構：
E步：把 q i ( z i ) = p ( z i ∣ x i ) q_{i}( z_{i}) =p( z_{i} |x_{i}) qi(zi)=p(zi∣xi)代入到下界中，再把常數項剔除，
Q ( θ , θ t − 1 ) = ∑ i = 1 N ∑ z i p ( z i ∣ x i , θ t − 1 ) log p ( x i , z i , θ ) = ∑ i = 1 N E [ log p ( x i , z i ∣ θ ) ∣ x i , θ t − 1 ] Q\left( \theta ,\theta ^{t-1}\right) =\sum ^{N}_{i=1}\sum _{z_{i}} p( z_{i} |x_{i},\theta^{t-1})\log p( x_{i} ,z_{i},\theta)=\sum ^{N}_{i=1} E\left[\log p( x_{i} ,z_{i} |\theta ) |x_{i} ,\theta ^{t-1}\right] Q(θ,θt−1)=i=1∑Nzi∑p(zi∣xi,θt−1)logp(xi,zi,θ)=i=1∑NE[logp(xi,zi∣θ)∣xi,θt−1]
M步：最大化下界ELBO
θ t = arg max θ Q ( θ , θ t − 1 ) \theta ^{t} =\arg\max_{\theta } Q\left( \theta ,\theta ^{t-1}\right) θt=argθmaxQ(θ,θt−1)
M步2：我們還可以做MAP估計，隻需要在Q加上參數的對數先驗就可以輕松完成，E步沒有任何變化
θ t = arg max θ Q ( θ , θ t − 1 ) + log p ( θ ) \theta ^{t} =\arg\max_{\theta } Q\left( \theta ,\theta ^{t-1}\right) +\log p( \theta ) θt=argθmaxQ(θ,θt−1)+logp(θ)
在MAP估計的時候，不僅需要考慮下界的最大化，還需要考慮先驗對參數的影響。