最大熵算法

1.最大熵原理（条件熵）

• 从符合条件的分布中选择熵最大的分布作为最优秀的分布
• 熵最大的预测出现的概率占绝对的优势
• 均匀分布熵最大

=>

• 当已知部分知识的前提下，对未知部分预测，最合理的推断应该是最符合自然状态的推断(熵最大)
• 概率平均分布=熵最大
• 在满足越是条件的模型中选择熵最大的模型

1.1 问题建模（最大熵是指条件熵）

• 问题转换：已知：$T=\{(x_1,y_1),...,(x_n,y_n)\}$ 学习的目标：用最大熵选择最好的分类模型

  结果： 对于给定的输入x,以条件概率P(Y|X)输出Y

• 一般模型

$\max\limits_{p\in P}H(Y|X)=-\sum\limits_{(x,y)}p(x,y)log p(y|x)$

P={p|p是X上满足条件的概率分布}

1.2 预定义

1.2.1 特征函数

• 对于某个特征(x,y)的样本

  1. y：这个特征中需要的确定信息
  2. x: 这个特征中的上下文信息

• 特征函数：$f(x,y)$ 表示输入x和输出y直接的事实：例如：对于特征$(x_0,y_0)$:

$\ \ f(x)= \begin{equation} \left\{ \begin{aligned} 1; \ \ \ x,y 满足某一个事实\\ 0；\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ \end{aligned} \right. \end{equation}$

=>上式是二值函数；x和y满足某个事实，则取值1；否则是0；

1.2.2 特征期望

• 特征函数关于经验分布$\overline{p}(x,y)$的期望,记$E_{\overline{p}}$：(样本下的期望)

$E_{\overline{p}}=\sum\limits_{(x_i,y_i)}\overline{p}(x,y)f(x,y)$

$\overline{p}(x,y)$是(x,y)在样本中的出现概率

• $\overline{p}(x)$：x出现的概率
• $\overline{p}(x,y)$：(x,y)在样本中出现的概率

1.2.3 条件

• 对于每一个特征(x,y);模型所建立的条件概率分布要与训练样本表现出来的分布相同

• 特征函数$f$在模型中的期望（理论模型）:特征函数在模型$P(Y|X)$和经验分布$\overline{p}(X)$的期望值

$E_(f)=\sum\limits_{x_i,y_i}p(x_i,y_i)f(x_i,y_i)$

$=\sum\limits_{(x_i,y_i)}p(y_i|x_i)p(x_i)f(x_i,y_i)$

$=\sum\limits_{(x_i,y_i)}\overline{p}(x_i)p(y_i|x_i)f(x_i,y_i)$

=>$p(y_i|x_i):未知$； =>$\overline{p}(x_i)$：已知

• 关于上式:理论模型应该与训练样本中的分不一致=>$p(X)=\overline{p}(X)$

2. 模型求解

2.1. 模型完整建立

• 若模型获取训练数据集中的信息，那么可以假设这两个期望相等

$E_p(f)=E_{\overline{p}}(f)$

<=>等价于

$\sum\limits_{x,y}\overline{p}(x)p(y|x)f(x,y)=\sum\limits_{x,y}\overline{p}(x,y)f(x,y )$

• 上式是约束条件，假设有$n个特征函数f_i(x,y)$，则有n个约束条件

$E_{\overline{p}}(f)=\sum\limits_{x,y} \overline{p}(x,y)f(x,y)$：观察分布上的期望

$E_(f)=\sum\limits_{x,y} \overline{p}(x)p(y|x)f(x,y)$：条件分布下的期望

2.2 学习模型

• 已知训练数据集合$T=\{(x_1,y_1),...,(x_n,y_n)\}$和特征函数$f_i(x,y),i=1,2,..,n$

• 条件熵的定义：

$H(y|x)=-\sum\limits_{(x,y)}p(y,x)logp(y|x)=\sum\limits_{x,y}\overline{p}(x)p(y|x)logp(y|x)$

• 模型目标：

$p^*(y|x)=arg\max\limits_{p(y|x)\in P} H(y|x)$

• 特征函数

$f_i(x,y)\in \{0,1\}$; $i=1,2,..,m$

• 约束条件:

$\sum\limits_{y\in Y}p(y|x)=1$

$E(f_i)=\overline{E}_(f_i)$; $\ \ \ i=1,2,..,m$

3. 求解

• 引入拉格朗日函数$L(P,w)$
• 因为$f(x,y)$是凸函数，将约束最优化的原问题转换为无约束优化的对偶问题，通过对偶问题求解原问题

$L(P,w)=-H(p)+\sum\limits_{i=1}^m\lambda_i(E(f_i)-\overline{E}(f_i))+\lambda_{m+1}(\sum\limits_{y\in Y}p(y|x)-1)$

=>推导参考李航P84

4 最大熵模型的最优解

• 因为maxent模型包含指数函数，所以不可能有解析解
• 构造目标函数求解

4.1 最大似然估计：MLE

• 带入最大似然函数=>对数似然函数

$L(w)=\sum\limits_{x,y}\overline{p}(x,y)\sum\limits_{i=1}^nw_if_i(x,y)-\sum\limits_x\overline{p}(x)logZ_w(x)$

其中：

$p^*(y|x)=\frac{1}{Z_{\lambda}(x)}e^{\sum_i\lambda_if_i(x,y)}$

$Z_w(x)=\sum\limits_yexp(\sum\limits_{i=1}^nw_if_i(x,y))$

• 目标是求对数似然函数的极大值$\hat{w}$

4.2 IIS法(improved iterative scaling)

• 工业界还是梯度下降算法

• Idea：

  1. 设最大熵模型当前的参数向量$\lambda$
  2. 希望找到新的参数向量$\lambda+\delta$,使得模型的对数似然函数L增加
  3. 重复，到找到最大值

4.3 推导

=>推导参考李航P90

5. 最大熵模型碎碎念

5.1 最大熵模型与logistic回归

• 最大熵模型和逻辑回归都是对数线性模型
• 都采用MLE，或者正则化的MLE
• 无约束优化问题：iis法，牛顿法，梯度下降法
• 最大熵模型和Softmax具有相同的目标函数
• 逻辑回归是两点分布的最大熵

=》

自然语言中，最大熵模型，是构造了特征函数，然后特征的发生和不发生就是一堆的伯努利事件，然后才和逻辑回归有了联系

5.2 熵的意义

• 熵是描述不确定性
• 知识是不确定性的补集（不确定性小，模型准确）

5.3 特征与熵

• 加入一个特征，熵少一点
• 特征越多，熵越小