最大熵模型的部分推导

---

最大熵模型的核心思想是“在满足已知约束的前提下，选择不确定性（熵）最大的概率分布”。

1. 回顾最大熵模型的优化问题

首先，我们来正式定义最大熵模型要解决的优化问题。

目标函数：最大化条件熵

最大熵模型的目标是找到一个条件概率分布 $P(y|x)$，使得在给定观测 $x$ 的情况下，对 $y$ 的预测具有最大的不确定性（即熵最大）。数学上，我们希望最大化条件熵 $H(Y|X)$：

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

其中：

• $\tilde{P}(x)$ 是训练数据中观测到的边缘概率分布（经验分布），即某个 $x$ 出现的频率。
• $P(y|x)$ 是我们希望学习得到的模型概率分布。

约束条件：

为了使模型能够反映训练数据中的统计规律，我们需要引入约束条件。这些约束通常基于特征函数 $f_i(x,y)$。==一个特征函数 $f_i(x,y)$ 是一个二值函数（通常为0或1），表示当 $(x,y)$ 满足某个条件时取值为1，否则为0。==

1. 概率归一化约束： 对于每一个给定的 $x$，所有可能的 $y$ 的概率之和必须为1。 ${\sum }_{y}P(y|x)=1\text{对于所有 }x$

2. 特征期望匹配约束（重要！）： 模型计算出的特征的期望值，必须等于训练数据中该特征的经验期望值。 ${\sum }_{x,y}P(x,y)f_i(x,y)={\sum }_{x,y}\tilde{P}(x,y)f_i(x,y)\text{对于所有特征 }i=1,\dots ,n$ 这里 $P(x,y)=\tilde{P}(x)P(y|x)$ 是模型预测的联合概率分布。 所以，约束条件可以写为： ${\sum }_{x,y}\tilde{P}(x)P(y|x)f_i(x,y)={\sum }_{x,y}\tilde{P}(x,y)f_i(x,y)\text{对于所有 }i$

优化问题总结：

最大熵模型是一个带约束的优化问题：

${\max }_{P}H(Y|X)=-{\sum }_{x,y}\tilde{P}(x)P(y|x)\log P(y|x)$ $\text{s.t.}{\sum }_{y}P(y|x)=1,\forall x$ ${\sum }_{x,y}\tilde{P}(x)P(y|x)f_i(x,y)-{\sum }_{x,y}\tilde{P}(x,y)f_i(x,y)=0,\forall i$ $P(y|x)\ge 0$ (这个是隐式的，在后续推导中自然满足)

2. 拉格朗日函数 (Lagrangian Function)

为了解决带约束的优化问题，我们通常使用拉格朗日乘子法。其核心思想是将约束条件融入到目标函数中，形成一个新的无约束函数——拉格朗日函数。

由于最大熵是最大化问题，为了使用标准的拉格朗日对偶性（通常用于最小化问题），我们将其转化为最小化负熵的问题： ${\min }_P-H(Y|X)={\sum }_{x,y}\tilde{P}(x)P(y|x)\log P(y|x)$

现在，我们构建拉格朗日函数 $L(P,\lambda ,\omega )$。这里，我们将为每个约束条件引入一个拉格朗日乘子。

• 对于每个 $x$ 的归一化约束 ${\sum }_{y}P(y|x)=1$，我们引入一个乘子 ${\lambda }_x$。
• 对于每个特征 $f_i$ 的期望匹配约束，我们引入一个乘子 ${\omega }_i$。

拉格朗日函数为： $L(P,\mathbf{\lambda },\mathbf{\omega })={\sum }_{x,y}\tilde{P}(x)P(y|x)\log P(y|x)\text{(负熵项)}$ $+{\sum }_x{\lambda }_x\left({\sum }_{y}P(y|x)-1\right)\text{(归一化约束项)}$ $+{\sum }_{i=1}^n{\omega }_i\left({\sum }_{x,y}\tilde{P}(x)P(y|x)f_i(x,y)-{\sum }_{x,y}\tilde{P}(x,y)f_i(x,y)\right)\text{(特征期望约束项)}$

重要说明： 这与统计机器学习（B站简博士版）中拉格朗日函数的形式略有不同，它将归一化约束写作 ${\omega }_0(1-{\Sigma }_{y}P(y|x))$ 并且是全局的 ${\omega }_0$ 而非 ${\lambda }_x$。这是一种简化或特定推导场景下的表示。更严谨和普适的表示是每个 $x$ 对应一个 ${\lambda }_x$。

简博士讲解的版本中的 $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{（特征期望约束）}$

我们按照原视频中的公式进行推导，但会明确指出其中的简化或隐含假设。

3. 原始问题与对偶问题 (Primal Problem & Dual Problem)

• 原始问题 (Primal Problem)： 对于带约束的最小化问题，其等价的拉格朗日形式是： ${\min }_P{\max }_{\omega }L(P,\omega )$ 这里 $P$ 是我们要优化的概率分布，$\omega$ 是拉格朗日乘子的向量。在给定 $P$ 的情况下，如果 $P$ 不满足任何约束，那么 ${\max }_{\omega }L(P,\omega )$ 将会是 $+\infty$，如果 $P$ 满足所有约束，那么 ${\max }_{\omega }L(P,\omega )$ 等于原始目标函数的值。因此，原始问题是在所有满足约束的 $P$ 中找到使目标函数最小的 $P$。

• 对偶问题 (Dual Problem)： 对应于原始问题，我们可以构造其对偶问题： ${\max }_{\omega }{\min }_{P}L(P,\omega )$ 对偶问题是首先对 $P$ 最小化拉格朗日函数，得到一个只与 $\omega$ 相关的函数 $g(\omega )={\min }_{P}L(P,\omega )$，然后最大化这个 $g(\omega )$。

弱对偶性 (Weak Duality)： 总是成立，即对偶问题的最优值总是小于等于原始问题的最优值： ${\max }_{\omega }{\min }_{P}L(P,\omega )\le {\min }_P{\max }_{\omega }L(P,\omega )$

强对偶性 (Strong Duality)： 在特定条件下（例如，目标函数是凸函数，约束是仿射函数，并且满足Slater条件等），原始问题和对偶问题的最优值相等： ${\max }_{\omega }{\min }_{P}L(P,\omega )={\min }_P{\max }_{P}L(P,\omega )$ 对于最大熵模型，由于负熵函数是凸函数，并且约束条件都是线性的（仿射），因此强对偶性成立。这意味着我们可以通过求解对偶问题来找到原始问题的最优解，这通常更简单。

相关内容可以再看最大熵与拉格朗日算子求解。

4. 求解对偶问题：推导最大熵模型的指数形式

为了求解对偶问题 ${\max }_{\omega }{\min }_{P}L(P,\omega )$，我们首先需要找到 $P$ 使得 $L(P,\omega )$ 最小化（假定 $\omega$ 固定）。这通过对 $L(P,\omega )$ 求关于 $P(y|x)$ 的偏导数并令其为零来实现。

第一步：对 $P(y|x)$ 求偏导并置为0

我们对拉格朗日函数 $L(P,\omega )$ 中每一个 $P(y|x)$ 求偏导。请注意，这里的求导是针对特定的 $(x,y)$ 对。

$L(P,\omega )={\sum }_{x^{\prime },y^{\prime }}\tilde{P}(x^{\prime })P(y^{\prime }|x^{\prime })\log P(y^{\prime }|x^{\prime })\text{（负熵）}$ $+{\omega }_0\left(1-{\sum }_{y^{\prime }}P(y^{\prime }|x^{\prime })\right)\text{（归一化约束，这里假定 }{x}^{\prime }\text{是与 }x\text{相同的）}$ $+{\sum }_{i=1}^n{\omega }_i\left({\sum }_{x^{\prime },y^{\prime }}\tilde{P}(x^{\prime },y^{\prime })f_i(x^{\prime },y^{\prime })-{\sum }_{x^{\prime },y^{\prime }}\tilde{P}(x^{\prime })P(y^{\prime }|x^{\prime })f_i(x^{\prime },y^{\prime })\right)\text{（特征期望约束）}$

让我们对 $P(y|x)$ (即某个特定的 $x,y$ 值) 求偏导：

1. 负熵项的偏导： $\frac{\partial }{\partial P(y|x)}\left(\tilde{P}(x)P(y|x)\log P(y|x)\right)$ 应用链式法则 $(uv{)}^{\prime }=u^{\prime }v+u{v}^{\prime }$，其中 $u=P(y|x)$, $v=\log P(y|x)$。 $u^{\prime }=1$ $v^{\prime }=\frac{1}{P(y|x)}$ 所以，$\frac{\partial }{\partial P(y|x)}(P(y|x)\log P(y|x))=1\cdot \log P(y|x)+P(y|x)\cdot \frac{1}{P(y|x)}=\log P(y|x)+1$ 因此，负熵项的偏导是： $\tilde{P}(x)(\log P(y|x)+1)$。

2. 归一化约束项的偏导： $\frac{\partial }{\partial P(y|x)}\left({\omega }_0\left(1-{\sum }_{y^{\prime }}P(y^{\prime }|x)\right)\right)$ 注意，只有当 $y^{\prime }=y$ 时，该项才与 $P(y|x)$ 相关。 其偏导为： $-{\omega }_0$

3. 特征期望约束项的偏导： $\frac{\partial }{\partial P(y|x)}\left({\sum }_{i=1}^n{\omega }_i\left({\sum }_{x^{\prime },y^{\prime }}\tilde{P}(x^{\prime },y^{\prime })f_i(x^{\prime },y^{\prime })-{\sum }_{x^{\prime },y^{\prime }}\tilde{P}(x^{\prime })P(y^{\prime }|x^{\prime })f_i(x^{\prime },y^{\prime })\right)\right)$ 其中，${\sum }_{x^{\prime },y^{\prime }}\tilde{P}(x^{\prime },y^{\prime })f_i(x^{\prime },y^{\prime })$ 是常数，其偏导为0。 我们只看第二部分： $\frac{\partial }{\partial P(y|x)}\left(-{\sum }_{i=1}^n{\omega }_i{\sum }_{x^{\prime },y^{\prime }}\tilde{P}(x^{\prime })P(y^{\prime }|x^{\prime })f_i(x^{\prime },y^{\prime })\right)$ 同样，只有当 $x^{\prime }=x$ 且 $y^{\prime }=y$ 时，被求和项才与 $P(y|x)$ 相关。 所以偏导为： $-{\sum }_{i=1}^n{\omega }_i\tilde{P}(x)f_i(x,y)$

将所有偏导置为零：

$\tilde{P}(x)(\log P(y|x)+1)-{\omega }_0-{\sum }_{i=1}^n{\omega }_i\tilde{P}(x)f_i(x,y)=0$

现在我们来解出 $P(y|x)$: $\tilde{P}(x)\log P(y|x)={\omega }_0+{\sum }_{i=1}^n{\omega }_i\tilde{P}(x)f_i(x,y)-\tilde{P}(x)$

假设 $\tilde{P}(x)>0$ (训练数据中 $x$ 至少出现过一次)： $\log P(y|x)=\frac{{\omega }_0}{\tilde{P}(x)}+{\sum }_{i=1}^n{\omega }_i{f}_i(x,y)-1$

取指数： $P(y|x)=\exp \left(\frac{{\omega }_0}{\tilde{P}(x)}+{\sum }_{i=1}^n{\omega }_i{f}_i(x,y)-1\right)$ $P(y|x)=\exp \left(\frac{{\omega }_0}{\tilde{P}(x)}-1\right)\cdot \exp \left({\sum }_{i=1}^n{\omega }_i{f}_i(x,y)\right)$

为了满足 ${\sum }_{y}P(y|x)=1$ 的归一化条件，我们引入一个归一化因子（也称为配分函数 Partition Function），记为 $Z_{\omega }(x)$。对于特定的 $x$ 和 $\omega$ 值，这个因子 $Z_{\omega }(x)$ 是一个常数。

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

我们将 $P(y|x)$ 代入到归一化条件，然后将 $Z_{\omega }(x)$ 替换掉 $P(y|x)$ 的部分，即可得到 $Z_{\omega }(x)$ 与 $\exp \left(\frac{{\omega }_0}{\tilde{P}(x)}-1\right)$ 的关系。

那么，最终 $P(y|x)$ 的形式为： $P(y|x)=\frac{1}{Z_{\omega }(x)}\exp \left({\sum }_{i=1}^n{\omega }_i{f}_i(x,y)\right)$

这个形式就是最大熵模型的指数形式，也是逻辑回归 (Logistic Regression) 的多分类形式（Softmax Regression）。这里， ${\omega }_i$ 就是模型需要学习的参数（权重）。

关于 ${\omega }_0$ 的解释： 在上述推导中， $\exp \left(\frac{{\omega }_0}{\tilde{P}(x)}-1\right)$ 被吸收进了 $1/Z_{\omega }(x)$ 中。这意味着 ${\omega }_0$ (或者更一般地，每个 $x$ 对应的 ${\lambda }_x$) 的作用就是确保 $P(y|x)$ 对于每个 $x$ 都能正确归一化。在实际计算中，我们通常直接使用归一化形式，不再显式地保留 ${\omega }_0$。

5. 对偶问题：找到最优的 $\omega$

现在我们有了 $P(y|x)$ 的表达式，它是关于 $\omega$ 的函数。我们将这个表达式代回拉格朗日函数 $L(P,\omega )$ 中，得到一个只关于 $\omega$ 的函数 $g(\omega )$。 $g(\omega )={\min }_{P}L(P,\omega )$

然后，我们需要最大化 $g(\omega )$，以找到最优的 $\omega$ 值。 ${\max }_{\omega }g(\omega )$

这个 $g(\omega )$ 函数通常被称为对偶函数。对于最大熵模型，最大化 $g(\omega )$ 等价于最大化对数似然函数 (log-likelihood)。因此，最大熵模型的训练过程通常就是通过迭代算法（如GIS、IIS、拟牛顿法、L-BFGS等）来最大化训练数据的对数似然函数，从而求解出最优的 $\omega$ 参数。

6. 关于原始问题与对偶问题

“Theorem (原始问题与对偶问题) 若函数 $f(x)$ 和 $c_i(x)$ 是凸函数，$h_j(x)$ 是仿射函数；并且假设不等式约束 $c_i(x)$ 是严格可行的，即存在 $x$，对所有的 $i$ 有 $c_i(x)<0$ (Slater’s Condition)。则存在 $x^{\ast }$，${\alpha }^{\ast }$，${\beta }^{\ast }$ 使 $x^{\ast }$ 是原始问题的解，${\alpha }^{\ast }$，${\beta }^{\ast }$ 是对偶问题的解，并且 $d^{\ast }=p^{\ast }=L(x^{\ast },{\alpha }^{\ast },{\beta }^{\ast })$。”

解释：

• $f(x)$： 对应我们这里的目标函数，即负熵 $-{\sum }_{x,y}\tilde{P}(x)P(y|x)\log P(y|x)$。这是一个凸函数。
• $c_i(x)$： 对应不等式约束。在最大熵模型中，我们主要是等式约束。一个等式约束 $h(x)=0$ 可以表示为两个不等式约束 $h(x)\le 0$ 和 $-h(x)\le 0$。这里的 $h_j(x)$ (仿射函数) 指的就是我们的等式约束，例如 ${\sum }_{y}P(y|x)-1=0$ 和 ${\sum }_{x,y}\tilde{P}(x)P(y|x)f_i(x,y)-{\sum }_{x,y}\tilde{P}(x,y)f_i(x,y)=0$。
• 仿射函数 (Affine Function)： 指的是线性的函数加上一个常数项。在最大熵模型中，我们的约束条件都是线性的，因此它们是仿射函数。
• Slater’s Condition (严格可行性条件)： 对于存在不等式约束的情况，如果存在一个点，使得所有不等式约束都严格成立（即不是等于0），那么强对偶性成立。对于只有等式约束的问题，只要目标函数是凸函数，约束是仿射的，并且问题有可行解，通常强对偶性也成立。最大熵模型满足这些条件。
• $x^{\ast }$，${\alpha }^{\ast }$，${\beta }^{\ast }$：
  • $x^{\ast }$ 代表原始问题的最优解（在这里是找到最优的概率分布 $P(y|x)$）。
  • ${\alpha }^{\ast }$，${\beta }^{\ast }$ 代表对偶问题的最优解（在这里是找到最优的拉格朗日乘子 $\omega$）。
• $d^{\ast }=p^{\ast }=L(x^{\ast },{\alpha }^{\ast },{\beta }^{\ast })$：
  • $p^{\ast }$ 是原始问题的最优值。
  • $d^{\ast }$ 是对偶问题的最优值。
  • 这个等式表明，在满足上述条件时，通过求解对偶问题得到的参数（$\omega$），代入原始的拉格朗日函数中，将得到与原始问题相同的最优解值。这从根本上解释了为什么我们可以通过求解对偶问题来训练最大熵模型。

---

总结一下所学到的：

1. 最大熵模型是一个凸优化问题，目标是最大化条件熵，并受限于概率归一化和特征期望匹配。
2. 我们使用拉格朗日乘子法将带约束的优化问题转化为无约束的拉格朗日函数。
3. 通过对拉格朗日函数求偏导并置零，我们得到了最大熵模型的指数形式：$P(y|x)=\frac{1}{Z_{\omega }(x)}\exp \left({\sum }_{i=1}^n{\omega }_i{f}_i(x,y)\right)$。
4. 由于最大熵问题满足强对偶性条件，我们可以通过求解其对偶问题来找到最优的参数 $\omega$。求解对偶问题通常等价于最大化训练数据的对数似然函数。