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

Abstract: The input vocabulary and the representations learned 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 often constituting the majority of model parameters. It is thus common to use a smaller vocabulary to lower memory requirements and construct 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 index, 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 select words based on frequency, TF-IDF and regression coefficients under L1 regularization, and show that this game-theoretic vocabulary selection outperforms all baseline on a range of different tasks and datasets.

## introduction most state-of-the-art nlp methods use neural networks that require a pre-defined vocabulary to vectorise 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 expensive 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. figure 1 : an example sentence from sst-2 @xcite , as well as the distribution of heuristic values based on vocabulary selection algorithms. frequency 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 @xmath0. this reduction in vocabulary size has many advantages. models with reduced vocabulary are more easily interpretable and achieve increased transparency @xcite , require less memory, can be used in resource constrained settings, and are less prone to overfitting @xcite @xcite . 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 are largely unimportant for the sentiment task at hand. we consider the vocabulary selection problem: given a target vocabulary size k (or equivalently, a target memory footprint or a "budget" of model parameters for the embedding layer), what is the optimal word subset we should use as our vocabulary? our solution's output, based on the shapley value, is also shown in figure 1 , demonstrating that it focuses on words relevant to the task. ## method we assume a dataset d and a training method m for training on d and producing a model f θ where θ are tuned model parameters. the model is evaluated on a validation set t to estimate how well the model generalizes to the true data distribution. an evaluation metric (for example the model accuracy or f 1 score, as evaluated on the validation set) for each model f θ is denoted by q(f θ ), thus allowing an assessment of the performance of a subset of words. we first briefly discuss preliminaries from cooperative game theory @xcite . ## empirical results we analyze the performance of our method and the baselines across a range of target vocabulary sizes, 6 in logistic regression with l1 regularization, the regression coefficients and derived word ranking depend on the degree of regularization and the initialization. methods like glmpath @xcite obtain the entire l1 path of the glm at the cost of fitting a single model. in the spirit of stability selection @xcite , to alleviate stochasticity we average 20 training runs of the l1regularized model, averaging coefficients to obtain the ranking over words (still cheaper computationally than our approach). investigating which method achieves a better tradeoff between vocabulary size and model quality. ## discussion the results in section 4 show that a game theoretic approach to vocabulary selection can achieve better tradeoffs between the vocabulary size and model performance than heuristics such as tf and tf-idf based selection, or a method based on regression coefficients in an l 1 regularized logistic regression. this advantage comes at the cost of having a significantly higher computational cost of selecting the vocabulary. following the expensive selection step, we now have the benefit of a smaller model which is more interpretable and explainable, has a reduced memory consumption and potentially less prone to overfitting. we have proposed several ways to mitigate the compute load of selecting the vocabulary: applying a heuristic pre-filtering step and using logisitic regression models rather than the full model while estimating power indices. ## related work we proposed a vocabulary selection method for nlp tasks, using cooperative game theory. we discuss related work on model compression, tailoring the vocabulary in nlp tasks and using subword embeddings, and approximating game theoretic solutions and using them for explainable ai. ## conclusion we proposed a vocabulary selection method based on cooperative game theory and empirically showed improvements over baselines in multiple nlp tasks. our approach, with its task-specific vocabulary, offers an improved model size and quality tradeoffs. several questions remain open for future research on better vocabulary selection. could alternative power indices, apart from what we have shown using the shapley and banzhaf indeces, achieve better performance? is there a way to better combine our methods with subword embeddings? moreover, given that our method is computationally demanding during vocabulary construction time, an interesting problem is to explore ways to speed up this process; both theoretically, through a different power index calculation, and practically, through better parallelization.