Phonological Comprehension and the Compilation of Optimality Theory

Jason EisnerACL 2002 · OpenReview

Introduction: The Computational Asymmetry of OT

In linguistics, Optimality Theory (OT) provides a framework for understanding how speakers select the most "optimal" surface form (pronunciation) for an underlying mental representation. This selection process involves evaluating a set of candidates against a hierarchy of ranked constraints. While the computational properties of production (mapping an input to an output) are well-understood and can be modeled using finite-state transducers (FSTs), the inverse process—comprehension (mapping an output back to its possible inputs)—presents a significant challenge.

The Problem: The "Counting Trap"

The primary hurdle in modeling comprehension within classical OT is the reliance on global violation counting. For instance, a constraint like NoCODA might penalize a candidate based on the total number of codas it contains. Because finite-state automata have a finite number of states, they cannot track an arbitrary number of violations across an infinitely long string.

Jason Eisner demonstrates that this global counting can lead to "non-regular" sets of possible inputs. If a comprehension system must find all inputs that could have produced a specific output, and the grammar relies on comparing total counts (similar to the non-regular language $a^n b^n$), the resulting set of inputs may exceed the power of finite-state tools. This makes standard FST-based methods inapplicable to classical OT comprehension.

Methodology: A Unified Algebraic Framework

To resolve this, the paper proposes a General Presentation of OT that treats all components—underlying forms, surface forms, and candidates—as strings or regular relations. The core of this framework is the Harmony Ordering ($\\succ$), a mathematical relation that determines which candidate is "better" than another.

Eisner introduces a generalized optimality operator ($\\circ\\circ_H$) that combines candidate sets with constraints and harmony orderings. The central theorem of the paper proves that if the harmony ordering itself is a regular relation, the entire OT grammar can be compiled into a single FST. Once compiled, comprehension becomes a simple matter of inverting the transducer.

Key Insights: Directionality vs. Global Counting

The solution to the "counting trap" lies in moving from global integers to more "local" evaluation methods, such as Directional OT. In this approach, violations are compared from left-to-right (or right-to-left) rather than being summed into a single total.

Comparison of classical OT (global counting) and directional OT (local evaluation) for the input 'bantodibo'.

As shown in Figure 3, classical OT (tableau c) evaluates candidates based on the total number of violations (e.g., ** vs ***!). In contrast, directional OT (tableau d) evaluates violations at specific positions ($\\sigma_1, \\sigma_2, \\dots$). This positional evaluation is a regular relation, making it computationally efficient and avoiding linguistic anomalies like "majority rule" effects—patterns where a language chooses a form simply because it has fewer total violations, even if those violations are distributed in ways never seen in human speech.

Key Results and Implications

The paper provides two major contributions:

  1. Formal Proof of Non-Regularity: A rigorous proof that classical OT can generate non-regular comprehension sets, necessitating a shift in formalism for computational tractability.
  2. The Compilation Theorem: A proof that any OT grammar with a regular harmony ordering can be compiled into an FST. This unifies various "flavors" of OT (Inviolable, Binary, 3-bounded, and Directional) into a single algebraic notation.

Furthermore, this framework simplifies the implementation of Directional OT, replacing complex automaton constructions with transparent regular expressions.

Conclusion

By shifting the focus from global violation counts to local, directional comparisons, Eisner provides a way to bring OT comprehension into the realm of finite-state processing. This unified framework not only solves a long-standing computational problem but also aligns more closely with observed linguistic phenomena. These finite-state representations offer a promising path forward for developing realistic learning algorithms that model how humans acquire complex phonological systems.

Summary updated

Abstract

This paper ties up some loose ends in finite-state Optimality Theory. First, it discusses how to perform comprehension under Optimality Theory grammars consisting of finite-state constraints. Comprehension has not been much studied in OT; we show that unlike production, it does not always yield a regular set, making finite-state methods inapplicable. However, after giving a suitably flexible presentation of OT, we show carefully how to treat comprehension under recent variants of OT in which grammars can be compiled into finite-state transducers. We then unify these variants, showing that compilation is possible if all components of the grammar are regular relations, including the harmony ordering on scored candidates. A side benefit of our construction is a far simpler implementation of directional OT (Eisner, 2000).
BibTeX
@inproceedings{eisner2002phonological,
  author = {Jason Eisner},
  title = {{Phonological Comprehension and the Compilation of Optimality Theory}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2002},
  url = {https://openreview.net/forum?id=Bybgb3lubB},
}
Figure