Alex_McAvoy

想要成为渔夫的猎手

最大熵模型的学习

Reference

【对偶函数的极大化】

对于最大熵模型的约束最优化问题,内部的极小化问题的求解得到了关于 ω 的对偶函数

ψ(ω)=minpCL(p,ω)=L(pω,ω)

此时,只需对最大熵模型进行学习,即对对偶问题 maxωminpCL(p,ω) 的外部极大化问题进行处理

将极大化问题的解记为 ω,有:

ω=argmaxωψ(ω)

pω(y|x) 代入到对偶函数 ψ(ω) 中,可得:

ψ(ω)=xXp~(x)yYp(y|x)logp(y|x)+ω(0)[1yYp(y|x)]+j=1mω(j)[xXyYp~(x,y)fj(x,y)xXp~(x)yYp(y|x)fj(x,y)]=xXp~(x)yYpω(y|x)logpω(y|x)+ω(0)[1yYpω(y|x)]+j=1mω(j)[xXyYp~(x,y)fj(x,y)xXp~(x)yYpω(y|x)fj(x,y)]

由于 yYp(y|x)=1,故有:

ψ(ω)=xX,yYp~(x)logpω(y|x)+j=1mω(j)xX,yYp~(x,y)fj(x,y) j=1mω(j)xX,yYp~(x)fj(x,y)

又因为:

logpω(y|x)=j=1mω(j)fj(x,y)logZω(x)

则有:

ψ(ω)=xX,yYp~(x)[j=1mω(j)fj(x,y)logZω(x)]+j=1mω(j)xX,yYp~(x,y)fj(x,y)j=1mω(j)xX,yYp~(x)fj(x,y)

化简得:

ψ(ω)=xX,yYp~(x,y)j=1mω(j)fj(x,y)xXp~(x)logZω(x)

故极大化问题为:

ω=argmaxω[xX,yYp~(x,y)j=1mω(j)fj(x,y)xXp~(x)logZω(x)]

【最大熵模型的极大似然估计】

假设样本集大小为 n,对于样本具体观测值 x1,x2,,xn,假设其取值有 K 个,分别为 v1,v2,,vK,用 C(X=vi) 表示在观测值中样本 vi 出现的频数,那么似然函数可写为:

L(x1,x2,...,xn;θ)=k=1Kp(vk;θ)C(X=vk)

对上式两边同时开 1n 次方,可得:

L(x1,x2,...,xn;θ)1n=k=1kp(vk;θ)C(X=vk)n

由于经验概率 p~(x)=C(X=vk)n,故有:

L(x1,x2,...,xn;θ)1n=xXp(x;θ)p~(x)

显然,对 L(x1,x2,,xn;θ)1n 求极大值与对 L(x1,x2,,xn;θ) 求极大值的优化结果是相同的,那么,最终的极大似然函数可表示为:

L(x;θ)=xXp(x;θ)p~(x)

当已知训练数据的经验概率分布为 p~(X,Y) 时,有:

Lp~=logxX,yYp(x,y)p~(x,y)=xX,yYp~(x,y)logp(x,y)=xX,yYp~(x,y)log[p~(x)p(y|x)]=xX,yYp~(x,y)logp(y|x)+xX,yYp~(x,y)logp~(x)

其中,对于第二项 xX,yYp~(x,y)logp~(x),一旦样本集确定,经验分布 p~(x,y)p~(x) 可直接算出,故该项为一常数,忽略即可,故而最终的对数似然函数为:

Lp~=xX,yYp~(x,y)logp(y|x)

当条件概率分布 p(y|x) 为最大熵模型 pω(y|x)=1Zω(x)exp[j=1mω(j)fj(x,y)] 时,对数似然函数为:

Lp~(pω)=xX,yYp~(x,y)logpω(y|x)=xX,yYp~(x,y)j=1mω(j)fj(x,y)xX,yYp~(x,y)logZω(x)=xX,yYp~(x,y)j=1mω(j)fj(x,y)xXp~(x)logZω(x)

可以发现,对数似然函数 Lp~(pω) 与对偶函数 ψ(ω) 相等,即:

Lp~(pω)=ψ(ω)

接着,考虑对偶函数 ψ(ω),有:

ψ(ω)=xp~(x)logZω(x)+j=1mω(j)Ep~(fj)=xp~(x)logZω(x)+j=mnω(j)x,yp~(x,y)fj(x,y)=x,yp~(x,y)j=1mω(j)fj(x,y)xp~(x)logZω(x)

可以发现,最大熵模型 pω(y|x) 的对数似然函数与对偶函数 ψ(ω) 等价,即:

ψ(ω)=Lp~(pω)

因此,最大熵模型学习中的对偶函数 ψ(ω) 极大化等价于最大熵模型的极大似然估计,这样对最大熵模型的学习问题就转化成了具体求解对数似然函数极大化或求解对偶函数极大化的问题,即:

maxωxX,yYp~(x,y)j=1mω(j)fj(x,y)xXp~(x)logZω(x)
感谢您对我的支持,让我继续努力分享有用的技术与知识点!

Gitalking ...