Reference

详解最大熵模型

最大熵模型原理

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

二十一.最大熵模型原理

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

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

【对偶函数的极大化】

对于最大熵模型的约束最优化问题，内部的极小化问题的求解得到了关于 $\boldsymbol{\omega}$ 的对偶函数

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

此时，只需对最大熵模型进行学习，即对对偶问题 $\max\limits_{\boldsymbol{\omega}}\:\min\limits_{p\in\mathcal{C}}\:L(p,\boldsymbol{\omega})$ 的外部极大化问题进行处理

将极大化问题的解记为 $\boldsymbol{\omega}^{*}$，有：

$\boldsymbol{\omega}^{*}=\arg \max_{\boldsymbol{\omega}} \psi(\boldsymbol{\omega})$

将 $p_{\boldsymbol{\omega}}(y|x)$ 代入到对偶函数 $\psi(\boldsymbol{\omega})$ 中，可得：

$\begin{align*} \psi(\boldsymbol{\omega}) =& \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] \\ =& \sum_{x\in X}\tilde{p}(x)\sum_{y\in Y}p_{\boldsymbol{\omega}}(y|x)\log p_{\boldsymbol{\omega}}(y|x) + \omega^{(0)}\bigl[1-\sum_{y\in Y} p_{\boldsymbol{\omega}}(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_{\boldsymbol{\omega}}(y|x)f_j(x,y) \Big] \end{align*}$

由于 $\sum\limits_{y\in Y} p(y|x)=1$，故有：

$\begin{align*} \psi(\boldsymbol{\omega}) =& \sum_{x\in X,y\in Y} \tilde{p}(x) \log p_{\boldsymbol{\omega}}(y|x) + \sum_{j=1}^m \omega^{(j)} \sum_{x\in X,y\in Y} \tilde{p}(x,y)f_j(x,y) \\\ &- \sum_{j=1}^m\omega^{(j)}\sum_{x\in X,y\in Y} \tilde{p}(x)f_j(x,y) \end{align*}$

又因为：

$\log p_{\boldsymbol{\omega}}(y|x) = \sum_{j=1}^m \omega^{(j)}f_j(x,y) - \log Z_{\boldsymbol{\omega}} (x)$

则有：

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

化简得：

$\psi(\boldsymbol{\omega}) = \sum_{x\in X,y\in Y} \tilde{p}(x,y)\sum_{j=1}^m \omega^{(j)} f_j(x,y) - \sum_{x\in X} \tilde{p}(x) \log Z_{\boldsymbol{\omega}}(x)$

故极大化问题为：

$\boldsymbol{\omega}^{*}=\arg \max_{\boldsymbol{\omega}} \Big [\sum_{x\in X,y\in Y} \tilde{p}(x,y)\sum_{j=1}^m \omega^{(j)} f_j(x,y) - \sum_{x\in X} \tilde{p}(x) \log Z_{\boldsymbol{\omega}}(x) \Big]$

【最大熵模型的极大似然估计】

假设样本集大小为 $n$，对于样本具体观测值 $x_1,x_2,…,x_n$，假设其取值有 $K$ 个，分别为 $v_1,v_2,…,v_K$，用 $C(X=v_i)$ 表示在观测值中样本 $v_i$ 出现的频数，那么似然函数可写为：

$L(x_1,x_2,...,x_n;\theta) = \prod_{k=1}^K p(v_k;\theta)^{C(X=v_k)}$

对上式两边同时开 $\frac{1}{n}$ 次方，可得：

$L(x_1,x_2,...,x_n;\theta)^{\frac{1}{n}} = \prod_{k=1}^k p(v_k;\theta)^\frac{C(X=v_k)}{n}$

由于经验概率 $\tilde{p}(x)=\frac{C(X=v_k)}{n}$，故有：

$L(x_1,x_2,...,x_n;\theta)^{\frac{1}{n}} = \prod_{x\in X} p(x;\theta)^{\tilde{p}(x)}$

显然，对 $L(x_1,x_2,…,x_n;\theta)^{\frac{1}{n}}$ 求极大值与对 $L(x_1,x_2,…,x_n;\theta)$ 求极大值的优化结果是相同的，那么，最终的极大似然函数可表示为：

$L(x;\theta) = \prod_{x\in X} p(x;\theta)^{\tilde{p}(x)}$

当已知训练数据的经验概率分布为 $\tilde{p}(X,Y)$ 时，有：

$\begin{align*} L_{\tilde{p}} &= \log \prod_{x\in X,y\in Y} p(x,y)^{\tilde{p}(x,y)} \\ &= \sum_{x\in X,y\in Y} \tilde{p}(x,y) \log p(x,y) \\ &= \sum_{x\in X,y\in Y} \tilde{p}(x,y) \log \big[ \tilde{p}(x)p(y|x) \big] \\ &= \sum_{x\in X,y\in Y} \tilde{p}(x,y)\log p(y|x) + \sum_{x\in X,y\in Y} \tilde{p}(x,y)\log \tilde{p}(x) \end{align*}$

其中，对于第二项 $\sum\limits_{x\in X,y\in Y} \tilde{p}(x,y)\log \tilde{p}(x)$，一旦样本集确定，经验分布 $\tilde{p}(x,y)$ 与 $\tilde{p}(x)$ 可直接算出，故该项为一常数，忽略即可，故而最终的对数似然函数为：

$L_{\tilde{p}}=\sum_{x\in X,y\in Y} \tilde{p}(x,y) \log p(y|x)$

当条件概率分布 $p(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]$ 时，对数似然函数为：

$\begin{align*} L_{\tilde{p}}(p_{\boldsymbol{\omega}}) &= \sum_{x\in X,y\in Y} \tilde{p}(x,y)\log p_{\boldsymbol{\omega}}(y|x) \\ &= \sum_{x\in X,y\in Y} \tilde{p}(x,y)\sum_{j=1}^m \omega^{(j)} f_j(x,y)-\sum_{x\in X,y\in Y}\tilde{p}(x,y)\log Z_{\boldsymbol{\omega}} (x) \\ &= \sum_{x\in X,y\in Y} \tilde{p}(x,y)\sum_{j=1}^m \omega^{(j)} f_j(x,y)-\sum_{x\in X}\tilde{p}(x)\log Z_{\boldsymbol{\omega}} (x) \\ \end{align*}$

可以发现，对数似然函数 $L_{\tilde{p}}(p_{\boldsymbol{\omega}}) $ 与对偶函数 $\psi(\boldsymbol{\omega}) $ 相等，即：

$L_{\tilde{p}}(p_{\boldsymbol{\omega}}) = \psi(\boldsymbol{\omega})$

接着，考虑对偶函数 $\psi(\boldsymbol{\omega})$，有：

$\begin{align*} \psi(\boldsymbol{\omega}) &= -\sum_x\tilde{p}(x)\log Z_{\boldsymbol{\omega}}(x)+\sum_{j=1}^m\omega^{(j)}E_{\tilde{p}}(f_j) \\ &= -\sum_x\tilde{p}(x)\log Z_{\boldsymbol{\omega}}(x)+\sum_{j=m}^n\omega^{(j)}\sum_{x,y}\tilde{p}(x,y)f_j(x,y)\\ &= \sum_{x,y}\tilde{p}(x,y)\sum_{j=1}^m\omega^{(j)}f_j(x,y)-\sum_x\tilde{p}(x)\log Z_{\boldsymbol{\omega}}(x) \end{align*}$

可以发现，最大熵模型 $p_{\boldsymbol{\omega}}(y|x)$ 的对数似然函数与对偶函数 $\psi(\boldsymbol{\omega})$ 等价，即：

$\psi(\boldsymbol{\omega})=L_{\tilde{p}}(p_{\boldsymbol{\omega}})$

因此，最大熵模型学习中的对偶函数 $\psi(\boldsymbol{\omega})$ 极大化等价于最大熵模型的极大似然估计，这样对最大熵模型的学习问题就转化成了具体求解对数似然函数极大化或求解对偶函数极大化的问题，即：

$\max_{\boldsymbol{\omega}}\sum_{x\in X,y\in Y}\tilde{p}(x,y)\sum_{j=1}^m\omega^{(j)}f_j(x,y)-\sum_{x\in X}\tilde{p}(x)\log Z_{\boldsymbol{\omega}}(x)$