最大熵模型

0.引言

这部分内容主要是从七月在线的课程上学习到的，算是自己的学习笔记。
在介绍最大熵模型和EM算法之前首先要明确几个熵的概念，然后再来研究什么是最大熵，什么是最大熵模型，什么是EM算法。一开始比较心急，直接去看EM算法，到头来发现一脸懵逼，还是要回来从基础学起。万丈高楼莫非平地起！本篇笔记主要介绍熵、联合熵、条件熵、互信息、相对熵（KL散度）和交叉熵。这里先给出个Venn图，后面会用到，图片来自百度，侵权删。

.1531022543542.png

信息增益在决策树中介绍，最大熵模型之后再来更。

1.各种熵的定义

1.1信息量

为了解释熵，首先要引入“信息量”这个词。直观上理解，信息量可以度量一个事件包含的信息。先给出公式，然后结合例子来理解。
信息量的定义：
h(x_{i})=-log_{2}p(x_{i})=log_{2}\frac{1}{p(x_{i})}
例子：比如有两个事件，狗咬了人与人咬了狗，那很明显狗咬人这件事情概率大，人咬了狗这件事情概率小，所以可以通过公式来分析。log是一个单调递增的凹函数，因此公式中p(x_{i})越大则信息量h(x_{i})越小；p(x_{i})越小则信息量h(x_{i})越大。例子中，狗咬人的信息量就很小，人咬狗的信息量就很大。总而言之信息量与概率成反比，概率越低则信息量越大，概率越大信息量则越小。

1.2熵——由信息量引出

有了信息量的基础，就可以用来解释熵是什么东西。简单的一句话来解释就是 “熵是信息量的期望”，先给出公式：
熵的定义：
H(X)=-\sum_{i=1}^{n}p(x_{i})log_{2}p(x_{i})=\sum_{i=1}^{n}p(x_{i})\frac{1}{p(x_{i})}
可以看到，事件的概率乘上这个时间的信息量再求和，那就是期望的定义。熵能够反映事件的不确定性，不确定性与熵成正比关系。

1.3联合熵

联合熵实际上是表示两个变量或者多个变量熵的并集。给出公式：
多变量X=\{x_1,x_2,...,x_n\}联合熵的定义：
H(x_1,x_2,...,x_n)=-\sum_{i=1}^{n}\sum_{j=1}^{n}...\sum_{k=1}^{n}p(x_{1i},x_{2j},...,x_{nk})log_{2}p(x_{1i},x_{2j},...,x_{nk})

性质1：H(x_1,x_2,...,x_n)\geqslant max\big[H(x_1),H(x_2)...,H(x_n)\big]

性质2：H(x_1,x_2,...,x_n)\leqslant H(x_1)+H(x_2)+...+H(x_n)

1.4条件熵

条件熵可以从引言部分中给出的Venn图中可以直观地理解，由于个人能力有限，无法用通俗的语言来解释。还是用公式来描述其含义比较准确。
条件熵的定义：
H(Y|X)=-\sum_{i=1}^{n}\sum_{j=1}^{n}p(x_i,y_j)log\frac{p(x_i)}{p(x_i,y_j)}
推导一波：
\begin{aligned} H(Y|X) &=\sum_{i=1}^{n}p(x_i)H(Y|X=x_i) \\ &=-\sum_{i=1}^{n}\sum_{j=1}^{n}p(x_i)p(y_j|x_i)logp(y_j|x_i)\\ &=-\sum_{i=1}^{n}\sum_{j=1}^{n}p(x_i,y_j)logp(y_j|x_i) \\ &=-\sum_{i=1}^{n}\sum_{j=1}^{n}p(x_i,y_j)log\frac{p(x_i)}{p(x_i,y_j)} \\ \end{aligned}
条件熵的两种含义：
H(X|Y)=H(X,Y)-H(Y)
H(X|Y)=H(X,Y)-I(X,Y)
第一种含义是说从联合熵H(X,Y)中减去熵H(Y)第二中含义是说熵H(Y)减去互信息I(X,Y). 其中，互信息就是指两个熵的交集，接下来马上介绍互信息。

1.5互信息

互信息的含义可以通过引言部分的Venn图理解一下，实际上就是两个熵的交集。给出公式：
互信息的定义：
I(X,Y)=-\sum_{i=1}^{n}\sum_{j=1}^{n}p(x_i,y_j)log\frac{p(x_i,y_j)}{p(x_i)p(y_j)}
特点：互信息常用于机器学习中的特征选择和特征关联性分析。互信息刻画了两个变量之间的非线性相关性，而概率论中的相关性\rho=\frac{cov(X,Y)}{\sqrt{var(X)}\sqrt{var(Y)}}用来刻画线性相关性

1.6相对熵（KL散度）

KL散度是什么？是用来做什么的？

KL散度用来刻画两个分布之间的差异性，可参考MLPR一书中对贝叶斯的描述。有很多类似的度量两个分布P和Q的方法，如KL(P||Q),\ Wase(P,Q),\ MMD,\ kernel\ hilbert\ distance(P||Q),这里只是mark一下，目前我还没有逐一去研究过，这里仅讨论KL散度。

为什么要用KL散度比较两个分布之间的差异性？

为什么需要用KL散度来比较两个分布之间的差异性呢？在这个问题之前还有问题，什么是两个分布？怎么就来了两个分布？答案是实际的应用问题引出的。机器学习中有时候需要比较两个样本集的差异，按照经验比较差异那就可以用一些范数距离来求解，如用一阶范数\sum||x_i-y_i||或者二阶范数\sum||x_i-y_i||^2直接来计算不久OK了吗？当然，用范数来做有一定的道理，也是可以的，但是有一个先决条件——“两个数据集中的样本能够逐一对应”。如果不满足这个先决条件，那么用范数来度量差异性就是不合理的。实际的应用中，很难保证两个样本集中的样本能够一一对应，因此用范数距离比较差异的方法就不可行了。那么就换一种思路，我用两个样本集的分布来比较差异性，这样就回答了“两个分布怎么来的”这个问题。

再回答标题中的问题，为什么需要用KL散度来比较两个分布之间的差异性呢？答案就很简单了，KL散度只是很多种比较分布差异性的一种，我们这里讨论熵的时候就用到了相对熵，那就是KL散度。条条大路通罗马，KL散度只是其中一种方法。

相对熵的推导

假设有两个分布P和Q，我们需要求他们的相对熵，那么用公式可以表示为
相对熵的定义：
KL(P||Q)=D(P||Q)=\sum_{i=1}^{n}p(x_i)log\frac{p(x_i)}{q(x_i)}
性质1：D(P||Q)\neq D(Q||P)
性质2：随着D(P||Q)的增大，P和Q两个分布的差异会非常明显
推导一波：D(P||Q)=\sum_{i=1}^{n}p(x_i)log\frac{p(x_i)}{q(x_i)}为了方便进一步的推导，我们令y_i=\frac{q(x_i)}{p(x_i)}, 则\frac{1}{y_i}=\frac{p(x_i)}{q(x_i)}; 令f(y_i)=log(y_i)则有
D(P||Q)=\sum_{i=1}^{n}p(x_i)log\frac{1}{y_i}=-\sum_{i=1}^{n}p(x_i)logy_i
由于log函数是一个凹函数，因此根据凹函数的詹森不等式E[f(x)]\leqslant f[EX]，可以对进一步推导:
\begin{aligned}-D(P||Q)\sum_{i=1}^{n}p(x_i)logy_i &\leqslant log\sum_{i=1}^{n}p(x_i)y_i\\ &=log\sum_{i=1}^{n}p(x_i)\frac{q(x_i)}{p(x_i)}\\ &=log\sum_{i=1}^{n}q(x_i)\\ &=log1\\&=0\\ \end{aligned}
其中\sum_{i=1}^{n}q(x_i)=1。通过推导可以发现
D(P||Q)\geqslant 0
证毕！

1.7交叉熵

交叉熵可以用来计算学习模型分布与训练分布之间的差异，交叉熵广泛用于逻辑回归的Sigmoid和Softmax函数中作为损失函数使用。（这句话引自https://www.cnblogs.com/kyrieng/p/8694705.html，感谢大佬的解读）给出公式：
交叉熵的定义
CH(P,Q)=-\sum_{i=1}^{n}p(x_i)logq(x_i)
实际上交叉熵还可以这样理解：
\begin{aligned}CH(P,Q) &=-\sum_{i=1}^{n}p(x_i)logp(x_i)+\sum_{i=1}^{n}p(x_i)logp(x_i)-\sum_{i=1}^{n}p(x_i)logq(x_i)\\ &=-\sum_{i=1}^{n}p(x_i)logp(x_i)+\sum_{i=1}^{n}p(x_i)log\frac{p(x_i)}{q(x_i)}\\ &=H(X)+D(P||Q)\\\end{aligned}
因此，交叉熵可以看做是熵加上KL散度.

1.8信息增益

决策树中介绍（还未更）

1.9最大熵

在介绍最大熵之前，首先来明确一下事件概率的经验值和理论值

事件概率的经验值与理论值

经验值：
假设有这样一个数据集T={(x_,y_1),...(x_n,y_n)}，我们用\hat{p}(x_i,y_i)来表示从包含n个样本的数据集中样本(x_i,y_i)所占的比例。这个\hat{p}(x_i,y_i)就是我们的经验值，实际上也就是我们从数据中训练得到的值。
\hat{p}(x_i,y_i)=\frac{num(x_i,y_i)}{n}
理论值：理论上这个事件的概率应该如何表示呢？实际上这个问题在很早以前就学过了。就是抛硬币的例子，例如抛100次出现30次正面，抛1000次出现400次正面，抛10000次出现4800次正面....抛n\to\infty次的时候出现\frac{n}{2}次正面。因此，最后逼近极限的\frac{n}{2}就是抛硬币例子中概率的理论值。在考虑我们的数据集T={(x_,y_1),...(x_n,y_n)}，在这个例子中事件(x_i,y_i)的理论概率值就是数据集T中的样本无穷多的时候\hat{p}(x_i,y_i)\approx p(x_i,y_i).用公式来描述就是：p(x_i,y_i)=\lim_{n\to\infty}\hat{p}(x_i,y_i)

最大熵原则

通过前面几节对熵的介绍，可以知道熵表示事件的不确定性，熵越大则不确定性越大。如果有A,B,C三件事情，通过已有数据测量发现他们发生的概率都是三分之一。那么问题来了，现在又发生了一个事件，请问到底是是A，B，C其中的哪件事情？要回答这个问题就先来看看最大熵原则是怎么说的
最大熵原则是这样一句话：承认已知数据，对未知数据无偏见。
通过这句话，我们在例子中所承认的就是“A,B,C三件事情，通过已有数据测量发现他们发生的概率都是三分之一”，对未知数据无偏见意思就是，再来一个事件我们主观地认为它可能会是哪个事件。

最大熵如何应用

通过上面的例子可能会有两个问题，最大熵到底有什么用？如何应用最大熵？那么下面的例子来解释这两个问题。
插播一条李航《统计学习方法》中对最大熵原理是这样讲的“最大熵原理认为，学习概率模型时，在所有可能的概率模型中，熵最大的模型是最好的模型”
先回忆条件熵：H(Y|X)=-\sum_{i=1}^{n}\sum_{j=1}^{n}p(x_i,y_j)log(p(y_j|x_i))最大熵怎么用呢？我们可以用最大熵来确定事件的概率，然后通过概率来确定事件的归属类别。通俗地将就是可以通过对数据进行分析后进行参数估计。
用上面的条件熵可以有：
p^{*}(y|x)=argmax\{H(y|x)\}这个式子的意思就是：求解p^{*}(y|x)，使得熵H(y|x)最大。实际上，这个式子就引出了最大熵模型的目标。再定义一个特征函数就构成了最大熵问题的清单。特征函数是什么呢？可以理解为数据的特征对估计结果的映射关系。接下来给出最大熵问题的清单：
\begin{cases} H(y|x)=-\sum_x\sum_y p(x,y)logp(y|x)\\ p^{*}(y|x)=argmax\{H(y|x)\}\\ f_i(x,y)= \begin{cases} 1, &x=x_0,y=y_0\\ 0,&other\ values\\ \end{cases}\\ \end{cases}
st.\begin{cases}\sum_{y}p(y|x)=1\\E(f_i)=\hat{E}(f_i)\end{cases}
接下来，有目标函数，有约束，那就可以用拉格朗日朗日乘子法求解。可以看到，这里又引入了一个经验值\hat{E}(f_i)，它和理想值E(f_i)相等是一个约束条件。用公式来描述：\hat{E}(f_i)=\sum_{i=1}^{n}\sum_{j=1}^{n}\hat{p}(x_i,y_j)f_i(x_i,y_j)=\sum_{i=1}^{n}\sum_{j=1}^{n}\hat{p}(x)p(y|x)f_i(x_i,y_j)
E(f_i)=\sum_{i=1}^{n}\sum_{j=1}^{n}p(x_i,y_j)f_i(x_i,y_j)=\sum_{i=1}^{n}\sum_{j=1}^{n}p(x)p(y|x)f_i(x_i,y_j)
开始构造拉格朗日函数：\begin{aligned}L(p(y|x),\lambda) &=H(y|x)+\sum_{i=1}^{m}\lambda_i[E(f_i)-\hat{E}(f_i)]+\lambda_0(\sum_{j=1}^{n}p(y_j|x)-1)\\ & =\sum_{x}\sum_{y}p(y|x)p(x)log\frac{1}{p(y|x)}+\sum_{i=1}^{m}\lambda_i\sum_x\sum_yf_i(x,y)[p(x,y)-\hat{p}(x,y)]+\lambda_0\big[\sum_{j=1}^{n}p(y_j|x)-1\big]\\ &=\sum_{x}\sum_{y}p(y|x)p(x)log\frac{1}{p(y|x)}+\sum_{i=1}^{m}\lambda_i\sum_x\sum_yf_i(x,y)[\hat{p}(x)p(y|x)-p(x,y)]+\lambda_0\big[\sum_{j=1}^{n}p(y_j|x)-1\big]\\ \end{aligned}
对p(y|x)求偏导：
\frac{\partial L}{\partial p(y|x)}=p(x)\big[log\frac{1}{p(y|x)}-1\big]+\sum_{i=1}\lambda_i\hat{p}(x)f_i(x,y)
令\frac{\partial L}{\partial p(y|x)}=0则可以推导得到：
p^{*}(y|x)=e^{\sum_{i=1}^{n}\lambda_if_i(x,y)-\frac{\lambda_0}{\hat{p}(x)}-1}=e^{\sum_{i=1}^{n}\lambda_if_i(x,y)}e^{-\frac{\lambda_0}{\hat{p}(x)}-1}
令\frac{1}{z}=e^{-\frac{\lambda_0}{\hat{p}(x)}-1}则有：
p^{*}(y|x)=\frac{1}{z}e^{\sum_{i=1}^{n}\lambda_if_i(x,y)}
这样，我们就得到了最终所要估计的概率p^{*}(y|x).