11. Information and Entropy

CS › Data Science
$$\huge\textbf{Information and Entropy} $$

1. Information Entropy

1.1. Information & Entropy

奈奎斯特，哈特利和香农研究了一类特殊的通信，即技术系统里的通信，他们假设通信的唯一目的是在接受后重新产生输出数据样式——即，信息是为了消除不确定性。香农给出的定义是，当我破门收到一条消息 $m$ 时，假设最初有 $n$ 个事件 $E_1,E_2,…,E_n$ 是等可能的，$E$ 表示他们当中的一个, 这些事件有对应的概率 $p_1,p_2,…,p_n$, 那么消息 $m$ 的熵为

$$H(m) := H(p_1,p_2,…,p_n)=-\sum_{i=1}^np_i\log_2p_i $$

其中, 对数的底是随机的, 如果以 $2$ 为底, 则单位为 $bit$, 如果以自然对数的底数 $e$ 为底, 则单位为 $nat$

1.2. Properties

香农描述了信息度量的三个性质: 单调性, 非负性和可加性

  1. 单调性：非确定性越高的事件，其信息量越高

  2. 非负性：信息是非负的，可以看作是概率延伸的必然

  3. 可加性：总信息量可拆解为各部分的信息量累加，这是广度量的一种表现

香农从数学上证明了满足上述三个条件的随机变量不确定性度量函数具有唯一形式：

$$H(X)=-C\sum_{x\in X}p(x)\log x $$

其中 $C$ 为常数，我们不妨归一化，令 $C = 1$ 就得到了信息熵公式

2. Computations

2.1. Joint Entropy

联合熵是一个集合中变量之间不确定性的衡量手段

$def.$ Joint Entropy

对于俩个和离散的随机变量 $X,Y$，联合熵的定义为：

$$H(X,Y)=-\sum_x\sum_yp(x,y)\log_2P(x,y) $$

其中 $x,y$ 是 $X$ 和 $Y$ 的特定值，相应地，$P(x,y)$ 是这些值一起出现的联合概率。如果 $P(x,y) = 0$，则定义

$$P(x,y)\log_2p(x,y) $$

对于两个以上的随机变量 $X_1,X_2,…,X_n$，联合熵的定义为：

$$H(X_1,X_2,…,X_n)=-\sum_{x_1}\sum_{x_2}…\sum_{x_n}p(x_1,x_2,…,x_n)\log_2p(x_1,x_2…,x_n) $$

$thm.$ Common Properties

$$\max_{X_i\in X}\{H(X_i)\}\leq H(X)\leq \sum_{i=1}^nH(X_i)\quad (X=\{X_1,X_2,…,X_n\}) $$

2.2. Conditional Entropy

条件熵量化了在一直一个随机变量 $X$ 的条件下，描述为值得随机变量 $Y$ 所需的信息量。基于 $X$ 条件下 $Y$ 的信息熵，用 $H(Y|X)$ 表示，也就是 $H(Y|X=x)$ 在 $X$ 取遍所有可能的 $x$ 之后平均的结果。

设给定随机变量 $X,Y$，我们有：

$$\begin{equation*} \begin{split} H(Y|X)&=-\sum_xp(x)H(Y|X=x)\\ &=\sum_x-p(x)\sum_yp(y|x)\log p(y|x)\\ &=-\sum_{x,y}p(x,y)\log\frac{p(x,y)}{p(x)} \end{split} \end{equation*} $$

$thm.$ Common Properties

  1. 条件熵 $H(Y|X)$ 完全等于 $0$ 当且仅当 $Y$ 的值完全取决于 $X$

  2. 条件熵 $H(Y|X)=H(X)$ 当且仅当 $Y$ 和 $X$ 相互独立

  3. 条件熵链式法则：

$$H(Y|X)=H(XY)-H(X) $$
  1. 条件熵的 $\text{Bayes}$ 规则
$$H(Y|X)+H(X)=H(X|Y)+H(Y) $$

2.3. Relative Entropy

$def.$ Relative Entropy

相对熵（Relative Entropy）又称为 $KL$ 散度（$\text{Kullback-Leibler Divergence}$），简称为 $KLD$ 或 信息散度，信息增益。设 $P(x),Q(X)$ 为随机变量 $X$ 上的两个概率分布，相对熵的定义为如下

对于离散型随机变量：

$$D_{KL}(P||Q)=-\sum_{i}P(i)\ln\frac{Q(i)}{P(i)} $$

对于连续型随机变量：

$$D_{KL}(P||Q)=\int_{-\infty}^{+\infty}p(x)\ln\frac{p(x)}{q(x)} $$

$KL$ 散度是两个概率分布 $P$ 和 $Q$ 的非对称性的度量，可以用来度量基于 $Q$ 的编码来编码来自 $P$ 的样本所需要的额外的位元数。

$thm.$ Common Properties

  1. 非负性：由于对数函数是上凸函数，所以根据相对熵的定义，有 (吉布斯不等式)
$$\begin{equation*} \begin{split} D_{KL}(P||Q)&=\sum_{x\in X}\log\frac{P(x)}{Q(x)}\\ &=-E\bigg[\log\frac{Q(x)}{P(x)}\bigg]\\ &\geq -\log E(\frac{Q(x)}{P(x)})\\ &=-\log\sum_{x\in X}P(x)\frac{Q(x)}{P(x)}\\ &=-\log \bigg[\sum_{x\in X}Q(x)\bigg]\\ &=0 \end{split} \end{equation*} $$
  1. 不对称性：相对熵是两个概率分布的不对称性的度量，即：
$$D_{KL}(P||Q)\not =D_{KL}(Q||P) $$

​ 我们常使用熵的均值来进行规约:

$$let\ D(P,Q)=\frac{[D_{KL}(P||Q)+D_{KL}(Q||P)]}{2} $$

2.4. Cross Entropy

$def.$ Cross Entropy

在信息论中，基于相同事件测度的两个概率分布 $p$ 和 $q$ 的交叉熵指的是，当基于一个“非自然”（相对于“真实的”分布 $p$ 而言）的概率分布 $q$ 进行编码时，在事件集合中唯一地标识一个事件所需的平均 $bit$ 数，基于概率分布 $p$ 和 $q$ 的交叉熵定义为：

$$H(p,q)=-\int_{X}p(x)\log q(x)dr(x)=E_P(-\log q)=H(p)+D_{KL}(p||q) $$

$thm.$ Common Properties

  1. 不对称性：
$$H(A,B)\not =H(B,A) $$

3. Variability

3.1. Mutual Information

$def.$ Mutual Information

对两个离散随机事件集 $X$ 和 $Y$，事件 $y_i$ 的出现给出关于 $x_i$ 的信息量，即为互信息量。

两个离散随机变量 $X$ 和 $Y$ 的互信息定义为：

$$I(X;Y):=\sum_{x\in X}\sum_{y\in Y}p(x,y)\log\bigg(\frac{p(x,y)}{p(x)p(y)}\bigg) $$

两个连续随机变量 $X$ 和 $Y$ 的互信息定义为：

$$I(X;Y):=\int_X\int_Yp(x,y)\log\bigg(\frac{p(x,y)}{p(x)p(y)}\bigg)dxdy $$

其中 $p(x,y)$ 是 $X$ 和 $Y$ 的联合密度函数，$p(x),p(y)$ 分别是 $X$ 和 $Y$ 的边缘概率密度函数

$thm.$ Common Principles

  1. 如果 $X$ 和 $Y$ 互相独立，则显然地：
$$\log\bigg(\frac{p(x,y)}{p(x)p(y)}\bigg)=0 $$

​ 也即他们的互信息为 $0$

  1. 互信息是非负的

  2. 互信息是对称的：

$$I(X;Y)=I(Y;X) $$
  1. 互信息的等价表示：
$$\begin{equation*} \begin{split} 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{split} \end{equation*} $$

​ 其中 $H(X)$ 和 $H(Y)$ 是边缘熵，$H(X|Y)$ 和 $H(Y|X)$ 是条件熵，$H(X,Y)$ 是联合熵

3.2. Information Increasement

如果 $P$ 为数据的真实分布，$Q$ 为数据的理论分布，根据相对熵的性质，对于离散型随机变量，我们有：

$$\text{Gain}(P,Q)=-\sum P(i)\ln \frac{Q(i)}{P(i)} $$

对于连续型随机变量，我们有：

$$\text{Gain}(P,Q)=\int_{-\infty}^{+\infty}p(x)\ln\frac{p(x)}{q(x)}dx $$

更一般地，如果 $P$ 和 $Q$ 是集合 $X$ 上的测度函数，$Q$ 关于 $P$ 绝对连续，从 $P$ 到 $Q$ 的信息增益定义为

$$\text{Gain}(P,Q)=-\int_X\ln\frac{dQ}{dP}dP $$

3.3. Information Gain

信息增益率指的是属性的信息增益两相对于该属性熵值的比值

$$\operatorname{GainRatio}(T,P)=\frac{Gain(T,P)}{Entropy(T,P)} $$

3.4. $\text{Gini}$ Coefficient

$\text{Gini}$ 系数指的是另外一种数据不纯度的测量方法，其定义如下

$$\operatorname{Gini}(D):=1-\sum_{i=1}^mp_i^2 $$

其中的 $m$ 表示数据集 $D$ 中类别 $C$ 的个数，$p_i$ 表示 $D$ 中任意一个记录属于 $C_i$ 的概率

4. Maximum Entropy

$def.$ Maximum Entropy Principle

一个正确的概率分布该满足下面的两个条件：

​ <1> 服从样本数据中的一直统计证据

​ <2> 使熵最大化

$$p^*=arg\max_{p\in P} H(p) $$

其中，$P$ 表示所有可能的概率分布

$def.$ Learning of Maximum Entropy Model

设特征函数 $f(x,y)$ 满足

$$f(x,y)= \left\{ \begin{array}{**lr**} 1,\ iff … \\0,\ else \end{array} \right. $$

特征函数 $f(x,y)$ 关于经验分布 $\overline P(X,Y)$ 的期望值，用 $E_{\overline P}(f)$ 表示为

$$E_{\overline P}(f)=\sum_{x,y}\overline P(x,y)f(x,y) $$

特征函数 $f(x,y)$ 关于条件分布 $P(X|Y)$ 和经验分布 $\overline P(X)$ 的期望值，用 $EP(f)$ 表示为

$$E_{\overline P}(f)=\sum_{x,y}\overline P(x)\overline P(y|x)f(x,y) $$

如果模型可以从训练集中学习，我呢吧就可以假设这两个期望相等，即：

$$E_{\overline P}(f)=EP(f) $$

$def.$ Maximum Entropy Model

设满足所有约束条件的模型集合为

$$E_{\overline P}(f_i)=EP(f_i)\\ $$

定义在条件概率分布 $P(X|Y)$ 上的条件熵为

$$H(P)=\sum_{x,y}\overline P(x)\overline P(y|x)f(x,y) $$