The connection between dependency trees and spanning trees is exploited by
the NLP community to train and to decode graph-based dependency parsers.
However, the NLP literature has missed an important difference between the two
structures: only one edge may emanate from the root in a dependency tree. We
analyzed the output of state-of-the-art parsers on many languages from the
Universal Dependency Treebank: although these parsers are often able to learn
that trees which violate the constraint should be assigned lower probabilities,
their ability to do so unsurprisingly de-grades as the size of the training set
decreases. In fact, the worst constraint-violation rate we observe is 24%.
Prior work has proposed an inefficient algorithm to enforce the constraint,
which adds a factor of n to the decoding runtime. We adapt an algorithm due to
Gabow and Tarjan (1984) to dependency parsing, which satisfies the constraint
without compromising the original runtime.

该研究分析了依存树和生成树之间的关系，发现依存树的根节点只能有一条边出去，提出了一种有效的算法解决这个约束问题，并且没有影响原来的运行时间。

请注意根节点：解码依存句法分析的树形结构

Please Mind the Root: Decoding Arborescences for Dependency Parsing

We introduce two first-order graph-based dependency parsers achieving a new
state of the art. The first is a consensus parser built from an ensemble of
independently trained greedy LSTM transition-based parsers with different
random initializations. We cast this approach as minimum Bayes risk decoding
(under the Hamming cost) and argue that weaker consensus within the ensemble is
a useful signal of difficulty or ambiguity. The second parser is a
"distillation" of the ensemble into a single model. We train the distillation
parser using a structured hinge loss objective with a novel cost that
incorporates ensemble uncertainty estimates for each possible attachment,
thereby avoiding the intractable cross-entropy computations required by
applying standard distillation objectives to problems with structured outputs.
The first-order distillation parser matches or surpasses the state of the art
on English, Chinese, and German.

介绍了两个第一阶段基于图的依存解析器，第一个是通过集成学习同质模型的共识解析器，利用最小贝叶斯风险解码法和 Hamming 代价，结合集成中的不确定性评估进行训练，第二个则是将集成模型压缩成单一模型的 'distillation' 解析器，利用新颖的结构化铰链损失函数避免了普通 'distillation' 目标的不可解交叉熵，首次在英语、汉语和德语上达到或超过了现有最先进水平。