最大熵模型（一）

Maximum Entropy Theory Intro

最大熵原理：学习概率模型时，所有可能的概率模型（分布）中，熵最大的模型是最好的模型。通常用约束条件来确定概率模型的集合，所以最大熵原理也可以表述为在给定已知信息下，满足约束条件的模型集合中，选取熵最大的模型。

也就是说，在目前已观测到的所有信息下，最合理的对未知信息的预测就是对所有未知信息最不确定的推断（每种未知情况等可能）。$H(P)$表示$P$的不确定性，最不确定的情况=熵最大的情况=每种未知情况都等可能发生，这就给出了最好模型选择的准则

$$H(P)=-\sum_xP(x)\log P(x),其中0≤H(P)≤\log|X|$$

表示随机变量$X$的概率分布$P(X)$的熵，$|X|$表示$X$的取值个数。当且仅当$X$的分布是均匀分布时右边等号成立，这时候条件熵最大。即：在已知信息下，$P(X)$的熵最大

对于模型$P(X)$，能够最大化熵$H(P)$的模型$P(X)$即是最好的模型

Maximum Entropy Model

给定训练数据集:$T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$

我们要求最准确的模型：$P(y|x)$

$1^o$ 特征函数与经验分布

①特征函数(feature function)（$X$的约束）：

$f(x,y)$表示训练数据中输入$x$和输出$y$之间的一个事实（关系），只要满足事实（一般存在很多对满足该事实的$(x_i,y_i)$，特征函数也有很多$f_i$，即有多个事实约束），则$(x_i,y_i)$就能用该特征函数$f(x,y)$表示一组数据

$$f(x,y)= \begin{cases} 1,x与y满足某一事实\\ 0,否则 \end{cases}$$

此函数为一个二值函数，要么0要么1（也可以是任意实值函数）。事实可以来源于先验知识等。

举几例：①$f(x,y)= \begin{cases}1,x为抛硬币出现正面,y为\frac{1}{2}\\ 0,否则 \end{cases}$

②已知从箱子里顺序两次抽出红球和白球的概率为$\frac{3}{10}$：

$f(x_1,x_2,y)= \begin{cases}1,x_1=红且x_2=白,或x_1=白且x_2=红,y=\frac{3}{10}\\ 0,否则 \end{cases}$

③也可以想CRF中的特征函数的意义，是一样的

注：输入$x$可以是很多个随机变量，所以实际应该表示为$f(\vec x,y)$或写成$f(x_1,x_2,\cdots,x_n,y)$，为了方便写，全都记成$f(x,y)$，同时一个模型中的特征函数也是可以有很多的，每个特征函数都表述了一组数据。

理解特征函数的意义：一是泛化表示，一个特征函数可以表示多组数据，相当于“从输入和输出中抽取了特征”，其实就是用来形式化表示X的相关知识信息。（比如从箱子里顺序两次抽出红球和白球的概率为$\frac{3}{10}$，就可以用特征函数来形式化的表示它）

二是放入公式中这样也相当于给数据添加了一个约束条件，即是在Maximum Entropy Theory Intro部分所述的约束条件，其也可以相当于是一个已知的前提信息，先验知识。（比如从箱子里顺序两次抽出红球和白球的概率为$\frac{3}{10}$就是一个先验知识，这就是个模型约束条件）

这里的特征feature，和机器学习中的特征feature不是一个概念

②经验分布即已知训练集的分布（$X$的分布）：

$$\hat P(X=x,Y=y)=\frac{||(X=x,Y=y)||_0}{N}$$ $$\hat P(X=x)=\frac{||(X=x,Y)||_0}{N}$$

其中$||||_0$表该数据样本出现的次数。

为什么要有经验分布？经验分布即训练集现在已知的分布，是在Maximum Entropy Theory Intro部分所述的已知部分前提信息。其中包含了已知信息$x,y$出现的概率，根据最大熵原理，这是我们应该作为已知事实考虑的。

那么如何将经验分布考虑进最大熵？只需要求概率分布期望的时候是对经验分布求期望即可，$x,y$的经验分布就相当于$x,y$的权重，见$2^o$。

③特征函数与经验分布一起构成了已知信息

所谓最大化条件熵，其中的“条件”就是指的这已知信息，包含$X$的分布和约束

$2^o$ 分布的期望

回顾理解复合函数期望（见后记）

特征函数$f(x,y)$(表征了已知$X$的约束）关于经验分布$\hat P(X,Y)$（表征了已知$X$的分布）的期望值构成已知信息，也即经验分布中样本满足某个特征函数$f(x,y)$的期望：

$$\mathbb E_{\hat P}(f)=\sum_{x,y}\hat P(x,y)f(x,y)$$

关键：根据最大熵原理，我们观察到的已知信息已经成为事实，在真实分布也应该符合在经验分布中的已知信息。换句话说——这个已知信息的期望无论在经验分布中还是真实分布中都应该是同样的。

通过贝叶斯公式展开构造出$P(y|x)$，正好是我们要求的模型。这就形成了一个对我们要求的模型$P(y|x)$的约束条件。只有符合这个条件，才能是我们想要的模型。

即：

$$\mathbb E_{P}(f)=\mathbb E_{\hat P}(f)$$ $$或,\sum_{x,y}\hat P(x)P(y|x)f(x,y)=\sum_{x,y}\hat P(x,y)f(x,y)$$

$3^o$最大熵模型

在$2^o$中根据已知信息得到了模型的约束条件，于是我们就可以得到满足这样的约束条件的模型集合。

$Def.$ 最大熵模型 Maximum Entropy Model：假设满足所有约束条件的模型集合为

$$\mathbb C=\{P∈\mathbb P|E_P(f_i)=E_{\hat P}(f_i),i=1,2,\cdots,n \}$$

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

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

则模型集合$\mathbb C$中条件熵$H(P)$最大的模型称为最大熵模型。式中的对数为自然对数。

最大熵模型的学习

满足这样的模型有很多，哪个才是最好的？在Maximum Entropy Theory Intro部分已述，熵最大的时候最好。

最大熵模型的学习过程就是求解最大熵模型的过程，也就是在满足约束条件的模型中求取最大熵模型的过程

所以，

对于给定的训练数据集$T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$以及特征函数$f_i(x,y),i=1,2,\cdots,n$，最大熵模型的学习等价于约束最优化问题：

$$\max_{P∈\mathbb C}H(P)=-\sum_{x,y}\hat P(x)P(y|x)\log P(y|x)$$ $$使得,\mathbb E_{P}(f_i)=\mathbb E_{\hat P}(f_i),i=1,2,\cdots,n$$ $$\sum_yP(y|x)=1$$

按照优化问题的习惯，将其改写为等价的求最小值问题：

$$\min_{P∈\mathbb C}-H(P)=\sum_{x,y}\hat P(x)P(y|x)\log P(y|x)$$ $$使得,\mathbb E_{P}(f_i)-\mathbb E_{\hat P}(f_i)=0,i=1,2,\cdots,n$$ $$\sum_yP(y|x)=1$$

求得上述问题的解即是MEM学习的解