數學雜記2 - 從高斯混合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！
現在我們就證明當剛度趨近無限大時，上述的高斯混合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！
留言
張貼留言