极大似然, 最大熵

29 Jun 2015

正如HMM可以理解为贝叶斯在序列变量上的应用,CRF则可以理解为最大熵和HMM在序列变量上的应用。所以要理解CRF 需要先理解贝叶斯,HMM以及概率图模型的相关知识。

极大似然估计

什么是极大似然估计呢? 考虑一个抛硬币的例子。假设这个硬币正面跟反面轻重不同。我们把这个硬币抛80次 (即,我们获取一个采样并把正面的次数记下来,正面记为H,反面记为T)。并把抛出一个正面的概率记为p, 抛出一个反面的概率记为1 − p(因此,这里的p即相当于上边的)。假设我们抛出了49个正面,31 个反面,即49次H,31次T。假设这个硬币是我们从一个装了三个硬币的盒子里头取出的。 这三个硬币抛出正面的概率分别为p = 1 / 3, p = 1 / 2, p = 2 / 3. 这些硬币没有标记,所以我们无法知道哪个是哪个。 使用最大似然估计,通过这些试验数据(即采样数据),我们可以计算出哪个硬币的可能性最大。 这个可能性函数取以下三个值中的一个:

P(H=49, T=31| p =1/3) = (1/3)^49 * (1 - 1/3)^31 == 0.00
P(H=49, T=31| p =1/2) = (1/2)^49 * (1 - 1/2)^31 == 0.012
P(H=49, T=31| p =2/3) = (2/3)^49 * (1 - 2/3)^31 == 0.054

我们可以看到当p=2/3时,可能性函数取得最大值,这就是p的最大似然估计。

Ref: Wiki

最大熵原理

熵是描述事物不确定程度的度量,换种说法也就是衡量不知道信息程度,熵越大对一个事物知道的就越少。最大熵原理是说当我们 并不确切的知道某个事情的时候,我们对该事情的估计总是非常谨慎的根据现有信息去假设,而不添加任何主观判断。

熵的计算公式: H(x) = -SUM[P(xi)log(P(xi))]

熵的性质:

例子 一个快餐店提供 3 种食品:汉堡(B)、鸡肉(C)、鱼(F)。价格分别是 1 元、2 元、3 元。已知人们在这家店的平均消费是 1.75 元,求顾客购买这 3 种食品的概率。如果你 假设一半人买鱼另一半人买鸡肉,那么根据熵公式,这不确定性就是 1 位(熵等于 1)。但 是这个假设很不合适,因为它超过了你所知道的事情。我们已知的信息是:

p(B)+ p(C)+ p(F)=1
1p(B)+2p(C)+3p(F)=1.75
关于对概率分布的不确定性度量,熵:
S = −p(B)log(p(B))− p(C)log(p(C))− p(F)log(p(F))
对前两个约束,两个未知概率可以由第三个量来表示,可以得到:
p(C) = 0.75−2p(F)
p(B)=0.25+ p(F)
把上式代入熵的表达式中,熵就可以用单个概率 p(F) 来表示:
S =−(0.25+ p(F))log((0.25+ p(F)))−(0.75−2p(F))log((0.75−2p(F)))− p(F)log(p(F))
对这个单变量优化问题,求出 
p(F) = 0.216 时熵最大,有 p(B) = 0.466 , p(C)=0.318和S =1.517。

以上,我们根据未知的概率分布表示了约束条件,又用这些约束条件消去了 两个变量,用剩下的变量表示熵, 最后求出了熵最大时剩余变量的值,结果就求出了一个符 合约束条件的概率分布, 它有最大不确定性,我们在概率估计中没有引入任何偏差。

Ref:HJT

极大似然和最大熵都是目标约束条件,换种说法也就是我们对问题的解决大方法,根据这两个大方法还有现有的统计数据得到 各个独立事件的发生情况,作为模型。

贝叶斯

输入变量XV(i)= (x1, x2, x3, …, xm)是特征变量,y是需要预测的类别变量。根据Bayes定律可得到:

p(y|XV) = p(XV|y)*p(y)/p(XV) (1)

公式(1)中的分母不是很重要,可以理解为一个标准化常量,

p(y)*p(XV/y) = p(XV, y)

根据前面的多元联合概率的计算,

P(A1,A2,A3,A4) = P(A1)*A(A2|A1)*P(A3|A1,A2)*P(A4|A1,A2,A3),

所以:

p(y)*p(XV/y) = p(y)*p(xm|x(m-1), x(m-2)....x1, y)

最后,p(y|XV) ∝ p(y, XV) = p(y)*p(xm|x(m-1), x(m-2)....x1, y).

Ref:Classical Probabilistic Models and Conditional Random Fields