NLP基础理论0x1–信息论

信息论

   信息是关于事物的运动状态和规律的认识，它可以脱离具体的事物而被摄取、传输、存贮、处理和变换。

  信息论，就是用数理统计方法研究信息的基本性质以及度量方法，研究最佳解决信息的摄取、传输、存贮、处理和变换的一般规律的科学。它的成果将为人们广泛而有效地利用信息提供基本的技术方法和必要的理论基础。

　　信息论的研究范围分成三种不同类型：

　　(1)狭义信息论是一门应用数理统计方法来研究信息处理和信息传递的科学。它研究存在于通讯和控制系统中普遍存在着的信息传递的共同规律，以及如何提高各信息传输系统的有效性和可靠性的一门通讯理论。

　　(2)一般信息论主要是研究通讯问题，但还包括噪声理论、信号滤波与预测、调制与信息处理等问题。

    (3)广义信息论不仅包括狭义信息论和一般信息论的问题，而且还包括所有与信息有关的领域，如心理学、语言学、神经心理学、语义学等。

  狭义信息，是针对通信意义上的信息而言的。1948年，美国数学家C. E. Shannon发表的《通信的数学理论》。差不多同一时候，美国数学家N. Wiener发表了《时间序列的内插、外推和平滑化》以及专著《控制论》。他们分别解决了狭义信息的度量问题，并且得到了相同的结果。

   Shannon的论文还给出了信息传输问题的一系列重要成果，建立了比较完整而系统的信息理论，这就是Shannon信息论，也叫狭义信息论。Shannon理论的建立，在很大程度上澄清了通信的基本问题。它以概率论为工具，刻画了信源产生信息的数学模型，导出了度量概率信息的数学公式；同时，它利用概率论的方法，描述了信道传输信息的过程，给出了表征信道传输能力的容量公式；此外，它还建立了一组信息传输的编码定理，论证了信息传输的一些基本界限。Shannon的理论是通信科学发展史上的一个转折点，它使通信问题的研究从经验转变为科学。

   作为运动状态表现的广义信息既具有一定的形式又具有一定的内容。在原则上，数学可以精确地刻画形式。但是，如何从数学上定量地刻画内容，至今仍是一个巨大的难题。一般的情形是用数学来表达形式，用语言来描述内容。但是，对于通信领域，通信只不过是信息的传输，因此可以把它看作是“在通信的一端精确地或近似地复现另一端所挑选的消息”，“至于通信的语义方面的问题，与工程方面的问题是没有关系的”。由于通信的任务只是单纯地复制消息，并不需要对信息的语义作任何处理和判断。只要在通信接收端把发送端发出的消息从形式上复制出来，也就同时复现了它的语义内容。

   信息论的主要内容用语言来阐述。 一种简洁的语言（以英语为例）通常有两个重要特点： 首先，最常用的词（比如”a”, “the”, “I”）应该比不太常用的词（比如”benefit”, “generation”, “mediocre”）要短一些；其次，如果句子的某一部分被漏听或者由于噪声干扰（比如一辆车辆疾驰而过）而被误听，听者应该仍然可以抓住句子的大概意思。而如果把电子通信系统比作一种语言的话，这种健壮性（robustness）是不可或缺的。将健壮性引入通信是通过信道编码完成的。信源编码和信道编码是信息论的基本研究课题。

 自信息量I(ai)表示一个消息ai出现后所带来的信息量，用其概率的负对数来表示，即I(ai)=-log2p(ai)，因此I(ai)是非负值，并且是概率p(ai)的单调递减函数。

熵

在信息论中，熵表示的是不确定性的量度。信息论的创始人香农在其著作《通信的数学理论》中提出了建立在概率统计模型上的信息度量。他把信息定义为“用来消除不确定性的东西”。

   1 Chaos（混沌），无序.物理学：除非施加能量，否则熵不会降低 举例：把房间弄乱很容易，整理干净不容易
   2 是不确定性(Uncertainty)的衡量, 不确定性越高，熵越高，我们从一次实验中得到的信息量越大.
   3 熵也可以被视为描述一个随机变量的不确定性的数量。一个随机变量的熵越大，它的不确定性越大。那么，正确估计其值的可能性就越小。越不确定的随机变量越需要大的信息量用以确定其值。

熵在信息论中的定义如下：
如果有一个系统S内存在多个事件S = {E1,…,En}, 每个事件的机率分布 P = {p1, …, pn}，则每个事件本身的讯息为
Ie = − log2pi
（对数以2为底，单位是位元(bit)）
Ie = − lnpi
（对数以e为底，单位是纳特/nats）
如英语有26个字母，假如每个字母在文章中出现次数平均的话，每个字母的讯息量为
I_e = -\log_2 {1\over 26} = 4.7
；而汉字常用的有2500个，假如每个汉字在文章中出现次数平均的话，每个汉字的信息量为
I_e = -\log_2 {1\over 2500} = 11.3
整个系统的平均消息量为
H_s = \sum_{i=1}^n p_i I_e = -\sum_{i=1}^n p_i \log_2 p_i
这个平均消息量就是消息熵。因为和热力学中描述热力学熵的玻耳兹曼公式形式一样，所以也称为“熵”。
如果两个系统具有同样大的消息量，如一篇用不同文字写的同一文章，由于是所有元素消息量的加和，那么中文文章应用的汉字就比英文文章使用的字母要少。所以汉字印刷的文章要比其他应用总体数量少的字母印刷的文章要短。即使一个汉字占用两个字母的空间，汉字印刷的文章也要比英文字母印刷的用纸少。
实际上每个字母和每个汉字在文章中出现的次数并不平均，因此实际数值并不如同上述，但上述计算是一个总体概念。使用书写单元越多的文字，每个单元所包含的讯息量越大。
I(A)度量事件A发生所提供的信息量，称之为事件A的自信息，P(A)为事件A发生的概率。如果一个随机试验有N个可能的结果或一个随机消息有N个可能值，若它们出现的概率分别为p1,p2,…，pN,则这些事件的自信息的和：[H=-SUM(pi*log(pi)),i=1,2…N]称为熵。

熵的公式
熵H(X)=-Σx∈Ωp(x)logxp(x)
– 假设PX(x)是随机变量X的分布
– 基本输出字母表是Ω
– 单位：bits
• 熵是X的平均信息量，是自信息量的期望
E(X)=Σx∈Ω p(x) x
I(X)=-logp(x)，取2为底，I(X)=-log2p(x)
E(I(X)=E(-log2p(x))= Σx∈Ω p(x)(-log2p(x)) = H(X)
H(X)=H(p)=Hp(X)=HX(p)=H(pX)

熵的例子
• 掷均匀硬币，Ω={H,T}
p(H)=.5, p(T)=.5
H(p)=-0.5log20.5 (-0.5log20.5)=1
• 32面的均匀股子，掷股子
H(p)=-32((1/32)log2(1/32))=5
• 事实上，掷的次数21=2, 25=32(perplexity)
• 掷不均匀硬币
p(H)=0.2, p(T)=0.8, H(p)=0.722（不确定性更大）
p(H)=0.01, p(T)=0.99, H(p)=0.081

什么时候H(p)=0?
– 试验结果事先已经知道
– 即：∃x∈Ω, p(x)=1; ∀y∈Ω, p(y)=0 if y≠x
• 熵有没有上限？
– 没有一般的上限
– 对于|Ω|=n，H(p)≤-log2n
– 均衡分布的熵是最大的

等概率分布
– 2个输出的等概率分布，H(p)=1bit
– 32个输出的等概率分布，H(p)=5bits
– 43亿输出的等概率分布，H(p)=32bits
• 非等概率分布
– 32个输出，2个0.5，其余为0，H(p)=1bit
– 怎样比较具有不同数量输出的“熵”?困惑度(perplexity)

困惑度(perplexity)即混乱度
G(p)=2的H(p)次方，在NLP中，如果词表中的词具有统一的分布概率，则最难预测，熵最大，混乱度最高
反之，分布越不均衡，熵越小，混乱度越小

条件熵
给定随机变量X的情况下，随机变量Y的条件熵定义为：
H(Y|X)=Σx∈Ωp(x)H(Y|X=x)
  = Σx∈Ωp(x)(-Σ y∈Ψp(y|x)log2p(y|x))
  =-Σx∈Ω Σ y∈Ψp(y|x)p(x)log2p(y|x)
  = -Σx∈Ω Σ y∈Ψp(x,y)log2p(y|x)
p(x,y)是加权，权值是没有条件的

联合熵(joint entropy)
如果X, Y 是一对离散型随机变量X, Y ~ p(x, y)，X, Y 的联合熵H(X, Y) 为：
(X,Y)被视为一个事件
H(X,Y)=-Σx∈Ω Σ y∈Ψp(x,y)log2p(x,y)
联合熵实际上就是描述一对随机变量平均所需要的信息量
联合熵(joint entropy)
如果X, Y 是一对离散型随机变量X, Y ~ p(x, y)，X, Y 的联合熵H(X, Y) 为：
(X,Y)被视为一个事件
H(X,Y)=-Σx∈Ω Σ y∈Ψp(x,y)log2p(x,y)
联合熵实际上就是描述一对随机变量平均所需要的信息量

熵的性质
熵是非负的
H(X)≥0
Chain Rule
H(X,Y)=H(Y|X) H(X)
H(X,Y)=H(X|Y) H(Y)
H(X,Y)≤H(X) H(Y)，X和Y独立时相等
H(Y|X)≤H(Y)，条件熵比熵小

互信息（Mutual Information）
如果( X, Y ) ~ p(x, y)，X, Y 之间的互信息I(X; Y) 为：I (X; Y) = H(X) –H( X | Y )
推导为：I(x,y)=log2p(x,y)/(p(x)p(y))
互信息I (X; Y) 是在知道了Y 的值后X 的不确定性的减少量。即，Y 的值透露了多少关于X 的信息量。
• 比如计算两个词的搭配
I(伟大,祖国)=log2p(伟大,祖国)/(p(伟大)p(祖国))
• 此值较高，说明“伟大”和“祖国”是一个比较强的搭配
I(的,祖国)=log2p(的,祖国)/(p(的)p(祖国))
• 此值较低，因为p(的)太高，“的”和“祖国”不是一个稳定的搭配
互信息性质
I(x,y)>>0：x和y关联强度大
I(x,y)=0：x和y无关
I(x,y)<<0：x和y具有互补的分布
由于H(X, X) = 0, 所以，
H(X) = H(X) –H(X|X) = I(X; X)
这一方面说明了为什么熵又称自信息，另一方面说明了两个完全相互依赖的变量之间的互信息并不是一个常量，而是取决于它们的熵。