深入機器學習系列21-最大熵模型

轉載請註明出處，該文章的官方來源：

最大熵模型 | Teaching ML

目錄

• 1.什麼是最大熵模型
• 2.相關數學知識
• 3.最大熵模型的定義
• 4.最大熵模型的學習
• 5.最優化演算法
• 6.參考資料

1.什麼是最大熵原理

• 例子1:假設隨機變數X有5個取值{A,B,C,D,E},要估計各個值的概率P(A),P(B),…,P(E).
• 這些概率值滿足條件P(A)+P(B)+P(C)+P(D)+P(E)=1
• 但是滿足這個條件的概率分布有無數個。如果沒有其他信息,一個可行的辦法就是認為他們的概率都相等,均為0.2。
• 如果再加一個條件P(A) + P(B) = 0.3,那麼各個值的概率為多少?

2.數學知識

拉格朗日乘子法

Bayes定理

• Bayes定理用來描述兩個條件概率之間的關係。若計P(A)和P(B)分別表示事件A和事件B發生的概率,P(A|B)表示事件B發生的情況下事件A發生的概率,P(A,B)表示事件A和B同時發生的概率,則有:

利用(1.2)和(1.3)可以進一步得到貝葉斯公式:

熵

• 熵(entropy)是熱力學中的概念,由香濃引入到資訊理論中。在資訊理論和概率統計中,熵用來表示隨機變數不確定性的度量。

• H(x)依賴於X的分布,而與X的具體值無關。H(X)越大,表示X的
  不確定性越大。

條件熵

3.最大熵模型的定義

• 最大熵原理是統計學習的一般原理,將它應用到分類就得到了最大熵模型
• 假設分類模型是一個條件概率分布P(Y|X),X表示輸入,Y表示輸出。這個模型表示的是對於給定的輸入X,以條件概率P(Y|X)輸出Y。
• 給定一個訓練數據集T,我們的目標就是利用最大熵原理選擇最好的分類模型。

• 按照最大熵原理,我們應該優先保證模型滿足已知的所有約束。那麼如何得到這些約束呢?
• 思路是:從訓練數據T中抽取若干特徵,然後要求這些特徵在T上關於經驗分布的期望與它們在模型中關於p(x,y)的數學期望相等,這樣,一個特徵就對應一個約束。

特徵函數

經驗分布

• 經驗分布是指通過訓練數據T上進行統計得到的分布。我們需要考察兩個經驗分布,分別是x,y的聯合經驗分布以及x的分布。其定義如下:

• (3.3)中count(x,y)表示(x,y)在數據T中出現的次數,count(x)表示x在數據T中出現的次數。

約束條件

• 對於任意的特徵函數f,記 E p ! ( f ) 表示f在訓練數據T上關於 p ! (x, y) 的數學
  期望。 E p ( f ) 表示f在模型上關於p(x,y)的數學期望。按照期望的定義,有:

• 我們需要注意的是公式(3.5)中的p(x,y)是未知的。並且我們建模的

  目標是p(y|x),因此我們利用Bayes定理得到p(x,y)=p(x)p(y|x)。

  此時,p(x)也還是未知,我們可以使用經驗分布對p(x)進行近似。

• 對於概率分布p(y|x),我們希望特徵f的期望應該和從訓練數據中得到的特徵期望是一樣的。因此,可以提出約束:

• 假設從訓練數據中抽取了n個特徵,相應的便有n個特徵函數以及n個約束條件。

最大熵模型

• 給定數據集T,我們的目標就是根據最大熵原理選擇一個最優的分類器。
• 已知特徵函數和約束條件,我們將熵的概念應用到條件分布上面去。我們採用條件熵。

• 至此,我們可以給出最大熵模型的完整描述了。對於給定的數據集T,特徵函數f i (x,y),i=1,…,n,最大熵模型就是求解模型集合C中條件熵最大的模型:

4.最大熵模型的學習

• 最大熵模型的學習過程就是求解最大熵模型的過程。求解約束最優化問題(3.12),(3.13)所得的解就是最大熵模型學習的解。思路如下:
• 利用拉格朗日乘子法將最大熵模型由一個帶約束的最優化問題轉化為一個與之等價的無約束的最優化問題,它是一個min max問題。
• 利用對偶問題的等價性,將原始問題轉換為一個max min問題。

原始問題和對偶問題

• 利用拉格朗日乘子法定義關於(3.7)、(3.12)和(3.13)的拉格朗日函數如下:

• 利用拉格朗日對偶性,(3.6)、(3.12)和(3.13)定義的最大熵模型等價於求解:

• 通過交換極大和極小的位置,可以得到公式(4.2)的對偶問題:

• 經過兩次等價轉換,求解最大熵模型,就是求解對偶問題(4.3)就可以了。極小問題求解
• 對偶問題(4.3)內部的極小問題是關於參數lamba的問題

• 我們可以利用拉格朗日乘子法獲取p。
• 首先計算拉格朗日函數L對p(y|x)的偏導數。

• 令上面的公式等於0，可以得到：

，進一步可以解得：

將上面的公示帶入(3.13),可以得到

，進一步可得：

，將(4.7)帶回(4.6),可以得到:

• (4.9)稱為規範化因子。(4.8)中的p是最大熵模型的解,可以看到他具有指數
  的形式。最大似然估計
• 得到對偶問題(4.3)內部的極小問題的解p之後,需要進一步求解外層的極大值問題。

例子

• 題:假設隨機變數X有5個取值{A,B,C,D,E},且滿足條件P(A)+P(B)=0.3且P(A)+P(B)+P(C)+P(D)+P(E)=1。求最大熵模型。
• 為了方便,分別用y 1 ~y 5 表示A~E於是最大熵模型的最優化問題是:

• 引進拉格朗日乘子w0和w1,定義拉格朗日函數如下:

• 根據拉格朗日對偶性,可以通過求解對偶最優化問題得到原始最優化問題的解。所以求解max min L(p,w)首先需要求解關於p的極小化問題。為此需要固定w0和w1。求偏導數:

• 再求L(p,w)關於w的極大化問題:

• 分別對w0和w1求偏導,並令其等於0,可以得到

5.最優化演算法

• 公式(4.11)沒有顯式的解析解,因此需要藉助於其他的方法。由於目標函數是一個 凸函數,所以可以藉助多種優化方法來進行求解,並且能保證得到全局最優解。
• 為最大熵模型量身定製的兩個最優化方法分別是通用迭代尺度法(GIS)和改進的迭代尺度法(IIS)。

GIS演算法

IIS演算法

6.參考資料

• 李航. 統計學習方法[M]. 北京:清華大學出版社,2012
• 吳軍. 數學之美[M]. 北京:人民郵電出版社,2012
• 最大熵學習筆記
• 關於最大熵模型的嚴重困惑:為什麼沒有解析解?
• 最大熵-IIS(Improved Iterative Scaling)訓練演算法的Java實現
  如何理解最大熵模型裡面的特徵?

推薦閱讀：