信息论入门
信息用来消除人们对事物的不确定性。信息量越大，不确定性减少程度越大，与信息作用大小无决定关系，因为对接收者来说，所获得的信息可能事关重大，也可能无足轻重。ing….
自信息
通过观测实际概率为$p$的事件的出现频率，可以推测实际概率，也就是得到信息。单一事件发生时所包含的信息量多寡，用$I(p)$来衡量，称为自信息。
$I(p)$必须具有以下属性：
- 非负：$I(p)\geq 0$
- 如果事件必然发生，则不能从出现频率中得到信息：$I(1)=0$
- 如果两个独立事件（联合概率是独立概率之和）出现，则可得到的总信息为各信息之和：$I(p_1\cap p_2)=I(p_1)+I(p_2)$
- 是概率$p$的连续、单调函数
从以上属性可导出，$I(p)=\log {1\over p}=-\log p$，以2为底数时单位为bit。
一个随机产生的事件所包含的自信息，只与事件发生的概率相关。事件发生的概率越低，在事件真的发生时，接收到的信息中，包含的自信息越大。这里的想法是，比较不可能发生的事情，当它发生了，会提供更多的信息。
例如，抛一次硬币的得到的自信息为$I({1\over 2})=1$bit，抛n次硬币就会得到n bit的自信息。
信息熵
设n个独立事件，以符号$\{a_1,a_2,…,a_n\}$表示，若第i个事件发生则符号$a_i$出现，各事件的概率为$\{p_1,p_2,…,p_n\}$。
现在信息源提供了N组符号（类似流），如果某组中出现$a_i$，则可得$a_i$的$-\log p_i$自信息，N组符号中$a_i$的出现概率为$Np_i$，则$a_i$的总自信息为$-(Np_i)\log p_i$，n个符号的总自信息为$I=\sum^n_{i=1}(-Np_i)\log p_i$，平均自信息为$I/N=-\sum^n_{i=1}p_i\log p_i$。注意到$\lim_{x\rightarrow 0}(-x\log(x))=0$，因此我们可以特别定义当$p_i=0时$有$-p_i\log p_i=0$。这个平均自信息也被称为信息熵。信息熵为不确定性的量度。信息熵越大，不确定性越大，把它搞清楚所需的信息量也越大。
正式地，假设有一组概率，即离散随机变量的概率分布$P=\{p_1,p_2,…,p_n\}$，则分布$P$的信息熵为$H(P)=-\sum^n_{i=1}p_i\log p_i$。
推广到连续随机变量的概率分布$P(x)$，信息熵为$H(P)=-\int P(x)\log P(x)dx$。
综上，一个概率分布$P$的熵就是它的互信息$I(p)$的期望值。
联合熵
$$
H(X,Y)=-\sum_{x\in \mathcal{X}}\sum_{y\in \mathcal{Y}} p(x,y)\log p(x,y)
$$
条件熵
$$
H(Y|X)=\sum_{x\in \mathcal{X}}^n p(x)H(Y|X=x)\\
=-\sum_{x\in \mathcal{X}} p(x)\sum_{y\in \mathcal{Y}} p(y|x)\log p(y|x)\\
=-\sum_{x\in \mathcal{X}}\sum_{y\in \mathcal{Y}}p(x,y)\log p(y|x)\\
=-\sum_{x\in \mathcal{X}}\sum_{y\in \mathcal{Y}}p(x,y) \log \frac{p(x,y)}{p(x)}
$$
互信息
$$
I(X;Y)=H(Y)-H(Y|X)\\
=-\sum_{x\in \mathcal{X}}\sum_{y\in \mathcal{Y}}p(x,y)\log \frac{p(x,y)}{p(x)p(y)}
$$
在决策树ID3中用到的信息增益（表示得知特征$X$的信息而是的类$Y$的信息的不确定性减少的程度）等价于训练数据集中类与特征的互信息。另外决策树C4.5用到的信息增益比则为$\frac{I(X;Y)}{H(Y)}$。
联合熵、条件熵和互信息之间的关系可参见下图：
以上基于香农熵理论（Shannon），实际信息论中还有很多别的熵定义，参见维基百科 。
