小象-机器学习-8.最大熵模型

法本课件包括演示文稿、示例、代码、题库、和在课程范围外向任何第散播。任何其他人或机构不得盗版、、仿造其中的创意及内容，我们 课 咨

邹本次目 理解联合熵H(X,Y)、相对熵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了解最大熵在自然语言处理NLP中的应 NaturalLanguage umLikelihood

预备定NlnN!NlnN lnN!lni

lnN1xlnxN1N1N

xdlnNlnN

x1dx1NlnNx1NlnNNNlnN

普通的一个的某一次投掷，出现点5的等概率：各点的概率都是对于“一无所知”的，假定所有点数等概对给定的某个，经过N次投掷后发现，

带约束的优化问令6个面朝上的概率为(p1,p2…p6)，用向量p表示

pln约束条

pi

ipiLp!,, plnp

ip

i求解

L

令

ln

11i2

15.932,2

预测结

从小学数学开 左边比右边右边比左边两边同样

答一种可能的称量方法如右图所答案：2追问：为什么2次

1+2?>=1?

3?5 51 2 3 41234

理论下令x表 币的序号：令yi表示第i次使用天平得到1表示“左轻”，2表示“平衡”，3用天平称n次，获得的结果是：y1y2…y1y2…yn的所有可能组合数目是根据题意，要求通过y1y2yn确定x。即影射map(y1y2…yn)=x；从而：y1y2…yn的变化数目大于等于x的变化数则：3n≥5——一般意义上Yn

进一步分YnXnlogYlogXnloglog用y1y2…yn表达x。即设计编码x：y1y2…log

log的“表达能力”是HYlog

log至少要多少个Y才能准确表示HXlog5H(Y log

题目的变 能够找

解

解释Huffman编12345

解释Huffman编1?3?12312345

附 定义信息某事件发生的概率小，则该事件的信思考：事件X的信息量的期望如何计算

熵注：经典熵的定义，底数是2，单位是本例中，为分析方便使用底数若底数是e，单位是nat(奈特

研究函数当f’(x)=0时，x=1/e由于limfx定义

离散采

绘

对熵的理解0HXlog熵是随量不确定性的度量，不确定性越大，熵值越大；若随量成定值，熵该不确定性度量的本质即为信息量的均匀分布是“最不确定”的分熵其实定义了一个函数(概率分布函数)到一(函数数值泛函：“变分推导”章

两点分布的

继续思考：三点分布呢HXpxlnpxp1lnp1p2lnp21p1p2ln1p1p2

组合数的关

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

自封闭系统的运动总是倒向均匀分

思考：根据函数形式判断概率分

2ln

ln

x

x该分布的对数是关于 根据计算过程的可逆性，若某对数分布能够写成随量二次形式，则该分布必然是正态分

举 px;,

x常系数

0lnpx;,ln1lnxxlnAxBlnx若某对数分布能够写成随

t1et

Gamma函数 Gamma分布的期望为：EX

若 成定值，熵最小：为若随机分布为均匀分布，熵最最大熵模

思考过argmaxHX

pxln

px

VarXEX2E2XEX2E2XVarX2

建立Lagrange函数，求驻

2x

xpx

x2px2

2

Llnpx1xx2 0lnpxx2x P(x)的对数是关于随

联合熵和条件 联合熵JointEntropy，用H(X,Y)表示(X,Y)发生所包含的熵，减去Y单独发生包含的该式子定义为Y发生前提下，X的熵条件熵

推导条件熵的定义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,

根据条件熵的定义式，可以得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

相对设p(x)、q(x)是X中取值的两个概率分布，则p对q相对熵Dp||q

x说明

px

相对熵可以度量两个 一般的，D(p||q)D(p||q)≥0D(q||p)0：凸函数中的Jensen

思假定已知随 方法：使用P和Q的K-L难点：K-L距离是非对称的，两个随

两个KL散度的区是使用近似p(z1,z2)=p(z1)p(z2)得到的等高左：KL(p||q)：zero右：KL(q||p)：zero

两个KL散度的区左：KL(p||q)：q趋向于覆盖中、右：KL(q||p)：q能够锁定某一个峰

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

计算条件熵的定义式：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

根据条件熵的定义式，可以得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)-根据互信息定义展开有些文献将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

强大的Venn图：帮

思考题：天平 问至少需要多少次称量才能找到这 答：3如何称量？如何证明

最大熵模型的原

例已知“学习”可以被标为主语、谓语、宾语、定语令y1y2表示被标为谓语，y3表示宾语，y4表示定语。得到下面的表示：4p(x1)p(x2)根据无偏原

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概率平均分布等价 熵最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上满足条件的概率分布注意区分这里的p和P

特征(Feature)和样本y:这个特征中需要确定的信x:这个特征中的上下文信(xi,yi)xi是yi的上下(x1,y1)(x2,y2)

特征函关于某个特征(x,y)的样y:x:特征函数：对于一个特征(x0,y0)，定义fx,y

xx0且y对于一个特征(x0,y0)，在样本中的期望值p(f)p(x,y)f(x,xi,yipxy是(x,y)

条件px)x出现的概率pxyxy出现的概率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模该条件约束优化问题的Lagrange (p,)H(yx)iE(fi)E(fi)m1p(yx)1

i

已知若干条件，要求若干变量的值使到目标函数(熵)最最优化问题(Optimization非线性规划(线性约束 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仅相差常系数，后面的推导将直接以λ0代替

“泛函求导通过条件熵最大，能够得到关于未知概率分布p(y|x)的目标函数，而p(y|x)函数(随 量)，从而，目标函数的函——泛函。根据方程F求最优的p(y|x)，是用的IIS算法

泛函求导——“类比根据积分的定义，很容易得知以下两个式xFxx

fxdxF'xf

xFxx

(1)(2)式中的t是关于x将其中的积分号变成加和符号，即得到如下式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次抛硬币的结果是：正正反正正正反反正 p71

极大似然估计思考：如何求解p ppx

0xn logfxi;1,2,!

取对p logpxpxpxlogp Lpppx,ylogpx,x,x,px,ylogpy|xpx,x, x,

MLE与条件Lpppx,ylogpy|x,演示推 x,y

(x,

求L的对偶函

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

结可以看到，二者的右端具有完全相同的目标函根据MLE的正确性，可以断定：最大熵的解(无偏做点思知识＝不确定度的

λ的求IIS：ImprovedIterativeScaling改进的迭代尺具体内容在本PPT最后篇末的附录但工业界使用最多的仍然是梯度下降算法

Softmax参数求

IIS假设最大熵模型当前的参数向量是λ，希望

再次强不确定度越小，模型越准什么特征都不限定：熵最加一个特征：熵少一加的特征越多，熵越

总词性标注也可以看作一种编码的过程求极值的技 ：Lagrange对偶问最大熵模型，涉及了很多前序的数学知事实上，机器学习本身就是多

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

我们在这 烦请邀请visio或其他人回答问本课 (小象学院：机器学习群

附：IIS算法公

改进的迭代尺度法p*(y|x)

Z

ifi(x,yeZ

eifi(