第九章 EM算法及其推廣

• 概述
• EM算法
• EM算法的收斂性
• EM算法實現
• K-Means與高斯混合模型
• • K-Means
  • 高斯混合模型

概述

EM算法是一種迭代算法，1977年由Dempster等人總結提出，用于含隱變量（Hidden variable）的概率模型參數的極大似然估計，或極大后驗概率估計。EM算法的每次迭代由兩步組成：E步，求期望（expectation）；M步，求極大（Maximization）。所以這一算法被稱為期望極大算法（Expectation Maximization Algorithm），簡稱EM算法。本章首先敘述EM算法，然后討論EM算法的收斂性；作為EM算法的應用，介紹高斯混合模型的學習；最后敘述EM算法的推廣–GEM算法。

概率模型有時既含有觀測變量（Observable Variable），又含有隱變量或潛在變量（Latent variable）。如果概率模型的變量都是觀測變量，那么給定數據，可以直接用極大似然估計法，或貝葉斯估計法估計模型參數。但是，當模型含有隱變量時，就不能簡單的使用這些估計方法。EM算法就是含有隱變量的概率模型參數的極大似然估計法，或極大后驗概率估計法。

EM算法與初值的選擇有關，選擇不同的初值可能得到不同的參數估計值。一般地，用Y表示觀測隨機變量的數據，Z表示隱隨機變量的數據。Y和Z連在一起稱為完全數據（complete-data），觀測數據Y又稱為不完全數據（incomplete-data）。假設給定觀測數據Y，其概率分布是$P(Y|\theta )$，其中$\theta$是需要估計的模型參數，那么不完全數據Y的似然函數是$P(Y|\theta )$，對數似然函數是$L(\theta )=logP(Y|\theta )$；假設Y和Z的聯合概率分布是$P(Y,Z|\theta )$，那么完全數據的對數似然函數是$logP(Y,Z|\theta )$。

EM算法通過迭代求$L(\theta )=logP(Y|\theta )$的極大似然估計。每次迭代包括兩步：E步，求期望；M步，求極大化。

EM算法

輸入：觀測變量數據Y，隱變量數據Z，聯合分布$P(Y,Z|\theta )$，條件分布$P(Z|Y,\theta )$
輸出：模型參數 $\theta$
（1）選擇參數的初值${\theta }^{(0)}$開始迭代
（2）E步：記${\theta }^{(i)}$為第i次迭代參數$\theta$的估計值，在第i+1次迭代的E步，計算$$Q(\theta ,{\theta }^{(i)})=E_Z[logP(Y,Z|\theta )|Y,{\theta }^{(i)}]$$
$$=\sum _{Z}logP(Y,Z|\theta )P(Z|Y,{\theta }^{(i)})$$
（3）M步：求使$Q(\theta ,{\theta }^{(i)})$極大化的$\theta$，確定第i+1次迭代的參數的估計值$${\theta }^{(i+1)}=argma{x}_{\theta }Q(\theta ,{\theta }^{(i)})$$
（4）重復第2步和第4步直到收斂。

在構建具體的EM算法時，重要的是定義Q函數。每次迭代中，EM算法通過極大化Q函數來增大對數似然函數$L(\theta )$。

EM算法的收斂性

EM算法在每次迭代后，均提高觀測數據的似然函數值，即
$$P(Y|{\theta }^{(i+1)})\ge P(Y|{\theta }^{(i)})$$
在一般條件下，EM算法是收斂的，但不能保證收斂到全局最優。

EM算法實現

import torch import torch.nn as nn import torch.nn.functional as Fclass AlexNet(nn.Module):def __init__(self, num_classes):super(AlexNet, self).__init__()# AlexNet與LeNet一樣也會同時使用卷積和池化層提取圖像特征# 與LeNet不同的是激活函數換成了ReLUself.conv1 = nn.Conv2d(in_channels=3, out_channels=96, kernel_size=11, stride=4, padding=5)self.pool1 = nn.MaxPool2d(kernel_size=2, stride=2)self.conv2 = nn.Conv2d(in_channels=96, out_channels=256, kernel_size=5, stride=1, padding=2)self.pool2 = nn.MaxPool2d(kernel_size=2, stride=2)self.conv3 = nn.Conv2d(in_channels=256, out_channels=384, kernel_size=3, stride=1, padding=1)self.conv4 = nn.Conv2d(in_channels=384, out_channels=384, kernel_size=3, stride=1, padding=1)self.conv5 = nn.Conv2d(in_channels=384, out_channels=256, kernel_size=3, stride=1, padding=1)self.pool5 = nn.MaxPool2d(kernel_size=2, stride=2)self.fc1 = nn.Linear(in_features=12544, out_features=4096)self.drop_ratio1 = 0.5self.fc2 = nn.Linear(in_features=4096, out_features=4096)self.drop_ratio2 = 0.5self.fc3 = nn.Linear(in_features=4096, out_features=num_classes)def forward(self, x):in_size = x.size(0)x = F.relu(self.conv1(x))x = self.pool1(x)x = F.relu(self.conv2(x))x = self.pool2(x)x = F.relu(self.conv3(x))x = F.relu(self.conv4(x))x = x.view(in_size, -1)x = torch.relu(self.fc1(x))# 在全連接之后使用Dropout抑制過擬合x = nn.Dropout2d(x, self.drop_ratio1)x = torch.relu(self.fc2(x))# 在全連接之后使用Dropout抑制過擬合x = nn.Dropout2d(x, self.drop_ratio2)x = self.fc3(x)return x

K-Means與高斯混合模型

K-Means

• K-Means的目標是將樣本集劃分為K個簇，使得同一個簇內樣本的距離盡可能的小，不同簇之間的樣本距離盡可能大，即最小化每個簇中樣本與質心的距離。K-means屬于原型聚類（prototype-based clustering），原型聚類指聚類結構能通過一組原型刻畫，而原型即為樣本空間中具有代表性的點。在K-means中，這個原型就是每個簇的質心$\mu$。
• 從EM算法的觀點來看，K-Means的參數就是每個簇的質心$\mu$，隱變量為每個樣本的所屬簇。如果事先已知每個樣本屬于哪個簇，則直接求平均即可得到$\mu$。但現實中不知道的情況下，則需要運用EM的思想。
• 假設要K個簇，先隨機選定K個點作為質心$\{{\mu }_1,{\mu }_2,{\mu }_3,?,{\mu }_k\}$

固定${\mu }_k$，將樣本劃分到距離最近的${\mu }_k$所屬的簇中，若用$r_{nk}$表示第n個樣本所屬的簇，則
$$r_{nk}=\{\begin{array}{ll}1,& ifk=argmi{n}_j||X_n?{\mu }_j|{|}^2\\ 2,& otherwise\end{array}$$

固定$r_{nk}$，根據上一步的劃分結果重新計算每個簇的質心。由于我們的目標是最小化每個簇中樣本與質心的距離，可將目標函數表示為$$J=\sum _{n=1}^N{r}_{nk}||X_n?{\mu }_k|{|}^2$$,要最小化J則對${\mu }_k$求導得$$2\sum _{n=1}^N{r}_{nk}(X_n?{\mu }_k)=0$$，則$${\mu }_k=\frac{{\sum }_n{r}_{nk}{X}_n}{{\sum }_n{r}_{nk}}$$，即簇中每個樣本的均值向量。

上面兩步分別更新$r_{nk}$和${\mu }_k$就對應了EM算法中的E步和M步，和EM算法一樣，K-Means每一步都最小化目標函數J，因而可以保證收斂到局部最優值，但是在非凸目標函數的情況下，不能保證收斂到全局最優值。

另外，K-means對每個樣本進行硬分配（Hard Assignment），即只歸為一個簇，然而某些樣本可能處于簇與簇的邊界處，將這些樣本強行分到其中一個簇可能并不能反映確信度，高斯混合模型可以進行軟分配（Soft Assignment），即對每個樣本劃分的簇進行概率估計。

最后總結一下K-Means算法的優缺點：
優點：

可解釋性比較強

調參的參數僅為簇數K

相對于高斯混合模型而言，收斂速度快，因而常用于高斯混合模型的初始值選擇，K-Means的時間復雜度為$O(N?K?I)$，簇數K和迭代次數I通常遠小于N，所以可優化為$O(N)$，效率較高。

缺點：

• 對離群點敏感。
• K值難以事先選取，交叉驗證不大合適，因為簇越多，目標函數$$\sum _{n=1}^N{r}_{nk}||X_n?{\mu }_k|{|}^2$$就越小。常采用的方法有：

一、拐點法，如下圖K=3就是一個拐點。

二、加入正則化系數$\lambda$，使得$$\sum _{n=1}^N(r_{nk}||X_n?{\mu }_k|{|}^2)+\lambda K$$最小。

• 無法保證收斂到全局最優值，常使用不同的初始值進行多次實驗。也可以通過K-means++算法進行優化，核心思想是選取與已有質心距離較遠的點作為初始值。
• 只能發現球狀的簇。
• 由于采用歐氏距離，無法直接計算類別型變量。

高斯混合模型

高斯混合模型同樣用于聚類，與K-means不同的是高斯混合模型采用概率模型來表達聚類原型。
首先，高斯混合模型（Gaussian Distribution）：對隨機變量x，其概率密度函數可表示為：$$N(x|\mu ,{\sigma }^2)=\frac{1}{\sqrt{(}2\pi {\sigma }^2)}exp(?\frac{(x?\mu {)}^2}{2{\sigma }^2})$$
若x為n維隨機變量，則多元高斯分布（Multivariate Gaussian Distribution）為：$$N(x|\mu ,\Sigma )=\frac{1}{(2\pi {)}^{n/2}|\Sigma {|}^{1/2}}exp(?\frac{1}{2}(x?\mu {)}^T{\Sigma }^{?1}(x?\mu ))$$
其中$\mu$為n維均值向量，$\Sigma$為$n?n$的協方差矩陣，$|\Sigma |$為$\Sigma$的行列式。
很多時候我們發現單個高斯分布無法很好地描述數據的性質，如下圖數據分為兩個簇，如果使用兩個高斯分布明顯能更好地描述數據結構。

因此沿著這個思路就誕生了高斯混合模型（Mixture of Gaussian），本質上是K個高斯分布的線性組合，這樣靈活性大增，能描述更多樣的分布：$$p(x)=\sum _{k=1}^K{\pi }_{k}N(x|{\mu }_k,{\Sigma }_k)$$
其中，$0\le {\pi }_k\le 1$為混合系數，滿足$$\sum _{k=1}^K{\pi }_k=1$$

下面以EM算法的角度看待高斯混合模型。EM算法是一種對含有隱變量的概率模型的極大似然估計，通常隱變量Z未知，而實際知曉的只有觀測變量X。而對于高斯混合模型來說，通過采樣得到的樣本，卻不知道每個樣本來自哪個樣本，這就是高斯混合模型的隱變量。

圖（a）是依照完全數據的聯合分布$p(x,z)$作圖，每個點依照其所屬于的第K個類別標記顏色，這樣本的聚類屬于硬分配。圖（b）則不考慮隱變量Z，僅依照不完全數據x直接作圖；圖（c）則考慮了每個樣本每個樣本來自于各個類別的后驗概率，這樣一些在簇中間得的點的顏色是三種顏色的混合，表明這些點來自于每個簇的概率比較接近，即軟分配。

高斯混合模型的優缺點：
優點：

• 相對于K-Means更具一般性，能形成各種不同大小和形狀的簇。K-Means可視為高斯混合聚類中每個樣本僅指派給一個混合成分的特例，且各混合成分協方差相等，均為對角矩陣${\sigma }^{2}I$。
• 僅使用少量的參數，就能較好地描述數據的特性。

缺點：

• 高斯混合模型的計算量較大且收斂較慢，因此先對樣本集進行K-Means聚類，依據得到的各個簇來確定高斯混合模型的初始值，其中質心即為均值向量，協方差矩陣為每個簇中樣本的協方差矩陣，混合系數為每個簇中樣本占總體樣本的比例。
• 分模型數量難以事先選擇，但可以通過劃分驗證集來比較。
• 對異常點敏感。
• 數據量少時效果不好。

參考文獻
1.https://blog.csdn.net/weixin_37763870/article/details/103012009
2.https://www.cnblogs.com/massquantity/p/9416109.html

總結

以上是生活随笔為你收集整理的机器学习理论《统计学习方法》学习笔记：第九章 EM算法及其推广的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。