最大熵模型

前言

今天看了《统计学习方法》的第6章逻辑斯蒂回归与最大熵模型,由于之前没有了解过最大熵模型,所以看的迷迷糊糊的,遂在网上找了点资料看了看,发现CSDN上有一篇文章总结的还不错,于是半抄半写的写了这篇blog。

熵的定义

首先要知道熵是什么,这里提到了熵,联合熵,相对熵,互信息(mutual info)的定义

如果一个随机变量X的可能取值为\(X = \lbrace x_1, x_2,…, x_k \rbrace\),其概率分布为\(P(X = x_i) = p_i (i = 1,2, ..., n)\),则随机变量X的熵定义为: \[H(x)=-\sum_x {p(x)logp(x)}\] 把最前面的负号放在最后,便成了:\[H(x)=\sum_x {p(x)log{1 \over p(x)}}\]

上面两个熵公式,无论用哪个都行,而且两者等价,一个意思

联合熵

表示两个随机变量X,Y的联合分布,可以形成联合熵(Joint Entropy),用\(H(X,Y)\)表示

条件熵

在随机变量X发生的前提下,随机变量Y发生所新带来的熵定义为Y的条件熵,用\(H(Y|X)\)表示,用来衡量在已知随机变量X的条件下随机变量Y的不确定性。

且有此式子成立:\(H(Y|X) = H(X,Y) - H(X)\),整个式子表示(X,Y)发生所包含的熵减去X单独发生包含的熵。至于怎么来的请看推导: 推导

简单解释下上面的推导过程。整个式子共6行,其中

  • 第二行推到第三行的依据是边缘分布\(p(x)\)等于联合分布\(p(x,y)\)的和;
  • 第三行推到第四行的依据是把公因子\(log{p(x)}\)乘进去,然后把x,y写在一起;
  • 第四行推到第五行的依据是:因为两个\(\sum\)都有\(p(x,y)\),故提取公因子\(p(x,y)\)放到外边,然后把里边的\(-(log {p(x,y)} - log {p(x)})\)写成\(- log {({p(x,y)} \over {p(x)} )} \)
  • 第五行推到第六行的依据是:\(p(x,y) = p(x) * p(y|x)\),故\({p(x,y)\over p(x)}=p(y|x)\)

相对熵

又称互熵,交叉熵,鉴别信息,Kullback熵,Kullback-Leible散度等。设\(p(x)\)\(q(x)\)是X中取值的两个概率分布,则p对q的相对熵是: 相对熵

在一定程度上,相对熵可以度量两个随机变量的“距离”,且有\(D(p\parallel q) \neq D(q \parallel p)\)。另外,值得一提的是,\(D(p\parallel q)\)是必然大于等于0的。

互信息

两个随机变量X,Y的互信息定义为X,Y的联合分布和各自独立分布乘积的相对熵,用\(I(X,Y)\)表示:\[I(X,Y) = \sum_{x,y} p(x,y) log {p(x,y) \over p(x)p(y)}\]

且有\(I(X,Y)=D(P(X,Y) \parallel P(X)P(Y))\). 下面,咱们来计算下\(H(Y)-I(X,Y)\)的结果,如下: H(Y)-I(X,Y)

通过上面的计算过程,我们发现竟然有\(H(Y)-I(X,Y) = H(Y\mid X)\)。故通过条件熵的定义,有:\(H(Y\mid X) = H(X,Y) - H(X)\),而根据互信息定义展开得到\(H(Y\mid X) = H(Y) - I(X,Y)\),把前者跟后者结合起来,便有\(I(X,Y)= H(X) + H(Y) - H(X,Y)\),此结论被多数文献作为互信息的定义。

最大熵

熵是随机变量不确定性的度量,不确定性越大,熵值越大;若随机变量退化成定值,熵为0。如果没有外界干扰,随机变量总是趋向于无序,在经过足够时间的稳定演化,它应该能够达到的最大程度的熵。

为了准确的估计随机变量的状态,我们一般习惯性最大化熵,认为在所有可能的概率模型(分布)的集合中,熵最大的模型是最好的模型。换言之,在已知部分知识的前提下,关于未知分布最合理的推断就是符合已知知识最不确定或最随机的推断,其原则是承认已知事物(知识),且对未知事物不做任何假设,没有任何偏见。

例如,投掷一个骰子,如果问“每个面朝上的概率分别是多少”,你会说是等概率,即各点出现的概率均为1/6。因为对这个“一无所知”的色子,什么都不确定,而假定它每一个朝上概率均等则是最合理的做法。从投资的角度来看,这是风险最小的做法,而从信息论的角度讲,就是保留了最大的不确定性,也就是说让熵达到最大。

无偏原则(重要)

下面再举个大多数有关最大熵模型的文章中都喜欢举的一个例子。(我认为这个例子很形象,我就是从这里貌似开始理解的

例如,一篇文章中出现了“学习”这个词,那这个词是主语、谓语、还是宾语呢?换言之,已知“学习”可能是动词,也可能是名词,故“学习”可以被标为主语、谓语、宾语、定语等等。(当然,我现在查到的关于最大熵模型的应用主要是关于NLP的)

  • \(x_1\)表示“学习”被标为名词, \(x_2\)表示“学习”被标为动词。
  • \(y_1\)表示“学习”被标为主语, \(y_2\)表示被标为谓语, \(y_3\)表示宾语, \(y_4\)表示定语。

且这些概率值加起来的和必为1,即\(p(x_1) + p(x_2) = 1\), \(\sum_{i=1}^{4}{p(y_i) = 1}\) , 则根据无偏原则,认为这个分布中取各个值的概率是相等的,故得到:

\[p(x_1) = p(x_2) = 0.5\] \[p(y_1) = p(y_2) = p(y_3) = p(y_4) = 0.25\]

因为没有任何的先验知识,所以这种判断是合理的。但是如果有了一定的先验知识呢?

即进一步,若已知:“学习”被标为定语的可能性很小,只有0.05,即\(p(y_4) = 0.05\) , 剩下的依然根据无偏原则,可得:\[p(x_1) = p(x_2) = 0.5\] \[p(y_1) = p(y_2) = p(y_3) = {0.95 \over 3}\]

再进一步,当“学习”被标作名词\(x_1\)的时候,它被标作谓语\(y_2\)的概率为0.95,即\(p(y_2 \mid x_1) = 0.95\) , 此时仍然需要坚持无偏见原则,使得概率分布尽量平均。但怎么样才能得到尽量无偏见的分布?

实践经验和理论计算都告诉我们,在完全无约束状态下,均匀分布等价于熵最大(有约束的情况下,不一定是概率相等的均匀分布。 比如,给定均值和方差,熵最大的分布就变成了正态分布 )。

于是,问题便转化为了:计算X和Y的分布,使得H(Y|X)达到最大值,并且满足下述条件:

  • \[p(x_1) + p(x_2) = 1\]
  • \[\sum_{i=1}^4 {p(y_i) = 1}\]
  • \[p(y_4) = 0.05\]
  • \[p(y_2 \mid x_1) = 0.95\]

因此,也就引出了最大熵模型的本质,它要解决的问题就是已知X,计算Y的概率,且尽可能让Y的概率最大(实践中,X可能是某单词的上下文信息,Y是该单词翻译成me,I,us、we的各自概率),从而根据已有信息,尽可能最准确的推测未知信息,这就是最大熵模型所要解决的问题。

相当于已知X,计算Y的最大可能的概率,转换成公式,便是要最大化下述式子\(H(Y\mid X)\)\[\max {H(Y \mid X)} = \sum_{x \in \lbrace x_1 , x_2 \rbrace y \in \lbrace y_1 , y_2 , y_3 , y_4 \rbrace} {p(x,y)log {1 \over p(y \mid x)}}\]

且满足以下4个约束条件:

  • \[p(x_1) + p(x_2) = 1\]
  • \[\sum_{i=1}^4 {p(y_i) = 1}\]
  • \[p(y_4) = 0.05\]
  • \[p(y_2 \mid x_1) = 0.95\]

最大熵模型的表示

至此,有了目标函数跟约束条件,我们可以写出最大熵模型的一般表达式了,如下: \[\max_{p \in P} {H(Y \mid X)} = \sum_{(x,y)}{p(x,y)log{1 \over p(y \mid x)}}\]

其中,\(P={p \mid p是X上满足条件的概率分布}\)

继续阐述之前,先定义下特征、样本和特征函数。

特征

\((x,y)\)

  • y: 这个特征中需要确定的信息
  • x:这个特征中的上下文信息

样本

关于某个特征\((x,y)\)的样本,特征所描述的语法现象在标准集合里的分布:\((x_i,y_i)\)对,其中,\(y_i\)\(y\)的一个实例,\(x_i\)\(y_i\)的上下文。

对于一个特征\((x_0,y_0)\),定义特征函数: \[f(n) = \begin{cases} 1, & \text{if $y=y_0$ and $x = x_0$} \\ 0, & \text{else} \\ \end{cases}\]

特征函数关于经验分布\(\overline p(x,y)\)在样本中的期望值是: \[\overline p(f) = \sum_{\lbrace x_i , y_i \rbrace}{\overline p(x,y)f(x,y)}\] 其中\(\overline p(x)\)表示x出现的概率,\(\overline p(x,y)\)表示xy出现的概率

特征函数关于模型\(P(Y\mid X)\)与经验分布\(\overline P(X)\)的期望值为: 期望值

换言之,如果能够获取训练数据中的信息,那么上述这两个期望值相等,即: \[p(f) = \overline p(f)\]

不过,因为实践中p(x)不好求,所以一般用样本中x出现的概率“\(\overline p(x)\)”代替x在总体中的分布概率“\(p(x)\)”,从而得到最大熵模型的完整表述如下:

\[p^* = \arg \max_{p \in P} {\sum_{\lbrace x, y \rbrace}{p(y\mid x) \overline p(x)log{1 \over p(y \mid x)}}}\]

其约束条件为: 约束条件

该问题已知若干条件,要求若干变量的值使到目标函数(熵)最大,其数学本质是最优化问题(Optimization Problem),其约束条件是线性的等式,而目标函数是非线性的,所以该问题属于非线性规划(线性约束)(non-linear programming with linear constraints)问题,故可通过引入Lagrange函数将原带约束的最优化问题转换为无约束的最优化的对偶问题。

\[\Lambda(p , \vec \lambda) = H(y \mid x) + \sum_{i=1}^m \lambda_i(E(f_i) - \overline E(f_i)) + \lambda_{m+1}(\sum_{y \in Y}p(y \mid x)-1)\]

凸优化中的对偶问题

考虑到机器学习里,不少问题都在围绕着一个“最优化”打转,而最优化中凸优化最为常见,所以为了过渡自然,这里简单阐述下凸优化中的对偶问题。

一般优化问题可以表示为下述式子: \[min f_0(x), x \in \mathbf R^n\]\[st. f_i(x) \le 0 , i = 1,\ldots,m \quad and \quad h_j(x) = 0, j=1, \ldots, p \] 其中,subject to导出的是约束条件,\(f(x)\)表示不等式约束,\(h(x)\)表示等式约束。

然后可通过引入拉格朗日乘子\(\lambda\)\(v\),建立拉格朗日函数,如下: \[L(x , \lambda , v) = f_0(x)+ \sum_{i=1}^m \lambda_if_i(x) + \sum_{j=1}^pv_jh_j(x)\] 对固定的x,拉格朗日函数L(x,λ,v)为关于λ和v的仿射函数。

对偶问题极大化的指数解

针对原问题,首先引入拉格朗日乘子\(\lambda_0 , \lambda_1, \lambda_2, \ldots , \lambda_i\),定义拉格朗日函数,转换为对偶问题求其极大化: 拉格朗日乘数法 然后求偏导为: \[{\partial L\over \partial p(y \mid x)} = \overline p(x)(log{1 \over p(y \mid x)} - 1) + \sum_i\lambda_i \overline p(x)f_i(x,y) + \lambda_0\]

注:上面这里是对P(y|x)求偏导,即只把P(y|x)当做未知数,其他都是常数。因此,求偏导时,只有跟P(y0|x0)相等的那个“(x0,y0)”才会起作用,其他的(x,y)都不是关于P(y0|x0)的系数,是常数项,而常数项一律被“偏导掉”了。

令上述的偏导结果等于0,解得:

\[p^*(y \mid x) = e^{\sum_i\lambda_if_i(x,y)- {\lambda_0 \over \overline p(x)} - 1}\]

进一步转换

\[p^*(y \mid x) = {1 \over Z_{\lambda}(x)}e^{\sum_{i}\lambda_if_i(x,y)}\]

其中,Z(x)称为规范化因子。

根据之前的约束条件之一: \(\sum_{y}p(y \mid x) = 1\),所以有:

\[{1 \over Z_{\lambda}(x)}e^{\sum_{i}\lambda_if_i(x,y)} = 1\]

从而有:

\[Z_{\lambda}(x) = \sum_ye^{\sum_{i}\lambda_if_i(x,y)}\]

现将求得的最优解\(P^*(y|x)\)带回之前建立的拉格朗日函数\(L\):

\[L = \sum_{(x,y)}p(y \mid x)\overline p(x)log{1 \over p(y\mid x)} + \sum_{i=1}^k\lambda_i \sum_{(x,y)}f_i(x,y)[p(y\mid x)\overline p(x) - \overline p(x,y)] + \lambda_0[\sum_yp(y\mid x) - 1]\]

得到关于\(\lambda\)的式子: 关于\lambda的式子

注:最后一步的推导中,把之前得到的结果\(p^*(y \mid x) = {1 \over Z_{\lambda}(x)}e^{\sum_{i}\lambda_if_i(x,y)}\)代入计算即可。

接下来,再回过头来看这个式子:

\[Z_{\lambda}(x) = \sum_ye^{\sum_{i}\lambda_if_i(x,y)}\]

可知,最大熵模型模型属于对数线性模型,因为其包含指数函数,所以几乎不可能有解析解。换言之,即便有了解析解,仍然需要数值解。那么,能不能找到另一种逼近?构造函数f(λ),求其最大/最小值?

相当于问题转换成了寻找与样本的分布最接近的概率分布模型,如何寻找呢?接下来讲述极大似然估计。

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

所谓最大似然,即最大可能,在“模型已定,参数θ未知”的情况下,通过观测数据估计参数θ的一种思想或方法,换言之,解决的是取怎样的参数θ使得产生已得观测数据的概率最大的问题。

举个例子,假设我们要统计全国人口的身高,首先假设这个身高服从服从正态分布,但是该分布的均值与方差未知。由于没有足够的人力和物力去统计全国每个人的身高,但是可以通过采样(所有的采样要求都是独立同分布的),获取部分人的身高,然后通过最大似然估计来获取上述假设中的正态分布的均值与方差

极大似然估计MLE的一般形式表示为:

\[L_{\overline p} = \prod_xp(x)^{\overline p(x)}\]

其中,\(p(x)\)是对模型进行估计的概率分布,\(\overline p(x)\)是实验结果得到的概率分布。

进一步转换,可得:

\[L_{\overline p} = log(\prod_xp(x)^{\overline p(x)}) = \sum_x\overline p(x)logp(x)\]

对上面两边取对数: 极大似然推导

因上述式子最后结果的第二项是常数项(因为第二项是关于样本的联合概率和样本自变量的式子,都是定值),所以最终结果为:

\[L_{\overline p}(p) = \sum_{x,y}\overline p(x,y)logp(y \mid x)\]

至此,我们发现极大似然估计和条件熵的定义式具有极大的相似性,故可以大胆猜测它们极有可能殊途同归,使得它们建立的目标函数也是相同的。 我们来推导下,验证下这个猜测。

将之前得到的最大熵的解带入MLE,计算得到(右边在左边的基础上往下再多推导了几步): 验证极大似然估计和条件上的定义式的相似性

注意:其中\(Z_{\lambda}(x) = \sum_ye^{\sum_{i}\lambda_if_i(x,y)}\),且\(\overline P(x,y) = \overline P(x) * P(y\mid x)\) , \(\sum_yp(y\mid x) = 1\)

然后拿这个通过极大似然估计得到的结果:

\[-(\sum_{x,y}\overline p(x)p_{\lambda}(y\mid x)logZ_{\lambda}(x) - \sum_{i=1}^k\overline p(x,y)\sum_{x,y}\lambda_if_i(x,y))\]

跟之前得到的对偶问题的极大化解:

\[\sum_{x,y}\overline p(x)p_{\lambda}(y\mid x)logZ_{\lambda}(x) - \sum_{i=1}^k\overline p(x,y)\sum_{x,y}\lambda_if_i(x,y)\]

只差一个“-”号,所以只要把原对偶问题的极大化解也加个负号,等价转换为对偶问题的极小化解:

\[-(\sum_{x,y}\overline p(x)p_{\lambda}(y\mid x)logZ_{\lambda}(x) - \sum_{i=1}^k\overline p(x,y)\sum_{x,y}\lambda_if_i(x,y))\]

则与极大似然估计的结果具有完全相同的目标函数。

换言之,之前最大熵模型的对偶问题的极小化等价于最大熵模型的极大似然估计。

且根据MLE的正确性,可以断定:最大熵的解(无偏的对待不确定性)同时是最符合样本数据分布的解,进一步证明了最大熵模型的合理性。两相对比,熵是表示不确定性的度量,似然表示的是与知识的吻合程度,进一步,最大熵模型是对不确定度的无偏分配,最大似然估计则是对知识的无偏理解。

参数求解法:IIS

回顾下之前最大熵模型的解:

\[p^*(y \mid x) = {1 \over Z_{\lambda}(x)}e^{\sum_{i}\lambda_if_i(x,y)}\] 其中

\[Z_{\lambda}(x) = \sum_ye^{\sum_{i}\lambda_if_i(x,y)}\]

对数似然函数为:

\[L_{\overline p}(p) = \sum_{x,y}\overline p(x,y)\sum_{i=1}^n\lambda_if_i(x,y) - \sum_x\overline p(x)logZ_{\lambda}(x)\]

相当于现在的问题转换成:通过极大似然函数求解最大熵模型的参数,即求上述对数似然函数参数λ 的极大值。此时,通常通过迭代算法求解,比如改进的迭代尺度法IIS、梯度下降法、牛顿法或拟牛顿法。这里主要介绍下其中的改进的迭代尺度法IIS。

改进的迭代尺度法IIS的核心思想是:假设最大熵模型当前的参数向量是\(\lambda\),希望找到一个新的参数向量\(\lambda + \delta\),使得当前模型的对数似然函数值L增加。重复这一过程,直至找到对数似然函数的最大值。

下面,咱们来计算下参数\(\lambda\) 变到\(\lambda + \delta\)的过程中,对数似然函数的增加量,用\(L(\lambda + \delta)-L(\lambda)\)表示,同时利用不等式:\(-lnx \ge 1-x , x\gt 0\),可得到对数似然函数增加量的下界,如下: 增量

将上述求得的下界结果记为\(A(\delta \mid \lambda)\),为了进一步降低这个下界,即缩小\(A(\delta \mid \lambda)\)的值,引入一个变量: \[f^\#(x,y) = \sum_if_i(x,y)\] 其中,\(f\)是一个二值函数,故\(f^\#(x, y)\)表示的是所有特征\((x, y)\)出现的次数,然后利用Jason不等式,可得: Jason不等式结果

我们把上述式子求得的\(A(\delta \mid \lambda)\)的下界记为\(B(\delta \mid \lambda)\)

\[B(\delta \mid \lambda) = \sum_{x,y}\overline p(x,y)\sum_{i=1}^n\delta_if_i(x,y) + 1 - \sum_x\overline p(x)\sum_yp_{\lambda}(y\mid x)\sum_{i=1}^n{f_i(x,y) \over f^\#(x,y)}\exp(\delta_if^\#(x,y))\]

相当于\(B(\delta \mid \lambda)\)是对数似然函数增加量的一个新的下界,可记作:\(L(\lambda + \delta)-L(\lambda) \ge B(\delta \mid \lambda)\).

接下来,对\(B(\delta \mid \lambda)\)求偏导,得: 求偏导 此时得到的偏导结果只含\(\delta\),除\(\delta\)之外不再含其它变量,令其为0,可得:

\[\sum_{x,y}\overline p(x)p_{\lambda}(y\mid x)f_i(x,y)\exp(\delta_if^\#(x,y)) = E_{\overline p}(f_i)\]

从而求得\(\delta\),问题得解。

值得一提的是,在求解δ的过程中,如果若\(f^\#(x,y)=M\)为常数,则:

\[\delta_i = {1\over M}log{E_{\overline p}(f_i) \over E_{p}(f_i)} \]

否则,用牛顿法解决:

\[\delta_i^{(k+1)} = \delta_i^{(k)} - {g(\delta_i^{(k)}) \over g^{'}(\delta_i^{(k)})}\]

求得了\(\delta\),便相当于求得权值\(\lambda\),最终将\(\lambda\) 回代到下式中:

\[p^*(y \mid x) = {1 \over Z_{\lambda}(x)}e^{\sum_{i}\lambda_if_i(x,y)}\]

\[Z_{\lambda}(x) = \sum_ye^{\sum_{i}\lambda_if_i(x,y)}\]

热评文章