熵的相關(guān)概念，第一次在決策樹那章做了簡(jiǎn)單介紹，但是要想正確理解熵的確實(shí)需要下一番功夫。這次，我們?cè)谧畲箪啬Ｐ瓦@章繼續(xù)來(lái)學(xué)習(xí)熵，理解熵在該模型中所扮演的角色。

以一個(gè)問(wèn)題開(kāi)始我們的學(xué)習(xí)：機(jī)器學(xué)習(xí)的目的或者意義是什么？

對(duì)于監(jiān)督學(xué)習(xí)來(lái)說(shuō)，我們希望通過(guò)現(xiàn)有獲得的觀測(cè)數(shù)據(jù)訓(xùn)練一個(gè)數(shù)據(jù)模型，然后來(lái)對(duì)未知類別樣本和數(shù)據(jù)進(jìn)行回歸和分類預(yù)測(cè)。

那么問(wèn)題來(lái)了，什么樣的模型才是比較好的模型呢？也許熵可以給我們提供了另一種特別的視角。

好，讓我們重新看一下熵的定義：

\[ H(x) = - \sum_{x=1}^N P(x)log(P(x)) \]

\[ 0 <= H(x) <= log|N|，右邊等號(hào)成立當(dāng)且僅當(dāng)P(x)服從均勻分布 \]

比如，一個(gè)拋硬幣的實(shí)驗(yàn)，得到正反兩面的概率分別都是0.5，相應(yīng)系統(tǒng)的熵為1。也就是說(shuō)，如果一個(gè)隨機(jī)變量的分布確定之后，熵也就唯一確定了。假設(shè)這里的$P(x)$是我們隨機(jī)變量的真實(shí)分布，因此這個(gè)熵是我們的下界，任何估計(jì)得到的數(shù)據(jù)分布的熵都應(yīng)當(dāng)大于等于它。

那么，最大熵模型以及同樣為指數(shù)模型的邏輯斯特回歸模型究竟是怎么和熵聯(lián)系起來(lái)的呢？為什么利用熵的約束可以使得我們訓(xùn)練的模型可以很好地表征觀測(cè)數(shù)據(jù)。

首先，讓我們來(lái)看一下邏輯斯特回歸所使用的交叉熵?fù)p失函數(shù)：

\[ CE(x) = - \sum_{x=1}^N P(x)log(Q(x)) \]

\[ H(x) <= CE(x) , 等號(hào)成立當(dāng)且僅當(dāng)Q(x) = P(x) \]

因此，通過(guò)優(yōu)化最小$CE(x)$會(huì)使得$Q(x)$盡量逼近真實(shí)數(shù)據(jù)分布$P(x)$。噢，原來(lái)通過(guò)最小化交叉熵可以使得模型朝著我們想要的方向進(jìn)行優(yōu)化，表達(dá)訓(xùn)練樣本?。?/p>

然后，我們?cè)賮?lái)看一下最大熵模型這邊又是什么情況。

經(jīng)驗(yàn)告訴我們，對(duì)于已知事件可以通過(guò)極大似然估計(jì)來(lái)統(tǒng)計(jì)各個(gè)事件發(fā)生的概率，而對(duì)于未知事件一般做法是把剩余概率平均分給這些事件。比如，下面這個(gè)簡(jiǎn)單的例子：

為什么這樣做？因?yàn)槲覀儫o(wú)法獲得額外的信息來(lái)使得熵進(jìn)一步減小，也可以說(shuō)我們無(wú)法再做進(jìn)一步的判斷。

平均這個(gè)詞生來(lái)就和熵有特殊的關(guān)系，我們知道當(dāng)$P(x)$服從均勻分布時(shí)，系統(tǒng)的熵最大。

我們的目標(biāo)剛好就是使得未知事件的概率分布為均勻分布，也就是使這些未知事件的熵最大。通過(guò)這個(gè)約束得到的模型就不會(huì)對(duì)未知事件做任何假設(shè)，公平的對(duì)待它們，這就是最大熵的核心思想。

先簡(jiǎn)單窺探一下最大熵模型中熵的引入定義：

\[ H(x) = - \sum_{x,y} P^-(x)P(y|x)log(P(y|x)) \]

注意，這里定義的是條件熵，$P(y|x)$是我們需要估計(jì)的目標(biāo)分布。所以，優(yōu)化上面的條件熵并使其最大，得到的最優(yōu)模型就能實(shí)現(xiàn)我們公平的理想。當(dāng)然，這種約束只應(yīng)該盡量施加在未知樣本上，而對(duì)于已知樣本還需要做點(diǎn)什么，后面我們會(huì)繼續(xù)探討。

可能這里有人會(huì)有一些疑問(wèn)，比如：

1. 為什么都是熵， 怎么一下求最大值好，一下又求最小值好？

   我們的最終目的都是希望模型最優(yōu)，熵大熵小只是準(zhǔn)則和途徑。最終都是希望估計(jì)分布和真實(shí)分布趨于一致。

2. 拋硬幣是服從均勻分布，如果我們針對(duì)該問(wèn)題學(xué)習(xí)到的模型也大致服從均勻分布是不是說(shuō)明該模型不好，因?yàn)殪卮螅?/p>

   我們只是希望估計(jì)分布的熵盡可能和真實(shí)分布的熵一致，而不是希望對(duì)真實(shí)分布做什么改變以求熵小。
   舉個(gè)栗子，我只是希望我畫蘋果像真實(shí)的蘋果，而不是要求蘋果像其它什么水果，比如香蕉（假設(shè)蘋果的熵比香蕉的熵大）。

最大熵模型

上一節(jié)提到最大熵模型是怎么利用熵來(lái)約束未知事件的概率分布服從均勻分布。那已知事件或者說(shuō)已知樣本怎么處理呢？我們還必須讓我們的模型能夠很好的表示已知樣本??！好像缺了什么，對(duì)吧？

是時(shí)候我們來(lái)看下最大熵代價(jià)損失函數(shù)：

\[ H(x) = - \sum_{x,y} P^-(x)P(y|x)log(P(y|x)) \]

\[ \sum_{x,y} P^-(x)P(y|x)f(x,y) = \sum_{x,y} P^-(x,y)f(x,y) \]

\[ \sum_{y} P(y|x) = 1 \]

第二個(gè)等式就是用來(lái)約束模型訓(xùn)練盡量表示我們的已知樣本信息。

最大熵模型這里引入了一個(gè)特征函數(shù)的概念：

f(x,y) = 1, x與y滿足某一事實(shí)
f(x,y) = 0, 否則

為什么需要特征函數(shù)？比較容易理解的是，特征函數(shù)其實(shí)是一個(gè)用戶接口，我們可以通過(guò)定制特征函數(shù)來(lái)控制模型的訓(xùn)練。比如，我們可以這樣設(shè)計(jì)特征函數(shù)：

f(x,y) = 1, 客戶擁有一套房產(chǎn)，允許貸款
f(x,y) = 0, 否則

好像還是不太清楚為什么需要特征函數(shù)??！我們換個(gè)角度來(lái)思考，即怎樣度量?jī)蓚€(gè)分布之間的距離或者相似度呢？

\[ \sum_{x,y} ||p(x,y)-q(x,y)|| \]

\[ \sum_{x,y} p(x,y)f(x,y) = \sum_{x,y} q(x,y)f(x,y) \]

\[ \sum_{x,y} p(x,y)log(p(x,y) / q(x,y)) \]

第一個(gè)就是常用的歐式距離；第二個(gè)是$f(x,y)$關(guān)于兩個(gè)分布的期望差值；第三個(gè)是KL距離。我們重點(diǎn)關(guān)注第二個(gè)度量方法，因?yàn)樽畲箪啬Ｐ陀玫木褪沁@種。

注意，$f(x,y)$必須是實(shí)數(shù)函數(shù)，而最大熵模型一般要求這個(gè)函數(shù)是一個(gè)二值函數(shù)。也就是說(shuō)通過(guò)這個(gè)特征函數(shù)把$x$和$y$之間千絲萬(wàn)縷的關(guān)系轉(zhuǎn)化成了一個(gè)實(shí)數(shù)值，這時(shí)我們就可以度量$P^{-(x)P(y|x)$和$P}-(x,y)$兩個(gè)分布之間的相似度了。

我們?cè)賮?lái)看個(gè)圖，理解一下特征函數(shù)$f(x,y)$的實(shí)質(zhì)意義是什么。

從這里看出，特征函數(shù)其實(shí)就是從分布上采樣，特征函數(shù)越多、越好就可以使得采樣越充分，但同時(shí)模型也就越復(fù)雜，容易過(guò)擬合。

所以在這些特征函數(shù)的約束下，使得兩個(gè)分布在這些采樣點(diǎn)上都能取得一致，進(jìn)而使得兩個(gè)分布盡量相似。

說(shuō)到這里，特征函數(shù)的意義應(yīng)該明白了。沒(méi)錯(cuò)，最大熵模型就是通過(guò)約束上面說(shuō)的兩個(gè)期望相等來(lái)使得模型盡量去學(xué)習(xí)表征我們的觀測(cè)數(shù)據(jù)。

最大熵模型學(xué)習(xí)

對(duì)于最大熵這種有約束的優(yōu)化問(wèn)題，一般情況下會(huì)通過(guò)拉格朗日乘子法把它轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題。

\[ min_p max_w L(p,w) = \sum_{x,y} P^-(x)P(y|x)log(P(y|x)) + w_0(1- \sum_y P(y|x)) + \sum_{i=1}^n w_i(\sum_{x,y} P^-(x,y)f_i(x,y) - \sum_{x,y} P^-(x)P(y|x)f_i(x,y)) \]

整個(gè)優(yōu)化目標(biāo)表達(dá)式包含兩個(gè)未知項(xiàng)，一個(gè)是待求的類后驗(yàn)分布$P(y|x)$，另一個(gè)是權(quán)重$w$。

一方面，我們希望$w$越大越好，這等價(jià)于要求模型要盡可能擬合或者說(shuō)表示我們的數(shù)據(jù)；另一方面，希望最后選擇的$P(y|x)$使得$L(p,w)$越小越好，這又等價(jià)于要求選擇的模型使得條件熵$H(x)$越大越好。

到此，只要優(yōu)化上面的函數(shù)，就可以滿足我們兩方面的需求了。

對(duì)于簡(jiǎn)單的栗子，我們可以直接求上面代價(jià)函數(shù)的解析解，其實(shí)就是二元函數(shù)的極值求解問(wèn)題。比如，先對(duì)$P(y|x)$求偏導(dǎo)并令求導(dǎo)公式等于0，然后再對(duì)$w$求導(dǎo)并令求導(dǎo)公式等于0，解出$w^*$。

最終，我們求得的$P(y|x)$形式為：

\[ P_w(y|x) = \frac{exp(\sum_{i=1}^n w_if_i(x,y))}{Z_w(x) } \]

\[ Z_w(x) = \sum_y exp(\sum_{i=1}^n w_if_i(x,y)) \]

而實(shí)際上，我們遇到的問(wèn)題大多是樣本多、特征函數(shù)也多的情況，這個(gè)時(shí)候只能采用迭代求解的方法。

最大熵模型目前最采用的迭代優(yōu)化算法主要是IIS（迭代尺度法），也出現(xiàn)了該算法的很多變體算法。大家有興趣可以關(guān)注一下。

基本IIS算法思想：

假設(shè)最大熵模型當(dāng)前的參數(shù)是：

\[ w_t = (w_1,w_2,...,w_n)^T \]

找到新的參數(shù)：

\[ w_{t+1} = (w_1+δ_1,w_2+δ_2,...,w_n+δ_n)^T \]

使得模型的對(duì)數(shù)似然值

\[ L(w) = \sum_{x,y} P^{-(x,y)\sum_{i=1}}n w_if_i(x,y) - \sum_x P^-(x)log(Z_w(x)) \]

增大。不斷地使用該方法對(duì)$w$進(jìn)行更新，就可以使得$w$最終收斂到$w^*$。那現(xiàn)在的問(wèn)題就變成了怎么去迭代尋找$δ = (δ_1,δ_2,...,δ_n)^T$了。

在機(jī)器學(xué)習(xí)領(lǐng)域，有一個(gè)非常好的優(yōu)化策略，就是當(dāng)原問(wèn)題難以求解的時(shí)候，可以通過(guò)優(yōu)化原問(wèn)題的下界函數(shù)，來(lái)間接優(yōu)化原問(wèn)題。

比如，現(xiàn)在的優(yōu)化問(wèn)題是：

\[ L(w_{t+1}) - L(w_t) = \sum_{x,y} P^{-(x,y)\sum_{i=1}}n δif_i(x,y) - \sum_x P^-(x)log\frac{Z{w+δ}(x)}{Z_w(x)} \]

我們當(dāng)然希望這個(gè)似然值改變量越大越好，可是這問(wèn)題不好求解怎么辦？那我們就求這個(gè)函數(shù)的下界函數(shù)嘛。于是，通過(guò)不停地改寫，就得到了下面的式子：

\[ L(w_{t+1}) - L(w_t) >= \sum_{x,y} P^{-(x,y)\sum_{i=1}}n δi f_i(x,y) + 1 - \sum_x P^-(x) \sum_y P_w(y|x) \sum{i=1}^n \frac{f_i(x,y)}{f^#(x,y)}exp(
δ_i f^#(x,y)) \]

\[ f^#(x,y) ＝ \sum_{i=1}^n f_i(x,y) \]

我們可以對(duì)這個(gè)下界函數(shù)針對(duì)$δ_i(i∈[1,n])$進(jìn)行求導(dǎo)，解出$δ_i$。

\[ \sum_{x,y} P^-(x,y)f_i(x,y) - \sum_{x,y} P^-(x) P_w(y|x) f_i(x,y) exp(δ_i f^#(x,y)) = 0 \]

最大熵的應(yīng)用

關(guān)于最大熵的應(yīng)用，我自己接觸的就是它在語(yǔ)言模型中的應(yīng)用。記得Mikolov的RNN的網(wǎng)絡(luò)結(jié)構(gòu)中，有集成一個(gè)最大熵的模型，有興趣可以去看一下。

另外，最大熵模型可以應(yīng)用于平常的序列標(biāo)注任務(wù)，比如專有名詞識(shí)別NER、語(yǔ)義角色標(biāo)注SRL，分詞、詞性標(biāo)注POS以及語(yǔ)義解析SP等任務(wù)。

語(yǔ)義解析是搜索、對(duì)話等AI技術(shù)的基石，所以就拿語(yǔ)義解析來(lái)簡(jiǎn)單舉例：

類似這樣序列化標(biāo)注的任務(wù)，都可以考慮使用最大熵模型來(lái)做。

總結(jié)

至此，我們最大熵模型的基本理論和應(yīng)用都已經(jīng)講完了，主要內(nèi)容包括：

• 邏輯斯特回歸與最大熵模型是怎么和熵聯(lián)系起來(lái)的；

• 最大熵模型的代價(jià)損失函數(shù)中約束項(xiàng)的含義分析；

• 最大熵模型常用的優(yōu)化及IIS方法基本原理；

• 最大熵模型的應(yīng)用場(chǎng)景簡(jiǎn)單介紹。

另外，注意1 2兩小節(jié)內(nèi)容僅是個(gè)人的理解和分析，僅供參考學(xué)習(xí)。有興趣的童鞋可以重點(diǎn)關(guān)注一下最大熵模型學(xué)習(xí)優(yōu)化的公式推導(dǎo)，仔細(xì)閱讀還是能夠看明白的。

參考資料

統(tǒng)計(jì)學(xué)習(xí)方法 李航著