Introduction
In syntactic dependency parsing, the objective is to map the grammatical relationships between words in a sentence, typically represented as a directed tree. Traditionally, ensuring that these trees were "projective" (meaning edges do not cross when drawn above the sentence) required explicit structured learning and complex decoding algorithms, such as Eisner’s algorithm.
However, recent state-of-the-art neural parsers have largely moved away from these explicit constraints. Models like those proposed by Dozat and Manning (2017) often use simple cross-entropy loss and "approximate" decoding, yet they frequently outperform their more complex predecessors. This paper investigates the theoretical underpinnings of this shift, addressing two primary questions: Is there a hidden, faster algorithm for projective decoding, and how do "simple" neural architectures manage to produce high-quality structured outputs without explicit guidance?
The Computational Complexity of Projective Decoding
The author first addresses the possibility of a more efficient decoding algorithm. By employing a reduction from the 3k-Clique problem, the paper establishes a formal lower bound for projective Maximum Spanning Tree (MST) decoding. The findings prove that no "sub-cubic" algorithm (faster than $O(n^3)$) exists for this task, assuming the Exponential Time Hypothesis (ETH) holds. This establishes that the $O(n^3)$ complexity of classical algorithms like Eisner’s is likely a fundamental barrier, rather than a limitation of previous research.
RNNs as Implicit Decoders
Given that no faster algorithm exists, the paper explores how neural networks achieve such high performance. The author provides a formal construction demonstrating that standard Recurrent Neural Networks (RNNs) using ReLU activation functions are expressive enough to simulate Eisner’s algorithm within their hidden states.
ReLU as a Logic Gate
The core of this simulation lies in the ability of ReLUs to perform conditional logic. The author demonstrates that the max(a, b) operation—a requirement for the dynamic programming steps in Eisner's algorithm—can be rewritten using only linear combinations and ReLUs:
$$max(a, b) = 0.5 \cdot (ReLU(a-b) + ReLU(b-a) + ReLU(a) + ReLU(b))$$
Simulating Dynamic Programming
By utilizing approximately 25 matrices and $O(n^2)$ space, the author shows that an RNN can effectively "calculate" the dynamic programming table as it processes the input. This suggests that the recurrent layers in modern parsers are not merely encoding features; they possess the mathematical capacity to perform the entire decoding algorithm internally.
Empirical Context and Insights
The paper references performance on the Penn Treebank (PTB), noting that "structure-less" parsers achieve competitive results (e.g., 92.61% UAS on PTB) without explicit structural decoding at test time. Instead, these models often simply select the maximum weighted incoming arc for each word.
The theoretical work suggests that "structure-free" is a misnomer. Even if a researcher does not program an explicit MST algorithm into the model, the network has the capacity to "discover" and execute that structure-building logic within its weights. This provides a rigorous explanation for why modern neural architectures are so effective at tasks that previously required hand-coded algorithmic constraints.
Limitations and Future Directions
While the paper proves that an RNN can simulate Eisner’s algorithm, it does not prove that current models actually learn this specific algorithm during training. The construction proves capacity, not necessarily the specific behavior of trained weights. Additionally, the simulation assumes high numerical precision for storing DP tables in hidden states, which may vary in real-world hardware implementations.
Future work may extend this analysis to other neural topologies and explore the formal relationship between deep learning architectures and other classical algorithmic problems in natural language processing.
Summary updated