最大熵模型

最大熵模型($The Maximum Entropy$,从信息论的角度来讲,就是保留了最大的不确定性,也就是让熵达到最大。当我们需要对一个时间的概率分布进行预测是,最大熵原理告诉我们所有的预测应当满足全部已知的条件,而对未知的情况不要做任何主观假设(不做主观假设这点很重要)。也就是让概率分布最均匀,预测风险最小。

数学知识

熵($Entropy$)是热力学中的概念,由香农引入到信息论中。在信息论和概率统计中,熵用来表示随机变量不确定性的度量。

定义:设$X\in\{x_1,x_2,x_3…,x_n\}$为一个离散随机变量,其概率分布为$p(X=x_i)=p_i, i=1,2,…,n$,则$X$的熵为

其中,当$p_i=0$时,定义$0\log 0=0.$

注意:$H(x)$依赖于$X$的分布,而与$X$的具体值无关。$H(x)$越大,表示$X$的不确定性越大。

条件熵

定义:设$X\in\{x_1,x_2,x_3…,x_n\}, Y\in \{y_1,y_2,…,y_m\}$为离散随机变量,在已知$X$的条件下,$Y$的条件熵$(Conditional Entropy)$可定义为

它表示已知$X$的条件下,$Y$的条件概率分布的熵对$X$的数学期望。

最大熵原理

最大熵原理是概率模型学习的一个准则,最大熵原理认为,学习概率模型时在所有可能的概率模型(分布)中,熵最大的模型是最好的模型。通常用约束条件来确定概率模型集合,所以,最大熵原理也可以表述为在满足约束条件的模型集合中选取熵最大的模型

假设离散随机变量$X$的概率分布是$P(X)$,则其熵是

熵满足下列不等式:

式中,$|X|$是$X$的取值个数,当且仅当$X$的分布式均匀分布时右边的等号成立。这就是说,当$X$服从均匀分布时候,熵最大

最大熵原理认为要选择的概率模型首先必须满足已有的事实,即约束条件。在没有更多信息条件下,那些不确定的成分是‘等可能的’。最大熵原理通过熵最大化来表示等可能性。‘等可能性’不易操作,而熵则是可优化的数值指标

最大熵模型定义

前提

1.最大熵原理是统计学习的一般原理,将它应用到分类就得到了最大熵模型

2.假设分类模型是一个条件概率分布$P(Y|X),$$X$表示输入,$Y$表示输出。这个模型表示的是对于给定的输入$X$,一条件概率$P(Y|X)$输出$Y$。

3.给定一个训练数据集$T$,我们的目标就是利用最大熵原理选择最好的分类模型。

4.按照最大熵原理,我们应该优先保证模型满足一致的所有约束。那么如何得到这些约束的?

$ $思路:从训练数据$T$中抽取若干特征(依靠特征函数),然后要求这些特征在$T$上关于经验分布的期望与他们在模型中关于$p(x,y)$的数学期望相等,这样,一个特征就对应一个约束

特征函数

特征函数的作用

1.用特征函数$f(x)$描述输入$x$和输出$y$之间的某一个事实。

2.按照最大熵原理,应该优先保证模型满足一致的所有约束。通过特征函数来定义、量化以及得到这些约束

3.特征函数的出现,可以让模型有更好的泛化能力(特征函数的选取、定义特别随意)。

特征函数可以类比决策树对于输入$x$的处理,假设输入$x$是一个有着多个属性值的实例,决策树在一个决策点并不是对所有属性都进行考虑,这就有点提取出了特征中更有信息量的属性。

如何让一个线性模型(例如$LR:h_{\theta}(x)=\sigma (\theta^Tx)$ )也有类似的功能?答案就是特征函数,让输入$X$先经过一些列特征函数的处理,变成$g(x)$再送给模型分类(如:$h_{\theta}(x)=\sigma (\theta^Tg(x))$).

此外,当输入的样本可能不是数值的向量,比如文本或图片时,特征函数的功能更像是特征向量的制作。对于给定输入$X$,使用一系列定义好的特征函数$\{g(x)\}$将其转换成需要的向量形式。

对于特征函数中‘特征’的理解

一般说的“特征”都是指输入的特征,而最大熵模型中的“特征”指的是输入和输出共同的特征。最大熵模型中的每个特征会有一个权重,你可以把它理解成这个特征所描述的输入和输出有多么倾向于同时出现。

可以以多类logistic regression为例,来感受一下两种视角的不同。在一般的视角下,每条输入数据会被表示成一个n维向量,可以看成n个特征。而模型中每一类都有n个权重,与n个特征相乘后求和再经过softmax的结果,代表这条输入数据被分到这一类的概率。在最大熵模型的视角下,每条输入的n个“特征”与k个类别共同组成了nk个特征,模型中有nk个权重,与特征一一对应。每个类别会触发nk个特征中的n个,这n个特征中的每个特征都会触发特征函数

经验分布

经验分布是指通过训练数据$T$进行统计得到的分布。我们需要考察两个经验分布,分别是$x,y$的联合经验分布,以及$x$的经验分布。其定义如下:

对于任意特征函数$f$,记$E_{\hat p}(f)$表示$f$在训练数据$T$上关于$\hat p(x,y)$的数学期望。$E_p(f)$表示$f$在模型上关于$p(x,y)$的数学期望,由于模型中$p(x,y)$是未知的,并且我们建模的目标是$p(y|x)$,因此我们利用$Bayes$定理得到$p(x,y)=p(x)p(y|x)$,此时,$p(x)$还是未知的,我们可以使用经验分布$\hat p(x)$对$p(x)$进行近似。按照期望的定义有:

对于概率分布$p(y|x)$我们希望特征$f$的期望应该和从训练数据中的到的一样的。(我的理解:特征函数是约束的提取量化,特征函数关于经验分布的期望与关于模型的期望相等就代表一个约束)因此我们可以提出约束:

假设从训练数据中抽取了n个特征,相应的便有n个特征函数以及n各约束条件。

最大熵模型

给定数据集$T$,我们的目标就是根据最大上原理选择一个最优分类器,假设满足所有约束条件的模型集合为:

定义在条件概率分布$P(Y|X)$上的条件熵为:

则模型集合$C$中条件熵$H(P)$最大的模型成为最大熵模型。式中的对数为自然对数

最大熵模型的学习

最大熵模型的学习可以形式化为约束最优化问题。对于给定训练数据集$T=\{(x_1,y_1),(x_2,y_2),…,(x_n,y_n)\}$以及特征函数$f_i(x,y), i=1,2,3,…,n$,最大熵模型的学习等价于约束最优化问题(注意自变量为$P$):

按照最优化习惯,将求最大值问题改写为等价的求最小值问题:

引入拉格朗日乘子$w_0,w_1,w_2,…,w_n$,定义拉格朗日函数$L(P,w)$(这里注意两自变量):

又:

带入得到$L(P,w)$:

对偶最优化的原始问题是(再次注意$min,max$的自变量是什么):

对偶问题是

由于拉格朗日函数$L(P,w)$是$P$的凸函数,原始问题的解与对偶问题的解是等价的。这样,可以通过求解对偶问题来求解原始问题

注:以上的推理解释可在另一篇拉格朗日文章中找到

首先,求解对偶问题内部的极小化问题$\min_{p\in C}L(P,w)$。$\min_{p\in C}L(P,w)$是关于$w$的函数(因为$\min_{p\in C}L(P,w)$代表$P$已经确定了),将其记作:

注:上式的最后一项$L(P_w,w)$是归于$w$的函数,因为此时$P_w=\arg min_{P\in C}L(P,w)=P_w(y|x)$

$\Psi(x)$成为对偶函数,其解为$P_w$。

具体地,求$L(P,w)$对$P(y|x)$的偏导数(这里直接插入图片了手写这一段$mathjax$太累,将图片中$\lambda$换成$w$就行)注意蓝色字部分

另偏导数等于0,在$\hat P(x)>0$的情况下,解得:

由于$\sum_y P(y|x)=1$,得(关于$w$的函数):

其中,

$Z_w(x)$成为规范化因子;$f_i(x,y)$是特征函数;$w_i$是特征的权值。表示的模型$P_w=P_w(y|x)$就是最大熵模型。这里$w$是最大熵模型中的参数向量。

得到对偶问题内部的极小问题的解$P_w(y|x)$后,需要进一步求解外层的极大值问题。

将其解记为$w^¥$,即:

令$\sum_{x,y}\hat P(x,y)f_i(x,y) = \tau_i$

$ \Psi (x)$

$=L(P_w,w) 注意这里P_w为定量是之前内部极小问题的解$

$=\sum_{x,y}\hat P(x)P_w(y|x)\log P_w(y|x)+\sum^n_{i=1}w_i( \tau_i-\sum_{x,y}\hat P(x)P_w(y|x)f_i(x,y) )$

$=\sum^n_{i=1}w_i\tau_i+\sum_{x,y}\hat P(x)P_w(y|x)( \log p_w(y|x)-\sum^n_{i=1}w_if_i(s,y) )$

又:$\log P_w(y|x)=\sum^n_{i=1}w_if_i(x,y)-\log Z_w(x)$

将上式带入到$\Psi$中,可以得到

$\Psi(w)$

$=\sum^n_{i=1}w_i\tau_i-\sum_{x,y}\hat P(x)P_w(y|x)\log Z_w(x)$

$=\sum^n_{i=1}w_i\tau_i-\sum_{x}\hat P(x)\log Z_w(x)\sum_y P_w(y|x)$

$=\sum^n_{i=1}w_i\tau_i-\sum_{x}\hat P(x)\log Z_w(x) (这里利用了\sum_yP_w(y|x)=1 )$

极大似然模型

下面证明对偶函数的极大化等价于最大熵模型的极大似然估计。

注:极大似然估计$MLE$的一般形式表示为(推导下一小节给出):

一直训练数据的经验概率分布$\hat P(x,y)$,条件概率分布$P(Y|X)$的对数似然表示为:

当条件概率分布$P(y|x)$是最大熵模型的内部极小函数的解释,对数似然函数$L_{\hat P}(P_w)$

为:

注:最后一步由$\sum_{x,y}\hat p(x,y)=\sum_x\hat p(x)\sum_yp(y|x)$且$\sum_yp(y|x)=1$得来

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

转载自CSDN

最近在学习最大熵模型,看到极大似然估计这部分,没有看明白条件概率分布$p(y|x)$的对数似然函数。上网查了很多资料都没有一个合理的解释。基本直接给出对数似然函数的一般形式 ($\hat p(x)$为经验概率,即:训练样本中x出现的概率,注意:这里$\Pi$下标是$x$的种类):

其实第一眼之所以不理解,因为这是最大似然函数的另外一种形式。一般书上描述的最大似然函数的一般形式是各个样本集XX中各个样本的联合概率:

其实这个公式和上式是等价的。$x_1,x_2,…,x_n$是样本具体观测值。随机变量$X$是离散的,所以它的取值范围是一个集合,假设样本集的大小为$n$,$X$的取值有$k$个,分别是$v_1,v_2,…,v_k$。用$C(X=v_i)$表示在观测值中样本$v_i$出现的频率。所以$L(x_1,x_2,…,x_n;θ)$可以表示为:

对等式两边同时开$n$次方得:

因为经验概率$\hat p(x)={C(X=v_i)\over n}$,所以简写可以得到

很明显对$L(x_1,x_2,…,x_n;θ)​$求最大值和对$L(x_1,x_2,…,x_n;θ)^{1\over n}​$求最大值的优化的结果是一样的。整理上式所以最终的最大似然函数可以表示为:

从最大熵模型角度理解LR

LR是最大熵模型在类别为2时候的特例

假设每条输入第$i$个特征对第$k$类的贡献是$w_{ki}$,则数据点$(x_1,x_2,…,x_n)$属于第$k$类的概率正比于$exp(w_{k1}x_1+w_{k2}x_2+…+w_{kn}x_n)$。

根据最大熵模型:

现在回到两类的情况$\{0,1\}$,此时分母上有两项:

分子、分母同时除以分子,则有:

这就变成了$logistic$函数。

0%