序列标注问题为,给定输入序列(观察序列)$X=\{x_1, x_2, ..., x_N\}$,我们希望找到最可能的状态序列$Y=\{y_1, y_2, ..., y_N\}$。最常用的三个模型分别为HMM(隐马尔科夫模型),MEMM(最大熵马尔科夫模型)和CRF(条件随机场)。按照这个顺序,我们可以粗略地认为越靠后的模型越优,也越复杂。

HMM属于生成模型(Generative Model),而MEMM和CRF属于判别模型(Discriminative Model)。简单来讲,生成模型是y决定x:对$p(x,y)=p(x|y)p(y)$联合概率分布进行建模;判别模型是x决定y:对$p(y|x)$条件概率分布进行建模。所以,从能力上来说,生成模型更“强大”,由全概率公式$p(x)=\sum_{y}{p(x,y)}$,生成模型有能力完全“生成”一个x。如果仅仅是为了对x进行分类,生成模型效果往往不如判别模型,原因我们可以粗略的理解为生成模型花了很多无用功在建模联合概率上。

下面我们分别介绍这三个模型。

HMM

HMM是生成模型,对于输入序列X和状态序列Y,HMM建模p(X,Y)。设序列长度为N,状态个数为K。按照链式法则对$p(X,Y)$进行展开得到
$p(X,Y)=p(X|Y)P(Y)=p(x_1|Y)p(x_2|x_1,Y)...p(x_N|x_1,...,x_{N-1},Y) \\ p(y_1)p(y_2|y_1)...p(y_N|y_1,...,y_{N-1})$
按照上面的公式,会发现模型参数暴增到指数级,为了简化问题,易于求解,HMM对上面的最复杂的形式做了假设:

  1. 对于p(Y),假设后一个状态之只和前一个状态有关,即$p(Y)=p(y_1)p(y_2|y_1)...p(y_N|y_{N-1})$,这样,可以将参数缩小到一个状态转移矩阵和一个初始状态分布,其参数个数为$K^{2} + K$,构成一阶马尔科夫链
  2. 对于p(X|Y),假设每个输入序列的项只与当前位置的状态有关,即$p(X|Y)=p(x_1|y_1)p(x_2|y_2)…p(x_N|y_N)$,这样,可以得到一个项目生成矩阵(符号生成矩阵),其参数个数为$KV$,其中$V$是所有项目(符号)的个数

HMM的概率图模型如下
hmm graph model

所以,HMM模型的参数一共有三部分:初始状态分布$\pi$,状态转移矩阵$A$,和项生成矩阵$B$。我们将HMM模型表示为$\mu = (\pi,A,B)$。有了这些表示,下面介绍HMM的三个基本问题

  1. 给定输入序列X和模型$\mu$,求概率$p(X|\mu)$
  2. 给定输入序列X和模型$\mu$,求其最有可能的状态序列,即$argmax_{Y}p(Y|X,\mu)$
  3. 给定输入序列X(可能包含对应的ground truth状态序列Y),估计模型参数$\mu$使得$p(X|\mu)$最大

对于前两个问题,解法的核心在于动态规划。由于输入序列X所有可能的状态序列个数为$K^{N}$个,不可能穷尽,我们需要利用HMM中一阶马尔科夫的假设,来构造动态规划的状态矩阵,降低复杂度。具体的算法称为Viterbi算法(解决问题2)和前向后向算法(解决问题1)。

对于问题3,如果包含ground truth状态序列Y,估计参数很简单,使用最大似然对导数取0即可。如果Y不可见,可以使用EM算法。

MEMM

MEMM是判别模型,对于输入序列X和状态序列Y,MEMM建模p(Y|X)。按照链式法则对$p(Y|X)$展开得到
$p(Y|X)=p(y_1|X)p(y_2|y_1,X)...p(y_N|y_1,...y_{N-1},X)$
类似于HMM中的一阶马尔科夫假设,MEMM认为后一个状态只依赖于前一个状态,所以
$p(Y|X)=p(y_1|X)p(y_2|y_1,X)...p(y_N|y_{N-1},X)$
MEMM模型使用softmax的形式对上述概率进行刻画

$p(y_i|y_{i-1},X)=\frac{exp(w \cdot f(y_i,y_{i-1},X))}{\sum_{y}{exp(w \cdot f(y,y_{i-1},X))}}$

上式中的$f$是特征函数,对于输入变量生成一个特征的向量,$w$为特征向量的权值。由此可见,MEMM与HMM最大的不同,在于MEMM不对输入序列做任何独立性假设,当前状态的概率不仅依赖于前一个状态和对应的输入项,还依赖于整个输入序列。而且由于MEMM是判别模型,可以很自然地引入特征函数,从而可以刻画很多HMM无法刻画的特征,例如词是否首字母大写、词的suffix等等。另外,由于MEMM是局部归一化(针对序列不同的位置i,利用softmax做概率归一),所以MEMM的参数估计不用进行动态规划,效率较高,但也因此存在标记偏置问题(label bias),CRF模型解决了这一问题。

MEMM的概率图模型如下(准确地说,模型中的每个词都应伸出N个边指向所有的状态节点)
memm graph model

CRF

CRF同样是判别模型,建模p(Y|X)。和MEMM不同的是,CRF使用了全局的特征函数,针对全局做概率归一化,从而克服了MEMM的标记偏置问题。

$p(Y|X)=\frac{exp(w \cdot f(Y,X))}{\sum_{Y^{'}}{exp(w \cdot f(Y^{'},X))}}$

上面的softmax形式,如果不做任何假设,不可能应用于实际问题,因为它太“大”了。所有可能的$Y^{'}$有$K^{N}$种,这是不能承受的。因此CRF做了和MEMM、HMM类似的假设

$f(Y,X)=\sum_{i=1}^{N}{f(y_i,y_{i-1},X)}$

也就是说,全局特征函数等于局部特征函数的加和,局部特征函数的形式和MEMM一样,所以,动态规划算法又可以用了。

CRF的概率图模型如下(准确地说,模型中的每个词都应伸出N个边指向所有的状态节点)
crf graph model

关于标记偏置问题,简单的来理解,由于MEMM的归一是局部的,如果训练数据中,所有状态$s_1$后面全是状态$s_2$,就会导致$p(s_2|s_1,X)=\frac{exp(w \cdot f(s_2,s_1,X))}{\sum_{s}{exp(w \cdot f(s,s_1,X))}}=1$,此时无论输入序列X是什么,转移概率都是1。标记偏置导致的结果是,那些下一状态个数较少(熵小)的状态更容易被走到。

引用CRF原论文中的一段话

MEMMs and other non-generative finite-state models based on next-state classifiers, such as discriminative Markov models (Bottou, 1991), share a weakness we call here the label bias problem: the transitions leaving a given state compete only against each other, rather than against all other transitions in the model. In probabilistic terms, transition scores are the conditional probabilities of possible next states given the current state and the observation sequence. This per-state normalization of transition scores implies a “conservation of score mass” (Bottou, 1991) whereby all the mass that arrives at a state must be distributed among the possible successor states. An observation can affect which destination states get the mass, but not how much total mass to pass on. This causes a bias toward states with fewer outgoing transitions. In the extreme case, a state with a single outgoing transition effectively ignores the observation. In those cases, unlike in HMMs, Viterbi decoding cannot downgrade a branch based on observations after the branch point, and models with statetransition structures that have sparsely connected chains of states are not properly handled. The Markovian assumptions in MEMMs and similar state-conditional models insulate decisions at one state from future decisions in a way that does not match the actual dependencies between consecutive states.

以及一个示例

参考资料:

  1. Lafferty J, McCallum A, Pereira F C N. Conditional random fields: Probabilistic models for segmenting and labeling sequence data[J]. 2001.
  2. Michael Collins. Log-Linear Models, MEMMs, and CRFs
  3. Sequence Tagging with HMM / MEMM / CRF