统计学习方法

熵的概念

信息熵

定义

对于一个随机变量$X$而言，其可能取值为$x_1,x_2,x_n\dots$，其取到的概率分别为$p_1,p_2,\dots p_n$那么定义其熵为（此处的$\log$底数是2）：
$$
H(X):=-\sum_{i=1}^n p_i\log p_i
$$
其含义是什么呢？把这个随机变量想成一个“数据”序列，例如$x_4 x_8 x_3 x_9 x_5 x_8\cdots$是发送的一串数据序列。某一个数据的信息量大于另一个数据，指的是“出现一次前者要经历的数据串长度”比“出现一次后者要经历的数据串长度”大，即“概率越小的数据，其信息含量越大”。如果$x_i$的概率是$p_i$，说明平均要经历$1/p_i$的数据串长度才会出现一次$x_i$。现在如果用二进制去存储这个$1/p_i$的长度，就是$\log(1/p_i)$，该值就定义为信息量，（以2为底时）单位为bit，而熵也就是该序列中数据的信息量大小的期望值$\sum_i p_i\log(1/p_i)$

性质

有不等式：
$$
H(X)\leq -\sum_{i=1}^n p_i\log q_i
$$

其中$\{q_i\}$是满足$\sum_i q_i=1$的一组非负数。该式等号成立当且仅当对各个$i$而言$q_i=p_i$都成立。

不等式的证明：

$-\sum_i p_i\ln p_i +\sum_i p_i\ln q_i=\sum_i p_i\ln \left(\frac{q_i}{p_i}\right)\leq\sum_{i} p_i\left(\frac{q_i}{p_i}-1\right)=0$

底数换成2无非是多一个scaling而已，证毕

该不等式说，如果把$\log$里面的概率分布换成$p_i$以外的另一个概率分布的话，值会变大。特别的，当换成均匀分布时，有：
$$
H(X)\leq -\sum_{i=1}^n p_i\log \frac{1}{n}=\sum_{i=1}^n p_i\log n=\log n
$$

当然本身该式也可以从Jensen不等式得来，利用$f(x):=\log(x)$函数是凹函数：
$$
H(X)=\sum_{i=1}^n p_i f\left(\frac{1}{p_i}\right)\leq f\left(\sum_{i=1}^n p_i \cdot \frac{1}{p_i}\right)=f(n)=\log n
$$

熵越大，说明不确定度越大，比如这里的平均分布$p_1=p_2=\cdots =p_n=\frac{1}{n}$时，熵是最大的，恰好能够取到$\log n$这个上界。而当某一个$p_i=1$时，代表该数据分布是十分确定的，熵为$0$，不确定度最小

条件熵

如把另一个随机变量$Y$考虑进来，把刚才的$p_i$全部替换为条件概率，那会如何呢？比如在$Y=y$这个事件发生的条件下，得到$X$的熵是：
$$
H(X|Y=y)=-\sum_{x} p_{X|Y}(x|y)\log p_{X|Y}(x|y)
$$
当然$Y$可取遍各个$y$，于是在这种“取遍”的平均意义下，定义条件熵：
$$
H(X|Y):=\sum_{y} p_Y(y)H(X|Y=y)=-\sum_{y}\sum_{x} p_Y(y)p_{X|Y}(x|y)\log p_{X|Y}(x|y)
$$

代表在$Y$的帮助下$X$的平均信息量大小

信息增益

定义为
$$
g(X,Y):=H(X)-H(X|Y)
$$
根据形式就知道，这是在$Y$的帮助后，$X$的信息熵的减小程度。但发现记号$g(X,Y)$貌似是对$X$与$Y$对称的，而右边看上去并不是，这是为什么？

实际上，右边也是关于$X,Y$对称的，引入联合分布的熵（十分自然的定义）：
$$
H(X,Y)=-\sum_x\sum_y p_{X,Y}(x,y)\log p_{X,Y}(x,y)
$$

这样就有：
$$
g(X,Y)=H(X)+H(Y)-H(X,Y)
$$

证明：只需证$H(X,Y)-H(X|Y)=H(Y)$

实际上
$$
\begin{align*}
&-\sum_x\sum_y p_{X,Y}(x,y)\log p_{X,Y}(x,y)+\sum_{y}\sum_{x} p_Y(y)p_{X|Y}(x|y)\log p_{X|Y}(x|y)\newline

\newline
&= -\sum_x\sum_y p_{X,Y}(x,y)\log p_{X,Y}(x,y)+\sum_{y}\sum_{x} p_{X,Y}(x,y)\log \frac{p_{X,Y}(x,y)}{p_Y(y)}
\newline

\newline
&= -\sum_{y}\sum_{x} p_{X,Y}(x,y)\log p_Y{y}=-\sum_{y}p_{Y}(y)\log p_Y(y)
\end{align*}
$$

证毕

比如决策树的构建中，我们要求信息增益最大化，这样构造的树能尽可能快的完成分类