Arc-Factored Model

The defining characteristic of arc-factored models is the independence assumption: the score of a dependency tree is simply the sum of the scores of its individual arcs. This means the model treats each head-dependent pair in isolation, ignoring interactions between sibling arcs, grandparent relations, or other higher-order structural contexts. While this simplifies inference to a maximum spanning tree problem, it limits the model's ability to capture complex syntactic phenomena like coordinated structures or nested dependencies.

Because the total tree score factorizes over individual arcs, finding the highest-scoring parse reduces to finding the maximum spanning tree (MST) in a complete directed graph. For projective parsing, this can be solved with dynamic programming in O(n³) time using the Eisner algorithm. For non-projective structures, the Chu-Liu/Edmonds algorithm finds the optimal tree in O(n²) time, enabling efficient global inference without beam search or greedy approximations.

Each potential dependency arc from head h to dependent d receives a score computed from locally extracted features. In neural arc-factored models, these scores are typically computed using biaffine attention over contextualized word representations:

• The head representation and dependent representation are passed through a bilinear transformation
• This produces an n × n score matrix for a sentence of length n
• Edge labels are scored separately using a tensor-based biaffine classifier that considers both the head and dependent representations

The first-order factorization prevents the model from conditioning arc decisions on sibling arcs or grandparent arcs. This creates known failure modes:

• Prepositional phrase attachment: Cannot model that a verb's existing objects influence PP attachment decisions
• Coordination structures: Cannot enforce parallelism between conjuncts
• Non-local agreement: Cannot capture long-distance subject-verb agreement patterns Higher-order models address these by adding sibling and grandparent factors, at the cost of NP-hard inference.

Arc-factored models support global training via maximum likelihood estimation over the full tree structure. Unlike transition-based parsers that make local decisions and suffer from error propagation, graph-based arc-factored models can be trained to maximize the probability of the correct tree given all possible arcs simultaneously. This is typically done using a margin-based hinge loss or cross-entropy loss over the normalized tree probabilities, providing more robust learning signals.

When projectivity is enforced, arc-factored models use the Eisner algorithm — a bottom-up dynamic programming approach with O(n³) time complexity and O(n²) space. The algorithm builds spans incrementally, distinguishing between incomplete spans (missing the head on one side) and complete spans (head found, dependencies resolved internally). This guarantees an exact solution for the highest-scoring projective dependency tree under the first-order factorization.

The global parsing paradigm that directly scores all possible arcs in a sentence simultaneously, treating the problem as finding a maximum spanning tree. Unlike transition-based methods, graph-based models like the arc-factored approach can naturally handle non-projective dependencies by using the Chu-Liu/Edmonds algorithm for exact decoding. This global view mitigates error propagation but typically incurs higher computational cost than greedy alternatives.

The primary evaluation metric for dependency parsers, measuring the percentage of tokens that receive both the correct syntactic head and the correct dependency relation label. For an arc-factored model, LAS directly reflects the quality of the local scoring function. A token is scored correct only if both the head index and the relation type match the gold-standard annotation exactly.

A neural mechanism that computes scores for all possible head-dependent pairs using a bilinear transformation. In deep arc-factored models, biaffine attention replaces traditional linear scoring: a learned weight matrix projects head and dependent representations into a joint space. This enables efficient, parallelized computation of the full arc score matrix, forming the foundation of the Deep Biaffine Parser architecture by Dozat and Manning.

The alternative parsing paradigm that processes sentences incrementally from left to right using a stack and buffer configuration. Unlike the global arc-factored approach, transition-based parsers apply a sequence of shift-reduce actions to build trees greedily. While offering linear-time complexity, they suffer from error propagation where early mistakes cascade. Dynamic oracles partially mitigate this limitation during training.