小象-機(jī)器學(xué)習(xí)-8.最大熵模型

法本課件包括演示文稿、示例、代碼、題庫(kù)、和在課程范圍外向任何第散播。任何其他人或機(jī)構(gòu)不得盜版、、仿造其中的創(chuàng)意及內(nèi)容，我們 課 咨

鄒本次目 理解聯(lián)合熵H(X,Y)、相對(duì)熵D(X||Y)、條件熵H(X|Y)、I(X,Y)的定義和含義，并了解如下公 H(X|Y)=H(X,Y)-H(Y)=H(X)- H(Y|X)=H(X,Y)-H(X)=H(Y)– I(X,Y)=H(X)-H(X|Y)=H(X)+H(Y)-H(X,Y)掌握最大熵模型 umEntropy了解最大熵在自然語(yǔ)言處理NLP中的應(yīng) NaturalLanguage umLikelihood

預(yù)備定NlnN!NlnN lnN!lni

lnN1xlnxN1N1N

xdlnNlnN

x1dx1NlnNx1NlnNNNlnN

普通的一個(gè)的某一次投擲，出現(xiàn)點(diǎn)5的等概率：各點(diǎn)的概率都是對(duì)于“一無(wú)所知”的，假定所有點(diǎn)數(shù)等概對(duì)給定的某個(gè)，經(jīng)過(guò)N次投擲后發(fā)現(xiàn)，

帶約束的優(yōu)化問(wèn)令6個(gè)面朝上的概率為(p1,p2…p6)，用向量p表示

pln約束條

pi

ipiLp!,, plnp

ip

i求解

L

令

ln

11i2

15.932,2

預(yù)測(cè)結(jié)

從小學(xué)數(shù)學(xué)開(kāi) 左邊比右邊右邊比左邊兩邊同樣

答一種可能的稱(chēng)量方法如右圖所答案：2追問(wèn)：為什么2次

1+2?>=1?

3?5 51 2 3 41234

理論下令x表 幣的序號(hào)：令yi表示第i次使用天平得到1表示“左輕”，2表示“平衡”，3用天平稱(chēng)n次，獲得的結(jié)果是：y1y2…y1y2…yn的所有可能組合數(shù)目是根據(jù)題意，要求通過(guò)y1y2yn確定x。即影射map(y1y2…yn)=x；從而：y1y2…yn的變化數(shù)目大于等于x的變化數(shù)則：3n≥5——一般意義上Yn

進(jìn)一步分YnXnlogYlogXnloglog用y1y2…yn表達(dá)x。即設(shè)計(jì)編碼x：y1y2…log

log的“表達(dá)能力”是HYlog

log至少要多少個(gè)Y才能準(zhǔn)確表示HXlog5H(Y log

題目的變 能夠找

解

解釋Huffman編12345

解釋Huffman編1?3?12312345

附 定義信息某事件發(fā)生的概率小，則該事件的信思考：事件X的信息量的期望如何計(jì)算

熵注：經(jīng)典熵的定義，底數(shù)是2，單位是本例中，為分析方便使用底數(shù)若底數(shù)是e，單位是nat(奈特

研究函數(shù)當(dāng)f’(x)=0時(shí)，x=1/e由于limfx定義

離散采

繪

對(duì)熵的理解0HXlog熵是隨量不確定性的度量，不確定性越大，熵值越大；若隨量成定值，熵該不確定性度量的本質(zhì)即為信息量的均勻分布是“最不確定”的分熵其實(shí)定義了一個(gè)函數(shù)(概率分布函數(shù))到一(函數(shù)數(shù)值泛函：“變分推導(dǎo)”章

兩點(diǎn)分布的

繼續(xù)思考：三點(diǎn)分布呢HXpxlnpxp1lnp1p2lnp21p1p2ln1p1p2

組合數(shù)的關(guān)

n1!n2!n3!!nk n!n!n!!n記W n!n!n!!n 求Hn,n,! 1lnW

公式推NlnN!NlnNH1N

kk

1lnN!

lnni

1nlnnN NlnN

1

nilnni

ninkN k 1

lnN

nilnniNiNi

Ni1 k k

nlnN

1

niN

niln

NNi1 N

nilnnik k

pilnpii1

自封閉系統(tǒng)的運(yùn)動(dòng)總是倒向均勻分

思考：根據(jù)函數(shù)形式判斷概率分

2ln

ln

x

x該分布的對(duì)數(shù)是關(guān)于 根據(jù)計(jì)算過(guò)程的可逆性，若某對(duì)數(shù)分布能夠?qū)懗呻S量二次形式，則該分布必然是正態(tài)分

舉 px;,

x常系數(shù)

0lnpx;,ln1lnxxlnAxBlnx若某對(duì)數(shù)分布能夠?qū)懗呻S

t1et

Gamma函數(shù) Gamma分布的期望為：EX

若 成定值，熵最?。簽槿綦S機(jī)分布為均勻分布，熵最最大熵模

思考過(guò)argmaxHX

pxln

px

VarXEX2E2XEX2E2XVarX2

建立Lagrange函數(shù)，求駐

2x

xpx

x2px2

2

Llnpx1xx2 0lnpxx2x P(x)的對(duì)數(shù)是關(guān)于隨

聯(lián)合熵和條件 聯(lián)合熵JointEntropy，用H(X,Y)表示(X,Y)發(fā)生所包含的熵，減去Y單獨(dú)發(fā)生包含的該式子定義為Y發(fā)生前提下，X的熵條件熵

推導(dǎo)條件熵的定義H(X,Y)H(Yp(x,y)logp(x,y)p(y)logp(x, p(x,y)logp(x,y)x,

p(x,y)p(p(x,y)logp(x,y)p(x,y)logp(x, x,p(x,y)logp(x,x,

p(p(x,y)logp(x|x,

根據(jù)條件熵的定義式，可以得H(X,Y)H(X)p(x,y)logp(y|x,p(x,y)logp(y| p(x)p(y|x)logp(y| p(x)p(y|x)logp(y| p(x)HY|Xx

相對(duì)設(shè)p(x)、q(x)是X中取值的兩個(gè)概率分布，則p對(duì)q相對(duì)熵Dp||q

x說(shuō)明

px

相對(duì)熵可以度量?jī)蓚€(gè) 一般的，D(p||q)D(p||q)≥0D(q||p)0：凸函數(shù)中的Jensen

思假定已知隨 方法：使用P和Q的K-L難點(diǎn)：K-L距離是非對(duì)稱(chēng)的，兩個(gè)隨

兩個(gè)KL散度的區(qū)是使用近似p(z1,z2)=p(z1)p(z2)得到的等高左：KL(p||q)：zero右：KL(q||p)：zero

兩個(gè)KL散度的區(qū)左：KL(p||q)：q趨向于覆蓋中、右：KL(q||p)：q能夠鎖定某一個(gè)峰

互信 I(X,Y) p(x,y)logp(x,x, p(x)p(

計(jì)算條件熵的定義式：H(X)-H(X)I(X,Yp(x)logp(x)p(x,y)logp(x,

p(x)p(p(x,

p(x)p(x

p(x,y)logp(x)p(x,y)logp(x, p(x,y)logp(x,

p(x)p(

p(p(x,y)logp(x|H(X|Y

根據(jù)條件熵的定義式，可以得H(X,Y)H(X)p(x,y)logp(y|x,p(x,y)logp(y| p(x)p(y|x)logp(y| p(x)p(y|x)logp(y| p(x)HY|Xx

整理得到的等H(X|Y)=H(X,Y)-條件熵定H(X|Y)=H(X)-根據(jù)互信息定義展開(kāi)有些文獻(xiàn)將I(X,Y)=H(Y)H(Y|X)H(Y|X)=H(X,Y)-H(Y|X)=H(Y)-I(X,Y)=H(X)+H(Y)-試證明：H(X|YH(X)，H(Y|X

強(qiáng)大的Venn圖：幫

思考題：天平 問(wèn)至少需要多少次稱(chēng)量才能找到這 答：3如何稱(chēng)量？如何證明

最大熵模型的原

例已知“學(xué)習(xí)”可以被標(biāo)為主語(yǔ)、謂語(yǔ)、賓語(yǔ)、定語(yǔ)令y1y2表示被標(biāo)為謂語(yǔ)，y3表示賓語(yǔ)，y4表示定語(yǔ)。得到下面的表示：4p(x1)p(x2)根據(jù)無(wú)偏原

p(yi)p(x1)p(x2)

p(y1)p(y2)p(y3)p(y4)引入新知 p(y4)0.05p(x1)p(x2)p(y)p(y)p(y)

再次引入新知p(y2|x1)

最大熵模 um概率平均分布等價(jià) 熵最p(x1)p(x2)44p(yi)p(y4)p(y2|x1)

最大熵模型maxH(Y|X)

p(x,y)logp(y|xx1,x2p(x1)p(x2)p(y1)p(y2)p(y3)p(y4)p(y4)p(y2|x1)

Maxent的一般maxH(Y|X)p(x,y)logp(y| x,y|p是X上滿(mǎn)足條件的概率分布注意區(qū)分這里的p和P

特征(Feature)和樣本y:這個(gè)特征中需要確定的信x:這個(gè)特征中的上下文信(xi,yi)xi是yi的上下(x1,y1)(x2,y2)

特征函關(guān)于某個(gè)特征(x,y)的樣y:x:特征函數(shù)：對(duì)于一個(gè)特征(x0,y0)，定義fx,y

xx0且y對(duì)于一個(gè)特征(x0,y0)，在樣本中的期望值p(f)p(x,y)f(x,xi,yipxy是(x,y)

條件px)x出現(xiàn)的概率pxyxy出現(xiàn)的概率pf特征f

條件p(f

pxi,yifxi,yixi,yi pyi|xipxifxi,yixi,yi pyi|xipxifxi,yixi,yip(f)p(f

最大熵模型：最大條件p*argmaxH(Y|X)p(x,y)logp(y| x,yp(f)p(f

最大熵模型在NLP中的完整提p*argmaxH(Y|Xp(x,y)logp(y|x,yp(y|x)pxlogp(y|x,yPpy|xfi:p(y|x)pxfix,yp(x,y)fix,y,x:

p(y|x)11 x,y

x,y

最大熵模型總定義條件 H(yx)p(y,x)logp(y(x,y模型目

p*(

x)argmaxH(yp(yx定義特征函 fi(x,y)

i1, ,約束條

p(E(fi)

x)(fi

i1, ,

(f) (x,y)f(x,y) f(x,

N (x,y (x,yE(fi) p(x,y)fi(x,y) p(x)p(yx)fi(x,(x,y (x,y

求解Maxent模該條件約束優(yōu)化問(wèn)題的Lagrange (p,)H(yx)iE(fi)E(fi)m1p(yx)1

i

已知若干條件，要求若干變量的值使到目標(biāo)函數(shù)(熵)最最優(yōu)化問(wèn)題(Optimization非線(xiàn)性規(guī)劃(線(xiàn)性約束 non-linearprogrammingwithlinear

L p(y|x)p(x)logp(y| x,y

(x,y

p(x)(logp(y|x)1)p(x)f(x,y)v p(y|0令0

0i p(x)p*(y|x)f(x,y)

f(x,y)

λ0與ν0僅相差常系數(shù)，后面的推導(dǎo)將直接以λ0代替

“泛函求導(dǎo)通過(guò)條件熵最大，能夠得到關(guān)于未知概率分布p(y|x)的目標(biāo)函數(shù)，而p(y|x)函數(shù)(隨 量)，從而，目標(biāo)函數(shù)的函——泛函。根據(jù)方程F求最優(yōu)的p(y|x)，是用的IIS算法

泛函求導(dǎo)——“類(lèi)比根據(jù)積分的定義，很容易得知以下兩個(gè)式xFxx

fxdxF'xf

xFxx

(1)(2)式中的t是關(guān)于x將其中的積分號(hào)變成加和符號(hào)，即得到如下式FxfxF'xfx

FxftxF'xf

p*(y|x)

f(x,y) p*(y|x)

f(x,y) Z f(x,

yZ

y y

最大熵模型與Logistic/Softmax回 eT

T

1

T

ex

eke k1,2,!,T TT

eT

1

e

1e ex

jp*(y|x)

f(x,y) Z

最大似然估 umlikelihood10次拋硬幣的結(jié)果是：正正反正正正反反正 p71

極大似然估計(jì)思考：如何求解p ppx

0xn logfxi;1,2,!

取對(duì)p logpxpxpxlogp Lpppx,ylogpx,x,x,px,ylogpy|xpx,x, x,

MLE與條件Lpppx,ylogpy|x,演示推 x,y

(x,

求L的對(duì)偶函

p(y|x)

Z ikp(y|x)p(x)logp(y|x) k

f(x,

i

p(y|x)

p(x,

v0 x, x,

(y|x)p(x)log

(y|x)

f(x,

i

p(x,x, x, p(x)p(y|x)logp(y|x)p(x)p(y|x)ifi(x,y)p(x,y)ifi(x,x, x, x, p(x)p(y|x)logp(y|x)p(x)p(y|x)ifi(x,y)p(x,y)ifi(x,x, x, x,kp(x)p(y|x)logZxp(x,y)ifi(x,kx, x,

帶入MLEpy|x

f(x,y) Z Lpppx,ylogpy|x, fx,ylogZpx,

npx,yifix,ypx,ylogZn npx,yifix,ypxlogZn kp(x)p(y|x)logZxp(x,y)ifi(x,k

結(jié)可以看到，二者的右端具有完全相同的目標(biāo)函根據(jù)MLE的正確性，可以斷定：最大熵的解(無(wú)偏做點(diǎn)思知識(shí)＝不確定度的

λ的求IIS：ImprovedIterativeScaling改進(jìn)的迭代尺具體內(nèi)容在本PPT最后篇末的附錄但工業(yè)界使用最多的仍然是梯度下降算法

Softmax參數(shù)求

IIS假設(shè)最大熵模型當(dāng)前的參數(shù)向量是λ，希望

再次強(qiáng)不確定度越小，模型越準(zhǔn)什么特征都不限定：熵最加一個(gè)特征：熵少一加的特征越多，熵越

總詞性標(biāo)注也可以看作一種編碼的過(guò)程求極值的技 ：Lagrange對(duì)偶問(wèn)最大熵模型，涉及了很多前序的數(shù)學(xué)知事實(shí)上，機(jī)器學(xué)習(xí)本身就是多

參考文ThomasM.Cover,JoyA.Thomas,ElementsofInformationTheory,AdamL.Berger,StephenA.DellaPietra,VincentJ.DellaPietra,Aumentropyapproachtonaturallanguageprocessing,1996AdamL.Berger,ABriefMaxEntTutorial,AdwaitRatnaparkhi,Learningtoparsenaturallanguagewithumentropymodels,1999AdwaitRatnaparkhi,AsimpleIntroductionto umEntropyModelsforNaturalLanguageProcessing,1997

我們?cè)谶@ 煩請(qǐng)邀請(qǐng)visio或其他人回答問(wèn)本課 (小象學(xué)院：機(jī)器學(xué)習(xí)群

附：IIS算法公

改進(jìn)的迭代尺度法p*(y|x)

Z

ifi(x,yeZ

eifi(