《機器學習實戰》學習總結（十三）——最大熵模型

摘要

1.最大熵模型

2.改進的迭代尺度法

3.牛頓法、擬牛頓法

1.最大熵模型

最大熵模型是我們在建立模型時的一個準則：在所有可能的概率模型中，熵最大的模型是最好的模型。

上面這句話該怎麼理解呢？給大家舉個例子：我們有一個骰子，那每一面朝上的概率為多少？大多數人都會回答1/6。為什麼這樣猜測呢？因為對一個「一無所知」骰子，假定它每一面朝上概率均等是最安全的，我們沒有對未知的情況做任何主觀假設，這時其概率分布的信息熵最大。我們把這種模型稱為「最大熵模型」。

如果我們繼續說，這個骰子被特殊處理過，「4」點朝上的概率為1/3，這種情況下每個面朝上的概率是多少？很多人認為其他面均為2/15，這種推斷也是有道理的。當我們已知部分前提時，對未知分布最合理的推斷就是在符合已知條件下最不確定或最隨機的推斷，這是我們可以做出的唯一不偏不倚的選擇，因為任何其他的選擇都意味著我們增加了其他的約束和假設，這些假設和約束根據我們所掌握的信息無法做出。

假設離散隨機變數X的概率分布為P(X)，則其熵為：

這是熵的定義式。

假設我們有訓練集合 ，則我們可以根據訓練樣本得到經驗分布

下面需要定義特徵函數 :

當 滿足這個事實時取1，否則取值為0.

設特徵函數 在訓練集中關於經驗分布 的數學期望為：

特徵函數 在模型中關於 的數學期望為：

根據貝葉斯公式，得

上面的 我們近似用經驗分布 表示，得

在分類問題中，我們希望求得的就是條件概率 。

在最大熵模型的定義中，我們說應首先保證模型滿足已知的所有約束。這些約束應該這樣提：從訓練集中抽取若干(對分類問題有用的)特徵，也就是我們之前定義的特徵函數 ，然後找出特徵函數的約束條件。為了讓模型擬合訓練數據，我們需要讓： ，即：

這樣一個特徵函數 就對應一個約束。

在約束得到之後，因為我們模型是對 建模，在滿足約束的前提下使得模型的熵最大，首先得條件熵為：

條件熵的推導見我的另一篇文章：

決策樹演算法

另外對任意輸入樣例 ，它肯定屬於某一個輸出類別，所以：

因此最大熵模型就等價為如下最優化問題：

我們將最大化問題轉化為最小化問題：

解決這種帶約束的優化問題，我們主要用拉格朗日乘子法，之前我們一起學習過，鏈接：

拉格朗日乘子法

引入拉格朗日乘子，定義拉格朗日函數 :

最優化的原始問題為：

其對偶問題為：

我們首先考慮對 對 的最小化，求導：

令上面導數等於0，在 時，得

由約束條件 ，得

令 ,稱為規範化因子，得到對偶問題的極小解為：

我們令

上式不考慮 ,經過化簡得到：

根據對偶問題所以我們需要最大化：

對偶函數的極大化其實等價於最大熵模型的極大似然估計，即求：

的極大值 。

上面的公式沒有一個顯式的解，我們需要藉助數值的方法，一般可以採用改進的迭代尺度法、牛頓法和擬牛頓法、梯度下降法。下面我們主要介紹迭代尺度法和擬牛頓法。

改進的迭代尺度法

改進的迭代尺度法（improved iterative scaling，IIS）是一種最大熵模型學習的最優化演算法。

IIS的思想很簡單：假設最大熵模型當前的參數向量為

我們希望找到一個新的參數向量

使得模型的對數似然函數值增大。如果能有這樣一種參數向量更新的方法 ，那就重複使用這一方法，直到找到對數似然函數的最大值。

牛頓法和擬牛頓法

1.牛頓法

考慮無約束最優化問題：

牛頓法的主要思想：在現有的極小值估計值的附近對f(x)做二階泰勒展開，進而找到極小點的下一個估計值，反覆迭代直到演算法收斂，其迭代公式為：

當 為多維向量時，

稱 為海塞矩陣(Hesse matrix)。

所以迭代公式變為：

這就是牛頓法

2.擬牛頓法

在牛頓法中，我們需要計算海賽矩陣的逆矩陣 ，這一計算比較複雜，當我們考慮用一個n階矩陣 來近似代替 ，這個方法就叫做擬牛頓法。

擬牛頓演算法主要有DFP演算法，BFGS演算法和Broyden類演算法。

以上就是最大熵模型全部的內容，希望能給大家一些下一次我們一起學習EM演算法。

聲明

最後，所有資料均本人自學整理所得，如有錯誤，歡迎指正，有什麼建議也歡迎交流，讓我們共同進步！轉載請註明作者與出處

以上原理部分主要來自於《機器學習》—周志華，《統計學習方法》—李航，《機器學習實戰》—Peter Harrington。