Entropy

介绍熵相关的概念：包括信息熵、相对熵、交叉熵、KL 散度和互信息。并且基于python 实现上述的算法。

（1）香侬信息量

计算机中，信息量用一个信息所需要的编码长度表示。信息量的长度和出现的概率呈负相关。一个词出现的频率越高，那么编码方式越短，同时表示的代价越高（使用该长度的01串表示之后，其他的信息不能使用该前缀的01串表示）。一个词出现的频率越高，信息量越大。

\begin{equation} I=\log _{2}\left(\frac{1}{p(x)}\right)=-\log _{2}(p(x)) \end{equation}

（2）信息熵（Entropy）

In information theory, we like to describe the “surprise” of an event. Low probability events are more surprising therefore have a larger amount of information. Whereas probability distributions where the events are equally likely are more surprising and have larger entropy. 在信息论中，使用“surprise”来描述事件。低概率事件具有更高的信息，反之亦然。从而可以推出：

均匀分布具有更高的信息熵
正太分布具有较小的信息熵

对于离散变量

\begin{equation} H(X)=-\sum_{x \in X} p(x) \log p(x) \end{equation}

对于连续变量

\begin{equation} H(X)=-\int_{X} p(x) \log p(x) d x \end{equation}

如果未加特殊说明，本文中一般认为 $p(x)$ 认为是真实分布， $q(x)$是用来生成分布，$q(x)$用来近似表示$p(x)$

（3）交叉熵（Cross-Entropy）

Cross-entropy is related to divergence measures that quantifies how much one distribution differs from another. 交叉熵是衡量分布差异的指标。可以看出是用一个猜测的分布的编码方式$q(x)$去编码真实的分布 $p(x)$, 计算平均的编码长度（信息量）

\begin{equation} H(p, q)=\sum_{X} p(x) \log _{2}\left(\frac{1}{q(x)}\right) \end{equation}

其中 $p(x)$是真实的分布，$q(x)$ 是猜测的分布。

1). 交叉熵作为损失函数

在机器学习中，交叉熵是非常常见的一种损失函数。交叉熵可以用于学习“真实分布”和“预测分布”之间的不同，当交叉熵最低的时候，模型很好得学习到了训练数据集分布，，并不能保证很好的扩展性。训练分布并不是真实分布，所以在模型中需要加上一个正则项，提高模型的泛化性能。

二分类交叉熵损失函数

\begin{equation} L=-[y \cdot \log (p)+(1-y) \cdot \log (1-p)] \end{equation}

其中 $y$表示真实样本 label（1为正类，0为负类）；$p$ 为预测为正的概率。

多分类交叉熵损失函数

\begin{equation} L=-\sum_{c=1}^{M} y_{c} \log \left(p_{c}\right) \end{equation}

其中 $M$表示总的类别数量， $y_c$ 表示指示变量（1或者0， 1 表示预测类别和真实类别相同，否则为0），$p_c$表示预测类比属于 $c$的概率。

2). 交叉熵损失函数相对于平方损失函数的优点

交叉熵搭配 LR激活函数，得到的导数形式为： $$ \frac{\partial}{\partial \theta_{j}} \ell(\theta)= \left(y-h_{\theta}(x)\right) x_{j}$$

其中$y$表示真实的标签， $h_{\theta}(x)$ 表示模型预测的结果。导数的形式可以说是相当的简单，所以在反向传播的时候计算量很小。上述公式推导过程可以看这里。而平方损失函数的导数形式为： $$ \frac{\partial}{\partial \theta_{j}} \ell(\theta) = \left(y-h_{\theta}(x)\right) h^{\prime}_{\theta}(x_j) $$

可以发现该导数形式需要求一阶导数。所以，交叉熵损失函数相对于平方损失函数是具有计算简单的优点。

3). 代码实现部分

交叉熵定义计算方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


# example of calculating cross entropy
from math import log2

# calculate cross entropy
def cross_entropy(p, q):
	return -sum([p[i]*log2(q[i]) for i in range(len(p))])

# define data
p = [0.10, 0.40, 0.50]
q = [0.80, 0.15, 0.05]
# calculate cross entropy H(P, Q)
ce_pq = cross_entropy(p, q)
print('H(P, Q): %.3f bits' % ce_pq)
# calculate cross entropy H(Q, P)
ce_qp = cross_entropy(q, p)
print('H(Q, P): %.3f bits' % ce_qp)

根据KL 散度计算交叉熵（具体推导关系在下面）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


# example of calculating cross entropy with kl divergence
from math import log2
# calculate the kl divergence KL(P || Q)
def kl_divergence(p, q):
	return sum(p[i] * log2(p[i]/q[i]) for i in range(len(p)))

# calculate entropy H(P)
def entropy(p):
	return -sum([p[i] * log2(p[i]) for i in range(len(p))])

# calculate cross entropy H(P, Q)
def cross_entropy(p, q):
	return entropy(p) + kl_divergence(p, q)

# define data
p = [0.10, 0.40, 0.50]
q = [0.80, 0.15, 0.05]
# calculate H(P)
en_p = entropy(p)
print('H(P): %.3f bits' % en_p)
# calculate kl divergence KL(P || Q)
kl_pq = kl_divergence(p, q)
print('KL(P || Q): %.3f bits' % kl_pq)
# calculate cross entropy H(P, Q)
ce_pq = cross_entropy(p, q)
print('H(P, Q): %.3f bits' % ce_pq)

交叉熵作为损失函数计算。（注意如果是二分类需要构造两个分布（0， 1））

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


# calculate cross entropy for classification problem
from math import log
from numpy import mean

# calculate cross entropy
def cross_entropy(p, q):
	return -sum([p[i]*log(q[i]) for i in range(len(p))])

# define classification data
p = [1, 1, 1, 1, 1, 0, 0, 0, 0, 0]
q = [0.8, 0.9, 0.9, 0.6, 0.8, 0.1, 0.4, 0.2, 0.1, 0.3]
# calculate cross entropy for each example
results = list()
for i in range(len(p)):
	# create the distribution for each event {0, 1}
	expected = [1.0 - p[i], p[i]]
	predicted = [1.0 - q[i], q[i]]
	# calculate cross entropy for the two events
	ce = cross_entropy(expected, predicted)
	print('>[y=%.1f, yhat=%.1f] ce: %.3f nats' % (p[i], q[i], ce))
	results.append(ce)

# calculate the average cross entropy
mean_ce = mean(results)
print('Average Cross Entropy: %.3f nats' % mean_ce)

4). 交叉熵和log loss 的关系

Log Loss 是LR 模型中的损失函数。在称述的过程中交叉熵，log loss和 negative log-likehood 经常交替使用。其实还是有一点区别的。

log loss 是LR 模型基于最大似然估计推导出来的，LR 模型是基于伯努利分布，具体的推导过程可以参考这里。

We can see that the negative log-likelihood is the same calculation as is used for the cross-entropy for Bernoulli probability distribution functions (two events or classes). In fact, the negative log-likelihood for Multinoulli distributions (multi-class classification) also matches the calculation for cross-entropy. 当交叉熵基于伯努利分布计算的时候，得到的结果和log loss 是一样的。但是两者不是一个东西，

（4）KL 散度（相对熵，Relative Entropy）

The Kullback-Leibler Divergence score, or KL divergence score, quantifies how much one probability distribution differs from another probability distribution. KL散度是一种分布距离函数（Statistical Distance），但是更加准确的理解是衡量分布相似度的计算函数，而不是距离计算函数，因为其并不满足严格意义上关于距离的定义。

离散变量表示为：

\begin{equation} D_{\mathrm{KL}}(p | q)=-\int_{X} p(x) \log \frac{q(x)}{p(x)} d x \end{equation}

连续变量表示为：

\begin{equation} D_{\mathrm{KL}}(p | q)=-\sum_{x \in X} p(x) \log \frac{q(x)}{p(x)} \end{equation}

1). KL 散度的特点

当 $p =q$ 的时候， KL 的值为0
不具有对称，即 $D_{\mathrm{KL}}(p | q) \ne D_{\mathrm{KL}}(q | p)$

2). 交叉熵和 KL 散度的关系：交叉熵等于熵加上KL 散度之和。推导也很简单

\begin{equation} \begin{aligned} H(p, q) &=-\sum_{x} p(x) \log q(x) \\
&=-\sum_{x} p(x) \log p(x)-\sum_{x} p(x) \log \frac{q(x)}{p(x)} \\
&=H(p)+K L(p | q) \end{aligned} \end{equation}

上述推导以于离散变量为例，连续变量的推导类似，只是把求和符号$\sum$换成积分符号$\int$。

3). 上代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


# define distributions
events = ['red', 'green', 'blue']
p = [0.10, 0.40, 0.50]
q = [0.80, 0.15, 0.05]

# plot of distributions
from matplotlib import pyplot
# define distributions
events = ['red', 'green', 'blue']
p = [0.10, 0.40, 0.50]
q = [0.80, 0.15, 0.05]
print('P=%.3f Q=%.3f' % (sum(p), sum(q)))
# plot first distribution
pyplot.subplot(2,1,1)
pyplot.bar(events, p)
# plot second distribution
pyplot.subplot(2,1,2)
pyplot.bar(events, q)
# show the plot
pyplot.show()

from math import log2
# calculate the kl divergence
def kl_divergence(p, q):
	return sum(p[i] * log2(p[i]/q[i]) for i in range(len(p)))
	
# calculate (P || Q)
kl_pq = kl_divergence(p, q)
print('KL(P || Q): %.3f bits' % kl_pq)
# calculate (Q || P)
kl_qp = kl_divergence(q, p)
print('KL(Q || P): %.3f bits' % kl_qp)

#KL(P || Q): 1.927 bits                                                                                                                                                                    
#KL(Q || P): 2.022 bits  

（5）JS 散度

It is more useful as a measure as it provides a smoothed and normalized version of KL divergence, with scores between 0 (identical) and 1 (maximally different), when using the base-2 logarithm. JS 也是一种分布距离函数（Statistical Distance）。JS 散度的存在主要是弥补KL 散度的非对称性。

It uses the KL divergence to calculate a normalized score that is symmetrical. This means that the divergence of P from Q is the same as Q from P, or stated formally:

$$JS(P || Q) == JS(Q || P) $$ The JS divergence can be calculated as follows: $$ JS(P || Q) = \frac{1}{2} \cdot KL(P || M) + \frac{1}{2} \cdot KL(Q || M) $$ Where M is calculated as: $$ M = \frac{1}{2} \cdot (P + Q) $$

数据和上面的一样，有了KL 散度的计算， JS也是比较简单的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


# calculate the js divergence
def js_divergence(p, q):
	m = 0.5 * (p + q)
	return 0.5 * kl_divergence(p, m) + 0.5 * kl_divergence(q, m)

# calculate JS(P || Q)
js_pq = js_divergence(p, q)
print('JS(P || Q) divergence: %.3f bits' % js_pq)
print('JS(P || Q) distance: %.3f' % sqrt(js_pq))

# calculate JS(Q || P)
js_qp = js_divergence(q, p)
print('JS(Q || P) divergence: %.3f bits' % js_qp)
print('JS(Q || P) distance: %.3f' % sqrt(js_qp))

同样sklearn 中有相应的实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


# calculate the jensen-shannon distance metric
from scipy.spatial.distance import jensenshannon
from numpy import asarray
# define distributions
p = asarray([0.10, 0.40, 0.50])
q = asarray([0.80, 0.15, 0.05])
# calculate JS(P || Q)
js_pq = jensenshannon(p, q, base=2)
print('JS(P || Q) Distance: %.3f' % js_pq)
# calculate JS(Q || P)
js_qp = jensenshannon(q, p, base=2)
print('JS(Q || P) Distance: %.3f' % js_qp)

（6）联合熵，条件熵和互信息（信息增益）

根据熵的定义，拓展到两个变量，就得到了联合熵。 \begin{equation} H(X, Y)=-\sum_{x \in X} \sum_{y \in Y} p(x, y) \log p(x, y) \end{equation}

其中 $X$, $Y$ 是两个离散变量，他们的联合分布是 $p(x, y)$。

条件熵定义为

\begin{equation} \begin{aligned} H(Y | X) &=-\sum_{x \in X} p(x) H(y | X =x)\\
&=- \sum_{x \in X} \sum{y \in Y} p(x, y) \log p(y|x)\\
&= E [- \log (y|x)] \end{aligned} \end{equation}

The entropy is a sum of conditional entropies 熵和条件熵的关系：

\begin{equation} H\left(X_{1}, X_{2}, X_{3}\right)=H\left(X_{1}\right)+H\left(X_{2} | X_{1}\right)+H\left(X_{3} | X_{2}, X_{1}\right) \end{equation}

如果说联合熵是并集，那么互信息是交集。 \begin{equation} \begin{aligned} I(X ; Y) &=H(X)-H(X | Y)=H(Y)-H(Y | X) \\ &=H(X)+H(Y)-H(X, Y) \\ &=H(X, Y)-H(X | Y)-H(Y | X) \end{aligned} \end{equation} 互信息(Mutual Information) ：一个随机变量由于已知另一个随机变量而减少的不确定性。从上面公式也是可以知道，当增加变量之后，互信息只能是越变越小。

互信息还可以使用 KL 散度进行定义：

\begin{equation} \begin{aligned} I(X ; Y) &= D_{KL} (p(X, Y) || p(X) p(Y)) \\
&= - \sum_{x \in X} \sum_{y \in Y} p(x, y) \log \frac{p(x, y)}{ p(x) p(y)} \end{aligned} \end{equation}

所以当 $X$ 和 $Y$ 独立的时候，即 $p(x, y) =p(x)p(y)$, 即$I(X ;Y) =0$。（认为规定 $0 \log 0 =0$）

不加证明，互信息是具有对称性和非负性。

上述熵的关系可以使用一张图表示。

（7）决策树ID3中的信息增益（互信息）

Mutual information calculates the statistical dependence between two variables and is the name given to information gain when applied to variable selection. 互信息计算的是两个变量统计上的依赖关系。

It is commonly used in the construction of decision trees from a training dataset, by evaluating the information gain for each variable, and selecting the variable that maximizes the information gain, which in turn minimizes the entropy and best splits the dataset into groups for effective classification. 信息增益是使得熵不断减少，最后的信息越来越确定。

Information Gain, or IG for short, measures the reduction in entropy or surprise by splitting a dataset according to a given value of a random variable.

$$ IG(S, a) = H(S) – H(S | a) $$

其中 $IG(S, a) $ 是数据集 $S$ 对于变量 $a$ 的信息增益， $H(S)$ 表示数据集整个熵， $H(S| a) $表示条件熵。

上代码：

问题是二分类，其中 $label =1$ 的样本有7个，$label =0$ 的样本有13个；其中有一个特征，该特征只有两个值 $s_1, s_2$，定义符号 $s_{i,j}$ 其中 $i$表示特征值， $j $表示label 值。所以 $s_{1, 0} =7$, $s_{1, 1} =1$, $s_{2, 0} =6$, $s_{2, 1} =6$。然后计算熵和信息增益。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


from math import log2
 
# calculate the entropy for the split in the dataset
def entropy(class0, class1):
	return -(class0 * log2(class0) + class1 * log2(class1))
 
# split of the main dataset
class0 = 13 / 20
class1 = 7 / 20
# calculate entropy before the change
s_entropy = entropy(class0, class1)
print('Dataset Entropy: %.3f bits' % s_entropy)
 
# split 1 (split via value1)
s1_class0 = 7 / 8
s1_class1 = 1 / 8
# calculate the entropy of the first group
s1_entropy = entropy(s1_class0, s1_class1)
print('Group1 Entropy: %.3f bits' % s1_entropy)
 
# split 2  (split via value2)
s2_class0 = 6 / 12
s2_class1 = 6 / 12
# calculate the entropy of the second group
s2_entropy = entropy(s2_class0, s2_class1)
print('Group2 Entropy: %.3f bits' % s2_entropy)
 
# calculate the information gain
gain = s_entropy - (8/20 * s1_entropy + 12/20 * s2_entropy)
print('Information Gain: %.3f bits' % gain)

使用sklearn 计算

1
2


from sklearn.tree import DecisionTreeClassifier
model =sklearn.tree.DecisionTreeClassifier(criterion ='entropy')

决策树相关的还需要总结。包括有收藏的连接和本地的文件。

（8）信息增益率

信息增益率是决策树 C4.5 引入的划分特征准则，（9）基尼系数

文章目录