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

1、會(huì)計(jì)學(xué)1最大熵模型最大熵模型(mxng)第一頁(yè)，共95頁(yè)。第1頁(yè)/共95頁(yè)第二頁(yè)，共95頁(yè)。已知：x1x2xn求：y1已知：x1x2xn y1求：y2已知：x1x2xn y1 y2求：y3已知：x1x2xn y1 y2 y3求：y4第2頁(yè)/共95頁(yè)第三頁(yè)，共95頁(yè)。x1x2xnp(y1=a|x1x2xn)x1x2xn y1p(y2=a|x1x2xn y1)x1x2xn y1 y2p(y3=a|x1x2xn y1 y2)x1x2xn y1 y2 y3p(y4=a|x1x2xn y1 y2 y3)第3頁(yè)/共95頁(yè)第四頁(yè)，共95頁(yè)。x1x2xnp(y1=a|x1x2xn)x1x2xn y1p(y2=

2、a|x1x2xn y1)x1x2xn y1 y2p(y3=a|x1x2xn y1 y2)x1x2xn y1 y2 y3p(y4=a|x1x2xn y1 y2 y3)第4頁(yè)/共95頁(yè)第五頁(yè)，共95頁(yè)。).().,().|(111111nnnninniyyxxpyyxxaypyyxxayp一個(gè)直觀(zhgun)的解決：?jiǎn)栴}again!(x1x2xn y1y2yi-1)？第5頁(yè)/共95頁(yè)第六頁(yè)，共95頁(yè)。第6頁(yè)/共95頁(yè)第七頁(yè)，共95頁(yè)。1+2 ? 3+41 ? 23 ? 4514=23第7頁(yè)/共95頁(yè)第八頁(yè)，共95頁(yè)。5,4,3,2,1 Xx表示；表示；表示其中321:3.1YyiXYn第8頁(yè)/共

3、95頁(yè)第九頁(yè)，共95頁(yè)。5 , 4 , 3 , 2 , 1 Xx表示；表示；表示其中321:3.1Yyi5loglogXXH 3loglogYYH 46. 13log5log)(YHXH第9頁(yè)/共95頁(yè)第十頁(yè)，共95頁(yè)。 5loglogXXH 3loglogYYH 46. 13log5log)(YHXH第10頁(yè)/共95頁(yè)第十一頁(yè)，共95頁(yè)。 YYYYYYHYHYHyHyH注意：)()()(21第11頁(yè)/共95頁(yè)第十二頁(yè)，共95頁(yè)。 46. 13log5log)(YHXH第12頁(yè)/共95頁(yè)第十三頁(yè)，共95頁(yè)。第13頁(yè)/共95頁(yè)第十四頁(yè)，共95頁(yè)。343log9log9133log3log3131

4、第14頁(yè)/共95頁(yè)第十五頁(yè)，共95頁(yè)。51/911/341/921/331/9第15頁(yè)/共95頁(yè)第十六頁(yè)，共95頁(yè)。3 ? 51/351/911/341/921/331/9第16頁(yè)/共95頁(yè)第十七頁(yè)，共95頁(yè)。1 ? 23 ? 51/351/911/341/921/331/9用反證法可以(ky)證明，這個(gè)是最小值。（假設(shè)第一個(gè)和第二個(gè)硬幣中有一個(gè)要稱兩次的話）第17頁(yè)/共95頁(yè)第十八頁(yè)，共95頁(yè)。1 ? 23 ? 51/351/911/341/921/331/91/91/91/91/91/91/9343log9log9133log3log3131第18頁(yè)/共95頁(yè)第十九頁(yè)，共95頁(yè)。 kiii

5、xxpxxpXH11log一般地，我們(w men)令c為2（二進(jìn)制表示），于是，X的信息量為：cxxpxxpcxxpxxpkiiikiiilog1loglog1log11第19頁(yè)/共95頁(yè)第二十頁(yè)，共95頁(yè)。 kiiixxpxxpXH11log XxxpxpXH1log第20頁(yè)/共95頁(yè)第二十一頁(yè)，共95頁(yè)。 XXHlog0第21頁(yè)/共95頁(yè)第二十二頁(yè)，共95頁(yè)。)(0XH 001log01log01log1101:1logXHxpxpxpxpxpxpxpxxpxpXHXxXx即第22頁(yè)/共95頁(yè)第二十三頁(yè)，共95頁(yè)。XXHlog)(第23頁(yè)/共95頁(yè)第二十四頁(yè)，共95頁(yè)。YXyxyxpyx

6、pYXH,|1log,|)()()|(YHXYHYXH)()|(XHYXH第24頁(yè)/共95頁(yè)第二十五頁(yè)，共95頁(yè)。)()|(XHYXHXY(X&Y)I: Complete KnowledgeSpace第25頁(yè)/共95頁(yè)第二十六頁(yè)，共95頁(yè)。第26頁(yè)/共95頁(yè)第二十七頁(yè)，共95頁(yè)。5 . 0)()(21xpxp如果僅僅知道(zh do)這一點(diǎn)，根據(jù)無(wú)偏見原則，“學(xué)習(xí)”被標(biāo)為名詞的概率與它被標(biāo)為動(dòng)詞的概率相等。1)()(21xpxp1)(41iiyp25. 0)()()()(4321ypypypyp第27頁(yè)/共95頁(yè)第二十八頁(yè)，共95頁(yè)。5 . 0)()(21xpxp除此之外，仍然堅(jiān)持(j

7、inch)無(wú)偏見原則：05. 0)(4yp我們引入這個(gè)新的知識(shí)：1)()(21xpxp1)(41iiyp395. 0)()()(321ypypyp第28頁(yè)/共95頁(yè)第二十九頁(yè)，共95頁(yè)。除此之外，仍然堅(jiān)持無(wú)偏見原則，我們盡量使概率分布平均。但問(wèn)題(wnt)是：什么是盡量平均的分布？05. 0)(4yp引入這個(gè)新的知識(shí)：1)()(21xpxp1)(41iiyp95. 0)|(12xyp第29頁(yè)/共95頁(yè)第三十頁(yè)，共95頁(yè)。1)()(21xpxp1)(41iiyp05. 0)(4yp95. 0)|(12xyp第30頁(yè)/共95頁(yè)第三十一頁(yè)，共95頁(yè)。95. 0)|(05. 0)(1)()()()(1

8、)()()|(1log),()|(max124432121,432121xypypypypypypxpxpxypyxpXYHyyyyyxxx第31頁(yè)/共95頁(yè)第三十二頁(yè)，共95頁(yè)。What is Constraints?-模型要與已知知識(shí)吻合What is known?-訓(xùn)練(xnlin)數(shù)據(jù)集合一般(ybn)模型：P=p|p是X上滿足條件的概率分布yxPpxypyxpXYH,)|(1log),()|(max第32頁(yè)/共95頁(yè)第三十三頁(yè)，共95頁(yè)。x1x2xnp(y1=a|x1x2xn)x1x2xn y1p(y2=a|x1x2xn y1)第33頁(yè)/共95頁(yè)第三十四頁(yè)，共95頁(yè)。第34頁(yè)/共95

9、頁(yè)第三十五頁(yè)，共95頁(yè)。已知：“學(xué)習(xí)(xux)”可能是動(dòng)詞，也可能是名詞?？梢员粯?biāo)為主語(yǔ)、謂語(yǔ)、賓語(yǔ)、定語(yǔ)“學(xué)習(xí)(xux)”被標(biāo)為定語(yǔ)的可能性很小，只有0.05特征：當(dāng)“學(xué)習(xí)(xux)”被標(biāo)作動(dòng)詞的時(shí)候，它被標(biāo)作謂語(yǔ)的概率為0.95x是什么(shn me)? y是什么(shn me)?樣本是什么(shn me)?第35頁(yè)/共95頁(yè)第三十六頁(yè)，共95頁(yè)。已知：“學(xué)習(xí)”可能是動(dòng)詞，也可能是名詞?？梢员粯?biāo)為主語(yǔ)、謂語(yǔ)、賓語(yǔ)、定語(yǔ)(dngy)特征：“學(xué)習(xí)”被標(biāo)為定語(yǔ)(dngy)的可能性很小，只有0.05當(dāng)“學(xué)習(xí)”被標(biāo)作動(dòng)詞的時(shí)候，它被標(biāo)作謂語(yǔ)的概率為0.95x是什么(shn me)? y是什么(shn

10、 me)?樣本是什么(shn me)?第36頁(yè)/共95頁(yè)第三十七頁(yè)，共95頁(yè)。特征函數(shù)：對(duì)于一個(gè)(y )特征(x0,y0)，定義特征函數(shù)：特征函數(shù)期望值：對(duì)于(duy)一個(gè)特征(x0,y0) ，在樣本中的期望值是：其他情況而且：如果0 xy1),(00 xyyxfiiyxyxfyxpfp,),(),()(是(x,y)在樣本中出現(xiàn)的概率),(yxp第37頁(yè)/共95頁(yè)第三十八頁(yè)，共95頁(yè)。條件：對(duì)每一個(gè)特征(x,y)，模型所建立的條件概率分布要與訓(xùn)練樣本表現(xiàn)(bioxin)出來(lái)的分布相同。出現(xiàn)的概率xxp)(在樣本中的期望值特征ffp)(假設(shè)(jish)樣本的分布是（已知）：出現(xiàn)的概率xyyxp)

11、,(特征f在模型中的期望值： iiiiiiyxiiiiiyxiiiiiyxiiiiyxfxpxypyxfxpxypyxfyxpfp,|,|,)()()(fpfp第38頁(yè)/共95頁(yè)第三十九頁(yè)，共95頁(yè)。)|(*maxargXYHpPpP=p|p是y|x的概率分布并且(bngqi)滿足下面的條件對(duì)訓(xùn)練樣本，對(duì)任意給定的特征fi：)()(iifpfp第39頁(yè)/共95頁(yè)第四十頁(yè)，共95頁(yè)。 yyxiyxiixypxyxfyxpyxfxpxypfxypP1|:),(,),(|:|, yxPpxypxpxypp,|1log|*maxarg第40頁(yè)/共95頁(yè)第四十一頁(yè)，共95頁(yè)。定義(dngy)條件熵( ,

12、 )()( , )log ()x yzH y xp y xp y x *()()arg max()p y xPpy xH y x 模型(mxng)目的定義(dngy)特征函數(shù)( , )0,1if x y ()()iiE fE f 約束條件1,2,im 1,2,im ( , )()( , )( , )iix yzE fp x y f x y ( , )()( , )( , )iix yzE fp x y f x y ( , )( ) ()( , )ix yzp x p y x f x y ( , )1( , )ix yTf x yN 1()( , )ix T y Yp y x f x yN NT

13、 （1）()1y Yp y x （2）第41頁(yè)/共95頁(yè)第四十二頁(yè)，共95頁(yè)。 11( ,)()()()()1miiimiy YpH y xE fE fp y x 該條件約束(yush)優(yōu)化問(wèn)題的Lagrange函數(shù)第42頁(yè)/共95頁(yè)第四十三頁(yè)，共95頁(yè)。第43頁(yè)/共95頁(yè)第四十四頁(yè)，共95頁(yè)。第44頁(yè)/共95頁(yè)第四十五頁(yè)，共95頁(yè)。bAppH)(max如何去掉約束？抽象(chuxing)問(wèn)題：假設(shè)：A的行向量線性無(wú)關(guān)。bAp 確定了m維空間里面n個(gè)方向上（就是與Ap=b確定的m-n個(gè)方向“垂直”的n個(gè)方向）的取值。p只能在剩下的r=m-n個(gè)方向上面移動(dòng)。第45頁(yè)/共95頁(yè)第四十六頁(yè)，共95頁(yè)

14、。bAp bpAZvpp就是p能夠自由活動(dòng)的所有空間(kngjin)了。v: m-n維變量于是有：00:AZZvAbZvpAv第46頁(yè)/共95頁(yè)第四十七頁(yè)，共95頁(yè)。bAppH)(max如何去掉約束？抽象(chuxing)問(wèn)題：0AZbpAZvpp)(maxZvpHZ: m*(m-n)常數(shù)矩陣v: m-n維變量第47頁(yè)/共95頁(yè)第四十八頁(yè)，共95頁(yè)。)(maxZvpHZ: m*(m-n)常數(shù)矩陣(j zhn)v: m-n維變量是正定矩陣而且0)(0)(*2*vHvH0AZbpAZvpp極值(j zh)條件：ZpHZvHpHZvHTT)()();()(*2*2*把 分解成Z方向向量和A方向向量：

15、)(*pHTAZvpH)(*第48頁(yè)/共95頁(yè)第四十九頁(yè)，共95頁(yè)。Z: m*(m-n)常數(shù)矩陣(j zhn)v: m-n維變量0AZbpAZvpp0000ZvZvZAZAZZvZTTTT00)()()(*TTTTTAZZvZpHZvHAZvpHTTAxHZvAZvpH)(0)(*第49頁(yè)/共95頁(yè)第五十頁(yè)，共95頁(yè)。0)()(*pLApHTbAppH)(max令：假設(shè)(jish)：A的行向量線性無(wú)關(guān)。AppHpL)()(*)()()(*AppHApHT第50頁(yè)/共95頁(yè)第五十一頁(yè)，共95頁(yè)。)(maxpH iibpCki:1拉格朗日函數(shù)(hnsh)為： kiiiibpCpHpL1,其中引入的

16、拉格朗日算子：Tk,.,1第51頁(yè)/共95頁(yè)第五十二頁(yè)，共95頁(yè)。Tk,.,1bAppH)(max kiiiiibpCpHpL1,0pL第52頁(yè)/共95頁(yè)第五十三頁(yè)，共95頁(yè)。1|),()()|(),()|(1log)()|(0),(),(yiyxiiyxxypyxpxpxypyxfxypxpxypL yyxiyxiixypxyxfyxpyxfxpxypfxypP1|:),(,),(|:|, yxPpxypxpxypp,|1log|*maxarg第53頁(yè)/共95頁(yè)第五十四頁(yè)，共95頁(yè)。1|),()()|(),()|(1log)()|(01),(),(ykiyxiiyxxypyxpxpxypyx

17、fxypxpxypLNoImageiiiyxfxpxypxpxypL0),()() 1)|(1)(log()|(1)(),(0)|(*xpyxfiiiexyp第54頁(yè)/共95頁(yè)第五十五頁(yè)，共95頁(yè)。NoImage0),()() 1)|(1)(log()|(0iiiyxfxpxypxpxypL1)(),(0)|(*xpyxfiiiexyp0)|()()|(22xypxpxypL第55頁(yè)/共95頁(yè)第五十六頁(yè)，共95頁(yè)。NoImage1)(),(0)|(*xpyxfiiiexypiiiyxfcexyp),()|(*yyxfiiiec),(1yyxfiiice1),(第56頁(yè)/共95頁(yè)第五十七頁(yè)，共9

18、5頁(yè)。NoImageiiiyxfcexyp),()|(*yyxfiiiec),(1iiiyxfexZxyp),()(1)|(*yyxfiiiexZ),()(?i第57頁(yè)/共95頁(yè)第五十八頁(yè)，共95頁(yè)。NoImage?幾乎不可能有解析解（包含指數(shù)函數(shù)(zh sh hn sh)）近似解不代表接近駐點(diǎn)。)(f第58頁(yè)/共95頁(yè)第五十九頁(yè)，共95頁(yè)。3421C第59頁(yè)/共95頁(yè)第六十頁(yè)，共95頁(yè)。yxCAliceBobyBobxAliceC,:3421雙方(shungfng)都很聰明：雙方(shungfng)都對(duì)對(duì)方有“最壞打算”yxxyC,maxminyxyxC,minmax第60頁(yè)/共95頁(yè)第六十

19、一頁(yè)，共95頁(yè)。yxCAliceBobyBobxAliceC,:3421yxxyCy,maxminarg* yxyxCx,minmaxarg*31min,yxyC34max,yxxC3:2, 2CAliceBob第61頁(yè)/共95頁(yè)第六十二頁(yè)，共95頁(yè)。yxCAliceBobyBobxAliceC,:2421yxxyCy,maxminarg* yxyxCx,minmaxarg*21min,yxyC24max,yxxC2:2, 1CAliceBob第62頁(yè)/共95頁(yè)第六十三頁(yè)，共95頁(yè)。yxxyyxyxCC,maxminminmax定理：當(dāng)存在馬鞍(m n)點(diǎn)（Saddle Point）的時(shí)候，等

20、號(hào)成立。并且結(jié)果=馬鞍(m n)點(diǎn)的值。馬鞍(m n)點(diǎn)：yxyxyxCCCyx*,*,*,|*)*,(第63頁(yè)/共95頁(yè)第六十四頁(yè)，共95頁(yè)。)(maxpH iibpCki:1拉格朗日函數(shù)(hnsh)： kiiiibpCpHpL1,于是(ysh)：,minmaxpLp iiiibpCibpCipHpL:,min因此，為了盡量大，p的選取必須保證滿足約束ppHpLp| )(max,minmax iibpCki:1考慮：第64頁(yè)/共95頁(yè)第六十五頁(yè)，共95頁(yè)。)(maxpH iibpCki:1同時(shí)(tngsh)： kiiiipbpCpHpL1,minmax等價(jià)(dngji)于：,maxmin,m

21、inmaxpLpLpp而*,maxpLpLpiiiyxfexZxyp),()(1)|(*第65頁(yè)/共95頁(yè)第六十六頁(yè)，共95頁(yè)。 *,min,maxmin,minmaxmaxppLpLpLpHpp滿足約束iiiyxfexZxyp),()(1)|(*?第66頁(yè)/共95頁(yè)第六十七頁(yè)，共95頁(yè)。 xyxyxyxyxkiyxiixZxpyxyxpyxyxpxZxypxpyxyxpyxxZyxxypxpyxyxpyxxypxypxpyxpxypxpyxfpHpLlog,log|,log,|,|log|,|,*,1,把p*代入L，得到(d do)： 令：kiiiyxfyx1,第67頁(yè)/共95頁(yè)第六十八頁(yè)，

22、共95頁(yè)。求導(dǎo)，計(jì)算(j sun)-L的梯度： xyxxZxpyxyxppLlog,*,kiiiyxfyx1, xyjipxyjyxfyxixiyxixyxkjjjiiyxfxypxpfEyxfexZxpyxfyxpxZxZxpyxfyxpxZxpyxfyxpLkjjj,|*,1,1,log,1,1yyxfiiiexZ),()(第68頁(yè)/共95頁(yè)第六十九頁(yè)，共95頁(yè)。遞推公式(gngsh)： yxjipiyxfxypxpfEL,|* yxjipniniyxfxypxpfEc,1,|*收斂(shulin)問(wèn)題第69頁(yè)/共95頁(yè)第七十頁(yè)，共95頁(yè)。371111ppppppppppppP第70頁(yè)/共

23、95頁(yè)第七十一頁(yè)，共95頁(yè)。371ppP37101maxmaxppPp最優(yōu)解是：p=0.7似然率的一般(ybn)定義： xxppxpL 是實(shí)驗(yàn)結(jié)果的分布模型是估計(jì)的概率分布xpxp第71頁(yè)/共95頁(yè)第七十二頁(yè)，共95頁(yè)。似然率的一般(ybn)定義： xxppxpL似然率的對(duì)數(shù)(du sh)形式： xxxppxpxpxpLloglog 是實(shí)驗(yàn)結(jié)果的分布模型是估計(jì)的概率分布xpxp第72頁(yè)/共95頁(yè)第七十三頁(yè)，共95頁(yè)。 在NLP里面(lmin)，要估計(jì)的是：語(yǔ)法標(biāo)注上下文:|yxxyp似然率是： yxyxyxyxpxpyxpxypyxpxypxpyxpyxpyxppL,log,|log,|log

24、,log,是常數(shù)，可以(ky)忽略 yxxypxpyxp,|log,第73頁(yè)/共95頁(yè)第七十四頁(yè)，共95頁(yè)。在NLP里面(lmin)，要估計(jì)的是：語(yǔ)法標(biāo)注上下文:|yxxyp似然率可以(ky)定義為： yxpxypyxppL,|log,通過(guò)求值可以(ky)發(fā)現(xiàn)，如果p(y|x)的形式是最大熵模型的形式的話，最大熵模型與最大似然率模型一致。第74頁(yè)/共95頁(yè)第七十五頁(yè)，共95頁(yè)。 yxxyxyxyxyxyxpxZxpyxyxpxZeyxpxZeyxpxypyxppL,log,loglog,log,|log,kiiiyxfyx1, xZyxexZxyp,1|第75頁(yè)/共95頁(yè)第七十六頁(yè)，共95頁(yè)。 xyxyxyxyxkiyxiixZxpyxyxpyxyxpxZxypxpyxyxpyxxZyxxypxpyxyxpyxxypxypxpyxpx