Sensitivity as a Complexity Measure for Sequence Classification Tasks

Sensitivity as a Complexity Measure for Sequence Classification Tasks Michael Hahn Stanford University, United States mhahn2@stanford.edu Dan Jurafsky Stanford University, United States jurafsky@stanford.edu Richard Futrell University of California, Irvine, United States rfutrell@uci.edu Abstract We introduce a theoretical framework for understanding and predicting the complexity of sequence classification tasks, using a novel extension of the theory of Boolean function sensitivity. The sensitivity of a function, given a distribution over input sequences, quan- tifies the number of disjoint subsets of the input sequence that can each be individually changed to change the output. We argue that standard sequence classification methods are biased towards learning low-sensitivity func- tions, so that tasks requiring high sensitivity are more difficult. To that end, we show ana- lytically that simple lexical classifiers can only express functions of bounded sensitivity, and we show empirically that low-sensitivity func- tions are easier to learn for LSTMs. We then estimate sensitivity on 15 NLP tasks, finding that sensitivity is higher on challenging tasks collected in GLUE than on simple text classi- fication tasks, and that sensitivity predicts the performance both of simple lexical classifiers and of vanilla BiLSTMs without pretrained contextualized embeddings. Within a task, sensitivity predicts which inputs are hard for such simple models. Our results suggest that the success of massively pretrained contextual representations stems in part because they pro- vide representations from which information can be extracted by low-sensitivity decoders. 1 Introduction What makes some tasks harder and others easier for modern machine learning methods?1 In NLP, simple models based on lexical classifiers provide good performance on some tasks, while strong performance on other tasks has been attained only recently with massive pretrained models. How- ever, there is no unified theoretical framework for understanding these difficulty differences between tasks, or what models might be more or less effective. 1Code: h t t p s : / / g i t h u b . c o m / m - h a h n /sensitivity. Existing complexity metrics provide limited practical insight. The Chomsky Hierarchy (Chomsky, 1956) is a prominent classification of formal lan- guages by complexity, but it describes asymptotic worst-case complexity and does not provide a measure of how hard it is to achieve high accuracy on realistic task distributions. Kolmogorov com- plexity (Li and Vitányi, 1993) is uncomputable and becomes well-defined only in the asymptotic limit. Psycholinguistic complexity metrics such as surprisal (Hale, 2001) and dependency length (Gibson, 1998) only capture formal features of the input, without regard to the task. We propose sensitivity as a theory of com- plexity for sequence classification tasks, that is, any task involving learning a function from sequences to labels. The sensitivity of a function, given a distribution over input sequences, quan- tifies the number of disjoint subsets of the input sequence that can each be individually changed in such a way as to change the output. Intuitively, high-sensitivity functions are complex because a single change in the input, in many differ- ent places, can completely change the output; …

Content truncated to 500 words