這一節(jié)開始我們討論非監(jiān)督學習(Unsupervised Learning)的算法。在監(jiān)督學習算法中，訓練數(shù)據(jù)既包含特征也包含標簽，通常表示為{(x⁽¹⁾, y⁽¹⁾), ..., (x^(m), y^(m))}；而在非監(jiān)督學習中，訓練數(shù)據(jù)只有特征沒有標簽，通常表示為{x⁽¹⁾, ..., x^(m)}。

K-Means算法

聚類(clustering)問題是最常見的非監(jiān)督學習問題。對于一組無標簽數(shù)組，可以用聚類算法將數(shù)據(jù)分成若干相似的“群組”，從而發(fā)掘數(shù)據(jù)中的隱藏結構。

K-Means算法是最常見的一種聚類算法，算法步驟描述如下：

1. 隨機選擇k個中心點(centroids): μ₁, μ₂, ..., μ_k

2. 重復如下過程直到收斂：{
   

   對于每個樣本i，令：
   
   對于每個中心點j，令：

}

在上面的算法中，k表示我們想要聚類的個數(shù)，μ_j表示目前我們對中心點的猜測。算法的第一步是初始化中心點，這個可以通過隨機選擇k個樣本數(shù)據(jù)獲得。算法的第二步是不斷循環(huán)如下兩個過程：首先將樣本x⁽ⁱ⁾“指派”給離它距離最近的中心點μ_j，然后將中心點μ_j更新為所有被“指派”給它的樣本距離的平均值。下圖展示了算法的執(zhí)行過程：

圖(a)表示原始的訓練數(shù)據(jù)。圖(b)表示隨機選取了兩個初始中心點，用記號x表示。圖(c)表示將每個訓練數(shù)據(jù)指派給離它最近的中心點，圖中用不同顏色表示數(shù)據(jù)與中心點的關系。圖(d)表示更新中心點的位置。圖(e)和(f)表示又進行了一輪迭代。

K-Means算法一定可以保證收斂。特別的，我們定義失真函數(shù)(distortion function)：

因此，J函數(shù)表示每個樣本點離它對應中心點的平方和?？梢宰C明，K-Means算法其實就是對J函數(shù)應用坐標下降算法。具體來說，K-Means算法內(nèi)層循環(huán)的第一步是固定μ使c關于J求最小化，第二步是固定c使μ關于J求最小化。因此J是單調(diào)遞減的，J的值必然是收斂的。

由于J函數(shù)不是凸函數(shù)，所以坐標下降法未必能得到全局最優(yōu)解，也就是說K-Means算法可能會得到局部最優(yōu)解。為了防止K-Means算法得出的結果是局部最優(yōu)解，通?？梢杂貌煌某跏贾刀噙\行幾次算法，然后取使得J函數(shù)最小的那個參數(shù)值。

混合高斯模型

這一部分我們介紹使用混合高斯模型進行聚類的算法?；仡櫾诟咚古袆e分析(GDA)模型中，我們假設x是連續(xù)的隨機變量，p(y)服從伯努利分布，p(x|y)服從多元正態(tài)分布，通過極大似然法使得聯(lián)合概率p(x, y)最大，從而求解出模型的參數(shù)。

而在非監(jiān)督學習的設定下，我們沒有y的數(shù)據(jù)，因此我們引入一個隱含(latent)隨機變量z。我們建立聯(lián)合分布p(x⁽ⁱ⁾, z⁽ⁱ⁾) = p(x⁽ⁱ⁾|z⁽ⁱ⁾)p(z⁽ⁱ⁾)，其中p(z⁽ⁱ⁾)服從參數(shù)為φ的多項式分布(p(z⁽ⁱ⁾ = j) = φ_j)，p(x⁽ⁱ⁾|z⁽ⁱ⁾)服從正態(tài)分布N(μ_j, Σ_j)。我們的模型首先讓z⁽ⁱ⁾隨機地從1到k中取值，然后x⁽ⁱ⁾是從k個高斯分布中選擇第z⁽ⁱ⁾個分布，這樣的模型就稱之為混合高斯模型(Mixtures of Gaussians)。由于z⁽ⁱ⁾是不可觀察的隱含變量，這使得我們的計算變得更為困難。

為了計算模型中φ, μ和Σ的值，我們寫出似然函數(shù)：

如果我們通過用求導的方式來求解參數(shù)，我們會發(fā)現(xiàn)這是不可能做到的。

由于z⁽ⁱ⁾是用來表示x⁽ⁱ⁾是來自k個高斯分布中的哪一個的，如果我們知道z⁽ⁱ⁾的取值的話，那么問題就變得簡單了，我們將問題簡化為：

對此似然函數(shù)最大化，我們求得各參數(shù)為：

因此，如果z⁽ⁱ⁾是已知的，那么最大化似然函數(shù)的問題就很簡單了，而且求解參數(shù)的結果和通過GDA求解得到的參數(shù)非常相似。

但是在我們實際問題中，z⁽ⁱ⁾是未知的，那我們應該怎么辦呢？

我們可以采用EM算法。EM算法是一個迭代式的算法，它總共分為兩步。在這個問題中，E步嘗試猜測一個合理的z⁽ⁱ⁾值，M步按照上一步猜測的z⁽ⁱ⁾來更新模型的參數(shù)。在M步，由于我們假設E步猜測的z⁽ⁱ⁾是正確的，因此最大化似然函數(shù)的問題變得簡單了。算法步驟描述如下：

重復如下過程直到收斂：{

E步：對于每個i, j，我們令：

M步：按如下公式更新參數(shù)：

}

在E步中，我們計算的是在給定x⁽ⁱ⁾和其他參數(shù)情況下z⁽ⁱ⁾的后驗概率，根據(jù)貝葉斯公式，我們有：

上式中的p(x⁽ⁱ⁾|z⁽ⁱ⁾ = j; μ,Σ)是通過平均值為μ_j，協(xié)方差為Σ_j的高斯分布在x⁽ⁱ⁾上的概率密度計算得出；p(z⁽ⁱ⁾ = j;φ)的值由φ^(j)計算得出。我們在E步中計算的w_j⁽ⁱ⁾可以認為是對z⁽ⁱ⁾的軟猜測(軟猜測是指猜測的結果是[0,1]之間的概率值，硬猜測是指0或1的取值)。

EM算法和K-Means算法的迭代步驟其實比較類似，不同的是K-Means算法中每次對c⁽ⁱ⁾的更新是硬猜測，而EM中每次對w⁽ⁱ⁾的更新是軟猜測。和K-Means算法相同的是，EM算法也可能得到局部最優(yōu)解，所以用不同的初始參數(shù)迭代會得到更好的結果。

這一部分我們用EM算法的思想講了混合高斯模型問題，后面我們會講更通用的EM算法，以及EM算法是如何保證算法的收斂性的。在講解通用EM算法之前，我們先要介紹一個定理作為預備知識。

Jensen不等式

令f是一個定義域為實數(shù)的函數(shù)。若f是凸函數(shù)(convex function)，則f''(x) >= 0。如果f的定義域是向量，那么凸函數(shù)的條件變?yōu)閒的Hessian矩陣H是半正定矩陣(H >= 0)。如果對于所有的x都有f''(x) > 0，那么我們說f是嚴格凸函數(shù)。對于定義域是向量的情況，如果H是正定矩陣(H > 0)，那么我們說f是嚴格凸函數(shù)。

Jensen不等式(Jensen’s inequality)可表述如下：

令f是凸函數(shù)，X是隨機變量，那么有：E[f(X)] >= f(EX)。如果f是嚴格凸函數(shù)，那么E[f(X)] = f(EX)當且僅當X = E[X]的概率為1(即X是常量)。

由于我們在書寫期望的時候有時候會把括號省略掉，所以上式中的EX是E[X]的縮寫。為了對這個公式有直觀的理解，我們可以用下圖來解釋：

上圖中的曲線表示函數(shù)f，X是一個隨機變量，它有一半的概率取a，有一半的概率取b，所以E[X]介于a和b的中間。另一方面我們可以看到y(tǒng)軸上f(a)，f(b)和f(EX)的值，而E[f(X)]介于f(a)和f(b)的中間。由于凸函數(shù)的特性，很容易看出一定有E[f(X)] >= f(EX)。

事實上很多人會記不清這個不等式的方向，有了上面這個圖的話可以幫助我們更好的記憶。

注意，如果f是凹函數(shù)(concave function)(即f''(x) <= 0或H <= 0)，Jensen不等式也是成立的，只不過不等式的方向變了，即E[f(X)] <= f(EX)。

EM算法

這一節(jié)我們介紹通用的EM算法。假設我們的訓練集是m個互相獨立的樣本{x⁽¹⁾, ..., x^(m)}，我們希望對p(x, z)進行建模，其似然函數(shù)為：

直接通過最大化似然函數(shù)求解參數(shù)是比較困難的。這里z⁽ⁱ⁾是隱含的隨機變量，如果z⁽ⁱ⁾的值是已知的，那么問題將變得簡單。

在這種情況下，EM算法給出了一個高效地求解最大化似然函數(shù)的方法。直接最大化l(θ)可能比較困難，那么我們的策略是不斷地構造l的下界(E步)，然后最大化該下界(M步)。

對于每一個i，令Q_i是z⁽ⁱ⁾的某個分布(Σ_zQ_i(z) = 1, Q_i(z) >= 0; 如果z⁽ⁱ⁾是連續(xù)的，那么Q_i是概率密度函數(shù))，引入Q_i后，我們有：

上式中最后一步的不等式是由于Jensen不等式推導而來。具體來說由于f(x) = log(x)是凹函數(shù)，并且我們把

這一項看成是[p(x⁽ⁱ⁾, z⁽ⁱ⁾; θ)/Q_i(z⁽ⁱ⁾)]關于z⁽ⁱ⁾的期望，所以根據(jù)Jensen不等式：

其中“z⁽ⁱ⁾ ~ Q_i”的下標表示這是關于z⁽ⁱ⁾的期望，而z⁽ⁱ⁾滿足Q_i的分布。綜上我們可以從等式(2)推導出等式(3)。

現(xiàn)在對于任意分布Q_i，等式(3)給出了l(θ)的下界。Q_i可以有很多選擇，而我們應該選擇Q_i使得l(θ)最接近下界，也就是說我們希望選擇Q_i使得Jensen不等式的等號成立。

回顧下使得Jensen不等式等號成立的條件，對照上式可得如下的隨機變量應該是常數(shù)：

其中c代表某個與z⁽ⁱ⁾無關的常數(shù)，我們把它寫成如下的形式：

再加上我們已知Σ_zQ_i(z⁽ⁱ⁾) = 1，因此可推導出：

所以Q_i是在給定x⁽ⁱ⁾和θ兩個參數(shù)下的z⁽ⁱ⁾的后驗概率。

現(xiàn)在我們可以給出EM算法的基本步驟：

重復如下過程直到收斂：{

E步：對于每個i，令：

M步：按如下公式更新參數(shù)：

}

算法中的E步給出了l(θ)的下界函數(shù)，M步是在最大化該下界。當算法收斂時我們便得到了最優(yōu)解。那么這個算法為什么能收斂呢？這里我們簡單證明一下。

假設θ^(t)和θ^(t+1)是EM算法連續(xù)兩次迭代中的參數(shù)，而θ^(t)是滿足Jensen不等式成立的參數(shù)，所以：

而θ^(t+1)是使得l(θ^(t))最大化的參數(shù)，所以有：

因此我們證明了l(θ^(t+1)) >= l(θ^(t))，所以EM算法是單調(diào)遞增的，由此可證算法是收斂的。

另外，如果我們定義：

那么EM算法可以視為將J函數(shù)作坐標上升的過程，其中在E步是固定θ使Q關于J求最大化，M步是固定Q使θ關于J求最大化。

混合高斯模型重述

在給出了通用的EM算法定義后，我們重新推導一下混合高斯模型中的EM算法。前面我們只描述了算法，但沒有證明為什么參數(shù)需要按照給定的公式更新。

證明E步是很簡單的，根據(jù)EM算法中的推導，可得：

而在M步中，我們需要最大化的目標函數(shù)是：

首先固定其他參數(shù)，關于μ作目標函數(shù)最大化，我們先求出目標函數(shù)關于μ的導數(shù)：

將導數(shù)設為0，可得：

這和我們之前給出的結論一致。

接下來我們再來求參數(shù)φ。將和φ有關的項進行合并，我們需要最大化的目標函數(shù)是：

除此之外，我們還有一個約束：所有的φ_j之和為1。為了最優(yōu)化該問題，我們構建拉格朗日算子：

其中β是拉格朗日乘數(shù)，對L求導可得：

將導數(shù)設為0，可得：

另外我們求解β，可得：

將β代入回φ_j式中：

因此，我們推導出了參數(shù)φ。參數(shù)Σ的推導類似，這里就不做證明了。

總結

• 聚類算法是最常見的無監(jiān)督學習算法，而K-Means算法是最常見的聚類算法
• Jensen不等式：令f是凸函數(shù)，X是隨機變量，那么有：E[f(X)] >= f(EX)。如果f是嚴格凸函數(shù)，那么E[f(X)] = f(EX)當且僅當X = E[X]的概率為1(即X是常量)；如果f是凹函數(shù)，那么Jensen不等式也成立，但不等式的方向相反
• EM算法是一個迭代式的算法，分為兩個步驟：E步和M步；EM算法也可以視為將目標函數(shù)作坐標上升的過程，每個步驟都是固定一個參數(shù)并估計另一個參數(shù)
• EM算法和K-Means算法的迭代過程比較類似，不同的是K-Means算法中每次對參數(shù)的更新是硬猜測，而EM中每次對參數(shù)的更新是軟猜測；相同的是，兩個算法都可能得到局部最優(yōu)解，采用不同的初始參數(shù)迭代會有利于得到全局最優(yōu)解
• 混合高斯模型是對單一高斯模型的擴展，可以通過EM算法進行參數(shù)求解

參考資料

• 斯坦福大學機器學習課CS229講義 The K-Means Algorithm | Mixture of Gaussians | The EM Algorithm
• 網(wǎng)易公開課：機器學習課程 雙語字幕視頻