美文网首页
Max Entropy Model

Max Entropy Model

作者: BigPeter | 来源:发表于2018-12-13 21:36 被阅读0次

概述


最大熵模型是根据最大熵原理推导出的分类模型,属于对数线性模型。模型学习过程使用拉格朗日对偶法。

特征函数


特征函数f(x,y)描述输入x和输出y之间的某一个事实,定义为

\begin{equation}f(x,y)=\left\{\begin{aligned}1 &,\  x,y满足事实t,\\0 &,\ 否则 \end{aligned}\right.\end{equation}

在NLP中,t可能是:输入x是地点名词,y为命名实体;输入x包含暴力词汇,y为消极评论...

最大熵原理


熵:信息论中的一个概念,表示随机变量包含的平均信息量的多少。离散随机变量X的熵为

H(X)=-\sum_{x}p(x)log(p(x))

,把上式中的求和改为积分就是连续随机变量的熵公式。

熵满足0\leq H(x) \leq |X|,当且仅当X的分布是均匀分布时右边取等号。

最大熵原理:在满足约束条件的的所有模型中,熵最大的模型是最好的模型。也就是说,在模型满足已知的事实条件下,模型对未知部分的判断应该是“等可能的”,模型在约束条件内对未知部分没有做额外的假设。最大熵原理通过熵[可优化的数值化目标]的最大化来描述等可能[不容易操作]这一目标。

example:

1.给定随机变量X,X={A,B,C,D},求X的概率分布。

在没有其他信息(约束条件)的情况下,假设X是均匀分布是最有益的。等可能代表了对事实的无知,因为没有更多地信息,这种判断是合理的。所以P(A)=P(B)=P(C)=P(D)=\frac{1}{4}

2.给定随机变量X,X={A,B,C,D},根据先验知识已经知道P(A)+P(B)=\frac{1}{3},求X得概率分布。

未知部分的事件是等可能的。

P(A)+P(B)=\frac{1}{3} \\
P(C)+P(D)=\frac{2}{3}\\
P(A)=P(B)=\frac{1}{6}\\
P(C)=P(D)=\frac{1}{3}

最大熵模型


将最大熵原理应用到分类问题中得到的模型就是最大熵模型。

给定数据集T=\{(x_1, y_1),(x_2, y_2),\ldots,(x_n, y_n)\},我们希望通过最大熵原理来求得模型P(Y|X).

首先我们可以得到数据集的经验边缘分布\hat P(X)和经验联合分布\hat P(X,Y):

\hat P(X=x_i)=\frac{count(X=x_i)}{\sum_{x_j \in X}count(X=x_j)}=\frac{count(X=x_i)}{n} \\\hat P(X=x_i, Y=y_i)=\frac{count(X=x_i, Y=y_i)}{\sum_{x_j \in X}\sum_{y_j \in Y}count(X=x_j,Y=y_j)}=\frac{count(X=x_i, Y=y_i)}{n}

我们提前定义了k个特征函数,特征函数f_i(x,y)关于经验联合分布\hat P(X,Y)的期望为:

E_{\hat P}(f_i)=E_{\hat P(X,Y)}[f_i(x,y)]=\sum_{x,y}\hat P(x,y)f_i(x,y)

特征函数f_i(x,y)关于模型P(Y|X)和经验边缘分布\hat {P}(x)的期望为:

E_{P}(f_i)=E_{P(X),P(Y|X)}[f_i(x,y)]=\sum_{x,y}\hat P(x)P(y|x)f_i(x,y)

我们希望模型能够捕获数据集中的信息,即

E_{\hat P}(f_i)=E_{P}(f_i)

该条件就是模型的约束条件:通过模型得到的数据集中关于某事实出现的期望与数据集中统计出的期望相等。

我们有k个这样的约束条件。

在模型满足这些已知的约束条件后,我们就可以将最大熵原理应用到模型上。定义在模型(条件概率分布P(Y|X))上的条件熵为

\begin{aligned}H(P)=H(Y|X)&=\sum_{x}\hat P(X=x)H(Y|X=x)\\&=-\sum_{x}\hat P(X=x)\sum_{y}P(Y=y|X=x)logP(Y=y|X=x)\\&=-\sum_{x,y}\hat P(x)P(y|x)logP(y|x)\end{aligned}

因此,我们可以定义最大熵模型:

假设满足所有约束条件的模型集合为

C\equiv \{P \in \Psi |E_{\hat P}(f_i)=E_{P}(f_i),\ for \ i=1,2,\ldots, k\}

定义在条件概率分布P(Y|X)上的条件熵为

H(P)=-\sum_{x,y}\hat P(x)P(y|x)logP(y|x)

则模型集合C中条件熵H(P)最大的模型称为最大熵模型。

模型学习


给定数据集T=\{(x_1, y_1),(x_2, y_2),\ldots,(x_n, y_n)\},特征函数f_i(x,y),\ i=1,2,\ldots,k,最大熵模型的学习归结为约束最优化问题

\max_{P}H(P)=-\sum_{x,y}\hat P(x)P(y|x)logP(y|x) \\s.t.E_{\hat P}(f_i)=E_{P}(f_i), \ for \ i=1,2,\ldots,k \\\sum_{y}P(y|x)=1

按照最优化问题的习惯,将最大化问题转化为最小化问题

\min_{P}-H(P)=\sum_{x,y}\hat P(x)P(y|x)logP(y|x) \\s.t.E_{\hat P}(f_i)-E_{P}(f_i)=0, \ for \ i=1,2,\ldots,k \\1-\sum_{y}P(y|x)=0

通过拉格朗日对偶法来解决该最优化问题。

\begin{align*}Lagrange(P,\alpha,\beta)&=\sum_{x,y}\hat P(x)P(y|x)logP(y|x)+\sum_{i=1}^k\alpha_i(E_{\hat P}(f_i)-E_{P}(f_i))+\beta(1-\sum_{y}P(y|x)) \\&=\sum_{x,y}\hat P(x)P(y|x)logP(y|x)+\sum_{i=1}^k\alpha_i(\sum_{x,y}\hat P(x,y)f_i(x,y)-\sum_{x,y}\hat P(x)P(y|x)f_i(x,y))+\beta(1-\sum_{y}P(y|x))\end{align*}

最优化的原始问题为

\min_{P}\max_{\alpha,\beta}Lagrange(P,\alpha,\beta)

对偶问题为

\max_{\alpha,\beta}\min_{P}Lagrange(P,\alpha,\beta)

Lagrange function是P的凸函数(H(P)是P的凸函数),所以原始问题的解和对偶问题的解是等价的。首先解内层的最小化问题,(Lagrange(P,\alpha,\beta)是P的一个泛函,应该用泛函的知识求导),对P(y|x)求偏导,有

\begin{align*}\frac{dLagrange(P,\alpha,\beta)}{dP(y|x)}&=\hat P(x)[P(y|x)\frac{1}{P(y|x)}+\log P(y|x)]-\sum_{i=1}^k\alpha_i\hat P(x)f_i(x,y)-\beta \\&=\hat P(x)(1+\log P(y|x))-\hat P(x)\sum_{i=1}^k\alpha_if_i(x,y)-\beta \\&=\hat P(x)(\log P(y|x)+1-\sum_{i=1}^k\alpha_if_i(x,y)-\frac{\beta}{\hat P(x)}) \\&=0\end{align*}

得到

P(y|x)=exp(\sum_{i=1}^k\alpha_if_i(x,y)+\frac{\beta}{\hat P(x)}-1)=\frac{exp(\sum_{i=1}^k\alpha_if_i(x,y))}{exp(1-\frac{\beta}{\hat P(x)})}

由于\sum_{y}P(y|x)=1,有

P_{\alpha,\beta}(y|x)=\frac{1}{Z_{\alpha,\beta}(x)}exp(\sum_{i=1}^k\alpha_if_i(x,y)),

其中

Z_{\alpha,\beta}(x)=\sum_{y}exp(\sum_{i=1}^k\alpha_if_i(x,y))

称为规范化因子。

求解外部的最大化问题

【待】

极大似然估计


【待】

相关文章

网友评论

      本文标题:Max Entropy Model

      本文链接:https://www.haomeiwen.com/subject/fuhbhqtx.html