安徽科技學院官網百度seo sem
文章目錄
- 導讀
- 符號說明
- 混合模型
- 伯努利混合模型(三硬幣模型)
- 問題描述
- 三硬幣模型的EM算法
- 1.初值
- 2.E步
- 3.M步
- 初值影響
- p,q 含義
- EM算法另外視角
- Q 函數(shù)
- BMM的EM算法
- 目標函數(shù)L
- EM算法導出
- 高斯混合模型
- GMM的EM算法
- 1. 明確隱變量, 初值
- 2. E步,確定Q函數(shù)
- 3. M步
- 4. 停止條件
- 如何應用
- GMM在聚類中的應用
- Kmeans
- K怎么定
導讀
-
概率模型有時既含有觀測變量,又含有隱變量或潛在變量。這句很重要,有時候我們能拿到最后的觀測結果,卻拿不到中間的過程記錄
-
EM算法可以用于生成模型的非監(jiān)督學習,EM算法是個一般方法,不具有具體模型
EM算法是一種迭代算法,用于含有隱變量的概率模型的極大似然估計,或極大后驗概率估計
-
似然和概率的關系可以推廣了解,這章關于概率和似然的符號表示,概率和似然是同樣的形式描述的都是可能性, P ( Y ∣ θ ) P(Y|\theta) P(Y∣θ)是一個兩變量的函數(shù),似然是給定結果,求參數(shù)可能性;概率是給定參數(shù)求結果可能性
是不是可以認為,似然和概率分別對應了Train和Predict的過程?假設給定觀測數(shù)據(jù)Y,其概率分布是P(Y|θ),其中θ是概率分布的參數(shù)。那么不完全數(shù)據(jù)Y的似然函數(shù)是通過將Y視為已知觀測數(shù)據(jù),而將未觀測到的數(shù)據(jù)表示為缺失或隱變量。似然函數(shù)可以表示為P(Y|θ)
-
無論是三硬幣還是GMM,采樣的過程都是如下:
- Sample z i ~ p ( z ∣ π ) z_i \sim p(z|\pi) zi?~p(z∣π)
- Sample x i ~ p ( x ∣ π ) x_i \sim p(x|\pi) xi?~p(x∣π)
注意,這里用到了 π \pi π,在強化學習中,隨機性策略 π ( x , a ) \pi(x,a) π(x,a)表示為狀態(tài) x x x下選擇動作 a a a的概率。
-
關于EM算法的解釋
注意這里EM不是模型,是個一般方法,不具有具體的模型,這點前面已經提到- PRML
k m e a n s → G M M → E M kmeans \rightarrow GMM \rightarrow EM kmeans→GMM→EM
k均值聚類算法就是一個典型的EM算法 - 統(tǒng)計學習方法
- M L E → B MLE \rightarrow B MLE→B
- F F F函數(shù)的極大-極大算法
- PRML
-
HMM作了兩個基本假設,實際上是在說在圖模型中,存在哪些邊
符號說明
一般地,用 Y Y Y表示觀測隨機變量的數(shù)據(jù), Z Z Z表示隱隨機變量的數(shù)據(jù)。 Y Y Y和 Z Z Z一起稱為完全數(shù)據(jù)(complete-data),觀測數(shù)據(jù) Y Y Y又稱為不完全數(shù)據(jù)(incomplete-data)
上面這個概念很重要,Dempster在1977年提出EM算法的時候文章題目就是《Maximum likelihood from incomplete data via the EM algorithm》,具體看書中本章參考文獻[^3]
假設給定觀測數(shù)據(jù) Y Y Y,其概率分布是 P ( Y ∣ θ ) P(Y|\theta) P(Y∣θ),其中 θ \theta θ是需要估計的模型參數(shù)
那么不完全數(shù)據(jù) Y Y Y的似然函數(shù)是 P ( Y ∣ θ ) P(Y|\theta) P(Y∣θ),對數(shù)似然函數(shù)是 L ( θ ) = log ? P ( Y ∣ θ ) L(\theta)=\log P(Y|\theta) L(θ)=logP(Y∣θ)假設 Y Y Y和 Z Z Z的聯(lián)合概率分布是 P ( Y , Z ∣ θ ) P(Y,Z|\theta) P(Y,Z∣θ),那么完全數(shù)據(jù)的對數(shù)似然函數(shù)是 log ? P ( Y , Z ∣ θ ) \log P(Y,Z|\theta) logP(Y,Z∣θ)
上面這部分簡單對應一下,這里說明一下,你看到下面概率分布和似然函數(shù)形式看起來一樣。在概率中, θ \theta θ已知, 求 Y Y Y,在似然函數(shù)中通過已知的Y去求 θ \theta θ
觀測數(shù)據(jù) Y Y Y | 不完全數(shù)據(jù) Y Y Y | ||
---|---|---|---|
不完全數(shù)據(jù) Y Y Y | 概率分布$P(Y | \theta)$ | 似然函數(shù)$P(Y |
完全數(shù)據(jù) ( Y , Z ) (Y, Z) (Y,Z) | Y Y Y和 Z Z Z的聯(lián)合概率分布$P(Y,Z | \theta )$ | 似然函數(shù)$P(Y,Z |
有一點要注意下, 這里沒有出現(xiàn) X X X, 有提到一種理解
- 有時訓練數(shù)據(jù)只有輸入沒有對應的輸出 ( x 1 , ? ) , ( x 2 , ? ) , … , ( x N , ? ) {(x_1,\cdot),(x_2,\cdot),\dots,(x_N,\cdot)} (x1?,?),(x2?,?),…,(xN?,?),從這樣的數(shù)據(jù)學習模型稱為非監(jiān)督學習問題。
- EM算法可以用于生成模型的非監(jiān)督學習。
- 生成模型由聯(lián)合概率分布 P ( X , Y ) P(X,Y) P(X,Y)表示,可以認為非監(jiān)督學習訓練數(shù)據(jù)是聯(lián)合概率分布產生的數(shù)據(jù)。 X X X為觀測數(shù)據(jù), Y Y Y為未觀測數(shù)據(jù)
有時候,只觀測顯變量看不到關系,就需要把隱變量引進來。
混合模型
書中用三硬幣模型做為引子,在學習這部分內容的時候,注意體會觀測數(shù)據(jù)的作用。
伯努利混合模型(三硬幣模型)
問題描述
問題的描述過程中有這樣一句:獨立的重復 n n n次實驗(這里 n = 10 n=10 n=10),觀測結果如下:
1,1,0,1,0,0,1,0,1,1
思考上面這個觀測和1,1,1,1,1,1,0,0,0,0
有區(qū)別么?
沒有任何信息的前提下,我們得到上面的觀測數(shù)據(jù)可以假定是一個二項分布的形式,參數(shù) n = 10 , p = 0.6 n=10, p=0.6 n=10,p=0.6
把 k = 6 k=6 k=6次成功分布在 n = 10 n=10 n=10次試驗中有 C ( 10 , 6 ) C(10,6) C(10,6)種可能
所以上面兩個觀測序列,可能出自同一個模型。在這個問題的求解上是沒有區(qū)別的
我們通過一段代碼來生成這個數(shù)據(jù)
import numpy as npp = 0.6
n = 10
# np.random.seed(2018)
flag_a = 1
flag_b = 1
cnt = 0
while flag_a or flag_b:tmp = np.random.binomial(1, p, n)if (tmp == np.array([1,1,1,1,1,1,0,0,0,0])).all():flag_a = 0print("[1,1,1,1,1,1,0,0,0,0] at %d\n" % cnt)if (tmp == np.array([1,1,0,1,0,0,1,0,1,1])).all():flag_b = 0print("[1,1,0,1,0,0,1,0,1,1] at %d\n" % cnt)cnt += 1
實際上題目的描述中說明了觀測數(shù)據(jù)生成的過程,這些參數(shù)是未知的,所以需要對這些參數(shù)進行估計
三硬幣模型可以寫作
P ( y ∣ θ ) = ∑ z P ( y , z ∣ θ ) = ∑ z P ( z ∣ θ ) P ( y ∣ z , θ ) = π p y ( 1 ? p ) 1 ? y + ( 1 ? π ) q y ( 1 ? q ) 1 ? y \begin{equation} \begin{aligned} P(y|\theta)&=\sum_z P(y,z|\theta) \\ &=\sum_z P(z|\theta)P(y|z,\theta) \\ &=\pi p^y (1-p)^{1-y} + (1-\pi)q^y(1-q)^{1-y} \end{aligned} \end{equation} P(y∣θ)?=z∑?P(y,z∣θ)=z∑?P(z∣θ)P(y∣z,θ)=πpy(1?p)1?y+(1?π)qy(1?q)1?y???
以上
- 隨機變量 y y y是觀測變量,表示一次試驗觀測的結果是1或0
- 隨機變量 z z z是隱變量,表示未觀測到的擲硬幣 A A A的結果
- θ = ( π , p , q ) \theta=(\pi,p,q) θ=(π,p,q)是模型參數(shù)
- 這個模型是以上數(shù)據(jù)(1,1,0,1,0,0,1,0,1,1)的生成模型
觀測數(shù)據(jù)表示為 Y = ( Y 1 , Y 2 , Y 3 , … , Y n ) T Y=(Y_1, Y_2, Y_3, \dots, Y_n)^T Y=(Y1?,Y2?,Y3?,…,Yn?)T, 未觀測數(shù)據(jù)表示為 Z = ( Z 1 , Z 2 , Z 3 , … , Z n ) T Z=(Z_1,Z_2, Z_3,\dots, Z_n)^T Z=(Z1?,Z2?,Z3?,…,Zn?)T, 則觀測數(shù)據(jù)的似然函數(shù)為
其實覺得這里應該是小寫的 y = ( y 1 , y 2 , … , y n ) , z = ( z 1 , z 2 , … , z n ) y=(y_1,y_2,\dots,y_n), z=(z_1, z_2, \dots,z_n) y=(y1?,y2?,…,yn?),z=(z1?,z2?,…,zn?)
P ( Y ∣ θ ) = ∑ Z P ( Z ∣ θ ) P ( Y ∣ Z , θ ) P(Y|\theta) = \sum\limits_{Z}P(Z|\theta)P(Y|Z,\theta) P(Y∣θ)=Z∑?P(Z∣θ)P(Y∣Z,θ)
注意這里的求和是下面的"+"描述的部分
即
P ( Y ∣ θ ) = ∏ j = 1 n [ π p y j ( 1 ? p ) 1 ? y j + ( 1 ? π ) q y j ( 1 ? q ) 1 ? y j ] P(Y|\theta)=\prod\limits^{n}_{j=1}[\pi p^{y_j}(1-p)^{1-y_j}+(1-\pi)q^{y_j}(1-q)^{1-y_j}] P(Y∣θ)=j=1∏n?[πpyj?(1?p)1?yj?+(1?π)qyj?(1?q)1?yj?]
p ( x ∣ θ ) p ( θ ) = p ( θ ∣ x ) p ( x ) ? p ( θ ∣ x ) = p ( x ∣ θ ) p ( θ ) p ( x ) ? argmax ? p ( θ ∣ x ) p(x|\theta)p(\theta)=p(\theta|x)p(x)\Rightarrow p(\theta|x)=\frac{p(x|\theta)p(\theta)}{p(x)}\Rightarrow\operatorname{argmax}p(\theta|x) p(x∣θ)p(θ)=p(θ∣x)p(x)?p(θ∣x)=p(x)p(x∣θ)p(θ)??argmaxp(θ∣x)
極大似然估計:
θ ^ = arg ? max ? θ log ? P ( Y ∣ θ ) \hat \theta = \arg\max\limits_{\theta}\log P(Y|\theta) θ^=argθmax?logP(Y∣θ)
極大后驗概率:
argmax? p ( θ ∣ x ) ? argmax? p ( x ∣ θ ) p ( θ ) \text{argmax} \ p(\theta|x)\iff\text {argmax} \ p(x|\theta)p(\theta) argmax?p(θ∣x)?argmax?p(x∣θ)p(θ)
均勻分布下,后一部分是等概率的,N
KL散度=交叉熵+const
三硬幣模型的EM算法
1.初值
EM算法首選參數(shù)初值,記作 θ ( 0 ) = ( π ( 0 ) , p ( 0 ) , q ( 0 ) ) \theta^{(0)}=(\pi^{(0)},p^{(0)}, q^{(0)}) θ(0)=(π(0),p(0),q(0)), 然后迭代計算參數(shù)的估計值。
如果第 i i i次迭代的模型參數(shù)估計值為 θ ( i ) = ( π ( i ) , p ( i ) , q ( i ) ) \theta^{(i)}=(\pi^{(i)}, p^{(i)}, q^{(i)}) θ(i)=(π(i),p(i),q(i))
2.E步
那么第 i + 1 i+1 i+1 次迭代的模型參數(shù)估計值表示為
μ j i + 1 = π ( i ) ( p ( i ) ) y j ( 1 ? p ( i ) ) 1 ? y j π ( i ) ( p ( i ) ) y j ( 1 ? p ( i ) ) 1 ? y j + ( 1 ? π ( i ) ) ( q ( i ) ) y j ( 1 ? q ( i ) ) 1 ? y j \mu_j^{i+1} = \frac{\pi^{(i)}(p^{(i)})^{y_j}(1-p^{(i)})^{1-y_j}}{\pi^{(i)}(p^{(i)})^{y_j}(1-p^{(i)})^{1-y_j} + (1-\pi^{(i)})(q^{(i)})^{y_j}(1-q^{(i)})^{1-y_j}} μji+1?=π(i)(p(i))yj?(1?p(i))1?yj?+(1?π(i))(q(i))yj?(1?q(i))1?yj?π(i)(p(i))yj?(1?p(i))1?yj??
因為是硬幣,只有0,1兩種可能,所有有上面的表達
這個表達方式還可以拆成如下形式
μ j i + 1 = { π ( i ) p ( i ) π ( i ) p ( i ) + ( 1 ? π ( i ) ) q ( i ) , y j = 1 π ( i ) ( 1 ? p ( i ) ) π ( i ) ( 1 ? p ( i ) ) + ( 1 ? π ( i ) ) ( 1 ? q ( i ) ) , y j = 0 \mu_j^{i+1} = \begin{cases} \frac{\pi^{(i)}p^{(i)}}{\pi^{(i)}p^{(i)} + (1-\pi^{(i)})q^{(i)}}&, y_j = 1\\ \frac{\pi^{(i)}(1-p^{(i)})}{\pi^{(i)}(1-p^{(i)}) + (1-\pi^{(i)})(1-q^{(i)})}&, y_j = 0\\ \end{cases} μji+1?=? ? ??π(i)p(i)+(1?π(i))q(i)π(i)p(i)?π(i)(1?p(i))+(1?π(i))(1?q(i))π(i)(1?p(i))??,yj?=1,yj?=0?
所以, 這步(求 μ j \mu_j μj?)干了什么,樣本起到了什么作用?
這一步,通過假設的參數(shù),計算了不同的樣本對假設模型的響應( μ j \mu_j μj?),注意這里因為樣本( y j y_j yj?)是二值的,所以,用 { y j , 1 ? y j } \{y_j, 1-y_j\} {yj?,1?yj?} 構成了one-hot的編碼,用來表示樣本歸屬的假設
以上,有點繞
這一步是什么的期望?書中有寫,**觀測數(shù)據(jù)來自硬幣 B B B的概率, 在二項分布的情況下, 響應度和概率是一個概念. **這個說明,有助于后面M步公式的理解。
3.M步
π ( i + 1 ) = 1 n ∑ j = 1 n μ j ( i + 1 ) p ( i + 1 ) = ∑ j = 1 n μ j ( i + 1 ) y j ∑ j = 1 n μ j ( i + 1 ) q ( i + 1 ) = ∑ j = 1 n ( 1 ? μ j ( i + 1 ) ) y j ∑ j = 1 n ( 1 ? μ j ( i + 1 ) ) \begin{align} \pi^{(i+1)} &= \frac{1}{n}\sum_{j=1}^{n}\mu_j^{(i+1)}\\ \color{red} p^{(i+1)} &= \frac{\sum_{j=1}^{n}\mu_j^{(i+1)}y_j}{\sum_{j=1}^{n}\mu_j^{(i+1)}}\\ \color{red} q^{(i+1)} &= \frac{\sum_{j=1}^{n}(1-\mu_j^{(i+1)})y_j}{\sum_{j=1}^{n}(1-\mu_j^{(i+1)})} \end{align} π(i+1)p(i+1)q(i+1)?=n1?j=1∑n?μj(i+1)?=∑j=1n?μj(i+1)?∑j=1n?μj(i+1)?yj??=∑j=1n?(1?μj(i+1)?)∑j=1n?(1?μj(i+1)?)yj????
上面,紅色部分的公式從觀測數(shù)據(jù)是來自硬幣B的概率
這句來理解
初值影響
這個例子里面0.5是個合理又牛逼的初值。迭代收斂的最后結果是(0.5, 0.6, 0.6)
這個結果說明,如果A是均勻的,那么一個合理的解就是B,C是同質的。他們的分布情況和觀測的分布一致
p,q 含義
這里面 p p p對應了 A = 1 A =1 A=1, B = 1 B=1 B=1, q q q對應了 A = 0 A=0 A=0, C = 1 C=1 C=1
這三個公式可以改寫成如下形式:
π ( i + 1 ) = 1 n ∑ j = 1 n μ j ( i + 1 ) p ( i + 1 ) = ∑ j = 1 n μ j ( i + 1 ) y j ∑ j = 1 n ( μ j ( i + 1 ) y j + μ j ( i + 1 ) ( 1 ? y j ) q ( i + 1 ) = ∑ j = 1 n ( 1 ? μ j ( i + 1 ) ) y j ∑ j = 1 n ( ( 1 ? μ j ( i + 1 ) ) y j + ( 1 ? μ j ( i + 1 ) ) ( 1 ? y j ) ) \begin{align} \pi^{(i+1)} &= \frac{1}{n}\sum_{j=1}^{n}\mu_j^{(i+1)}\\ \color{red} p^{(i+1)} &= \frac{\sum_{j=1}^{n}\mu_j^{(i+1)}y_j}{\sum_{j=1}^{n}(\mu_j^{(i+1)}y_j+\mu_j^{(i+1)}(1-y_j)}\\ \color{red} q^{(i+1)} &= \frac{\sum_{j=1}^{n}(1-\mu_j^{(i+1)})y_j}{\sum_{j=1}^{n}((1-\mu_j^{(i+1)})y_j+(1-\mu_j^{(i+1)})(1-y_j))} \end{align} π(i+1)p(i+1)q(i+1)?=n1?j=1∑n?μj(i+1)?=∑j=1n?(μj(i+1)?yj?+μj(i+1)?(1?yj?)∑j=1n?μj(i+1)?yj??=∑j=1n?((1?μj(i+1)?)yj?+(1?μj(i+1)?)(1?yj?))∑j=1n?(1?μj(i+1)?)yj????
π \pi π的表達式回答這樣一個問題: 刷了這么多樣本,拿到一堆數(shù),那么 π \pi π應該是多少,均值是個比較好的選擇
p p p的表達式回答這樣一個問題: 如果我知道每個結果 y j y_j yj?以 μ j \mu_j μj?的可能來自硬幣B(A=1),那么用這些數(shù)據(jù)刷出來他可能是正面的概率。這里面 μ j \mu_j μj?對應了 A = 1 A=1 A=1
q q q的表達式同理,其中 1 ? μ j 1-\mu_j 1?μj?對應了 A = 0 A=0 A=0
到后面講高斯混合模型的時候,可以重新審視這里
α 0 ? π μ 0 ? p y j ( 1 ? p ) 1 ? y j α 1 ? 1 ? π μ 1 ? q y j ( 1 ? q ) 1 ? y j \begin{aligned} \alpha_0& \leftrightarrow \pi \\ \mu_0& \leftrightarrow p^{y_j}(1-p)^{1-y_j}\\ \alpha_1& \leftrightarrow 1-\pi\\ \mu_1& \leftrightarrow q^{y_j}(1-q)^{1-y_j} \end{aligned} α0?μ0?α1?μ1???π?pyj?(1?p)1?yj??1?π?qyj?(1?q)1?yj??
以上對應了包含兩個分量的伯努利混合模型
bmm.py對伯努利混合模型做了實現(xiàn), 有幾點說明一下:
-
( p ( i ) ) y i ( 1 ? p ( i ) ) 1 ? y i (p^{(i)})^{y_i}(1-p^{(i)})^{1-y_i} (p(i))yi?(1?p(i))1?yi?這個表達式對應了伯努利分布的概率密度,可以表示成矩陣乘法,盡量不要用for,效率會差
-
采用了 π , p , q \pi, p, q π,p,q來表示,注意在題目的說明部分有說明三個符號的含義
-
實際上不怎么拋硬幣,但是0-1的伯努利分布很多
當參數(shù) θ \theta θ的維數(shù)為 d ( d ≥ 2 ) d(d\ge2 ) d(d≥2)的時候,可以采用一種特殊的GEM算法,它將算法的M步分解成d次條件極大化,每次只改變參數(shù)向量的一個分量,其余量不改變。
EM算法另外視角
輸入: 觀測變量數(shù)據(jù) Y Y Y,隱變量數(shù)據(jù) Z Z Z,聯(lián)合分布 P ( Y , Z ∣ θ ) P(Y,Z|\theta) P(Y,Z∣θ),條件分布 P ( Z ∣ Y , θ ) P(Z|Y,\theta) P(Z∣Y,θ)
輸出: 模型參數(shù) θ \theta θ
選擇參數(shù)的初值 θ ( 0 ) \theta^{(0)} θ(0),開始迭代
E步:記 θ ( i ) \theta^{(i)} θ(i)為第 i i i 次迭代參數(shù) θ \theta θ的估計值,在第 i + 1 i+1 i+1次迭代的 E E E步,計算
Q ( θ , θ ( i ) ) = E Z [ log ? P ( Y , Z ∣ θ ) ∣ Y , θ ( i ) ] = ∑ Z log ? P ( Y , Z ∣ θ ) P ( Z ∣ Y , θ ( i ) ) \begin{align} Q(\theta, \theta^{(i)}) =& E_Z[\log P(Y,Z|\theta)|Y,\theta^{(i)}]\\ =&\sum_Z\color{red}\log P(Y,Z|\theta)\color{green}P(Z|Y, \theta^{(i)}) \end{align} Q(θ,θ(i))==?EZ?[logP(Y,Z∣θ)∣Y,θ(i)]Z∑?logP(Y,Z∣θ)P(Z∣Y,θ(i))??M步
求使 Q ( θ , θ ( i ) ) Q(\theta, \theta^{(i)}) Q(θ,θ(i))最大化的 θ \theta θ,確定第 i + 1 i+1 i+1次迭代的參數(shù)估計值θ ( i + 1 ) = arg ? max ? θ Q ( θ , θ ( i ) ) \theta^{(i+1)}=\arg\max_\theta Q(\theta, \theta^{(i)}) θ(i+1)=argθmax?Q(θ,θ(i))
Q 函數(shù)
注意Q函數(shù)的定義,可以幫助理解上面E步中的求和表達式
完全數(shù)據(jù)的對數(shù)似然函數(shù) log ? P ( Y , Z ∣ θ ) \log P(Y, Z|\theta) logP(Y,Z∣θ)關于給定觀測數(shù)據(jù) Y Y Y的當前參數(shù) θ ( i ) \theta^{(i)} θ(i)下對為觀測數(shù)據(jù) Z Z Z的條件概率分布 P ( Z ∣ Y , θ ( i ) ) P(Z|Y,\theta^{(i)}) P(Z∣Y,θ(i))的期望稱為Q函數(shù)
BMM的EM算法
輸入: 觀測變量數(shù)據(jù) y 1 , y 2 , … , y N y_1, y_2, \dots, y_N y1?,y2?,…,yN?,伯努利混合模型
輸出: 伯努利混合模型參數(shù)
- 選擇參數(shù)的初始值開始迭代, 2 K 2K 2K 個參數(shù)
- E步:
γ ^ j k = α k B e r n ( y j ∣ θ k ) ∑ k = 1 K α k B e r n ( y j ∣ θ k ) = α k μ k y j ( 1 ? μ k ) 1 ? y j ∑ k = 1 K α k μ k y j ( 1 ? μ k ) 1 ? y j , j = 1 , 2 , … , N ; k = 1 , 2 , … , K \hat\gamma_{jk}=\frac{\alpha_kBern(y_j|\theta_k)}{\sum_{k=1}^K\alpha_kBern(y_j|\theta_k)}=\frac{\alpha_k\mu_k^{y_j}(1-\mu_k)^{1-y_j}}{\sum_{k=1}^K\alpha_k\mu_k^{y_j}(1-\mu_k)^{1-y_j}}, j=1,2,\dots,N; k=1,2,\dots,K γ^?jk?=∑k=1K?αk?Bern(yj?∣θk?)αk?Bern(yj?∣θk?)?=∑k=1K?αk?μkyj??(1?μk?)1?yj?αk?μkyj??(1?μk?)1?yj??,j=1,2,…,N;k=1,2,…,K- M步:
μ ^ k = ∑ j = 1 N γ ^ j k y j ∑ j = 1 N γ ^ j k α ^ k = n k N \hat\mu_k=\frac{\sum_{j=1}^N\hat\gamma_{jk}y_j}{\sum_{j=1}^N\hat\gamma_{jk}}\\ \hat\alpha_k=\frac{n_k}{N} μ^?k?=∑j=1N?γ^?jk?∑j=1N?γ^?jk?yj??α^k?=Nnk??
目標函數(shù)L
L ( θ ) = log ? P ( Y ∣ θ ) = log ? ∑ Z P ( Y , Z ∣ θ ) = log ? ( ∑ Z P ( Y ∣ Z , θ ) P ( Z ∣ θ ) ) L(\theta)=\log P(Y|\theta)=\log \sum_Z P(Y,Z|\theta)=\log(\sum_Z P(Y|Z,\theta)P(Z|\theta)) L(θ)=logP(Y∣θ)=logZ∑?P(Y,Z∣θ)=log(Z∑?P(Y∣Z,θ)P(Z∣θ))
目標函數(shù)是不完全數(shù)據(jù)的對數(shù)似然
EM算法導出
書中這部分內容回答為什么EM算法能近似實現(xiàn)對觀測數(shù)據(jù)的極大似然估計?
L ( θ ) ? L ( θ ( i ) ) = log ? ( ∑ Z P ( Z ∣ Y , θ ( i ) ) P ( Y ∣ Z , θ ) P ( Z ∣ θ ) P ( Z ∣ Y , θ ( i ) ) ) ? log ? P ( Y ∣ θ ( i ) ) ≥ ∑ Z P ( Z ∣ Y , θ ( i ) ) log ? P ( Y ∣ Z , θ ) P ( Z ∣ θ ) P ( Z ∣ Y , θ ( i ) ) ? log ? P ( Y ∣ θ ( i ) ) = ∑ Z P ( Z ∣ Y , θ ( i ) ) log ? P ( Y ∣ Z , θ ) P ( Z ∣ θ ) P ( Z ∣ Y , θ ( i ) ) ? ∑ Z P ( Z ∣ Y , θ ( i ) ) log ? P ( Y ∣ θ ( i ) ) = ∑ Z P ( Z ∣ Y , θ ( i ) ) log ? P ( Y ∣ Z , θ ) P ( Z ∣ θ ) P ( Z ∣ Y , θ ( i ) ) P ( Y ∣ θ ( i ) ) \begin{align} L(\theta)-L(\theta^{(i)})&=\log \left(\sum_Z\color{green}P(Z|Y,\theta^{(i)})\frac{P(Y|Z,\theta)P(Z|\theta)}{\color{green}P(Z|Y,\theta^{(i)})}\right)-\log P(Y|\theta^{(i)})\\ &\ge\sum_Z \color{green}P(Z|Y,\theta^{(i)})\log \frac{P(Y|Z,\theta)P(Z|\theta)}{\color{green}P(Z|Y,\theta^{(i)})}-\log P(Y|\theta^{(i)})\\ &=\sum_Z P(Z|Y,\theta^{(i)})\log \frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})}-\color{red}\sum_Z P(Z|Y,\theta^{(i)})\color{black}\log P(Y|\theta^{(i)})\\ &=\sum_ZP(Z|Y,\theta^{(i)})\log \frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})} \end{align} L(θ)?L(θ(i))?=log(Z∑?P(Z∣Y,θ(i))P(Z∣Y,θ(i))P(Y∣Z,θ)P(Z∣θ)?)?logP(Y∣θ(i))≥Z∑?P(Z∣Y,θ(i))logP(Z∣Y,θ(i))P(Y∣Z,θ)P(Z∣θ)??logP(Y∣θ(i))=Z∑?P(Z∣Y,θ(i))logP(Z∣Y,θ(i))P(Y∣Z,θ)P(Z∣θ)??Z∑?P(Z∣Y,θ(i))logP(Y∣θ(i))=Z∑?P(Z∣Y,θ(i))logP(Z∣Y,θ(i))P(Y∣θ(i))P(Y∣Z,θ)P(Z∣θ)???
以上用于推導迭代過程中兩次 L L L會變大, 這里面紅色部分是后加的方便理解前后兩步之間的推導。綠色部分是為了構造期望, 進而應用琴聲不等式
高斯混合模型
混合模型,有多種,高斯混合模型是最常用的
高斯混合模型(Gaussian Mixture Model)是具有如下概率分布的模型:
P ( y ∣ θ ) = ∑ k = 1 K α k ? ( y ∣ θ k ) P(y|\theta)=\sum\limits^{K}_{k=1}\alpha_k\phi(y|\theta_k) P(y∣θ)=k=1∑K?αk??(y∣θk?)
其中, α k \alpha_k αk?是系數(shù), α k ≥ 0 \alpha_k\ge0 αk?≥0, ∑ k = 1 K α k = 1 \sum\limits^{K}_{k=1}\alpha_k=1 k=1∑K?αk?=1, ? ( y ∣ θ k ) \phi(y|\theta_k) ?(y∣θk?) 是高斯分布密度, θ k = ( μ , σ 2 ) \theta_k=(\mu,\sigma^2) θk?=(μ,σ2)
? ( y ∣ θ k ) = 1 2 π σ k exp ? ( ? ( y ? μ k ) 2 2 σ k 2 ) \phi(y|\theta_k)=\frac{1}{\sqrt{2\pi}\sigma_k}\exp\left(-\frac{(y-\mu_k)^2}{2\sigma_k^2}\right) ?(y∣θk?)=2π?σk?1?exp(?2σk2?(y?μk?)2?)
上式表示第k個分模型
以上, 注意幾點:
-
GMM的描述是概率分布,形式上可以看成是加權求和,有啥用?
-
加權求和的權重 α \alpha α滿足 ∑ k = 1 K α k = 1 \sum_{k=1}^K\alpha_k=1 ∑k=1K?αk?=1的約束
-
求和符號中除去權重的部分,是高斯分布密度(PDF)。高斯混合模型是一種 ∑ ( 權重 × 分布密度 ) = 分布 \sum(權重\times 分布密度)=分布 ∑(權重×分布密度)=分布的表達
高斯混合模型的參數(shù)估計是EM算法的一個重要應用,隱馬爾科夫模型的非監(jiān)督學習也是EM算法的一個重要應用 -
書中描述的是一維的高斯混合模型,d維的形式如下[^2],被稱作多元正態(tài)分布,也叫多元高斯分布
? ( y ∣ θ k ) = 1 ( 2 π ) d ∣ Σ ∣ exp ? ( ? ( y ? μ k ) T Σ ? 1 ( y ? μ k ) 2 ) \phi(y|\theta_k)=\frac{1}{\sqrt{(2\pi)^d|\Sigma|}}\exp\left(-\frac{(y-\mu_k)^T\Sigma^{-1}(y-\mu_k)}{2}\right) ?(y∣θk?)=(2π)d∣Σ∣?1?exp(?2(y?μk?)TΣ?1(y?μk?)?)
其中,協(xié)方差矩陣 Σ ∈ R n × n \Sigma\in \R^{n\times n} Σ∈Rn×n -
另外,關于高斯模型的混合,還有另外一種混合的方式,沿著時間軸的方向做混合??梢岳斫鉃闉V波器,典型的算法就是Kalman Filter,對應了時域與頻域之間的關系,兩個高斯的混合依然是高斯,混合的方法是卷積,而不是簡單的加法,考慮到的是概率密度的混合,也是一種線性的加權
GMM的EM算法
問題描述:
已知觀測數(shù)據(jù) y 1 , y 2 , … , y N y_1, y_2, \dots , y_N y1?,y2?,…,yN?,由高斯混合模型生成
P ( y ∣ θ ) = ∑ k = 1 K α k ? ( y ∣ θ k ) P(y|\theta)=\sum_{k=1}^K\alpha_k\phi(y|\theta_k) P(y∣θ)=k=1∑K?αk??(y∣θk?)
其中, θ = ( α 1 , α 2 , … , α K ; θ 1 , θ 2 , … , θ K ) \theta=(\alpha_1,\alpha_2,\dots,\alpha_K;\theta_1,\theta_2,\dots,\theta_K) θ=(α1?,α2?,…,αK?;θ1?,θ2?,…,θK?)
補充下,不完全數(shù)據(jù)的似然函數(shù)應該是
P ( y ∣ θ ) = ∏ j = 1 N P ( y j ∣ θ ) = ∏ j = 1 N ∑ k = 1 K α k ? ( y ∣ θ k ) \begin{align} P(y|\theta)=&\prod_{j=1}^NP(y_j|\theta)\\ =&\prod_{j=1}^N\sum_{k=1}^K\alpha_k\phi(y|\theta_k) \end{align} P(y∣θ)==?j=1∏N?P(yj?∣θ)j=1∏N?k=1∑K?αk??(y∣θk?)??
使用EM算法估計GMM的參數(shù) θ \theta θ
1. 明確隱變量, 初值
-
觀測數(shù)據(jù) y j , j = 1 , 2 , … , N y_j, j=1,2,\dots,N yj?,j=1,2,…,N這樣產生, 是已知的:
-
依概率 α k \alpha_k αk?選擇第 k k k個高斯分布分模型 ? ( y ∣ θ k ) \phi(y|\theta_k) ?(y∣θk?);
-
依第 k k k個分模型的概率分布 ? ( y ∣ θ k ) \phi(y|\theta_k) ?(y∣θk?)生成觀測數(shù)據(jù) y j y_j yj?
-
反映觀測數(shù)據(jù) y j y_j yj?來自第 k k k個分模型的數(shù)據(jù)是未知的, k = 1 , 2 , … , K k=1,2,\dots,K k=1,2,…,K 以**隱變量 γ j k \gamma_{jk} γjk?**表示
注意這里 γ j k \gamma_{jk} γjk?的維度 ( j × k ) (j\times k) (j×k)
γ j k = { 1 , 第 j 個觀測來自第 k 個分模型 0 , 否則 j = 1 , 2 , … , N ; k = 1 , 2 , … , K ; γ j k ∈ { 0 , 1 } \gamma_{jk}= \begin{cases} 1, &第j個觀測來自第k個分模型\\ 0, &否則 \end{cases}\\ j=1,2,\dots,N; k=1,2,\dots,K; \gamma_{jk}\in\{0,1\} γjk?={1,0,?第j個觀測來自第k個分模型否則?j=1,2,…,N;k=1,2,…,K;γjk?∈{0,1}
注意, 以上說明有幾個假設: -
隱變量和觀測變量的數(shù)據(jù)對應, 每個觀測數(shù)據(jù),對應了一個隱變量, γ j k \gamma_{jk} γjk?是一種one-hot的形式。
-
具體的單一觀測數(shù)據(jù)是混合模型中的某一個模型產生的
-
-
完全數(shù)據(jù)為 ( y j , γ j 1 , γ j 2 , … , γ j K , k = 1 , 2 , … , N ) (y_j,\gamma_{j1},\gamma_{j2},\dots,\gamma_{jK},k=1,2,\dots,N) (yj?,γj1?,γj2?,…,γjK?,k=1,2,…,N)
-
完全數(shù)據(jù)似然函數(shù)
P ( y , γ ∣ θ ) = ∏ j = 1 N P ( y j , γ j 1 , γ j 2 , … , γ j K ∣ θ ) = ∏ k = 1 K ∏ j = 1 N [ α k ? ( y j ∣ θ k ) ] γ j k = ∏ k = 1 K α k n k ∏ j = 1 N [ ? ( y j ∣ θ k ) ] γ j k = ∏ k = 1 K α k n k ∏ j = 1 N [ 1 2 π σ k exp ? ( ? ( y j ? μ k ) 2 2 σ 2 ) ] γ j k \begin{aligned} P(y,\gamma|\theta)=&\prod_{j=1}^NP(y_j,\gamma_{j1},\gamma_{j2},\dots,\gamma_{jK}|\theta)\\ =&\prod_{k=1}^K\prod_{j=1}^N\left[\alpha_k\phi(y_j|\theta_k)\right]^{\gamma_{jk}}\\ =&\prod_{k=1}^K\alpha_k^{n_k}\prod_{j=1}^N\left[\phi(y_j|\theta_k)\right]^{\gamma_{jk}}\\ =&\prod_{k=1}^K\alpha_k^{n_k}\prod_{j=1}^N\left[\frac{1}{\sqrt{2\pi}\sigma_k}\exp\left(-\frac{(y_j-\mu_k)^2}{2\sigma^2}\right)\right]^{\gamma_{jk}}\\ \end{aligned} P(y,γ∣θ)====?j=1∏N?P(yj?,γj1?,γj2?,…,γjK?∣θ)k=1∏K?j=1∏N?[αk??(yj?∣θk?)]γjk?k=1∏K?αknk??j=1∏N?[?(yj?∣θk?)]γjk?k=1∏K?αknk??j=1∏N?[2π?σk?1?exp(?2σ2(yj??μk?)2?)]γjk??
其中 n k = ∑ j = 1 N γ j k , ∑ k = 1 K n k = N n_k=\sum_{j=1}^N\gamma_{jk}, \sum_{k=1}^Kn_k=N nk?=∑j=1N?γjk?,∑k=1K?nk?=N -
完全數(shù)據(jù)對數(shù)似然函數(shù)
log ? P ( y , γ ∣ θ ) = ∑ k = 1 K { n k log ? α k + ∑ j = 1 N γ j k [ log ? ( 1 2 π ) ? log ? σ k ? 1 2 σ 2 ( y j ? μ k ) 2 ] } \log P(y,\gamma|\theta)=\sum_{k=1}^K\left\{n_k\log \alpha_k+\sum_{j=1}^N\gamma_{jk}\left[\log \left(\frac{1}{\sqrt{2\pi}}\right)-\log \sigma_k -\frac{1}{2\sigma^2}(y_j-\mu_k)^2\right]\right\} logP(y,γ∣θ)=k=1∑K?{nk?logαk?+j=1∑N?γjk?[log(2π?1?)?logσk??2σ21?(yj??μk?)2]}
2. E步,確定Q函數(shù)
把 Q Q Q 函數(shù)表示成參數(shù)形式
Q ( θ , θ ( i ) ) = E [ log ? P ( y , γ ∣ θ ) ∣ y , θ ( i ) ] = E ∑ k = 1 K n k log ? α k + ∑ j = 1 N γ j k [ log ? ( 1 2 π ) ? log ? σ k ? 1 2 σ 2 ( y j ? μ k ) 2 ] = E ∑ k = 1 K ∑ j = 1 N γ j k log ? α k + ∑ j = 1 N γ j k [ log ? ( 1 2 π ) ? log ? σ k ? 1 2 σ 2 ( y j ? μ k ) 2 ] = ∑ k = 1 K ∑ j = 1 N ( E γ j k ) log ? α k + ∑ j = 1 N ( E γ j k ) [ log ? ( 1 2 π ) ? log ? σ k ? 1 2 σ 2 ( y j ? μ k ) 2 ] \begin{aligned}Q(\theta,\theta^{(i)}) =&E[\log P(y,\gamma|\theta)|y,\theta^{(i)}]\\ =&\color{green}E\color{black}{\sum_{k=1}^K{\color{red}n_k\color{black}\log \alpha_k+\color{blue}\sum_{j=1}^N\gamma _{jk}\color{black}[\log(\frac{1}{\sqrt{2\pi}})-\log \sigma _k-\frac{1}{2\sigma^2(y_j-\mu_k)^2}]}}\\ =&\color{green}E\color{black}{\sum_{k=1}^K{\color{red}\sum_{j=1}^N\gamma_{jk}\color{black}\log \alpha_k+\color{blue}\sum_{j=1}^N\gamma _{jk}\color{black}[\log (\frac{1}{\sqrt{2\pi}})-\log \sigma _k-\frac{1}{2\sigma^2(y_j-\mu_k)^2}]}}\\ =&\sum_{k=1}^K{\color{red}\sum_{j=1}^{N}(\color{green}E\color{red}\gamma_{jk})\color{black}\log \alpha_k+\color{blue}\sum_{j=1}^N(\color{green}E\color{blue}\gamma _{jk})\color{black}[\log (\frac{1}{\sqrt{2\pi}})-\log \sigma _k-\frac{1}{2\sigma^2(y_j-\mu_k)^2}]}\\ \end{aligned} Q(θ,θ(i))====?E[logP(y,γ∣θ)∣y,θ(i)]Ek=1∑K?nk?logαk?+j=1∑N?γjk?[log(2π?1?)?logσk??2σ2(yj??μk?)21?]Ek=1∑K?j=1∑N?γjk?logαk?+j=1∑N?γjk?[log(2π?1?)?logσk??2σ2(yj??μk?)21?]k=1∑K?j=1∑N?(Eγjk?)logαk?+j=1∑N?(Eγjk?)[log(2π?1?)?logσk??2σ2(yj??μk?)21?]?
γ ^ j k = E ( γ j k ∣ y , θ ) = P ( γ j k = 1 ∣ y , θ ) = P ( γ j k = 1 , y j ∣ θ ) ∑ k = 1 K P ( γ j k = 1 , y j ∣ θ ) = P ( y j ∣ γ j k = 1 , θ ) P ( γ j k = 1 ∣ θ ) ∑ k = 1 K P ( y j ∣ γ j k = 1 , θ ) P ( γ j k = 1 ∣ θ ) = α k ? ( y j ∣ θ k ) ∑ k = 1 K α k ? ( y j ∣ θ k ) \begin{aligned}\hat \gamma _{jk}= &\color{purple}E(\gamma_{jk}|y,\theta)=P(\gamma_{jk}=1|y,\theta)\\=&\frac{P(\gamma_{jk}=1,y_j|\theta)}{\sum_{k=1}^KP(\gamma_{jk}=1,y_j|\theta)}\\=&\frac{P(y_j|\color{red}\gamma_{jk}=1,\theta\color{black})\color{green}P(\gamma_{jk}=1|\theta)}{\sum_{k=1}^KP(y_j|\gamma_{jk}=1,\theta)P(\gamma_{jk}=1|\theta)}\\=&\frac{\color{green}\alpha_k\color{black}\phi(y_j|\color{red}\theta_k)}{\sum_{k=1}^K\alpha_k\phi(y_j|\theta_k)}\end{aligned} γ^?jk?====?E(γjk?∣y,θ)=P(γjk?=1∣y,θ)∑k=1K?P(γjk?=1,yj?∣θ)P(γjk?=1,yj?∣θ)?∑k=1K?P(yj?∣γjk?=1,θ)P(γjk?=1∣θ)P(yj?∣γjk?=1,θ)P(γjk?=1∣θ)?∑k=1K?αk??(yj?∣θk?)αk??(yj?∣θk?)??
這部分內容就是搬運了書上的公式,有幾點說明:
- 注意這里 E ( γ j k ∣ y , θ ) E(\gamma_{jk}|y,\theta) E(γjk?∣y,θ),記為 γ ^ j k \hat\gamma_{jk} γ^?jk?, 對應了E步求的期望中的一部分。
- 對應理解一下上面公式中的紅色,藍色和綠色部分,以及 γ ^ j k \hat\gamma_{jk} γ^?jk?中紅色和綠色的對應關系
- 這里用到了 n k = ∑ j = 1 N γ j k n_k=\sum_{j=1}^N\gamma_{jk} nk?=∑j=1N?γjk?
- γ ^ j k \hat \gamma_{jk} γ^?jk?為分模型 k k k對觀測數(shù)據(jù) y j y_j yj?的響應度。這里,紫色標記的第一行參考伯努利分布的期望。
Q ( θ , θ ( i ) ) = ∑ k = 1 K n k log ? α k + ∑ j = 1 N γ ^ j k [ log ? ( 1 2 π ) ? log ? σ k ? 1 2 σ k 2 ( y j ? μ k ) 2 ] Q(\theta,\theta^{(i)})=\sum_{k=1}^Kn_k\log \alpha_k+\sum_{j=1}^N\hat \gamma_{jk}\left[\log \left(\frac{1}{\sqrt{2\pi}}\right)-\log \sigma_k-\frac{1}{2\sigma_k^2}(y_j-\mu_k)^2\right] Q(θ,θ(i))=k=1∑K?nk?logαk?+j=1∑N?γ^?jk?[log(2π?1?)?logσk??2σk2?1?(yj??μk?)2]
其中 i i i表示第 i i i步迭代
- 寫出 Q Q Q 函數(shù)在推導的時候有用,但是在程序計算的時候,E步需要計算的就是 γ ^ j k \hat\gamma_{jk} γ^?jk?,M步用到了這個結果。其實抄公式沒有什么意義,主要是能放慢看公式的速度。和圖表一樣,公式簡潔的表達了很多信息,公式中也許更能體會到數(shù)學之美。
3. M步
求函數(shù) Q ( θ , θ ( i ) ) Q(\theta,\theta^{(i)}) Q(θ,θ(i))對 θ \theta θ的極大值,分別求 σ , μ , α \sigma, \mu, \alpha σ,μ,α
θ ( i + 1 ) = arg ? max ? θ Q ( θ , θ ( i ) ) \theta^{(i+1)}=\arg\max_\theta Q(\theta,\theta^{(i)}) θ(i+1)=argθmax?Q(θ,θ(i))
- arg ? max ? \arg\max argmax 就是求Q的極值對應的參數(shù) θ \theta θ,如說是離散的,遍歷所有值,最大查找,如果是連續(xù)的,偏導為零求極值。
- ? Q ? μ k = 0 , ? Q ? σ 2 = 0 \frac {\partial Q}{\partial \mu_k}=0, \frac {\partial{Q}}{\partial{\sigma^2}}= 0 ?μk??Q?=0,?σ2?Q?=0 得到 μ ^ k , σ ^ k 2 \hat\mu_k, \hat \sigma_k^2 μ^?k?,σ^k2?
- ∑ k = 1 K α k = 1 , ? Q ? α k = 0 \sum_{k=1}^K\alpha_k=1, \frac{\partial{Q}}{\partial{\alpha_k}}=0 ∑k=1K?αk?=1,?αk??Q?=0 得到 α k \alpha_k αk?
4. 停止條件
重復以上計算,直到對數(shù)似然函數(shù)值不再有明顯的變化為止。
如何應用
GMM在聚類中的應用
使用EM算法估計了GMM的參數(shù)之后,有新的數(shù)據(jù)點,怎么計算樣本的類別的?
在機器學習[^5]中有一些關于聚類的表述,摘錄這里:
Gaussian mixture modeling is among the popular clustering algorithms. The main assumption is that the points, which belong to the same cluster, are distributed according to the same Gaussian distribution(this is how similarity is defined in this case), of unknown mean and covariance matrix.
Each mixture component defines a different cluster. Thus, the goal is to run the EM algorithm over the available data points to provide, after convergence, the posterior probabilities P ( k ∣ x n ) , k = 1 , 2 , . . . , K , n = 1 , 2 , . . . , N P(k|x_n), k=1,2,...,K, n=1,2,...,N P(k∣xn?),k=1,2,...,K,n=1,2,...,N, where each k corresponds to a cluster. Then each point is assigned to cluster k k k according to the rule.
Assign x n x_n xn?to cluster k = arg ? m a x P ( i ∣ x n ) , i = 1 , 2 , . . . , K k=\arg max P(i|x_n), i =1,2,...,K k=argmaxP(i∣xn?),i=1,2,...,K
可以參考下scikit-learn的具體實現(xiàn),就是用了argmax,選擇概率最大的那個輸出。
Kmeans
另外,直覺上看,GMM最直觀的想法就是Kmeans,那么:
- 在Kmeans常見的描述中都有距離的概念,對應在算法9.2 的描述中,該如何理解?
這里面距離對應了方差,二范數(shù)平方 - 那么又是怎么在每輪刷過距離之后,重新劃分樣本的分類呢?
這里對應了響應度,響應度對應了一個 j × k j \times k j×k的矩陣,記錄了每一個 y j y_j yj? 對第 k k k個模型的響應度,可以理解為劃分了類別
K怎么定
- 手肘法
- Gap Statistics[^1]
- 第二版中,有對應的描述。 P 267 P_{267} P267?,一般的類別變大的時候,平均直徑會增加,當類別數(shù)超過某個值之后,平均直徑不會變化,這個值可以是最優(yōu)的 k k k