Entropy

http://colah.github.io/posts/2015-09-Visual-Information/ Visual Information Theory

http://yugnaynehc.github.io/2017/01/02/visual-information-theory/ [译]直观理解信息论

从数据压缩和传输角度解释的，对于高频词，以更短的码来编码。

Entropy

自信息量(香农信息量)

$I(x_i) = \log \frac {1} {P(x_i)} = -\log P(x_i)$

在信息论里面对数log默认都是指以2为底数。即熵的单位是比特。

倘若底数不是2，可以通过换底公式 换成已2为底数，然后乘上一个倍数就行了。 $\log_a b = \frac {\log_c b}{\log_c a}$

联合自信息量

$I(x_i,y_i) = -\log P(x_i,y_i)$

条件自信息量

$I(x_i|y_i) = -\log P(x_i|y_i)$

看这张图，想要的量都可以推导出来。

信息熵 Entropy

熵的定义为信息的期望值。某个事件用随机变量X表示，则该事件的信息熵定义为：

$$\begin{align} H(X) & = E(I(X)) = \sum_{i=1}^n P(x_i)I(x_i) = -\sum_{i=1}^n P(x_i) \log_2 ⁡P(x_i )\\ H(X) & = -\int_a^b f(x)\ln f(x)dx , f(x) \text{表示相对概率密度函数} \end{align}$$

熵是对不确定性的测量。所以概率越平均，则熵越大。越不平均，某一事件发生的概率非常大，则不确定性小，熵值小。

联合熵 joint Entropy

联合熵：联合信息的数学期望，二维随机变量XY的不确定性的度量。

两个随机变量X和Y联合分布为p(x,y)，则联合信息熵：

$$H(X,Y) = -\sum_x \sum_y p(x,y)\log ⁡p(x,y) = H(X) + H(Y|X) = H(Y) + H(X|Y)$$

可以看出信息增益。 特性：

• 大于子系统的熵：$H(X,Y) \ge \max [H(X),H(Y)]$
• 子可加性：$H(X,Y) \le H(X) + H(Y)$
• 非负性：$H(X,Y) \ge 0$

条件熵 Conditional Entropy

条件熵：表示已知X时，Y的平均不确定性。

$$H(Y|X) = \sum_x p(x)H(Y|X=x) \\ =-\sum_x p(x)\sum_y p(y|x)\log p(y|x) \\ =-\sum_x \sum_y p(x)p(y|x)\log p(y|x) \\ =-\sum_x \sum_y p(x,y)\log p(y|x) \\ \text{或者} H(Y|X) = -\sum_{xy} p(x,y)\log p(y|x) \\ H(Y|X) = - \int \int f(x)f(y|x) \log f(y|x) \mathrm{d}x \mathrm{d}y$$

可以证明$H(Y) \ge H(Y|X)$，也就是说，多了X信息，Y的不确定性下降了。

同理： $H(Z|Y,X) = -\sum_{xyz} p(x,y,z)\log p(z|y,x)$,可以证明$H(Z|Y) \ge H(Z|Y,X)$。就是说，三元模型比二元模型好。

信息增益

信息增益，是一种衡量样本特征重要性的方法。 特征A对训练数据集D的信息增益g(D,A) ，定义为集合D的经验熵H(D)与特征A在给定条件下D的经验条件熵H(D|A)之差，即

$$g(D,A) = H(D) - H(D|A)$$

一般地熵H(Y)与条件熵H(Y|X)之差称为互信息（mutual information）。 互信息定义： $I(X,Y) = \sum_{x,y} p(x,y)\log \frac {p(x,y)}{p(x)p(y)}$，所以 $I(X,Y) = H(X)-H(X|Y) = I(Y,X) = H(Y)-H(Y|X)$

信息增益比

$$g_R(D,A) = \frac {g(D,A)}{H(D)}$$

互信息Mutual Informantion

$y_i$对$x_i$的互信息定义为后验概率与先验概率比值的对数:

$$I(x_i,y_i) = \log \frac {p(x_i|y_i)}{p(x_i)} = I(x_i) - I(x_i|y_i)$$

互信息越大，表明$y_i$对于确定$x_i$的取值的贡献度越大。

$$H(X,Y) = H(X) + H(Y|X) = H(Y) + H(X|Y) \\ MI(X,Y) = H(X) – H(X|Y) = H(Y) – H(Y|X)$$

互信息与相关性关系：当相关性为+/-1时，互信息趋于无穷；当相关性为0时，互信息为0。

反作弊基于左右信息熵和互信息的新词挖掘

相对熵 KL散度

相对熵（KL-Divergence KL散度）: 用来描述两个概率分布P和Q差异的一种方法。 它是非对称的，这意味着D(P||Q) ≠ D(Q||P)。特别的，在信息论中，D(P||Q)表示当用概率分布Q来拟合真实分布P时，产生的信息损耗，其中P表示真实分布，Q表示P的拟合分布。 有人将KL散度称为KL距离，但事实上，KL散度并不满足距离的概念，因为：1）KL散度不是对称的；2）KL散度不满足三角不等式。

对于两个完全相同的分布，他们的相对熵为0。

如实际分布函数P(x),我们估计的分布函数Q(x)。KL(P||Q) 就是函数P和函数Q之间的相似度成反比，因此可以通过最小化相对熵来使函数Q逼近函数P，也就是使得我们估计的函数Q接近真实的分布函数。

定义： $KL(f(x)||g(x)) = \sum_x f(x) \cdot \log \frac {f(x)}{g(x)}$

$$\begin{align} D_{KL}(p || q) &= \sum_{x \in X}{p(x) \log{\frac{p(x)}{q(x)} }} \\ &= \sum_{x \in X}{p(x) \log{p(x)}} – \sum_{x \in X}{p(x) \log{q(x)} } \\ &= H(X,p,q) – H(X,p) \\ &= H(p,q) – H(p) \qquad \text{简写} \\ \end{align}$$

就是用Q代替P，带来的信息损失。

交叉熵 cross entropy

设随机变量x的真实分布为P，用Q分布来近似P，则随机变量x的交叉熵定义为：

$$H(X,p,q) = E_p[-\log q] = – \sum_{x \in X}{p(x) \log{q(x)}} \\ H(X,p,q) = -\int_X p(x) \log q(x) dx \\$$

形式上可以理解为使用$q(x)$来代替原来$p(x)$的信息量。 当x取值只有两种时，比如二分类的问题， 交叉熵就等于似然估计了。

交叉熵：$c= - [y \ln a + (1-y)\ln (1-a)]$

另外交叉熵与KL距离的关系：

$$H(p,q) = – \sum_{x}{p(x) \log{q(x)}} = – \sum_{x}{p(x) \log \frac {q(x)}{p(x)} p(x)} =– \sum_{x}{p(x) \log p(x)} – \sum_{x}{p(x) \log \frac {q(x)}{p(x)}} = H(p) + D_{KL}(p||q)$$

所以p与q的交叉熵，就是p分布的信息熵和 p与q的KL散度和。

https://www.zhihu.com/question/41252833 如何通俗的解释交叉熵与相对熵?

基于期望交叉熵的特征项选择

$$CE(w) = \sum_i P(C_i|w) \log \frac {P(C_i|w)}{P(C_i)}$$

$P(C_i|w)$表示在出现词条w时文档属于类别ci的概率。

交叉熵反应了文本类别的概率分布与在出现了某个词条的情况下文本类别的概率分布之间的距离。词条的交叉熵越大，对文本类别分布影响也就越大。所以选CE最大的K个词条作为最终的特征项。

参考佳文

信息论

信息熵是什么？ 条件熵 信息增益 特征选择方法之信息增益 第02章：深入浅出ML之Entropy-Based家族

MIFS – parallelized Mutual Information based Feature Selection module

从香农熵到手推KL散度：纵览机器学习中的信息论

详解机器学习中的熵、条件熵、相对熵和交叉熵

机器学习各种熵：从入门到全面掌握