词性标注

part-of-speech词性标签一般分两类,一类是closed class type,这类词性所含的内容一般比较固定,很少有新增元素,如介词;另一类是open class type,这类相反,经常会有新的元素加入,如名词。前者一般为功能词,比较短且出现的比较频繁。最常见的open class type词性有:名词,动词,副词和形容词。

在英文中,名词也分为两类:专有名词(proper noun)和通用名词。专有名词一般指代特定的东西,如“东方明珠塔”,在英文中,专有名词前面不用加定冠词。通用名词又可分为可数名词和不可数名词。

动词有不同的时态,第三人称单数,正在进行时,过去完成时。

副词主要用来修饰动词,也可以是其他副词或者动词短语。大致分为:方位副词(home, here, downhill),程度副词(extremely, very, somewhat),manner副词(slowly),时间副词(yesterday,Monday)。

closed class包含以下几类:介词,小品词(与动词构成短语的副词或介词),冠词,连词,代词,数词,助动词(包含情态动词和be动词)。

penn Treebank pos tag

pos tagging是一项消岐工作,很多单词存在多种可能的tag。有些单词虽然存在多种POS tag的可能性,但是因为大部分情况下都是某一种特定的tag(如a大部分时候都是DT),因此,如果将每个单词都tag为其最常见的pos tag,形成的标注模型可以作为其他模型对比的baseline。书中表示,该baseline的准确率能达到92%左右,而目前最好的标注模型准确率大概为97%左右。

用HMM进行词性标注

考虑HMM的时候,我们先考虑HMM如何对应到词性标注的实践中去。

我们能观察到的是word,因此,观测O是word,能取$\vert V\vert$个值;不能观察到的是POS tag,能取到所有tag集合;转换矩阵是tag与tag之间的转换矩阵,发射矩阵是tag与word之间的发射矩阵;初始状态$\pi$是最初tag分布的概率(即每个句子句首单词的tag)。

因此词性标注的训练过程,是根据现有的观测序列和状态序列,求参数;词性标注的过程,是根据参数和观测序列,求最可能的状态序列,也称为解码过程。令词性序列为$t_1^n$,单词序列为$w_1^n$,故最佳的词性序列为:
$$
\begin{align}
\hat t_1^n &= \arg\max P(t_1^n | w_1^n) \\
&= \arg\max P(t_1^n) P(w_1^n|t_1^n) \\
&= \arg\max P(t_1)\prod_{i=1}^{n-1} P(t_{i+1}| t_{i}) \prod_{i=1}^n P(w_i|t_i)
\end{align}
$$

具体关于decoding的算法,可以参见关于HMM的专题。

实际使用过程中,可以有HMM的其它变体,比如tri-gram HMM,tag的转换概率,依赖于前两个tag。

tri-gram HMM

由bigram转换成trigram之后,发射矩阵不用变化,转换矩阵需要改变,由之前的$N\times N$矩阵,变成$N^2 \times N$矩阵。相应地,在使用维特比算法的时候,也需要考虑更多的组合:之前是计算由上一个时刻的所有状态到当前时刻某一状态的最大概率,现在需要计算上两个时刻的所有状态的组合到当前时刻某一个状态的最大概率。

除了增加了运算的复杂度,转换矩阵变得更加稀疏了。这时候我们需要采用一定的平滑手段,避免训练集中没有出现的组合会被认为不可能出现。这里采用的是Interpolation方法,考虑tri-gram,bi-gram和uni-gram的加权平均。
$$
P(t_i|t_{i-1}t_{i-2}) = \lambda_3 P(t_i|t_{i-1}t_{i-2}) + \lambda_2 P(t_i|t_{i-1}) + \lambda_1 P(t_i)
$$
在n-gram语言模型中,我们常根据dev set来优化参数$\lambda_1, \lambda_2, \lambda_3$,在这里,我们引入一个新的算法,deleted interploation。它通过依次删除每一个tri-gram来优化参数。

deleted interpolatoin算法:首先,将三个参数都设置为0。将训练集中所有的tri-gram和其计数都罗列出来,一次循环。每次循环中,删除当前tri-gram,

deleted_interpolation

虽然维特比算法可以大幅度降低运算量,但是当N或者T很大的时候,运算量依旧很大。因此,为了让算法practical,我们需要继续降低运算量。beam search的思想就是,对于任何时刻t,我们不保存对于每一个可能状态的最大路径,而是保存概率最大的前n个节点(可能的状态)。

未知单词

待总结

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

MEMM和最大熵模型是两个完全不同的模型,最大熵模型是在满足限定条件的情况下,使得模型的熵最大,以此求出最佳模型;而最大熵马尔科夫模型则是一个sequential版本的逻辑回归模型。在传统的逻辑回归中,我们根据输入的features,利用sigmoid或者softmax函数,最小化交叉熵(即使得预测的分布和真实分布尽可能接近)。而MEMM则是依次预测每一个word的tag,而每次的输入,是该句所有的word,和之前预测出来的所有tag(为什么不是所有的tag?因为后面的tag还没有预测出来),利用feature template在所有的word和所有已经预测出来的tag中,提取特征。每次预测word可以看成是一个传统的多分类逻辑回归,唯一不同的就是输入跟之前的预测有关。
$$
\begin{align}
\hat T &= \arg\max_T P(T|w) \\
&= \arg\max \prod_{i=1} P(t_i| t_1^{i-1}, w_1^N) \\
&= \arg\max \prod_{i=1} \frac{exp(\sum_j \theta_j f_j)}{\sum_{tagset} exp(\sum_j \theta_j f_j)}
\end{align}
$$

上式中$f_j$是特征函数,每一个特征函数都是二值函数,都跟一个weight相乘然后加和。

特征模板

Feature template是一个很高效的提取特征的方法,免去了人工挑选特征的工程。

首先可以作为特征包括所有单词,之前的所有tag,单词和tag的组合:
$$
(t_i, w_{i-2}),(t_i, w_{i-1}),(t_i, w_{i}),(t_i, w_{i+1}),(t_i, w_{i+2}) \\
(t_i, t_{i-1}),(t_i, t_{i-1}, t_{i-2}) \\
(t_i, t_{i-1}, w_i),(t_i, w_{i-1},w_i),(t_i, w_i, w_{i+1})
$$
然后就是word spelling:是否包含某个prefix(长度小于或等于4),是否包含某个suffix,包含number,Uppercase letter,hyphen,all uppercase。

word shape也是很好的特征,它是将word转换成抽象的结构:小写字母变成x,大写字母变成X,数字变成d,保留标点。如DC10-30变成XXdd-dd。还有一种转化方式是将连续的相同类别只保留一个,称为short-word shape。

用了特征模板之后,未知词就不需要单独处理了,因为它能从现有的特征中获取信息。当然,因为特征函数是二值函数,如果在训练样本中,某个特征函数等于1的情况出现的很少,我们可以考虑舍弃该特征。因此,可以设置一个阈值,如特征出现次数大于某个值的时候,才考虑该特征。

总结和对比HMM和MEMM

HMM是生成模型,学习先验概率$P(tag|tagBefore)$和似然概率$P(word|tag)$从而学习到联合概率,在预测的时候,遍历所有的tag,求出每一个tag的情况下,是当前word的概率,即$p(tag)p(word|tag)$,然后从中选出使得概率最大的tag。而MEMM是判别模型,对于单个word的判断,模型将输入(所有的words和已经预测出来的tag)生成的features与weights相乘,然后送入softmax,找出概率最大的tag类别,便是此次预测的tag。当然,这只是保证了单个word的概率最大,词性标注是序列标注,需要保证整体序列的概率最大,因此,需要采用维特比算法找出全局最优解。

MEMM可能整体上优于HMM,但依然存在一些问题,如label bias。(TO BE CONTINUED)

HMM和MEMM都是自左向右的模型,有方向性的,因此也决定了我们不能用当前时刻之后的tag信息,具有一定的局限性。因此,引入双向模型势必会提升序列标注的准确率。条件随机场就是一个无方向的模型,其一个比较明显的缺点就是训练比较慢,计算量较大。