HMM,MEMM和CRF:统计建模方法的比较分析

LITElric 2018-05-18

本文提出了隐马尔可夫模型(HMM),最大熵马尔可夫模型(MEMM)和条件随机场(CRF)的比较分析。HMM,MEMM和CRF是三种流行的统计建模方法,常用于模式识别和机器学习问题。让我们更详细地探讨每种方法。

隐马尔可夫模型(HMM)

“Hidden”一词表示这样一个事实,即只有系统发布的符号是可观察的,而用户不能查看状态之间潜在的random walk。本领域的许多人将HMM识别为有限状态机。

HMM,MEMM和CRF:统计建模方法的比较分析

Hidden Markov Model (HMM)

HMM的优点

HMM具有强大的统计基础和高效的学习算法,可以直接从原始序列数据中进行学习。它允许以本地可学方法的形式一致地处理插入和删除惩罚,并且可以处理可变长度的输入。它们是序列概况最灵活的概括。它还可以执行多种操作,包括多重对齐,数据挖掘和分类,结构分析和模式发现。它也很容易合并到库中。

HMM的缺点

HMM仅依赖于每个状态及其相应的观察对象:

序列标注除了与单个词相关之外,还与观察到的序列长度,单词上下文等有关。

目标函数和预测目标函数不匹配:

HMM获取状态和观察序列的联合分布P(Y,X),而在估计问题中,我们需要一个条件概率P(Y | X)。

最大熵马尔可夫模型(MEMM)

HMM,MEMM和CRF:统计建模方法的比较分析

Maximum Entropy Markov Models

MEMM考虑了相邻状态之间的依赖关系和整个观察序列,因此具有更好的表达能力。MEMM不考虑P(X),这会减少建模工作量并学习目标函数和估计函数之间的一致性。

MEMM标签偏差

HMM,MEMM和CRF:统计建模方法的比较分析

Viterbi algorithm decoding of MEMM

在图3中,状态1倾向于转换到状态2,状态2倾向于同时停留在状态2。

P(1→1→1→1)= 0.4×0.45×0.5 = 0.09,P(2→2→2→2)= 0.2×0.3×0.3 = 0.018,

P(1→2→1→2)= 0.6×0.2×0.5 = 0.06,P(1→1→2→2)= 0.4×0.55×0.3 = 0.066。

但是,最佳状态转换路径是1> 1> 1> 1。为什么?

这是因为状态2比状态1具有更多的可转换状态,因此降低了转换概率--MEMM倾向于选择具有更少可转换状态的状态。这种选择被称为标签偏差问题。CRF很好地解决了标签偏差问题。

条件随机场(CRF模型)

HMM,MEMM和CRF:统计建模方法的比较分析

CRF模型解决了标签偏差问题,并消除了HMM中两个不合理的假设。当然,这个模型也变得更加复杂。

MEMM采用局部方差归一化,而CRF采用全局方差归一化。

另一方面,MEMM无法找到相应的参数来满足以下分配:

abc→a / A b / B c / C p(ABC | abc)= 1

a be→a / A b / D e / E p(ADE | abe)= 1

p(A | a)p ,A)p(C | c,B)= 1

p(A | a)p(D | b,A)p(E | e,D)= 1

但CRFs可以。

生成模型或判别模型

假设o是观测值,m是模型。

a)生成模型:无限样本>概率密度模型=生成模型>预测

如果你模拟P(o | m),它是一个生成模型。其基本思想是首先建立样本的概率密度模型,然后使用该模型进行推断预测。样品无限或尽可能大的要求是常识。该方法来自统计力学和贝叶斯理论。

HMM直接模拟转换概率和表型概率,并计算共现概率。因此,它是一个生成模型。

b)判别模型:有限样本>判别函数=判别模型>预测

如果您对条件概率P(m | o)进行建模,则它是区分性模型。其基本思想是建立具有有限样本的判别函数,直接研究预测模型而不考虑样本的生成模型。其代表性理论是统计学习理论。

CRF是一种判别模型。MEMM不是一个生成模型,而是一个基于状态分类的具有有限状态的模型。

拓扑结构

HMM和MEMM是一个有向图,而CRF是一个无向图。

全局最优或局部最优

HMM直接模拟转移概率和表型概率,并计算共现概率。

MEMM基于转移概率和表型概率建立共现概率。它计算条件概率,只采用局部方差归一化,使其易陷入局部最优。

CRF计算全局范围内的归一化概率,而不是像MEMM那样在局部范围内。这是一个最佳的全局解决方案,解决了MEMM中的标签偏差问题。

CRF的优点和缺点

优点

与HMM相比:由于CRF没有HMM那样严格的独立性假设,因此它可以适应任何上下文信息。其功能设计灵活(与ME相同)。

与MEMM相比:由于CRF计算全局最优输出节点的条件概率,它克服了MEMM中标签偏差的缺点。

与ME相比:当计划用于标记的观测序列可用时,CRF计算整个标记序列的联合概率分布,而不是在给定的当前状态条件下定义下一个状态的状态分布。

缺点

在算法的训练阶段,CRF在计算上非常复杂。当新的数据变得可用时,这使得重新训练模型变得非常困难。

结论:

本文详细介绍了隐马尔可夫模型(HMM),最大熵马尔可夫模型(MEMM)和条件随机场(CRF)之间的对比分析。在这篇文章中,我们明确地知道CRF和MEMMS主要是区分序列模型,而HMM主要是生成序列模型。它是构成HMM基础的贝叶斯规则。相反,基于MaxEnt模型的CRF和MEMM基于过渡和可观察特征。