Elamur Research⌕
☰
home / papers / 2021 / Sensitivity as a Complexity Measure for Sequence Classification Tasks

Sensitivity as a Complexity Measure for Sequence Classification Tasks

Paper · 2021 · Michael Hahn, Dan Jurafsky and Richard Futrell

Summary

Why can bag-of-words models handle some NLP classification tasks, while others yielded only to large pretrained networks? Hahn, Jurafsky and Futrell answer this by adapting sensitivity, a concept from the analysis of Boolean functions, to natural-language inputs. Their block sensitivity counts how many non-overlapping parts of an input can each be rewritten, in ways that stay plausible under the statistics of the language, so that the label changes. To estimate it, they sample replacements with a generalized language model (XLNet) and score the altered inputs with a strong task model (RoBERTa). They prove that lexical and n-gram classifiers can only represent functions of bounded sensitivity. Experiments show that LSTMs learn low-sensitivity functions more easily. They also measure sensitivity on 15 NLP tasks and check the estimates against human judgments. GLUE tasks turn out to be more sensitive than plain text classification, and sensitivity predicts how well simple models perform, both per task and per input. The measure is computable, unlike Chomsky-hierarchy or Kolmogorov views of difficulty, and it helps explain why pretrained representations work so well.

Key points

  • Theory (Proposition 1): a classifier combining features over at most k words at a time has block sensitivity bounded by a term quadratic in k, independent of input length n.
  • Estimation pipeline: XLNet (and u-PMLM) propose context-aware substitutions, and RoBERTa provides task predictions. In SST-2 (Stanford Sentiment Treebank) examples, the same one-word slot yields sensitivity of about 0.0 in a strongly positive context and 0.58 when both polarities fit.
  • Across 15 tasks, sensitivity is higher for GLUE than for simple text classification. It forecasts how accurate word-level classifiers are, as well as how accurate plain BiLSTMs are when they lack pretrained contextual embeddings, and it also identifies hard inputs within a task.
  • Sensitivity is distinct from both the Chomsky hierarchy and Kolmogorov complexity. Parity is maximally sensitive, yet it needs only a two-state automaton and has a very short description.
  • Practical takeaway: fine-tuning combines a high-sensitivity pretrained encoder with a low-sensitivity classifier, and harder benchmarks could be designed by maximizing sensitivity. Code is available at github.com/m-hahn/sensitivity (TACL vol. 9, pp. 891–908).

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Stanford UniversityStanford · United States434 works · 314,419 citations🎓University of California, IrvineIrvine · United States37 works · 36,319 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

Cite

Cite as Michael Hahn, Dan Jurafsky and Richard Futrell. 2021. Sensitivity as a Complexity Measure for Sequence Classification Tasks. Transactions of the Association for Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1162/tacl_a_00403

@article{hahn2021sensitivity,
  title = {{Sensitivity as a Complexity Measure for Sequence Classification Tasks}},
  author = {Michael Hahn, Dan Jurafsky and Richard Futrell},
  journal = {Transactions of the Association for Computational Linguistics},
  year = {2021},
  doi = {10.1162/tacl\_a\_00403},
  url = {https://doi.org/10.1162/tacl_a_00403}
}

References

63 references, 30 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Sanjeev Arora, Yingyu Liang, and Tengyu Ma. 2017. A simple but tough-to-beat baseline for sentence embeddings. In ICLR 2017: International Conference on Learning Representations 2017. find
  2. William B. Dolan and Chris Brockett. 2005. Automatically constructing a corpus of sentential paraphrases. In Proceedings of the Third International Workshop on Paraphrasing, IWP@IJCNLP 2005, Jeju Island, Korea, October 2005, 2005. Asian Federation of Natural Language Processing.
  3. A. Bernasconi. 1996. Sensitivity vs. block sensitivity (an average-case study). find
  4. Information Kawin Ethayarajh. 2018. Unsupervised random walk sentence embeddings: A strong but simple baseline. In Proceedings of The Third Workshop on Representation Learning for NLP, pages 91–100. https://doi.org/10 .18653/v1/W18-3012 find
  5. Suchin Gururangan, Swabha Swayamdipta, Omer Levy, Roy Schwartz, Samuel Bowman, and Noah A. Smith. 2018. Annotation artifacts in natural language inference data. In NAACL HLT 2018: 16th Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Te…
  6. Leonardo Franco. 2006. Generalization ability of boolean functions implemented in feedforward neural networks. Neurocomputing, 70(1): 351–361. https://doi.org/10.1016/j.neucom.2006.01.025 ↗
  7. Michael Hahn. 2020. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156–171. https://doi.org/10.1162/tacl a 00306 ↗
  8. Richard Futrell, Ethan Wilcox, Takashi Morita, Peng Qian, Miguel Ballesteros, and Roger Levy. 2019. Neural language models as psycholinguistic subjects: Representations of syntactic state. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Lingui…
  9. John T. Hale. 2001. A probabilistic Earley parser as a psycholinguistic model. In Proceedings of the Second Meeting of the North American Chapter of the Association for Computational Linguistics and Language Technologies, pages 1–8. https://doi.org/10.3115/1073336.1073357 ↗
  10. Pooya Hatami, Raghav Kulkarni, and Denis Pankratov. 2010. Variations on the sensitivity conjecture. Theory of Computing, 4:1–27. find
  11. Matt Gardner, Yoav Artzi, Victoria Basmova, Jonathan Berant, Ben Bogin, Sihao Chen, Pradeep Dasigi, Dheeru Dua, Yanai Elazar, Ananth Gottumukkala, Nitish Gupta, Hanna Hajishirzi, Gabriel Ilharco, Daniel Khashabi, Kevin Lin, Jiangming Liu, Nelson F. Liu, Phoebe Mulcaire, Qiang Ning, Sameer Singh, Noa… find
  12. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural Computation, 9(8):1735–1780. find
  13. Bill G. Horne and Don R. Hush. 1994. Bounds on the complexity of recurrent neural network implementations of finite state machines. In Advances in Neural Information Processing Systems, pages 359–366. find
  14. Jeremy Howard and Sebastian Ruder. 2018. Universal language model fine-tuning for text classification. In ACL 2018: 56th Annual Meeting of the Association for Computational Linguistics, volume 1, pages 328–339. https://doi.org/10.18653/v1/P18 -1031 ↗
  15. Jon Gauthier, Jennifer Hu, Ethan Wilcox, Peng Qian, and Roger Levy. 2020. SyntaxGym: An online platform for targeted evaluation of language models. In Proceedings of the Association for Computational Linguistics: System Demonstrations (ACL 2020).
  16. Jennifer Hu, Sherry Y. Chen, and Roger P. Levy. 2020. A closer look at the performance of neural language models on reflexive anaphor licensing. Proceedings of the Society for Computation in Linguistics, 3(1):382–392.
  17. Edward Gibson. 1998. Linguistic complexity: Locality of syntactic dependencies. Cognition, 68(1):1–76. https://doi.org/10.1016 /S0010-0277(98)00034-1 find
  18. Minqing Hu and Bing Liu. 2004. Mining and summarizing customer reviews. In Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 168–177. find
  19. Hector J. Levesque, Ernest Davis, and Leora Morgenstern. 2012. The winograd schema challenge. In KR’12 Proceedings of the Thirteenth International Conference on Principles of Knowledge Representation and Reasoning, pages 552–561. find
  20. Paloma Jeretic, Alex Warstadt, Suvrat Bhooshan, and Adina Williams. 2020. Are natural language inference models IMPPRESsive? Learning IM-Plicature and PRESupposition. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020, Online, July 5-10, 2020, pages… — [doi:10.18653/v1/2020](https://doi.org/10.18653/v1/2020) find
  21. Ming Li and Paul Vitányi. 1993. An Introduction to Kolmogorov Complexity and its Applications, Springer. find
  22. Yi Liao, Xin Jiang, and Qun Liu. 2020. Probabilistically masked language model capable of autoregressive generation in arbitrary word order. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 263–274. https://doi.org/10.18653/v1/2020 .acl-main.24 ↗
  23. Robin Jia and Percy Liang. 2017. Adversarial examples for evaluating reading comprehension systems. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 2021–2031. https://doi.org/10.18653/v1/D17 -1215 ↗
  24. Tal Linzen, Emmanuel Dupoux, and Yoav Goldberg. 2016. Assessing the ability of LSTMs to learn syntax-sensitive dependencies. Transactions of the Association for Computational Linguistics, 4:521–535. https://doi.org/10.1162/tacl a 00115 ↗
  25. Jeff Kahn, Gil Kalai, and Nathan Linial. 1988. The influence of variables on Boolean functions. In [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science, pages 68–80. https://doi.org/10.1109/SFCS.1988.21923 — [doi:10.1109/sfcs.1988.21923](https://doi.org/10.1109/sfcs.1988.21923) ↗
  26. Rebecca Marvin and Tal Linzen. 2018. Targeted syntactic evaluation of language models. arXiv preprint arXiv:1808.09031. https://doi.org/10.18653/v1/D18-1151 ↗
  27. Divyansh Kaushik, Eduard Hovy, and Zachary Lipton. 2020. Learning the difference that makes a difference with counterfactually-augmented data. In ICLR 2020: Eighth International Conference on Learning Representations. find
  28. William Merrill. 2019. Sequential neural networks as automata. arXiv preprint arXiv:1906.01615. https://doi.org/10.18653/v1/W19 -3901 ↗
  29. Marvin Minsky and Seymour A. Papert. 1969. Perceptrons: An Introduction to Computational Geometry. The MIT Press. find
  30. Divyansh Kaushik and Zachary C. Lipton. 2018. How much reading does reading comprehension require? A critical investigation of popular benchmarks. In EMNLP 2018: 2018 Conference on Empirical Methods in Natural Language Processing, pages 5010–5015. https://doi.org/10.18653/v1/D18 -1546 ↗
  31. Nikita Nangia and Samuel R. Bowman. 2019. Human vs. muppet: A conservative estimate of human performance on the glue benchmark. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 4566–4575. https://doi.org/10.18653/v1/P19 -1449 ↗
  32. Yoon Kim. 2014. Convolutional neural networks for sentence classification. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1746–1751. https://doi.org/10.3115/v1/D14 -1181 ↗
  33. Noam Nisan. 1991. CREW PRAMs and decision trees. SIAM Journal on Computing, 20(6): 999–1007. https://doi.org/10.1137/0220062 ↗
  34. Joakim Nivre, Marie-Catherine de Marneffe, Filip Ginter, Yoav Goldberg, Jan Hajic, Christopher D. Manning, Ryan T. McDonald, Slav Petrov, Sampo Pyysalo, Natalia Silveira, Reut Tsarfaty, and Daniel Zeman. 2016. Universal dependencies v1: A multilingual treebank collection. In Tenth International Conf…
  35. Jeffrey Pennington, Richard Socher, and Christopher Manning. 2014. GloVe: Global vectors for word representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1532–1543. https://doi.org/10.3115/v1/D14 -1162 ↗
  36. Roman Novak, Yasaman Bahri, Daniel A. Abolafia, Jeffrey Pennington, and Jascha Sohl-Dickstein. 2018. Sensitivity and generalization in neural networks: an empirical study. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conferenc… find
  37. Matthew E. Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. 2018. Deep contextualized word representations. In NAACL HLT 2018: 16th Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Te…
  38. Ryan O’Donnell. 2014. Analysis of Boolean Functions. Cambridge University Press. find
  39. Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. 2019. fairseq: A fast, extensible toolkit for sequence modeling. In NAACL-HLT 2019: Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 48–…
  40. Slav Petrov, Dipanjan Das, and Ryan McDonald. 2012. A universal part-of-speech tagset. In Proceedings of the Eighth International Conference on Language Resources and Evaluation (LREC-2012), pages 2089–2096.
  41. Adam Poliak, Jason Naradowsky, Aparajita Haldar, Rachel Rudinger, and Benjamin Van Durme. 2018. Hypothesis only baselines in natural language inference. In Proceedings of the Seventh Joint Conference on Lexical and Computational Semantics, pages 180–191. https://doi.org/10.18653/v1/S18 -2023 ↗
  42. Giacomo De Palma, Bobak Toussi Kiani, and Seth Lloyd. 2019. Random deep neural networks are biased towards simple functions. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Can… find
  43. Peng Qi, Timothy Dozat, Yuhao Zhang, and Christopher D. Manning. 2018. Universal dependency parsing from scratch. In Proceedings of the CoNLL 2018 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies, pages 160–170.
  44. Bo Pang and Lillian Lee. 2004. A sentimental education: Sentiment analysis using subjectivity summarization based on minimum cuts. In Proceedings of the 42nd Meeting of the Association for Computational Linguistics (ACL’04), Main Volume, pages 271–278. https://doi.org/10.3115/1218955 .1218990 ↗
  45. Peng Qi, Yuhao Zhang, Yuhui Zhang, Jason Bolton, and Christopher D. Manning. 2020. Stanza: A Python natural language processing toolkit for many human languages. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: System Demonstrations, ACL 2020, Online, July…
  46. Bo Pang and Lillian Lee. 2005. Seeing stars: Exploiting class relationships for sentiment categorization with respect to rating scales. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05), pages 115–124.
  47. Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019. Language models are unsupervised multitask learners. OpenAI Blog, 1(8):9. find
  48. Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances in Neural Information Processing Systems, pages 5998–6008.
  49. Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville. 2019. On the spectral bias of neural networks. In ICML 2019: Thirty-sixth International Conference on Machine Learning, pages 5301–5310. find
  50. Alex Wang, Yada Pruksachatkun, Nikita Nangia, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. 2019a. SuperGLUE: A stickier benchmark for general-purpose language understanding systems. In Advances in Neural Information Processing Systems, pages 3266–3280.
  51. Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. 2016. Squad: 100,000+ questions for machine comprehension of text. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 2383–2392. https://doi.org/10.18653/v1/D16 -1264 ↗
  52. Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. 2019b. GLUE: A multi-task benchmark and analysis platform for natural language understanding. In ICLR 2019: 7th International Conference on Learning Representations. https://doi.org/10.1162/tacl a 00290 ↗
  53. Natalia Silveira, Timothy Dozat, Marie-Catherine de Marneffe, Samuel Bowman, Miriam Connor, John Bauer, and Chris Manning. 2014. A gold standard dependency corpus for English. In Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC’14), pages 2897–2904. find
  54. Alex Warstadt, Amanpreet Singh, and Samuel R. Bowman. 2019. Neural network acceptability judgments. Transactions of the Association for Computational Linguistics, 7:625–641. find
  55. Janyce Wiebe, Theresa Wilson, and Claire Cardie. 2005. Annotating expressions of opinions and emotions in language. Language Resources and Evaluation, 39(2):165–210. find
  56. Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Ng, and Christopher Potts. 2013. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1631–…
  57. John Wieting, Mohit Bansal, Kevin Gimpel, and Karen Livescu. 2016. Towards universal paraphrastic sentence embeddings. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings.
  58. Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. 2014. Intriguing properties of neural networks. In 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceeding…
  59. Adina Williams, Nikita Nangia, and Samuel Bowman. 2018. A broad-coverage challenge corpus for sentence understanding through inference. In NAACL HLT 2018: 16th Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, volume 1, pag…
  60. Guillermo Valle-Perez, Chico Q. Camargo, and Ard Louis. 2019. Deep learning generalizes because the parameter-function map is biased towards simple functions. In ICLR 2019: 7th International Conference on Learning Representations. find
  61. Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, and Jamie Brew. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, 2019. Huggingface’s transformers: State-ofthe-ar…
  62. Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Ruslan Salakhutdinov, and Quoc V. Le. 2019. XLNet: Generalized autoregressive pretraining for language understanding. In NeurIPS 2019: Thirty-third Conference on Neural Information Processing Systems, pages 5753–5763.
  63. Zhi-Qin John Xu, Yaoyu Zhang, and Yanyang Xiao. 2019. Training behavior of deep neural network in frequency domain. In International Conference on Neural Information Processing, pages 264–274. Springer. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/hahn-2021-sensitivity-as-complexity-measure-sequence/