IP Library › Granted Patent US 12,573,371
Granted Patent B2
US 12,573,371 · App. 18/038,631 · Granted Mar 10, 2026

Vocabulary selection for text processing tasks using power indices

Inventors: Ian Michael Gemp (London, GB); Yoram Bachrach (London, GB); Roma Patel (Providence, RI); Christopher James Dyer (London, GB)
Assignee: GDM HOLDING LLC
G10L13/047G10L13/08
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,573,371
App. No.
18/038,631
Granted
Mar 10, 2026
Kind
B2
Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for selecting an input vocabulary for a machine learning model using power indices. One of the methods includes computing a respective score for each of a plurality of text tokens in an initial vocabulary and then selecting the text tokens in the input vocabulary based on the respective scores.

Claims (68)

1 . A method performed by one or more computers, the method comprising:

obtaining a training data set comprising a plurality of text segments in one or more natural languages, each text segment comprising one or more text tokens that are each selected from an initial vocabulary of text tokens in the one or more natural languages;

selecting an input vocabulary for a first machine learning model to be trained on the training data set to perform one or more text processing tasks, wherein the input vocabulary is a proper subset of the text tokens in the initial vocabulary, and wherein the text tokens in the input vocabulary are represented as unique tokens in inputs to the first machine learning model, the selecting comprising:

for each particular text token of a plurality of text tokens in the initial vocabulary:

generating a plurality of first candidate input vocabularies that do not include the particular text token;

for each of the plurality of first candidate input vocabularies, generating a corresponding second input vocabulary that includes (i) the text tokens in the first candidate input vocabulary and (ii) the particular text token;

for each of the plurality of first candidate input vocabularies, training a second machine learning model to perform the one or more text processing tasks on at least a portion of the training data set with an input vocabulary for the second machine learning model set to the first candidate input vocabulary;

for each of the plurality of second candidate input vocabularies, training the second machine learning model to perform the one or more text processing tasks on at least a portion of the training data set with the input vocabulary for the second machine learning model set to the second candidate input vocabulary; and

determining a score for the particular text token that measures a difference between (i) the performance on the one or more text processing tasks of the second machine learning model when trained with the plurality of first candidate input vocabularies that do not include the particular text token and (ii) the performance on the one or more text processing tasks of the second machine learning model when trained with the plurality of second candidate input vocabularies that do include the particular text token;

selecting the input vocabulary based on the scores for the particular text tokens; and

training the first machine learning model to perform the one or more text processing tasks on at least a portion of the training data set with the input vocabulary for the first machine learning model set to the selected input vocabulary.

2 . The method of claim 1 , wherein the text tokens in the initial vocabulary of text tokens comprise words.

3 . The method of claim 1 , wherein the text tokens in the initial vocabulary of text tokens comprise subwords.

4 . The method of claim 1 , wherein the text tokens in the initial vocabulary that are not in the input vocabulary are all represented as a single, shared token in inputs to the first machine learning model.

5 . The method of claim 4 , wherein the first machine learning model is configured to receive a model input comprising an input text segment and to process the model input to generate an output for the one or more text processing tasks, and wherein:

any text tokens in the input text segment that are in the input vocabulary are represented as unique tokens in the model input; and

any text tokens in the input text segment that are not in the input vocabulary are represented as the single, shared token in the model input.

6 . The method of claim 1 , further comprising:

providing data specifying the trained first machine learning model and the selected input vocabulary for use in generating outputs for the one or more text processing tasks for new text segments that are not in the training data set.

7 . The method of claim 1 , further comprising:

selecting the plurality of text tokens from the initial vocabulary by filtering out one or more tokens from the text tokens in the initial vocabulary.

8 . The method of claim 7 , wherein filtering out one or more text tokens comprises:

ranking the text tokens in the initial vocabulary based on one or more heuristics; and

selecting a threshold number of text tokens based on the ranking.

9 . The method of claim 8 , wherein the one or more heuristics include one or more of TF, TF-IDF, or coefficients assigned to the text tokens in the initial vocabulary in a linear regression model trained with regularization.

10 . The method of claim 1 , wherein generating a plurality of first candidate input vocabularies that do not include the particular text token comprises generating each first candidate input vocabulary by:

assigning a probability p to each of the plurality of text tokens in the initial vocabulary; and

selecting tokens for inclusion in the first candidate input vocabulary based on the probability p.

11 . The method of claim 10 , wherein the probability p assigned to each of the plurality of tokens is 0.5.

12 . The method of claim 11 , wherein generating a plurality of first candidate input vocabularies that do not include the particular text token comprises generating each first candidate input vocabulary by:

generating a random ordering of the plurality of text tokens in the initial vocabulary; and

selecting the plurality of text tokens that precede the particular text token in the random ordering for inclusion in the first candidate input vocabulary.

13 . The method of claim 12 , wherein generating a random ordering comprises applying a random permutation to an initial ordering of the plurality of text tokens.

14 . The method of claim 1 , wherein determining a score for the particular text token comprises:

for each of the plurality of first candidate input vocabularies:

determining a first performance measure that measures a performance on the one or more text processing tasks of the second machine learning model when trained with the first candidate input vocabulary;

determining a second performance measure that measures performance on the one or more text processing tasks of the second machine learning model when trained with the corresponding second candidate input vocabulary; and

determining a difference between the first performance measure and the second performance measure.

15 . The method of claim 14 , wherein determining a score for the particular text token further comprises:

computing an average of the differences for the plurality of first candidate input vocabularies.

16 . The method of claim 1 , wherein selecting the input vocabulary based on the scores for the particular text tokens comprises:

selecting, as the text tokens in the input vocabulary, a threshold number of text tokens having the highest scores.

17 . The method of claim 1 , wherein the first machine learning model is the same as the second machine learning model.

18 . The method of claim 1 , wherein the second machine learning model is a different machine learning model from the first machine learning model that is less computationally expensive than the first machine learning model.

19 . The method of claim 1 , wherein the one or more text processing tasks include a text-to-speech task and wherein the first machine learning model is configured to receive text in a natural language and generate as output audio data defining audio of the text being spoken in the natural language.

20 . A system comprising one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:

obtaining a training data set comprising a plurality of text segments in one or more natural languages, each text segment comprising one or more text tokens that are each selected from an initial vocabulary of text tokens in the one or more natural languages;

selecting an input vocabulary for a first machine learning model to be trained on the training data set to perform one or more text processing tasks, wherein the input vocabulary is a proper subset of the text tokens in the initial vocabulary, and wherein the text tokens in the input vocabulary are represented as unique tokens in inputs to the first machine learning model, the selecting comprising:

for each particular text token of a plurality of text tokens in the initial vocabulary:

generating a plurality of first candidate input vocabularies that do not include the particular text token;

for each of the plurality of first candidate input vocabularies, generating a corresponding second input vocabulary that includes (i) the text tokens in the first candidate input vocabulary and (ii) the particular text token;

for each of the plurality of first candidate input vocabularies, training a second machine learning model to perform the one or more text processing tasks on at least a portion of the training data set with an input vocabulary for the second machine learning model set to the first candidate input vocabulary;

for each of the plurality of second candidate input vocabularies, training the second machine learning model to perform the one or more text processing tasks on at least a portion of the training data set with the input vocabulary for the second machine learning model set to the second candidate input vocabulary; and

determining a score for the particular text token that measures a difference between (i) the performance on the one or more text processing tasks of the second machine learning model when trained with the plurality of first candidate input vocabularies that do not include the particular text token and (ii) the performance on the one or more text processing tasks of the second machine learning model when trained with the plurality of second candidate input vocabularies that do include the particular text token;

selecting the input vocabulary based on the scores for the particular text tokens; and

training the first machine learning model to perform the one or more text processing tasks on at least a portion of the training data set with the input vocabulary for the first machine learning model set to the selected input vocabulary.

21 . One or more non-transitory computer-readable storage media encoded with instructions that, when executed by one or more computers, cause the one or more computers to perform operations comprising:

obtaining a training data set comprising a plurality of text segments in one or more natural languages, each text segment comprising one or more text tokens that are each selected from an initial vocabulary of text tokens in the one or more natural languages;

selecting an input vocabulary for a first machine learning model to be trained on the training data set to perform one or more text processing tasks, wherein the input vocabulary is a proper subset of the text tokens in the initial vocabulary, and wherein the text tokens in the input vocabulary are represented as unique tokens in inputs to the first machine learning model, the selecting comprising:

for each particular text token of a plurality of text tokens in the initial vocabulary:

generating a plurality of first candidate input vocabularies that do not include the particular text token;

for each of the plurality of first candidate input vocabularies, generating a corresponding second input vocabulary that includes (i) the text tokens in the first candidate input vocabulary and (ii) the particular text token;

for each of the plurality of first candidate input vocabularies, training a second machine learning model to perform the one or more text processing tasks on at least a portion of the training data set with an input vocabulary for the second machine learning model set to the first candidate input vocabulary;

for each of the plurality of second candidate input vocabularies, training the second machine learning model to perform the one or more text processing tasks on at least a portion of the training data set with the input vocabulary for the second machine learning model set to the second candidate input vocabulary; and

determining a score for the particular text token that measures a difference between (i) the performance on the one or more text processing tasks of the second machine learning model when trained with the plurality of first candidate input vocabularies that do not include the particular text token and (ii) the performance on the one or more text processing tasks of the second machine learning model when trained with the plurality of second candidate input vocabularies that do include the particular text token;

selecting the input vocabulary based on the scores for the particular text tokens; and

training the first machine learning model to perform the one or more text processing tasks on at least a portion of the training data set with the input vocabulary for the first machine learning model set to the selected input vocabulary.

22 . The system of claim 20 , wherein the text tokens in the initial vocabulary that are not in the input vocabulary are all represented as a single, shared token in inputs to the first machine learning model.

Assignments (2)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 6, 2025
From: DEEPMIND TECHNOLOGIES LIMITED
To: GDM HOLDING LLC
Reel/Frame 071498/0210 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 13, 2023
From: GEMP, IAN MICHAEL; BACHRACH, YORAM; PATEL, ROMA; DYER, CHRISTOPHER JAMES
To: DEEPMIND TECHNOLOGIES LIMITED
Reel/Frame 063932/0917 →
Continuity (2)
Provisional Application 63117953 · Nov 24, 2020
Related Publication 20240013769A1 · Jan 11, 2024
References Cited (53)
US 10650667B1 · Afghah · 2020 [cited by examiner]
US 20150200962A1 · Xu · 2015 [cited by examiner]
US 20180121817A1 · Datta · 2018 [cited by examiner]
Adadi et al., “Peeking inside the black-box: a survey on explainable artificial intelligence (XAI),” IEEE access, Sep. 16, 2018, 6:52138-60. [cited by applicant]
Bachrach et al., “Approximating power indices: theoretical and empirical analysis,” Autonomous Agents and Multi-Agent Systems, Mar. 2010, 20:105-22. [cited by applicant]
Bahdanau et al., “Learning to compute word embeddings on the fly,” CoRR, submitted on Jun. 1, 2017, arXiv:1706.00286, 12 pages. [cited by applicant]
Bilbao et al., “Voting power in the European Union enlargement,” European Journal of Operational Research, Nov. 16, 2002, 143(1):181-96. [cited by applicant]
Bowman et al., “A large annotated corpus for learning natural language inference,” CoRR, submitted on Aug. 21, 2015, arXiv:1508.05326v1, 11 pages. [cited by applicant]
Banzhaf, “Weighted voting doesn't work: A mathematical analysis,” Rutgers Law Review, 1964, 19:317 (abstract only). [cited by applicant]
Chen et al., “How large a vocabulary does text classification need? a variational approach to vocabulary selection,” CoRR, submitted on Apr. 3, 2019, arXiv:1902.10339v4, 11 pages. [cited by applicant]
Datta et al., “Algorithmic transparency via quantitative input influence: Theory and experiments with learning systems,” In 2016 IEEE symposium on security and privacy (SP), May 22, 2016, p. 598-617. [cited by applicant]
Dubey et al., “Mathematical properties of the Banzhaf power index,” Mathematics of Operations Research, May 1979, 4(2):99-131 (abstract only). [cited by applicant]
Dubey, “On the uniqueness of the Shapley value,” International Journal of Game Theory, Sep. 1975, 4:131-9 (abstract only). [cited by applicant]
Elkind et al., “Computational complexity of weighted threshold games,” In AAAI, Jul. 22, 2007, p. 718-723. [cited by applicant]
Faruqui et al., “Sparse overcomplete word vector representations,” CoRR, submitted on Jun. 5, 2015, arXiv:1506.02004v1, 10 pages. [cited by applicant]
Fatima et al., “A linear approximation method for the Shapley value,” Artificial Intelligence, Sep. 1, 2008, 172(14):1673-99. [cited by applicant]
Friedman et al., “Regularization paths for generalized linear models via coordinate descent,” Journal of statistical software, 2010, 33(1):1. [cited by applicant]
Gilpin et al., “Explaining explanations: An overview of interpretability of machine learning,” In 2018 IEEE 5th International Conference on data science and advanced analytics (DSAA), Oct. 1, 2018, p. 80-89. [cited by applicant]
Han et al., “Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding,” CoRR, submitted on Feb. 15, 2016, arXiv:1510.00149v5, 14 pages. [cited by applicant]
Hubara et al., “Quantized neural networks: Training neural networks with low precision weights and activations,” The Journal of Machine Learning Research, 18(1):6869-6898 (2018). [cited by applicant]
International Preliminary Report on Patentability in Appln. No. PCT/EP2021/082488, mailed on Jun. 8, 2023, 7 pages. [cited by applicant]
International Search Report and Written Opinion in Appln. No. PCT/EP2021/082488, mailed on Feb. 24, 2022, 12 pages. [cited by applicant]
Kim et al., “Character-aware neural language models,” In Proceedings of the AAAI conference on artificial intelligence, Mar. 5, 2016, 9 pages. [cited by applicant]
Kudo et al., “Sentencepiece: A simple and language independent subword tokenizer and detokenizer for neural text processing,” CoRR, submitted on Aug. 19, 2018, arXiv:1808.06226v1, 6 pages. [cited by applicant]
Le et al., “A simple way to initialize recurrent networks of rectified linear units,” CoRR, submitted on Apr. 7, 2015, arXiv:1504.00941v2, 9 pages. [cited by applicant]
Lee et al., “Fully character-level neural machine translation without explicit segmentation,” Transactions of the Association for Computational Linguistics, Oct. 1, 2017, 5:365-78. [cited by applicant]
L'Hostis et al., “Vocabulary selection strategies for neural machine translation,” CoRR, submitted on Oct. 1, 2016, arXiv:1610.00072v1, 9 pages. [cited by applicant]
Ling et al., “Character-based neural machine translation,” CoRR, submitted on Nov. 14, 2015, arXiv:1511.04586v1, 11 pages. [cited by applicant]
Lundberg et al., “A unified approach to interpreting model predictions,” In Advances in neural information processing systems, submitted on Nov. 25, 2017, p. 4765-4774. [cited by applicant]
Lundberg et al., “From local explanations to global understanding with explainable AI for trees,” Nature machine intelligence, Jan. 2020, 2(1):56-67. [cited by applicant]
Maleki et al., “Bounding the estimation error of sampling-based Shapley value approximation,” CoRR, submitted on Feb. 12, 2014, arXiv:1306.4265v2, 14 pages. [cited by applicant]
Matsui et al., “A survey of algorithms for calculating power indices of weighted majority games,” Journal of the Operations Research Society of Japan, 2000, 43(1):71-86. [cited by applicant]
Matsui et al., “Np-completeness for calculating power indices of weighted majority games,” Theoretical Computer Science, Jul. 28, 2001, 263(1-2):305-310. [cited by applicant]
Meinshausen et al., “Stability selection,” Journal of the Royal Statistical Society Series B: Statistical Methodology, Sep. 2010,72(4):417-73. [cited by applicant]
Molchanov et al., “Variational dropout sparsifies deep neural networks,” In International Conference on Machine Learning, Jul. 17, 2017, p. 2498-2507. [cited by applicant]
Neklyudov et al., “Structured bayesian pruning via log-normal multiplicative noise,” Advances in Neural Information Processing Systems, 2017, 10 pages. [cited by applicant]
Nimon et al., “Understanding the results of multiple linear regression: Beyond standardized regression coefficients,” Organizational Research Methods, Oct. 2013, 16(4):650-74. [cited by applicant]
Provilkov et al., “Bpe-dropout: Simple and effective subword regularization,” CoRR, submitted on May 1, 2020, arXiv:1910.13267v2, 11 pages. [cited by applicant]
Qian et al., “Human Versus Machine and Human-Machine teaming on Masked Language Modeling Tasks,” Computer Vision, Oct. 17, 2020, 12 pages. [cited by applicant]
Radev et al., “Evaluating web-based question answering systems,” In LREC, May 2002, 4 pages. [cited by applicant]
Ramos, “Using tf-idf to determine word relevance in document queries,” In Proceedings of the first instructional conference on machine learning, Dec. 3, 2003, 242(1):29-48. [cited by applicant]
Schmeidler et al., “The nucleolus of a characteristic function game,” SIAM Journal on applied mathematics, 17(6):1163-1170 (partial) (1969). [cited by applicant]
Sennrich et al., “Neural machine translation of rare words with subword units,” CoRR, submitted on Jun. 10, 2016, arXiv:1508.07909v5, 11 pages. [cited by applicant]
Shapley, “A value for n-person games,” Contributions to the Theory of Games, 1953, 2(28):307-317. [cited by applicant]
Shi et al., “Speeding up neural machine translation decoding by shrinking run-time vocabulary,” In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (vol. 2: Short Papers), Jul. 201… [cited by applicant]
Socher et al., “Recursive deep models for semantic compositionality over a sentiment treebank,” In Proceedings of the 2013 conference on empirical methods in natural language processing, Oct. 2013, p. 1631-1642. [cited by applicant]
Strafiin, “The Shapley-Shubik and Banzhaf power indices as probabilities,” The Shapley value: essays in honor of Lloyd S. Shapley, Oct. 28, 1988, p. 71. [cited by applicant]
Tjandra et al., “Compressing recurrent neural network with tensor train,” In 2017 International Joint Conference on Neural Networks (IJCNN), May 14, 2017, p. 4451-4458. [cited by applicant]
Wang et al., “Glue: A multi-task benchmark and analysis platform for natural language understanding,” CoRR, submitted on Feb. 22, 2019, arXiv:1804.07461v3, 20 pages. [cited by applicant]
Warstadt et al., “Neural network acceptability judgments,” Transactions of the Association for Computational Linguistics, Sep. 1, 2019, 7:625-41. [cited by applicant]
Wen et al., “Learning structured sparsity in deep neural networks,” Advances in neural information processing systems, 2016, 9 pages. [cited by applicant]
Yogatama et al., “Learning word representations with hierarchical sparse coding,” In International Conference on Machine Learning, Jun. 1, 2015, p. 87-96. [cited by applicant]
Zhang et al., “Character-level convolutional networks for text classification,” In Advances in neural information processing systems, 2015, 9 pages. [cited by applicant]