最大熵模型

Logistic Regression

Logistic Distribution

设$X$是连续随机变量，$X$服从 logistic distribution 是指$X$具有下列分布函数和密度函数：

$$\begin{align} F(x) &= P(X \leq x) = \frac{1}{1 + e^{-(x-\mu)/\gamma}} \tag{1} \\ f(x) &= F'(x) = \frac{e^{-(x-\mu)/\gamma}}{\gamma\left(1 + e^{-(x-\mu)/\gamma}\right)^2} \tag{2} \end{align}$$

Binomial Logistic Regression Model

这是一种二分类模型，这里规定模型输出 $Y \in \{0, 1\}$， 也就是 $y_i \in \{0, 1\}$

$$\begin{align} P(Y = 0 | x) &= \frac{1}{1 + \exp (1 + \vec{w} \cdot \vec{x} + b)} \tag{3} \\ P(Y = 1 | x) &= \frac{\exp (\vec{w} \cdot \vec{x} + b)}{1 + \exp (1 + \vec{w} \cdot \vec{x} + b)} \tag{4} \end{align}$$

其中，$x \in \mathbb{R}^n$ 是输入，$w \in \mathbb{R}^n$ 和 $ b \in \mathbb{R}$ 分别是权值向量和偏置，$\vec{w} \cdot \vec{x}$ 是向量内积运算。

Evaluation of Model Parameters

采用极大似然估计法估计模型参数，从而得到 logistics regression model。

我们设

$$P(Y = 1 | x) = \pi(x) \tag{5}$$

则得到似然函数为

$$\prod_{i=1}^{N}[\pi(x_i)]^{y_i}[1 - \pi(x_i)]^{1 - y_i} \tag{6}$$

经过计算，对数似然函数为

$$L(w) = \sum_{i=1}^{N} [y_i(\vec{w} \cdot \vec{x_i}) - \ln (1 + \exp (\vec{w} \cdot \vec{x_i}))] \tag{7}$$

对 $L(w)$ 求极大值，得到 $w$ 的估计值 $\hat{w}$

---

Maximum Entropy Model

The Principle of Maximum Entropy

最大熵原理的核心在于，使得整个概率模型的熵最大。

MaxEntropy Model

模型输入 $X \in \mathcal{X} \subseteq \mathbb{R}^n$，输出 $Y \in \mathcal{Y}$，条件概率分布 $P(Y | X)$ 表示对于给定输入 $X$ 以该条件概率输出 $Y$。

给定训练数据集，可以确定联合分布 $P(X, Y)$ 的经验分布和边缘分布。

$$\begin{align} \tilde{P}(X = x, Y = y) &= \frac{\nu(X = x, Y = y)}{N} \tag{8} \\ \tilde{P}(X = x) &= \frac{\nu(X = x)}{N} \tag{9} \end{align}$$

其中 $\nu(X = x, Y = y)$ 是样本 $(x, y)$ 出现的频数。

接下来介绍特征函数 feature function $f(x,y)$，$f()$ 描述输入 $x$ 与输出 $y$ 之间的某一个事实。

$$f(x, y) = \begin{cases} 1, &\text{satisfying} \\ 0, &\text{otherwise} \tag{10} \end{cases}$$

特征函数关于经验分布的期望值

$$E_{\tilde{P}}(f) = \sum_{x,y} \tilde{P}(x,y) f(x,y) \tag{11}$$

特征函数关于模型与经验分布的期望值

$$E_P(f) = \sum_{x,y} \tilde{P}(x) P(y|x) f(x,y) \tag{12}$$

如果模型能够获得训练数据中的信息，则可以认为上述两个期望值相等，即

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

综上，我们引出最大熵模型。

假设满足所有约束条件的模型集合为

$$\mathcal{C} \equiv \{P \in \mathcal{P} \mid E_{\tilde{P}}(f_i) = E_P(f_i), \quad i=1,2,\dots,n\} \tag{14}$$

定义在条件概率分布 $P(Y|X)$ 上的条件熵为

$$H(P) = -\sum_{x,y} \tilde{P}(x) P(y|x) \ln P(y|x) \tag{15}$$

则模型集合 $\mathcal{C}$ 中条件熵 $H(P)$ 最大的模型称为最大熵模型。

Training a Maximum Entropy Model

类似 SVM 的学习过程。给定训练数据集 $T = \{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\}$ 以及特征函数 $f_i(x,y), \quad i = 1, 2, \dots, n$，最大熵模型的学习等价于约束最优化问题：

$$\begin{align*} \max_{P \in \mathcal{C}} \quad & H(P) = -\sum_{x, y} \tilde{P}(x) P(y \mid x) \ln P(y \mid x) \\ \text{subject to} \quad & E_{\tilde{P}}[f_i] = E_P[f_i], \quad i = 1, 2, \dots, n \\ & \sum_{y} P(y \mid x) = 1 \end{align*}$$

将其换为等价的最小化问题

$$\begin{align*} \min_{P \in \mathcal{C}} \quad -&H(P) = \sum_{x, y} \tilde{P}(x) P(y \mid x) \ln P(y \mid x) \tag{16} \\ \text{subject to} \quad & E_{\tilde{P}}[f_i] - E_P[f_i]= 0, \quad i = 1, 2, \dots, n \tag{17} \\ & \sum_{y} P(y \mid x) = 1 \tag{18} \end{align*}$$

将约束最优化问题转换为无约束最优化的对偶问题。引入拉格朗日乘子 $w_0, w_1, \dots, w_n$，定义拉格朗日函数 $L(P, w)$：

$$\begin{align*} L(P, w) &\equiv -H(P) + w_0 \left(1 - \sum_{y} P(y | x)\right) + \sum_{i = 1}^{n} w_i (E_{\tilde{P}}(f_i) - E_{P}(f_i)) \tag{19} \\ &= \sum_{x,y} \tilde{P}(x) P(y | x) \ln P(y | x) + w_0\left(1 - \sum_{y} P(y | x)\right) + \\ &\sum_{i = 1}^{n} w_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) \end{align*}$$

最优化的原始问题是

$$\min_{P \in \mathcal{C}} \max_{w} L(P, w) \tag{20}$$

对偶问题是

$$\max_{w} \min_{P \in \mathcal{C}} L(P, w) \tag{21}$$

先解决极小化问题， 记

$$\Psi(w) = \min_{P \in \mathcal{C}} L(P, w) = L(P_w, w) \tag{22}$$

求 $L(P, w)$ 对 $P(y | x)$ 的偏导数

$$\begin{align*} \frac{\partial L(P, w)}{\partial P(y | x)} &= \sum_{x, y} \tilde{P}(x)(\ln P(y | x) + 1) - \sum_{y}w_0 - \sum_{x, y} \left(\tilde{P}(x) \sum_{i = 1}^{n} w_i f_i(x, y) \right) \\ &= \sum_{x, y} \tilde{P} \left(\ln P(y | x) + 1 - w_0 - \sum_{i = 1}^{n} w_i f_i(x, y) \right) \end{align*}$$

令偏导数等于 $0$， 在 $\tilde{P} > 0$ 的情况下，解得

$$P_w(y | x) = \frac{1}{Z_w(x)} \exp \left(\sum_{i = 1}^{n} w_i f_i(x, y) \right) \tag{23}$$

其中

$$Z_w(x) = \sum_{y} \exp \left(\sum_{i = 1}^{n} w_i f_i(x, y) \right) \tag{24}$$

称 $Z_w(x)$ 为归一化因子。

最后求解对偶问题外部的极大化问题

$$\max_{w} \Psi(w) \tag{25}$$

Improved Iterative Scaling

已知最大熵模型

$$P_w(y | x) = \frac{1}{Z_w(x)} \exp \left(\sum_{i = 1}^{n} w_i f_i(x, y) \right)$$

其中

$$Z_w(x) = \sum_{y} \exp \left(\sum_{i = 1}^{n} w_i f_i(x, y) \right)$$

对数似然函数为

$$L(w) = \sum_{x, y} \tilde{P}(x, y) \sum_{i = 1}^{n} w_i f_i(x, y) - \sum_{x} \tilde{P}(x) \ln Z_w(x)$$

改进迭代算法的思路是，假设最大熵模型当前的参数向量是 $w = (w_1, w_2, \dots, w_n)^{T}$，我们希望找到一个新的参数向量 $w + \delta = (w_1 + \delta_1, \dots, w_n + \delta_n)^{T}$，使得模型的对数似然函数增值。

算法步骤

输入：特征函数 $f_1, f_2, \dots, f_n$；经验分布 $\tilde{P}(X, Y)$；模型 $P_w(y | x)$

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

步骤1：对所有 $i \in \{1, 2, \dots, n\}$，取初值 $w_i = 0$。

步骤2：对每一 $i \in \{1, 2, \dots, n\}$，执行以下操作：

首先，令 $\delta_i$ 为下列方程的解：

$$\sum_{x, y} \tilde{P}(x) P(y | x) f_i(x, y) \exp \left(\delta_i f^{\Sigma}(x, y) \right) = E_{\tilde{P}}(f_i)$$

其中，$f^{\Sigma}(x, y)$ 定义为：

$$f^{\Sigma}(x, y) = \sum_{i = 1}^{n} f_i(x, y)$$

然后，更新 $w_i$ 的值：

$$w_i \leftarrow w_i + \delta_i$$

步骤3：如果不是所有 $w_i$ 都收敛，则重复步骤2。

Quasi-Newton Method : BFGS

对最大熵模型而言，

$$P_w(y | x) = \frac{\exp \left(\sum_{i = 1}^{n} w_i f_i(x, y) \right)}{\sum_{y} \exp \left(\sum_{i = 1}^{n} w_i f_i(x, y) \right)}$$

目标函数：

$$\min_{w \in \mathbb{R}^n} f(w) = \sum_{x} \tilde{P}(x) \ln \sum_{y} \exp \left(\sum_{i = 1}^{n} w_i f_i(x, y) \right) - \sum_{x, y} \tilde{P}(x, y) \sum_{i = 1}^{n} w_i f_i(x, y)$$

相应 $i$ 的梯度有，

$$\frac{\partial f(w)}{\partial w_i} = \sum_{x, y} \tilde{P}(x) P_w(y | x) f_i(x, y) - E_{\tilde{p}}(f_i)$$

定义 $g()$

$$g(w) = \left(\frac{\partial f(x)}{\partial w_1}, \frac{\partial f(x)}{\partial w_2}, \dots,\frac{\partial f(x)}{\partial w_n} \right)^T$$

算法步骤

输入：特征函数 $f_1, f_2, \dots, f_n$；经验分布 $\tilde{P}(X, Y)$；目标函数 $f(w)$；梯度 $g(w) = \nabla f(w)$；精度要求 $\epsilon$
输出：最优参数值 $w_i^{\ast}$；最优模型 $P_{w^{\ast}}$

1. 选定初始点 $w^{(0)}$，取 $B_0$ 为正定对称矩阵，置 $k = 0$。
2. 计算 $g_k = g(w^{(k)})$。
   若 $\lVert g_k \rVert < \epsilon$，则停止计算，得 $w^{*} = w^{(k)}$；否则转第 3 步。
3. 由 $B_k p_k = -g_k$ 求出 $p_k$。
4. 一维搜索，求 $\lambda_k$ 使得 $$f(w^{(k)} + \lambda_k p_k) = \min_{\lambda \geq 0} f(w^{(k)} + \lambda p_k)$$
5. 置 $w^{(k + 1)} = w^{(k)} + \lambda_k p_k$。
6. 计算 $g_{k + 1} = g(w^{(k + 1)})$。
   若 $\lVert g_{k + 1} \rVert < \epsilon$，则停止计算，得 $w^{*} = w^{(k + 1)}$；否则，按下式求出 $B_{k + 1}$： $$B_{k + 1} = B_k + \frac{y_k y_k^T}{y_k^T \delta_k} - \frac{B_k \delta_k \delta_k^T B_k}{\delta_k^T B_k \delta_k}$$ 其中， $$y_k = g_{k + 1} - g_k, \quad \delta_k = w^{(k + 1)} - w^{(k)}$$
7. 置 $k = k + 1$，转第 3 步。

补充说明

在 BFGS 算法中，$B_k$ 是对目标函数 Hessian 矩阵的近似。初始时 $B_0$ 通常取为单位矩阵或其他对称正定矩阵。每次迭代后，$B_k$ 按如下公式更新：

$$B_{k + 1} = B_k + \frac{y_k y_k^T}{y_k^T \delta_k} - \frac{B_k \delta_k \delta_k^T B_k}{\delta_k^T B_k \delta_k}$$

其中，

• $\delta_k = w^{(k + 1)} - w^{(k)}$ 表示参数的变化，
• $y_k = g_{k + 1} - g_k$ 表示梯度的变化。

$B_k$ 的更新保证了其对称正定性，并逐步逼近真实的 Hessian 矩阵，从而提升搜索方向的准确性和收敛速度。