Pretraining with Contrastive Sentence Objectives Improves Discourse Performance of Language Models

Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 443–459 July 5 - 10, 2020. c⃝2020 Association for Computational Linguistics 443 A Formal Hierarchy of RNN Architectures William Merrill∗ Gail Weiss† Yoav Goldberg∗ ‡ Roy Schwartz∗ § Noah A. Smith∗ § Eran Yahav† ∗Allen Institute for AI † Technion ‡ Bar Ilan University § University of Washington {willm,yoavg,roys,noah}@allenai.org {sgailw,yahave}@cs.technion.ac.il Abstract We develop a formal hierarchy of the expres- sive capacity of RNN architectures. The hi- erarchy is based on two formal properties: space complexity, which measures the RNN’s memory, and rational recurrence, defined as whether the recurrent update can be described by a weighted finite-state machine. We place several RNN variants within this hierarchy. For example, we prove the LSTM is not ratio- nal, which formally separates it from the re- lated QRNN (Bradbury et al., 2016). We also show how these models’ expressive capacity is expanded by stacking multiple layers or com- posing them with different pooling functions. Our results build on the theory of “saturated” RNNs (Merrill, 2019). While formally extend- ing these findings to unsaturated RNNs is left to future work, we hypothesize that the prac- tical learnable capacity of unsaturated RNNs obeys a similar hierarchy. Experimental find- ings from training unsaturated networks on for- mal languages support this conjecture. 1 Introduction While neural networks are central to the perfor- mance of today’s strongest NLP systems, theoret- ical understanding of the formal properties of dif- ferent kinds of networks is still limited. It is estab- lished, for example, that the Elman (1990) RNN is Turing-complete, given infinite precision and computation time (Siegelmann and Sontag, 1992, 1994; Chen et al., 2018). But tightening these un- realistic assumptions has serious implications for expressive power (Weiss et al., 2018), leaving a sig- nificant gap between classical theory and practice, which theorems in this paper attempt to address. Recently, Peng et al. (2018) introduced rational RNNs, a subclass of RNNs whose internal state can be computed by independent weighted finite automata (WFAs). Intuitively, such models have a computationally simpler recurrent update than Figure 1: Hierarchy of state expressiveness for satu- rated RNNs and related models. The y axis represents increasing space complexity. ∅ means provably empty. Models are in bold with qualitative descriptions in gray. conventional models like long short-term memory networks (LSTMs; Hochreiter and Schmidhuber, 1997). Empirically, rational RNNs like the quasi- recurrent neural network (QRNN; Bradbury et al., 2016) and unigram rational RNN (Dodge et al., 2019) perform comparably to the LSTM, with a smaller computational budget. Still, the underlying simplicity of rational models raises the question of whether their expressive power is fundamentally limited compared to other RNNs. In a separate line of work, Merrill (2019) intro- duced the saturated RNN1 as a formal model for analyzing the capacity of RNNs. A saturated RNN is a simplified network where all activation func- tions have been replaced by step functions. The saturated network may be seen intuitively as a “sta- ble” version of its original …

Content truncated to 500 words