最大熵模型的求解

在 上一节 中，我们知道对偶函数的极大化与最大熵模型的极大似然估计是等价的，因此，我们可以通过求解最大熵模型的极大似然估计问题来求解对偶函数的极大化问题，进而求解原始优化问题，这也是本节介绍的改进的迭代尺度法的思路。而拟牛顿法可通过直接求解的方式得到最优化的最大熵模型。

改进的迭代尺度法

在 上一节 中我们得到的最大熵模型的对数似然函数为：

$$\mathcal{L}(w)=\Sigma_{x,y}\widetilde{P}(x,y)\Sigma_{i=1}^nw_if_i(x, y)-\Sigma_x\widetilde{P}(x)logZ_w(x)$$

其中，$Z_w(x)=\Sigma_yexp(\Sigma_{i=1}^nw_if_i(x, y))$。

为解决上述对数似然函数极大化的问题，一种显而易见的方法是，令 $\nabla_w\mathcal{L}(w)=0$。但是，考虑到 $Z_w(x)$ 中的指数项 $exp(\Sigma_1^nw_if_i(x, y))$，含有 $n$ 个变量（$w_1, w_2, …, w_n$）的指数和的形式不易同时优化。因此，提出了这里所述的改进的迭代尺度法（IIS）的思想。

设最大熵模型的参数 $w$ 的当前值为 $w=(w_1, w_2, …, w_n)$，给予其一个增量 $\delta$，得新的模型参数 $w+\delta=(w_1+\delta_1, w_2+\delta_2, …, w_n+\delta_n)$，这种参数更新过程使得对数似然函数不断增大，最终达到一个极大值，以此完成对最大熵模型的对数似然函数的极大化过程。这就是改进的迭代尺度法的基本思想。

考虑:

$$\mathcal{L}(w+\delta)-\mathcal{L}(w)=\Sigma_{x,y}\widetilde{P}(x, y)\Sigma_{i=1}^n\delta_if_i(x, y)-\Sigma_x\widetilde{P}(x)log\frac{Z_{w+\delta}(x)}{Z_w(x)}$$

根据不等式：$-log\alpha \geq 1-\alpha\;(\alpha > 0)$，有：

$$\mathcal{L}(w+\delta)-\mathcal{L}(w) \geq \Sigma_{x,y}\widetilde{P}(x, y)\Sigma_{i=1}^n\delta_if_i(x, y)+\Sigma_x\widetilde{P}(x)(1-\frac{Z_{w+\delta}(x)}{Z_w(x)})\\
=\Sigma_{x,y}\widetilde{P}(x, y)\Sigma_{i=1}^n\delta_if_i(x, y)+1-\Sigma_x\widetilde{P}(x)\frac{Z_{w+\delta}(x)}{Z_w(x)}$$

而：

$$\frac{Z_{w+\delta}(x)}{Z_w(x)}=\frac{\Sigma_yexp[\Sigma_{i=1}^nw_if_i(x, y)+\Sigma_{i=1}^n\delta_if_i(x,y)]}{\Sigma_yexp(\Sigma_{i=1}^nw_if_i(x, y))}\\
=\frac{\Sigma_y[exp(\Sigma_{i=1}^nw_if_i(x, y)) \cdot exp(\Sigma_{i=1}^n\delta_if_i(x, y))]}{\Sigma_yexp(\Sigma_{i=1}^nw_if_i(x, y))}\\
=\Sigma_yP_w(y|x) \cdot exp(\Sigma_{i=1}^n\delta_if_i(x, y))$$

故：

$$\mathcal{L}(w+\delta)-\mathcal{L}(w) \geq \Sigma_{x,y}\widetilde{P}(x, y)\Sigma_{i=1}^n\delta_if_i(x, y)+1-\Sigma_x\widetilde{P}(x)\Sigma_yP_w(y|x)exp(\Sigma_{i=1}^n\delta_if_i(x, y))$$

记：

$$A(\delta|w)=\Sigma_{x,y}\widetilde{P}(x, y)\Sigma_{i=1}^n\delta_if_i(x, y)+1-\Sigma_x\widetilde{P}(x)\Sigma_yP_w(y|x)exp(\Sigma_{i=1}^n\delta_if_i(x, y))$$

$A(\delta|w)$ 为当参数变量取得一个增量时，对数似然函数变化量的一个下界。当该下界增大时，对数似然函数也会随之增大，当该下界取得极大值时，此对数似然函数的变化量也会取得一个较为理想的值，从而达到不断增大最大熵模型的对数似然函数的目的。然而，同上文所述，$A(\delta|w)$ 是一个同时含 $n$ 个变量（$\delta_1, \delta_2, …, \delta_n$）指数和的形式，这 $n$ 个变量不易同时进行优化，故而 $A(\delta|w)$ 的形式还需进行变换，最好变换为方便我们对其中一个分量 $\delta_i$ 进行优化而其他分量 $\delta_j\;(i \neq j)$ 保持不变的形式。在这里，我们根据 Jensen 不等式进行变换。

Jensen 不等式的定义    设函数 $\varphi$ 为凸函数，参数 $\alpha_i$ 为权重参数，且 $\Sigma_i\alpha_i=1$，则有：$\varphi(\Sigma_i\alpha_ix_i) \leq \Sigma_i(\alpha_i \varphi(x_i))$。

为使 $A(\delta|w)$ 满足应用以上 Jensen 不等式的条件，我们引入 $f^*(x, y)=\Sigma_if_i(x, y)$，则有：$\Sigma_{i=1}^n\frac{f_i(x, y)}{f^*(x, y)}=1$，式 $\frac{f_i(x, y)}{f^*(x, y)}$ 相当于 Jensen 不等式中的权重参数 $\alpha_i$。实际上，由于 $f_i(x, y)$ 是一个二值函数，故而 $f^*(x, y)$ 可理解为 $x$ 与 $y$ 所满足的特征约束条件的总个数。综上，我们可将下界 $A(\delta|w)$ 变换为如下形式：

$$A(\delta|w)=\Sigma_{x,y}\widetilde{P}(x, y)\Sigma_{i=1}^n\delta_if_i(x, y)+1-\Sigma_x\widetilde{P}(x)\Sigma_yP_w(y|x)exp(\Sigma_{i=1}^n\frac{f_i(x, y)}{f^*(x, y)}f^*(x, y)\delta_i)\\
\geq \Sigma_{x,y}\widetilde{P}(x, y)\Sigma_{i=1}^n\delta_if_i(x, y)+1-\Sigma_x\widetilde{P}(x)\Sigma_yP_w(y|x)\Sigma_{i=1}^n[\frac{f_i(x, y)}{f^*(x, y)}exp(f^*(x, y)\delta_i)]$$

若令 $B(\delta|w)=\Sigma_{x,y}\widetilde{P}(x, y)\Sigma_{i=1}^n\delta_if_i(x, y)+1-\Sigma_x\widetilde{P}(x)\Sigma_yP_w(y|x)\Sigma_{i=1}^n[\frac{f_i(x, y)}{f^*(x, y)}exp(f^*(x, y)\delta_i)]$，则有 $\mathcal{L}(w+\delta)-\mathcal{L}(w) \geq B(\delta|w)$。

此时的 $B(\delta|w)$ 成了满足我们条件的易于优化的形式，针对 $B(\delta|w)$，我们对其中的一个 $\delta_i$ 求偏导并令其为 $0$（这是 $B(\delta|w)$ 取得极大值的必要条件），得：

$$\frac{\partial B(\delta|w)}{\partial \delta_i}=\Sigma_{x,y}\widetilde{P}(x, y)f_i(x, y)-\Sigma_x\widetilde{P}(x)\Sigma_yP_w(y|x)f_i(x, y)exp(f^*(x, y)\delta_i)=0$$

即有：

$$\Sigma_{x,y}\widetilde{P}(x)P_w(y|x)f_i(x, y)exp(f^*(x, y)\delta_i)=\mathbb{E}_{\widetilde{P}}(f_i(x, y))$$

根据上式求解每一个 $\delta_i\;(i=1, 2, …, n)$，然后将 $w+\delta$ 设为新的 $w$，重复以上过程，直至 $\mathcal{L}(w)$ 收敛，此时最大熵模型的对数似然函数将不再增大，由于此前对数似然函数 $\mathcal{L}(w)$ 一直处于爬升状态，因此收敛时必有 $\delta=0$，将 $\delta=0$ 代入 $B(\delta|w)$ 中可知此式亦为 $0$，因此 $B(\delta|w)$ 与 $\mathcal{L}(w)$ 收敛条件是一致的，当 $\delta=0$ 时，参数 $w$ 将不再变化，$w$ 收敛。

综上，我们可得改进的迭代尺度法如下：

输入：特征约束条件 $f_1(x, y), f_2(x, y), …, f_n(x, y)$，经验分布 $\widetilde{P}(x, y)$，模型 $P_w(y|x)$
输出：最优参数 $w^*$，最优模型 $P_{w^*}(y|x)$
(1) 置初始值 $w_i=0\;(i=1, 2, …, n)$；
(2) 按 $i=1, 2, …, n$ 根据以下方程：

$$\Sigma_{x,y}\widetilde{P}(x)P_w(y|x)f_i(x, y)exp(f^*(x, y)\delta_i)=\mathbb{E}_{\widetilde{P}}(f_i(x, y))$$

分别求解 $\delta_i$，将 $w_i+\delta_i$ 作为新的 $w_i$；
(3) 若 $w_i$ 不收敛，则返回步骤（2），否则，令此时 $w$ 为最优值 $w^*$，代入 $P_w(y|x)$ 得最优模型 $P_{w^*}(y|x)$。

以上算法的关键是步骤（2）中求解方程的过程，若 $f^*(x, y)$ 是一个恒定的常数，即它与任何具体的 $x, y$ 无关，设此时 $f^*(x, y)=M$，则：

$$\delta_i=\frac{1}{M}log\frac{\mathbb{E}_{\widetilde{P}}(f_i(x, y))}{\mathbb{E}_P(f_i(x, y))}$$

但是若 $f^*(x, y)$ 不是一个恒定的常数，（2）中方程的求解就需要用到 牛顿法，设 $g(\delta_i)=\Sigma_{x,y}\widetilde{P}(x)P_w(y|x)f_i(x, y)exp(f^*(x, y)\delta_i)-\mathbb{E}_{\widetilde{P}}(f_i(x, y))$，运用牛顿法可以通过迭代求出此函数的零点，即得（2）中方程的解，这里不再赘述了。

拟牛顿法

这里的拟牛顿法过程可参见 牛顿法与拟牛顿法，很简单，这里就不过多赘述了。