用500行Python实现英语依存句法解析

概述

句法解析器用于分析句子的语法结构，帮助应用程序进行语义推理。自然语言存在许多意外的歧义，需要依靠世界知识进行过滤。例如句子"They ate the pizza with anchovies"中，正确的解析应将"with"连接到"pizza"，而非"eat"。

技术实现

解析算法

采用贪婪转移式解析算法，该算法作为有限状态转换器，将N个单词的数组映射到N个头索引的输出数组。解析器支持三种操作：

SHIFT：将当前词压入栈
RIGHT：添加右依赖关系并弹出栈
LEFT：添加左依赖关系并弹出栈

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


SHIFT = 0; RIGHT = 1; LEFT = 2
MOVES = [SHIFT, RIGHT, LEFT]

def transition(move, i, stack, parse):
    if move == SHIFT:
        stack.append(i)
        return i + 1
    elif move == RIGHT:
        parse.add_arc(stack[-2], stack.pop())
        return i
    elif move == LEFT:
        parse.add_arc(i, stack.pop())
        return i

数据结构

解析状态由三部分组成：

当前词索引i
已添加的依赖关系（Parse对象）
存储待分配头词的栈

1
2
3
4
5
6
7
8
9


class Parse(object):
    def __init__(self, n):
        self.n = n
        self.heads = [None] * (n-1)
        self.lefts = []
        self.rights = []
        for i in range(n+1):
            self.lefts.append(DefaultList(0))
            self.rights.append(DefaultList(0))

特征提取

从上下文中提取12个token的特征，包括：

缓冲区的前三个词（n0, n1, n2）
栈顶三个词（s0, s1, s2）
s0的最左两个子节点（s0b1, s0b2）
s0的最右两个子节点（s0f1, s0f2）
n0的最左两个子节点（n0b1, n0b2）

对这些token提取词形、词性标签以及左右子节点数量信息。

训练过程

使用平均感知器算法进行在线学习，通过动态oracle训练方法显著提升准确率（通常提高1-2%）。关键突破在于Goldberg和Nivre（2012）提出的训练方法改进。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


def train_one(self, itn, words, gold_tags, gold_heads):
    n = len(words)
    i = 2; stack = [1]; parse = Parse(n)
    tags = self.tagger.tag(words)
    while stack or (i + 1) < n:
        features = extract_features(words, tags, i, n, stack, parse)
        scores = self.model.score(features)
        valid_moves = get_valid_moves(i, n, len(stack))
        guess = max(valid_moves, key=lambda move: scores[move])
        gold_moves = get_gold_moves(i, n, stack, parse.heads, gold_heads)
        best = max(gold_moves, key=lambda move: scores[move])
    self.model.update(best, guess, features)
    i = transition(guess, i, stack, parse)

性能对比

解析器	准确率	速度(词/秒)	语言	代码行数
某机构PCFG	89.6%	19	Java	<4,000
parser.py	89.8%	2,020	Python	~500
Redshift	93.6%	2,580	Cython	~4,000

应用场景

该技术可用于智能设备指令解析，例如：“开会时静音，除非约翰学校来电”。依赖解析器返回词词关系图，使此类推理更加容易。

实验细节

在华尔街日报语料库第22节上进行测试，使用无标记附着得分（所有非标点符号词的头索引正确率）作为评估指标。训练数据使用WSJ 02-21的黄金标准PTB树。

参考文献

采用动态oracle的Arc-Hybrid系统，相关论文包括：

Goldberg和Nivre (2013). Training Deterministic Parsers with Non-Deterministic Oracles
Zhang和Clark (2011). Syntactic Processing Using the Generalized Perceptron and Beam Search
Collins (2002). Discriminative Training Methods for Hidden Markov Models

该实现证明了简洁算法代码的高效性，在保持高性能的同时大幅减少了代码复杂度。

Python实现500行英语依存句法解析器

本文详细介绍了使用Python在500行代码内实现英语依存句法解析器的技术方案，包括贪婪转移解析算法、特征提取方法和动态训练机制，对比了与传统解析器的性能差异并提供了完整实现细节。