DanielLaah

《统计学习方法》笔记 (九) -最大熵模型


本篇博客为《统计学习方法》笔记系列第9篇, 对应《统计学习方法》中第6章中的最大熵模型.
说明: 目前来讲, 本系列博客内容基本完全摘抄自李航博士的《统计学习方法》, 所以阅读本系列博客极有可能造成您的不适, 如发生, 请尽快关闭浏览器. 写此系列博客目的一是学习的时候加深印象二是为了方便自己随时复习. 后面如果在其他书籍或课程中学习了相关的知识, 可能会对文章内容进行适量增删. 谢谢你!
PPT下载


一. 最大熵原理

最大熵原理是概率模型学习的一个准则. 最大熵原理认为, 学习概率模型时, 在所有可能的概率模型(分布) 中, 熵最大的模型是最好的模型. 通常用约束条件来确定概率模型的集合, 所以, 最大熵原理也可以表述为在满足约束条件的模型集合中选取熵最大的模型.
假设离散随机变量X的概率分布是P(X), 则其熵是
$$H(P)=-\sum_xP(x)\log P(x)$$
熵满足下列不等式:
$$0\le H(P)\le \log|X|$$
式中, $|X|$是$X$的取值个数, 当且仅当$X$的分布是均匀分布时右边的等号成立. 这就是说, 当$X$服从均匀分布时, 熵最大.
直观地, 最大熵原理认为要选择的概率模型首先必须满足已有的事实, 即约束条件. 在没有更多信息的情况下, 那些不确定的部分都是等可能的. 最大熵原理通过熵的最大化来表示等可能性. 等可能不容易操作, 而熵则是一个可优化的数值指标.

二. 最大熵模型的定义

最大熵原理是统计学习的一般原理, 将它应用到分类得到最大熵模型.
假设分类模型是一个条件概率分布$P(Y|X)$, $X\in\mathcal{X} \subseteq R^n$表示输入, $Y\in\mathcal{Y}$表示输出, $\mathcal{X}$和$\mathcal{Y}$分别是输入和输出的集合. 这个模型表示的是对于给定的输入$X$, 以条件概率$P(Y|X)$输出$Y$.
给定一个训练数据集
$$T={(x_1, y_1), (x_2, y_2),…,(x_N, y_N)}$$
学习的目标是用最大熵原理选择最好的分类模型.
首先考虑模型应该满足的条件. 给定训练数据集, 可以确定联合分布$P(X,Y)$的经验分布和边缘分布$P(X)$的经验分布, 分别以$\widetilde{P}(X,Y)$和$\widetilde{P}(X)$表示. 这里,
$$\widetilde{P}(X=x,Y=y)=\frac{v(X=x,Y=y)}{N}$$
$$\widetilde{P}(X=x)=\frac{v(X=x)}{N}$$
其中, $v(X=x,Y=y)$表示训练数据中样本$(X,Y)$出现的频数, $v(X=x)$表示训练数据中输入$x$出现的频数, $N$表示训练样本容量.
用特征函数(feature function) $f(X,Y)$描述输入$x$和输出$y$之间的某一个事实. 其定义是
$$f(x,y)=
\begin{cases} 1, & \text{x与y满足某一事实}, \\
0, & \text{否}
\end{cases}$$
它是一个二值函数, 当$x$和$y$满足这个事实时取值为1, 否则取值为0.
特征函数$f(X,Y)$关于经验分布$\widetilde{P}(X,Y)$的期望值, 用$E_{\widetilde{P}}(f)$表示.
$$E_{\widetilde{P}}(f)=\sum_{x,y}\widetilde{P}(x,y)f(x,y)$$
特征函数$f(X,Y)$关于模型$P(Y|X)$与经验分布$\widetilde{P}(X)$的期望值, 用$$E_{P}(f)$$表示.
$$E_{P}(f)=\sum_{x,y}\widetilde{P}(x)P(y|x)f(x,y)$$
如果模型能够获取训练数据中的信息, 那么就可以假设这两个期望值相等, 即
$$E_{\widetilde{P}}(f)=E_{P}(f)\tag{6.10}$$
$$\sum_{x,y}\widetilde{P}(x)P(y|x)f(x,y)=\sum_{x,y}\widetilde{P}(x,y)f(x,y)\tag{6.11}$$
我们将式(6.10) 或式(6.11) 作为模型学习的约束条件. 假如有$n$个特征函数$f_i(X,Y), i=1,2,…,n$那么就有$n$个约束条件.
假设满足所有约束条件的模型集合为
$$\mathcal{C}\equiv\{P\in \mathcal{P}|E_p(f_i)=E_{\widetilde{P}}(f_i), i=1,2,…,n\}$$
定义在条件概率分布P(Y|X)上的条件熵为
$$H(P)=-\sum_{x,y}\widetilde{P}(x)P(y|x)\log P(y|x)$$
则模型集合$\mathcal{C}$中条件熵$H(P)$最大的模型称为最大熵模型. 式中的对数为自然对数.

三. 最大熵模型的学习

最大熵模型的学习过程就是求解最大熵模型的过程. 最大熵模型的学习可以形式化为约束最优化问题.
对于给定的训练数据集$T={(x_1, y_1),(x_2, y_2),…,(x_N,y_N)}$以及特征函数$f_i(X,Y), i=1,2,…,n$最大熵模型的学习等价于约束最优化问题:
$$\begin{align}
\max_{P\in C} &\quad H(P)=-\sum_{x,y}\widetilde{P}(x)P(y|x)\log P(y|x) \\
\\
\text{s.t.} &\quad E_{\widetilde{P}}(f_i)=E_{P}(f_i), i=1,2,…,n \\
\\
&\quad \sum_{y}P(y|x)=1
\end{align}$$
按照最优化问题的习惯, 将求最大值问题改写为等价的求最小值问题:
$$\begin{align}
\min_{P\in C} &\quad -H(P)=-\sum_{x,y}\widetilde{P}(x)P(y|x)\log P(y|x) \tag{6.14}\\
\\
\text{s.t.} &\quad E_{\widetilde{P}}(f_i)-E_{P}(f_i)=0, i=1,2,…,n\tag{6.15} \\
\\
&\quad 1-\sum_{y}P(y|x)=0\tag{6.16}
\end{align}$$
求解约束最优化问题(6.14) ~(6.16) , 所得出的解, 就是最大熵模型学习的解. 下面给出具体推导.
这里, 将约束最优化的原始问题转换为无约束最优化的对偶问题[4]. 通过求解对偶问题求解原始问题.
首先, 引进拉格朗日乘子$w_0,w_1,w_2,…,w_n$, 定义拉格朗日函数$L(P,w)$:
$$\begin{align}
L(P,w) & \equiv -H(P) + w_0\left(1-\sum_{y}P(y|x)\right) + \left(\sum_{i=1}^nw_i(E_{\widetilde{P}}(f_i)-E_{p}(f_i)\right) \\
\\
& = \sum_{x,y}\widetilde{P}(x)P(y|x)\log P(y|x) + w_0\left(1-\sum_{y}P(y|x)\right) \\
& + \sum_{i=1}^nw_i\left(\sum_{x,y}\widetilde{P}(x,y)f_i{(x,y)}-\sum_{x,y}\widetilde{P}(x)P(y|x)f_i(x,y)\right)
\end{align} \tag{6.17}$$
最优化的原始问题是
$$\min_{P\in \mathcal{C}}\max_{w}L(P,w)\tag{6.18}$$
对偶问题是
$$\max_{w}\min_{P\in \mathcal{C}}L(P,w)\tag{6.19}$$
由于拉格朗日函数$L(P,w)$是$P$的凸函数, 原始问题(6.18) 的解与对偶问题(6.19) 的解是等价的. 这样, 可以通过求解对偶问题(6.19) 来求解原始问题(6.18).
首先, 求解对偶问题(6.19)内部的极小化问题$\min_{P\in \mathcal{C}}L(P,w)$, $\min_{P\in \mathcal{C}}L(P,w)$是$w$的函数, 将其记作
$$\Psi(w)=\min_{P\in \mathcal{C}}L(P,w)=L(P_w,w) \tag{6.20}$$
$\Psi(w)$称为对偶函数. 同时, 将其解记作
$$P_w=\arg\min_{P\in \mathcal{C}}L(P,w)=P_w(y|x) \tag{6.21}$$
具体地, 求L(P,w)对P(Y|X)的偏导数
$$\begin{align}
\frac{\partial L(P,w)}{\partial P(y|x)} & = \sum_{x,y}\widetilde{P}(x)(\log P(y|x)+1)-\sum_{y}w_0-\sum_{x,y}\left(\widetilde{P}(x)\sum_{i=1}^nw_if_i(x,y)\right) \\
\\
& = \sum_{x,y}\widetilde{P}(x)\left(\log P(y|x)+1-w_0-\sum_{i=1}^nw_if_i(x,y)\right) \\
\end{align}$$
令偏导数等于0, 在$\widetilde{P}(x)\gt 0$的情况下, 解得
$$P(y|x)=\exp\left(\sum_{i=1}^nw_if_i(x,y)+w_0-1\right)=\frac{\exp\left(\sum_{i=1}^nw_if_i(x,y)\right)}{\exp(1-w_0)}$$
由于$\sum_{y}P(y|x)=1$, 得
$$P_{w}(y|x)=\frac{1}{Z_w(x)}\exp\left(\sum_{i=1}^nw_if_i(x,y)\right) \tag{6.22}$$
其中,
$$Z_w(x)=\sum_{y}\exp\left(\sum_{i=1}^nw_if_i(x,y)\right) \tag{6.23}$$
$Z_w(x)$称为规范化因子;$f_i(X,Y)$是特征函数;$w_i$是特征的权值. 由式(6.22), 式(6.23) 表示的模型$P_w=P_w(y|x)$就是最大熵模型. 这里, $w$是最大熵模型中的参数向量. 之后, 求解对偶问题外部的极大化问题
$$\max_{w}\Psi(w)$$
将其解记为$w^*$, 即
$$w^*=\arg\max_{w}\Psi(w)$$
这就是说, 可以应用最优化算法求对偶函数$\Psi(w)$的极大化, 得到$w^*$, 用来表示$P^*\in \mathcal{C}$. 这里, $P^*=P_{w*}=P_{w*}(Y|X)$是学习到的最优模型(最大熵模型) . 也就是说, 最大熵模型的学习归结为对偶函数$\Psi(w)$的极大化.


四. 极大似然估计

从以上最大熵模型学习中可以看出, 最大熵模型是由式(6.22), 式(6.23) 表示的条件概率分布. 下面证明对偶函数的极大化等价于最大熵模型的极大似然估计.
已知训练数据的经验概率分布$\widetilde{P}(X,Y)$, 条件概率分布$P(Y|X)$的对数似然函数表示为
$$L_{\widetilde{P}}(P_w)=\log\Pi_{x,y}P(y|x)^{\tilde{P}(x,y)}=\sum_{x,y}\widetilde{P}(x,y)\log P(y|x)$$
当条件概率分布$P(Y|X)$是最大熵模型(6.22) 和(6.23) 时, 对数似然函数$L_{\widetilde{P}}(P_w)$为
$$\begin{align}
L_{\widetilde{P}}p(_w) & = \sum_{x,y}\widetilde{P}(x,y)\log P(y|x) \\
\\
& = \sum_{x,y}\widetilde{P}(x,y)\sum_{i=1}^nw_if_i(x,y)-\sum_{x,y}\widetilde{P}(x,y)\log Z_w(x) \\
\\
& = \sum_{x,y}\widetilde{P}(x,y)\sum_{i=1}^nw_if_i(x,y)-\sum_{x}\widetilde{P}(x)\log Z_w(x)
\end{align}$$
再看对偶函数$\Psi(w)$. 由式(6.17) 及式(6.20) 可得

最后一步用到$\sum_{y}P(y|x)=1$.
比较式(6.26) 和式(6.27) , 可得
$$\Psi(w)=L_{\widetilde{P}}(P_w)$$
既然对偶函数$\Psi(w)$等价于对数似然函数$L_{\widetilde{P}}(P_w)$, 于是证明了最大熵模型学习中的对偶函数极大化等价于最大熵模型的极大似然估计这一事实.
这样, 最大熵模型的学习问题就转换为具体求解对数似然函数极大化或对偶函数极大化的问题.
可以将最大熵模型写成更一般的形式.
$$P_w(y|x)=\frac{1}{Z_(x)}\exp\left(\sum_{i=1}^nw_if_i(x,y)\right)$$
其中,
$$Z_w(x)=\sum_{y}\exp\left(\sum_{i=1}^nw_if_i(x,y)\right)$$
这里, $x\in R^n$为输入, $y\in {1,2,…,K}$为输出, $w\in R^n$为权值向量, $f_i(X,Y), i=1,2,…,n$为任意实值特征函数.
最大熵模型与逻辑斯谛回归模型有类似的形式, 它们又称为对数线性模型(log linear model) . 模型学习就是在给定的训练数据条件下对模型进行极大似然估计或正则化的极大似然估计.