核心概念#
期望最大化算法（Expectation Maximization, EM）被作者稱為「上帝的算法」——只需要訓練數據和一個目標函數，不需要人工干預和先驗經驗，經過若干次迭代就能自動完成分類。
文本的自收斂分類#
- 傳統分類方法的局限：事先設定類別的方法需要預設文本中心（Centroids）；自底向上兩兩比較的方法計算時間過長
- EM 算法既不需要事先設定類別，也不需要兩兩比較，而是隨機挑選初始聚類中心，然後迭代優化
分類步驟：
- 隨機挑選 $K$ 個點作為初始中心 $c_1(0), c_2(0), …, c_K(0)$
- 計算所有點到各聚類中心的距離，將每個點歸到最近的一類
- 重新計算每類的中心：$w_i = \frac{v_{1i} + v_{2i} + … + v_{mi}}{m}$
- 重複上述過程，直到新舊中心的偏移非常小，即過程收斂
這個方法不需要任何人工干預和先驗經驗，是純粹的數學計算，最後就完全得到了自動的分類。作者稱之為上帝的算法，因為簡直令人難以置信。
延伸閱讀：期望最大化和收斂的必然性#
- 收斂的數學證明：若距離函數足夠好（同類相對距離較近、不同類相對距離較遠），則每一步迭代後類內平均距離 $d$ 變小、類間平均距離 $D$ 變大，直到最佳分類
- 推廣到一般機器學習：EM 算法包含兩個過程和一組目標函數
- E 過程（Expectation）：根據現有聚類結果重新劃分數據，計算期望值
- M 過程（Maximization）：根據重新劃分的結果，最大化目標函數
- 前面介紹的很多算法其實都是 EM 算法：隱馬爾可夫模型的 Baum-Welch 算法、最大熵模型的 GIS 算法等
EM 算法不一定能保證找到全局最優解。如果目標函數是凸函數則可以，但在很多實際情況中（如文本分類中的餘弦距離），目標函數不是凸函數，因此 EM 可能給出局部最佳解而非全局最佳解。
本章小結#
EM 算法只需要訓練數據，定義一個最大化函數，剩下的事情就交給計算機了。經過若干次迭代，模型就訓練好了。這也許是造物主刻意安排的，所以作者稱它為上帝的算法。