Fast and Accurate Reordering with ITG Transition RNN

Proceedings of the 27th International Conference on Computational Linguistics, pages 1454–1463 Santa Fe, New Mexico, USA, August 20-26, 2018. 1454 Fast and Accurate Reordering with ITG Transition RNN Hao Zhang Google haozhang@google.com Axel Ng Google Richard Sproat Google Abstract Attention-based sequence-to-sequence neural network models learn to jointly align and translate. The quadratic-time attention mechanism is powerful as it is capable of handling arbitrary long- distance reordering, but computationally expensive. In this paper, with the goal of making neural translation both accurate and efficient, we follow the traditional pre-reordering approach to de- couple reordering from translation. We add a reordering RNN that shares the input encoder with the decoder. The RNNs are trained jointly with a multi-task loss function and applied sequen- tially at inference time. The task of the reordering model is to predict the permutation of the input words following the target language word order. After reordering, the attention in the decoder becomes more peaked and monotonic. For reordering, we adopt Inversion Transduction Gram- mars (ITG) and propose a transition system to parse input to trees for reordering. We harness the ITG transition system with RNN. With the modeling power of RNNs, we achieve superior reordering accuracy without any feature engineering. In experiments, we apply the model to the task of text normalization. Compared to a strong baseline of attention-based RNN, our ITG RNN reordering model can reach the same reordering accuracy with only 1/10 of the training data and is 2.5x faster in decoding. 1 Introduction The encoder-decoder neural network architecture for sequence-to-sequence problems has achieved enor- mous success especially after the introduction of the attention mechanism (Bahdanau et al., 2014). Its applications in NLP range from machine translation (Bahdanau et al., 2014) and sentence summariza- tion (Rush et al., 2015) to text normalization (Sproat and Jaitly, 2017). The attention mechanism is effectively a random memory access mechanism, enabling access to any source sequence position at any decoding step. In principle, it can handle arbitrary reordering of any input length. But its power comes with a high computational cost. The time complexity of the attention mechanism is O(N2) if the num- ber of decoding steps is proportional to the input length N. In addition to the computational concern, for dominantly-monotonic translation tasks, such as text normalization (Sproat and Jaitly, 2017), soft attention can be too relaxed and sub-optimal in terms of modeling efficiency. Hence, to reduce compu- tational complexity as well as to improve model accuracy, recently there has been a surge of research interest in enforcing monotonic attention (Raffel et al., 2017) and hard attention (Aharoni and Goldberg, 2017) based on the observation that many sequence-to-sequence tasks are monotonic, including speech recognition and morphological inflection. In reality, the monotonicity assumption has to be made carefully. Even in the highly monotonic trans- lation task of text normalization, which is mapping written text to spoken text, there are systematic reordering patterns like from “2018-10-03” to “October third, two thousand eighteen”, and from “$100” to “one hundred dollars”. These reordering …

Content truncated to 500 words