Weighting Finite-State Transductions With Neural Context

Pushpendre Rastogi, Ryan Cotterell, Jason EisnerNAACL 2016 · OpenReview

TL;DR

This paper introduces a novel hybrid approach that combines the strengths of traditional finite-state transducers (FSTs) with the power of recurrent neural networks (RNNs) to improve sequence-to-sequence transduction tasks. By using LSTMs to learn contextual features for FST arc weights, the model achieves state-of-the-art results on morphological reinflection and lemmatization tasks, outperforming both pure FSTs and standard neural sequence-to-sequence models.

What Problem Does This Paper Address?

Many natural language processing tasks, such as converting text to speech or changing word forms (morphological reinflection), involve transforming one sequence of characters into another. Traditionally, these tasks were handled by finite-state transducers (FSTs), which are excellent at modeling alignments between input and output sequences and allow for efficient inference using dynamic programming. However, FSTs typically rely on hand-crafted features for their weights, limiting their ability to capture complex, long-range dependencies in the input. More recent deep learning approaches, like sequence-to-sequence models with attention, can learn rich features but often sacrifice the structured alignment guarantees of FSTs. This paper aims to bridge this gap by combining the structured inference of FSTs with the powerful feature learning capabilities of RNNs.

Methods

The core innovation is a "weighted finite-state automaton" (WFSA) where the weights of the arcs are not fixed but are dynamically computed by a neural network. Specifically, the authors start with an unweighted FST that defines the possible edit operations (like substitutions, insertions, deletions) between input and output strings. This FST is then composed with a representation of the input string to create a dynamic programming lattice. The key novelty lies in how the weights for the arcs in this lattice are calculated.

Instead of relying on hand-crafted features, the authors use a bidirectional LSTM (BiLSTM) to process the input string. The BiLSTM generates context-aware vector representations for substrings of the input. These vector representations, along with information about the specific edit operation (the source and target substrings, and the FST's internal states), are fed into a learned weight function. This function, inspired by log-bilinear models, computes a score for each possible edit at a given position in the input, considering both the local edit and the broader input context. This allows the model to learn complex, data-driven features that go beyond the limited context captured by traditional FST states.

Datasets

The paper evaluates their approach on morphological reinflection and lemmatization tasks using datasets derived from the CELEX morphological database. They also use datasets for lemmatization from Basque, English, Irish, and Tagalog. These datasets are standard for evaluating morphological tasks and are the same ones used by previous work, allowing for direct comparison.

Key Insights and Ideas

  • Hybridization is Powerful: Combining the structured inference of FSTs with the feature learning of LSTMs offers a powerful way to tackle sequence transduction. This hybrid approach leverages the best of both worlds.
  • Context is King (for Weights): The traditional FST approach limits context to the current state. By using LSTMs to provide rich, dynamic contextual features for arc weights, the model can capture much more nuanced dependencies.
  • Learned Features Reduce Hand-Engineering: The neural component significantly reduces the need for manual feature engineering, which is a major bottleneck in traditional FST-based systems.
  • Exact Inference is Still Possible: Despite the neural components, the framework still allows for exact inference using dynamic programming (like the forward algorithm for pathsum), which is a significant advantage over many end-to-end neural models that rely on approximate decoding.

Key Results

The proposed BiLSTM-WFST model consistently outperforms baseline WFSTs and standard neural sequence-to-sequence models on the evaluated morphological tasks. It is competitive with, and in some cases surpasses, a sophisticated latent-variable FST model specifically designed for morphological transduction. For example, on the morphological reinflection task, their model achieves state-of-the-art results on several sub-tasks, and when trained on twice the data, it further improves performance. The ablation studies also highlight the importance of the BiLSTM, the depth of the network, and the inclusion of local context for achieving these strong results.

Limitations and Future Work

The authors acknowledge that while their model is competitive, it doesn't uniformly outperform the best latent-variable FST model. They suggest future work could involve augmenting the FST itself with more explicit latent variables, increasing the history stored in FST states, or allowing for longer source/target substrings in FST arcs. They also note that the current arc weight function is just one possibility and that further investigation into different parametric functions, potentially involving learned embeddings of edit operations and their contexts, could yield further improvements. Additionally, they found that a simple parameter tying for copy edits led to some errors, suggesting that more nuanced handling of copy operations might be beneficial.

Summary updated

BibTeX
@inproceedings{rastogi2016weighting,
  author = {Pushpendre Rastogi and Ryan Cotterell and Jason Eisner},
  title = {{Weighting Finite-State Transductions With Neural Context}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2016},
  url = {https://openreview.net/forum?id=BJbjvXZ_ZH},
}
Figure