In computational linguistics, ambiguity is usually the enemy. Most researchers focus on genuine ambiguity—when a sentence like "I saw the man with the telescope" has two distinct meanings. However, a more insidious problem often lurks within the grammar itself: spurious ambiguity.
Spurious ambiguity occurs when a formal grammar provides multiple distinct ways to derive the exact same semantic interpretation or structural output. It is not a property of the language's meaning, but a redundancy in the mathematical rules used to process it. As Masaru Tomita noted in An Efficient Context-Free Parsing Algorithm for Natural Languages, maintaining separate parsing states for every possible interpretation leads to exponential growth in resource requirements. When those "interpretations" are actually identical, the system performs massive amounts of redundant work.
The Computational Cost of Redundancy
Why does it matter if a parser finds ten ways to say the same thing? The issue is twofold: efficiency and mathematical tractability.
First, redundancy wastes the "search budget." In Statistical Machine Translation, David Chiang showed in A Hierarchical Phrase-Based Model for Statistical Machine Translation that spurious ambiguity generates multiple internal derivations for the same output string. This clutters $n$-best lists with identical candidates, preventing the system from exploring a diverse range of potential translations.
Second, redundancy breaks probabilistic modeling. As Khalil Sima'an proved in Computational Complexity of Probabilistic Disambiguation by means of Tree-Grammars, finding the Most Probable Derivation is easy, but finding the Most Probable Parse (the actual structure) becomes NP-hard when multiple derivations lead to the same result. This is because the algorithm must sum the probabilities of every possible path to that result, transforming a simple search into a combinatorial nightmare.
The CCG Case Study: Associativity as a Bug
Combinatory Categorial Grammar (CCG) is perhaps the most famous victim of this phenomenon. Because CCG uses operations like functional composition, it is "associative." You can group words $(A+B)+C$ or $A+(B+C)$ and arrive at the same semantic meaning.
Remo Pareschi and Mark Steedman addressed this in A Lazy way to Chart-Parse with Categorial Grammars, arguing that parsers should avoid building redundant, semantically equivalent trees. Without such "lazy" or "normal-form" constraints, the search space for a single sentence can explode, as Mark Hepple observed in Maximal Incrementality in Linear Categorial Deduction.
Solutions: Normal Forms and Canonical Paths
The primary strategy for defeating spurious ambiguity is to enforce a Normal Form—a set of restrictions that ensures only one "canonical" derivation is allowed for any given structure.
- Canonical Sequences: In transition-based parsing, Shay B Cohen, Giorgio Satta, and Carlos Gómez-Rodríguez proposed in Elimination of Spurious Ambiguity in Transition-Based Dependency Parsing a method to enforce a single sequence of operations for every dependency tree. This makes training probabilistic models more efficient because the model doesn't have to guess which of the many valid paths to follow.
- Grammar Constraints: In word alignment for translation, Shujian Huang and colleagues introduced the LGFN (Left-heavy Grammar) in Dealing with Spurious Ambiguity in Learning ITG-based Word Alignment. By forcing the grammar to always branch in a specific way, they eliminated redundant alignments, leading to faster and more accurate learning.
- Dependency-Focused Parsing: Instead of scoring the derivation (how the tree was built), researchers like Wenduan Xu and Stephen Clark shifted the focus to the dependencies (the final meaning) in Shift-Reduce CCG Parsing with a Dependency Model. If the model only cares about the final semantic relations, the specific path taken to get there becomes irrelevant, effectively neutralizing the impact of spurious ambiguity.
Embracing Ambiguity with Oracles
An alternative to eliminating redundancy is to make the parser smarter about it. Xu Sun and Xuancheng Ren introduced the Hybrid Oracle in Hybrid Oracle: Making Use of Ambiguity in Transition-based Chinese Dependency Parsing. Rather than forcing the model to follow one arbitrary "correct" path during training, the Hybrid Oracle allows the model to learn from all valid sequences that lead to the correct parse. This approach treats spurious ambiguity not as a bug to be deleted, but as a source of flexible training data.
By identifying and collapsing these redundant paths—whether through normal forms, canonical sequences, or smarter oracles—researchers have transformed theoretically "intractable" grammars into efficient tools for real-world language processing.