1.  熵和條件熵的回顧

　　在決策樹演算法原理(上)一文中，我們已經講到了熵和條件熵的概念，這裡我們對它們做一個簡單的回顧。

　　熵度量了事物的不確定性，越不確定的事物，它的熵就越大。具體的，隨機變數X的熵的表達式如下：$$H(X) = -\sum\limits_{i=1}^{n}p_i logp_i$$

　　其中n代表X的n種不同的離散取值。而$p_i$代表了X取值為i的概率，log為以2或者e為底的對數。

　　熟悉了一個變數X的熵，很容易推廣到多個個變數的聯合熵，這裡給出兩個變數X和Y的聯合熵表達式：

$$H(X,Y) = -\sum\limits_{x_i \in X}\sum\limits_{y_i \in Y}p(x_i,y_i)logp(x_i,y_i)$$

　　有了聯合熵，又可以得到條件熵的表達式H(Y|X)，條件熵類似於條件概率,它度量了我們的Y在知道X以後剩下的不確定性。表達式如下：

$$H(Y|X) = -\sum\limits_{x_i \in X}\sum\limits_{y_i \in Y}p(x_i,y_i)logp(y_i|x_i) = \sum\limits_{j=1}^{n}p(x_j)H(Y|x_j) $$

　　用下面這個圖很容易明白他們的關係。左邊的橢圓代表H(X),右邊的橢圓代表H(Y),中間重合的部分就是我們的互資訊或者資訊增益I(X,Y), 左邊的橢圓去掉重合部分就是H(X|Y),右邊的橢圓去掉重合部分就是H(Y|X)。兩個橢圓的並就是H(X,Y)。

2.  最大熵模型的定義

　　最大熵模型假設分類模型是一個條件概率分布$P(Y|X)$,X為特徵，Y為輸出。

　　給定一個訓練集${(x^{(1)},y^{(1)}), (x^{(2)},y^{(2)}), … ，(x^{(m)},y^{(m)})}$,其中x為n維特徵向量，y為類別輸出。我們的目標就是用最大熵模型選擇一個最好的分類類型。

　　在給定訓練集的情況下，我們可以得到總體聯合分布$P(X,Y)$的經驗分布$\overline{P}(X,Y)$,和邊緣分布$P(X)$的經驗分布$\overline{P}(X)$。$\overline{P}(X,Y)$即為訓練集中X,Y同時出現的次數除以樣本總數m，$\overline{P}(X)$即為訓練集中X出現的次數除以樣本總數m。

　　用特徵函數$f(x,y)$描述輸入x和輸出y之間的關係。定義為：

$$f(x,y)=\left\{\begin{matrix}

1 & x和y滿足某個關係\\
0 & 否則
\end{matrix}\right.$$ 

　　可以認為只要出現在訓練集中出現的$(x^{(i)},y^{(i)})$,其$f(x^{(i)},y^{(i)}) = 1$. 同一個訓練樣本可以有多個約束特徵函數。

　　特徵函數$f(x,y)$關於經驗分布$\overline{P}(X,Y)$的期望值，用$E_{\overline{P}}(f)$表示為:$$E_{\overline{P}}(f) = \sum\limits_{x,y}\overline{P}(x,y)f(x,y)$$　　　

　　特徵函數$f(x,y)$關於條件分布$P(Y|X)$和經驗分布$\overline{P}(X)$的期望值，用$E_{P}(f)$表示為:

$$E_{P}(f) = \sum\limits_{x,y}\overline{P}(x)P(y|x)f(x,y)$$

　　如果模型可以從訓練集中學習，我們就可以假設這兩個期望相等。即：

$$E_{\overline{P}}(f) = E_{P}(f)$$ 

　　上式就是最大熵模型學習的約束條件，假如我們有M個特徵函數$f_i(x,y) (i=1,2…,M)$就有M個約束條件。可以理解為我們如果訓練集里有m個樣本，就有和這m個樣本對應的M個約束條件。

　　這樣我們就得到了最大熵模型的定義如下：

　　假設滿足所有約束條件的模型集合為：

$$E_{\overline{P}}(f_i) = E_{P}(f_i) (i=1,2,…M)$$ 

　　定義在條件概率分布$P(Y|X)$上的條件熵為：

$$H(P) = -\sum\limits_{x,y}\overline{P}(x)P(y|x)logP(y|x)$$

　　我們的目標是得到使$H(P)$最大的時候對應的$P(y|x)$,這裡可以對$H(P)$加了個負號求極小值，這樣做的目的是為了使$-H(P)$為凸函數，方便使用凸優化的方法來求極值。 

3.  最大熵模型損失函數的優化

　　在上一節我們已經得到了最大熵模型的函數$H(P)$。它的損失函數$-H(P)$定義為:

$$ \underbrace{ min }_{P} -H(P) = \sum\limits_{x,y}\overline{P}(x)P(y|x)logP(y|x)$$

　　約束條件為：

$$E_{\overline{P}}(f_i) – E_{P}(f_i) = 0 (i=1,2,…M) $$

$$\sum\limits_yP(y|x) = 1 $$

　　由於它是一個凸函數，同時對應的約束條件為仿射函數，根據凸優化理論，這個優化問題可以用拉格朗日函數將其轉化為無約束優化函數，此時損失函數對應的拉格朗日函數$L(P,w)$定義為：　　

$$L(P,w) \equiv -H(P) + w_0(1 – \sum\limits_yP(y|x)) + \sum\limits_{i=1}^{M}w_i(E_{\overline{P}}(f_i) – E_{P}(f_i))$$　

　　其中$w_i(i=1,2,…m)$為拉格朗日乘子。如果大家也學習過支援向量機，就會發現這裡用到的凸優化理論是一樣的，接著用到了拉格朗日對偶也一樣。、

　　我們的拉格朗日函數，即為凸優化的原始問題：$\underbrace{ min }_{P} \underbrace{ max }_{w}L(P, w)$

　　其對應的拉格朗日對偶問題為：$\underbrace{ max}_{w} \underbrace{ min }_{P}L(P, w)$

　　由於原始問題滿足凸優化理論中的KKT條件，因此原始問題的解和對偶問題的解是一致的。這樣我們的損失函數的優化變成了拉格朗日對偶問題的優化。

　　求解對偶問題的第一步就是求$\underbrace{ min }_{P}L(P, w)$, 這可以通過求導得到。這樣得到的$\underbrace{ min }_{P}L(P, w)$是關於w的函數。記為：

$$\psi(w) = \underbrace{ min }_{P}L(P, w) = L(P_w, w)$$

　　$\psi(w)$即為對偶函數，將其解記為：

$$P_w = arg \underbrace{ min }_{P}L(P, w) = P_w(y|x)$$

　　具體的是求$L(P, w)$關於$P(y|x)$的偏導數:

$$\frac{\partial L(P, w)}{\partial P(y|x)} = \sum\limits_{x,y}\overline{P}(x)(logP(y|x) +1) –  \sum\limits_yw_0 – \sum\limits_{x,y}(\overline{P}(x)\sum\limits_{i=1}^{M}w_if_i(x,y))$$　

$$ = \sum\limits_{x,y}\overline{P}(x)(logP(y|x) +1- w_0 -\sum\limits_{i=1}^{M}w_if_i(x,y))$$

　　令偏導數為0，可以解出$P(y|x)$關於$w$的表達式如下：

$$P(y|x) = exp(\sum\limits_{i=1}^{M}w_if_i(x,y) +w_0 -1) = \frac{exp(\sum\limits_{i=1}^{M}w_if_i(x,y))}{exp(1-w_0)}$$　　　　

　　由於$\sum\limits_yP(y|x) = 1 $，可以得到$P_w(y|x)$的表達式如下：

$$P_w(y|x) = \frac{1}{Z_w(x)}exp(\sum\limits_{i=1}^{M}w_if_i(x,y))$$　

　　其中，$Z_w(x)$為規範化因子，定義為：

$$Z_w(x) = \sum\limits_yexp(\sum\limits_{i=1}^{M}w_if_i(x,y))$$　

　　這樣我們就得出了$P(y|x)$和$w$的關係，從而可以把對偶函數$\psi(w)$裡面的所有的$P(y|x)$替換成用$w$表示，這樣對偶函數$\psi(w)$就是全部用$w$表示了。接著我們對$\psi(w)$求極大化，就可以得到極大化時對應的w向量的取值，帶入$P(y|x)$和$w$的關係式， 從而也可以得到$P(y|x)$的最終結果。

　　對$\psi(w)$求極大化，由於它是連續可導的，所以優化方法有很多種，比如梯度下降法，牛頓法，擬牛頓法都可以。對於最大熵模型還有一種專用的優化方法，叫做改進的迭代尺度法(improved iterative scaling, IIS)。

　　IIS也是啟發式方法，它假設當前的參數向量是$w$,我們希望找到一個新的參數向量$w+\delta$,使得對偶函數$\psi(w)$增大。如果能找到這樣的方法，就可以重複使用這種方法，直到找到對偶函數的最大值。

　　IIS使用的方法是找到$\psi(w + \delta) – \psi(w)$的一個下界$B(w|\delta)$，通過對$B(w|\delta)$極小化來得到對應的$\delta$的值，進而來迭代求解$w$。對於$B(w|\delta)$，它的極小化是通過對$\delta$求偏導數而得到的。

　　由於IIS一般只用於最大熵模型，適用範圍不廣泛，這裡就不詳述演算法過程了，感興趣的朋友可以直接參考IIS的論文The improved iterative scaling algorithm: A gentle introduction。

4.  最大熵模型小結

　　最大熵模型在分類方法里算是比較優的模型，但是由於它的約束函數的數目一般來說會隨著樣本量的增大而增大，導致樣本量很大的時候，對偶函數優化求解的迭代過程非常慢，scikit-learn甚至都沒有最大熵模型對應的類庫。但是理解它仍然很有意義，尤其是它和很多分類方法都有千絲萬縷的聯繫。　

　　慣例，我們總結下最大熵模型作為分類方法的優缺點：

　　最大熵模型的優點有：

　　a) 最大熵統計模型獲得的是所有滿足約束條件的模型中資訊熵極大的模型,作為經典的分類模型時準確率較高。

　　b) 可以靈活地設置約束條件，通過約束條件的多少可以調節模型對未知數據的適應度和對已知數據的擬合程度

　　最大熵模型的缺點有：

　　a) 由於約束函數數量和樣本數目有關係，導致迭代過程計算量巨大，實際應用比較難。

本文轉載自：//www.cnblogs.com/pinard/p/6093948.html