Disambiguation of Finite-State Transducers

N. Smaili, P. Cardinal, G. Boulianne, P. DumouchelCOLING 2002

TL;DR

This paper introduces a novel method for disambiguating finite-state transducers (FSTs), a crucial step for efficient speech recognition. By composing phonological rules with pronunciation dictionaries before disambiguation, they achieve a more compact and manageable representation, overcoming limitations of previous approaches.

What Problem Does This Paper Address?

Speech recognition systems often model the search space as a composition of multiple finite-state transducers (FSTs). Each FST represents a step in the recognition process, such as acoustic modeling, phonological rules, and pronunciation dictionaries. A key challenge arises when a pronunciation dictionary (mapping phone sequences to words) is ambiguous – multiple words can share the same phone sequence. This ambiguity prevents the application of standard determinization algorithms, which are essential for reducing redundancy and improving search efficiency. Traditional methods often involve adding special symbols to the dictionary to resolve ambiguity, but this can lead to complex and bloated transducers, especially when combined with phonological rules. This paper aims to address this by proposing a method to disambiguate the composed transducer (phonological rules + dictionary) rather than disambiguating each component separately.

Methods

The core of the paper's contribution lies in its approach to disambiguation. Instead of disambiguating individual transducers (like the dictionary and phonological rules) and then composing them, the authors propose composing them first and then disambiguating the resulting transducer. This is achieved through a novel algorithm that leverages a "fundamental property" of transducers: any cycle must contain at least one transition with an input from a specific alphabet subset (Σ₁).

The process involves:

  1. Composition: Combining the phonological rule transducer (R) and the dictionary transducer (D) into a single transducer T = R ∘ D.
  2. Disambiguation: Applying a transformation (denoted by Ψ) to create an acyclic version of T, removing ambiguity by introducing auxiliary symbols.
  3. Reinsertion: Reintroducing the removed transitions (from the original E₁ set) to obtain an unambiguous transducer T₁.

This approach is underpinned by a fundamental theorem that guarantees the resulting composed transducer T = R ∘ D will also possess the "fundamental property" if R satisfies a specific condition related to its transitions and the output alphabet of D.

Datasets

Not discussed in the paper. The paper mentions a French dictionary with 20,000 words and their pronunciations as an example application, but it's not presented as a formal dataset for evaluation.

Key Insights and Ideas

  • Composition Before Disambiguation: The most significant insight is that composing transducers before disambiguation can lead to more compact and manageable representations compared to disambiguating components individually.
  • "Fundamental Property" for Disambiguation: The paper introduces and utilizes a "fundamental property" (cycles must contain transitions from Σ₁) to characterize ambiguous paths and guide the disambiguation process.
  • Auxiliary Symbols for Disambiguation: The method relies on introducing auxiliary symbols to break ambiguous paths, a common technique, but applied here to the composed transducer.
  • Invariance of the Fundamental Property: A key theorem proves that if a transducer R satisfies a certain condition and D has the fundamental property, then their composition R ∘ D also has the fundamental property. This is crucial for the proposed method's validity.

Key Results

The paper demonstrates that their approach leads to a smaller transducer size compared to previous methods. Table 1 shows a significant reduction in states and transitions when applying their algorithm to a French dictionary and a phonological rule for liaison. For instance, the composed transducer R ∘ D has 115943 states and 151434 transitions, while the disambiguated version ψ(R ∘ D) reduces this to 17955 states and 50769 transitions. This is a substantial improvement over the "old approach" where auxiliary labels were propagated, leading to larger intermediate transducers.

Limitations and Future Work

The authors acknowledge that their disambiguation approach systematically increases the size of the transducer. Their future work will focus on developing a "more effective algorithm for disambiguating an acyclic transducer," aiming to mitigate this size increase.

Summary updated

BibTeX
@inproceedings{smaili2002disambiguation,
  author = {N. Smaili and P. Cardinal and G. Boulianne and P. Dumouchel},
  title = {{Disambiguation of Finite-State Transducers}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2002},
}
Figure