最大熵模型

GitHub
简书
 CSDN

1. 最大熵原理

最大熵模型（Maximum Entropy Model)是通过最大熵原理推导实现,那什么是最大熵原理？

熵是随机变量不确定性大的度量，不确定性越大，熵值越大；若随机变量变为定值，即某个值发生的概率为1，而其它事件都为0，此时熵值为0，均匀分布是熵值最大的分布，也即“最不确定的分布”。

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

$H(P)=-\sum_{x}p(x)logp(x) \tag{1}$

熵满足如下条件:

$0 \leq H(P) \leq log|X|$
其中, $|X|$ 表示 $X$ 的取值，当 $X$ 的分布是均匀分布时，满足左边等号，当 $X$ 是确定事件时，满足左边的等号。

从上面可知，最大熵原理认为该求解的概率模型满足如下条件:

满足事先已约束的条件；
然后在满足这些条件的模型中选择熵最大的模型，即让不确定的信息等可能的发生；

2. 最大熵模型

将最大熵原理应用到分类问题中即得到最大熵模型。假设分类模型的一个条件概率分布 $P(Y|X)$ , $X\in\chi\subseteq R^n$ 表示输入， $X\in\gamma$ 表示输出。这个模型表示给定的输入 $X$ ,以条件概率 $P(Y|X)$ 输出 $Y$ 。

给定一个训练数据集

$T=\{(x_1, y_1), (x_2,y_2)...(x_N, y_N)\}$

学习的目标是用最大熵原理选择最好的模型。

对于给定训练数据集，我们可以确定联合分布 $P(X, Y)$ 的经验分布 $\tilde P(X,Y)$ 和边缘分布 $P(X)$ 的经验分布 $\tilde P(X)$ ,即：

$\tilde P(X=x, Y=x) = \frac{v(X=x, Y=y)}{N} \\ \tilde P(X=x) = \frac{X(X=x)}{N} \tag{2}$

其中， $v(X=x, Y=y)$ 表示训练数据中样本 $(x, y)$ 出现的频数， $V(X=x)$ 表示训练数据集中 $x$ 出现的频数。 $N$ 表示训练样本的总容量。

特征函数 $f(x, y)$ 表示输入 $x$ 和输出 $y$ 之间的某个约束。其定义为:

$f(x,y)=\begin{cases} 1,\quad x和y满足约束\\ 0, \quad x和y不满足约束 \end{cases} \tag{3}$

特征函数 $f(x,y)$ 关于经验分布 $\tilde P(X, Y)$ 的期望值为:

$E_{\tilde p}(f) = \sum_{x, y} \tilde P(x,y)f(x, y) \tag{4}$

特征函数 $f(x,y)$ 关于模型 $P(Y|X)$ 和经验分布 $\tilde P(X)$ 的期望值为:

$E_{p}(f) = \sum_{x, y} \tilde P(x)P(y|x)f(x, y) \tag{5}$

因为机器学习的目的就是从数据集中学得数据中包含的某种内在信息，因此我们可以假设公式4和公式5相等，即

$E_{\tilde p}(f) = E_{p}(f) \\ \sum_{x, y} \tilde P(x,y)f(x, y) = \sum_{x, y} \tilde P(x)P(y|x)f(x, y) \tag{6}$

公式6就作为模型的约束条件，如果有 n 个特征函数，则就有 n 个约束条件。

最大熵模型 假设满足所有约束条件的模型集合为

$C=\{P|E_{\tilde p}(f_i) = E_{p}(f_i), i=1,2...n\}$

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

$H(P) = - \sum_{x,y}\tilde P(x)P(y|x)logP(y|x) \tag{7}$

则模型集合 $C$ 条件熵最大的模型成为最大熵模型

补充

条件概率的熵的公式为
$H(y|x)=-\sum_{x,y}p(x,y)logp(y|x) \tag{8}$

因此最大熵模型如公式7所示。

总之，最大熵模型就是在满足约束的模型集合中选择条件概率分布 $P(Y|X)$ 最大的模型。

3. 最大熵模型的学习

通过上述上述的描述，最大熵模型可以形式化为约束最优化问题，即

$\max_{P \in C} H(P) = -\sum_{x,y}\tilde P(x)P(y|x)\log P(y|x) \\ s.t. \quad E_{\tilde p}(f_i) = E_{p}(f_i), \quad i=1, 2...,n \\ \quad \sum_yP(y|x) = 1 \tag{9}$

按照优化习惯，通常将最大值优化转换为最小值优化。即
$\max_{P \in C} -H(P) = \sum_{x,y}\tilde P(x)P(y|x)\log P(y|x) \\ s.t. \quad E_{\tilde p}(f_i) = E_{p}(f_i), \quad i=1, 2...,n \\ \quad \sum_yP(y|x) = 1 \tag{10}$

公式10所得出的解就是最大熵模型学习的模型。

解决上述约束最优化问题，我们通过拉格朗日对偶性来进行解决。

首先我们引入拉格朗日乘子 $w_0, w_1,w_2...w_n$ ,定义拉格朗日函数 $L(p, w)$ 为
$\begin{aligned} L(P, w) &=-H(P) + w_0(1-\sum_yP(y|x))+\sum_{i=1}^{n}w_i(E_{\tilde p}(f_i) - E_{p}(f_i)) \\ &=\sum_{x,y}\tilde P(x)P(y|x)\log P(y|x) + w_0(1-\sum_yP(y|x)) \\ &+\sum_{i=1}^{n}w_i(\sum_{x,y}\tilde P(x,y)f(x, y) - \sum_{x, y} \tilde P(x)P(y|x)f(x, y)) \end{aligned} \tag{11}$

因此，最优化问题的原始问题为
$\min_{P\in C} \max_{w} L(P,w) \tag{12}$
对偶问题

$\max_{w} \min_{P\in C} L(P,w) \tag{13}$

我们称公式10、11和12为原始问题，公式13为原始问题的对偶问题，且原始问题的解与对偶问题的解是等价的，因此，公式11的解就是我们求解的模型。

我们首先求解对偶问题公式13内部的极小化问题 $\min_{P\in C} L(P,w)$ ,该函数是关于 $w$ 的函数，我们将其记作:

$\psi (w) = \min_{P\in C} L(P,w) = L(P_w, w) \tag{14}$

$\psi (w)$ 称为对偶函数，同时其解记为:

$P_w = \arg \min_{p}L(P,w) = P_w(y|x) \tag{15}$

我们可以利用偏导数来求解公式15，即

$\begin{aligned} \frac{\partial L(P,w)}{\partial P(y|x)} &= \sum_{x,y}(\tilde P(x) \log P(y|x) + \tilde{P}(x)) -\sum_{y}w_o+\sum_{i=1}^{n}w_i(-\sum_{x,y}\tilde{P}(x)f_{i}(x,y)) \\ &= \sum_{x,y}\tilde{P}(x)(\log P(y|x) + 1) - \sum_{y}w_0-\sum_{x,y}{\tilde{P}(x)\sum_{i=1}^nw_if_i(x,y)} \\ &=\sum_{x,y}\tilde{P}(x)(\log P(y|x) + 1) - \sum_x \tilde{P}(x)\sum_{y}w_0-\sum_{x,y}{\tilde{P}(x)\sum_{i=1}^nw_if_i(x,y)} \\ &= \sum_{x,y}\tilde{P}(x)(\log P(y|x) + 1-w_0-\sum_{i=1}^nw_if_i(x,y)) \end{aligned} \tag{16}$

由于 $L(P,w)$ 是凸函数，我们我可令上式偏导数为0，在 $\tilde P(x)>0$ 的情况下，即可求出 $P(y|x)$ , 即：
$\begin{aligned} P(y|x) &=\exp(\sum_{i=1}^{n}w_if_i(x,y)+w_0-1)\\ &=\frac{\exp{\sum_{i=1}^{n}w_if_i(x,y)}}{\exp(1-w_0)} \end{aligned} \tag{17}$

由于在概率论中， $\sum_{y}P(y|x)=1$ ,因此需对公式17进行归一化，又 $\exp(1-w_0)$ 为常数,因此：

$P_w(y|x)=\frac{1}{Z_w(x)}\exp(\sum_{i=1}^{n}w_if_i(x,y)) \tag{18}$

其中

$Z_w(x)=\sum_{y}\exp(\sum_{i=1}^nw_if_i(x,y)) \tag{19}$

公式18、19表示的模型就是最大熵模型 $P_w=p_w(y|x)$ .然后求解对偶函数的极大化问题
$\max_{w} \psi (w) \tag{20}$

求得 $w^*$ ,得到最终模型。

4 极大似然估计

通过上面一小节的计算，我们已经求出最大熵模型，但是此时该模型还是一个关于 $w$ 的函数，我们如何求出 $w$ 来求得最终的模型呢。

我们先来描述对数似然函数，通过前面一章的逻辑回归模型中的最大似然估计，我们可知对数似然函数和熵在值上互为相反数，又通过公式8得知条件概率的熵形式，因此我们可以得知，条件概率分布 $P(Y|X)$ 的对数似然函数

$L_{\tilde P}(P_w) = \sum_{x,y}\tilde{P}(x,y)\log P(y|x) \tag{21}$

我们再冲似然函数的定义方面证明上述公司的正确性。

在给定数据集 $\{(x_1,y_1),(x_2,y_2)...(x_n,y_n)\}$ ,我们可求得当前模型的似然函数为:

$L(\theta)=\prod_{i=1}^n P(x_i, \theta) \tag{22}$

我们假设 $X_i$ 在训练集中出现了 $C(x_i)$ ,因此公式22可以转化为:

$L(\theta)=\prod_{i=1}^k P(x_i, \theta)^{C(x_i)} \tag{23}$

$k$ 表示训练数据集中总共有 k 种不同的输入特征，我们对上市求其 $\frac{1}{n}$ 次方，得：

$L(\theta)^{\frac{1}{n}}=\prod_{i=1}^k P(x_i, \theta)^{\frac{C(x_i)}{n}} \tag{24}$

对公式24求对数的:

$\begin{aligned} \log L(\theta)^{\frac{1}{n}} &=\log \prod_{i=1}^k P(x_i, \theta)^{\frac{C(x_i)}{n}} \\ &= \sum_{i=1}^k \frac{C(x_i)}{n} \log P(x_i, \theta)\\ \end{aligned} \tag{25}$

因此对于 $\log L(\theta)^{\frac{1}{n}}$ 和 $\log L(\theta)$ 是等价的，

因此对于条件概率分布 $P(Y|X)$ 的对数似然函数

$L_{\tilde P}(P_w) = \sum_{x,y}\tilde{P}(x,y)\log P(y|x) \tag{26}$

对于公式21-26的推导，不具有严格的树学理论，只是为了理解下面公式27做铺垫。

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

$\begin{aligned} L_{\tilde P}(P_w) &=\log \prod_{xy}P(y|x)^{\tilde P(x,y)} = \sum_{x,y}\tilde{P}(x,y)\log P(y|x) \end{aligned} \tag{27}$

将公式18和19带入公式27可得:
$\begin{aligned} L_{\tilde P}(P_w) &=\sum_{x,y}\tilde{P}(x,y)(\sum_{i=1}^{n}w_if_i(x,y)-\log Z_w(x) \\ &=\sum_{x,y}\tilde{P}(x,y)\sum_{i=1}^{n}w_if_i(x,y)-\sum_{x,y}\tilde{P}(x,y)\log Z_w(x) \\ &=\sum_{x,y}\tilde{P}(x,y)\sum_{i=1}^{n}w_if_i(x,y)-\sum_{x}\tilde {P}(x)\log Z_w(x) \end{aligned} \tag{28}$

公式28就是极大似然函数。上式最后两步最后一项的转化是因为 $Z_w(x)$ 是关于 x 的函数，所以可以对 $\tilde{P}(x,y)$ 对 $x$ 进行累加得到 $\tilde {P}(x)$ .

我们再看看对偶函数 $\psi (w)$ ,我们将 $P_w(y|x)$ 带入公式11得:

$\begin{aligned} \psi (w) =& \sum_{x,y}\tilde P(x)P_w(y|x)\log P_w(y|x) + w_0(1-\sum_yP(y|x)) \\ &+\sum_{i=1}^{n}w_i(\sum_{x,y}\tilde P(x,y)f(x, y) - \sum_{x, y} \tilde P(x)P_w(y|x)f(x, y)) \\ =&\sum_{x,y}\tilde P(x)P_w(y|x)\log P_w(y|x) \\ &+\sum_{i=1}^{n}w_i(\sum_{x,y}\tilde P(x,y)f(x, y) - \sum_{x, y} \tilde P(x)P_w(y|x)f(x, y)) \\ =& \sum_{x,y}\tilde P(x,y)\sum_{i=1}^{n}w_if(x, y)+\sum_{x,y}\tilde{P}(x)P_w(y|x)(\log P_w(y|x)-\sum_{i=1}^{n}w_if_i{(x,y)}) \\ =& \sum_{x,y}\tilde P(x,y)\sum_{i=1}^{n}w_if(x, y)-\sum_{x,y}\tilde{P}(x)P_w(y|x)\log Z_w(x) \\ =& \sum_{x,y}\tilde P(x,y)\sum_{i=1}^{n}w_if(x, y)-\sum_{x,y}\tilde{P}(x)\log Z_w(x) \end{aligned} \tag{29}$

公式29第三步到第四步用到下面公式进行推导:

$P_w(y|x)=\frac{1}{Z_w(x)}\exp(\sum_{i=1}^{n}w_if_i(x,y)) \Rightarrow \log P_w(y|x)=\sum_{i=1}^{n}w_if_i(x,y)-\log Z_w(x)$

倒数第二步到最后一步的推导用到了 $\sum_{y}P(y|x)=1$ .

比较公式公式28和公式29，可得:

$\psi (w) = L_{\tilde P}(P_w)$

因此，可以证明，最大熵模型学习中的对偶函数极大化等价于最大熵模型的极大似然估计。

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 205,033评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 87,725评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,473评论 0赞 338
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,846评论 1赞 277
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,848评论 5赞 368
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,691评论 1赞 282
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,053评论 3赞 399
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,700评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 42,856评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,676评论 2赞 323
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,787评论 1赞 333
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,430评论 4赞 321
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,034评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,990评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,218评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,174评论 2赞 352
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,526评论 2赞 343

最大熵模型

1. 最大熵原理

2. 最大熵模型

3. 最大熵模型的学习

4 极大似然估计

推荐阅读更多精彩内容