Reference

详解最大熵模型

最大熵模型原理

深入机器学习系列21-最大熵模型

二十一.最大熵模型原理

最大熵模型中的对数似然函数表示法解释

最大熵模型中的对数似然函数的解释

【约束最优化问题】

最大熵模型的学习过程，即求解最大熵模型的过程，其可以形式化为约束最优化问题

对于给定的训练数据集 $T=\{(\mathbf{x_1},y_1),(\mathbf{x_2},y_2),…,(\mathbf{x_n},y_n)\}$，第 $i$ 组样本中的输入 $\mathbf{x_i}$ 具有 $m$ 个特征值，即：$\mathbf{x_i} =(x_i^{(1)},x_i^{(2)},…,x_i^{(m)})\in \mathbb{R}^m$，输出 $y_i\in\mathcal{Y}= \{c_1,c_2,…,c_K\}$ 为实例的类别，特征函数 $f_j(x^{(j)},y),j=1,2,…,m$

最大熵模型的学习等价于下述的约束最优化问题，即求取最大的条件熵使得边际概率和为 $1$，同时特征期望相同：

$\begin{gather*} \max_{p\in \mathcal{C}} & H(Y|X)=-\sum_{x\in X}\tilde{p}(x)\sum_{y\in Y}p(y|x)\log p(y|x) \\ s.t. & \left\{\begin{array}{rl} \sum\limits_{y\in Y}p(y|x) &=& 1 &\\ E_p(f_j) &=& E_{\tilde{p}}(f_j), & j=1,2,...,m \end{array}\right. \end{gather*}$

按照最优化问题的习惯，将最大化问题改写为等价的最小化问题：

$\begin{gather*} \min_{p\in \mathcal{C}} & -H(Y|X)=\sum_{x\in X}\tilde{p}(x)\sum_{y\in Y}p(y|x)\log p(y|x) \\ s.t. & \left\{\begin{array}{rl} 1-\sum\limits_{y\in Y}p(y|x) &=& 0& \\ E_{\tilde{p}}(f_j) - E_p(f_j) &=& 0, & j=1,2,...,m \end{array}\right. \end{gather*}$

此时，求解最小化问题所得出的解，即最大熵模型学习的解

【最大熵模型】

对于上述的约束最优化问题，使用拉格朗日乘子法进行求解，关于拉格朗日乘子法，详见：拉格朗日乘子法与对偶性

首先，引入拉格朗日乘子 $\boldsymbol{\omega} = \{\omega^{(0)},\omega^{(1)},…,\omega^{(m)}\}$，并定义拉格朗日函数：

$\begin{align*} L(p,\boldsymbol{\omega}) \equiv& -H(Y|X) + \omega^{(0)}\bigl[1-\sum_{y\in Y} p(y|x)\bigr] + \sum_{j=1}^m \omega^{(j)}\bigl[E_{\tilde{p}}(f_j)-E_p(f_j)\bigr] \\ =& \sum_{x\in X}\tilde{p}(x)\sum_{y\in Y}p(y|x)\log p(y|x) + \omega^{(0)}\bigl[1-\sum_{y\in Y} p(y|x)\bigr] \\ &+ \sum_{j=1}^m \omega^{(j)}\Big[ \sum_{x\in X}\sum_{y\in Y} \tilde{p}(x,y)f_j(x,y) - \sum_{x\in X}\tilde{p}(x)\sum_{y\in Y}p(y|x)f_j(x,y) \Big] \end{align*}$

此时，最优化的原始问题为：

$\min_{p\in\mathcal{C}}\:\max_{\boldsymbol{\omega}}\:L(p,\boldsymbol{\omega})$

其对偶问题为：

$\max_{\boldsymbol{\omega}}\:\min_{p\in\mathcal{C}}\:L(p,\boldsymbol{\omega})$

由于拉格朗日函数 $L(p,\boldsymbol{\omega})$ 是 $p$ 的凸函数，且其满足 Slater 条件，故原始问题的解与对偶问题的解是等价的，进而可以通过求解对偶问题来求解原始问题

对于对偶问题内部的极小化问题 $\min\limits_{p\in\mathcal{C}}\:L(p,\boldsymbol{\omega})$，其是 $\boldsymbol{\omega}$ 的函数，将其记为 $\psi(\boldsymbol{\omega})$，即对偶函数，有：

$\psi(\boldsymbol{\omega})= \min\limits_{p\in\mathcal{C}}\:L(p,\boldsymbol{\omega}) = L(p_{\boldsymbol\omega},\boldsymbol\omega)$

将对偶函数 $\psi(\boldsymbol{\omega})$ 解记为 $p_{\boldsymbol{\omega}}$，有：

$p_{\boldsymbol{\omega}} = \arg\min_{p\in\mathcal{C}}L(p,\boldsymbol{\omega}) = p_{\boldsymbol{\omega}}(y|x)$

具体地，计算 $L(p,\boldsymbol{\omega})$ 对 $p(y|x)$ 的偏导数，即：

$\begin{align*} \frac{\partial L(p,\boldsymbol{\omega})}{\partial p(y|x)} =& \sum_{x\in X} \tilde{p}(x) \sum_{y\in Y} \log p(y|x) + \sum_{x\in X} \tilde{p}(x) - \sum_{y\in Y} \omega^{(0)} \\ &- \sum_{x\in X} p(x) \sum_{j=1}^m \omega^{(j)} \sum_{y \in Y} f_j(x,y) \\ =& \sum_{x\in X,y\in Y} \tilde{p}(x)\log p(y|x) + \sum_{x\in X} \tilde{p}(x) -\sum_{y\in Y} \omega^{(0)}\\ &- \sum_{x\in X,y\in Y}\tilde{p}(x)\sum_{j=1}^m \omega^{(j)}f_j(x,y) \\ =& \sum_{x\in X,y\in Y} \tilde{p}(x)\Big[ \log p(y|x) + 1 - \omega^{(0)} - \sum_{j=1}^m \omega^{(j)}f_j(x,y) \Big] \end{align*}$

令偏导数 $\frac{\partial L(p,\boldsymbol{\omega})}{\partial p(y|x)}=0$，即：

$\sum_{x\in X,y\in Y}\tilde{p}(x)\bigl[ \log p(y|x)+1-\omega^{(0)}-\sum_{j=1}^m \omega^{(j)}f_j(x,y) \bigr]=0$

在已知 $\tilde{p}(x)>0$ 的情况下，有：

$\log p(y|x)+1-\omega^{(0)}-\sum_{j=1}^m \omega^{(j)}f_j(x,y) = 0$

即：

$\log p(y|x) = \sum_{j=1}^m \omega^{(j)}f_j(x,y)+\omega^{(0)}-1$

可得：

$p(y|x) = \exp \Big[ \sum_{j=1}^m \omega^{(j)}f_j(x,y)+\omega^{(0)}-1 \Big]$

即：

$p(y|x)=\frac{\exp \Big[ \sum_{j=1}^m \omega^{(j)}f_j(x,y) \Big]}{\exp\Big[1-\omega^{(0)}\Big]}$

由于 $\sum\limits_{y\in Y} p(y|x)=1$，根据等概率原则可得：

$\exp\Big[1-\omega^{(0)}\Big] = \sum_{y\in Y} \exp \Big[ \sum_{j=1}^m \omega^{(j)}f_j(x,y) \Big]$

记 $Z_{\boldsymbol\omega}(x)=\sum\limits_{y\in Y} \exp \Big[ \sum\limits_{j=1}^m \omega^{(j)}f_j(x,y) \Big]$，称为规范化因子，其具有归一化的作用，保证了 $p_{\boldsymbol{\omega}}(y|x)$ 是概率，那么有：

$p_{\boldsymbol{\omega}}(y|x) = \frac{1}{Z_{\boldsymbol\omega}(x)} \exp\Big[\sum_{j=1}^m\omega^{(j)}f_j(x,y)\Big]$

此时所得到的对偶函数 $\psi(\boldsymbol{\omega})$ 的解 $p_{\boldsymbol{\omega}}=p_{\boldsymbol{\omega}}(y|x)$ 即为最大熵模型