放牧代码和思想
专注自然语言处理、机器学习算法

200行Python代码实现感知机词性标注器

目录

译自Matthew的《A Good Part-of-Speech Tagger in about 200 Lines of Python》,本文用最精简的代码演示了如何写一个基于感知机的高性能词性标注器。以下是正文:

pos-tagger_large.jpg

自然语言处理的最新技术大部分都停留在学术界,但学术界往往非常谨慎、不愿意把话说满以免作茧自缚。但太谦虚也没有意义,本文就展示了如何写一个高性能的词性标注器。

现在有成千上万种所谓的“最好的词性标注技术”,但它们都没有卵用,你用Averaged Perceptron就行了。(译注:术语Averaged Perceptron在中文学术界常用平均感知机,也有简称AP的用法)屏幕快照 2016-09-03 下午7.02.24.png

你应该用上两个词的词性,以及Brown word clusters中用到的那些特征。

如果你的需求只是将标注器用于那些规范的文本,那么你应该用大小写敏感的特征,但如果你想要写一个更健壮的标注器,那你就不要这么做,因为这么做会使得标注器在训练数据上过拟合。相反,那些能够反映“在互联网大型语料上这个词不计大小写时的词频”的特征挺有用。这时,你就可以把语料中的词语都转成小写。

为了效率起见,你应该找出训练数据中哪些词语仅有唯一的词性,这样当你碰到它们的时候只需直接输出就行了。大约有50%的词语的词性都是唯一的。

除非你真的真的不愿意放弃那0.1%的准确率提升,否则你就不必操心各种各样的搜索算法(译注:viterbi、NBest等),直接上一个贪心算法就行了(如同许多用户发现的一样,HanLP的HMM词性标注采用的就是决策长度为2的贪心算法)。

如果你全都听我的,你就会发现你的标注器既好写又好懂,并且一个高效的Cython实现可以在13万的华尔街语料上跑出下列成绩:

TAGGER ACCURARCY TIME (130K WORDS)
CyGreedyAP 97.1% 4s

这4秒包含了初始化的时间——实际的标注速度会更快,绝对不会成为程序的性能瓶颈。

看着这97%的准确率站着说点不腰疼的话是很简单的,但这并没有意义。在手工精心整理的数据集上,我的标注器还可以上升1个百分点,另外,任何标注器在开放领域上的表现都很差。幸运的是,最近10年这种差别正在逐渐减小。这也是我为什么推荐使用一个准确度良好但速度超级快的标注器的原因。

但可笑的是,我经常看到人们用一些很糟糕的标注器!比如,那些新手们总喜欢用如下两个工具:

TAGGER ACCURARCY TIME (130K WORDS)
NLTK 94.0% 3m56s
Pattern 93.5% 26s

Pattern和NLTK的代码都非常健壮,并且文档丰富,所以很多人爱用它们。但Pattern的算法非常烂,而NLTK则拖家带口地附带了一堆包,因为它还承担着教学演示的任务。

作为一个独立的标注器,我的Cython实现有点过于复杂了,因为是为我的Parser配套写的。所以今天我用Python写了一个200行的替代品,它的性能是:

TAGGER ACCURARCY TIME (130K WORDS)
PyGreedyAP 96.8% 12s

为了保证代码简洁,我牺牲了一些准确率和速度。下面就是关于它的原理。

平均感知机

词性标注是一个监督学习,所谓监督学习,指的是给你一张表格,并且告诉你在测试的时候最后一列会被拿掉。你的工作就是通过其他列去预测最后这一列。

对于词性标注来讲,缺失的这一列就是词性。其他列(特征)可能是“上个词”的词性,“下个词的最后三个字符”之类的信息。

预测

首先,让我们看看预测的代码:

def predict(self, features):
    '''Dot-product the features and current weights and return the best label.'''
    scores = defaultdict(float)
    for feat, value in features.items():
        if feat not in self.weights or value == 0:
            continue
        weights = self.weights[feat]
        for label, weight in weights.items():
            scores[label] += value * weight
    # Do a secondary alphabetic sort, for stability
    return max(self.classes, key=lambda label: (scores[label], label))

前面我将学习问题比作一张表格,该表格在预测的时候缺失了最后一列。对NLP来讲,我们的表格通常特别稀疏。表格中可能有一个格子是“上一个词=国会”,这种特征的数量可能接近0。所以我们的“特征向量”可能从来都不会做成向量形式。Map类型是个好主意,在这里我们使用了Python的dictionary类型。

输入数据,也就是特征,是表格中频次大于0的那些格子的集合。通常在实现的时候可以写成dictionary类型,这样就可以set值了。但我直接将其写成“命中与否”的二值类型。

weight是一个双层的dictionary,保存了特征->类别->权重。我特意这么写,而不是把类别作为第一层键的原因是:词语词频差别巨大——低频词非常少见,高频词非常常见。

训练

好吧,你说的很有道理,何不给我充Q币?那么怎么学习特征权重呢?我们先初始化一个特征权重dictionary,然后迭代如下步骤:

1、输入一个(特征,词性)键值对。

2、通过当前的特征权重预测词性。

3、如果预测错误,那么将(特征,正确词性)对应的特征权重+1,并且将(特征,错误词性)对应的特征权重-1。

这是最简单的训练算法了,只要模型犯了一个错误,就将正确词性对应的特征权重(译注:复数,指的是词性正确那些特征函数,下文同理)增加,并且惩罚那些误导模型的特征函数,写成Python代码如下:

def train(self, nr_iter, examples):
    for i in range(nr_iter):
        for features, true_tag in examples:
            guess = self.predict(features)
            if guess != true_tag:
                for f in features:
                    self.weights[f][true_tag] += 1
                    self.weights[f][guess] -= 1
        random.shuffle(examples)

如果你在一个训练实例上运行上述代码,该实例的词性相关的权重很快就能算出来。如果是两个训练实例呢?除非它们的特征各不相同,你才可能得到相应的正确结果。一般来讲,算法会连续运行很久,因为训练实例总得一个个输入进来(译注:在线学习)。

平均权重

为了让感知机算法真正力压群雄,我们还得努力。上述算法的问题在于,如果你在两个轻微不同的实例上训练的话,你可能会得到截然不同的模型。模型不能聪明地泛化问题。更大的问题在于,如果你让算法跑到收敛,它会过于关注那些误分类的点,并且调整整个模型以适应它们。

所以,我们要减小特征权重的变化速度——让模型没法在一个迭代中作太多改变以免前功尽弃。我们的做法是返回平均权重,而不是最终权重。

我猜很多人会说,为什么?但我们不是来做学究的,这个做法已经被长时间的实践证明了。如果你有其他主意,欢迎做做试验然后与大家共享。事实上,我很期待看到更多新发现,因为现在平均感知机在NLP中的地位已经变得非常之高了。

好了,回过头来继续讨论平均。如何平均呢?注意我们并不在每个外层循环中做平均,我们在内层循环中作平均。如果我们有5000个训练实例,我们训练10个迭代,对每个权重我们平均50000次。

我们当然不会把这么多中间变量都存起来了,我们只记录每个权重的累加值,然后除以最终的迭代次数,不就平均了吗。重申一遍,我们想要的是每个(特征,词性)对应的平均权重,所以关键点在于其累计权重。但如何累计权重也是个技术活。对于大部分训练实例,都只会引起特定的几个权重变化,其他特征函数的权重都不会变化。所以我们不应该傻乎乎地将这些不变的权重也累加起来。

你我都不是傻瓜,让我们一起实现上述改进算法吧。我们维护一个额外的dictionary,记录每个权重上次变化的时间。当我们改变一个特征权重的时候,我们就取出这个值用于更新。

下面就是更新时具体的代码了:

def update(self, truth, guess, features):
    def upd_feat(c, f, v):
        nr_iters_at_this_weight = self.i - self._timestamps[f][c]
        self._totals[f][c] += nr_iters_at_this_weight * self.weights[f][c]
        self.weights[f][c] += v
        self._timestamps[f][c] = self.i

    self.i += 1
    for f in features:
        upd_feat(truth, f, 1.0)
        upd_feat(guess, f, -1.0)

特征和预处理

词性标注语料中有成千上万错综复杂的特征,包括大小写和标点符号等。它们对华尔街语料的准确率是有帮助的,但我没见到对其他语料有任何帮助。

为了训练一个更通用的模型,我们将在特征提取之前预处理数据:

  • 所有词语都转小写

  • 1800-2100之间的数字被转义为!YEAR

  • 其他数字被转义为!DIGITS

  • 写一个专门识别日期、电话号码、邮箱等的模块可能更好,但这会使问题复杂化,成为分词器了

我用过这些特征,考虑到它们能够取得的97%的成绩、以及较低的内存占用,它们还是很划算的。

特征提取代码如下:

def _get_features(self, i, word, context, prev, prev2):
    '''Map tokens-in-contexts into a feature representation, implemented as a
    set. If the features change, a new model must be trained.'''
    def add(name, *args):
        features.add('+'.join((name,) + tuple(args)))

    features = set()
    add('bias') # This acts sort of like a prior
    add('i suffix', word[-3:])
    add('i pref1', word[0])
    add('i-1 tag', prev)
    add('i-2 tag', prev2)
    add('i tag+i-2 tag', prev, prev2)
    add('i word', context[i])
    add('i-1 tag+i word', prev, context[i])
    add('i-1 word', context[i-1])
    add('i-1 suffix', context[i-1][-3:])
    add('i-2 word', context[i-2])
    add('i+1 word', context[i+1])
    add('i+1 suffix', context[i+1][-3:])
    add('i+2 word', context[i+2])
    return features

我没有加入外部特征,比如从Google Web 1T中统计出的词频等。我可能会在后续版本加入这些,但现在还是保持精简吧。

搜索

我推荐的模型直接输出当前词语的词性,然后处理下一个。这些预测词性之后作为下一个词语的特征。这么做有潜在问题,但问题也不大。用柱搜索很容易解决,但照我说根本不值得。更不用说采用类似如条件随机场那样的又慢又复杂的算法了。

这个潜在的问题是这样的:当前位置假设是3,上个词语和下个词语是2和4,在当前位置决定词性的最佳因素可能是词语本身,但次之就是2和4的词性了。于是就导致了一个“鸡生蛋”的问题:我们想要预测3的词性,可是它会用到未确定的2或4的词性。举个具体的例子:

Their management plan reforms worked

根据上述算法,你可以发现从左到右处理句子和从右到左会得到完全不同的结果。

如果你还没明白,那就这么思考:从右往左看,“worked”很可能是个动词,所以基于此把“reform”标注为名词。但如果你从左往右、从“plan”出发,可能就会觉得“reform”是名词或动词。

只有当你会犯错的时候才需要用搜索。它可以防止错误的传播,或者说你将来的决策会改正这个错误。这就是为什么对词性标注来说,搜索非常重要!你的模型非常棒的时候,你过去做的决定总是对的的话,你就不需要搜索了。

当我们改进标注器后,搜索的重要性就会下降。相较于搜索,我们更应关注多标签。如果我们让模型不那么确定,当允许单个词语平均有1.05个词性的时候,我们可以得到99%的准确率(Vadas et al, ACL 2006)。虽然平均感知机对于多标签任务就是个垃圾,但这本来就不是它的强项,你应该用一些概率模型。

贪心搜索的时候注意,模型必须假设测试时历史标签是不完美的。否则它就会过于依赖历史标签。由于感知机是迭代式的,所以这很简单。

下面是标注器的训练主循环:

def train(self, sentences, save_loc=None, nr_iter=5, quiet=False):
    '''Train a model from sentences, and save it at save_loc. nr_iter
    controls the number of Perceptron training iterations.'''
    self._make_tagdict(sentences, quiet=quiet)
    self.model.classes = self.classes
    prev, prev2 = START    for iter_ in range(nr_iter):
        c = 0; n = 0
        for words, tags in sentences:
            context = START + [self._normalize(w) for w in words] + END            for i, word in enumerate(words):
                guess = self.tagdict.get(word)
                if not guess:
                    feats = self._get_features(
                                i, word, context, prev, prev2)
                    guess = self.model.predict(feats)
                    self.model.update(tags[i], guess, feats)
                # Set the history features from the guesses, not the
                # true tags
                prev2 = prev; prev = guess
                c += guess == tags[i]; n += 1
        random.shuffle(sentences)
        if not quiet:
            print("Iter %d: %d/%d=%.3f" % (iter_, c, n, _pc(c, n)))
    self.model.average_weights()
    # Pickle as a binary file
    if save_loc is not None:
        cPickle.dump((self.model.weights, self.tagdict, self.classes),
                     open(save_loc, 'wb'), -1)

与上一段代码不同,我尝试让代码更简单。如果存在bug,那肯定是这个原因。

完整代码

(译注:作者将代码集成到TextBlob中,这不利于学习。我将其感知机代码拆分独立出来,并且配上了训练数据,本文全部源码和测试数据在:https://github.com/hankcs/AveragedPerceptronPython )

其调用方式如下:

tagger = PerceptronTagger(False)
try:
    tagger.load(PICKLE)
    print(tagger.tag('are you ok ?'))
    logging.info('Start testing...')
    right = 0.0
    total = 0.0
    sentence = ([], [])
    for line in open('data/test.txt'):
        params = line.split()
        if len(params) != 2: continue
        sentence[0].append(params[0])
        sentence[1].append(params[1])
        if params[0] == '.':
            text = ''
            words = sentence[0]
            tags = sentence[1]
            for i, word in enumerate(words):
                text += word
                if i < len(words): text += ' '
            outputs = tagger.tag(text)
            assert len(tags) == len(outputs)
            total += len(tags)
            for o, t in zip(outputs, tags):
                if o[1].strip() == t: right += 1
            sentence = ([], [])
    logging.info("Precision : %f", right / total)
except IOError:
    logging.info('Reading corpus...')
    training_data = []
    sentence = ([], [])
    for line in open('data/train.txt'):
        params = line.split('\t')
        sentence[0].append(params[0])
        sentence[1].append(params[1])
        if params[0] == '.':
            training_data.append(sentence)
            sentence = ([], [])
    logging.info('training corpus size : %d', len(training_data))
    logging.info('Start training...')
    tagger.train(training_data, save_loc=PICKLE)

注意,由于该Python实现注重代码的清晰度胜于效率,所以训练速度很慢。我在GitHub上使用的是一个非常非常小的训练集,所以在测试集上的分数较低,这不作为该算法或该实现的性能评测,特此说明。

最终比较

这几年我听过很多非议华尔街语料评测的言论,他们认为我们过拟合了。事实上,我可以证明这是错误的。一般来说,如果一项技术在某个评测上面显著地更好,那么它在其他评测也应该更好。我使用了同一个模型在其他语料上做了测试,证实了我的说法:

TAGGER WSJ ABC WEB
Pattern 93.5 90.7 88.1
NLTK 94.0 91.5 88.4
PyGreedyAP 96.8 94.8 91.8

(译注:WSJ指的是华尔街语料,不是卫生巾)

如你所见,我的标注器排名很稳定,并且优势很明显。事实上,Pattern标注器在开放领域简直烂透了,它几乎跟个傻乎乎的词典一样,所以极其受限于领域。我以前还没发现,现在吓了一跳。

我们可以在其他语料上多训练训练,以提高成绩。我训练的时候参考的是Daume III, 2007这篇论文。

Reference

https://spacy.io/blog/part-of-speech-pos-tagger-in-python

转载须注明:码农场 » 200行Python代码实现感知机词性标注器

分享到:更多 ()

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机