最大熵的定以及概念 | 推薦系統(tǒng)

解析：

1、預(yù)備知識

為了更好的理解本文，需要了解的概率必備知識有：

①大寫字母X表示隨機變量，小寫字母x表示隨機變量X的某個具體的取值；

②P(X)表示隨機變量X的概率分布，P(X,Y)表示隨機變量X、Y的聯(lián)合概率分布，P(Y|X)表示已知隨機變量X的情況下隨機變量Y的條件概率分布；

③p(X = x)表示隨機變量X取某個具體值的概率，簡記為p(x)；

④p(X = x, Y = y) 表示聯(lián)合概率，簡記為p(x,y)，p(Y = y|X = x)表示條件概率，簡記為p(y|x)，且有：p(x,y) = p(x) * p(y|x)。

需要了解的有關(guān)函數(shù)求導(dǎo)、求極值的知識點有：

1) 如果函數(shù)y=f(x)在[a, b]上連續(xù)，且其在(a,b)上可導(dǎo)，如果其導(dǎo)數(shù)f’(x) >0，則代表函數(shù)f(x)在[a,b]上單調(diào)遞增，否則單調(diào)遞減；如果函數(shù)的二階導(dǎo)f''(x) > 0，則函數(shù)在[a,b]上是凹的，反之，如果二階導(dǎo)f''(x) < 0，則函數(shù)在[a,b]上是凸的。

2) 設(shè)函數(shù)f(x)在x0處可導(dǎo)，且在x處取得極值，則函數(shù)的導(dǎo)數(shù)F’(x0) = 0。

3) 以二元函數(shù)z = f(x,y)為例，固定其中的y，把x看做唯一的自變量，此時，函數(shù)對x的導(dǎo)數(shù)稱為二元函數(shù)z=f(x,y)對x的偏導(dǎo)數(shù)。

4) 為了把原帶約束的極值問題轉(zhuǎn)換為無約束的極值問題，一般引入拉格朗日乘子，建立拉格朗日函數(shù)，然后對拉格朗日函數(shù)求導(dǎo)，令求導(dǎo)結(jié)果等于0，得到極值。

更多請查看《高等數(shù)學(xué)上下冊》、《概率論與數(shù)理統(tǒng)計》等教科書，或參考本博客中的：數(shù)據(jù)挖掘中所需的概率論與數(shù)理統(tǒng)計知識。

2、何為熵

從名字上來看，熵給人一種很玄乎，不知道是啥的感覺。其實，熵的定義很簡單，即用來表示隨機變量的不確定性。之所以給人玄乎的感覺，大概是因為為何要取這樣的名字，以及怎么用。熵的概念最早起源于物理學(xué)，用于度量一個熱力學(xué)系統(tǒng)的無序程度。在信息論里面，熵是對不確定性的測量。

2.1 熵的引入

事實上，熵的英文原文為entropy，最初由德國物理學(xué)家魯?shù)婪颉た藙谛匏固岢?，其表達(dá)式為：

它表示一個系系統(tǒng)在不受外部干擾時，其內(nèi)部最穩(wěn)定的狀態(tài)。后來一中國學(xué)者翻譯entropy時，考慮到entropy是能量Q跟溫度T的商，且跟火有關(guān)，便把entropy形象的翻譯成“熵”。

我們知道，任何粒子的常態(tài)都是隨機運動，也就是"無序運動"，如果讓粒子呈現(xiàn)"有序化"，必須耗費能量。所以，溫度（熱能）可以被看作"有序化"的一種度量，而"熵"可以看作是"無序化"的度量。

如果沒有外部能量輸入，封閉系統(tǒng)趨向越來越混亂（熵越來越大）。比如，如果房間無人打掃，不可能越來越干凈（有序化），只可能越來越亂（無序化）。而要讓一個系統(tǒng)變得更有序，必須有外部能量的輸入。

1948年，香農(nóng)Claude E. Shannon引入信息（熵），將其定義為離散隨機事件的出現(xiàn)概率。一個系統(tǒng)越是有序，信息熵就越低；反之，一個系統(tǒng)越是混亂，信息熵就越高。所以說，信息熵可以被認(rèn)為是系統(tǒng)有序化程度的一個度量。

若無特別指出，下文中所有提到的熵均為信息熵。

2.2 熵的定義

下面分別給出熵、聯(lián)合熵、條件熵、相對熵、互信息的定義。

熵：如果一個隨機變量X的可能取值為X = {x1, x2,…, xk}，其概率分布為P(X = xi) = pi（i = 1,2, ..., n），則隨機變量X的熵定義為：

把最前面的負(fù)號放到最后，便成了：

上面兩個熵的公式，無論用哪個都行，而且兩者等價，一個意思（這兩個公式在下文中都會用到）。

聯(lián)合熵：兩個隨機變量X，Y的聯(lián)合分布，可以形成聯(lián)合熵Joint Entropy，用H(X,Y)表示。

條件熵：在隨機變量X發(fā)生的前提下，隨機變量Y發(fā)生所新帶來的熵定義為Y的條件熵，用H(Y|X)表示，用來衡量在已知隨機變量X的條件下隨機變量Y的不確定性。且有此式子成立：H(Y|X) = H(X,Y) – H(X)，整個式子表示(X,Y)發(fā)生所包含的熵減去X單獨發(fā)生包含的熵。至于怎么得來的請看推導(dǎo)：

簡單解釋下上面的推導(dǎo)過程。整個式子共6行，

其中第二行推到第三行的依據(jù)是邊緣分布p(x)等于聯(lián)合分布p(x,y)的和；

第三行推到第四行的依據(jù)是把公因子logp(x)乘進去，然后把x,y寫在一起；

第四行推到第五行的依據(jù)是：因為兩個sigma都有p(x,y)，故提取公因子p(x,y)放到外邊，然后把里邊的-（log p(x,y) - log p(x)）寫成- log (p(x,y)/p(x) ) ；

第五行推到第六行的依據(jù)是：p(x,y) = p(x) * p(y|x)，故p(x,y) / p(x) =  p(y|x)。

相對熵：又稱互熵，交叉熵，鑒別信息，Kullback熵，Kullback-Leible散度等。設(shè)p(x)、q(x)是X中取值的兩個概率分布，則p對q的相對熵是：

在一定程度上，相對熵可以度量兩個隨機變量的“距離”，且有D(p||q) ≠D(q||p)。另外，值得一提的是，D(p||q)是必然大于等于0的。

互信息：兩個隨機變量X，Y的互信息定義為X，Y的聯(lián)合分布和各自獨立分布乘積的相對熵，用I(X,Y)表示：

且有I(X,Y)=D(P(X,Y) || P(X)P(Y))。下面，咱們來計算下H(Y)-I(X,Y)的結(jié)果，如下：

通過上面的計算過程，我們發(fā)現(xiàn)竟然有H(Y)-I(X,Y) = H(Y|X)。故通過條件熵的定義，有：H(Y|X) = H(X,Y) - H(X)，而根據(jù)互信息定義展開得到H(Y|X) = H(Y) - I(X,Y)，把前者跟后者結(jié)合起來，便有I(X,Y)= H(X) + H(Y) - H(X,Y)，此結(jié)論被多數(shù)文獻(xiàn)作為互信息的定義。

3、最大熵

熵是隨機變量不確定性的度量，不確定性越大，熵值越大；若隨機變量退化成定值，熵為0。如果沒有外界干擾，隨機變量總是趨向于無序，在經(jīng)過足夠時間的穩(wěn)定演化，它應(yīng)該能夠達(dá)到的最大程度的熵。

為了準(zhǔn)確的估計隨機變量的狀態(tài)，我們一般習(xí)慣性最大化熵，認(rèn)為在所有可能的概率模型（分布）的集合中，熵最大的模型是最好的模型。換言之，在已知部分知識的前提下，關(guān)于未知分布最合理的推斷就是符合已知知識最不確定或最隨機的推斷，其原則是承認(rèn)已知事物（知識），且對未知事物不做任何假設(shè)，沒有任何偏見。

例如，投擲一個骰子，如果問"每個面朝上的概率分別是多少"，你會說是等概率，即各點出現(xiàn)的概率均為1/6。因為對這個"一無所知"的色子，什么都不確定，而假定它每一個朝上概率均等則是最合理的做法。從投資的角度來看，這是風(fēng)險最小的做法，而從信息論的角度講，就是保留了最大的不確定性，也就是說讓熵達(dá)到最大。

3.1 無偏原則

下面再舉個大多數(shù)有關(guān)最大熵模型的文章中都喜歡舉的一個例子。

例如，一篇文章中出現(xiàn)了“學(xué)習(xí)”這個詞，那這個詞是主語、謂語、還是賓語呢？換言之，已知“學(xué)習(xí)”可能是動詞，也可能是名詞，故“學(xué)習(xí)”可以被標(biāo)為主語、謂語、賓語、定語等等。

令x1表示“學(xué)習(xí)”被標(biāo)為名詞， x2表示“學(xué)習(xí)”被標(biāo)為動詞。

令y1表示“學(xué)習(xí)”被標(biāo)為主語， y2表示被標(biāo)為謂語， y3表示賓語， y4表示定語。

且這些概率值加起來的和必為1，即 ，

則根據(jù)無偏原則，認(rèn)為這個分布中取各個值的概率是相等的，故得到：

因為沒有任何的先驗知識，所以這種判斷是合理的。如果有了一定的先驗知識呢？

即進一步，若已知：“學(xué)習(xí)”被標(biāo)為定語的可能性很小，只有0.05，即，

剩下的依然根據(jù)無偏原則，可得： 再進一步，當(dāng)“學(xué)習(xí)”被標(biāo)作名詞x1的時候，它被標(biāo)作謂語y2的概率為0.95，即，此時仍然需要堅持無偏見原則，使得概率分布盡量平均。但怎么樣才能得到盡量無偏見的分布？

實踐經(jīng)驗和理論計算都告訴我們，在完全無約束狀態(tài)下，均勻分布等價于熵最大（有約束的情況下，不一定是概率相等的均勻分布。比如，給定均值和方差，熵最大的分布就變成了正態(tài)分布 ）。

于是，問題便轉(zhuǎn)化為了：計算X和Y的分布，使得H(Y|X)達(dá)到最大值，并且滿足下述條件：

因此，也就引出了最大熵模型的本質(zhì)，它要解決的問題就是已知X，計算Y的概率，且盡可能讓Y的概率最大（實踐中，X可能是某單詞的上下文信息，Y是該單詞翻譯成me，I，us、we的各自概率），從而根據(jù)已有信息，盡可能最準(zhǔn)確的推測未知信息，這就是最大熵模型所要解決的問題。

相當(dāng)于已知X，計算Y的最大可能的概率，轉(zhuǎn)換成公式，便是要最大化下述式子H(Y|X)：

且滿足以下4個約束條件：

本文素材來源于七月在線面試題，關(guān)注公號，獲取更多面試資料。

本期特訓(xùn)課程
僅需1元限時秒，名額僅剩200個
掃下方二維碼即可報名
▲ 學(xué)習(xí)多種優(yōu)化方法，掌握比賽上分利器

僅需1元限時秒，名額僅剩200個
掃下方二維碼/點擊閱讀原文即可報名

點擊這里閱讀原文