We show that most structured prediction problems can be solved in linear time
and space by considering them as partial orderings of the tokens in the input
string. Our method computes real numbers for each token in an input string and
sorts the tokens accordingly, resulting in as few as 2 total orders of the
tokens in the string. Each total order possesses a set of edges oriented from
smaller to greater tokens. The intersection of total orders results in a
partial order over the set of input tokens, which is then decoded into a
directed graph representing the desired structure. Experiments show that our
method achieves 95.4 LAS and 96.9 UAS by using an intersection of 2 total
orders, 95.7 LAS and 97.1 UAS with 4 on the English Penn Treebank dependency
parsing benchmark. Our method is also the first linear-complexity coreference
resolution model and achieves 79.2 F1 on the English OntoNotes benchmark, which
is comparable with state of the art.

本文提出一种基于部分排序的线性时间和空间复杂度算法来解决结构化预测问题，其中通过计算输入字符串中每个令牌的实数并相应地进行排序，得到了尽可能少的 2 个令牌总订单，这些总订单的交集形成了令牌的部分排序，并被解码成代表所需结构的有向图。在英语依存句法分析基准测试上，我们的方法通过使用 2 个总订单和 4 个总订单分别获得 95.4 LAS 和 96.9 UAS 以及 95.7 LAS 和 97.1 UAS 的结果；此外，该方法还是第一个实现了线性复杂度共指消解模型 —— 在英语 OntoNotes 基准测试上获得了 79.2 F1 分数，与现有技术相当。