In dependency parsing, a structure is considered projective if its dependency arcs do not cross when drawn above the sentence. While many languages follow this constraint, others—such as Czech, German, and Hindi—exhibit flexible word orders that result in non-projective structures. These crossing arcs present a computational challenge: most efficient parsing algorithms, such as greedy transition-based parsers or cubic-time graph-based parsers, are strictly limited to projective outputs.
Pseudo-projective transformation is a strategy to bridge this gap. Instead of designing more complex, computationally expensive parsers to handle crossing arcs directly, this approach transforms non-projective trees into projective ones that a standard parser can handle, while encoding enough information to recover the original structure afterward.
The Intuition of Arc Lifting
The core mechanism of this transformation is arc lifting. As described by Nivre et al. (2005), a non-projective tree is converted into a projective one by iteratively reattaching a "crossing" dependent to a higher ancestor—such as its head's parent—until the crossing is eliminated.
Imagine a word that has "jumped" out of its expected position. By "lifting" the dependency edge so that the word is temporarily attached to its "grandparent" rather than its "parent," the crossing edge is flattened. Veselá et al. (2004) provided an early formalization of this, proposing recursive algorithms to rearrange nodes to satisfy projectivity while preserving the relative word order.
Trading Structure for Labels
If we simply lift arcs, we lose the information about where the word originally belonged. To solve this, the transformation treats structural complexity as a labeling problem.
When an arc is lifted, its label is augmented with metadata about its original head. Nivre et al. (2006) demonstrate that by encoding the original structural information into these augmented dependency labels, a projective parser can effectively "learn" to signal when an arc has been lifted. Johansson et al. (2007) refined this using a "Head+Path" encoding, which provides a precise roadmap for the post-processing step to follow.
The intuition here is a trade-off: we make the parser's job easier by simplifying the geometry of the tree, but we make the classification task slightly harder by increasing the number of possible labels (e.g., a nsubj label might become nsubj+obj to indicate it was lifted via an object).
Recovery and Reconstruction
The final stage of the process is de-projectivization. Once a projective parser generates a tree with augmented labels, a post-processing heuristic uses that metadata to "lower" the arcs back to their intended heads.
As Nilsson et al. (2007) explain, this recovery process searches for the most likely original attachment points based on the encoded tags. This allows the system to output a final non-projective analysis while using a parser that is internally restricted to projective structures. This two-step transformation—lifting during training and lowering during inference—enables greedy transition-based parsers to maintain their speed while achieving high accuracy on complex linguistic structures, as shown by de Lhoneux et al. (2017).
Applications Beyond Syntactic Parsing
The utility of pseudo-projective transformation extends beyond basic syntax. The authors of various studies have applied these principles to diverse linguistic tasks:
- Semantic Role Labeling: Johansson et al. (2008) and Che et al. (2009) used these transformations to handle long-distance dependencies and non-local links in semantic graphs, mapping them into a format compatible with standard parsers.
- Surface Realization: In natural language generation, Björkelund et al. (2012) showed that edge lifting allows standard linearization algorithms to generate sentences with crossing edges, effectively handling the stylistic "jumps" common in languages like German.
- Deep Linguistic Graphs: Schluter et al. (2009) demonstrated that even complex graph-based relationships, like those in Lexical Functional Grammar (LFG), can be represented as pseudo-projective trees by lifting re-entrancies and encoding them in labels.
By decoupling the handling of non-projectivity from the parsing algorithm itself, pseudo-projective transformation provides a robust, general-purpose framework for processing the world's most structurally complex languages.
Key Foundational Work
Pseudo-Projectivity, A Polynomially Parsable Non-Projective Dependency Grammar (1998) — contributed 2 concept elements to this direction.
Condition of Projectivity in the Underlying Dependency Structures (2004) — contributed 1 concept elements to this direction.