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

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\leq H(X)\leq \log n $$

当且仅当 $X$ 服从均匀分布即 $p_1=p_2=\dots=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{align} H(Y\mid X)&=\sum_{i=1}^{n}P(x_i)H(Y\mid X=x_i)\\ &=\sum_{i=1}^{n}P(x_i)\left(-\sum_{i=1}^mP(y_i\mid x_i)\log P(y_i\mid x_i)\right)\\ &=-\sum_{x,y}P(x)P(y\mid x)\log P(y\mid x) \end{align} $$

2. 最大熵模型

2.1. 问题提出

对于训练数据集 $D=\{(\boldsymbol{x}_1,y_1),(\boldsymbol{x}_2,y_2),\dots,(\boldsymbol{x}_n,y_n)\}$，其中 $\boldsymbol{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{cases} 1,&x\,与\,y\,满足某一事实\\ 0,&否则 \end{cases} $$

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

$$ 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=\{(\boldsymbol{x}_1,y_1),(\boldsymbol{x}_2,y_2),\dots,(\boldsymbol{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{align} &\min_{P\in\mathcal{C}}-H(P)=\sum_{x,y}\hat{P}(x)P(y\mid x)\log P(y\mid x)\\ &\begin{aligned} \mathrm{s.t.}\;&E_p(f_i)-E_{\hat{p}}(f_i)=0,i=1,2,\dots,n\\ &\sum_yP(y\mid x)=1 \end{aligned} \end{align} $$

2.2. 问题求解

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

$$ L(P,\boldsymbol{\lambda})=-H(P)+\lambda_0\left(1-\sum_yP(y\mid x)\right)+\sum_{i=1}^n\lambda_i(E_p(f_i)-E_{\hat{p}}(f_i)) $$

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

$$ \min_{P\in\mathcal{C}}\max_{\boldsymbol{\lambda}}L(P,\boldsymbol{\lambda}) $$

转换为对偶问题：

$$ \max_{\boldsymbol{\lambda}}\min_{P\in\mathcal{C}}L(P,\boldsymbol{\lambda}) $$

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

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

$$ \begin{align} \frac{\partial L(P,\boldsymbol{\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_if_i(x,y)\\ &=\sum_{x,y}\hat{P}(x)\left(\log P(y\mid x)+1-\lambda_0-\sum_{i=1}^n\lambda_if_i(x,y)\right)=0 \end{align} $$

$$ \begin{align} &\log P(y\mid x)+1-\lambda_0-\sum_{i=1}^n\lambda_if_i(x,y)=0\\ \Rightarrow\;&\log P(y\mid x)=-1+\lambda_0+\sum_{i=1}^n\lambda_if_i(x,y)\\ \Rightarrow\;&P(y\mid x)=\exp\left(-1+\lambda_0+\sum_{i=1}^n\lambda_if_i(x,y)\right)\\ \Rightarrow\;&P(y\mid x)=\frac{\displaystyle\exp\left(\sum_{i=1}^n\lambda_if_i(x,y)\right)}{\exp(1-\lambda_0)} \end{align} $$

由 $\sum_yP(y\mid x)=1$ 可得：

$$ \sum_yP(y\mid x)=\sum_y\frac{\displaystyle\exp\left(\sum_{i=1}^n\lambda_if_i(x,y)\right)}{\exp(1-\lambda_0)}=\frac{\displaystyle\sum_y\exp\left(\sum_{i=1}^n\lambda_if_i(x,y)\right)}{\exp(1-\lambda_0)}=1\\ \Rightarrow\exp(1-\lambda_0)=\sum_y\exp\left(\sum_{i=1}^n\lambda_if_i(x,y)\right) $$

为了式子简洁，令 $Z_\lambda(x)=\sum_y\exp\left(\sum_{i=1}^n\lambda_if_i(x,y)\right)$，将其回代到 $P(y\mid x)$ 的表达式中得：

$$ P(y\mid x)=\frac{1}{Z_\lambda(x)}\exp\left(\sum_{i=1}^n\lambda_if_i(x,y)\right) $$

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

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

$$ \max_{\boldsymbol{\lambda}}\Psi(\boldsymbol{\lambda}) $$

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