k-means 與高斯混合模型：沒有標籤時怎麼分群｜Stanford CS229 第 9 堂

🌏 English version

影片狀態：已附影片。 這篇依 Stanford Online 公開的 Spring 2026 第 9 堂錄影的英文字幕寫成，公式記號對照 2026 主講義第 10 章與第 11 章前半；沒看到板書畫面，講者手繪的圖只能靠口述還原。

這是 Stanford CS229 導讀系列的第 9 堂，講者是 Chris Ré。上一堂講完反向傳播，監督式學習告一段落；這一堂開始拿掉標籤。需要的先備是高斯分布的密度函數、貝氏定理，以及第 5 堂的高斯判別分析（GDA）：這堂的 M-step 幾乎就是 GDA 的參數估計。讀完之後你應該能手算一輪 k-means 和一輪 EM，說得出兩者各自保證什麼、不保證什麼，並看懂 Jensen 不等式在 EM 裡負責哪一步。

影片標題的「non-EM」容易誤會。這堂其實已經把 GMM 的 E-step 和 M-step 公式寫出來，也畫了 EM 的整體圖像；沒做的是「為什麼這兩步是在做最大概似估計」的推導，那是第 10 堂的事。

沒有標籤之後，問題本身變得不明確

（錄影 00:00–06:20）

監督式學習的圖很好畫：平面上有正例和負例，目標是找一條線把它們分開。標籤給了一個很強的結構，「好的答案」只有一種意思。把標籤擦掉之後，同一批點還在，但你要的是「描述這批資料的結構」，例如裡面有幾團、各在哪裡。這個目標沒有唯一的正確答案。

講者把代價說得很直接：非監督式學習要做更強的假設（例如假設資料真的是某個生成過程產生的），同時只能接受更弱的保證。第 5 堂的 GDA 是對照組：GDA 也在替資料建高斯模型，但每個點屬於哪一類是已知的。這堂要處理的，就是把那個類別標籤拿掉之後還能做什麼。

他也先講了看這堂課的角度（02:00 前後）：

The algorithms, you could just look up in five minutes. But why we think about these algorithms, why we pick them, that's what I want you thinking about during this lecture and next.

所以後面每次遇到「k 怎麼選」「分出來的群有沒有意義」這類問題，他的回答都會繞回建模假設。

k-means：指派和取平均交替做

（錄影 06:20–13:55）

輸入是 $n$ 個沒有標籤的點 $x^{(1)},\ldots,x^{(n)}\in\mathbb{R}^d$ 和一個正整數 $k$。輸出是每個點的群編號 $c^{(i)}\in\{1,\ldots,k\}$，$c^{(i)}=j$ 的意思是第 $i$ 個點分到第 $j$ 群。

演算法另外引進 $k$ 個群中心 $\mu_1,\ldots,\mu_k$，它們是同一個空間裡的點。先隨機放好，然後重複兩步：

指派：每個點找離自己最近的中心。

$$c^{(i)} := \arg\min_j \lVert x^{(i)}-\mu_j\rVert^2$$

更新中心：每個中心搬到「分給它的那些點」的算術平均。

$$\mu_j := \frac{\sum_{i=1}^n \mathbf{1}\{c^{(i)}=j\}\,x^{(i)}}{\sum_{i=1}^n \mathbf{1}\{c^{(i)}=j\}}$$

距離取不取平方不影響指派結果，因為只是在比誰比較小；平方是留給後面的目標函數用的。停止條件很自然：如果某一輪的指派跟上一輪完全相同，中心也就不會再動，繼續跑只是原地重複，可以停了。講者補充實務上更常見的做法是跑固定步數就收工（20:30 前後）。

課堂上有人問：兩個中心最後停的位置互換，有沒有差？沒有差。沒有標籤的時候，「第 1 群」和「第 2 群」只是編號，重要的是中心落在對的地方。

手算一次

以下是本文自擬的例子，不是課堂內容。六個一維的點 $1, 2, 4, 7, 9, 10$，$k=2$，故意把初始中心放得很差：$\mu_1=1$，$\mu_2=2$。表中的 $J$ 是所有點到自己那一群中心的平方距離總和，下一節會用到。

步驟	第 1 群	第 2 群	$\mu_1$	$\mu_2$	$J$
指派	1	2, 4, 7, 9, 10	1	2	142
更新中心	1	2, 4, 7, 9, 10	1	6.4	45.2
指派	1, 2	4, 7, 9, 10	1	6.4	26.84
更新中心	1, 2	4, 7, 9, 10	1.5	7.5	21.5
指派	1, 2, 4	7, 9, 10	1.5	7.5	15.5
更新中心	1, 2, 4	7, 9, 10	2.33	8.67	9.33
指派	1, 2, 4	7, 9, 10	2.33	8.67	9.33

拿第二列驗算：$\mu_2=(2+4+7+9+10)/5=6.4$，$J=0+4.4^2+2.4^2+0.6^2+2.6^2+3.6^2=45.2$。第三列裡 $x=2$ 離 $\mu_1=1$ 的距離是 1，離 $\mu_2=6.4$ 的距離是 4.4，所以改投第 1 群，$J$ 少掉 $4.4^2-1^2=18.36$。

最後一次指派沒有任何點換群，演算法停止。兩件事值得注意：$J$ 每一步都在變小或持平，從 142 一路降到 9.33；而 $x=4$ 這個夾在中間的點，到第三輪才被拉回左邊那一群。

為什麼一定會停，停下來的地方又為什麼不一定最好

（錄影 13:55–21:30）

講者問全班：這個演算法會不會停？一位學生的回答在字幕裡不完整，講者轉述的大意是：分群是確定性的，可能的分法遲早會走完。講者說方向對，但少了一塊：有限多種分法並不排除在幾種分法之間來回跳。補上那一塊的是一個會單調下降的量，他只說了結論，叫大家去看講義的論證。這裡把它走完。

定義失真函數（distortion）：

$$J(c,\mu)=\sum_{i=1}^n \lVert x^{(i)}-\mu_{c^{(i)}}\rVert^2$$

指派步驟不會讓 $J$ 變大。 固定 $\mu$，$J$ 是 $n$ 項的和，第 $i$ 項只跟 $c^{(i)}$ 有關。每一項各自挑最小的，總和就是在固定 $\mu$ 之下對 $c$ 的最小值。

更新步驟不會讓 $J$ 變大。 固定 $c$，把分到第 $j$ 群的點集合記為 $S_j$，$J$ 裡跟 $\mu_j$ 有關的只有 $\sum_{i\in S_j}\lVert x^{(i)}-\mu_j\rVert^2$。對 $\mu_j$ 取梯度並設為零：

$$\nabla_{\mu_j}\sum_{i\in S_j}\lVert x^{(i)}-\mu_j\rVert^2=-2\sum_{i\in S_j}\bigl(x^{(i)}-\mu_j\bigr)=0 \quad\Longrightarrow\quad \mu_j=\frac{1}{|S_j|}\sum_{i\in S_j}x^{(i)}$$

這是 $\mu_j$ 的二次函數，開口向上，所以這個解是最小值。「取平均」因此有了來歷：在平方距離之下，平均就是讓群內距離總和最小的那個點。講義把這兩步合起來稱為對 $J$ 的座標下降（coordinate descent）。

所以會停。 講義寫到「$J$ 單調下降，所以 $J$ 的值會收斂」為止，下面有限步的論證是本文補的。先講定一個細節：指派時如果某個點到兩個中心一樣近，就留在原來那一群（平手不換），並假設沒有哪一群變成空的。這樣只要某一輪的指派跟上一輪不同，就一定有點換到嚴格更近的中心，$J$ 嚴格下降，接下來的更新步驟也不會把它加回去。另一方面，一種分法對應的中心就是各群的平均，是確定的，更新後的 $J$ 值也跟著確定。假如同一種分法先後出現兩次，兩次的 $J$ 應該相同，可是中間每一輪指派都有變、$J$ 一路嚴格下降，兩者矛盾。所以每種分法最多出現一次，分法最多 $k^n$ 種，演算法一定在有限步內走到「指派不變」而停下。拿掉平手不換這條規則，論證就不成立：講義提到的理論上例外，正是幾種分法的 $J$ 剛好相等、演算法在它們之間來回跳，講義說實務上幾乎遇不到。

講者提醒這個論證沒說下降多快，可能非常慢（15:25 前後）。有學生擔心資料很散的時候，中心會為了邊緣的幾個點拉來拉去；單調性保證不會無止盡地這樣下去，只是沒保證很快結束。

局部最佳與初始化

第二個問題：停下來的地方是不是 $J$ 的全域最小？不是。講者的論據是找出 k-means 的最佳解是 NP-hard 問題，一個每步都很便宜的演算法如果總能找到最佳解會很可疑。實際情況是 $J$ 有多個局部最小值，演算法會卡在其中一個。

本文自擬一個例子：四個點 $(0,0)$、$(0,1)$、$(4,0)$、$(4,1)$，$k=2$。左右分的中心是 $(0,0.5)$ 和 $(4,0.5)$，每個點離中心 0.5，$J=4\times0.25=1$。上下分的中心是 $(2,0)$ 和 $(2,1)$，每個點離自己的中心 2，離另一個中心 $\sqrt{5}\approx2.24$，所以沒有點想換群，演算法停在這裡，$J=4\times4=16$。兩種都是演算法的不動點，後者的 $J$ 是前者的 16 倍。

既然演算法的兩個步驟都是確定性的，結果不同只可能來自一個地方：一開始隨機放中心的那一步。這就是初始化重要的原因，也是「多跑幾次不同起點、挑 $J$ 最小的」這個常見做法的由來。

講者接著介紹 k-means++（18:30 前後）：史丹佛的研究生提出一種挑起點的方式，對任何資料都能證明某個近似比（approximation ratio），也就是解的成本與最佳成本的比值有上界。他說這個方法現在是 Python 套件 scikit-learn 的預設。scikit-learn 的 KMeans 文件裡，init 的預設值確實是 'k-means++'。本文補充：k-means++ 的作者是 David Arthur 與 Sergei Vassilvitskii，論文發表於 2007 年；字幕在這裡出現的「Vasily」是在唸後者的姓氏。

講者自己替這段下的結論不在成本本身，他認為成本未必是有意義的結構，重點是：初始化有影響，而且有聰明的做法。

什麼時候跑 k-means 才有意義，k 又怎麼選

（錄影 21:30–29:40）

這一段幾乎全是學生提問帶出來的，沒有公式，卻是這堂課最接近實務的部分。

資料沒有結構時。 有學生把話題接到高維空間。講者先提醒高維的直覺很怪，隨機點的最近鄰和最遠鄰距離差不多。然後回答核心問題：對一團沒有結構的隨機點跑 k-means 是很奇怪的事（22:33 前後）。

If you have a spray of points that have no structure to them, k-means will return something, but it won't be meaningful.

k-means 永遠會回傳 $k$ 個群，它不會告訴你這些群是不是真的。講者舉他當天聽到的演講當例子：基因表現的分群之所以有意義，是因為生物學上相信同源基因應該聚在一起，而且有別的方法可以檢驗。他歸納出兩種正當用法：對資料取得描述性的感覺，或者你從別處知道裡面真的有群。

k 怎麼選。 講者畫了一張圖，從口述推測是四小團點、兩兩靠近。說有兩群可以，說有四群也可以，三群反而不知道該怎麼切。選 $k$ 是在對世界下判斷：「事件發生與沒發生的地方」是兩群，「我知道有五個資料來源」是五群。

有學生提議用平均成本比較不同的 $k$。講者反問全班這樣比有什麼問題，接著說 $k$ 愈大、群切得愈細，但那不見得真的比較好。用上一節的 $J$ 來說（本文補充）：最佳的 $J$ 隨 $k$ 只降不升，極端情況每個點自成一群，$J=0$，所以光看成本永遠會選最大的 $k$。另一位學生問能不能找成本曲線的轉折點。講者承認文獻裡有這類檢定，但他自己的經驗是幫助不大（29:00 前後）：

I'm just telling you intuitively I haven't found them to be particularly useful in my own work.

他比較相信模型參數以外的輔助資訊，例如你事先知道群應該長成什麼形狀。他也預告下一堂的 PCA 有一個真正好用的適配度指標，跟特徵值解釋了多少變異數有關。這一段裡他有一句話可以當總結（24:34 前後）：「Machine learning only works under assumptions.」

高斯混合模型：把「屬於哪一群」改成機率

（錄影 29:40–36:20）

講者對第二個主題的介紹是（29:38）：

This is basically going to be k-means with a little bit of annoying math and Bayes' rule.

他用的例子來自華盛頓大學的朋友：望遠鏡拍一塊天區，底片上每個 × 是一顆被記錄到的光子，位置是平面上的 $(x,y)$。天上有幾個光源，有的（他姑且稱為類星體）打出來的光子又多又集中，有的散得很開、形狀像壓扁的盤子、強度也比較低。目標是把每顆光子歸給某個光源。

跟 k-means 的差別在邊界上的點。k-means 逼你做硬指派：這個點是第 1 群，沒有第二句話。高斯混合模型（Gaussian mixture model，GMM）允許你說「這個點六成來自光源 1、四成來自光源 2」，也就是替每個點算一個長度為 $k$ 的機率向量 $P(z^{(i)}=j)$。這叫軟指派。

這個模型的假設有三條：

• 光源個數 $k$ 已知，跟 k-means 一樣。
• 每個光源的形狀是高斯，由平均 $\mu_j$ 和共變異數 $\Sigma_j$ 描述；每個光源可以有自己的形狀。高斯的等高線是圓或可以旋轉的橢圓，講者提到球形、對角、完整共變異數三種。
• 每個光源各產生多少點是未知的，要從資料裡學。

一維的生成模型與隱變數

（錄影 36:20–49:30）

為了少寫符號，講者改用一維。模型先講「資料是怎麼來的」：

1. 丟一枚不公平的硬幣決定來源：$z^{(i)}\sim\text{Multinomial}(\phi)$，$\phi_j\ge0$，$\sum_j\phi_j=1$，$P(z^{(i)}=j)=\phi_j$。例如 $\phi=(0.6,0.4)$。
2. 到那個來源的高斯去抽一個點：$x^{(i)}\mid z^{(i)}=j\sim\mathcal{N}(\mu_j,\sigma_j^2)$。

兩步合起來是聯合機率：

$$P(x^{(i)},z^{(i)})=P(x^{(i)}\mid z^{(i)})\,P(z^{(i)})$$

我們只看得到數線上的點 $x^{(i)}$，看不到每個點是哪個來源抽出來的。$z^{(i)}$ 因此叫隱變數（latent variable）：假設它存在，但沒有直接觀測到。講者說「假設有 $z$」實質上就等於「假設存在 $k$ 個群」（45:00 前後；他的用詞是 morally，意思是精神上等價）。要估計的參數是 $\phi$、$\mu$、$\sigma^2$。

如果看得到 $z$。 那每個點都有顏色，問題就退回 GDA：把同色的點收集起來，各自算比例、平均、變異數。講者強調這堂真正新的只有一件事，就是沒有標籤，其餘零件前面都學過。有學生問是不是要像 GDA 那樣共用同一個變異數，答案是不用，每個來源的形狀可以不同。

沒有 $z$ 怎麼辦。 講者請全班猜。拼出來的方案是：先有一個對群的猜測，用它算每個點屬於各群的機率，再用這些機率重新估群的參數，來回做。骨架跟 k-means 一樣，只是「離哪個中心近」換成「在哪個來源底下比較可能」。

$\phi$ 的作用。 有學生問 $\phi$ 怎麼影響估計。講者做了一個思想實驗（47:00 前後）：有一個點剛好落在兩條高斯曲線的交點，單看密度是五五波。如果你知道來源 2 產生的資料是來源 1 的 100 倍，你會猜它來自哪裡？全班回答來源 2。他說，你剛剛做的推論就是貝氏定理。

本文替這個思想實驗補上數字（自擬）：$\mu_1=0$、$\mu_2=4$、兩邊 $\sigma^2=1$，交點在 $x=2$，兩個密度都是 $\mathcal{N}(2;0,1)=\mathcal{N}(2;4,1)\approx0.054$。若 $\phi=(0.5,0.5)$，來自來源 2 的機率是 0.5。若 $\phi=(1/101,\,100/101)$：

$$P(z=2\mid x=2)=\frac{\frac{100}{101}\times0.054}{\frac{1}{101}\times0.054+\frac{100}{101}\times0.054}=\frac{100}{101}\approx0.990$$

密度相同的時候，判斷完全交給 $\phi$。

稍早（43:00 前後）回答另一個關於 $\phi$ 的提問時，講者順帶澄清 $\phi$ 在這裡不算事前機率（prior）：如果有人直接告訴你 90/10，那才是事前知識；這裡 $\phi$ 是要從資料估出來的參數。

GMM 的 EM：E-step 是貝氏定理，M-step 是加權平均

（錄影 49:30–59:20）

演算法的名字先放上來，為什麼叫 Expectation 和 Maximization 要到下一堂才清楚。

E-step：猜隱變數。 給定目前的參數 $\phi,\mu,\sigma^2$，對每個點 $i$ 和每個來源 $j$，算

$$w_j^{(i)} := P\bigl(z^{(i)}=j\mid x^{(i)};\phi,\mu,\sigma^2\bigr)$$

模型給的是正向的 $P(x\mid z)$，要的卻是反向的 $P(z\mid x)$。拆三步：

$$\begin{aligned} P(z^{(i)}=j\mid x^{(i)}) &=\frac{P(x^{(i)},z^{(i)}=j)}{P(x^{(i)})} \\ &=\frac{P(x^{(i)}\mid z^{(i)}=j)\,P(z^{(i)}=j)}{\sum_{l=1}^{k}P(x^{(i)}\mid z^{(i)}=l)\,P(z^{(i)}=l)} \\ &=\frac{\phi_j\,\mathcal{N}(x^{(i)};\mu_j,\sigma_j^2)}{\sum_{l=1}^{k}\phi_l\,\mathcal{N}(x^{(i)};\mu_l,\sigma_l^2)} \end{aligned}$$

第一行是條件機率的定義。第二行分子用模型的分解，分母把 $x^{(i)}$ 的機率寫成對所有可能來源的加總，也就是把隱變數邊際化掉。第三行把模型的兩個零件代進去：$P(z=j)=\phi_j$，$P(x\mid z=j)$ 是高斯密度。最後這個式子裡每一項都能從目前的參數直接算出來。

M-step：用猜測更新參數。 把 $w_j^{(i)}$ 當成「第 $i$ 個點有多少比例算在第 $j$ 個來源」：

$$\phi_j := \frac{1}{n}\sum_{i=1}^n w_j^{(i)},\qquad \mu_j := \frac{\sum_{i=1}^n w_j^{(i)}x^{(i)}}{\sum_{i=1}^n w_j^{(i)}}$$

講者的讀法是：如果 $w$ 只有 0 和 1，$\phi_j$ 就是第 $j$ 群佔全部點的比例，$\mu_j$ 就是 k-means 的群中心。現在一個點可以半個算這邊、半個算那邊，於是比例變成期望的點數除以 $n$，平均變成加權平均。k-means 不需要估 $\phi$，GMM 需要。

學生指出他漏了變異數。他說做法相同，是加權的經驗估計，課堂上沒寫式子。依主講義第 11.1 節（一維時 $\Sigma_j$ 就是 $\sigma_j^2$）：

$$\Sigma_j := \frac{\sum_{i=1}^n w_j^{(i)}\bigl(x^{(i)}-\mu_j\bigr)\bigl(x^{(i)}-\mu_j\bigr)^{\top}}{\sum_{i=1}^n w_j^{(i)}}$$

然後回到 E-step，反覆做。講者說這三條更新式現在看起來像是憑感覺寫的，下一堂會推導它們為什麼是對的。

手算一輪 EM

以下是本文自擬的例子。同樣六個點 $1,2,4,7,9,10$，$k=2$，初始參數 $\phi=(0.5,0.5)$，$\mu=(2,8)$，$\sigma_1^2=\sigma_2^2=4$。

E-step。 因為兩邊的 $\phi$ 和 $\sigma^2$ 相同，會在分子分母消掉，只剩指數項。以 $x=4$ 為例：

$$w_1=\frac{e^{-(4-2)^2/8}}{e^{-(4-2)^2/8}+e^{-(4-8)^2/8}}=\frac{e^{-0.5}}{e^{-0.5}+e^{-2}}=\frac{1}{1+e^{-1.5}}\approx0.818$$

六個點全部算完：

$x$	$w_1$	$w_2$
1	0.998	0.002
2	0.989	0.011
4	0.818	0.182
7	0.047	0.953
9	0.002	0.998
10	0.001	0.999

M-step。 兩欄各自加總得到 $2.855$ 和 $3.145$，所以 $\phi=(0.476,\,0.524)$。平均是

$$\mu_1=\frac{0.998\times1+0.989\times2+0.818\times4+0.047\times7+0.002\times9+0.001\times10}{2.855}\approx2.314$$

同樣算出 $\mu_2\approx8.391$，再代變異數的式子得 $\sigma_1^2\approx1.87$、$\sigma_2^2\approx2.83$。（表中數字是四捨五入後的值，照表手算會在第三位小數有出入；上面的結果是用未捨入的值算的。）

這個結果代表什麼。 k-means 在同一批資料上停在 $\mu=(2.33,\,8.67)$。EM 的 $\mu_2$ 偏左到 8.39，是因為 $x=4$ 有 18% 的份量算在來源 2，把它往左拉；k-means 裡這個點整個歸左邊。兩個來源的變異數也都從 4 往下修，模型發現資料比初始猜測集中。再往下跑，log-likelihood（定義在最後一節）依序是 $-14.94$（初始）、$-14.22$、$-14.03$、$-13.99$，每一輪都上升。這個單調上升在這裡只是觀察到的現象，原因是最後一節要講的事。

講者還口頭描述了一個 k-means 沒有的現象（58:30 前後）：因為形狀也在更新，如果某個來源被估成很窄的橢圓，窄的那個方向上密度隨距離掉得很快，原本看起來不遠的點在機率上會被踢到別的來源。在 GMM 裡，遠近要看共變異數，不能只看歐氏距離。

稍早有學生問，如果某個來源沒有分到點會怎樣。講者說跑過算式就會看到，但這堂沒有回頭講。從 M-step 的式子可以讀出（本文的解讀）：該來源的 $\sum_i w_j^{(i)}$ 趨近零，$\phi_j$ 跟著趨近零，而 $\mu_j$ 的分母也趨近零，估計會變得不穩定。

凸函數與 Jensen 不等式

（錄影 59:20–1:09:30）

講者在這裡繞路。理由是下一堂的推導有一步會把期望值「搬進」函數裡面，那一步就是 Jensen 不等式，他希望先把圖畫清楚。

凸集合。 集合 $\Omega$ 是凸的，如果任取其中兩點 $a,b$，連接它們的線段整條都在 $\Omega$ 裡：對所有 $\lambda\in[0,1]$，$\lambda a+(1-\lambda)b\in\Omega$。圓盤是凸的；有凹口的形狀不是。條件是「所有」點對都要成立，找到一對線段跑出去就不算凸。

凸函數。 把函數圖形上方的區域 $\{(x,y):y\ge f(x)\}$ 塗滿（教科書叫 epigraph，講者口頭直接稱它為 graph），如果這個集合是凸的，$f$ 就是凸函數。典型例子是碗狀的 $x^2$。圖形上的兩點 $(a,f(a))$、$(b,f(b))$ 都在這個集合裡，凸集合的定義說它們的連線也在裡面，而「在裡面」的意思是 $y$ 座標不低於函數值：

$$\lambda f(a)+(1-\lambda)f(b)\ \ge\ f\bigl(\lambda a+(1-\lambda)b\bigr)$$

也就是弦在函數圖形的上方。只要有一個 $z$ 讓弦跑到圖形下面，函數就不是凸的。

二階導數判別法。 如果 $f$ 二次可微且處處 $f''(x)\ge0$，則 $f$ 是凸的。（字幕裡講者唸成 f prime，從後面的泰勒展開和講義看是二階導數。）這段板書字幕還原不出細節，以下是本文依他口述的三個要素（泰勒定理帶餘項、一階項消掉、剩下非負的 $c$）重建的版本。

令 $z=\lambda a+(1-\lambda)b$。在 $z$ 附近展開到二階，存在 $\xi_a$、$\xi_b$ 使得

$$\begin{aligned} f(a)&=f(z)+f'(z)(a-z)+\tfrac12 f''(\xi_a)(a-z)^2\\ f(b)&=f(z)+f'(z)(b-z)+\tfrac12 f''(\xi_b)(b-z)^2 \end{aligned}$$

第一式乘 $\lambda$、第二式乘 $1-\lambda$ 再相加。一階項的係數是 $\lambda(a-z)+(1-\lambda)(b-z)=\lambda a+(1-\lambda)b-z=0$，剛好消掉。剩下

$$\lambda f(a)+(1-\lambda)f(b)=f(z)+\underbrace{\tfrac12\Bigl[\lambda f''(\xi_a)(a-z)^2+(1-\lambda)f''(\xi_b)(b-z)^2\Bigr]}_{c\ \ge\ 0}$$

$c$ 非負是因為 $f''\ge0$ 乘上平方項。課堂上有學生指出投影片漏了 $\tfrac12$，講者當場承認。講者把 $f''>0$ 的情況稱為 strongly convex；主講義第 11.2 節用的詞是 strictly convex（嚴格凸），並用它來敘述等號何時成立，讀講義時以這個詞為準。

Jensen 不等式。 對凸函數 $f$ 和隨機變數 $X$：

$$\mathbb{E}[f(X)]\ \ge\ f(\mathbb{E}[X])$$

取最簡單的 $X$：以機率 $\lambda$ 取 $a$，以機率 $1-\lambda$ 取 $b$。那麼 $\mathbb{E}[X]=\lambda a+(1-\lambda)b$，$\mathbb{E}[f(X)]=\lambda f(a)+(1-\lambda)f(b)$，Jensen 不等式一字不差就是上面那條弦的不等式。講者的說法（1:07:40 前後）：

Jensen's inequality is the definition of convexity. Sometimes it's presented as some mysterious consequence.

兩點推到有限多點用歸納法，再推到連續的情況。

凹函數方向相反。 $f$ 是凹函數的意思是 $-f$ 是凸函數，不等式反過來：$\mathbb{E}[f(X)]\le f(\mathbb{E}[X])$。這門課最常用的凹函數是 $\log$，因為要處理的是機率的對數。線性函數既凸又凹，兩個方向都成立，所以是等號，這正是期望值的線性性質。

用數字驗一次（本文自擬）：$X$ 各以一半機率取 1 和 4，$\mathbb{E}[X]=2.5$。

• $f(x)=x^2$（凸）：$\mathbb{E}[f(X)]=(1+16)/2=8.5$，$f(\mathbb{E}[X])=6.25$，$8.5\ge6.25$。
• $f(x)=\log x$（凹）：$\mathbb{E}[\log X]=(0+1.386)/2=0.693$，$\log2.5=0.916$，$0.693\le0.916$。

記法：先平均再取 $\log$ 比較大；把 $\log$ 搬到期望值裡面，得到的是一個比較小的數，也就是下界。

把 EM 看成最大概似：一條貼著的下界

（錄影 1:09:30–1:16:20）

最後七分鐘把 EM 放回熟悉的框架。參數全部打包成 $\theta$，資料的 log-likelihood 是

$$\ell(\theta)=\sum_{i=1}^n\log p(x^{(i)};\theta),\qquad p(x;\theta)=\sum_z p(x,z;\theta)$$

講者問為什麼可以寫成加總。字幕裡學生的回答聽不清楚；依主講義第 11.3 節，前提是 $n$ 筆資料互相獨立，聯合機率是連乘，取對數後變成加總。第二個式子是把隱變數加總掉，講者這裡刻意假設 $z$ 是離散的，講義則註明連續時把加總換成積分。

困難在 $\log$ 裡面包著一個對 $z$ 的加總，直接最大化 $\ell(\theta)$ 不好做。講者畫的圖是這樣：

1. 橫軸是 $\theta$，畫出 $\ell(\theta)$ 這條彎彎曲曲的曲線。從一個猜測 $\theta^{(t)}$ 出發。
2. 造一條替代曲線 $L_t(\theta)$，滿足兩個性質：它處處不高於 $\ell$，而且在目前的位置碰到 $\ell$。

$$L_t(\theta)\le\ell(\theta)\ \ \text{對所有}\ \theta,\qquad L_t(\theta^{(t)})=\ell(\theta^{(t)})$$

3. $L_t$ 是開口向下、比較好最佳化的形狀。找到它的頂點，當成下一個猜測：$\theta^{(t+1)}=\arg\max_\theta L_t(\theta)$。
4. 在 $\theta^{(t+1)}$ 重新造一條 $L_{t+1}$，重複。

對應到兩個步驟：E-step 是給定 $\theta^{(t)}$ 造出 $L_t$；M-step 是給定 $L_t$ 找出 $\theta^{(t+1)}$。講者強調「$L_t$ 比較好最大化」在這個時間點還只是希望，要等下一堂才兌現。

這兩個性質已經足以說明 log-likelihood 不會下降。下面這條鏈是本文依這兩個性質補的，講者只說了圖上會往上爬，講義在第 11.3 節有同樣的論證：

$$\ell(\theta^{(t+1)})\ \ge\ L_t(\theta^{(t+1)})\ \ge\ L_t(\theta^{(t)})\ =\ \ell(\theta^{(t)})$$

第一個不等號用「下界」，第二個用「$\theta^{(t+1)}$ 是 $L_t$ 的最大點」，等號用「在 $\theta^{(t)}$ 貼合」。前面手算例子裡 $-14.94\to-14.22\to-14.03\to-13.99$ 的上升就是這條鏈在起作用。

會到全域最大嗎？ 不會保證。講者給了兩個理由：圖上 $\ell$ 在別處可能高得多，局部往上爬看不到；而且把 $w$ 限制成 0 和 1 時 EM 會退化成 k-means，k-means 已經有局部最佳的問題，EM 不可能倖免。

Jensen 用在哪裡。 課堂到這裡為止，還沒說 $L_t$ 具體長什麼樣。預告一下，依主講義第 11.3 節（式 11.6–11.7），對任何一個 $z$ 上的機率分布 $Q$：

$$\log\sum_z p(x,z;\theta)=\log\sum_z Q(z)\frac{p(x,z;\theta)}{Q(z)}\ \ge\ \sum_z Q(z)\log\frac{p(x,z;\theta)}{Q(z)}$$

中間那個式子是「$\log$ 包著對 $Q$ 的期望值」，不等號就是凹函數版的 Jensen：把 $\log$ 搬進期望值，得到下界。右邊在講義裡叫 ELBO（evidence lower bound）。講者開場提到他的研究生正在替一個擴散式的估計器寫 ELBO（字幕寫成「elbow」），指的是同一個東西。至於 $Q$ 要怎麼選才會貼合、為什麼選出來正好是 E-step 的 $w_j^{(i)}$，是第 10 堂的內容。

自我檢查

1. 手算 k-means。 四個一維的點 $0,2,3,10$，$k=2$，初始 $\mu_1=0$、$\mu_2=3$。跑到停止，寫出每一輪的分群、中心，以及最後的 $J$。

答案：第一輪分成 $\{0\}$、$\{2,3,10\}$，中心 $(0,5)$；第二輪 $\{0,2\}$、$\{3,10\}$，中心 $(1,6.5)$；第三輪 $\{0,2,3\}$、$\{10\}$，中心 $(1.67,10)$；第四輪指派不變，停止。$J=1.67^2+0.33^2+1.33^2+0\approx4.67$。$x=3$ 在第三輪才換群：它離 1 的距離是 2，離 6.5 的距離是 3.5。

2. 解釋收斂。 用自己的話說明為什麼 $J$ 在指派步驟和更新步驟都不會變大，以及為什麼這不代表找到了最好的分群。

判準：指派那步要講到「固定中心，每個點各自挑最近的，各項分別最小」；更新那步要講到「固定分群，平均是讓平方距離和最小的點」（最好能寫出梯度為零那一行）。第二問要舉得出兩個不同的不動點，例如本文的長方形四個點，並指出差別來自初始化。

3. 手算 E-step。 $\mu_1=0$、$\mu_2=4$、$\sigma_1^2=\sigma_2^2=1$，觀測到 $x=1$。分別在 $\phi=(0.5,0.5)$ 和 $\phi=(0.1,0.9)$ 之下算 $w_1$。

答案：密度比是 $e^{-0.5}:e^{-4.5}$。$\phi$ 相等時 $w_1=1/(1+e^{-4})\approx0.982$。$\phi=(0.1,0.9)$ 時 $w_1=1/(1+9e^{-4})\approx0.858$。來源 2 的佔比變成九成，把 $x=1$ 屬於來源 1 的機率從 98% 拉到 86%；這個點離 $\mu_1$ 近很多，所以仍然偏向來源 1。

4. Jensen 的方向。 $X$ 各以一半機率取 2 和 8。比較 $\mathbb{E}[\log X]$ 和 $\log\mathbb{E}[X]$，並說明 EM 為什麼因此得到的是下界而不是上界。

答案：$\mathbb{E}[\log X]=(\log2+\log8)/2=\log4\approx1.386$，$\log\mathbb{E}[X]=\log5\approx1.609$。$\log$ 是凹函數，所以 $\mathbb{E}[\log X]\le\log\mathbb{E}[X]$。log-likelihood 的形式是「$\log$ 包著期望值」，把 $\log$ 搬進去只會變小，所以得到下界；最大化下界才有意義，因為它從下方把真正的目標往上推。

5. 連回 k-means。 如果 E-step 算出來的 $w_j^{(i)}$ 全都是 0 或 1，M-step 的 $\mu_j$ 變成什麼？GMM 還多估了哪些 k-means 沒有的東西？

答案：$\mu_j$ 變成第 $j$ 群所有點的算術平均，跟 k-means 的更新步驟相同。GMM 另外估每個來源的佔比 $\phi_j$ 和形狀 $\Sigma_j$。

對應閱讀

• 主講義第 10 章 Clustering and the k-means algorithm（第 147–149 頁）：演算法、失真函數 $J$、座標下降的論證、局部最佳與多次重跑。課堂只口頭提到 $J$ 單調下降，論證在講義裡。講義沒有 k-means++、NP-hard、怎麼選 $k$、高維與無結構資料這幾段討論，那些只在課堂上。
• 第 11.1 節 EM for mixture of Gaussians（第 150–153 頁）：GMM 的模型定義、$z$ 已知時的最大概似解、E-step 與 M-step 的完整公式（含 $\Sigma_j$）。講義從一般的 $d$ 維寫起；課堂為了簡化改用一維的 $\sigma^2$，並用光子與光源的例子帶入，講義沒有這個例子。
• 第 11.2 節 Jensen's inequality（第 153–154 頁）：講義直接以 $f''\ge0$ 當凸函數的定義並敘述定理，配一張兩點的圖。課堂從凸集合與弦講起，並示範用泰勒展開推出 $f''\ge0$ 蘊含凸性，這段講義沒有。講義多了等號成立的條件（嚴格凸時，若且唯若 $X$ 是常數），這個條件下一堂選 $Q$ 的時候會用到，課堂這次沒提。
• 第 11.3 節 General EM algorithms（第 154 頁起）：課堂只走到 log-likelihood 的定義與下界的圖像，對應式 (11.1)–(11.4) 和「反覆造下界、再最佳化下界」那段文字。ELBO 的推導、$Q$ 的選法與收斂證明都在第 10 堂。

系列導覽：上一堂 第 8 堂：反向傳播｜下一堂 第 10 堂：EM 演算法與 PCA｜課程總覽

課程影片來源

原始影片：Stanford CS229 Machine Learning | Spring 2026 | Lecture 9: K-Means and GMM (non-EM)

• Stanford CS229 Machine Learning｜Spring 2026 播放清單（Stanford Online，17 支）
• CS229 課程官網
• CS229 主講義 main_notes.pdf

查核日期：2026-10-12。

內容核對：已依字幕核對（2026-10-12）：全文依這支影片的英文字幕（約 77 分鐘）逐段對照，引用的英文句子都出自字幕；沒看板書與投影片畫面，講者手繪的圖、泰勒展開那張投影片的確切寫法，以及幾處字幕標為聽不清楚的學生發言，都無法確認。

參考資料

• Stanford CS229 Machine Learning | Spring 2026 | Lecture 9: K-Means and GMM (non-EM)：本文的底本，課堂進行順序、講者說法與引文都來自它的英文字幕。
• CS229 主講義 main_notes.pdf：第 10 章補失真函數與座標下降的論證，第 11.1 節補 $\Sigma_j$ 的更新式，第 11.2–11.3 節補 Jensen 不等式的敘述與下一堂的預告。
• scikit-learn：sklearn.cluster.KMeans：確認 init 的預設值是 'k-means++'（2026-10-12 查詢）。
• Stanford CS229 導讀：課程總覽：系列入口與各堂位置。