机器学习之各种熵的总结

一、什么是熵

物理学上，熵 Entropy 是“混乱” 程度的量度。
系统越有序，熵值越低；系统越混乱或者分散，熵值越高
信息理论：
1、当系统的有序状态一致时，数据越集中的地方熵值越小，数据越分散的地方熵值越大。这是从信息的完整性上进行的描述。
2、当数据量一致时，系统越有序，熵值越低；系统越混乱或者分散，熵值越高。这是从信息的有序性上进行的描述。

假如事件A的分类划分是（A1,A2,…,An），每部分发生的概率是(p1,p2,…,pn)，那信息熵定义为公式如下：

E n t (A) = - \sum_{k = 1}^{n} p_{k} l o g_{2} p_{k}

二分法：
如果有32个球队，准确的信息量应该是：
H = -（p1 * logp1 + p2 * logp2 + … + p32 * logp32），其中 p1, …, p32 分
别是这 32 支球队夺冠的概率。当每支球队夺冠概率相等都是 1/32 的时：H = -（32 * 1/32 * log1/32） = 5 每个事件概率相同时，熵最大，这件事越不确定。

二、联合熵

联合熵是一集变量之间不确定的衡量手段。
二维随机变量XY的联合熵(joint entropy)定义为联合自信息的数学期望，它是二维随机变量XY的不确定性的度量

H (X, Y) = \sum \sum - p (x, y) \log (p (x, y))

特性：
1）大于子系统的熵
H(X,Y)≥H(X)
增加一个新系统不减少不确定性。

2）子可加性 (Subadditivity)
H(X,Y)≤H(X)+H(Y)

3）非负性（Bounds）
H(X,Y)≥0

三、条件熵

条件熵 H(Y|X) 表示在已知随机变量 X 的条件下随机变量 Y 的不确定性。条件熵 H(Y|X) 定义为 X 给定条件下 Y 的条件概率分布的熵对 X 的数学期望：
机器学习之各种熵的总结
条件熵 H(Y|X) 相当于联合熵 H(X,Y) 减去单独的熵 H(X)，
即H(Y|X)=H(X,Y)−H(X)，证明如下：

举个例子，比如环境温度是低还是高，和我穿短袖还是外套这两个事件可以组成联合概率分布 H(X,Y)，因为两个事件加起来的信息量肯定是大于单一事件的信息量的。假设 H(X) 对应着今天环境温度的信息量，由于今天环境温度和今天我穿什么衣服这两个事件并不是独立分布的，所以在已知今天环境温度的情况下，我穿什么衣服的信息量或者说不确定性是被减少了。当已知 H(X) 这个信息量的时候，H(X,Y) 剩下的信息量就是条件熵
H(Y|X) =H(X,Y)-H(X)
因此，可以这样理解，描述 X 和 Y 所需的信息是描述 X 自己所需的信息,加上给定 X 的条件下具体化 Y 所需的额外信息。关于条件熵的例子可以看这篇文章，讲得很详细。https://zhuanlan.zhihu.com/p/26551798

四、相对熵 (Relative entropy)，也称KL散度 (Kullback–Leibler divergence)

设 p(x)、q(x) 是离散随机变量 X 中取值的两个概率分布，则 p 对 q 的相对熵是：

D_{K L} (p | | q) = \sum_{x} p (x) l o g \frac{p (x)}{q (x)} = E_{p (x)} l o g \frac{p (x)}{q (x)}

性质：
1、如果 p(x) 和 q(x) 两个分布相同，那么相对熵等于0
2、DKL(p||q)≠DKL(q||p) ，相对熵具有不对称性。大家可以举个简单例子算一下。
3、DKL(p||q)≥0 证明如下（利用Jensen不等式
机器学习之各种熵的总结

因为：

\sum_{x} p (x) = 1

所以：

D_{K L} (p | | q) \geq 0

总结：相对熵可以用来衡量两个概率分布之间的差异，上面公式的意义就是求 p 与 q 之间的对数差在 p 上的期望值。

五、交叉熵 (Cross entropy)

现在有关于样本集的两个概率分布 p(x) 和 q(x)，其中 p(x) 为真实分布， q(x) 非真实分布。如果用真实分布 p(x) 来衡量识别别一个样本所需要编码长度的期望（平均编码长度）为:
$H (p) = \sum_{x} p (x) l o g \frac{1}{p (x)}$
如果使用非真实分布 q(x) 来表示来自真实分布 p(x) 的平均编码长度，则是：
$H (p, q) = \sum_{x} p (x) l o g \frac{1}{q (x)}$ 。（因为用 q(x) 来编码的样本来自于分布 q(x) ，所以 H(p,q) 中的概率是 p(x)）。此时就将 H(p,q) 称之为交叉熵。举个例子。考虑一个随机变量 x，真实分布 $p (x) = (\frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{8})$ ，非真实分布 $q (x) = (\frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{4})$ ，则 $H (p) = 1.75 b i t s$ （最短平均码长），交叉熵 $H (p, q) = \frac{1}{2} l o g_{2} 4 + \frac{1}{4} l o g_{2} 4 + \frac{1}{8} l o g_{2} 4 + \frac{1}{8} l o g_{2} 4 = 2 b i t s$ 。由此可以看出根据非真实分布 q(x) 得到的平均码长大于根据真实分布 p(x) 得到的平均码长。
我们再化简一下相对熵的公式。
$D_{K L} (p | | q) = \sum_{x} p (x) l o g \frac{p (x)}{q (x)} = \sum_{x} p (x) l o g p (x) - p (x) l o g q (x)$
有没有发现什么？
熵的公式 $H (p) = - \sum_{x} p (x) l o g p (x)$
交叉熵的公式 $H (p, q) = \sum_{x} p (x) l o g \frac{1}{q (x)} = - \sum_{x} p (x) l o g q (x)$
所以有：
$D_{K L} (p | | q) = H (p, q) - H (p)$ 当用非真实分布 q(x) 得到的平均码长比真实分布 p(x) 得到的平均码长多出的比特数就是相对熵）
又因为 $D_{K L} (p | | q) \geq 0$
所以 H(p,q)≥H(p)（当 p(x)=q(x) 时取等号，此时交叉熵等于信息熵）

并且当 H(p) 为常量时（注：在机器学习中，训练数据分布是固定的），最小化相对熵 DKL(p||q) 等价于最小化交叉熵 H(p,q) 也等价于最大化似然估计（具体参考Deep Learning 5.5）。

六、最大熵模型 Maximum Entropy Model

熵的概念在统计学习与机器学习中真是很重要，熵的介绍在这里：信息熵 Information Theory 。今天的主题是最大熵模型（Maximum Entropy Model，以下简称MaxEnt），MaxEnt 是概率模型学习中一个准则，其思想为：在学习概率模型时，所有可能的模型中熵最大的模型是最好的模型；若概率模型需要满足一些约束，则最大熵原理就是在满足已知约束的条件集合中选择熵最大模型。最大熵原理指出，对一个随机事件的概率分布进行预测时，预测应当满足全部已知的约束，而对未知的情况不要做任何主观假设。在这种情况下，概率分布最均匀，预测的风险最小，因此得到的概率分布的熵是最大。

直观理解 MaxEnt

在求解概率模型时，当没有任何约束条件则只需找到熵最大的模型，比如预测一个骰子的点数，每个面为 16，是，当模型有一些约束条件之后，首先要满足这些约束条件，然后在满足约束的集合中寻找熵最大的模型，该模型对未知的情况不做任何假设，未知情况的分布是最均匀的。举例来说对于随机变量 X ，其可能的取值为 {A,B,C} ，没有任何约束的情况下下，各个值等概率得到的 MaxEnt 模型为：

P (A) = P (B) = P (C) = \frac{1}{3}

当给定一个约束 P(A)=12 , 满足该约束条件下的 MaxEnt 模型是：

P (A) = \frac{1}{2}

P (B) = P (C) = \frac{1}{4}

如果用欧式空间中的 simplex 来表示随机变量 X 的话，则 simplex 中三个顶点分别代表随机变量 X 的三个取值 A, B, C , 这里定义 simplex 中任意一点 p 到三条边的距离之和（恒等于三角形的高）为 1，点到其所对的边为该取值的概率，比如任给一点 p ，则P(A) 等于 p 到边 BC 的距离，如果给定如下概率：

P (A) = 1, P (B) = P (C) = 0

P (A) = P (B) = P (C) = \frac{1}{3}

分别用下图表示以上两种情况：
机器学习之各种熵的总结

明白了 simplex 的定义之后，将其与概率模型联系起来，在 simplex 中，不加任何约束，整个概率空间的取值可以是 simplex 中的任意一点，只需找到满足最大熵条件的的即可；当引入一个约束条件

C_{1}

后，如下图中 (b),模型被限制在

C_{1}

表示的直线上，则应在满足约束

C_{1}

的条件下来找到熵最大的模型；当继续引入条件

C_{2}

后，如图(c)，模型被限制在一点上，即此时有唯一的解；当

C_{1}

与

C_{2}

不一致时，如图(d)，此时模型无法满足约束，即无解。在 MaxEnt 模型中，由于约束从训练数据中取得，所以不会出现不一致。即不会出现(d) 的情况。
机器学习之各种熵的总结

接下来以统计建模的形式来描述 MaxEnt 模型，给定训练数据

{(x_{i}, y_{i})}_{i = 1}^{N}

，现在要通过Maximum Entrop 来建立一个概率判别模型，该模型的任务是对于给定的 X=x 以条件概率分布 P(Y|X=x) 预测 Y 的取值。根据训练语料能得出 (X,Y) 的经验分布，得出部分 (X,Y) 的概率值，或某些概率需要满足的条件,即问题变成求部分信息下的最大熵或满足一定约束的最优解，约束条件是靠特征函数来引入的，首先先回忆一下函数期望的概念
对于随机变量

X = x_{i}, i = 1, 2, \dots

则可以得到：
随机变量期望: 对于随机变量 X ，其数学期望的形式为

E (X) = \sum_{i} x_{i} p_{i}

随机变量函数期望：若 Y=f(X) ，则关于 X 的函数 Y 的期望：

E (Y) = \sum_{i} f (x_{i}) p_{i}

特征函数

特征函数 f(x,y) 描述 x 与 y 之间的某一事实，其定义如下：

f (x, y) = {\begin{aligned} 1, & 当 x 、 y 满 足 某 一 事 实 . \\ 0, & 不 满 足 该 事 实 . \end{aligned}

特征函数 f(x,y) 是一个二值函数，当 x 与 y 满足事实时取值为 1 ，否则取值为 0 。比如对于如下数据集：
机器学习之各种熵的总结

数据集中，第一列为 Y ，右边为 X ，可以为该数据集写出一些特征函数，数据集中得特征函数形式如下：

f (x, y) = {\begin{aligned} 1, & i f x = C l o u d y a n d y = O u t d o o r . \\ 0, & e l s e . \end{aligned}

为每个

< f e a t u r e, l a b e l >

对都做一个如上的特征函数，用来描述数据集数学化。
约束条件

接下来看经验分布，现在把训练数据当做由随机变量 (X,Y) 产生,则可以根据训练数据确定联合分布的经验分布 P˜(X,Y) 与边缘分布的经验分布 P˜(X) :

\begin{aligned} \tilde{P} (X = x, Y = y) & = \frac{c o u n t (X = x, Y = y)}{N} \\ \tilde{P} (X = x) & = \frac{c o u n t (X = x)}{N} \end{aligned}

用 EP˜(f) 表示特征函数 f(x,y) 关于经验分布 P˜(X,Y) 的期望，可得：

E_{\tilde{P}} (f) = \sum_{x, y} \tilde{P} (x, y) f (x, y) = \frac{1}{N} \sum_{x, y} f (x, y)

P˜(x,y) 前面已经得到了，数数 f(x,y) 的次数就可以了，由于特征函数是对建立概率模型有益的特征，所以应该让 MaxEnt 模型来满足这一约束，所以模型 P(Y|X) 关于函数 f 的期望应该等于经验分布关于 f 的期望，模型 P(Y|X) 关于 f 的期望为：

E_{P} (f) = \sum_{x, y} P (x, y) f (x, y) \approx \sum_{x, y} \tilde{P} (x) P (y | x) f (x, y)

经验分布与特征函数结合便能代表概率模型需要满足的约束，只需使得两个期望项相等，即

E_{P} (f) = E_{\tilde{P}} (f)

：

\sum_{x, y} \tilde{P} (x) p (y | x) f (x, y) = \sum_{x, y} \tilde{P} (x, y) f (x, y)

上式便为 MaxEnt 中需要满足的约束，给定 n 个特征函数 fi(x,y) ，则有 n 个约束条件，用 C 表示满足约束的模型集合：

C = {P | E_{P} (f_{i}) = E_{\tilde{P}} (f_{i}), I = 1, 2, \dots, n}

从满足约束的模型集合 C 中找到使得 P(Y|X) 的熵最大的即为 MaxEnt 模型了。
最大熵模型

关于条件分布 P(Y|X) 的熵为：

H (P) = - \sum_{x, y} P (y, x) l o g P (y | x) = - \sum_{x, y} \tilde{P} (x) P (y | x) l o g P (y | x)

首先满足约束条件然后使得该熵最大即可，MaxEnt 模型 P∗ 为：

P^{*} = a r g max_{P \in C} H (P) 或 P^{*} = a r g min_{P \in C} - H (P)

综上给出形式化的最大熵模型：
给定数据集

{(x_{i}, y_{i})}_{i = 1}^{N}

，特征函数 fi(x,y)，i=1,2…,n ，根据经验分布得到满足约束集的模型集合 C ：

\begin{aligned} min_{P \in C} \sum_{x, y} \tilde{P} (x) P (y | x) l o g P (y | x) \\ s . t . E_{p} (f_{i}) = E_{\tilde{P}} (f_{i}) \\ \sum_{y} P (y | x) = 1 \end{aligned}

MaxEnt 模型的求解

MaxEnt 模型最后被形式化为带有约束条件的最优化问题，可以通过拉格朗日乘子法将其转为无约束优化的问题，引入拉格朗日乘子：

w0,w1,…,wn，定义朗格朗日函数 L(P,w):

\begin{aligned} L (P, w) & = - H (P) + w_{0} (1 - \sum_{y} P (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) l o g P (y | x) + w_{0} (1 - \sum_{y} P (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}

现在问题转化为: minP∈CL(P,w) ，拉格朗日函数 L(P,w) 的约束是要满足的，如果不满足约束的话，只需另 wi→+∞ ，则可得 L(P,w)→+∞ ，因为需要得到极小值，所以约束必须要满足，满足约束后可得：

L (P, w) = max L (P, w)

，现在问题可以形式化为便于拉格朗日对偶处理的极小极大的问题：

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

由于 L(P,w) 是关于 P 的凸函数，根据拉格朗日对偶可得 L(P,w) 的极小极大问题与极大极小问题是等价的：

min_{P \in C} max_{w} L (P, w) = max_{w} min_{P \in C} L (P, w)

现在可以先求内部的极小问题 minP∈CL(P,w) ，minP∈CL(P,w) 得到的解为关于 w 的函数，可以记做 Ψ(w) ：

Ψ (w) = min_{P \in C} L (P, w) = L (P_{w}, w)

上式的解 Pw 可以记做：

P_{w} = a r g min_{P \in C} L (P, w) = P_{w} (y | x)

由于求解 P 的最小值 Pw ,只需对于 P(y|x) 求导即可,令导数等于 0 即可得到 Pw(y|x) ：

\begin{aligned} \frac{\partial L (P, w)}{\partial P (y | x)} & = \sum_{x, y} \tilde{P} (x) (l o g P (y | x) + 1) - \sum_{y} w_{0} - \sum_{x, y} (\tilde{P} (x) \sum_{i = 1}^{n} w_{i} f_{i} (x, y)) \\ = \sum_{x, y} \tilde{P} (x) (l o g P (y | x) + 1 - w_{0} - \sum_{i = 1}^{n} w_{i} f_{i} (x, y)) = 0 \\ \Rightarrow \\ P (y | x) & = e x p (\sum_{i = 1}^{n} w_{i} f_{i} (x, y) + w_{0} - 1) = \frac{e x p (\sum_{i = 1}^{n} w_{i} f_{i} (x, y))}{e x p (1 - w_{0})} \end{aligned}

由于 ∑yP(y|x)=1，可得:

\sum_{y} P (y | x) = 1 \Rightarrow \frac{1}{e x p (1 - w_{0})} \sum_{y} e x p (\sum_{i = 1}^{n} w_{i} f_{i} (x, y)) = 1

进而可以得到：

e x p (1 - w_{0}) = \sum_{y} e x p (\sum_{i = 1}^{n} w_{i} f_{i} (x, y))

这里 exp(1−w0) 起到了归一化的作用，令 Zw(x) 表示 exp(1−w0) ，便得到了 MaxEnt 模型：

\begin{aligned} P_{w} (y | x) & = \frac{1}{Z_{w} (x)} e x p (\sum_{i = 1}^{n} w_{i} f_{i} (x, y)) \\ Z_{w} (x) & = \sum_{y} e x p (\sum_{i = 1}^{n} w_{i} f_{i} (x, y)) \end{aligned}

这里 fi(x,y) 代表特征函数，wi 代表特征函数的权值， Pw(y|x) 即为 MaxEnt 模型，现在内部的极小化求解得到关于 w 的函数，现在求其对偶问题的外部极大化即可，将最优解记做 w∗:

w^{*} = a r g max_{w} Ψ (w)

所以现在最大上模型转为求解 Ψ(w) 的极大化问题，求解最优的 w∗ 后，便得到了所要求的MaxEnt 模型，将 Pw(y|x) 带入 Ψ(w) ，可得：

\begin{aligned} Ψ (w) & = \sum_{x, y} \tilde{P} (x) P_{w} (y | x) l o g 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_{i} f_{i} (x, y) + \sum_{x, y} \tilde{P} (x) P_{w} (y | x) (l o g P_{w} (y | x) - \sum_{i = 1}^{n} w_{i} f_{i} (x, y)) \\ = \sum_{x, y} \tilde{P} (x, y) \sum_{i = 1}^{n} w_{i} f_{i} (x, y) + \sum_{x, y} \tilde{P} (x) P_{w} (y | x) l o g Z_{w} (x) \\ = \sum_{x, y} \tilde{P} (x, y) \sum_{i = 1}^{n} w_{i} f_{i} (x, y) + \sum_{x} \tilde{P} (x) l o g Z_{w} (x) \sum_{y} P_{w} (y | x) \\ = \sum_{x, y} \tilde{P} (x, y) \sum_{i = 1}^{n} w_{i} f_{i} (x, y) + \sum_{x} \tilde{P} (x) l o g Z_{w} (x) \end{aligned}

以上推倒第二行到第三行用到以下结论：
.

P_{w} (y | x) = \frac{1}{Z_{w} (x)} e x p (\sum_{i = 1}^{n} w_{i} f_{i} (x, y)) \Rightarrow l o g P_{w} (y | x) = \sum_{i = 1}^{n} w_{i} f_{i} (x, y) - l o g Z_{w} (x)

倒数第二行到最后一行是由于：∑yPw(y|x)=1，最终通过一系列极其复杂的运算，得到了需要极大化的式子：

max_{p \in C} \sum_{x, y} \tilde{P} (x, y) \sum_{i = 1}^{n} w_{i} f_{i} (x, y) + \sum_{x} \tilde{P} (x) l o g Z_{w} (x)

极大化似然估计解法

这太难了，有没有简单又 work 的方式呢？答案是有的，就是极大似然估计 MLE 了，这里有训练数据得到经验分布 P˜(x,y) ，待求解的概率模型 P(Y|X) 的似然函数为：

L_{\tilde{P}} (P_{w}) = l o g \prod_{x, y} P (y | x)^{\tilde{P} (x, y)} = \sum_{x, y} \tilde{P} (x, y) l o g P (y | x)

将 Pw(y|x) 带入以下公式可以得到：

\begin{aligned} L_{\tilde{P}} (P_{w}) & = \sum_{x, y} \tilde{P} (x, y) l o g P (y | x) \\ = \sum_{x, y} \tilde{P} (x, y) (\sum_{i = 1}^{n} w_{i} f_{i} (x, y) - l o g Z_{w} (x)) \\ = \sum_{x, y} \tilde{P} (x, y) \sum_{i = 1}^{n} w_{i} f_{i} (x, y) - \sum_{x, y} \tilde{P} (x, y) l o g Z_{w} (x) \\ = \sum_{x, y} \tilde{P} (x, y) \sum_{i = 1}^{n} w_{i} f_{i} (x, y) - \sum_{x} \tilde{P} (x) l o g Z_{w} (x) \end{aligned}

显而易见，拉格朗日对偶得到的结果与极大似然得到的结果时等价的，现在只需极大化似然函数即可，顺带优化目标中可以加入正则项，这是一个凸优化问题，一般的梯度法、牛顿法都可解之，专门的算法有GIS IIS 算法。

最大熵模型内容来自：https://www.cnblogs.com/ooon/p/5677098.html