最大熵模型PPT学习教案

1、会计学1最大熵模型最大熵模型第1页/共95页已知：x1x2xn求：y1已知：x1x2xn y1求：y2已知：x1x2xn y1 y2求：y3已知：x1x2xn y1 y2 y3求：y4第2页/共95页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页/共95页x1x2xnp(y1=a|x1x2xn)x1x2xn y1p(y2=a|x1x2xn y1)x1x2xn y1 y2p(y3=a|x1x2xn y1 y

2、2)x1x2xn y1 y2 y3p(y4=a|x1x2xn y1 y2 y3)第4页/共95页).().,().|(111111nnnninniyyxxpyyxxaypyyxxayp一个直观的解决：问题again!(x1x2xn y1y2yi-1)？第5页/共95页第6页/共95页1+2 ? 3+41 ? 23 ? 4514=23第7页/共95页5,4,3,2,1 Xx表示；表示；表示其中321:3.1YyiXYn第8页/共95页5 , 4 , 3 , 2 , 1 Xx表示；表示；表示其中321:3.1Yyi5loglogXXH 3loglogYYH 46. 13log5log)(YHXH第

3、9页/共95页 5loglogXXH 3loglogYYH 46. 13log5log)(YHXH第10页/共95页 YYYYYYHYHYHyHyH注意：)()()(21第11页/共95页 46. 13log5log)(YHXH第12页/共95页第13页/共95页343log9log9133log3log3131第14页/共95页51/911/341/921/331/9第15页/共95页3 ? 51/351/911/341/921/331/9第16页/共95页1 ? 23 ? 51/351/911/341/921/331/9用反证法可以证明，这个是最小值。（假设第一个和第二个硬币中有一个要称两

4、次的话）第17页/共95页1 ? 23 ? 51/351/911/341/921/331/91/91/91/91/91/91/9343log9log9133log3log3131第18页/共95页 kiiixxpxxpXH11log一般地，我们令c为2（二进制表示），于是，X的信息量为：cxxpxxpcxxpxxpkiiikiiilog1loglog1log11第19页/共95页 kiiixxpxxpXH11log XxxpxpXH1log第20页/共95页 XXHlog0第21页/共95页)(0XH 001log01log01log1101:1logXHxpxpxpxpxpxpxpxxpxp

5、XHXxXx即第22页/共95页XXHlog)(第23页/共95页YXyxyxpyxpYXH,|1log,|)()()|(YHXYHYXH)()|(XHYXH第24页/共95页)()|(XHYXHXY(X&Y)I: Complete KnowledgeSpace第25页/共95页第26页/共95页5 . 0)()(21xpxp如果仅仅知道这一点，根据无偏见原则，“学习”被标为名词的概率与它被标为动词的概率相等。1)()(21xpxp1)(41iiyp25. 0)()()()(4321ypypypyp第27页/共95页5 . 0)()(21xpxp除此之外，仍然坚持无偏见原则：05. 0

6、)(4yp我们引入这个新的知识：1)()(21xpxp1)(41iiyp395. 0)()()(321ypypyp第28页/共95页除此之外，仍然坚持无偏见原则，我们尽量使概率分布平均。但问题是：什么是尽量平均的分布？05. 0)(4yp引入这个新的知识：1)()(21xpxp1)(41iiyp95. 0)|(12xyp第29页/共95页1)()(21xpxp1)(41iiyp05. 0)(4yp95. 0)|(12xyp第30页/共95页95. 0)|(05. 0)(1)()()()(1)()()|(1log),()|(max124432121,432121xypypypypypypxpxp

7、xypyxpXYHyyyyyxxx第31页/共95页What is Constraints?-模型要与已知知识吻合What is known?-训练数据集合一般模型：P=p|p是X上满足条件的概率分布yxPpxypyxpXYH,)|(1log),()|(max第32页/共95页x1x2xnp(y1=a|x1x2xn)x1x2xn y1p(y2=a|x1x2xn y1)第33页/共95页第34页/共95页已知：“学习”可能是动词，也可能是名词。可以被标为主语、谓语、宾语、定语“学习”被标为定语的可能性很小，只有0.05特征：当“学习”被标作动词的时候，它被标作谓语的概率为0.95x是什么? y是

8、什么?样本是什么?第35页/共95页已知：“学习”可能是动词，也可能是名词。可以被标为主语、谓语、宾语、定语特征：“学习”被标为定语的可能性很小，只有0.05当“学习”被标作动词的时候，它被标作谓语的概率为0.95x是什么? y是什么?样本是什么?第36页/共95页特征函数：对于一个特征(x0,y0)，定义特征函数：特征函数期望值：对于一个特征(x0,y0) ，在样本中的期望值是：其他情况而且：如果0 xy1),(00 xyyxfiiyxyxfyxpfp,),(),()(是(x,y)在样本中出现的概率),(yxp第37页/共95页条件：对每一个特征(x,y)，模型所建立的条件概率分布要与训练样

9、本表现出来的分布相同。出现的概率xxp)(在样本中的期望值特征ffp)(假设样本的分布是（已知）：出现的概率xyyxp),(特征f在模型中的期望值： iiiiiiyxiiiiiyxiiiiiyxiiiiyxfxpxypyxfxpxypyxfyxpfp,|,|,)()()(fpfp第38页/共95页)|(*maxargXYHpPpP=p|p是y|x的概率分布并且满足下面的条件对训练样本，对任意给定的特征fi：)()(iifpfp第39页/共95页 yyxiyxiixypxyxfyxpyxfxpxypfxypP1|:),(,),(|:|, yxPpxypxpxypp,|1log|*maxarg第4

10、0页/共95页定义条件熵( , )()( , )log ()x yzH y xp y xp y x *()()arg max()p y xPpy xH y x 模型目的定义特征函数( , )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

11、 NT （1）()1y Yp y x （2）第41页/共95页 11( ,)()()()()1miiimiy YpH y xE fE fp y x 该条件约束优化问题的Lagrange函数第42页/共95页第43页/共95页第44页/共95页bAppH)(max如何去掉约束？抽象问题：假设：A的行向量线性无关。bAp 确定了m维空间里面n个方向上（就是与Ap=b确定的m-n个方向“垂直”的n个方向）的取值。p只能在剩下的r=m-n个方向上面移动。第45页/共95页bAp bpAZvpp就是p能够自由活动的所有空间了。 v: m-n维变量于是有：00:AZZvAbZvpAv第46页/共95页bA

12、ppH)(max如何去掉约束？抽象问题：0AZbpAZvpp)(maxZvpHZ: m*(m-n)常数矩阵v: m-n维变量第47页/共95页)(maxZvpHZ: m*(m-n)常数矩阵v: m-n维变量是正定矩阵而且0)(0)(*2*vHvH0AZbpAZvpp极值条件：ZpHZvHpHZvHTT)()();()(*2*2*把 分解成Z方向向量和A方向向量：)(*pHTAZvpH)(*第48页/共95页Z: m*(m-n)常数矩阵v: m-n维变量0AZbpAZvpp0000ZvZvZAZAZZvZTTTT00)()()(*TTTTTAZZvZpHZvHAZvpHTTAxHZvAZvpH)

13、(0)(*第49页/共95页0)()(*pLApHTbAppH)(max令：假设：A的行向量线性无关。AppHpL)()(*)()()(*AppHApHT第50页/共95页)(maxpH iibpCki:1 拉格朗日函数为： kiiiibpCpHpL1, 其中引入的拉格朗日算子：Tk,.,1第51页/共95页Tk,.,1bAppH)(max kiiiiibpCpHpL1,0pL第52页/共95页1|),()()|(),()|(1log)()|(0),(),(yiyxiiyxxypyxpxpxypyxfxypxpxypL yyxiyxiixypxyxfyxpyxfxpxypfxypP1|:),(

14、,),(|:|, yxPpxypxpxypp,|1log|*maxarg第53页/共95页1|),()()|(),()|(1log)()|(01),(),(ykiyxiiyxxypyxpxpxypyxfxypxpxypLiiiyxfxpxypxpxypL0),()() 1)|(1)(log()|(1)(),(0)|(*xpyxfiiiexyp第54页/共95页0),()() 1)|(1)(log()|(0iiiyxfxpxypxpxypL1)(),(0)|(*xpyxfiiiexyp0)|()()|(22xypxpxypL第55页/共95页1)(),(0)|(*xpyxfiiiexypiiiy

15、xfcexyp),()|(*yyxfiiiec),(1yyxfiiice1),(第56页/共95页iiiyxfcexyp),()|(*yyxfiiiec),(1iiiyxfexZxyp),()(1)|(*yyxfiiiexZ),()(?i第57页/共95页? 几乎不可能有解析解（包含指数函数） 近似解不代表接近驻点。)(f第58页/共95页3421C第59页/共95页yxCAliceBobyBobxAliceC,:3421双方都很聪明：双方都对对方有“最坏打算”yxxyC,maxminyxyxC,minmax第60页/共95页yxCAliceBobyBobxAliceC,:3421yxxyCy

16、,maxminarg* yxyxCx,minmaxarg*31min,yxyC34max,yxxC3:2, 2CAliceBob第61页/共95页yxCAliceBobyBobxAliceC,:2421yxxyCy,maxminarg* yxyxCx,minmaxarg*21min,yxyC24max,yxxC2:2, 1CAliceBob第62页/共95页yxxyyxyxCC,maxminminmax定理：当存在马鞍点（Saddle Point）的时候，等号成立。并且结果=马鞍点的值。马鞍点：yxyxyxCCCyx*,*,*,|*)*,(第63页/共95页)(maxpH iibpCki:1拉

17、格朗日函数： kiiiibpCpHpL1,于是：,minmaxpLp iiiibpCibpCipHpL:,min因此，为了尽量大，p的选取必须保证满足约束ppHpLp| )(max,minmax iibpCki:1考虑：第64页/共95页)(maxpH iibpCki:1同时： kiiiipbpCpHpL1,minmax等价于：,maxmin,minmaxpLpLpp而*,maxpLpLpiiiyxfexZxyp),()(1)|(*第65页/共95页 *,min,maxmin,minmaxmaxppLpLpLpHpp满足约束iiiyxfexZxyp),()(1)|(*?第66页/共95页 xy

18、xyxyxyxkiyxiixZxpyxyxpyxyxpxZxypxpyxyxpyxxZyxxypxpyxyxpyxxypxypxpyxpxypxpyxfpHpLlog,log|,log,|,|log|,|,*,1,把p*代入L，得到： 令：kiiiyxfyx1,第67页/共95页求导，计算-L的梯度： xyxxZxpyxyxppLlog,*,kiiiyxfyx1, xyjipxyjyxfyxixiyxixyxkjjjiiyxfxypxpfEyxfexZxpyxfyxpxZxZxpyxfyxpxZxpyxfyxpLkjjj,|*,1,1,log,1,1yyxfiiiexZ),()(第68页/共9

19、5页递推公式： yxjipiyxfxypxpfEL,|* yxjipniniyxfxypxpfEc,1,|*收敛问题第69页/共95页371111ppppppppppppP第70页/共95页371ppP37101maxmaxppPp 最优解是：p=0.7 似然率的一般定义： xxppxpL 是实验结果的分布模型是估计的概率分布xpxp第71页/共95页 似然率的一般定义： xxppxpL 似然率的对数形式： xxxppxpxpxpLloglog 是实验结果的分布模型是估计的概率分布xpxp第72页/共95页 在NLP里面，要估计的是：语法标注上下文:|yxxyp 似然率是： yxyxyxyxpxpyxpxypyxpxypxpyxpyxpyxppL,log,|log,|log,log,是常数，可以忽略 yxxypxpyxp,|log,第73页/共95页 在NLP里面，要估计的是：语法标注上下文:|yxxyp 似然率可以定义为： yxpxypyxppL,|log, 通过求值可以发现，如果p(y|x)的形式是最大熵模型的形式的话，最大熵模型与最大似然率模型一致。第74页/共95页 yxxyxyxyxyxyxpxZxpyxyxpxZeyxpxZeyxpxypyxppL,log,loglog,log,|log,kiiiyxfyx1, xZyxexZxyp,1|第