Sensitivity as a Complexity Measure for Sequence Classification Tasks

Michael Hahn, Dan Jurafsky, Richard Futrell

TL;DR

This paper introduces sensitivity—a concept borrowed from Boolean function theory—as a formal measure of complexity for natural language tasks. The authors demonstrate that tasks requiring high sensitivity (where many different parts of the input can independently flip the output label) are fundamentally harder for simple models to learn, explaining why massive pretraining is essential for complex reasoning but unnecessary for basic sentiment analysis.

What Problem Does This Paper Address?

In NLP, we intuitively know that some tasks are "harder" than others. Sentiment analysis can often be solved by a simple bag-of-words model, while Natural Language Inference (NLI) seems to require massive Transformers like RoBERTa. However, we lack a unified theoretical framework to quantify this difficulty.

Existing metrics fall short: the Chomsky Hierarchy describes asymptotic complexity but doesn't account for real-world data distributions; Kolmogorov complexity is uncomputable; and psycholinguistic metrics like surprisal focus on the input's form rather than the specific task being performed. This paper fills that gap by proposing sensitivity as a practical, computable measure of task complexity.

Methods

The authors generalize the "sensitivity" of Boolean functions to natural language sequences.

  1. Block Sensitivity: In this context, sensitivity measures how many disjoint subsets (blocks) of an input sequence can be changed to flip the model's prediction.
  2. Low Sensitivity: The output is predictable from redundant information (e.g., a movie review with many positive adjectives).
  3. High Sensitivity: Small changes in many different places can change the meaning (e.g., changing "all" to "some" or "not" in a logic-heavy sentence).
  4. Theoretical Bounds: The authors prove that simple lexical classifiers (like n-gram models or bag-of-embeddings) have a mathematical "ceiling" on the sensitivity they can express.
  5. Estimation: To calculate sensitivity on real data, they use a strong "oracle" model (RoBERTa) to provide labels and a masked language model (XLNet) to generate plausible word substitutions that stay within the natural language distribution.
  6. Human Validation: They conducted experiments where humans were asked to find as many disjoint word changes as possible that would flip a sentence's label, verifying that their automated metric aligns with human intuition.

Datasets

The study evaluates sensitivity across 15 diverse NLP tasks:

  • Standard Text Classification: MR (movie reviews), SUBJ (subjectivity), CR (customer reviews), and MPQA (opinion polarity).
  • GLUE Benchmark: MNLI, MRPC, QNLI, QQP, STS-B, RTE, CoLA, and SST-2.
  • Syntactic Tasks: POS tagging, dependency labeling, and head identification.
  • SyntaxGym: Targeted syntactic evaluations (anaphor licensing).

Key Insights and Ideas

  • Sensitivity as Nonlinearity: Sensitivity essentially measures the "wiggliness" or nonlinearity of a task's decision boundary. High-sensitivity tasks have complex boundaries where many different input features interact non-linearly.
  • The LSTM Bias: While LSTMs are theoretically capable of representing high-sensitivity functions (like the Parity function), the authors found they have a strong inductive bias toward learning low-sensitivity functions. This explains why vanilla LSTMs struggle with reasoning tasks even when they have enough parameters.
  • Why Pretraining Works: The results suggest that massive pretraining (like BERT/RoBERTa) works because it creates a representation space where complex, high-sensitivity information is "unpacked." This allows a simple, low-sensitivity linear head to extract the correct answer easily.
  • Redundancy vs. Reasoning: Text classification tasks (like sentiment) are low-sensitivity because they are highly redundant—you can change many words without flipping the label. Reasoning tasks (like RTE) are high-sensitivity because the logic is fragile; changing a single quantifier or entity often flips the entire meaning.

Key Results

  • Predictive Power: Sensitivity is a strong predictor of model performance. There is a high negative correlation ($R \approx -0.8$) between a task's sensitivity and how well simple models (Bag-of-Embeddings or vanilla BiLSTMs) perform on it.
  • Task Hierarchy: GLUE tasks, particularly those involving inference (RTE, MRPC, WSC), show significantly higher sensitivity than standard sentiment or subjectivity tasks.
  • Constituent Dispersion: In sentiment analysis, the authors found that "high sensitivity" inputs are typically those where different parts of the sentence have conflicting sentiments (e.g., a "mixed" review), creating a more complex decision for the model.

Limitations and Future Work

  • Oracle Dependence: The method relies on having a "strong" model (like RoBERTa) to act as a proxy for the true function. If the model has its own biases or "brittleness," the sensitivity estimate might reflect the model's flaws rather than the task's inherent difficulty.
  • Computational Cost: Estimating block sensitivity is computationally expensive, as it requires sampling many substitutions from a language model for every possible subset of the input.
  • Future Directions: The authors suggest applying this framework to other domains, such as computer vision, or using sensitivity to guide "curriculum learning," where a model starts with low-sensitivity examples and gradually moves to high-sensitivity ones.

Summary updated

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.
BibTeX
@article{hahn2021sensitivity,
  author = {Michael Hahn and Dan Jurafsky and Richard Futrell},
  title = {{Sensitivity as a Complexity Measure for Sequence Classification Tasks}},
  journal = {Trans. Assoc. Comput. Linguistics},
  year = {2021},
  url = {https://openreview.net/forum?id=B6mKMUfzoFx},
}

Loading related content...

Figure