Abstract
Weighted finite-state transducers (WFSTs) suffer from the lack of a general training algorithm. Training is particularly challenging for transducers assembled via finite-state operations such as composition, minimization, union, concatenation, and closure, as these operations yield complex parameter tying. We formulate a "parameterized FST" paradigm and provide training algorithms, including a general bookkeeping trick—the "expectation semiring"—that cleanly and efficiently computes expectations and gradients.
Introduction
Weighted finite-state transducers are fundamental tools in natural language processing, powering systems for speech recognition, machine translation, and morphological analysis. Their primary strength lies in their closure under various algebraic operations, most notably composition. This allows researchers to build complex, modular systems by piping together simpler, specialized transducers.
However, a significant bottleneck has persisted: parameter estimation. While specialized algorithms exist for specific models—such as the Forward-Backward algorithm for Hidden Markov Models (HMMs)—there has been no general-purpose method to train the weights of an arbitrary FST, especially one constructed through a sequence of operations. Historically, weights were often trained externally and manually mapped back onto arcs, a process that becomes intractable when parameters are tied across different parts of a complex, composed machine.
The Parameterized FST Framework
The core of the proposed solution is the "parameterized FST." Instead of treating arc weights as independent scalar values, they are treated as functions of a smaller set of underlying parameters, $\theta$. This formulation naturally supports parameter tying, where a single parameter can influence multiple arcs across different components of a system. It also facilitates the use of log-linear models, where arc weights are defined as products of feature strengths.
As shown in Figure 1, the composition of two machines (b and c) results in a more complex machine (a). The weights in the resulting machine are derived from the original components. For instance, the arc a:x/.63 in (a) is the result of composing a:p/.7 from (b) with p:x/.9 from (c), where $0.7 \times 0.9 = 0.63$. Training such a system requires a way to propagate gradients or expectations back through these operations to the original parameters.
The Expectation Semiring
The technical breakthrough of this work is the introduction of the expectation semiring. In FST theory, a semiring defines the operations for "adding" (combining paths) and "multiplying" (sequencing transitions) weights. Eisner proposes a novel semiring where each weight is represented as a pair: $\langle p, v \rangle$, where $p$ is a probability and $v$ is an expected value vector.
The "magical" property of this semiring lies in its multiplication operation: $$\langle p_1, v_1 \rangle \otimes \langle p_2, v_2 \rangle = \langle p_1 p_2, p_1 v_2 + v_1 p_2 \rangle$$ This definition perfectly mirrors the product rule from calculus. By running standard FST algorithms—such as composition or the algebraic path problem—using this semiring, the system automatically and efficiently tracks how probabilities and feature counts accumulate. This allows for the application of Expectation-Maximization (EM) or gradient-based optimization (like L-BFGS) to any FST-based model, regardless of its construction history.
Efficiency and Results
For acyclic transducers, which are common in many NLP tasks, training values can be computed in $O(m)$ time, where $m$ is the number of edges. This matches the efficiency of the classic Forward-Backward algorithm while offering far greater generality. The framework also provides a unified view of NLP, demonstrating that diverse tasks like chunking, alignment, and speech recognition can be trained using the same underlying code.
Furthermore, the paper proves the theoretical equivalence of joint probabilistic relations, Markovian FSTs, and probabilistic regular expressions. This unification simplifies the theoretical landscape and provides a robust foundation for future FST-based research.
Conclusion and Future Work
By introducing the expectation semiring and the parameterized FST paradigm, this work removes a major barrier to using modular, composed finite-state models. While challenges remain—such as the $O(n^3)$ complexity for certain cyclic machines and the risk of local maxima in non-convex optimization—the framework provides a powerful, general-purpose toolkit for the NLP community. Future extensions could apply these principles to more complex structures, such as Synchronous Context-Free Grammars (SCFGs), potentially revolutionizing training for hierarchical models.
Summary updated