特征集

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

• 缓存中的前三个单词 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），我们的语法解析器的性能可能会有所提升，他们曾指出我们错了很多年。

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

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

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

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

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

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

这里需要领会很多东西。

因此我们有函数 Oraclestate）:

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]  

进行“动态 oracle”训练过程会产生很大的精度差异——通常为1-2%，和运行时的方式没有区别。旧的“静态oracle”贪婪训练过程已经完全过时；没有任何理由那样做了。