High order dependency parsing leverages high order features such as siblings
or grandchildren to improve state of the art accuracy of current first order
dependency parsers. The present paper uses biaffine scores to provide an
estimate of the arc scores and is then propagated into a graphical model. The
inference inside the graphical model is solved using dual decomposition. The
present algorithm propagates biaffine neural scores to the graphical model and
by leveraging dual decomposition inference, the overall circuit is trained
end-to-end to transfer first order informations to the high order informations.

本研究提出了一种使用双仿射算法将双仿射神经评分传播到图模型中的高阶依存分析方法来提高一阶依存分析器的精度。

神经电位传递用于高阶依存句法分析

Transferring Neural Potentials For High Order Dependency Parsing

Accurately segmenting a citation string into fields for authors, titles, etc.
is a challenging task because the output typically obeys various global
constraints. Previous work has shown that modeling soft constraints, where the
model is encouraged, but not require to obey the constraints, can substantially
improve segmentation performance. On the other hand, for imposing hard
constraints, dual decomposition is a popular technique for efficient prediction
given existing algorithms for unconstrained inference. We extend the technique
to perform prediction subject to soft constraints. Moreover, with a technique
for performing inference given soft constraints, it is easy to automatically
generate large families of constraints and learn their costs with a simple
convex optimization problem during training. This allows us to obtain
substantial gains in accuracy on a new, challenging citation extraction
dataset.

本文介绍一种通过使用软约束的方式对引文字符串进行分割的方法，并使用双重分解技术实现了在约束条件下的预测和凸优化问题进行训练，从而能够在新的引文提取数据集上获得显著的准确性提升。

应用于引文领域提取的软线性约束学习

Learning Soft Linear Constraints with Application to Citation Field  Extraction

Dual decomposition, and more generally Lagrangian relaxation, is a classical
method for combinatorial optimization; it has recently been applied to several
inference problems in natural language processing (NLP). This tutorial gives an
overview of the technique. We describe example algorithms, describe formal
guarantees for the method, and describe practical issues in implementing the
algorithms. While our examples are predominantly drawn from the NLP literature,
the material should be of general relevance to inference problems in machine
learning. A central theme of this tutorial is that Lagrangian relaxation is
naturally applied in conjunction with a broad class of combinatorial
algorithms, allowing inference in models that go significantly beyond previous
work on Lagrangian relaxation for inference in graphical models.

本篇论文概述了 Lagrangian relaxation 的技术，介绍了应用该方法的示例算法以及在实现过程中的一些实际问题，并阐明了 Lagrangian relaxation 自然与广泛类的组合算法相结合，用于推理图形模型中的信息，在机器学习领域具有重要实际意义。

自然语言处理中的对偶分解和 Lagrange 松弛推理教程

A Tutorial on Dual Decomposition and Lagrangian Relaxation for Inference  in Natural Language Processing

Dual decomposition provides a tractable framework for designing algorithms
for finding the most probable (MAP) configuration in graphical models. However,
for many real-world inference problems, the typical decomposition has a large
integrality gap, due to frustrated cycles. One way to tighten the relaxation is
to introduce additional constraints that explicitly enforce cycle consistency.
Earlier work showed that cluster-pursuit algorithms, which iteratively
introduce cycle and other higherorder consistency constraints, allows one to
exactly solve many hard inference problems. However, these algorithms
explicitly enumerate a candidate set of clusters, limiting them to triplets or
other short cycles. We solve the search problem for cycle constraints, giving a
nearly linear time algorithm for finding the most frustrated cycle of arbitrary
length. We show how to use this search algorithm together with the dual
decomposition framework and clusterpursuit. The new algorithm exactly solves
MAP inference problems arising from relational classification and stereo
vision.

本文介绍了双重分解及其在图形模型中的应用，以及解决在此框架下由于困惑循环而产生的整数相差较大的问题的方法，介绍了引入循环一致性和其他高阶一致性约束的基于簇的追踪算法，以及利用循环约束搜索算法和双重分解框架综合使用的算法，可以精确地解决由关系分类和立体视觉产生的 MAP 推断问题。