最大熵模型(Maximum Entropy Models)(二)

上面《MaxEnt: 最大熵模型(Maximum Entropy Models)(一)》 其实就是讲了下熵，下面我们继续最大熵模型(Maximum Entropy Models)。

最大熵原理指出，当我们需要对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设。在这种情 况下，概率分布最均匀，预测的风险最小。因为这时概率分布的信息熵最大，所以人们称这种模型叫“最大熵模型”。我们常说，不要把所有的鸡蛋放在一个篮子 里，其实就是最大熵原理的一个朴素的说法，因为当我们遇到不确定性时，就要保留各种可能性。说白了，就是要保留全部的不确定性，将风险降到最小。---- 摘自《Google黑板报》作者：吴军

link

========

继续用【参考5】的例子。

“学习”这个词可能是动词，也可能是名词。可以可以被标为主语、谓语、宾语、定语……
令x 1 表示“学习”被标为名词， x 2 表示“学习”被标为动词。令y 1 表示“学习”被标为主语， y 2 表示被标为谓语，y 3 表示宾语， y 4 表示定语。得到下面的表示：

p ( x 1 ) + p ( x 2 ) = 1 ∑ i = 1 4 p ( y i ) = 1

如果没有其他的知识，根据信息熵的理论，概率趋向于均匀。所以有：

p ( x 1 ) = p ( x 2 ) = 0.5 p ( y 1 ) = p ( y 2 ) = p ( y 3 ) = p ( y 4 ) = 0.25

但是在实际情况中，“学习”被标为定语的可能性很小，只有0.05。我们引入这个新的知识：p ( y 4 ) = 0.05 ，在满足了这个约束的情况下，其他的事件我们尽可能的让他们符合自然，符合均匀分布：

p ( x 1 ) = p ( x 2 ) = 0.5 p ( y 1 ) = p ( y 2 ) = p ( y 3 ) = 0.95 3

嗯，如果再加入一个知识，当“学习”被标作动词的时候，它被标作谓语的概率为0.95，这个其实是很自然的事情。都已经是动词了，那么是谓语的可能性就很大了：

p ( y 2 | x 1 ) = 0.95

已经有了两个知识了，第二个还是条件概率的知识，那么其他的我们尽可能的让他们不受约束，不受影响，分布的均匀一些，现在应该怎么让他们符合尽可能的均匀分布呢？

其实就是使熵尽可能的大就行了。也就是有个分布p，他尽可能的把训练集中的知识表示出来，损失最小，并且还能够保证p的熵最大：

p ∗ = arg max p H ( p )

那约束是什么呢？

用概率分布的极大似然对训练语料表示如下，其中是C o u n t ( x , y ) 在语料中出现的次数，N为总次数：

p ˉ ( x , y ) = 1 N × C o u n t ( x , y )

在实际问题中，由于条件x和结果y取值比较多样化，为模型表示方便起见，通常我们将条件x和结果y表示为一些二制特征。对于一个特征( x 0 , y 0 ) ，定义特征函数：

f ( x , y ) = { 1 : y = y 0 & x = x 0 0 : o t h e r s

特征函数在样本中 的期望值为：

p ˉ ( f ) = ∑ ( x i , y i ) p ˉ ( x i , y i ) f ( x i , y i )

其中p ˉ ( x , y ) 在前面已经数了，数数次数就行。

有了训练集，我们就能够训练一个模型出来，特征f在这个模型中 的期望值为：

p ( f ) = ∑ ( x i , y i ) p ( x i , y i ) f ( x i , y i ) = ∑ ( x i , y i ) p ( y i | x i ) p ( x i ) f ( x i , y i ) = ∑ ( x i , y i ) p ( y i | x i ) p ˉ ( x i ) f ( x i , y i )

其中p ˉ ( x i ) 为x出现的概率，数数归一化就行。

好了，约束来了，有了样本的分布，有了模型，那么对每一个特征(x,y)，模型所建立的条件概率分布要与训练样本表现出来的分布相同：

p ( f ) = p ˉ ( f )

==========

目标函数有了，约束有了，归纳一下最大熵模型(Maximum Entropy Models)。

p ∗ = arg max p ∈ P H ( Y | X )

P={p|p是y|x的概率分布并且满足下面的条件}，对训练样本，对任意给定的特征f i ：

p ( f i ) = p ˉ ( f i )

展开：

p ∗ = arg max p ∈ P ∑ ( x , y ) p ( y | x ) p ˉ ( x ) log 1 p ( y | x )

约束P为：

P = ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ p ( y | x ) ∣ ∣ ∣ ∣ ∣ ∀ f i : ∑ ( x , y ) p ( y | x ) p ˉ ( x ) f i ( x , y ) = ∑ ( x , y ) p ˉ ( x , y ) f i ( x , y ) ∀ x : ∑ y p ( y | x ) = 1 ⎫ ⎭ ⎬ ⎪ ⎪ ⎪ ⎪

========

都齐了，该求解了吧？哈哈，有没有看过wiki上的关于拉格朗日乘子Lagrange Multiplier 的问题，恰好这里面有个例子就是求最大熵的，哈哈。所以我们可以用拉格朗日乘子法来求解。

对于有k个约束的优化问题：

 

max H ( p ) s . t . : C i ( p ) = b i , i = 1 , 2 , . . . , k

可以引入k个拉格朗日算子

 

Λ = [ λ 1 , λ 2 , . . . , λ k ] T

，那么拉格朗日函数为：

 

L ( p , λ ) = H ( p ) + ∑ i = 1 k λ i [ C i ( p ) − b i ]

OK，咱们开始一步一步的带入求解∂ L ∂ p = 0 。

由于约束中有两部分组成，对于第二部分，我们引入拉格朗日算子为γ :

 

L ( p , Λ , γ ) = ∑ ( x , y ) p ( y | x ) p ˉ ( x ) log 1 p ( y | x ) +         ∑ i = 1 k λ i ∑ ( x , y ) ( p ( y | x ) p ˉ ( x ) f i ( x , y ) − p ˉ ( x , y ) f i ( x , y ) ) +       γ ⎛ ⎝ ∑ y p ( y | x ) − 1 ⎞ ⎠

下面就是就偏微分=0计算最优解了：

 

∂ L ∂ p ( y | x ) = p ˉ ( x ) ( log 1 p ( y | x ) − 1 ) + ∑ i = 1 k λ i p ˉ ( x ) f i ( x , y ) + γ = 0

求得最优解的参数形式：

 

p ∗ ( y | x ) = e ∑ i λ i f i ( x , y ) + γ p ˉ ( x ) − 1

但是里面还有参数，所以我们必须求得γ ∗ 和Λ ∗ 。

巧妙的是我们发现最后节的后面部分有个类似的常数项：

 

e ∑ i λ i f i ( x , y ) + γ p ˉ ( x ) − 1 = e ∑ i λ i f i ( x , y ) e γ p ˉ ( x ) − 1

而且有意思的是，前面问题的第二个约束中有：

 

∀ x : ∑ y p ( y | x ) = 1

从而：

 

∑ y p ∗ ( y | x ) = ∑ y ( e ∑ i λ i f i ( x , y ) e γ p ˉ ( x ) − 1 ) = 1 e γ p ˉ ( x ) − 1 ∑ y e ∑ i λ i f i ( x , y ) = 1 e γ p ˉ ( x ) − 1 = 1 ∑ y e ∑ i λ i f i ( x , y ) = Z ( x )

也就是式子中的关于γ 的常数项我们用关于Λ 的常数项进行代替了，这样参数就剩下一个了：

 

p ∗ ( y | x ) = Z ( x ) e ∑ i λ i f i ( x , y ) Z ( x ) = 1 ∑ y e ∑ i λ i f i ( x , y )

那么剩下的一个参数Λ 应该怎么进行求解呢？

解法以及最大熵模型与最大似然估计的关系在参考5中很详细，还有GIS以及IIS的方法进行求解，以后再写《MaxEnt: 最大熵模型(Maximum Entropy Models)(三)》。