3.28 最????熵模型中的數(shù)學(xué)推導(dǎo) ?? 0 引? ?? 寫完SVM之后，?直想繼續(xù)寫機(jī)器學(xué)習(xí)的系列，?奈?直時(shí)間不穩(wěn)定且對(duì)各個(gè)模型算法的理解尚不夠，所以導(dǎo)致遲遲未動(dòng)筆。?獨(dú)有偶，重寫KMP得益于今年4?個(gè)?組織的算法班，?動(dòng)筆繼續(xù)寫這個(gè)機(jī)器學(xué)習(xí)系列，正得益于今年10?組織的機(jī)器學(xué)習(xí)班。? ?? 10?26?機(jī)器學(xué)習(xí)班第6次課，鄒講最????熵模型，從熵的概念，講到為何要最????熵、最????熵的推導(dǎo)，以及求解參數(shù)的IIS?法，整個(gè)過程講得?常流暢，特別是其中的數(shù)學(xué)推導(dǎo)。晚上我把上課PPT 在微博上公開分享了出來，但對(duì)于沒有上過課的朋友直接看PPT 會(huì)感到?常跳躍，因此我打算針對(duì)機(jī)器學(xué)習(xí)班的某些次課寫?系列博客，剛好也算繼續(xù)博客中未完的機(jī)器學(xué)習(xí)系列。綜上，本?結(jié)合10?機(jī)器學(xué)習(xí)班最????熵模型的PPT和其它相關(guān)資料寫就，可以看成是課程筆記或?qū)W習(xí)?得，著重推導(dǎo)。有何建議或意見，歡迎隨時(shí)于本?評(píng)論下指出，thanks. 1 預(yù)備知識(shí) ?? 為了更好的理解本?，需要了解的概率必備知識(shí)有： ?寫字母X表?隨機(jī)變量，?寫字母x表?隨機(jī)變量X的某個(gè)具體的取值； P(X)表?隨機(jī)變量X的概率分布，P(X,Y)表?隨機(jī)變量X、Y的聯(lián)合概率分布，P(Y|X)表?已知隨機(jī)變量X的情況下隨機(jī)變量Y的條件概率分布； p(X = x)表?隨機(jī)變量X取某個(gè)具體值的概率，簡(jiǎn)記為p(x)； p(X = x, Y = y) 表?聯(lián)合概率，簡(jiǎn)記為p(x,y)，p(Y = y|X = x)表?條件概率，簡(jiǎn)記為p(y|x)，且有： p(x,y) = p(x) * p(y|x)。 需要了解的有關(guān)函數(shù)求導(dǎo)、求極值的知識(shí)點(diǎn)有： 如果函數(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]上是凸的。 設(shè)函數(shù)f(x)在x0處可導(dǎo)，且在x處取得極值，則函數(shù)的導(dǎo)數(shù)F’(x0) = 0。 以?元函數(shù)z = f(x,y)為例，固定其中的y，把x看做唯?的?變量，此時(shí)，函數(shù)對(duì)x的導(dǎo)數(shù)稱為?元函數(shù)z=f(x,y)對(duì)x的偏導(dǎo)數(shù)。 為了把原帶約束的極值問題轉(zhuǎn)換為?約束的極值問題，?般引?拉格朗?乘?，建?拉格朗?函數(shù)，然后對(duì)拉格朗?函數(shù)求導(dǎo)，令求導(dǎo)結(jié)果等于0，得到極值。 更多請(qǐng)查看《?等數(shù)學(xué)上下冊(cè)》、《概率論與數(shù)理統(tǒng)計(jì)》等教科書，或參考本博客中的：數(shù)據(jù)挖掘中所需的概率論與數(shù)理統(tǒng)計(jì)知識(shí)。 2 何謂熵？ ????♂? 從名字上來看，熵給??種很?乎，不知道是啥的感覺。其實(shí)，熵的定義很簡(jiǎn)單，即?來表?隨機(jī)變量的不確定性。之所以給??乎的感覺，?概是因?yàn)闉楹我∵@樣的名字，以及怎么?。熵的概念最早起源于物理學(xué)，?于度量?個(gè)熱?學(xué)系統(tǒng)的?序程度。在信息論??，熵是對(duì)不確??定性的測(cè)量。 ?? 2.1 熵的引? 事實(shí)上，熵的英?原?為entropy，最初由德國(guó)物理學(xué)家魯?shù)婪颉た藙谛匏固岢觯浔磉_(dá)式為： \[H(X) = - \sum_{i=1}^{k} p(x_i) \log p(x_i)\] 它表??個(gè)系系統(tǒng)在不受外部?擾時(shí)，其內(nèi)部最穩(wěn)定的狀態(tài)。后來?中國(guó)學(xué)者翻譯entropy時(shí)， 考??慮到entropy是能量Q跟溫度T的商，且跟?有關(guān)，便把entropy形象的翻譯成“熵”。我們知道，任何粒?的常態(tài)都是隨機(jī)運(yùn)動(dòng)，也就是"?序運(yùn)動(dòng)"，如果讓粒?呈現(xiàn)"有序化"，必須耗費(fèi)能量。所以，溫度（熱能）可以被看作"有序化"的?種度量，?"熵"可以看作是"?序化"的度量。 如果沒有外部能量輸?，封閉系統(tǒng)趨向越來越混亂（熵越來越?）。?如，如果房間??打掃，不可能越來越?凈（有序化），只可能越來越亂（?序化）。?要讓?個(gè)系統(tǒng)變得更有序，必須有外部能量的輸?。 1948年，?農(nóng)Claude E. Shannon引?信息（熵），將其定義為離散隨機(jī)事件的出現(xiàn)概率。?個(gè)系統(tǒng)越是有序，信息熵就越低；反之，?個(gè)系統(tǒng)越是混亂，信息熵就越?。所以說，信息熵可以被認(rèn)為???是系統(tǒng)有序化程度的?個(gè)度量。 若?特別指出，下?中所有提到的熵均為信息熵。 ?? 2.2 熵的定義 下?分別給出熵、聯(lián)合熵、條件熵、相對(duì)熵、互信息的定義。 ? ?? 熵：如果?個(gè)隨機(jī)變量X的可能取值為X = {x1, x2,…, xk}，其概率分布為P(X = xi) = pi（i = 1,2, ..., n），則隨機(jī)變量X的熵定義為： \[H(X) = - \sum_{i=1}^{k} p(x_i) \log p(x_i)\] 把最前?的負(fù)號(hào)放到最后，便成了： \[H(X) = \sum_{i=1}^{k} p(x_i) \log \frac{1}{p(x_i)}\] 上?兩個(gè)熵的公式，?論?哪個(gè)都?，?且兩者等價(jià)，?個(gè)意思（這兩個(gè)公式在下?中都會(huì)?到。 聯(lián)合熵：兩個(gè)隨機(jī)變量X，Y的聯(lián)合分布，可以形成聯(lián)合熵Joint Entropy，?H(X,Y)表?。 ?? 條件熵：在隨機(jī)變量X發(fā)?的前提下，隨機(jī)變量Y發(fā)?所新帶來的熵定義為Y的條件熵，?H(Y|X)表?，?來衡量在已知隨機(jī)變量X的條件下隨機(jī)變量Y的不確定性。 且有此式?成?：\[H(Y|X) = H(X,Y) – H(X)\]，整個(gè)式?表?(X,Y)發(fā)?所包含的熵減去X單獨(dú)發(fā)?包含的熵。?于怎么得來的請(qǐng)看推導(dǎo)： ? 簡(jiǎn)單解釋下上?的推導(dǎo)過程。整個(gè)式?共6?，其中 第??推到第三?的依據(jù)是邊緣分布p(x)等于聯(lián)合分布p(x,y)的和； 第三?推到第四?的依據(jù)是把公因?logp(x)乘進(jìn)去，然后把x,y寫在?起； 第四?推到第五?的依據(jù)是：因?yàn)閮蓚€(gè)sigma都有p(x,y)，故提取公因?p(x,y)放到外邊，然后把?邊的-\(log p(x,y) - log p(x)\)寫成-\(log \frac{p(x,y)}{p(x)}\) ； 第五?推到第六?的依據(jù)是：\(p(x,y) = p(x) * p(y|x)\)，故\(\frac{p(x,y)}{p(x)} =?p(y|x)\)。 ?? 相對(duì)熵：又稱互熵，交叉熵，鑒別信息，Kullback熵，Kullback-Leible散度等。設(shè)p(x)、q(x)是X中 取值的兩個(gè)概率分布，則p對(duì)q的相對(duì)熵是： ? \[D(p||q) = \sum_{i=1}^{k} p(x_i) \log \frac{p(x_i)}{q(x_i)}\] 在?定程度上，相對(duì)熵可以度量?jī)蓚€(gè)隨機(jī)變量的“距離”，且有\(zhòng)[D(p||q) \neq D(q||p)\]。另外，值得?提的是，\[D(p||q)\]是必然?于等于0的。 ?? 互信息：兩個(gè)隨機(jī)變量X，Y的互信息定義為X，Y的聯(lián)合分布和各?獨(dú)?分布乘積的相對(duì)熵，? \[I(X,Y) = D(P(X,Y) || P(X)P(Y))\] 表?： ? 通過上?的計(jì)算過程，我們發(fā)現(xiàn)竟然有\(zhòng)[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é)合起來，便有\(zhòng)[I(X,Y)= H(X) + H(Y) - H(X,Y)\]，此結(jié)論被多數(shù)?獻(xiàn)作為互信息的定義。 ?? 3 最?熵 熵是隨機(jī)變量不確定性的度量，不確定性越?，熵值越?；若隨機(jī)變量退化成定值，熵為0。如果沒有外界?擾，隨機(jī)變量總是趨向于?序，在經(jīng)過?夠時(shí)間的穩(wěn)定演化，它應(yīng)該能夠達(dá)到的最?程度的熵。 為了準(zhǔn)確的估計(jì)隨機(jī)變量的狀態(tài)，我們?般習(xí)慣性最?化熵，認(rèn)為在所有可能的概率模型（分布）???的集合中，熵最?的模型是最好的模型。換?之，在已知部分知識(shí)的前提下，關(guān)于未知分布最合理的推斷就是符合已知知識(shí)最不確定或最隨機(jī)的推斷，其原則是承認(rèn)已知事物（知識(shí)），且對(duì)未知事物不做任何假設(shè)，沒有任何偏見。 例如，投擲?個(gè)骰?，如果問"每個(gè)?朝上的概率分別是多少"，你會(huì)說是等概率，即各點(diǎn)出現(xiàn)的概率均為1/6。因?yàn)閷?duì)這個(gè)"??所知"的??，什么都不確定，?假定它每?個(gè)朝上概率均等則是最合???理的做法。從投資的?度來看，這是風(fēng)險(xiǎn)最?的做法，?從信息論的?度講，就是保留了最?的不確定性，也就是說讓熵達(dá)到最?。 ?? 3.2 最?熵模型的表? ?此，有了?標(biāo)函數(shù)跟約束條件，我們可以寫出最?熵模型的?般表達(dá)式了，如下： \[P(y|x) = \frac{1}{Z(x)} \exp \left( \sum_{i=1}^{n} \lambda_i f_i(x,y) \right)\] 其中，P={p | p是X上滿?條件的概率分布} 繼續(xù)闡述之前，先定義下特征、樣本和特征函數(shù)。特征：(x,y) y：這個(gè)特征中需要確定的信息x：這個(gè)特征中的上下?信息 樣本：關(guān)于某個(gè)特征(x,y)的樣本，特征所描述的語(yǔ)法現(xiàn)象在標(biāo)準(zhǔn)集合?的分布：(xi,yi)對(duì)，其中， yi是y的?個(gè)實(shí)例，xi是yi的上下?。 對(duì)于?個(gè)特征(x0,y0)，定義特征函數(shù)： \[f_i(x,y) = \begin{cases} 1 & \text{如果特征i在(x,y)中出現(xiàn)} \\ 0 & \text{否則} \end{cases}\] 特征函數(shù)關(guān)于經(jīng)驗(yàn)分布P-在樣本中的期望值是： \[E_{P^-}[f_i(x,y)] = \frac{1}{N} \sum_{j=1}^{N} f_i(x_j, y_j)\] 其中，N是樣本的總數(shù)。 特征函數(shù)關(guān)于模型P(Y|X)與經(jīng)驗(yàn)分布P-(X)的期望值為： \[E_{P(Y|X)P^-(X)}[f_i(x,y)] = \sum_{x \in X} \sum_{y \in Y} P(x) P(y|x) f_i(x,y)\] 換?之，如果能夠獲取訓(xùn)練數(shù)據(jù)中的信息，那么上述這兩個(gè)期望值相等，即： \[E_{P^-}[f_i(x,y)] = E_{P(Y|X)P^-(X)}[f_i(x,y)]\] 不過，因?yàn)閷?shí)踐中p(x)不好求，所以?般?樣本中x出現(xiàn)的概率"p(x)-"代替x在總體中的分布概率 “p(x)”，從?得到最?熵模型的完整表述如下： \[P(y|x) = \frac{1}{Z(x)} \exp \left( \sum_{i=1}^{n} \lambda_i f_i(x,y) \right)\] 其約束條件為： \[\sum_{y \in Y} P(y|x) = 1, \forall x \in X\] 該問題已知若?條件，要求若?變量的值使到?標(biāo)函數(shù)（熵）最?，其數(shù)學(xué)本質(zhì)是最優(yōu)化問題 （Optimization Problem），其約束條件是線性的等式，??標(biāo)函數(shù)是?線性的，所以該問題屬于?線性規(guī)劃（線性約束）(non-linear programming with linear constraints)問題，故可通過引?Lagrange函數(shù)將原帶約束的最優(yōu)化問題轉(zhuǎn)換為?約束的最優(yōu)化的對(duì)偶問題。 ?? 3.3 凸優(yōu)化中的對(duì)偶問題 考慮到機(jī)器學(xué)習(xí)?，不少問題都在圍繞 凸優(yōu)化，故我們以機(jī)器學(xué)習(xí)?經(jīng)常出現(xiàn)的對(duì)偶問題來說。特別是在線性SVM，LR等機(jī)器學(xué)習(xí)?獻(xiàn)?，都會(huì)涉及到對(duì)偶問題。在此僅以?個(gè)小?喻簡(jiǎn)單說明： 在最優(yōu)化問題中，往往存在?個(gè)原始問題（Primal Problem）和?個(gè)對(duì)偶問題（Dual Problem）。原始問題的求解往往是?維度問題，?對(duì)偶問題通常?較低維度，因此往往容易求解。更重要的是，解對(duì)偶問題有助于理解原始問題，解決原始問題。因此，?論是理論分析還是計(jì)算求解，對(duì)偶問題都具有重要意義。 舉?個(gè)例?，考慮?個(gè)線性分類問題，給定樣本集合D = {(x1, y1), (x2, y2), ..., (xn, yn)}，其中xi ∈ R^n 表?第i個(gè)樣本，yi ∈ {-1, 1} 表?第i個(gè)樣本的類別，線性分類模型的假設(shè)函數(shù)可表示為： \[f(x) = sign(w \cdot x + b) \] 其中，w ∈ R^n 是權(quán)值向量，b ∈ R 是偏置，sign()是符號(hào)函數(shù)。最小化線性分類模型的損失函數(shù)可寫成以下形式： \[min_{w,b} L(w,b) = \sum_{i=1}^{n} L(w,b) = \sum_{i=1}^{n} max(0, -y_i(w \cdot x_i + b)) \] 其中，L(w,b)是損失函數(shù)，max(0, -y_i(w \cdot x_i + b)) 是經(jīng)典的hinge loss。 這是一個(gè)典型的支持向量機(jī)（Support Vector Machine，SVM）的優(yōu)化問題，其原始問題是在所有w和b的組合中找到一個(gè)最優(yōu)解，使得損失函數(shù)L(w,b)最小。然而，這個(gè)問題的求解可能會(huì)非常復(fù)雜，因?yàn)閣和b都是高維的參數(shù)。 為了簡(jiǎn)化問題，我們可以引入對(duì)偶問題。對(duì)偶問題的目標(biāo)是找到一組拉格朗日乘子α_i，其中i = 1, 2, ..., n，使得在滿足一些條件的情況下，原始問題的最優(yōu)值等于對(duì)偶問題的最優(yōu)值。對(duì)偶問題的形式通常更簡(jiǎn)單，因?yàn)樗婕暗降膮?shù)更少。 對(duì)于上面的SVM問題，對(duì)偶問題的形式如下： \[max_{\alpha} W(\alpha) = \sum_{i=1}^{n} \alpha_i - \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j x_i \cdot x_j \] 其中，α_i 是拉格朗日乘子，W(α) 是對(duì)偶問題的目標(biāo)函數(shù)，x_i 和 x_j 是樣本集合中的樣本，y_i 和 y_j 是對(duì)應(yīng)樣本的類別，n 是樣本的數(shù)量。通過求解對(duì)偶問題，我們可以得到原始問題的最優(yōu)解，即權(quán)值向量 w 和偏置 b。 總結(jié)一下，對(duì)偶問題是一個(gè)在原始問題的約束條件下尋找最優(yōu)解的問題，通常情況下，對(duì)偶問題的形式更簡(jiǎn)單，因?yàn)樗婕暗膮?shù)更少。解決對(duì)偶問題可以幫助我們理解原始問題，并且在某些情況下更容易求解。在機(jī)器學(xué)習(xí)中，對(duì)偶問題經(jīng)常出現(xiàn)在支持向量機(jī)等模型中的優(yōu)化問題中，對(duì)于理論分析和求解算法都具有重要意義。 ? 3.4 最????熵模型的對(duì)偶問題 最????熵模型的對(duì)偶問題定義如下： \[max_{\lambda_i}?W(\lambda) = \sum_{i=1}^{n} \lambda_i - \frac{1}{N} \sum_{i=1}^{N} \sum_{j=1}^{N} \lambda_i \lambda_j p(y_i, x_i, x_j, y_j) \sum_{x \in X} p^-(x) f(x, y_i) f(x, y_j)?\] 其中， n是特征函數(shù)的數(shù)量； N是樣本的總數(shù)； λ_i 是拉格朗日乘子，對(duì)應(yīng)于每個(gè)特征函數(shù)； W(λ) 是對(duì)偶問題的目標(biāo)函數(shù)； p(y_i, x_i, x_j, y_j) 是聯(lián)合分布的概率； p^-(x) 是樣本中 x 出現(xiàn)的概率； f(x, y) 是特征函數(shù)。 對(duì)偶問題的目標(biāo)是找到一組拉格朗日乘子λ_i，使得目標(biāo)函數(shù)W(λ)最大化。通過求解對(duì)偶問題，我們可以得到最大熵模型的參數(shù)λ_i，進(jìn)而得到條件概率分布P(y|x)。 總結(jié)：最大熵模型是一種用于分類和回歸的機(jī)器學(xué)習(xí)模型，其核心思想是在滿足已知約束條件的情況下，選擇使熵最大化的模型。熵是用來度量隨機(jī)變量的不確定性的，最大熵模型的目標(biāo)是找到一個(gè)概率分布，使得在滿足約束條件的情況下，系統(tǒng)的不確定性最大。最大熵模型的參數(shù)可以通過求解對(duì)偶問題來獲得，該問題通常涉及拉格朗日乘子的求解。最大熵模型在自然語(yǔ)言處理等領(lǐng)域廣泛應(yīng)用，它可以用來解 決文本分類、語(yǔ)言模型等問題。