仅用500行Python代码实现一个英文解析器的教程

> parser = parser.Parser()
> tokens = "Set the volume to zero when I 'm in a meeting unless John 's school calls".split()
> tags, heads = parser.parse(tokens)
> heads
[-1, 2, 0, 0, 3, 0, 7, 5, 7, 10, 8, 0, 13, 15, 15, 11]
> for i, h in enumerate(heads):
...  head = tokens[heads[h]] if h >= 1 else 'None'
...  print(tokens[i] + ' <-- ' + head])
Set <-- None
the <-- volume
volume <-- Set
to <-- Set
zero <-- to
when <-- Set
I <-- 'm
'm <-- when
in <-- 'm
a <-- meeting
meeting <-- in
unless <-- Set
John <-- 's
's  <-- calls
school <-- calls
calls <-- unless

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))
 
  def add_arc(self, head, child):
    self.heads[child] = head
    if child < head:
      self.lefts[head].append(child)
    else:
      self.rights[head].append(child)

SHIFT = 0; RIGHT = 1; LEFT = 2
MOVES = [SHIFT, RIGHT, LEFT]
 
def transition(move, i, stack, parse):
  global SHIFT, RIGHT, LEFT
  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
  raise GrammarError("Unknown move: %d" % move)

class Parser(object):
  ...
  def parse(self, words):
    tags = self.tagger(words)
    n = len(words)
    idx = 1
    stack = [0]
    deps = Parse(n)
    while stack or idx < n:
      features = extract_features(words, tags, idx, n, stack, deps)
      scores = self.model.score(features)
      valid_moves = get_valid_moves(i, n, len(stack))
      next_move = max(valid_moves, key=lambda move: scores[move])
      idx = transition(next_move, idx, stack, parse)
    return tags, parse
 
def get_valid_moves(i, n, stack_depth):
  moves = []
  if i < n:
    moves.append(SHIFT)
  if stack_depth >= 2:
    moves.append(RIGHT)
  if stack_depth >= 1:
    moves.append(LEFT)
  return moves

class Perceptron(object)
  ...
  def score(self, features):
    all_weights = self.weights
    scores = dict((clas, 0) for clas in self.classes)
    for feat, value in features.items():
      if value == 0:
        continue
      if feat not in all_weights:
        continue
      weights = all_weights[feat]
      for clas, weight in weights.items():
        scores[clas] += value * weight
    return scores

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"htmlcode">

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)提问：“前进的最佳路径的成本是多少"htmlcode">

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”贪婪训练过程已经完全过时；没有任何理由那样做了。

总结
我感觉，语言技术，特别是那些相关语法，特别神秘。我不能想象什么样的程序可以实现。
我认为对于人们来说，最好的解决方案可能相当复杂是很自然的。200,000 行的Java包感觉为宜。
但是，仅仅实现一个单一算法时，算法代码往往很短。当你只实现一种算法时，在写之前你确实知道要写什么，你不需要关注任何不必要的具有很大性能影响的抽象概念。

注释
[1] 我真的不确定如何计算Stanford解析器的代码行数。它的jar文件装载了200k大小内容，包括大量不同的模型。这并不重要，但在50k左右似乎是安全的。
[2]例如，如何解析“John's school of music calls”"htmlcode">

java -mx10000m -cp "$scriptdir/*:" edu.stanford.nlp.parser.lexparser.LexicalizedParser -outputFormat "penn" edu/stanford/nlp/models/lexparser/englishFactored.ser.gz $*



应用了一个小的后处理，撤销Stanford 解析器为数字添加的假设标记，使数字符合 PTB 标记：

 




"""Stanford parser retokenises numbers. Split them."""
import sys
import re
 
qp_re = re.compile('\xc2\xa0')
for line in sys.stdin:
  line = line.rstrip()
  if qp_re.search(line):
    line = line.replace('(CD', '(QP (CD', 1) + ')'
    line = line.replace('\xc2\xa0', ') (CD ')
  print line



由此产生的PTB格式的文件转换成使用 Stanford 转换器的依赖关系：

 




for f in $1/*.mrg; do
 echo $f
 grep -v CODE $f &gt; "$f.2"
 out="$f.dep"
 java -mx800m -cp "$scriptdir/*:" edu.stanford.nlp.trees.EnglishGrammaticalStructure   -treeFile "$f.2" -basic -makeCopulaHead -conllx &gt; $out
done



我不能轻易的读取了，但它应该只是使用相关文献的一般设置，将一个目录下的每个.mrg文件转换成一个CoNULL格式的 Stanford 基本依赖文件。
接着我从华尔街日报语料库第22条转换了黄金标准树进行评估。准确的分数是指所有未标记标识中未标记的附属分数（如弧头索引）
为了训练 parser.py，我将华尔街日报语料库 02-21 的黄金标准 PTB 树结构输出到同一个转换脚本中。
一言以蔽之，Stanford 模型和 parser.py 在同一组语句中进行训练，在我们知道答案的持有测试集上进行预测。准确性是指我们答对多少正确的语句首词。
在一个 2.4Ghz 的 Xeon 处理器上测试速度。我在服务器上进行了实验，为 Stanford 解析器提供了更多内存。parser.py 系统在我的MacBook Air上运行良好。在parser.py 的实验中，我使用了PyPy；与早期的基准相比，CPython大约快了一半。
parser.py 运行如此之快的一个原因是它进行未标记解析。根据以往的实验，经标记的解析器可能慢400倍，准确度提高大约1%。如果你能访问数据，使程序适应已标记的解析器对读者来说将是很好的锻炼机会。
RedShift 解析器的结果是从版本 b6b624c9900f3bf 取出的，运行如下：

 




./scripts/train.py -x zhang+stack -k 8 -p ~/data/stanford/train.conll ~/data/parsers/tmp
./scripts/parse.py ~/data/parsers/tmp ~/data/stanford/devi.txt /tmp/parse/
./scripts/evaluate.py /tmp/parse/parses ~/data/stanford/dev.conll