數學雜記2 - 從高斯混合EM推導K-means

為了IA9內容的完整性，我還是趕快把如何從高斯混合EM過渡到K-means的證明補齊吧，免得時間一久不但忘了也懶了😂

　讓我們從置信度開始，它是這樣表示的 $$\gamma(z_{nk})=\frac{\pi_k \mathcal{N}(x_n|\mu_k,\sigma_k^2)}{\sum_{k^\prime}\pi_{k^\prime}\mathcal{N}(x_n|\mu_{k^\prime},\sigma_{k^\prime}^2)}\tag{1}$$ 用來闡明該點$x_n$是屬於第$k$群的可能性，注意分母的$k^\prime$是個dummy variable，並且在上式中的參數捨去了粗體寫法，讀者必須知道它們都可以直接推廣到向量的形式。所以我們便可以計算出第$k$群的中心位置$\mu_k$: $$\mu_k=\frac{1}{N_k}\sum_{n} \gamma(z_{nk})x_n \tag{2}$$ 和 $$N_k=\sum_{n}\gamma(z_{nk}).\tag{3}$$ 由於高斯分佈完整的形式為 $$\mathcal{N}(x_n|\mu_k,\sigma_k^2)=\frac{1}{\sqrt{2\pi}\sigma_k}\exp \left[-\frac{(x_n-\mu_k)^2}{2\sigma_k^2}\right]\tag{4}$$ 並將它代入Eq. (1)稍做整理後得到 $$\gamma(z_{nk})=\frac{\beta_k \exp(-\beta_k^2 \ell_{nk}^2)}{\sum_{k^\prime} \beta_{k^\prime} \exp(-\beta_{k^\prime}^2 \ell_{nk^\prime}^2)},$$ 其中標準差的倒數$\beta_k = 1/\sigma_k$稱做肛…啊不好意思，是剛度 (stiffness) 而$\ell_{nk}$即歐氏距離$\sqrt{(x_n-\mu_k)^2}$，又由於$\pi_k$是個常量 ($z_k$出現的先驗機率) 和我們在意的變數都沒有直接關聯，所以我將他等式中移除並不影響。
　現在我們就證明當剛度趨近無限大時，上述的高斯混合EM會變成K-mean的形式，故有對第$k$群而言 $$\underset{\beta_{k}\to\infty}{\lim}\frac{\beta_{k}\exp(-\beta_{k}^{2}\ell_{nk}^{2})}{\sum_{k^{\prime}}\beta_{k^{\prime}}\exp(-\beta_{k^{\prime}}^{2}\ell_{nk^{\prime}}^{2})}=\underset{\beta_{k}\to\infty}{\lim}\frac{e^{-\beta_{k}^{2}\ell_{nk}^{2}(1-2\beta_{k}^{2}\ell_{nk}^{2})}}{e^{-\beta_{k}^{2}\ell_{nk}^{2}(1-2\beta_{k}^{2}\ell_{nk}^{2})}}=1.$$ 最左邊取極限時整個式子變成了$\frac{\infty\times 0}{\infty \times 0}=$undetermined，所以我們使用羅必達法則 (L'Hôpital's rule) 將分子分母同時對$\beta_k$微分 $\partial/\partial \beta_k$，但注意在分母只有啞變數$k^\prime=k$才有微分後不等於0。
　Vola! 最終我們得到了 $$\gamma(x_{n})=\begin{cases} 1, & k^{\prime}=k,\\ 0, & k^{\prime}\neq k. \end{cases}\tag{5}$$ 這個結論告訴我們了只有當$x_n$屬於$k^\prime=k$群時它才有置信度等於1，其它都是0，而$z$在這裡已經無關緊要了。所以Eq. (2)變成 $$\mu_k =\frac{1}{N_k}\sum_{n \in k} x_n\tag{6}$$ 然後原本Eq. (3)的$N_k$現在就只是單純數有幾個點$x_n$是屬於第$k$群而已。至於怎麼在$K$個群中決定$x_n$要屬於誰，就只能用 $$\hat{k}^\prime = {\rm argmin}~\ell_{nk} \equiv {\rm argmin}~(x_n-\mu_k)^2.\tag{7}$$ 距離$\mu_k$有最小變屬於那群！這也就是K-means算法！
　一些comments，在於當我們將$\beta_k\to\infty$時也正對應了標準差趨近於0，整個高斯分佈變成一根尖尖細細的delta function，中心圍繞著$\mu_k$，故原本所有分佈的性質變消失了，比如當處在兩群中的點原本可以利用它對某一群的pdf比較大來決定它比較靠近誰變成單純的只能用和中心點$\mu_k$的距離$\ell$來決定了，這不僅僅大大的降低了分類的彈性，也使得資料集$\mathbf{x}$數據分佈的狀態與形式在計算中被遺失了，所以最終才會衍生出IA9中所呈現K-means對一類狹長形的資料分佈並不能很好的分類的狀況。
　這個情況可以直接從做圖的方式看出 (1D-case就足夠了)，不過有點懶😬，有數學底子或可以操作Mathematica或Matlab之類的讀者應該可以自己試著畫畫看，這不用用python，我覺得用python demo這個很麻煩XD！