最大熵马尔可夫模型
信息与熵
熵(信息熵)可被认为是系统不确定性(混乱程度)的度量，熵值越大，系统越混乱。
一个X值域为{x1, ..., xn}的随机变量的熵值H定义为：
[math]\displaystyle{ H(X)=E(I(X)) }[/math]
其中，E 代表了期望函数，而I(X)是X的信息量（又称为信息本体），熵是随机变量的各值域概率及其信息量积的加总。
信息量是用来衡量单一随机变量发生时所含信息的的多寡，随机变量发生的概率越低，其发生后消除系统不确定性的能力越强，所含信息量就越大。所以信息量与随机变量概率成反比。注意：信息量与信息作用的概念不同。
[math]\displaystyle{ I(X)=log(\frac{1}{P(X)})=-logP(X) }[/math]
由对数函数可以看出信息量的一个特性：若[math]\displaystyle{ p(c) = p(a)p(b) }[/math], 则[math]\displaystyle{ I(c) = I(a) + I(b) }[/math]
把信息量公式带入熵公式展开得：
[math]\displaystyle{ H(X)=E(I(X))=-\sum_{x \in X} p(x)logp(x) }[/math]
熵满足如下不等式：
[math]\displaystyle{ 0 \le H(X) \le log|X| }[/math]
[math]\displaystyle{ \sum_{x \in X} p(x)=1 }[/math]
|X|是X的取值个数，当且仅当X的分布是均匀分布式时右边的等号成立，也就是说X服从均匀分布式时，熵最大。
最大熵原理
当熵最大时，则表示该系统内各随机事件(变量)发生的概率是近似均匀的，等可能性的，根据这一性质我们可以将已知事件作为约束条件，作出最不偏倚的假设，求得可使熵最大化的概率分布。
我们先引入特征函数f(x,y)，f(x,y)是一个二值函数，表示当x,y满足某一事实其特征函数值为1。
[math]\displaystyle{ f_i(x,y) \in \{0,1\},i=1,2,...,m }[/math]
在真实的语言环境里，某一观测值对应的隐藏状态是由上下文环境(观测，状态)决定的，引入特征函数可使我们能够自由的选取特征(观测或状态的组合)。可以说是用特征(观测组合)来代替观测，避免生成模型HMM, naive bayes的观测独立性假设的局限性。
我们可以根据大小为T的训练数据D={(x,y)}得到一个经验期望和模型期望。
[math]\displaystyle{ \tilde{E}(f_i)=\frac {1}{n} \sum_{x,y} p(x,y)f_i(x,y) }[/math]
[math]\displaystyle{ E(f_i)=\frac {1}{n} \sum_{x,y} p(x)p(y|x)f_i(x,y) }[/math]
我们假设经验期望与模型期望相等，那么就存在多个满足此约束的有关任意特征函数fi的条件概率分布的集合C，于是有：
[math]\displaystyle{ C=\{ P|E_p(f_i)=\tilde{E_p}(f_i), i=1,2,...,m \} }[/math]
最大熵原理认为，从不完整的信息（例如有限数量的训练数据）推导出的唯一合理的概率分布应该在满足这些信息提供的约束条件下拥有最大熵值——即熵最大的分布在条件概率集合是最优的，那么最大熵模型变为凸函数的约束优化问题
[math]\displaystyle{
\max_{P \in C} H(P)=-\sum_{x,y} P(x)P(y|x)logP(y|x)
}[/math]
[math]\displaystyle{ s.t. E_p(f_i)=\tilde{E_p}(f_i), i=1,2,...,m }[/math]
[math]\displaystyle{ s.t. \sum_{y}p(y|x)=1 }[/math]
我们通常使用拉格朗日对偶原理来将原式变形为无约束的极值求解：
[math]\displaystyle{ L(\omega, \alpha, \beta)=f(\omega) + \sum_{i=1}^k\alpha_i g_i(\omega) + \sum_{j=1}^l\beta_j h_j(\omega) }[/math]
[math]\displaystyle{ \Lambda(p, \tilde{\lambda})=H(y|x) + \sum_{i=1}^m \lambda _i(E_p(f_i) - \tilde{E_p}(f_i)) + \lambda _{m+1}(\sum_{y \in Y} P(y|x)-1) }[/math]
在拉格朗日函数对p求偏导，并使之等于0，求解方程，省略N步整型可得下式: (其实是俺不会推..)
[math]\displaystyle{ p_{\tilde{\lambda}}^*(y|x)=\frac{1}{Z_{\tilde{\lambda}}(x)}exp(\sum_{i=1}^m \lambda_i f_i(x,y)) }[/math]
[math]\displaystyle{ Z_{\tilde{\lambda}}(x)=\sum_{y \in Y}exp(\sum_{i=1}^m \lambda_i f_i(x,y)) }[/math]
其中[math]\displaystyle{ \lambda_i }[/math]是模型中各个特征函数[math]\displaystyle{ f_i(x,y) }[/math]的参数向量，Z是以观测序列X为条件概率的归一化因子，其意义是将复杂的联合分布分解为多个因子的乘积(最大团)，实质是得到归一化因子Z(x)均衡给定x任意y的条件概率分布[math]\displaystyle{ p(y_j|x) }[/math]数值(局部归一)，最大熵模型学习过程就是估计出这两种有关x,y的参数
[math]\displaystyle{ Z_{\tilde{\lambda}}(x)=\sum_{y \in Y}\prod_{i=1}^m exp(\lambda_i f_i(x,y)) }[/math]
最大熵马尔可夫模型
最大熵模型是在已知经验分布的基础上求解有关特征函数f(x,y)的最优的P(y|x)概率分布，但它的随机变量y有相互独立的假设，所以不能很好的描述y_i, x_i与y_{i-1}的关系，而HMM又有观测独立性假设不能自由的选择特征，所以我们希望找到一个能同时服从马尔可夫性假设和服从最大熵假设的模型解决序列标注的问题
模型形式
对比隐马尔可夫模型(HMM)
[math]\displaystyle{ P(X)=\sum_y \prod_{i=1}^T p(y_i|y_{i-1})p(x_i|y_i) }[/math]
状态序列Y，观测序列X，两个状态转移概率: 从y_{i-1}到y_i的条件概率分布 [math]\displaystyle{ p(y_i|y_{i-1}) }[/math]，状态y_i的输出观测概率 [math]\displaystyle{ p(x_i|y_i) }[/math]，初始概率[math]\displaystyle{ p_0(y) }[/math]。隐马尔可夫模型依赖于已知数据的概率分布，已经历史经验来决定现实决策，但实际能提供训练的数据是少量且稀疏的，我们不能枚举所有的数据分布状况，所以需要在数据稀疏的条件下估计未知x,y的条件概率。
最大熵马尔可夫模型(MEMM)
[math]\displaystyle{ p_{y_{i-1}}(y_i|x_i)=\frac{1}{Z_{\tilde{\lambda}}(x_i,y_{i-1})}exp(\sum_{a}^m \lambda_a f_a(x_i,y_i)),i=1,2,...,T }[/math]
用[math]\displaystyle{ p(y_i| y_{i-1},x_i) }[/math]分布来替代HMM中的两个条件概率分布，它表示从先前状态，在观测值下得到当前状态的概率，即根据前一状态和当前观测预测当前状态。每个这样的分布函数[math]\displaystyle{ p_{y_{i-1}}(y_i|x_i) }[/math]都是一个服从最大熵的指数模型。
左边是hmm模型，右边是memm模型
HMM 双状态转移条件概率的输出独立性假设，在训练过程通过统计[math]\displaystyle{ x,y,y_{i-1} }[/math]的联合概率[math]\displaystyle{ p(y_{i-1},y),p(y,x) }[/math]，在解码中通过联合概率反向递推[math]\displaystyle{ p(y_i|y_{i-1},x) }[/math]的条件概率
MEMM 限定条件求最优条件概率分布，在训练过程中收敛一组有关特征函数[math]\displaystyle{ f_i(x,y) }[/math]的参数向量[math]\displaystyle{ \lambda_i }[/math]，以及有关[math]\displaystyle{ x_i }[/math]与[math]\displaystyle{ y_{i-1} }[/math]的正则化因子，在解码过程中直接求得条件概率[math]\displaystyle{ p(y_i| y_{i-1},x_i) }[/math]
优势与局限
隐马尔可夫模型因为其严格的观测独立性假设，对于具有多个互相作用的观测状态组合以及中长范围的元素依赖的数据环境识别特征的能力有限，而最大熵模型特征选择灵活，且不需要额外的独立性假设或内在约束。
隐马尔可夫是生成模型，学习的是联合概率，必须列举所有观察序列的可能值，而最大熵马尔可夫模型可以在不完整信息下有推导出未知数据的能力来。
最大熵马尔可夫模型本质是有向概率图模型，即每个y_i只依赖于x_i，并且每个component(y_i, y_{i-1}, x_i)(特征组合)之间是独立且做局部归一，可能存在label bias(标记偏置)的问题(概率很低)。
学习方法(召唤大神)
改进迭代算法(IIS)
随机梯度下降(SGD)
参考文献
- Roman Klinger, Katrin Tomanek, Classical Probabilistic Models and Conditional Random Fields