500 行 Python 代码做一个英文解析器

2014-5-15 14:08| 发布者: 红黑魂| 查看: 4439| 评论: 0|来自: 伯乐在线

摘要: 语法分析器描述了一个句子的语法结构，用来帮助其他的应用进行推理。自然语言引入了很多意外的歧义，以我们对世界的了解可以迅速地发现这些歧义。举一个我很喜欢的例子：They ate the pizza with anchovies正确的解 ...

特征集

特征提取代码总是很丑陋。语法分析器的特征指的是上下文中的一些标识。

缓存中的前三个单词（n0, n1, n2）
堆栈中的栈顶的三个单词（s0, s1, s2）
s0 最左边的两个孩子 (s0b1, s0b2);
s0 最右边的两个孩子 (s0f1, s0f2);
n0 最左边的两个孩子 (n0b1, n0b2);

我们指出了上述12个标识的单词表，词性标注，和标识关联的左右孩子数目。

因为使用的是线性模型，特征指的是原子属性组成的三元组。

def extract_features(words, tags, n0, n, stack, parse):
    def get_stack_context(depth, stack, data):
        if depth >;= 3:
            return data[stack[-1]], data[stack[-2]], data[stack[-3]]
        elif depth >= 2:
            return data[stack[-1]], data[stack[-2]], ''
        elif depth == 1:
            return data[stack[-1]], '', ''
        else:
            return '', '', ''
 
    def get_buffer_context(i, n, data):
        if i + 1 >= n:
            return data[i], '', ''
        elif i + 2 >= n:
            return data[i], data[i + 1], ''
        else:
            return data[i], data[i + 1], data[i + 2]
 
    def get_parse_context(word, deps, data):
        if word == -1:
            return 0, '', ''
        deps = deps[word]
        valency = len(deps)
        if not valency:
            return 0, '', ''
        elif valency == 1:
            return 1, data[deps[-1]], ''
        else:
            return valency, data[deps[-1]], data[deps[-2]]
 
    features = {}
    # Set up the context pieces --- the word, W, and tag, T, of:
    # S0-2: Top three words on the stack
    # N0-2: First three words of the buffer
    # n0b1, n0b2: Two leftmost children of the first word of the buffer
    # s0b1, s0b2: Two leftmost children of the top word of the stack
    # s0f1, s0f2: Two rightmost children of the top word of the stack
 
    depth = len(stack)
    s0 = stack[-1] if depth else -1
 
    Ws0, Ws1, Ws2 = get_stack_context(depth, stack, words)
    Ts0, Ts1, Ts2 = get_stack_context(depth, stack, tags)
 
    Wn0, Wn1, Wn2 = get_buffer_context(n0, n, words)
    Tn0, Tn1, Tn2 = get_buffer_context(n0, n, tags)
 
    Vn0b, Wn0b1, Wn0b2 = get_parse_context(n0, parse.lefts, words)
    Vn0b, Tn0b1, Tn0b2 = get_parse_context(n0, parse.lefts, tags)
 
    Vn0f, Wn0f1, Wn0f2 = get_parse_context(n0, parse.rights, words)
    _, Tn0f1, Tn0f2 = get_parse_context(n0, parse.rights, tags)
 
    Vs0b, Ws0b1, Ws0b2 = get_parse_context(s0, parse.lefts, words)
    _, Ts0b1, Ts0b2 = get_parse_context(s0, parse.lefts, tags)
 
    Vs0f, Ws0f1, Ws0f2 = get_parse_context(s0, parse.rights, words)
    _, Ts0f1, Ts0f2 = get_parse_context(s0, parse.rights, tags)
 
    # Cap numeric features at 5? 
    # String-distance
    Ds0n0 = min((n0 - s0, 5)) if s0 != 0 else 0
 
    features['bias'] = 1
    # Add word and tag unigrams
    for w in (Wn0, Wn1, Wn2, Ws0, Ws1, Ws2, Wn0b1, Wn0b2, Ws0b1, Ws0b2, Ws0f1, Ws0f2):
        if w:
            features['w=%s' % w] = 1
    for t in (Tn0, Tn1, Tn2, Ts0, Ts1, Ts2, Tn0b1, Tn0b2, Ts0b1, Ts0b2, Ts0f1, Ts0f2):
        if t:
            features['t=%s' % t] = 1
 
    # Add word/tag pairs
    for i, (w, t) in enumerate(((Wn0, Tn0), (Wn1, Tn1), (Wn2, Tn2), (Ws0, Ts0))):
        if w or t:
            features['%d w=%s, t=%s' % (i, w, t)] = 1
 
    # Add some bigrams
    features['s0w=%s,  n0w=%s' % (Ws0, Wn0)] = 1
    features['wn0tn0-ws0 %s/%s %s' % (Wn0, Tn0, Ws0)] = 1
    features['wn0tn0-ts0 %s/%s %s' % (Wn0, Tn0, Ts0)] = 1
    features['ws0ts0-wn0 %s/%s %s' % (Ws0, Ts0, Wn0)] = 1
    features['ws0-ts0 tn0 %s/%s %s' % (Ws0, Ts0, Tn0)] = 1
    features['wt-wt %s/%s %s/%s' % (Ws0, Ts0, Wn0, Tn0)] = 1
    features['tt s0=%s n0=%s' % (Ts0, Tn0)] = 1
    features['tt n0=%s n1=%s' % (Tn0, Tn1)] = 1
 
    # Add some tag trigrams
    trigrams = ((Tn0, Tn1, Tn2), (Ts0, Tn0, Tn1), (Ts0, Ts1, Tn0), 
                (Ts0, Ts0f1, Tn0), (Ts0, Ts0f1, Tn0), (Ts0, Tn0, Tn0b1),
                (Ts0, Ts0b1, Ts0b2), (Ts0, Ts0f1, Ts0f2), (Tn0, Tn0b1, Tn0b2),
                (Ts0, Ts1, Ts1))
    for i, (t1, t2, t3) in enumerate(trigrams):
        if t1 or t2 or t3:
            features['ttt-%d %s %s %s' % (i, t1, t2, t3)] = 1
 
    # Add some valency and distance features
    vw = ((Ws0, Vs0f), (Ws0, Vs0b), (Wn0, Vn0b))
    vt = ((Ts0, Vs0f), (Ts0, Vs0b), (Tn0, Vn0b))
    d = ((Ws0, Ds0n0), (Wn0, Ds0n0), (Ts0, Ds0n0), (Tn0, Ds0n0),
        ('t' + Tn0+Ts0, Ds0n0), ('w' + Wn0+Ws0, Ds0n0))
    for i, (w_t, v_d) in enumerate(vw + vt + d):
        if w_t or v_d:
            features['val/d-%d %s %d' % (i, w_t, v_d)] = 1
    return features

训练

学习权重和词性标注使用了相同的算法，即平均感知器算法。它的主要优势是，它是一个在线学习算法：例子一个接一个流入，我们进行预测，检查真实答案，如果预测错误则调整意见（权重）。

循环训练看起来是这样的：

class Parser(object):
    ...
    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)
    # Return number correct
    return len([i for i in range(n-1) if parse.heads[i] == gold_heads[i]])

训练过程中最有趣的部分是 get_gold_moves。通过Goldbery 和 Nivre （2012），我们的语法解析器的性能可能会有所提升，他们曾指出我们错了很多年。

在词性标注文章中，我提醒大家，在训练期间，你要确保传递的是最后两个预测标记做为当前标记的特征，而不是最后两个黄金标记。测试期间只有预测标记，如果特征是基于训练过程中黄金序列的，训练环境就不会和测试环境保持一致，因此将会得到错误的权重。

在语法分析中我们面临的问题是不知道如何传递预测序列！通过采用黄金标准树结构，并发现可以转换为树的过渡序列，等等，使得训练得以工作，你获得返回的动作序列，保证执行运动，将得到黄金标准的依赖关系。

问题是，如果语法分析器处于任何没有沿着黄金标准序列的状态时，我们不知道如何教它做出的“正确”运动。一旦语法分析器发生了错误，我们不知道如何从实例中训练。

这是一个大问题，因为这意味着一旦语法分析器开始发生错误，它将停止在不属于训练数据的任何一种状态——导致出现更多的错误。

对于贪婪解析器而言，问题是具体的：一旦使用方向特性，有一种自然的方式做结构化预测。

像所有的最佳突破一样，一旦你理解了这些，解决方案似乎是显而易见的。我们要做的就是定义一个函数，此函数提问“有多少黄金标准依赖关系可以从这种状态恢复”。如果能定义这个函数，你可以依次进行每种运动，进而提问，“有多少黄金标准依赖关系可以从这种状态恢复？”。如果采用的操作可以让少一些的黄金标准依赖实现，那么它就是次优的。

这里需要领会很多东西。

因此我们有函数 Oracle（state）:

Oracle(state) = | gold_arcs ∩ reachable_arcs(state) |

我们有一个操作集合，每种操作返回一种新状态。我们需要知道：

shift_cost = Oracle(state) – Oracle(shift(state))
right_cost = Oracle(state) – Oracle(right(state))
left_cost = Oracle(state) – Oracle(left(state))

现在，至少一种操作返回0。Oracle(state)提问：“前进的最佳路径的成本是多少?”最佳路径的第一步是转移，向右，或者向左。

事实证明，我们可以得出 Oracle 简化了很多过渡系统。我们正在使用的过渡系统的衍生品 —— Arc Hybrid 是 Goldberg 和 Nivre （2013）提出的。

我们把oracle实现为一个返回0-成本的运动的方法，而不是实现一个功能的Oracle(state)。这可以防止我们做一堆昂贵的复制操作。希望代码中的推理不是太难以理解，如果感到困惑并希望刨根问底的花，你可以参考 Goldberg 和 Nivre 的论文。

def get_gold_moves(n0, n, stack, heads, gold):
    def deps_between(target, others, gold):
        for word in others:
            if gold[word] == target or gold[target] == word:
                return True
        return False
 
    valid = get_valid_moves(n0, n, len(stack))
    if not stack or (SHIFT in valid and gold[n0] == stack[-1]):
        return [SHIFT]
    if gold[stack[-1]] == n0:
        return [LEFT]
    costly = set([m for m in MOVES if m not in valid])
    # If the word behind s0 is its gold head, Left is incorrect
    if len(stack) >= 2 and gold[stack[-1]] == stack[-2]:
        costly.add(LEFT)
    # If there are any dependencies between n0 and the stack,
    # pushing n0 will lose them.
    if SHIFT not in costly and deps_between(n0, stack, gold):
        costly.add(SHIFT)
    # If there are any dependencies between s0 and the buffer, popping
    # s0 will lose them.
    if deps_between(stack[-1], range(n0+1, n-1), gold):
        costly.add(LEFT)
        costly.add(RIGHT)
    return [m for m in MOVES if m not in costly]