chapter10-词性标注

  • 词性分类 clossed class, open Classes
  • 标记集 Tagset
  • HMM tagging: 生成模型 \(p(t_i|w_i)=p(w_i|t_i)p(t_i|t_{i-1})\) 有viterbi算法和greedy算法~
  • MEMM: 判别模型 \(p(t_i|w_i,t_{i-1},...f;w)\) 也有Viterbi和greedy两种算法,更新参数w~
  • 双向模型 CRF,chapter20讲

前言: 词性标注(parts-of-speech)又称 (pos, word classes, or syntactic categories) 分为8类: noun, verb, pronoun, preposition, adverb, conjunction, participle, and article.(名词,动词,代词,介词,副词,连词,分词和文章。)

词性标注在寻找命名实体(named entities)和其他一些 信息提取(information extraction) 的工作中是很重要的特征。词性标注也会影响形态词缀(morphological affixes),从而影响词干(stemming)的信息检索;在语音识别中对语音的生成也有很重要的作用,比如CONtent是名词,而conTENT是形容词。

(Mostly) English Word Classes

传统上,词类根据形态和语法功能来分类:

  • distributional properties 分布特征:单词出现在相似的环境中;
  • morphological properties 形态特征:单词的词缀具有相似的功能。

词类可分为两大类:封闭类 closed class types 和 开放类 open class type. 封闭类:prepositions 介词,function words, like,of,it,.... 一般都很短,而且频率高;开放类:nouns, verbs,adjectives, and adverbs

  • noun 名词: 专有名词(Proper nouns)和普通名词(common nouns)。专有名词一般不受冠词限制,且一地个字母要大写。普通名词又分为可数名词(count nouns)和不可数名词(mass nouns). 当某种东西能在概念上按照同质来分组时,就使用物质名词,这样的词是不可数的。(Mass nouns are used when something is conceptualized as a homogeneous group).

  • verb 动词: 用来表示动作或过程。动词有若干形态,(non-third-person-sg非第三人称单数 (eat), third-person-sg第三人称单数 (eats), 进行时progressive (eating), 过去分词past participle (eaten)).

  • adjectives 形容词: 描述性质和质量的单词。

  • adverbs 副词: 无论是从语义上还是形态上,都比较杂。通常用来修饰动词,也可以用来修饰其他副词或是动词短语。方位副词和地点副词 Directional adverbs or locative adverbs程度副词 degree adverbs (extremely, very, somewhat); 方式副词 manner adverbs (slowly, slinkily, delicately); 时间副词 temporal adverbs (yesterday, Monday).

封闭类:

  • preposition 介词: 出现在名词短语之前,从语义上讲,他们是表示关系的。
  • particle 小品词: 与介词或副词相似,经常和动词结合,形成动词短语。
  • determiner 限定词: 其中包括 article 冠词,a,an,the. 其他的限定词,比如 this,that
  • conjunction 连词: 连接两个短语、分句或句子。
  • pronoun 代词: 简短地援引某些名词短语、实体或事件的一种形式。
  • auxiliary 助动词: 包括系动词be,两个动词do, have,以及情态动词。
  • 英语中还有很多 叹词(oh,ah,hey,man,alas),否定词(no,not),礼貌标志词(please,thank you). 是否把这些词放在一起,取决于标记的目的。

The Penn Treebank Part-of-Speech Tagset 标记集

Peen Treebank标记集是Brown语料库原有的87个标记集中挑选出来的。还有两个比较大的标记集 C5,C7.

词性标注

词性标注(pos tagging)与计算机语言的 tokenization (词形还原?分词) 过程是一致的,但词性标注具有更多的歧义性。在Brown语料库中,只有11.5%的英语词型(word type)是具有歧义的,40%以上的词例(word token)有歧义的。

chapter2中几个容易混淆的概念:

  • 词型 word type 不包括重复词,
  • 词例 word token 包括重复词。
  • lemma 是词意,am is are是同一个单词be
  • Wordform 是词的形状。

词性标注是歧义消解(disambiguation)的一个重要方面,大多数的标注算法分为两类:基于规则的标注算法(rule-based tagger),一类是随机标注算法(stochastic tagger).

HMM Part-of-Speech Tagging

基于隐马尔可夫的词性标注,语料库是观察序列,part-of-speech是隐藏状态,对于Peen Treebank标记集有45中隐藏状态。因为训练数据是有人工标注的,所以我们的目标是,根据已知的观察序列和对应的隐藏状态,可以根据极大似然估计或者相对频率计算出状态转移矩阵和发射矩阵的参数~

所以词性标注的问题和预测问题是一样的~可以使用viterbi算法,对带标注的序列进行标注~

The basic equation of HMM Tagging

HMM decoding:求概率最大的tagging序列 \[\hat t_1^n = argmax_{t_1^n}P(t_1^n|w_1^n)\]

使用bayes公式: \[\hat t_1^n=argmax_{t_1^n}\dfrac{P(w_1^n|t_1^n)P(t_1^n)}{P(w_1^n)}\]

目的是让观察序列的似然概率最大化~因此观察序列对于任何隐藏序列都是一样的~故可以直接去掉分母: \[\hat t_1^n=argmax_{t_1^n}P(w_1^n|t_1^n)P(t_1^n)\]

根据概率图模型中,一个word的生成只取决于其对应的tag,而与其他word和word无关,也就是条件独立可得: \[P(w_1^n|t_1^n)\approx \prod_{i=1}^nP(w_i|t_i)\]

根据bigram假设: \[P(t_1^n)\approx \prod_{i=1}^nP(t_i|t_{i-1})\]

联立可得: \[\hat t_1^n = argmax_{t_1^n}P(t_1^n|w_1^n)\approx argmaxmax_{t_1^n}\prod_{i=1}^nP(w_i|t_i)P(t_i|t_{i-1})\tag{10.8}\]

Estimating probabilities 概率估计

在HMM tagging中,概率估计是直接通过对训练语料库中进行计数得到的。

状态转移概率 transition probabilities: \(P(t_i|t_{i-1})\),shape=(45,45) \[P(t_i|t_{i-1})=\dfrac{C(t_{i-1},t_i)}{C(t_{i-1})}\]

发射概率 emission probabilities: \(P(w_i|t_i)\),shape=(45, V) \[P(w_i|t_i)=\dfrac{C(t_i,w_i)}{C(t_i)}\]

Working through an example

举个栗子

其中状态转移概率和发射概率依据已经标记好的语料库WSJ corpus计算得到,其对应的状态转移矩阵A和发射矩阵B:

那么对应的可能的状态序列如下图,加粗的黑色路径是概率最大的状态序列。

Viterbi算法

先回顾下隐马尔科夫模型中的viterbi算法:

这是在给定模型 \(\lambda=(A,B)\) 的情况下,寻找状态序列使得观察序列的似然概率最大~

矩阵 viterbi [N+2,T], 第一行和第二行是 states 0 和 \(q_F\)

从state 1 开始: \[v_t(j)=\max_{i=1}^Nv_{t-1}(i)a_{ij}b_j(o_t)\]

可以看到,行代表的是[start, NNP, MD,..., DT, end]^T,总共 N+2 中状态。 列代表的是时间步 [1,2,3...,t],因为t=0时刻,肯定是start状态,没有emission. 从第一列 t=1 到 第二列 t=2,每一步都是前一步的N种状态转移到当前状态的max.

Extending the HMM Algorithm to Trigrams

\[P(t_1^n)\approx \prod_{i=1}^nP(t_i|t_{i-1})\] 改为: \[P(t_1^n)\approx \prod_{i=1}^nP(t_i|t_{i-1},t_{t-2})\] 每一步的计算复杂度,从N变成 \(N^2\).

本书上写的,当前 state-of-art 的HMM 标注算法是 A statistical part-of-speech tagger. In ANLP 2000, Seattle. 论文作者让标注者在每句话结尾处加上 end-of-sequence marker for \(t_{n+1}\). 这里的n表示序列长度。

\[\hat t_1^n = argmax_{t_1^n}P(t_1^n|w_1^n)\approx argmaxmax_{t_1^n}[\prod_{i=1}^nP(w_i|t_i)P(t_i|t_{i-1},t_{i-2})]P(t_{n+1}|t_n)\]

其中,转移概率可以通过语料库计数得到: \[P(t_i|t_{i-1},t_{i-2})=\dfrac{C(t_{i-2},t_{i-1},t_i)}{C(t_{i-2},t_{i-1})}\]

但是在测试集中,很可能遇到状态序列(也就是tag序列) \(t_{i-2},t_{i-1},t_i\) 在训练集中从未出现过,也就是其概率为zeros,这样就无法对测试集中的序列进行标注了。也就是语言模型中提到的zeros情况~比如图10.7中,某个时间步没有可选择的隐藏状态tag

同样,我们也可以使用插值法~

其中 \(\lambda\) 的计算可以用 deleted interpolation

不太理解。。。

Unknown Words

Samuelsson (1993) and Brants (2000)根据形态(morphology)来判断unknown word的可能状态. 比如 -s 通常是复数名词NNS, -ed通常是过去时态VBN, -able通常是形容词 JJ.... \[P(t_i|l_{n-i+1}...l_n)\]

这个概率也是可以通过语料库中相对频率计算得到~

他们使用尽量短的后缀(shorter and shorter suffixes)应用回退smoothing方法来估计unknow word的可能状态,但要尽量避免其状态为 closed class,比如介词 prepositions,可以将unknow word的状态tag选择从频率 \(\le 10\) 中选择,或者只从open classes 中选择可能的tag.

Brants(2000) 还额外使用了首字母的特征信息,将公式(10.21)可改写为: \[P(t_i,c_i|t_{i-1},c_{i-1},t_{i-2},c_{i-2})\] 这样语料库中标记集就包括首字母大写和小写两种版本,其对应的标记集tagset就增大为2倍。

state-of-art HMM tagging也就是论文Brants(2000) 的准确率达到 96.7% 在使用Penn Treebank标记集。

Maximum Entropy Markov Models

最大熵隐马尔可夫模型,是依据logistic回归的,所以它是判别模型 discriminative sequence model, 而HMM是生成模型 generative sequence model.

  • sequence of words: W = \(w_1^n\)
  • sequence of tags: T = \(t_1^n\)

那么HMM模型的P(T|W)是依据bayes规则和最大似然P(w|T)得到的:

而在最大熵隐马尔科夫模型,直接计算后验概率 posterior P(T|W).

\[\hat T = argmax_TP(T|W) = argmax_T\prod_iP(t_i|w_i,t_i-1)\]

对比HMM和MEMM,HMM计算是在tag的条件下观察序列似然最大, MEMM计算是在观察序列的条件下tag序列似然最大~显然在tag已经标注好的训练集里,判别模型是完全可行的,也许会是更好的~

Features in a MEMM

在HMM中,我们得到下一个tag的概率只依赖与前一个或两个tag,以及当前的word,如果想考虑更多的特征,比如首字母capitalization,后缀suffix,那样计算复杂度会增加很多。

相比之下,MEMM可以考虑更多的特征:

MEMM可以依赖的特征可以是 word,neighboring words, previous tags, and various tags, and various combinations. 可使用 features templates 来表示:

对于之前的例子:

Janet/NNP will/MD back/VB the/DT bill/NN

\(w_i\) 是 back 时,对应的特征模板 features templates,也就是 know-words feature:

除此之外,还有当前词 \(w_i\) 的拼写和形状特征,这些特征对于处理 unknow word 很有必要~

那么根据上述规则,单词 well-dressed 的 word shape 特征就是:

这样一来,特征就很多很多了,通常需要进行一定的cutoff.

其中 \(w_{i-l}^{i+l}\) 表示考虑当前词前后 l 个单词, \(t_{i-k}^{i-1}\) 表示考虑前k个tags.

Decoding and Training MEMMs 训练MEMMs

在MEMMs中,每一步都是一个local classifer,然后make a hard decision,选择概率最大的词。。。以此类推。因此,这是贪心greedy算法~

虽然这样使用greedy的方法,得到的准确率也还不错~

Viterbi算法

原始Viterbi: \[v_t(j) = max_{i=1}^Nv_{t-1}(i)a_{ij}b_j(o_t)\] HMM tagging: \[v_t(j) = max_{i=1}^Nv_{t-1}P(s_j|s_i)P(o_t|s_j)\] MEMM: \[v_t(j) = max_{i=1}^Nv_{t-1}P(s_j|s_i,o_t)\]

书上对如何训练参数一笔带过了,我自己总结如下:

  • 初始化转移矩阵和发射矩阵参数,设为w
  • 根据Viterbi算法填写矩阵 \(N\times T\), 也就是每一个网格用概率 \(P(t_i|w_{i-1}^{i+l},t_{i-k}^{i-1})\), 并保留 backpointers
  • 比较tag路径与真实路径,然后反向传播,更新参数权重w, 注意有正则化L1,L2

要更深入的理解MEMM,需要和HMM tagging对比更容易理解~~

  • HMM是生成模型,它是在求已知 \(t_i\) 条件下生成 \(w_i\) 的概率 \(P(w_i|t_i)\),这根据语料库中的频率是可以计算得到的;然后后验概率 \(P(t_i|t_{i-1})\) 也是可以通过频率计算得到的~ 知道似然概率和发射概率后根据bayes公式就可以预测了P(T|W)~

  • MEMM是判别模型,它是直接求 P(T|W),显然是tag生成word,而不是word生成tag,因此无法直接通过频率,但我们将它分解为每一个时间步计算 $P(t_i|w_i,t_{i-1},...)(各种特征),每一个特征有对应的权重w,然后根据最大熵原理,也就是公式(10.29)所示,从前一个tag \(t_{i-1}\) 有N中状态,到下一个tag \(t_i\), 是max的过程,但整个过程不是greedy的(这需要好好理解,其实也就是Viterbi一样的。。),然后根据backpoints得到的tag序列与真实tag序列对比,不断更新权重参数w!

Bidirectionality

这里举了个例子来阐述双向的重要性。

will/NN to/TO fight/VB

通常 to 都是接在名词NN后面,而不会是情态动词 MD 后面,这里的will也应该是 NN。 但是在 \(P(t_{will}|< s >)\)\(t_{will}\) 更倾向于是情态动词 MD,而且 \(P(TO|t_{will},to)\) 的概率接近于1,无论 \(t_{will}\) 是啥,所以这时候 \(t_{will}\) 就会错误的标注为 MD.

这样的错误叫 label bias or observation bias, 所以我们需要双向~ 条件随机场 Conditional Random Field or CRF 就是这样的~

任何sequence model都可以是双向的。比如,对于tagging,可以在第一遍 left to right, 而从二遍开始就可以双向了~

SVMTool system 就是这样的,不过它在每一个时间步使用的不是最大熵分类器,而是SVM分类器,然后用Viterbi算法或者是greedy应用到整个sequence model~

Part-of-Speech Tagging for Other Languages

中文的分词可以和标注一起进行~

中文的未登录词问题~

总结: