Game-theoretic Vocabulary Selection via the Shapley Value and Banzhaf Index

Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2789–2798 June 6–11, 2021. ©2021 Association for Computational Linguistics 2789 Game-theoretic Vocabulary Selection via the Shapley Value and Banzhaf Index Roma Patel ∗ Brown University Marta Garnelo DeepMind Ian Gemp DeepMind Chris Dyer DeepMind Yoram Bachrach DeepMind Abstract The input vocabulary and their learned repre- sentations are crucial to the performance of neural NLP models. Using the full vocabulary results in less explainable and more memory intensive models, with the embedding layer of- ten constituting the majority of model parame- ters. It is thus common to use a smaller vocab- ulary to lower memory requirements and con- struct more interpertable models. We propose a vocabulary selection method that views words as members of a team trying to maximize the model’s performance. We apply power indices from cooperative game theory, including the Shapley value and Banzhaf in- dex, that measure the relative importance of individual team members in accomplishing a joint task. We approximately compute these indices to identify the most influential words. Our empirical evaluation examines multiple NLP tasks, including sentence and document classification, question answering and textual entailment. We compare to baselines that se- lect words based on frequency, TF-IDF and re- gression coefficients under L1 regularization, and show that this game-theoretic vocabulary selection outperforms all baselines on a range of different tasks and datasets. 1 Introduction Most state-of-the-art NLP methods use neural net- works that require a pre-defined vocabulary to vec- torise and encode text. In large text datasets, the vocabulary size can grow to hundreds of thousands of words, and having an embedding space over the entire vocabulary results in models that are expen- sive in memory and compute, and hard to interpret. Many of the words in the vocabulary are not crucial to task performance, and can be removed without a significant drop in final task performance. ∗Work done during an internship at DeepMind. Corresponding email: romapatel@brown.edu or yorambac@google.com. Figure 1: An example sentence from SST-2 (Socher et al., 2013), as well as the distribution of heuristic values based on vocabulary selection algorithms. Fre- quency and TF-IDF weight stopwords (right) higher whereas a game-theoretic Shapley-based approach tends to value task-specific words (left) more. It is common to use heuristics such as frequency or TF-IDF to reduce vocabulary size. After filtering to obtain a smaller vocabulary, “out-of-vocabulary” (OOV) words are replaced with an unknown word token <UNK>. This reduction in vocabulary size has many advantages. Models with reduced vo- cabulary are more easily interpretable and achieve increased transparency (Adadi and Berrada, 2018; Samek et al., 2019), require less memory, can be used in resource constrained settings, and are less prone to overfitting (Sennrich et al., 2015; Shi and Knight, 2017; L’Hostis et al., 2016; Chen et al., 2019). However, reducing the vocabulary size with a heuristic such as frequency is often not optimal. For example, Figure 1 shows the top ranked words according to frequency (blue), that …

Content truncated to 500 words