机器学习中最大熵模型的介绍，包括模型思想、学习问题、学习算法等

最大熵原理

预备知识

离散型变量$X$的概率分布是$P(X)$。它的熵$H(X)orH(P)$越大，代表越均匀、越混乱、越不确定。各种熵点这里

$$H(P)=-\sum _{x\in X}P(x)\log P(x)$$

熵满足下面不等式

$$0\le H(P)\le \log |X|,\mathrm{其}\mathrm{中}|X|\mathrm{是}X\mathrm{的}\mathrm{取}\mathrm{值}\mathrm{个}\mathrm{数}$$

当前仅当$X$的分布是均匀分布的时候等号成立。当$X$服从均匀分布时，熵最大。

最大熵的思想

最大熵原理认为，学习概率模型时，在所有可能的概率模型中，熵最大的模型是最好的模型。

事情分为两个部分：确定的部分（约束条件）和不确定的部分。选择模型时要

• 要满足所有的约束条件，即满足已有的确定的事实
• 要均分不确定的部分

$X$有5个取值$\{A,B,C,D,E\}$，取值概率分别为$P(A),P(B),P(C),P(D),P(E)$。满足以下约束条件

$$P(A)+P(B)+P(C)+P(D)+P(E)=1$$

满足这个条件的模型有很多。再加一个约束条件

$$P(A)+P(B)=\frac{3}{10}$$

则，满足约束条件，不确定的平分（熵最大）：这样的模型是最好的模型

$$P(A)=P(B)=\frac{3}{20},P(C)=P(D)=P(E)=\frac{7}{30}$$

即：约束条件，熵最大

最大熵模型

假设分类模型是一个条件概率分布$P(Y\mid X)$。(有的不是选择条件模型，如论文里面)。训练数据集$N$个样本 $T=\{(x_1,y_1),(x_2,y_2),\cdots ,(x_N,y_N)\}$

基本概念

• 联合分布：$P(X,Y)$
• 边缘分布：$P(X)$
• 联合经验分布：$\tilde{P}(X,Y)=\frac{v(X=x,Y=y)}{N}$，其中$v(x,y)$为频数
• 联合边缘分布：$\tilde{P}(X)=\frac{v(X=x)}{N}$

特征函数$f(x,y)$用来描述$x$和$y$满足的一个事实约束条件：

$$f(x,y)=\{\begin{array}{ll}1,& x\mathrm{与}y\mathrm{满}\mathrm{足}\mathrm{一}\mathrm{个}\mathrm{事}\mathrm{实}，\mathrm{即}\mathrm{约}\mathrm{束}\mathrm{条}\mathrm{件}\\ 0,& \mathrm{否}\mathrm{则}\end{array}$$

如果有$n$个特征函数$f_i(x,y),i=1,2,\cdots ,n$, 就有$n$个约束条件。

概率期望的计算

$X$的期望

$X$ 是随机变量，概率分布是$P(X)$ ，或概率密度函数是$f(x)$

$$E(X)=\{\begin{array}{lll}& \sum _i{x}_{i}P(x_i),& \text{离散}\\ & {\int }_{-\mathrm{\infty }}^{+\mathrm{\infty }}x\cdot f(x)\mathrm{d}x,& \text{连续}\end{array}$$

下面只考虑离散型的期望，连续型同理，求积分即可。

一元函数的期望

$Y=g(X)$，期望是

$$E[Y]=E[g(X)]=\sum _i^{\mathrm{\infty }}g(x_i)\cdot P(x_i)$$

二元函数的期望

$Z=g(X,Y)$ ，期望是

$$E(Z)=\sum _{x,y}g(x,y)\cdot p(x,y)=\sum _{i=1}\sum _{j=1}g(x_i,y_j)p(x_i,y_j)$$

期望其实就是$E\mathrm{狗}=\sum \mathrm{狗}\cdot \mathrm{老}\mathrm{概}\mathrm{率}$ 。可离散，可连续。

约束条件等式

实际分布期望

特征函数$f(x,y)$关于经验分布$\tilde{P}(x,y)$的期望$E_{\tilde{P}}(f)$，即实际应该有的特征 ，也就是一个给模型加的约束条件 ：

$$E_{\tilde{P}}(f)=\sum _{x,y}\tilde{P}(x,y)f(x,y)$$

理论模型期望

特征函数$f(x,y)$ 关于模型$P(Y\mid X)$和经验分布$\tilde{P}(X)$的期望$E_P(f)$ ，即理论上模型学得后的期望：

$$E_P(f)=\sum _{x,y}\tilde{P}(x)P(y\mid x)f(x,y)$$

要从训练数据中获取信息，特征函数关于实际经验分布和理论模型的两个期望就得相等，即理论模型要满足实际约束条件

$$E_{\tilde{P}}(f)=E_P(f)$$

最大熵模型思想

条件概率分布$P(Y\mid X)$的条件熵为$H(P)$如下，条件熵：

$$H(P)=-\sum _{x,y}\tilde{P}(x)P(y\mid x)\log P(y\mid x)$$

则满足约束条件$E_{\tilde{P}}(f)=E_P(f)$的模型中，条件熵$H(P)$最大的模型就是最大熵模型。

最大熵模型的学习

学习问题

最大熵模型的学习等价于约束最优化问题，这类问题可以用拉格朗日对偶性去求解。

给定数据集$T=\{(x_1,y_1),(x_2,y_2),\cdots ,(x_N,y_N)\}$和特征函数$f_i(x,y),i=1,2,\cdots ,n$。

要满足2个约束条件

$$E_{\tilde{P}}(f)=E_P(f),\sum _{x,y}P(y\mid x)=1$$

要得到最大化熵

$$\underset{P\in C}{max}H(P)=-\sum _{x,y}\tilde{P}(x)P(y\mid x)\log P(y\mid x)$$

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

$$\underset{P\in C}{min}-H(P)=\sum _{x,y}\tilde{P}(x)P(y\mid x)\log P(y\mid x)$$

推导最大熵模型

一般使用拉格朗日对偶性去求解，可以见李航书附录。 引入拉格朗日乘子$w=(w_0,w_1,\cdots ,w_n)$，即参数向量，构造拉格朗日函数$L(P,w)$ ：

$$L(P,w)=-H(P)+w_0\cdot (1-\sum _{x,y}P(y\mid x))+\sum _{i=1}^n{w}_i\cdot (E_{\tilde{P}}(f)-E_P(f))$$

由于是凸函数，根据相关性质，所以原始问题和对偶问题同解，原始问题如下：

$$\underset{P\in C}{min}\underset{w}{max}L(P,w)$$

对应的对偶问题如下：

$$\underset{w}{max}\underset{P\in C}{min}L(P,w)$$

主要思路是：先固定$w$，去计算$\underset{P\in C}{min}L(P,w)$，即去找到一个合适的$P(Y\mid X)$。再去找到一个合适的$w$。

第一步：求解$P$ 。设对偶函数$\mathrm{\Psi }(w)$如下：

$$\mathrm{\Psi }(w)=\underset{P\in C}{min}L(P,w)=L(P_w,w)$$

对偶函数的解，即我们找到的$P(Y\mid X)$，记作$P_w$，如下：

$$P_w=\arg \underset{P\in C}{min}L(P,w)=P_w(y\mid x)$$

用$L(P,w)$对$P$进行求偏导，令偏导为0，可以解得$P_w$，即最大熵模型 如下：

$$P_w(y\mid x)=\frac{1}{Z_w(x)}\cdot \exp \left(\sum _{i=1}^n{w}_i{f}_i(x,y)\right),Z_w(x)=\sum _y\exp (\sum _{i=1}^n{w}_i{f}_i(x,y))$$

其中$Z_w(x)$是归一化因子，$f_i(x,y)$是特征函数，$w_i$是特征的权值，$P_w(y\mid x)$ 就是最大熵模型， $w$是最大熵模型中的参数向量。

第二步：求解$w$。即求$w$去最大化对偶函数，设解为$w^{\ast }$ 。可以使用最优化算法去求极大化。

$$w^{\ast }=\arg \underset{w}{max}\mathrm{\Psi }(w)$$

最终，求到的$P^{\ast }=P_{w^{\ast }}=P_{w^{\ast }}(y\mid x)$就是学习得到的最大熵模型。

最大熵模型

最大熵模型如下，其中$Z_w(x)$是归一化因子，$f_i(x,y)$是特征函数，$w_i$是特征的权值 。

$$P_w(y\mid x)=\frac{1}{Z_w(x)}\cdot \exp \left(\sum _{i=1}^n{w}_i{f}_i(x,y)\right),Z_w(x)=\sum _y\exp (\sum _{i=1}^n{w}_i{f}_i(x,y))$$

极大似然估计

其实对偶函数$\mathrm{\Psi }(w)$的极大化等价于最大熵模型的极大似然估计。

已知训练数据的经验分布$\tilde{P}(X,Y)$，条件概率分布的$P(Y\mid X)$的对数似然函数是：

$$\begin{array}{rl}{L}_{\tilde{P}}(P_w)& =\log \prod _{x,y}P(y\mid x{)}^{\tilde{P}(X,Y)}=\sum _{x,y}\tilde{P}(x,y)\log P(y\mid x)\\ & =\sum _{x,y}\tilde{P}(X,Y)\sum _{i=1}^n{w}_i{f}_i(x,y)-\sum _x\tilde{P}(X)\log Z_w(x)\end{array}$$

可以证明得到，$L_{\widetilde P}(P_w) = \Psi (w) $，极大似然函数等于对偶函数。

模型学习的最优化算法

逻辑回归、最大熵模型的学习都是以似然函数为目标函数的最优化问题，可以通过迭代算法求解。这个目标函数是个光滑的凸函数。通过很多方法都可以保证找到全局最优解，常用的有改进的迭代尺度法、梯度下降法、牛顿法或拟牛顿法，其中牛顿法和拟牛顿法一般收敛速度更快。

改进的迭代尺度法

改进的迭代尺度法(improved iterative scaling, IIS)是一种最大熵模型学习的最优化算法。

已知最大熵模型如下：

$$P_w(y\mid x)=\frac{1}{Z_w(x)}\cdot \exp \left(\sum _{i=1}^n{w}_i{f}_i(x,y)\right),Z_w(x)=\sum _y\exp (\sum _{i=1}^n{w}_i{f}_i(x,y))$$

对数似然函数如下：

$$L_{\tilde{P}}(P_w)=\sum _{x,y}\tilde{P}(X,Y)\sum _{i=1}^n{w}_i{f}_i(x,y)-\sum _x\tilde{P}(X)\log Z_w(x)$$

目标是：通过极大似然估计学习模型参数，即求对数似然函数的极大值$\hat{w}$。

基本思想

当前参数向量$w=(w_1,w_2,\cdots ,w_n{)}^T$，找到一个新的参数向量$w+\delta =(w_1+{\delta }_1,w_2+{\delta }_2,\cdots ,w_n+{\delta }_n)$，使得每次更新都使似然函数值增大。

由于$\delta$是一个向量，含有多个变量，不易同时优化。所以IIS 每次只优化其中一个变量${\delta }_i$，而固定其他变量${\delta }_j$。

设所有特征在$(x,y)$中的出现次数$f^{\mathrm{\#}}(x,y)=M$ ：

$$f^{\mathrm{\#}}(x,y)=\sum _i{f}_i(x,y)$$

计算每次的改变量：

$$L(w+\delta )-L(w)\ge B(\delta \mid w),\mathrm{改}\mathrm{变}\mathrm{量}\mathrm{的}\mathrm{下}\mathrm{界}\mathrm{限}$$

如果找到适当的$\delta$使得改变量的下界$B(\delta \mid w)$提高，则对数似然函数也能提高。

计算$B(\delta \mid w)$对${\delta }_i$求偏导，令偏导等于0，得如下方程：

$$\sum _{x,y}\tilde{P}(x)P_w(y\mid x)f_i(x,y)\exp ({\delta }_i{f}^{\mathrm{\#}}(x,y))=E_{\tilde{p}}(f_i),\mathrm{其}\mathrm{中}{E}_{\tilde{p}}(f_i)=\sum _{x,y}\tilde{P}(x,y)f_i(x,y)$$

然后，依次对${\delta }_i$求解该方程，就可以求得$\delta$，也就能够更新$w$，即$w\to w+\delta$

算法步骤

输入：特征函数$f_1,\cdots ,f_n$；经验分布$\tilde{P}(x,y)$，模型$P_w(y\mid x)$

输出：最优参数值$w_i^{\ast }$；最优模型$P_{w^{\ast }}$

(1) 初始化参数，取初值 $w_i=0$

(2) 求解方程 ${\delta }_i$

$$\sum _{x,y}\tilde{P}(x)P_w(y\mid x)f_i(x,y)\exp ({\delta }_i{f}^{\mathrm{\#}}(x,y))=E_{\tilde{p}}(f_i),$$

(3) 更新参数 $w_i+{\delta }_i\to w_i$

其中解方程的时候，如果特征出现次数$f^{\mathrm{\#}}(x,y)$ 是常数$M$，则可以直接计算${\delta }_i$ ：

$${\delta }_i=\frac{1}{M}\log \frac{E_{\tilde{p}}(f_i)}{E_p(f_i)}$$

如果$f^{\mathrm{\#}}(x,y)$不是常数，则必须通过数值计算${\delta }_i$。最简单就是通过牛顿迭代法去迭代求解${\delta }_i^{\ast }$。以$g({\delta }_i)=0$ 表示该方程，进行如下迭代：

$${\delta }_i^{(k+1)}={\delta }_i^{(k)}-\frac{g({\delta }_i^{(k)})}{g^{\prime }({\delta }_i^{(k)})}$$