Basic Concepts in Information Theory

摘要: 本文主要记录熵、相对熵、互信息以及交叉熵等概念. 因为这些概念在机器学习以及数据挖掘，例如信息检索在做文本特征选择的时候，反复用到，因此在这里做个记录.

熵和信息量

熵用于衡量随机变量组成的序列的随机性(不确定性或者不可预测性). 离散分布的熵定义为:

H=−∑mi=1Pilog2Pi

是一个关于p的concave function. 对数以2为底表示将这个随机序列编码需要的比特数.
需要特别注意的是对于离散随机变量，熵的值并不依赖于变量本身，而仅仅依赖于这些变量的概率.
可以自然的拓展到多变量的联合熵,joint entropy. 假设(x,y)服从分布p(x,y),那么(x,y)的联合熵定义为:

H(p)=−∑x∈X∑y∈Yp(x,y)logp(x,y)

条件熵(conditional entropy) 表示已知一个变量的信息时，另一个变量的熵:

对于连续的情况，熵的定义为:

H=∫∞−∞p(x)lnp(x)dx

以下概念均以熵为基础概念.

相对熵

假设对同一个离散随机变量x,有两种不同形式的离散概率分布p(x)和q(x). 为了衡量x在不同分布下的距离，定义相对熵:

DKL(p(x),q(x))=∑xq(x)lnq(x)p(x)

相对熵也称为KL(Kullback-Leibler)距离. 然而相对熵并不是一个真正的metric，如上式，DKL不满足对称性和三角不等式.

互信息

假设有两个不同变量的概率分布p(x)和q(y). 互信息是指在获取一个变量的信息后，另一个变量的不确定性的减少量:

I(p;q)=H(p)−H(p|q)=∑x,yr(x,y)log2r(x,y)p(x)q(y)

r(x,y)为x,y的联合概率分布函数. 结合相对熵，可以看到，互信息是联合概率分布r(x,y)与概率分布乘积p(x)q(y)的相对熵, 表示x,y的分布与统计独立的差异度. 互信息也称为信息增益(information gain)

交叉熵

假设x的真实分布是p(x): x ~ p(x), 而模型认为x服从另一种分布q(x)，那么定义于X和q之间的交叉熵为:

H(X,q)=Ep[H(X)]=H(X)+DKL(p|q)

其中DKL(p|q)表示将x错误的认为服从q(x)分布的代价，这个代价同样用熵表示.

当x是离散变量时,H(X,q)=−∑xp(x)logp(x)，是连续变量时,H(X,q)=−∫−Xp(x)logp(x).

熵之间的关系图:
Alt text
Individual (H(X),H(Y)), joint (H(X,Y)),
and conditional entropies for a pair of
correlated subsystems X,Y
with mutual information I(X; Y).

参考材料

模式分类
Information Theory
CS769 Spring 2010 Advanced Natural Language Processing
熵的社会学意义
阮一峰的网络日志