极大似然估计与最大熵

极大似然估计 (Maximum Likelihood Estimation, MLE)

1. MLE 的核心思想

直观理解： 假设我们有一个数据集，这些数据是根据某个未知的概率分布生成的。极大似然估计的目标就是找到一组模型参数，使得我们观测到的这个数据集出现的概率最大。 换句话说，就是让我们的模型“最可能”生成出我们手上已有的数据。

• 例子： 假设你有一个硬币，你不知道它是公平的还是不公平的。你抛了10次，结果是8次正面，2次反面。
  • 如果你假设硬币是公平的（正面概率0.5），那么出现8正2反的概率是 $C_{10}^8\times (0.5{)}^8\times (0.5{)}^2=0.0439$。
  • 如果你假设硬币正面概率是0.8，那么出现8正2反的概率是 $C_{10}^8\times (0.8{)}^8\times (0.2{)}^2=0.3020$。 显然，在 $P(\text{正面})=0.8$ 的假设下，你观测到的数据出现的可能性更大。因此，0.8就是这个例子中通过极大似然估计得到的参数（正面概率）的最佳估计值。

作用： MLE 是参数估计的一种常用方法，广泛应用于各种统计模型和机器学习模型中。对于最大熵模型，它被用来估计模型中的权重参数 $\omega =({\omega }_1,\dots ,{\omega }_n)$。

2. 最大熵模型的条件概率分布与归一化因子

在最大熵模型的部分推导，我们已经推导出了最大熵模型的条件概率分布形式，它由参数 $\omega$ 决定：

$P_{\omega }(y|x)=\frac{1}{Z_{\omega }(x)}\exp \left({\sum }_{i=1}^n{\omega }_i{f}_i(x,y)\right)$

其中，$Z_{\omega }(x)$ 是归一化因子（也称配分函数），确保对于每一个 $x$，所有可能的 $y$ 的概率之和为1：

$Z_{\omega }(x)={\sum }_y\exp \left({\sum }_{i=1}^n{\omega }_i{f}_i(x,y)\right)$

3. 构建最大熵模型的似然函数

假设我们有一个训练数据集 $D=\{(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N)\}$，其中 $N$ 是样本总数。 我们希望找到参数 $\omega$，使得这些样本出现的概率最大。由于每个样本的出现是独立的，整个数据集出现的概率（即似然函数）是每个样本概率的乘积：

$L(\omega )={\prod }_{k=1}^N{P}_{\omega }(y_k|x_k)$

为什么使用对数似然函数？

在实际计算中，我们通常最大化对数似然函数 (Log-Likelihood Function)，而不是直接最大化似然函数。原因有几点：

1. 连乘变连加： 概率值通常很小，多个小概率值相乘容易导致下溢（Underflow），即结果接近于零，超出计算机浮点数表示范围。取对数可以将乘积转换为求和，避免下溢。
2. 不改变最大值点： 对数函数是一个单调递增函数，因此对数似然函数和似然函数在相同的参数 $\omega$ 处取得最大值。最大化对数似然函数与最大化似然函数是等价的。
3. 简化求导： 连加形式比连乘形式更容易求导，便于优化算法的实现。

所以，我们定义对数似然函数 $L_{log}(\omega )$: $L_{log}(\omega )=\log L(\omega )=\log \left({\prod }_{k=1}^N{P}_{\omega }(y_k|x_k)\right)$ 根据对数运算的性质 $\log (AB)=\log A+\log B$ 和 $\log (A^B)=B\log A$： $L_{log}(\omega )={\sum }_{k=1}^N\log P_{\omega }(y_k|x_k)$

4. 对数似然函数与经验分布的联系

现在，我们来分析如何将这个求和形式的对数似然函数，转化为与经验联合分布 $\tilde{P}(x,y)$ 相关的形式。

我们知道，在训练数据集中，一对 $(x,y)$ 可能出现多次。假设 $(x,y)$ 对在数据集中出现了 $m_{(x,y)}$ 次。那么，总样本数 $N$ 与经验联合分布 $\tilde{P}(x,y)$ 的关系是： $m_{(x,y)}=N\cdot \tilde{P}(x,y)$ 其中，$\tilde{P}(x,y)$ 是 $(x,y)$ 在训练数据中出现的频率。

所以，我们可以将上述求和 ${\sum }_{k=1}^N\log P_{\omega }(y_k|x_k)$ 按照 $(x,y)$ 对进行分组：

$L_{log}(\omega )={\sum }_{x,y}{m}_{(x,y)}\log P_{\omega }(y|x)$ （这里的 ${\sum }_{x,y}$ 是对所有在数据集中出现过的 $(x,y)$ 对求和）

将 $m_{(x,y)}=N\cdot \tilde{P}(x,y)$ 代入：

$L_{log}(\omega )={\sum }_{x,y}N\tilde{P}(x,y)\log P_{\omega }(y|x)$ $L_{log}(\omega )=N{\sum }_{x,y}\tilde{P}(x,y)\log P_{\omega }(y|x)$

$L_{\tilde{P}}(P_{\omega })=\log {\prod }_{x,y}{P}_{\omega }(y|x{)}^{\tilde{P}(x,y)}$

对于上面这个表达式可以这样理解：它不是整个数据集的对数似然，而是单位样本的平均对数似然，或者说是关于经验分布的对数似然。

让我们来验证这个转换： $L_{\tilde{P}}(P_{\omega })=\log \left({\prod }_{x,y}{P}_{\omega }(y|x{)}^{\tilde{P}(x,y)}\right)$ 根据对数性质 $\log (\prod A^B)=\sum B\log A$: $L_{\tilde{P}}(P_{\omega })={\sum }_{x,y}\tilde{P}(x,y)\log P_{\omega }(y|x)$

这与我们推导出的 $L_{log}(\omega )$ 只差一个常数因子 $N$。 $L_{log}(\omega )=N\cdot L_{\tilde{P}}(P_{\omega })$

由于 $N$ 是一个正的常数，最大化 $L_{log}(\omega )$ 与最大化 $L_{\tilde{P}}(P_{\omega })$ 是完全等价的，它们会在相同的 $\omega$ 处取得最大值。因此，在实际优化时，我们通常使用后者，因为它更简洁，并且可以视为期望对数似然。

总的来说，从 $N$ 个样本的对数似然到平均对数似然的转换有如下过程：

$\log {\prod }_{x,y}{P}_{\omega }(y|x{)}^{N\tilde{P}(x,y)}$ $=N\log {\prod }_{x,y}{P}_{\omega }(y|x{)}^{\tilde{P}(x,y)}$ （利用对数性质 $\log (A^B)=B\log A$，将 $N$ 提到 $\log$ 外面） $=N{\sum }_{x,y}\tilde{P}(x,y)\log P_{\omega }(y|x)$ （利用对数性质 $\log (\prod A^B)=\sum B\log A$，将连乘转换为连加）

这正是我们最终用于优化的对数似然函数（或者其 $1/N$ 倍）。

5. 最大熵模型与极大似然估计的等价性

现在，我们将最大熵模型的目标（最大化熵）与 MLE 联系起来。

回顾我们之前推导的，最大熵模型的对偶问题是： ${\max }_{\omega }g(\omega )={\max }_{\omega }{\min }_{P}L(P,\omega )$

其中，$L(P,\omega )$ 是拉格朗日函数： $L(P,\omega )={\sum }_{x,y}\tilde{P}(x)P(y|x)\log P(y|x)+{\sum }_x{\lambda }_x\left({\sum }_{y}P(y|x)-1\right)+{\sum }_{i=1}^n{\omega }_i\left({\sum }_{x,y}\tilde{P}(x,y)f_i(x,y)-{\sum }_{x,y}\tilde{P}(x)P(y|x)f_i(x,y)\right)$

当我们将 KKT 条件得到的 $P_{\omega }(y|x)$ 表达式代回 $L(P,\omega )$ 中，并进行一系列化简后，可以证明：

$g(\omega )={\sum }_{x,y}\tilde{P}(x,y)\log P_{\omega }(y|x)-{\sum }_{x,y}\tilde{P}(x,y)\log \tilde{P}(x,y)$ (这只是一个简化的形式，实际推导略复杂，但结论是关键)

会发现，第一项 ${\sum }_{x,y}\tilde{P}(x,y)\log P_{\omega }(y|x)$ 正是我们推导出的平均对数似然函数 $L_{\tilde{P}}(P_{\omega })$！ 第二项 ${\sum }_{x,y}\tilde{P}(x,y)\log \tilde{P}(x,y)$ 实际上是经验分布的熵的负值（一个常数，因为它不依赖于 $\omega$）。

所以，最大化 $g(\omega )$ 就等价于最大化平均对数似然函数 $L_{\tilde{P}}(P_{\omega })$。

核心结论： 求解最大熵模型的过程，等价于在满足所有约束的前提下，找到使得训练数据对数似然函数最大的模型参数 $\omega$。 因此，最大熵模型的学习问题，可以转化为一个无约束的优化问题：最大化对数似然函数 $L(\omega )$。

${\max }_{\omega }{L}_{log}(\omega )={\max }_{\omega }{\sum }_{x,y}\tilde{P}(x,y)\log P_{\omega }(y|x)$

这个目标函数是关于 $\omega$ 的凸函数，因此可以使用梯度下降、牛顿法、拟牛顿法（如L-BFGS）等优化算法来求解。其中，IIS (Iterative Scaling) 和 GIS (Generalized Iterative Scaling) 是早期专门用于最大熵模型参数估计的算法，现在更常用的是 L-BFGS 等通用优化器。

对偶函数 $\Psi (\omega )$ 的推导

我们从最大熵模型的拉格朗日函数 $L(P,\omega )$ 开始。

拉格朗日函数：

$L(P,\omega )={\sum }_{x,y}\tilde{P}(x)P(y|x)\log P(y|x)\text{（负熵项）}$ $+{\omega }_0\left(1-{\sum }_{y}P(y|x)\right)\text{（归一化约束项）}$ $+{\sum }_{i=1}^n{\omega }_i\left({\sum }_{x,y}\tilde{P}(x,y)f_i(x,y)-{\sum }_{x,y}\tilde{P}(x)P(y|x)f_i(x,y)\right)\text{（特征期望约束项）}$

我们的目标是计算对偶函数 $\Psi (\omega )={\min }_{P}L(P,\omega )$。这意味着我们需要将 $L(P,\omega )$ 对 $P(y|x)$ 求偏导并置为0，然后将得到的 $P(y|x)$ 的形式代回 $L(P,\omega )$。

第一步：代入 $P_{\omega }(y|x)$ 的指数形式

我们之前通过 KKT 条件已经求得了使 $L(P,\omega )$ 最小化的 $P(y|x)$ 的形式（这里我们用 $P_{\omega }(y|x)$ 来强调它是依赖于 $\omega$ 的）：

$P_{\omega }(y|x)=\frac{1}{Z_{\omega }(x)}\exp \left({\sum }_{i=1}^n{\omega }_i{f}_i(x,y)\right)$

其中 $Z_{\omega }(x)={\sum }_y\exp \left({\sum }_{i=1}^n{\omega }_i{f}_i(x,y)\right)$。

现在，我们把这个 $P_{\omega }(y|x)$ 代入到 $L(P,\omega )$ 的每个部分。

1. 负熵项代入： ${\sum }_{x,y}\tilde{P}(x)P_{\omega }(y|x)\log P_{\omega }(y|x)$

将 $P_{\omega }(y|x)$ 的表达式代入 $\log P_{\omega }(y|x)$： $\log P_{\omega }(y|x)=\log \left(\frac{1}{Z_{\omega }(x)}\exp \left({\sum }_{i=1}^n{\omega }_i{f}_i(x,y)\right)\right)$ $=\log \exp \left({\sum }_{i=1}^n{\omega }_i{f}_i(x,y)\right)-\log Z_{\omega }(x)$ $={\sum }_{i=1}^n{\omega }_i{f}_i(x,y)-\log Z_{\omega }(x)$

所以，负熵项变为： ${\sum }_{x,y}\tilde{P}(x)P_{\omega }(y|x)\left[{\sum }_{i=1}^n{\omega }_i{f}_i(x,y)-\log Z_{\omega }(x)\right]$

2. 归一化约束项代入： ${\omega }_0\left(1-{\sum }_y{P}_{\omega }(y|x)\right)$

因为 $P_{\omega }(y|x)$ 是一个合法的概率分布，它必然满足归一化条件：${\sum }_y{P}_{\omega }(y|x)=1$。 所以，这一项在 $P_{\omega }(y|x)$ 处的值是 ${\omega }_0(1-1)={\omega }_0\cdot 0=0$。

3. 特征期望约束项代入： ${\sum }_{i=1}^n{\omega }_i\left({\sum }_{x,y}\tilde{P}(x,y)f_i(x,y)-{\sum }_{x,y}\tilde{P}(x)P_{\omega }(y|x)f_i(x,y)\right)$

我们知道，KKT 条件要求模型计算的特征期望与经验特征期望相等。这意味着在最优解 $P_{\omega }(y|x)$ 处，这一项的值也应该为 0。 即：${\sum }_{x,y}\tilde{P}(x)P_{\omega }(y|x)f_i(x,y)={\sum }_{x,y}\tilde{P}(x,y)f_i(x,y)$。 所以，整个特征期望约束项在 $P_{\omega }(y|x)$ 处的值也是 ${\sum }_{i=1}^n{\omega }_i(0)=0$。

4. 结合所有项得到对偶函数 $\Psi (\omega )$

将所有项代入拉格朗日函数，并展开：

$\Psi (\omega )={\sum }_{x,y}\tilde{P}(x)P_{\omega }(y|x)\left[{\sum }_{i=1}^n{\omega }_i{f}_i(x,y)-\log Z_{\omega }(x)\right]+0+0$ $\Psi (\omega )={\sum }_{x,y}\tilde{P}(x)P_{\omega }(y|x){\sum }_{i=1}^n{\omega }_i{f}_i(x,y)-{\sum }_{x,y}\tilde{P}(x)P_{\omega }(y|x)\log Z_{\omega }(x)$

让我们进一步简化这两项：

第一部分： ${\sum }_{x,y}\tilde{P}(x)P_{\omega }(y|x){\sum }_{i=1}^n{\omega }_i{f}_i(x,y)$

回想 KKT 条件的推导，$\tilde{P}(x)(\log P(y|x)+1)-{\omega }_0-{\sum }_{i=1}^n{\omega }_i\tilde{P}(x)f_i(x,y)=0$。 从中我们可以得到： ${\sum }_{i=1}^n{\omega }_i\tilde{P}(x)f_i(x,y)=\tilde{P}(x)(\log P_{\omega }(y|x)+1)-{\omega }_0$

让我们直接从对偶函数的推导来看。 这一部分可以改写为： ${\sum }_{i=1}^n{\omega }_i{\sum }_{x,y}\tilde{P}(x)P_{\omega }(y|x)f_i(x,y)$ 根据 KKT 条件，在最优解 $P_{\omega }(y|x)$ 处，${\sum }_{x,y}\tilde{P}(x)P_{\omega }(y|x)f_i(x,y)={\sum }_{x,y}\tilde{P}(x,y)f_i(x,y)$。 所以，这一部分等于： ${\sum }_{i=1}^n{\omega }_i{\sum }_{x,y}\tilde{P}(x,y)f_i(x,y)$

第二部分： $-{\sum }_{x,y}\tilde{P}(x)P_{\omega }(y|x)\log Z_{\omega }(x)$

注意 $\log Z_{\omega }(x)$ 只依赖于 $x$，不依赖于 $y$。我们可以将它提到对 $y$ 求和的外面： $-{\sum }_x\tilde{P}(x)\log Z_{\omega }(x){\sum }_y{P}_{\omega }(y|x)$ 由于 ${\sum }_y{P}_{\omega }(y|x)=1$ (归一化条件)，这一项简化为： $-{\sum }_x\tilde{P}(x)\log Z_{\omega }(x)$

因此，对偶函数 $\Psi (\omega )$ 的最终形式是：

$\Psi (\omega )={\sum }_{i=1}^n{\omega }_i{\sum }_{x,y}\tilde{P}(x,y)f_i(x,y)-{\sum }_x\tilde{P}(x)\log Z_{\omega }(x)$

让我们一步步来验证： $\Psi (\omega )={\min }_{P}L(P,\omega )$ $L(P,\omega )={\sum }_{x,y}\tilde{P}(x)P(y|x)\log P(y|x)+{\omega }_0(1-{\sum }_{y}P(y|x))+{\sum }_{i=1}^n{\omega }_i({\sum }_{x,y}\tilde{P}(x,y)f_i(x,y)-{\sum }_{x,y}\tilde{P}(x)P(y|x)f_i(x,y))$

将 $P_{\omega }(y|x)$ 的形式代入： $P_{\omega }(y|x)=\frac{\exp (\sum {\omega }_i{f}_i(x,y))}{Z_{\omega }(x)}$ $\log P_{\omega }(y|x)=\sum {\omega }_i{f}_i(x,y)-\log Z_{\omega }(x)$

代入负熵项： ${\sum }_{x,y}\tilde{P}(x)P_{\omega }(y|x)({\sum }_{i=1}^n{\omega }_i{f}_i(x,y)-\log Z_{\omega }(x))$ $={\sum }_{x,y}\tilde{P}(x)P_{\omega }(y|x){\sum }_{i=1}^n{\omega }_i{f}_i(x,y)-{\sum }_{x,y}\tilde{P}(x)P_{\omega }(y|x)\log Z_{\omega }(x)$ $={\sum }_{i=1}^n{\omega }_i{\sum }_{x,y}\tilde{P}(x)P_{\omega }(y|x)f_i(x,y)-{\sum }_x\tilde{P}(x)\log Z_{\omega }(x){\sum }_y{P}_{\omega }(y|x)$ $={\sum }_{i=1}^n{\omega }_i{\sum }_{x,y}\tilde{P}(x)P_{\omega }(y|x)f_i(x,y)-{\sum }_x\tilde{P}(x)\log Z_{\omega }(x)$ (利用 ${\sum }_y{P}_{\omega }(y|x)=1$)

代入归一化约束项（此项为0）： ${\omega }_0(1-{\sum }_y{P}_{\omega }(y|x))=0$

代入特征期望约束项： ${\sum }_{i=1}^n{\omega }_i({\sum }_{x,y}\tilde{P}(x,y)f_i(x,y)-{\sum }_{x,y}\tilde{P}(x)P_{\omega }(y|x)f_i(x,y))$

将这三部分相加，得到 $\Psi (\omega )$： $\Psi (\omega )=\left[{\sum }_{i=1}^n{\omega }_i{\sum }_{x,y}\tilde{P}(x)P_{\omega }(y|x)f_i(x,y)-{\sum }_x\tilde{P}(x)\log Z_{\omega }(x)\right]$ $+0$ $+\left[{\sum }_{i=1}^n{\omega }_i{\sum }_{x,y}\tilde{P}(x,y)f_i(x,y)-{\sum }_{i=1}^n{\omega }_i{\sum }_{x,y}\tilde{P}(x)P_{\omega }(y|x)f_i(x,y)\right]$

注意，第一部分和第三部分中都含有 ${\sum }_{i=1}^n{\omega }_i{\sum }_{x,y}\tilde{P}(x)P_{\omega }(y|x)f_i(x,y)$ 项，它们符号相反，因此相互抵消！

最终只剩下： $\Psi (\omega )={\sum }_{i=1}^n{\omega }_i{\sum }_{x,y}\tilde{P}(x,y)f_i(x,y)-{\sum }_x\tilde{P}(x)\log Z_{\omega }(x)$

这正是我们前面推导的对偶函数 $\Psi (\omega )$ 的形式！

对偶函数与极大似然函数的关系

现在，让我们再次回顾我们此前推导的平均对数似然函数：

$L_{\tilde{P}}(P_{\omega })={\sum }_{x,y}\tilde{P}(x,y)\log P_{\omega }(y|x)$

将 $P_{\omega }(y|x)=\frac{\exp (\sum {\omega }_i{f}_i(x,y))}{Z_{\omega }(x)}$ 代入： $L_{\tilde{P}}(P_{\omega })={\sum }_{x,y}\tilde{P}(x,y)\left[{\sum }_{i=1}^n{\omega }_i{f}_i(x,y)-\log Z_{\omega }(x)\right]$ $L_{\tilde{P}}(P_{\omega })={\sum }_{x,y}\tilde{P}(x,y){\sum }_{i=1}^n{\omega }_i{f}_i(x,y)-{\sum }_{x,y}\tilde{P}(x,y)\log Z_{\omega }(x)$

注意第二个求和项： ${\sum }_{x,y}\tilde{P}(x,y)\log Z_{\omega }(x)$ 由于 $\tilde{P}(x,y)=\tilde{P}(x)\tilde{P}(y|x)$，且 $\log Z_{\omega }(x)$ 不依赖于 $y$： $={\sum }_x{\sum }_y\tilde{P}(x)\tilde{P}(y|x)\log Z_{\omega }(x)$ $={\sum }_x\tilde{P}(x)\log Z_{\omega }(x){\sum }_y\tilde{P}(y|x)$ 由于 ${\sum }_y\tilde{P}(y|x)=1$ (经验条件概率的归一化)，所以： $={\sum }_x\tilde{P}(x)\log Z_{\omega }(x)$

将此代回 $L_{\tilde{P}}(P_{\omega })$： $L_{\tilde{P}}(P_{\omega })={\sum }_{x,y}\tilde{P}(x,y){\sum }_{i=1}^n{\omega }_i{f}_i(x,y)-{\sum }_x\tilde{P}(x)\log Z_{\omega }(x)$

对比：

$\Psi (\omega )={\sum }_{i=1}^n{\omega }_i{\sum }_{x,y}\tilde{P}(x,y)f_i(x,y)-{\sum }_x\tilde{P}(x)\log Z_{\omega }(x)$ $L_{\tilde{P}}(P_{\omega })={\sum }_{x,y}\tilde{P}(x,y){\sum }_{i=1}^n{\omega }_i{f}_i(x,y)-{\sum }_x\tilde{P}(x)\log Z_{\omega }(x)$

会发现，它们是完全相同的！

因此，通过求解最大熵模型的对偶问题（最大化对偶函数 $\Psi (\omega )$），就等价于最大化训练数据的对数似然函数 $L_{\tilde{P}}(P_{\omega })$。

这个等价性是最大熵模型理论的基石，它使得我们能够将一个带复杂约束（熵最大化和特征期望匹配）的原始优化问题，转化为一个无约束的、更容易求解的凸优化问题（最大化对数似然）。

总结：

1. 对偶函数 $\Psi (\omega )$ 的构建： 首先对拉格朗日函数 $L(P,\omega )$ 中的 $P(y|x)$ 求偏导并令为零，得到 $P_{\omega }(y|x)$ 的指数形式。然后将这个 $P_{\omega }(y|x)$ 代回到 $L(P,\omega )$ 中，并利用 KKT 条件中隐藏的等式（例如归一化和特征期望匹配）来简化表达式。
2. 各项的抵消与简化： 在代入 $P_{\omega }(y|x)$ 之后，拉格朗日函数中的一些项会相互抵消（例如特征期望约束项与负熵项中一部分），最终留下一个简洁的对偶函数形式。
3. 与对数似然的等价： 最终的对偶函数 $\Psi (\omega )$ 与平均对数似然函数 $L_{\tilde{P}}(P_{\omega })$ 表达式完全一致，从而证明了最大熵模型的学习问题可以通过最大化对数似然函数来解决。