Linear-Time Modeling of Linguistic Structure: An Order-Theoretic Perspective (2023)

Abstract: Tasks that model the relation between pairs of tokens in a string are a vital part of understanding natural language. Such tasks, in general, require exhaustive pair-wise comparisons of tokens, thus having a quadratic runtime complexity in the length of the string. We show that these exhaustive comparisons can be avoided, and, moreover, the complexity of such tasks can be reduced to linear by casting the relation between tokens as a partial order over the string. Our method predicts real numbers for each token in a string in parallel and sorts the tokens accordingly, resulting in total orders of the tokens in the string. Each total order implies a set of arcs oriented from smaller to greater tokens, sorted by their predicted numbers. The intersection of total orders results in a partial order over the set of tokens in the string, which is then decoded into a directed graph representing the desired linguistic structure. Our experiments on dependency parsing and coreference resolution show that our method achieves state-of-the-art or comparable performance. Moreover, the linear complexity and parallelism of our method double the speed of graph-based coreference resolution models, and bring a 10-times speed-up over graph-based dependency parsers.

## introduction strings of tokens in natural language are not constructed arbitrarily. indeed, which tokens co-occur within the same string is highly structured according to the rules of the language. understanding such structures is critical to the comprehension of natural language. in natural language processing (nlp), many structured prediction tasks aim to automatically extract the underlying structure that dictates the relationship between the tokens in a string of text. examples of such tasks include dependency parsing, semantic parsing, and coreference resolution. these tasks involve predicting complex and hierarchical output structures, making them inherently more challenging than their classification or regression counterparts. this paper contributes a novel and generic framework for structured prediction with empirical evidence from dependency parsing and coreference resolution. many machine learning models for structured prediction score and predict graphs @xcite , in which the vertices represent the tokens in the string and the edges represent the relations between them. one common strategy to model a graph is to decompose it into smaller subgraphs that are tractable @xcite .2). for example, arc-factored models @xcite score a graph only using the score of each constituent edge. however, even with such simplification, the computational costs of arc-factored models are superlinear. the reason is that one needs to exhaustively compute scores for all possible edges in the graph, which, in general, requires at least quadratic number of computations with respect to the length of the string. another common strategy employs weighted transition-based systems @xcite @xcite . they decompose structures into transitions between intermediate model states and do offer linear-time algorithms. however, in general, predicting the transitions between states cannot be parallelized, which is another worrying limitation. the authors of this paper contend the limitations of both graphbased and transition-based models are frustrating in an era when researchers are processing longer and longer texts @xcite . from a more abstract perspective, the mathematical and algorithmic foundation on which structured prediction models rest can be regarded as a design choice. graph-based and transition-based modeling are both specific design choices. these design (a) an example dependency structure. the root arc and arc labels are omitted. figure 1 : an overview of our method. to model a linguistic structure, represented as a directed graph in fig. 1a , we first convert it into a token-split structure (see §3.4) in fig. 1b , which is a partial order, to remove undesired transitivity. then, 2 real numbers are predicted for each vertex in fig. 1b . the positions of vertices in fig. 1c in the inequalities indicate the real numbers the vertices are mapped to. the vertices are sorted twice accordingly, resulting in a realizer (see def. 3.8) of 2 total orderings, each possessing a set of edges e 1 and e 2 . the exact set of desired edges in the original structure can be restored from the intersection of e 1 and e 2 (see §3.3). some qualitative examples are included in app. j. concretely, we treat structured prediction as a regression task. because the set of real numbers r is naturally ordered by <, we use real numbers as the proxy for determining the partial order. we predict k numbers for each token and sort the tokens k times accordingly. two tokens are partially ordered by ≺ if and only if they are ordered @xmath0. we further provide an efficiency guarantee based on the well-established result in order theory that partial orders satisfying particular conditions can be represented as the intersection of as few as @xmath1. we show that most structures in natural language, including trees, alignments, and set partitions, satisfy these conditions. this result enables us to develop a linear-time algorithm for predicting such structures. fig. 1 gives an illustrative example of our framework applied to dependency parsing, in which the structure being modeled is a tree. ## motivation we now provide high-level motivation for order-theoretic structured prediction. ## order and structure in this section, we describe an order-theoretic treatment for linguistic structure prediction. specifically, we treat the structure to be predicted as a partially ordered set, i.e., a set equipped with a transitive relation ≺. we begin by revisiting how linguistic structures are represented as graphs. ## a neural parameterization in this section, we describe the core technical contribution of our work. we show how to model partially ordered structures with a neural model. specifically, we define a parameterized realizer of def. 3.8 and an objective function for training the realizer to model the token-split structures. we also give algorithms for efficient training and decoding. ## experiments we report the experimental results on two representative linguistic structure prediction problems in nlp, namely dependency parsing and coreference resolution. the graph-theoretic definitions of these tasks are given in examples 3.2 and 3.3. we first convert the linguistic structures to partially ordered (token-split) structures as described in §3.4, and then apply the neural method described in §4 to model the partially ordered structures. ## conclusion in this paper, we propose an order-theoretic treatment of linguistic structured prediction. theoretical and empirical results show that most linguistic structure prediction problems can be solved in linear time and memory by framing them as partial orderings of the tokens in the input string. we demonstrate the effectiveness of our method on dependency parsing and coreference resolution, setting the new state-of-the-art accuracy in some cases and achieving significant efficiency improvements.