最大熵马尔可夫模型
虽然HMM可以达到很高的精确度,但是我们发现它需要大量的体系结构创新来处理未知的单词、后退、后缀等等。如果我们能够以一种干净的方式将任意的特性直接添加到模型中,这将会容易得多,但是这对于生成模型(如HMMs)来说很难。幸运的是,我们已经看到了这样做的模型:逻辑回归模型!但logistic回归不是一个序列模型;它为单个观察分配一个类。然而,我们可以将逻辑回归转化为一个判别序列模型,只需对连续的单词运行它,使用分配给前一个单词的类作为下一个单词分类的一个特征。当我们以这种方式应用逻辑回归时,它被称为最大熵马尔可夫模型或MEMM5
设单词序列为 W = w_{1}^n ,标签序列 T = t_{1}^n 。在隐马尔可夫模型中,为了计算使P(T|W)最大化的最佳标记序列,我们依赖于贝叶斯规则和概率P(W|T):
相比之下,在MEMM中,我们直接计算后验 P(T|W) ,训练它区分可能的标签序列:
考虑只标记一个单词。一个多项式逻辑回归分类器可以用与隐马尔可夫模型不同的方法计算单概率 P(t_i | w_{i},t_{i-1}) 。图8.12通过箭头的方向直观地显示了差异;HMMs计算似然(观察词以标记为条件),而MEMMs计算后验(标记以观察词为条件)。
MEMM中的特征
当然,我们不会只在 w_i 和 t_i 上建立MEMMs。使用判别序列模型的原因是它更容易包含许多特性。图8.13显示了这些附加特性的图形直观。
基本的MEMM词性标记器以观察词本身、相邻词、以前的标记以及各种组合为条件,使用的特征模板如下:
特征模板用于自动填充训练和测试集中每个实例的特征集。因此,我们的示例Janet/NNP will/MD back/VB the/DT bill/NN,当 w_i 为词back时,将生成以下特征:
此外,还需要处理未知单词的特性,表示单词的拼写或形状的属性:
针对 w_i 可有如下情况:
- w_i包含特定前缀
- w_i包含特定后缀
- w_i包含数字
- w_i包含一个大写字母
- w_i包含一个字符
- w_i全是大写字母
- w_i 的单词形状
- w_i 的短单词形状
- w_i 是大写,有数字和破折号
- w_i 是大写字母,Co., Inc.等在3个字以内
单词的形状特征用于表示单词的抽象字母图案,方法是将小写字母映射为“x”,将大写字母映射到“X”,将数字映射到“d”,并保留标点符号。 因此,例如I.M.F将映射到X.X.X. 和DC10-30将映射到XXdd-dd。 还使用第二类较短的字形特征。 在这些特征中,连续的字符类型被删除,因此DC10-30将被映射到Xd-d,但是I.M.F仍将映射到X.X.X. 例如,well-dressed将生成以下非零值特征值:
已知单词的特征,如式8.33中的模板,对训练集中出现的每个单词进行计算。未知单词的特征也可以对训练中的所有单词进行计算,或者只对频率低于某个阈值的训练单词进行计算。已知单词模板和单词签名特性的结果是一组非常大的特征。通常使用特征截断,如果训练集中的特征数小于5,则会抛出这些特征。
解码和训练MEMMs
然后,结合输入单词 w_i 的这些特征,计算出最有可能的标签序列, w_i 附近l长度窗口以内的单词 w_{l-l}^{i+l} 系列(左边的l个单词和右边的l个单词),和当前单词 w_i 前k个标签 t_{i-k}^{i-1} 如下(使用θ来代替权重而不是w,以避免和单词w弄混):
我们应该如何解码才能找到这个最优的标签序列T ?将logistic回归转化为序列模型最简单的方法是构建一个局部分类器,从左到右对每个单词进行分类,对句子中的第一个单词进行硬分类,然后对第二个单词进行硬决策,以此类推。这被称为贪心解码算法,因为我们贪婪地为每个单词选择最好的标签,如图8.14所示。
贪心算法的问题在于,在进入下一个单词之前,对每个单词做出艰难的决定,分类器不能使用来自未来决定的证据。虽然贪心算法非常快,偶尔也有足够的精度来使用,但一般来说,硬决策会导致性能下降太多,我们不使用它。相反,我们使用维特比算法解码MEMM,就像使用HMM一样,找到对整个句子最优的词性标记序列。
例如,假设我们的MEMM只以前面的标记 t_{i-1} 和观察到的单词 w_i 为条件。具体来说,这涉及到用 p(t_i | t_{i-1},w_i) 的适当值填充 N\times T 数组,并在继续执行时维护反向指针,与HMM Viterbi一样,当表被填满时,我们只需按照最后一列中的最大值返回指针来检索所需的标签集。Viterbi的hmm风格应用程序的必要更改只与我们如何填充每个单元格有关。由式8.20可知,维特比方程的递推步骤计算状态j的时间t的维特比值为:
HMM的实现:
MEMM只需要对后一个公式稍加修改,将a和b的先验概率和似然概率替换为直接后验概率:
MEMMs中的学习依赖于我们提出的用于逻辑回归的监督学习算法。在给定一系列观测值、特征函数和相应隐藏状态的情况下,利用梯度下降法训练权值,使训练语料库的对数似然值达到最大。
所介绍的MEMM和HMM模型的一个问题是,它们完全是从左到右运行的。虽然Viterbi算法仍然允许当前的决策受到未来决策的间接影响,但是如果一个关于词wi的决策可以直接使用关于未来标记 t_{i+1} 和 t_{i+2} 的信息,那么它将更有帮助
实现双向性的一种方法是切换到一个更强大的模型,称为条件随机场(CRF)。CRF是一个无向的图形模型,这意味着它不会在每个时间步长计算每个标记的概率。相反,CRF在每个时间步长上计算一个小圈子上的对数线性函数,这是一组相关特性。与MEMM不同的是,这些可能在将来的时间步骤中包含单词的输出特性。最佳序列的概率同样由维特比算法计算。因为CRF对所有标签序列的概率进行标准化,而不是对单个时间t的所有标签进行标准化,所以训练需要计算所有可能标签的和,这使得CRF训练非常慢。