最大熵原理：学习概率模型时，在所有可能的概率模型中，熵最大的模型是最好的模型。用最大熵原理推导实现的模型是最大熵模型。

1. 熵

1.1. 熵

假设离散型随机变量 $X$ 的样本空间 $\mathcal{X}=\{x_1,x_2,\dots ,x_n\}$，概率分布 $P(X=x_i)=p_i$，那么随机变量 $X$ 的熵为：

$$H(X)=-\sum _{i=1}^n{p}_i\log p_i$$

熵满足下列不等式：

$$0\le H(X)\le \log n$$

当且仅当 $X$ 服从均匀分布即 $p_1=p_2=\cdots =p_n=1/n$ 时，右侧等号成立，熵取得最大值 $\log n$.

1.2. 条件熵

假设离散型随机变量 $X,Y$ 的样本空间 $\mathcal{X}=\{x_1,x_2,\dots ,x_n\},\mathcal{Y}=\{y_1,y_2,\dots ,y_m\}$，那么在 $X$ 条件下，$Y$ 的条件熵为：

$$\begin{array}{rl}H(Y\mid X)& =\sum _{i=1}^{n}P(x_i)H(Y\mid X=x_i)\\ & =\sum _{i=1}^{n}P(x_i)(-\sum _{i=1}^{m}P(y_i\mid x_i)\log P(y_i\mid x_i))\\ & =-\sum _{x,y}P(x)P(y\mid x)\log P(y\mid x)\end{array}$$

2. 最大熵模型

2.1. 问题提出

对于训练数据集 $D=\{({\mathit{x}}_1,y_1),({\mathit{x}}_2,y_2),\dots ,({\mathit{x}}_n,y_n)\}$，其中 ${\mathit{x}}_i=(x_{i1},x_{i2},\dots ,x_{id}{)}^{\mathrm{T}}\in \mathcal{X}\subseteq {\mathbb{R}}^d,y_i\in \mathcal{Y}$.

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

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

我们知道对于二维离散随机变量的期望的表达式：

$$E=\sum _{x,y}p(x,y)f(x,y)$$

现在的问题就是如何得到 $p(x,y)$，一种方法是用经验分布来近似表示：

$$\hat{p}(x,y)=\frac{\mathrm{count}(x,y)}{n}$$

其中 $\mathrm{count}(x,y)$ 代表在训练数据集 $D$ 中 $(x,y)$ 出现的次数。

那么特征函数关于经验分布的期望值 $E_{\hat{p}}(f)$ 为：

$$E_{\hat{p}}(f)=\sum _{x,y}\hat{p}(x,y)f(x,y)$$

另一种方法是使用学习到的模型 $p(y\mid x)$ 来表示：

$$p(x,y)=p(x)p(y\mid x)$$

但是其中还是有未知的 $p(x)$，我们仍然用经验分布来近似表示：

$$\hat{p}(x)=\frac{\mathrm{count}(x)}{n}$$

那么特征函数关于模型和经验分布的期望值 $E_p(f)$ 为：

$$E_p(f)=\sum _{x,y}\hat{p}(x)p(y\mid x)f(x,y)$$

如果模型能够获取到训练数据中的信息，那么我们可以假设 $E_{\hat{p}}(f)$ 和 $E_p(f)$ 是相等的，即：

$$\sum _{x,y}\hat{p}(x,y)f(x,y)=\sum _{x,y}\hat{p}(x)p(y\mid x)f(x,y)$$

对于训练数据集 $D=\{({\mathit{x}}_1,y_1),({\mathit{x}}_2,y_2),\dots ,({\mathit{x}}_n,y_n)\}$，特征函数 $f_i(x,y),i=1,2,\dots ,n$，满足所有约束条件的模型集合为 $\mathcal{C}=\{P\in \mathcal{P}\mid E_p(f_i)=E_{\hat{p}}(f_i),i=1,2,\dots ,n\}$，那么最大熵模型的学习就是解决以下问题：

$$\begin{array}{rl}& \underset{P\in \mathcal{C}}{min}-H(P)=\sum _{x,y}\hat{P}(x)P(y\mid x)\log P(y\mid x)\\ & \begin{array}{rl}\mathrm{s}.\mathrm{t}.& E_p(f_i)-E_{\hat{p}}(f_i)=0,i=1,2,\dots ,n\\ & \sum _{y}P(y\mid x)=1\end{array}\end{array}$$

2.2. 问题求解

该问题为有约束的最优化问题，通过拉格朗日乘子法先转为无约束的最优化问题。引入拉格朗日乘子 $\mathit{\lambda }$ 写出拉格朗日函数：

$$L(P,\mathit{\lambda })=-H(P)+{\lambda }_0(1-\sum _{y}P(y\mid x))+\sum _{i=1}^n{\lambda }_i(E_p(f_i)-E_{\hat{p}}(f_i))$$

那么原始问题就转换成无约束的最优化问题：

$$\underset{P\in \mathcal{C}}{min}\underset{\mathit{\lambda }}{max}L(P,\mathit{\lambda })$$

转换为对偶问题：

$$\underset{\mathit{\lambda }}{max}\underset{P\in \mathcal{C}}{min}L(P,\mathit{\lambda })$$

首先求解内层问题，直接对 $P$ 求导并置为 $0$：

式中 $\log$ 的底数为 $\mathrm{e}$.

$$\begin{array}{rl}\frac{\partial L(P,\mathit{\lambda })}{\partial P(y\mid x)}& =\sum _{x,y}\hat{P}(x)(\log P(y\mid x)+1)-\sum _y{\lambda }_0-\sum _{i=1}^n{\lambda }_i\sum _{x,y}\hat{P}(x)f_i(x,y)\\ & =\sum _{x,y}\hat{P}(x)(\log P(y\mid x)+1)-\sum _y{\lambda }_0-\sum _{x,y}\hat{P}(x)\sum _{i=1}^n{\lambda }_i{f}_i(x,y)\\ & =\sum _{x,y}\hat{P}(x)(\log P(y\mid x)+1-{\lambda }_0-\sum _{i=1}^n{\lambda }_i{f}_i(x,y))=0\end{array}$$

$$\begin{array}{rl}& \log P(y\mid x)+1-{\lambda }_0-\sum _{i=1}^n{\lambda }_i{f}_i(x,y)=0\\ \Rightarrow & \log P(y\mid x)=-1+{\lambda }_0+\sum _{i=1}^n{\lambda }_i{f}_i(x,y)\\ \Rightarrow & P(y\mid x)=\exp (-1+{\lambda }_0+\sum _{i=1}^n{\lambda }_i{f}_i(x,y))\\ \Rightarrow & P(y\mid x)=\frac{{\displaystyle \exp (\sum _{i=1}^n{\lambda }_i{f}_i(x,y))}}{\exp (1-{\lambda }_0)}\end{array}$$

由 $\sum _{y}P(y\mid x)=1$ 可得：

$$\begin{array}{rl}\sum _{y}P(y\mid x)& =\sum _y\frac{{\displaystyle \exp (\sum _{i=1}^n{\lambda }_i{f}_i(x,y))}}{\exp (1-{\lambda }_0)}=\frac{{\displaystyle \sum _y\exp (\sum _{i=1}^n{\lambda }_i{f}_i(x,y))}}{\exp (1-{\lambda }_0)}=1\\ & \Rightarrow \exp (1-{\lambda }_0)=\sum _y\exp (\sum _{i=1}^n{\lambda }_i{f}_i(x,y))\end{array}$$

为了式子简洁，令 $Z_{\lambda }(x)=\sum _y\exp (\sum _{i=1}^n{\lambda }_i{f}_i(x,y))$，将其回代到 $P(y\mid x)$ 的表达式中得：

$$P(y\mid x)=\frac{1}{Z_{\lambda }(x)}\exp (\sum _{i=1}^n{\lambda }_i{f}_i(x,y))$$

这样内层问题便解决了，将解出来的 $P(y\mid x)$ 回代到 $L(P,\mathit{\lambda })$，记为 $\mathrm{\Psi }(\mathit{\lambda })$.

接下来就要求解外层问题：

$$\underset{\mathit{\lambda }}{max}\mathrm{\Psi }(\mathit{\lambda })$$

该问题解决的方法可以为改进的迭代尺度法 (Improved Iterative Scaling, IIS) 或者是拟牛顿法 (BFGS)，等我学到了这两个算法后再写笔记。