Sensitivity as a Complexity Measure for Sequence Classification Tasks (2021)

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, quantifies 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 functions, so that tasks requiring high sensitivity are more difficult. To that end, we show analytically that simple lexical classifiers can only express functions of bounded sensitivity, and we show empirically that low-sensitivity functions 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 classification 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 provide representations from which information can be extracted by low-sensitivity decoders.

## 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. however, there is no unified theoretical framework for understanding these difficulty differences between tasks, or what models might be more or less effective. existing complexity metrics provide limited practical insight. the chomsky hierarchy @xcite ) is a prominent classification of formal languages 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 complexity @xcite is uncomputable and becomes well-defined only in the asymptotic limit. psycholinguistic complexity metrics such as surprisal @xcite and dependency length @xcite only capture formal features of the input, without regard to the task. we propose sensitivity as a theory of complexity 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, quantifies 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 different places, can completely change the output; low-sensitivity functions are simpler because the output is predictable from redundant information in many subsets of the input. we will argue that sensitivity predicts what tasks are easy or hard for modern machine learning methods to learn. our notion of sensitivity is grounded in a wellstudied theory for boolean functions (o'donnell, 2014), which we generalize to natural language. unlike measures like kolmogorov complexity, sensitivity can be estimated on real datasets and single inputs without asymptotic approximations, only requiring a generalized language model such as xlnet @xcite and a strong model of the task. in this paper, we argue that sensitivity captures informal notions of complexity both at the level of architectures and on the level of tasks. first, we show that sensitivity quantifies architectural limitations and inductive biases of various machine learning architectures used in nlp, including both lexical classifiers and vanilla lstms without pretrained contextualized embeddings (section 3). second, in a survey of 15 major nlp tasks, we find that sensitivity quantitatively predicts how difficult a task is for simple lexical classifiers and neural models, both across tasks and across different inputs for a single task (section 4). the validity of our methods for quantifying sensitivity is verified using human experiments in section 5. section 6 discusses the relationship of sensitivity to previous theories of complexity and brittleness in neural networks, and implications for nlp practice. section 7 concludes. ## sensitivity bounds for nlp methods many statistical nlp methods proposed over the past decades involve linear combinations of features that look at individual words or groups of a few words. proposition 1 shows that such methods can only express functions of bounded block sensitivity, with an upper bound quadratic in the number k of inputs the model looks at simultaneously, independently of input length n. proposition 1. let f be any function σ * → r parameterized as follows: changing inputs in p i affects up to k|p i | of the summands in g. the ℓ 2 norm of the sum of these affected terms is bounded by ck|p i | n , and thus this result has direct bearing on a wide variety of methods used in nlp, such as averaging word embeddings to construct sentence embeddings @xcite @xcite , cnns @xcite with average pooling, and log-linear models with n-gram features. the parameter k equals 1 for models averaging word embeddings, the kernel width for cnns with average pooling, and n for models using n-gram features. c describes the norm of word embeddings, of the output of a cnn kernel, or of the weights of a linear model. lipschitz functions h include the sigmoid function σ used in logistic regression and its generalization softmax, which are 1-lipschitz, and feedforward networks with lipschitz activations. rnns and lstms @xcite can express functions of any sensitivity, such as f parity , because they can express all regular languages @xcite . on the other hand, transformers @xcite have asymptotically bounded sensitivity as the input length n increases @xcite . we show that even lstms have a learning bias towards low-sensitivity functions, despite their theoretical capacity to represent high-sensitivity functions. we consider functions f : {-1, 1} @xmath0, 1} n . we first evaluated average block sensitivity both for randomly initialized lstms and for the uniform distribution over boolean functions {-1, 1} 7 → {-1, 1}. we constructed boolean functions from a randomly initialized lstm by obtaining a scalar output and making this a binary output f based on a threshold chosen to maximize var(f ). we initialized the lstm's weights uniformly from [-d -0.5 , d -0.5 ] or from a gaussian with σ 2 = d -1 , where d is the number of hidden units. results are shown in figure 2 , for @xmath1. random boolean functions have block sensitivity tightly concentrated around ≈ 4.5, whereas the randomly initialized lstms consistently show lower block sensitivity. this suggests that low-sensitivity functions are 'overrepresented' in the lstm parameter space, echoing a theoretical result for feedforward networks @xcite . second, we directly examined learnability on functions of different sensitivities. as randomly chosen functions have tightly clustered sensitivity, we sampled foot_2 functions with a specific targeted average sensitivity as(f ) = 1 we did this for sequence lengths @xmath2, 10, 15. for each @xmath3, . . . , n, we constructed five such functions, and then trained an lstm (128 hidden units) for 10 5 iterations with adam (learning rate 0.003, batch size 32), and recorded average mean squared error after 10 2 , 10 3 , 10 4 , 10 5 training iterations. training batches and test examples are sampled uniformly from the 2 n elements of {-1, 1} n , without consideration of out-of-sample generalization. results are shown in figure 2 . for @xmath4, we arrange functions by bs(f ); for @xmath5, 15 we take as(f ) instead as it can be computed efficiently and is strongly correlated with bs(f ) at @xmath6.95). low-sensitivity functions are learned perfectly with fewer iterations, whereas high-sensitivity functions are not approximated much better than chance even after 10 5 training iterations. we note that this is a result on the ability to simply fit a function of 2 n inputs, not the (harder) task of generalizing to unseen input. ## sensitivity and difficulty of nlp tasks in section 3, we provided evidence that sensitivity describes how hard a function is to learn and represent for simple machine learning architectures that do not include pretrained contextual embeddings. in this section, we argue empirically that sensitivity is successful at capturing intuitive notions of task difficulty: low-sensitivity tasks are those on which simple classifiers as described in proposition 1, and vanilla lstms without pretraining, are relatively successful. more challenging tasks such as those collected in the glue suite @xcite ) have higher sensitivity. estimating block sensitivity (5) requires two ingredients: an estimate of the distributions of neighboring strings π(x|@xmath7, and an estimate of f on this set. we approximate π via a language model, and f via a trained model that is known to attain strong performance on the task. that is, we estimate the sensitivity of a task f by measuring the sensitivity of a model f that is known to provide close fit to f on the task's input distribution. in section 5, we report human annotation studies that justify this approximation. ## human validation in section 4, we estimated the sensitivity of nlp tasks by plugging a model f of the task f into equation 5. this methodology requires that the model f provides good labels on the samples from x ⊕p obtained using the language models. as the language models only approximate the input distribution, their samples could fall outside of the data distribution on which f approximates the true task f at high accuracy. if this were the case, high estimated sensitivity on tasks such as rte might reflect brittleness of large models rather than true high sensitivity. here, we show that this is not the case: reasoning tasks like rte have higher sensitivity than text classification tasks like sst-2, even when using human labels. ## discussion we have proposed sensitivity as a theoretical framework for studying the complexity of sequence classification tasks, arguing that it captures complexity both across several machine learning architectures (section 3) and across nlp tasks (section 4). prior work has studied the ability of rnns and transformers to represent and learn languages in different classes of the chomsky hierarchy (e.g., @xcite . sensitivity is orthogonal to the chomsky hierarchy: the maximally sensitive function f parity has a two-state finite automaton, but there are also low-sensitivity functions that are not even computable. sensitivity is also distinct from kolmogorov complexity and similar description length measures @xcite ): f parity has high sensitivity but very low description length. whereas kolmogorov complexity is uncomputable and can only be approximated asymptotically, sensitivity can be calculated for individual inputs, enabling us to explicitly evaluate it as a predictor of difficulty on nlp tasks. implications for nlp practice our results in section 4 suggest that pretrained contextualized embeddings have been so successful in nlp because they make it possible to learn highsensitivity functions with modest amounts of task-specific training data. we conjecture that, through large-scale pretraining, models implicitly learn high-sensitivity operations that are generally useful for language understanding. finetuning such models for classification tasks @xcite @xcite amounts to composing a high-sensitivity model with a low-sensitivity classifier. some classical techniques can also be interpreted in this light, such as aligning parse trees (a potentially high-sensitivity computation) and extracting features from these alignments that then are fed into an svm (a low-sensitivity classifier) as an approach to tasks like rte @xcite . decision boundaries in nlp the decision boundaries of nlp models are commonly studied to understand their linguistic knowledge (e.g., @xcite @xcite . @xcite and @xcite propose to improve nlp models and their evaluation by specifically considering input pairs that differ in some part and in their (true) label. @xcite propose to quantify the difficulty of an input by the largest eigenvalue of the fisher information matrix of a task model, finding that it predicts how sensitive classifiers are to word substitutions. sensitivity is different from widely studied pheh nomena of adversarial brittleness @xcite : the existence of adversarial examples typically means that natural examples have some neighbors, possibly outside of the input distribution, on which model output changes even though the true label does not. in contrast, high sensitivity means that there are many neighboring inputs within the data distribution on which the true label changes. sensitivity may be related to the observation that models often rely on spurious statistical patterns, such as simple lexical correlates of the label observed in reading comprehension datasets (e.g., @xcite ; we expect that such artifacts decrease task sensitivity as they make the gold labels correlated with the output of simple lexical classifiers. similarly, if the premise alone is predictive of the label in an entailment task @xcite , changing the hypothesis while staying within the task distribution is less likely to flip the label, again decreasing sensitivity. ## conclusion we proposed block sensitivity as a complexity measure for functions from sequences to labels, applying the measure to quantify the complexity of sequence classification tasks in nlp. block sensitivity generalizes well-understood complexity measures from the theory of boolean functions to the setting of natural language. we showed both theoretically and empirically that low sensitivity characterizes tasks on which simple models without massive pretraining provide reasonable performance, and that, in such tasks, more difficult inputs correspond to those with high sensitivity. our results show that pretrained contextual embeddings enable models to learn tasks with higher sensitivity, and suggest designing challenging tasks by maximizing sensitivity.