最大熵模型
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 | \mathbf{x}) &= \frac{1}{1 + \exp (\mathbf{w} \cdot \mathbf{x} + b)} \tag{3} \\ P(Y = 1 | \mathbf{x}) &= \frac{\exp (\mathbf{w} \cdot \mathbf{x} + b)}{1 + \exp (\mathbf{w} \cdot \mathbf{x} + b)} \tag{4} \end{align} \]
其中，\(\mathbf{x} \in \mathbb{R}^n\) 是输入，\(\mathbf{w} \in \mathbb{R}^n\) 和 $ b $ 分别是权值向量和偏置，\(\mathbf{w} \cdot \mathbf{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}(x) \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}}\)
- 选定初始点 \(w^{(0)}\)，取 \(B_0\) 为正定对称矩阵，置 \(k = 0\)。
- 计算 \(g_k = g(w^{(k)})\)。
若 \(\lVert g_k \rVert < \epsilon\)，则停止计算，得 \(w^{*} = w^{(k)}\)；否则转第 3 步。 - 由 \(B_k p_k = -g_k\) 求出 \(p_k\)。
- 一维搜索，求 \(\lambda_k\) 使得 \[ f(w^{(k)} + \lambda_k p_k) = \min_{\lambda \geq 0} f(w^{(k)} + \lambda p_k) \]
- 置 \(w^{(k + 1)} = w^{(k)} + \lambda_k p_k\)。
- 计算 \(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)} \] - 置 \(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 矩阵，从而提升搜索方向的准确性和收敛速度。