李宏毅机器学习任务七

信息论

主要讨论离散型

信息量

信息是用来消除随机不确定性的东西。也就是说衡量信息量大小就看这个信息消除不确定性的程度
信息量度量的是一个具体事件发生带来的信息

公式化表示为：
$I(X)=\log_{2} \frac{1}{p(x)}=-\log_{2} p(x)$
单位：当 $log$ 以2为底时，对应单位为比特 (bit)。当 $log$ 以 $e$ 为底时，对应单位为奈特 (nat)。且 1 nat = 1.44 bit

以 $e$ 为底，如果是 1 nat 的信息量，则该事件发生的概率为 $1/e$ ，此概率用以2为底计算为 $log_{2}{1/e} = 1.44 bit$

来源：

用概率描述信息量需要满足一下三个重要性质：

事件发生的概率越低，信息量越大
事件发生的概率越大，信息量越少
多个事件同时发生的概率是多个事件概率相乘，总信息量是多个事件信息量相加

通过前两点，我们知道信息量和概率之间是减函数的关系，第三点确定了对数关系。然后进一步列方程求解，因为方程对应多个解，默认使用常系数为 1 的形式（可能这样较为简单吧，并且对于计算机二进制系统，对数的底数为2计算会方便）

信息熵

熵则是在结果出来之前对可能发生的信息量的期望——考虑该随机变量的所有可能取值，即所有可能发生事件所带来的信息量的期望
信息熵是用来衡量事物不确定性的。信息熵越大，事物越具不确定性，事物越复杂
因此，所谓的信息熵，就是衡量事件发生后带来信息量多少的一个度量
信息熵衡量了系统的不确定性，而我们要消除在这个不确定性，所要付出的最小努力

公式表示为：

信息熵是信息量的数学期望，即 $I(X)$ 在以 $P(x)$ 分布下信息量的数学期望

$H(X)=E(I(X))=-\sum_{i=1}^{n}P\left(x_{i}\right) \log _{2} P\left(x_{i}\right)$

从公式可得，随机变量的取值个数越多，状态数也就越多，信息熵就越大，混乱程度就越大。当随机分布为均匀分布时，熵最大，且 $0 \le H(X) \le logn$ , 这里 $n$ 为随机变量取值的个数。

证明：

利用拉格朗日乘子法证明：

目标函数：
$f(p(1), p(2), \ldots, p(n))=-p(1) \log p(1)-p(2) \log p(2) \ldots-p(n) \log p(n)$
约束条件：
$p(1)+p(2)+\ldots+p(n)=1$
构造拉格朗日函数，然后分别求导，然后求解（得： $p(1)=p(2)=\cdots=p(n)=\frac{1}{n}$ ），可得目标函数的极大值（因为目标函数为凹函数，极大值即最大值）为 $f\left(\frac{1}{n}, \frac{1}{n}, \ldots, \frac{1}{n}\right) = logn$

得证：
$0 \le H(X) \le logn$

联合熵

两个离散型随机变量 $X$ 和 $Y$ 的联合熵为：
$H(X, Y)=-\sum_{y \in Y} \sum_{x \in X} p(x, y) \log p(x, y)$
联合熵表征了两事件同时发生系统的不确定度。

条件熵

条件熵 $H(Y|X)$ 表示在已知随机变量 $X$ 的条件下随机变量 $Y$ 的不确定性，定义为 $X$ 给定条件下 $Y$ 的条件概率分布的熵对 $X$ 的数学期望：
$H(Y | X)=\sum_{x \in X} p(x) H(Y | x)=-\sum_{x \in X} p(x) \sum_{y \in Y} p(y | x) \log p(y | x)$
进一步推导：
$\begin{aligned} H(Y | X) &=-\sum_{x \in X} p(x) \sum_{y \in Y} p(y | x) \log p(y | x) \\ &=-\sum_{x \in X} \sum_{y \in Y} p(x, y) \log \frac{p(x, y)}{p(x)} \\ &=-\sum_{x \in X} \sum_{y \in Y} p(x, y)(\log p(x, y)-\log p(x)) \\ &=-\sum_{x \in X} \sum_{y \in Y} p(x, y) \log p(x, y)+\sum_{x \in X} \sum_{y \in Y} p(x, y) \log p(x) \\ &=-\sum_{x \in X} \sum_{y \in Y} p(x, y) \log p(x, y)+\sum_{x \in X} p(x) \log p(x) \\ &=H(X, Y)-H(X) \end{aligned}$

互信息

两个离散随机变量 $X$ 和 $Y$ 的互信息定义为：
$I(X, Y)=\sum_{y \in Y} \sum_{x \in X} p(x, y) \log \left(\frac{p(x, y)}{p(x) p(y)}\right)$
为了理解互信息的涵义，我们把公式中的对数项分解：
$\begin{aligned} \log \left(\frac{p(x, y)}{p(x) p(y)}\right) &=\log (p(x, y)-(\log p(x)+\log p(y))\\ &=-\log p(x)-\log p(y)-(-\log p(x, y)) \end{aligned}$

我们知道概率取负对数表征了当前概率发生所代表的信息量。上式表明，两件事的互信息为各自单独发生所代表的信息量之和减去两事件同时发生所代表的信息量之和后剩余的信息量。这表明了两事件单独发生给出的信息量之和是有重复的，互信息度量了这种重复的信息量大小。最后再求概率和表示了量事件互信息量的期望值。从式中也可以看出，当两事件完全独立时， $p(x, y)=p(x) \cdot p(y)$ ，互信息计算为0，这也与常识判断相吻合。

https://blog.csdn.net/BigData_Mining/article/details/81279612

互信息、联合熵、条件熵之间的关系

$\begin{aligned} I(X, Y) &=H(X)+H(Y)-H(X, Y) \\ &=H(Y)-H(Y | X) \\ &=H(X)-H(X | Y) \\ &=H(X, Y)-H(Y | X)-H(X | Y) \end{aligned}$

img

相对熵（KL散度）

表示使用理论分析拟合真实分布时产生的信息损耗
交叉熵可以用来衡量两个概率分布之间的差异，其公式的意义就是求 $p$ 与 $q$ 之间的对数差在 $p$ 上的期望

设 $p(x)、q(x)$ 是离散随机变量 $X$ 中取值的两个概率分布，则 $p$ 对 $q$ 的相对熵是：
$D_{K L}(p \| q)=\sum_{x} p(x) \log \frac{p(x)}{q(x)}=E_{p(x)} \log \frac{p(x)}{q(x)}$
性质：

如果 $p(x)$ 和 $q(x)$ 两个分布相同，那么相对熵等于0
$D_{K L}(p \| q) \neq D_{K L}(q \| p)$ ，相对熵具有不对称性
$D_{K L}(p \| q) \geq 0$ ，证明如下（利用Jensen不等式）：

$\begin{aligned} D_{K L}(p \| q) &=\sum_{x} p(x) \log \frac{p(x)}{q(x)} \\ &=-\sum_{x} p(x) \log \frac{q(x)}{p(x)} \\ &=-E_{p(x)}\left(\log \frac{q(x)}{p(x)}\right) \\ & \geq-\log \sum_{p(x)}\left(\frac{q(x)}{p(x)}\right) \\ &=-\log \sum_{x} p(x) \frac{q(x)}{p(x)} \\ &=-\log \sum_{x} q(x) \end{aligned}$

因为： $\sum_{x} q(x)=1$ ，所以： $D_{K L}(p \| q) \geq 0$

交叉熵

用来衡量在给定的真实分布下，使用非真实分布指定的策略消除系统的不确定性所需要付出努力的大小

公式表示为：
$H(P, Q)=-\sum_{x} P(x) \log Q(x)$
前提：机器学习中不管是 “判断模型” 还是 “生成模型”，都是希望从样本中学习到总体的概率分布（前者：条件概率分布，后者：联合概率分布）

通俗理解：

样本标签相当于从真实概率分布中得到的结果，即对应于交叉熵中的 $p(x)$ ，例如：判断一张照片是猫还是狗，猫、狗对应的标签假设分别为1和0。即照片是猫的概率为1，是狗的概率为0。

我们模型的目标是拟合一个概率分布，使其尽可能的和真实概率分布一样。

从一个角度来理解，即最小化拟合概率和真实概率之间的相对熵，因为针对同一个样本，真实概率的信息熵是个定值，所以等同于最小化拟合概率和真实概率之间的交叉熵。

交叉熵个人理解：样本分布是根据真实分布得到，如果拟合的概率分布等于真实的概率分布，此时交叉熵等于信息熵，即消除不确定性平均所需要付出的努力的大小。若拟合概率分布和真实概率分布差距越大，交叉熵就越大。

另一个角度，编码长度：

现在有关于样本集的两个概率分布 $p(x)$ 和 $q(x)$ ，其中 $p(x)$ 为真实分布， $q(x)$ 非真实分布。如果用真实分布 $p(x)$ 来衡量识别一个样本所需要编码长度的期望（平均编码长度）为：
$H(p)=\sum_{x} p(x) \log \frac{1}{p(x)}$
如果使用非真实分布 $q(x)$ 来表示来自真实分布 $p(x)$ 的平均编码长度，则是：
$H(p, q)=\sum_{x} p(x) \log \frac{1}{q(x)}$
（因为用 $q(x)$ 来编码的样本来自于分布 $p(x)$ ，所以 $H(p, q)$ 中的概率是 $p(x)$ ）

KL散度、交叉熵和熵之间的关系

$D_{K L}(p \| q)=H(p, q)-H(p)$

在机器学习中，训练数据的分布已经固定，所以 $H(p)$ 为常量，最小化相对熵等价于最小化交叉熵，也等价于最大化似然估计（Deep Learning 5.5）

机器如何“学习”

在机器学习中，我们希望在训练数据上模型学到的分布 $P(model)$ 和真实数据的分布 $P(real)$ 越接近越好，所以我们可以使其相对熵最小。但是我们没有真实数据的分布，所以只能希望模型学到的分布 $P(model)$ 和训练数据的分布 $P(train)$ 尽量相同。假设训练数据是从总体中独立同分布采样的，那么我们可以通过最小化训练数据的经验误差来降低模型的泛化误差。即：

希望学到的模型的分布和真实分布一致， $P(model)≃P(real)$
但是真实分布不可知，假设训练数据是从真实数据中独立同分布采样的， $P(train)≃P(real)$
因此，我们希望学到的模型分布至少和训练数据的分布一致， $P(train)≃P(model)$

根据之前的描述，最小化训练数据上的分布 $P(train)$ 与模型分布 $P(model)$ 的差异等价于最小化相对熵， $D_{K L}(P(\text {train}) \| P(\text {model}))$ 。此时， $P(train)$ 就是 $D_{K L}(p \| q)$ 中的 $p$ ，即真实分布， $P(model)$ 就是 $q$ 。又因为训练数据的分布 $p$ 是固定的，所以求 $D_{K L}(p \| q)$ 等价于求 $H(p, q)$ 。得证，交叉熵可以用来计算学习模型分布与训练分布之间的差异。

信息编码角度

信息熵：编码方案完美时，最短平均编码长度的多少

交叉熵：编码方案不一定完美时（由于对概率分布的估计不一定正确），平均编码长度的多少

平均编码长度 = 最短平均编码长度 + 一个增量

相对熵：编码方案不一定完美时，平均编码长度相对于最小值的增加值。（即上面的增量）

计算给定数据的香农熵

import numpy as np
import pandas as pd

data = pd.read_csv(r"/home/kangaroo/project/LiHongYi/watermelon_3a.csv")
data = data.values.tolist()

def cancShannonEnt(dataSet):
    '''
    :param dataSet: dataSet
    :return: shannonEnt
    '''
    # 计算公式前，注意数据的格式(array)
    numEntries = len(dataSet)   # 获取数据的行数
    labelCounts = { }    # 设置字典数据格式，想要存储的数据格式为：类别：频数
    for featVec in dataSet:   # 获取数据集每一行的数据
        currentLabel = featVec[-1]   # 获取特征向量的最后一列
        # 检查字典中key是否存在
        # 如果key不存在
        if currentLabel not in labelCounts.keys():
            # 将当前的标签存于字典中，并将频数置为0
            labelCounts[currentLabel] = 0
        # 如果key存在，在当前的键值上+1
        labelCounts[currentLabel] +=1

    # 数据已准备好，计算熵
    shannonEnt = 0.0          # 初始化信息熵
    for key in labelCounts:   # 遍历出数据中所的类别
        pro = float(labelCounts[key]) /numEntries   
        shannonEnt -= pro * np.log2(pro)  # 计算信息熵
    return shannonEnt                       # 返回信息熵

print(cancShannonEnt(data))

# 输出结果为：0.9975025463691153