正确的解析是连接“with”和“pizza”，而错误的解析将“with”和“eat”联系在了一起：
过去的一些年，自然语言处理（NLP）社区在语法分析方面取得了很大的进展。现在，小小的Python实现可能比广泛应用的Stanford解析器表现得更出色。
在你的手机中输入这样一条指令是非常友善的：
SetvolumetozerowhenI'minameeting,unlessJohn'sschoolcalls.
接着进行适当的策略配置。在Android系统上，你可以应用Tasker做这样的事情，而NL接口会更好一些。接收可以编辑的语义表示，你就能了解到它认为你表达的意思，并且可以修正他的想法，这样是特别友善的。
这项工作有很多问题需要解决，但一些种类的句法形态绝对是必要的。我们需要知道：
UnlessJohn'sschoolcalls,whenI'minameeting,setvolumetozero
是解析指令的又一种方式，而
UnlessJohn'sschool,callwhenI'minameeting
表达了完全不同的意思。
依赖解析器返回一个单词与单词间的关系图，使推理变得更容易。关系图是树形结构，有向边，每个节点（单词）有且仅有一个入弧（头部依赖）。
用法示例：
>>>parser=parser.Parser()>>>tokens="SetthevolumetozerowhenI'minameetingunlessJohn'sschoolcalls".split()>>>tags,heads=parser.parse(tokens)>>>heads[-1,2,0,0,3,0,7,5,7,10,8,0,13,15,15,11]>>>fori,hinenumerate(heads):...head=tokens[heads[h]]ifh>=1else'None'...print(tokens[i]+'<--'+head])Set<--Nonethe<--volumevolume<--Setto<--Setzero<--towhen<--SetI<--'m'm<--whenin<--'ma<--meetingmeeting<--inunless<--SetJohn<--'s's<--callsschool<--callscalls<--unless一种观点是通过语法分析进行推导比字符串应该稍稍容易一些。语义分析映射有望比字面意义映射更简单。
这个问题最让人困惑的是正确性是由惯例，即注释指南决定的。如果你没有阅读指南并且不是一个语言学家，就不能判断解析是否正确，这使整个任务显得奇怪和虚假。
例如，在上面的解析中存在一个错误：根据Stanford的注释指南规定，“John'sschoolcalls”存在结构错误。而句子这部分的结构是指导注释器如何解析一个类似于“John'sschoolclothes”的例子。
这一点值得深入考虑。理论上讲，我们已经制定了准则，所以“正确”的解析应该相反。如果我们违反约定，有充分的理由相信解析任务会变得更加困难，因为任务和其他语>法的一致性会降低。【2】但是我们可以测试经验，并且我们很高兴通过反转策略获得优势。
我们确实需要惯例中的差异——我们不希望接收相同的结构，否则结果不会很有用。注释指南在哪些区别使下游应用有效和哪些解析器可以轻松预测之间取得平衡。映射树
在决定构建什么样子的关系图时，我们可以进行一项特别有效的简化：对将要处理的关系图结构进行限制。它不仅在易学性方面有优势，在加深算法理解方面也有作用。大部分的>英文解析工作中，我们遵循约束的依赖关系图就是映射树：
树。除了根外，每个单词都有一个弧头。映射关系。针对每对依赖关系（a1,a2）和（b1,b2），如果a1
在解析非映射树方面有丰富的文献，解析无环有向图方面的文献相对而言少一些。我将要阐述的解析算法用于映射树领域。贪婪的基于转换的解析
我们的语法分析器以字符串符号列表作为输入，输出代表关系图中边的弧头索引列表。如果第i个弧头元素是j,依赖关系包括一条边（j,i）。基于转换的语法分析器>是有限状态转换器；它将N个单词的数组映射到N个弧头索引的输出数组。
弧头数组表示了MSNBC的弧头：MSNBC的单词索引是1，reported的单词索引是2，head[1]==2。你应该已经发现为什么树形结构如此方便——如果我们输出一个DAG结构，这种结构中的单词可能包含多个弧头，树形结构将不再工作。
虽然heads可以表示为一个数组，我们确实喜欢保持一定的替代方式来访问解析，以方便高效的提取特征。Parse类就是这样：
classParse(object):def__init__(self,n):self.n=nself.heads=[None]*(n-1)self.lefts=[]self.rights=[]foriinrange(n+1):self.lefts.append(DefaultList(0))self.rights.append(DefaultList(0))defadd_arc(self,head,child):self.heads[child]=headifchild 解析过程的每一步都应用了三种操作之一： SHIFT=0;RIGHT=1;LEFT=2MOVES=[SHIFT,RIGHT,LEFT]deftransition(move,i,stack,parse):globalSHIFT,RIGHT,LEFTifmove==SHIFT:stack.append(i)returni+1elifmove==RIGHT:parse.add_arc(stack[-2],stack.pop())returnielifmove==LEFT:parse.add_arc(i,stack.pop())returniraiseGrammarError("Unknownmove:%d"%move)LEFT和RIGHT操作添加依赖关系并弹栈，而SHIFT压栈并增加缓存中i值。 因此，语法解析器以一个空栈开始，缓存索引为0，没有依赖关系记录。选择一个有效的操作，应用到当前状态。继续选择操作并应用直到栈为空且缓存索引到达输入数组的终点。（没有逐步跟踪是很难理解这种算法的。尝试准备一个句子，画出映射解析树，接着通过选择正确的转换序列遍历完解析树。） 下面是代码中的解析循环： classParser(object):...defparse(self,words):tags=self.tagger(words)n=len(words)idx=1stack=[0]deps=Parse(n)whilestackoridx classPerceptron(object)...defscore(self,features):all_weights=self.weightsscores=dict((clas,0)forclasinself.classes)forfeat,valueinfeatures.items():ifvalue==0:continueiffeatnotinall_weights:continueweights=all_weights[feat]forclas,weightinweights.items():scores[clas]+=value*weightreturnscores这里仅仅对每个特征的类权重求和。这通常被表示为一个点积，然而我发现处理很多类时就不太适合了。 如果认真阅读了词性标记，你可能会发现下面的相似性。我们所做的是将解析问题映射到一个使用“扁平化”解决的序列标记问题，或者非结构化的学习算法（通过贪婪搜索）。特征集 特征提取代码总是很丑陋。语法分析器的特征指的是上下文中的一些标识。 我们指出了上述12个标识的单词表，词性标注，和标识关联的左右孩子数目。 因为使用的是线性模型，特征指的是原子属性组成的三元组。 学习权重和词性标注使用了相同的算法，即平均感知器算法。它的主要优势是，它是一个在线学习算法：例子一个接一个流入，我们进行预测，检查真实答案，如果预测错误则调整意见（权重）。 循环训练看起来是这样的： classParser(object):...deftrain_one(self,itn,words,gold_tags,gold_heads):n=len(words)i=2;stack=[1];parse=Parse(n)tags=self.tagger.tag(words)whilestackor(i+1) 在语法分析中我们面临的问题是不知道如何传递预测序列！通过采用黄金标准树结构，并发现可以转换为树的过渡序列，等等，使得训练得以工作，你获得返回的动作序列，保证执行运动，将得到黄金标准的依赖关系。 问题是，如果语法分析器处于任何没有沿着黄金标准序列的状态时，我们不知道如何教它做出的“正确”运动。一旦语法分析器发生了错误，我们不知道如何从实例中训练。 这是一个大问题，因为这意味着一旦语法分析器开始发生错误，它将停止在不属于训练数据的任何一种状态——导致出现更多的错误。 对于贪婪解析器而言，问题是具体的：一旦使用方向特性，有一种自然的方式做结构化预测。 像所有的最佳突破一样，一旦你理解了这些，解决方案似乎是显而易见的。我们要做的就是定义一个函数，此函数提问“有多少黄金标准依赖关系可以从这种状态恢复”。如果能定义这个函数，你可以依次进行每种运动，进而提问，“有多少黄金标准依赖关系可以从这种状态恢复？”。如果采用的操作可以让少一些的黄金标准依赖实现，那么它就是次优的。 这里需要领会很多东西。 因此我们有函数Oracle（state）: Oracle(state)=|gold_arcs∩reachable_arcs(state)|我们有一个操作集合，每种操作返回一种新状态。我们需要知道： 事实证明，我们可以得出Oracle简化了很多过渡系统。我们正在使用的过渡系统的衍生品——ArcHybrid是Goldberg和Nivre（2013）提出的。 我们把oracle实现为一个返回0-成本的运动的方法，而不是实现一个功能的Oracle(state)。这可以防止我们做一堆昂贵的复制操作。希望代码中的推理不是太难以理解，如果感到困惑并希望刨根问底的花，你可以参考Goldberg和Nivre的论文。 defget_gold_moves(n0,n,stack,heads,gold):defdeps_between(target,others,gold):forwordinothers:ifgold[word]==targetorgold[target]==word:returnTruereturnFalsevalid=get_valid_moves(n0,n,len(stack))ifnotstackor(SHIFTinvalidandgold[n0]==stack[-1]):return[SHIFT]ifgold[stack[-1]]==n0:return[LEFT]costly=set([mforminMOVESifmnotinvalid])#Ifthewordbehinds0isitsgoldhead,Leftisincorrectiflen(stack)>=2andgold[stack[-1]]==stack[-2]:costly.add(LEFT)#Ifthereareanydependenciesbetweenn0andthestack,#pushingn0willlosethem.ifSHIFTnotincostlyanddeps_between(n0,stack,gold):costly.add(SHIFT)#Ifthereareanydependenciesbetweens0andthebuffer,popping#s0willlosethem.ifdeps_between(stack[-1],range(n0+1,n-1),gold):costly.add(LEFT)costly.add(RIGHT)return[mforminMOVESifmnotincostly]进行“动态oracle”训练过程会产生很大的精度差异——通常为1-2%，和运行时的方式没有区别。旧的“静态oracle”贪婪训练过程已经完全过时；没有任何理由那样做了。总结 我认为对于人们来说，最好的解决方案可能相当复杂是很自然的。200,000行的Java包感觉为宜。 [1]我真的不确定如何计算Stanford解析器的代码行数。它的jar文件装载了200k大小内容，包括大量不同的模型。这并不重要，但在50k左右似乎是安全的。 长期以来，增量语言处理算法是科学界的主要兴趣。如果你想要编写一个语法分析器来测试人类语句处理器如何工作的理论，那么，这个分析器需要建立部分解释器。这里有充分的证据，包括常识性反思，它设立我们不缓存的输入，说话者完成表达立即分析。 但与整齐的科学特征相比，当前算法胜出！尽我所能告诉大家，胜出的秘诀就是： 增量。早期的文字限制搜索。错误驱动。训练包含一个发生错误即更新的操作假设。 和人类语句处理的联系看起来诱人。我期待看到这些工程的突破是否带来一些心理语言学方面的进步。参考书目 我所描述的解析器是动态oraclearc-hybrid系统的实现： Goldberg,Yoav;Nivre,Joakim TrainingDeterministicParserswithNon-DeterministicOracles TACL2013 然而，我编写了自己的特征。arc-hybrid系统的最初描述在这里： Kuhlmann,Marco;Gomez-Rodriguez,Carlos;Satta,Giorgio Dynamicprogrammingalgorithmsfortransition-baseddependencyparsers ACL2011 这里最初描述了动态oracle训练方法： ADynamicOracleforArc-EagerDependencyParsing COLING2012 当Zhang和Clark研究定向搜索时，这项工作依赖于以转换为基础的解析器在准确性上的重大突破。他们发表了很多论文，但首选的引用是： Zhang,Yue;Clark,Steven SyntacticProcessingUsingtheGeneralizedPerceptronandBeamSearch ComputationalLinguistics2011(1) Zhang,Yue;Nivre,Joakim Transition-basedDependencyParsingwithRichNon-localFeatures Collins,Michael DiscriminativeTrainingMethodsforHiddenMarkovModels:TheoryandExperimentswithPerceptronAlgorithms EMNLP2002 实验细节 java-mx10000m-cp"$scriptdir/*:"edu.stanford.nlp.parser.lexparser.LexicalizedParser\-outputFormat"penn"edu/stanford/nlp/models/lexparser/englishFactored.ser.gz$*应用了一个小的后处理，撤销Stanford解析器为数字添加的假设标记，使数字符合PTB标记： """Stanfordparserretokenisesnumbers.Splitthem."""importsysimportreqp_re=re.compile('\xc2\xa0')forlineinsys.stdin:line=line.rstrip()ifqp_re.search(line):line=line.replace('(CD','(QP(CD',1)+')'line=line.replace('\xc2\xa0',')(CD')printline由此产生的PTB格式的文件转换成使用Stanford转换器的依赖关系： 接着我从华尔街日报语料库第22条转换了黄金标准树进行评估。准确的分数是指所有未标记标识中未标记的附属分数（如弧头索引） 为了训练parser.py，我将华尔街日报语料库02-21的黄金标准PTB树结构输出到同一个转换脚本中。 一言以蔽之，Stanford模型和parser.py在同一组语句中进行训练，在我们知道答案的持有测试集上进行预测。准确性是指我们答对多少正确的语句首词。 在一个2.4Ghz的Xeon处理器上测试速度。我在服务器上进行了实验，为Stanford解析器提供了更多内存。parser.py系统在我的MacBookAir上运行良好。在parser.py的实验中，我使用了PyPy；与早期的基准相比，CPython大约快了一半。 parser.py运行如此之快的一个原因是它进行未标记解析。根据以往的实验，经标记的解析器可能慢400倍，准确度提高大约1%。如果你能访问数据，使程序适应已标记的解析器对读者来说将是很好的锻炼机会。 RedShift解析器的结果是从版本b6b624c9900f3bf取出的，运行如下： ./scripts/train.py-xzhang+stack-k8-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