从马尔科夫到最大熵到条件随机场

来自:远洋号(微信号:seaboat-top),作者:wj seaboat

马尔科夫模型

对于某个系统包含了n个有限状态,某个状态随着时刻推移而转移到另一个状态。如果t时刻状态与前面m个时刻相关则称为m阶马尔科夫链,即马尔可夫过程是一个随机过程,系统从一个状态到另外一个状态存在转移概率,而转移概率通过前m个状态来计算出来。这就是马尔科夫模型,即MM,也可认为是随机有限状态自动机。

马尔科夫模型例子

根据 ‘the quick brown fox jumps over the lazy dog’这句话,要得到马尔科夫链,先给每一个单词设定成一个状态,然后计算状态间转换的概率。

当用大量文本去做统计的时候,会得到更大的状态转移矩阵,例如 the 后面可以连接的单词,及相应的概率

TIM图片20190503134318

隐马尔科夫模型

马尔科夫模型能处理直接观察的序列的概率问题,通过马尔科夫假设能建立起马尔科夫链,从而解决一些序列问题。但有时候观察的对象并不是我们待处理的目标对象,它的规律隐含在观察对象中,观察的事件和隐含事件存在一定的相关关系,这时候就要用到隐马尔科夫模型,即HMM。

实际上隐马尔科夫模型是一个双重随机过程,过程中包含状态序列和观察序列。第一重随机过程是状态经过随机转移生成状态序列,而第二重随机过程则是根据状态序列随机转移生成观察序列。

TIM图片20190503214654

HMM重要假设

  1. 齐次马尔科夫性假设,即任意时刻t的状态只依赖于前一时刻的状态,与其他时刻的状态及观测序列无关。

  2. 观测独立性假设,即任意时刻t的观测只依赖于该时刻状态,与其他时刻的观测和状态无关。

  3. 不动性假设,即状态与具体的时间无关。


最大熵模型

最大熵模型是一种根据熵来确定的模型,最大熵模型认为在所有可能的概率模型中熵最大模型是最好的。也就是说我们只掌握未知分布的部分信息,而契合已知分布的有多个,然后通过熵最大来确定分布。

事件发生的概率只要满足所有已知约束,并且不对任何未知信息做假设,对未来做等概率处理。熵最大时,系统的不确定性最大。

TIM图片20190504005900

最大熵马尔科夫模型

隐马尔科夫模型中存在观察独立性假设,也就是任意时刻的观察只依赖于该时刻的状态,与其它时刻的观察和状态无关。但很多场景中我们需要将观察的特征考虑进去,即认为某个时刻的状态取决于前一时刻状态和当前时刻的观察。而如果再使用最大熵模型来学习这些条件概率,则此为最大熵马尔科夫模型。

images

每个时刻的条件概率如下,其中Z用于归一化,为每个特征函数的权重参数,f为特征函数,根据实际情况可以定义很多特征函数的。

条件随机场

对于序列的处理,如果既想要考虑观察与状态之间的特征,也要考虑前后状态之间的特性,则会考虑条件随机场,更具体的是线性条件随机场。条件随机场摒弃了隐马尔科夫中的齐次马尔科夫性假设和观测独立性假设,模型更加复杂,但能学习到更多特征。

条件随机场引入了特征函数,在实际使用中我们可以定义很多个特征函数,包括各种状态的特征和观察的特征。

如果再加上归一化,最终条件随机场的条件概率为,

条件随机场的训练与隐马尔科夫模型的训练不同,隐马尔科夫模型是对各类条件概率进行建模,而条件随机场是从整体去拟合函数,可以采用极大似然估计法。

推荐↓↓↓
程序员数学之美
上一篇:以贝叶斯思维看待世界 下一篇:x * x >= 0 一定成立吗?