自然界中的熵:

自封闭系统的运动总是倒向均匀分布:

 

一.信息论基础

1.自信息:

信息: i(x) = -log(p(x))

 

a.如果说概率p是对确定性的度量

b.那么信息就是对不确定性的度量

c.当一个小概率事件发生了，这个事件的信息量很大；反之如果一个大概率事件发生了，这个事件的信息量就很少。

2.熵：自信息的期望

熵是对平均不确定性的度量.

熵的理解:熵其实定义了一个函数(概率分布函数)到一个值(信息熵)的映射:P(x)->H(函数->值)

3.联合熵和条件熵

a.联合熵：两个随机变量X，Y的联合分布，可以形成联合熵Joint Entropy，用H(X,Y)表示。

b.条件熵：在随机变量X发生的前提下，随机变量Y发生所新带来的熵定义为Y的条件熵，用H(Y|X)表示，用来衡量在已知随机变量X的条件下随机变量Y的不确定性,  用H(X|Y)表示

4.相对熵

相对熵，又称互熵，交叉熵，鉴别信息,Kullback熵，Kullback-Leible散度等,设p(x)、q(x)是X中取值的两个概率分布，则p对q的相对熵是:

在一定程度上，相对熵可以度量两个随机变量的“距离”

5.互信息

两个随机变量X，Y的互信息定义为X，Y的联合分布和各自独立分布乘积的相对熵，用I(X,Y)表示：

性质:

I(x,y)>>0：x和y关联强度大

I(x,y)=0：x和y无关

I(x,y)<<0：x和y具有互补的分布

6.各个熵之间的关系

7.信息增益和熵的关系

a.信息增益是针对一个一个的特征而言的，就是看一个特征t，系统有它和没它的时候信息量各是多少，两者的差值就是这个特征给系统带来的信息量，即增益。

b.系统含有特征t的时候信息量很好计算，就是刚才的式子，它表示的是包含所有特征时系统的信息量。

8.信息论与机器学习的关系

 

二.最大熵模型

1.最大熵原理:

a.承认已知事物(知识)

b.对未知事物不做任何假设

c.最大熵存在且唯一(凸优化)

 

理解最大熵例子:

已知：

“学习”可能是动词，也可能是名词。

“学习”可以被标为主语、谓语、宾语、定语……

令x1表示“学习”被标为名词， x2表示“学习”被标为动词。

令y1表示“学习”被标为主语， y2表示被标为谓语，y3表示宾语， y4表示定语。得到下面的表示：

　　p(x1) + p(x2) =1    p(y1) + p(y2) + p(y3) + p(y4) =1

根据无偏原则:

　　p(x1) = p(x2) = 0.5

　　p( y1) = p( y2) = p( y3) = p( y4) = 0.25

引入新知识:

　　若已知：“学习”被标为定语的可能性很小，只有0.05

　　　　p( y4) = 0.05　　

　　仍然坚持无偏原则：　　

　　　　p(x1) = p(x2) = 0.5　　

　　　　p( y1)= p( y2) = p( y3) = 0.95/3

再次引入新知识:

　　当“学习”被标作动词的时候，它被标作谓语的概率为0.95

　　　　p( y2 | x1) = 0.95

　　除此之外，仍然坚持无偏见原则，尽量使概率分布平均。

问：怎么样能尽量无偏见的分布？

概率平均分布 等价于 熵最大

　　问题转化为：计算X和Y的分布，使H(Y|X)达到最大值，并且满足条件　　

　　　　

 

2.最大熵模型:

a.定义条件熵:

b.模型目的:

　　

c.定义特征函数:

　　

d.约束条件:

　　

　　

特征函数理解:

　　

 

特征函数 f(x,y) 是一个二值函数， 当 x 与 y 满足事实时取值为 1 ，否则取值为 0 。比如对于如下数据集：

数据集中，第一列为 Y ，右边为 X ，可以为该数据集写出一些特征函数，数据集中得特征函数形式如下：

为每个 <feature,label> 对 都做一个如上的特征函数，用来描述数据集数学化。

 

约束条件理解:

 

针对原问题，首先引入拉格朗日乘子λ0,λ1,λ2, ..., λi，定义拉格朗日函数，转换为对偶问题求其极大化：

(后面会专门讲拉格朗日乘子法)

然后求偏导:

令上述的偏导结果等于0，解得：

将求得的最优解P*(y|x)带回之前建立的拉格朗日函数L:

得到关于λ的式子:

其中:

　　

三.最大熵模型与极大似然函数

1.极大似然估计MLE

　　

　　理解一般形式:

　　　　

　　　　

2.对最大熵拉格朗日乘子式取对数:

　　

　　将最优解p*代入MLE:

　　

　　其中:

　　　　

3.MaxEnt与MLE两者比较:

　　a.极大似然估计得到的结果:

　　　　

　　b.之前对偶问题的极大化解得到的结果: