Word Ordering Without Syntax

Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 2319–2324, Austin, Texas, November 1-5, 2016. c⃝2016 Association for Computational Linguistics Word Ordering Without Syntax Allen Schmaltz and Alexander M. Rush and Stuart M. Shieber Harvard University {schmaltz@fas,srush@seas,shieber@seas}.harvard.edu Abstract Recent work on word ordering has argued that syntactic structure is important, or even re- quired, for effectively recovering the order of a sentence. We find that, in fact, an n-gram language model with a simple heuristic gives strong results on this task. Furthermore, we show that a long short-term memory (LSTM) language model is even more effective at re- covering order, with our basic model outper- forming a state-of-the-art syntactic model by 11.5 BLEU points. Additional data and larger beams yield further gains, at the expense of training and search time. 1 Introduction We address the task of recovering the original word order of a shuffled sentence, referred to as bag gen- eration (Brown et al., 1990), shake-and-bake genera- tion (Brew, 1992), or more recently, linearization, as standardized in a recent line of research as a method useful for isolating the performance of text-to-text generation models (Zhang and Clark, 2011; Liu et al., 2015; Liu and Zhang, 2015; Zhang and Clark, 2015). The predominant argument of the more re- cent works is that jointly recovering explicit syn- tactic structure is crucial for determining the correct word order of the original sentence. As such, these methods either generate or rely on given parse struc- ture to reproduce the order. Independently, Elman (1990) explored lineariza- tion in his seminal work on recurrent neural net- works. Elman judged the capacity of early recurrent neural networks via, in part, the network’s ability to predict word order in simple sentences. He notes, The order of words in sentences reflects a num- ber of constraints...Syntactic structure, selective restrictions, subcategorization, and discourse con- siderations are among the many factors which join together to fix the order in which words oc- cur...[T]here is an abstract structure which un- derlies the surface strings and it is this structure which provides a more insightful basis for under- standing the constraints on word order.... It is, therefore, an interesting question to ask whether a network can learn any aspects of that underlying abstract structure (Elman, 1990). Recently, recurrent neural networks have reemerged as a powerful tool for learning the latent structure of language. In particular, work on long short-term memory (LSTM) networks for language modeling has provided improvements in perplexity. We revisit Elman’s question by applying LSTMs to the word-ordering task, without any explicit syn- tactic modeling. We find that language models are in general effective for linearization relative to ex- isting syntactic approaches, with LSTMs in particu- lar outperforming the state-of-the-art by 11.5 BLEU points, with further gains observed when training with additional text and decoding with larger beams. 2 Background: Linearization The task of linearization is to recover the original or- der of a shuffled sentence. We assume a vocabulary V and are given a sequence …

Content truncated to 500 words