Local String Transduction as Sequence Labeling

Proceedings of the 27th International Conference on Computational Linguistics, pages 1360–1371 Santa Fe, New Mexico, USA, August 20-26, 2018. 1360 Local String Transduction as Sequence Labeling Joana Ribeiro† Shashi Narayan† Shay B. Cohen† Xavier Carreras‡ † School of Informatics, University of Edinburgh, 10 Crichton Street, Edinburgh EH8 9AB, UK ‡ dMetrics, Brooklyn, NY 11211, USA s1536851@sms.ed.ac.uk shashi.narayan@ed.ac.uk scohen@inf.ed.ac.uk xavier.carreras@dmetrics.com Abstract We show that the general problem of string transduction can be reduced to the problem of sequence labeling. While character deletions and insertions are allowed in string transduction, they do not exist in sequence labeling. We show how to overcome this difference. Our approach can be used with any sequence labeling algorithm and it works best for problems in which string transduction imposes a strong notion of locality (no long range dependencies). We experiment with spelling correction for social media, OCR correction, and morphological inflection, and we see that it behaves better than seq2seq models and yields state-of-the-art results in several cases. 1 Introduction String transduction (mapping one string to another) is an essential ingredient in the natural language processing (NLP) toolkit that helps solve problems ranging from morphological inflection (Dreyer et al., 2008) and lemmatization to spelling correction (Cotterell et al., 2014), text normalization (Porta and Sancho, 2013) and machine translation (Kumar et al., 2006). Finite-state technology is often used with string transduction (Allauzen et al., 2007), especially when there is a strong notion of locality in the transduction problem, i.e., when there are no long range dependencies between the predicted characters. More recently, neural network methods have become more common for such problems using the seq2seq models that were introduced for machine translation (Bahdanau et al., 2015). Similarly, sequence labeling algorithms have been the mainstay for an array of problems in NLP, including part-of-speech tagging, named entity recognition and semantic role labeling. Various models have been proposed to do sequence labeling, including conditional random fields, hidden Markov models and neural networks. String transduction and sequence labeling are often treated as two separate entities, and indeed, usually give treatment to different problems in NLP. We claim and show that there is a great similarity between them, and that one can be reduced to the other. Sequence labeling is often associated with a set of problems in which the set of labels is small compared to the vocabulary. Still, this labeling essentially associates each symbol (usually a word) in a sequence (usually a sentence) with a label. As such, it can be seen as a specific case of string transduction that imposes a one-to-one correspondence between input and output symbols. This is the easier side of the reduction between sequence labeling and string transduction, and it has been exploited in the deep learning literature with seq2seq models. In this paper, we come to address the reduction in the reverse direction – i.e. we show how to frame string transduction as sequence labeling. We do this by decomposing the transduction process into two parts: first, we induce an alignment between the …

Content truncated to 500 words