IP Library › Granted Patent US 12,265,555
Granted Patent B2
US 12,265,555 · App. 18/510,079 · Granted Apr 1, 2025

Adaptive multi-model item selection systems and methods

Inventors: Jesse Anderton (Princeton Junction, NJ); Maryam Aziz (Princeton Junction, NJ); David Bourgin (Brooklyn, NY); Benjamin Austin Carterette (Wilmington, DE)
Assignee: Spotify AB
G06F16/285G06N3/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,265,555
App. No.
18/510,079
Granted
Apr 1, 2025
Kind
B2
Abstract

An adaptive multi-model item selection method, comprising: receiving, from one of a plurality of client devices, a request including a client-side feature vector representing a state of the client device; determining, by an advocate model, a probability distribution of a plurality of specialist cluster models from the client-side feature vector; choosing, by a use case selector, a cluster corresponding to a use case from the probability distribution; and obtaining, by the use case selector based on the cluster (i.e., the cluster that was sampled by the user case selector), a specialist cluster model from the plurality of specialist cluster models.

Claims (67)

1. A computer-implemented method for adaptive multi-model item selection, comprising:

receiving a request from a client device among a plurality of client devices, the request including a representation of a current state of the client device;

determining a probability distribution across a plurality of models based on the current state of the client device, wherein each of the plurality of models corresponds to a particular use case and the probability distribution provides one or more use cases the client device is in;

selecting a specific use case from the probability distribution; and

obtaining a model from the plurality of models based on the specific use case.

2. The method according to claim 1 , further comprising:

training, by a model trainer, a contextual bandit for each of the plurality of models on (1) a plurality of client-side feature vectors associated with the client device and (2) a plurality of server-side client feature vectors representing a set of features associated with a plurality of requests from the plurality of client devices, to predict the probability distribution.

3. The method according to claim 2 ,

wherein training the contextual bandit for each of the plurality of models generates a plurality of advocate contextual bandits; and

wherein each model is associated with one of the plurality of advocate contextual bandits.

4. The method according to claim 1 , further comprising:

scoring the probability distribution based on an estimate of a probability the client device is associated with each use case.

5. The method according to claim 1 , further comprising:

selecting a specific item from a database of items using the model.

6. The method according to claim 1 , further comprising:

receiving, from a server, a plurality of server-side client feature vectors, each server-side client feature vector representing any one of (i) a set of item features associated with a plurality of items available to particular client devices, (ii) a set of client features associated with at least one of the particular client devices, or (iii) a combination of (i) and (ii);

storing, in a memory, a plurality of mini-specialist cluster models, each mini-specialist cluster model of the plurality of mini-specialist cluster models being (i) associated with a corresponding client-side feature vector and (ii) trained on the plurality of server-side client feature vectors;

clustering the plurality of mini-specialist cluster models to obtain a soft cluster assignment for each of the mini-specialist cluster models, thereby generating a plurality of soft cluster assignments; and

training, by a model trainer, each of the plurality of models corresponding to a use case by combining the plurality of mini-specialist cluster models based on the soft cluster assignments associated with the mini-specialist cluster models.

7. The method according to claim 6 , further comprising:

determining whether to retrain any one of the plurality of mini-specialist cluster models; and

retraining, by the model trainer, the mini-specialist cluster models according to the determining.

8. The method according to claim 6 , further comprising:

reclustering the plurality of mini-specialist cluster models after a predetermined number of requests have been received.

9. The method according to claim 6 , further comprising:

receiving an instruction to retrain the mini-specialist cluster models.

10. A system for multi-model item selection, comprising:

a data communication device configured to receive, from one of a plurality of client devices, a request including a representation of a current state of a client device;

an analyzer configured to determine a probability distribution across a plurality of models based on the current state of the client device, wherein each of the plurality of models corresponds to a particular use case and the probability distribution provides one or more use cases the client device is in:

a use case selector configured to:

select a specific use case from the probability distribution; and

obtain a model from the plurality of models based on the specific use case.

11. The system according to claim 10 , further comprising:

a model trainer configured to:

train a contextual bandit for each of the plurality of models on (1) a plurality of client-side feature vectors associated with the client device and (2) a plurality of server-side client feature vectors representing a set of features associated with a plurality of requests from the plurality of client devices, to predict the probability distribution.

12. The system according to claim 11 ,

wherein training the contextual bandit for each of the plurality of models generates a plurality of advocate contextual bandits; and

wherein each model is associated with one of the plurality of advocate contextual bandits.

13. The system according to claim 10 , wherein the analyzer is further configured to score the probability distribution based on an estimate of a probability the client device is associated with each use case.

14. The system according to claim 10 , further comprising:

an item selector interface configured to select a specific item from a database of items using the model.

15. The system according to claim 10 , wherein:

the analyzer is further configured to:

receive a plurality of server-side client feature vectors, each server-side client feature vector representing any one of (i) a set of item features associated with a plurality of items available to a client device, (ii) a set of client features associated with at least one client device, or (iii) a combination of (i) and (ii);

a memory device is further configured to:

store a plurality of mini-specialist cluster models, each mini-specialist cluster model of the plurality of mini-specialist cluster models being (i) associated with a corresponding client-side feature vector and (ii) trained on the plurality of server-side client feature vectors;

the analyzer is further configured to:

cluster the plurality of mini-specialist cluster models to obtain a soft cluster assignment for each of the mini-specialist cluster models, thereby generating a plurality of soft cluster assignments; and

further comprising:

a model trainer configured to train each of the plurality of models corresponding to a use case by combining the plurality of mini-specialist cluster models based on the soft cluster assignments associated with the mini-specialist cluster models.

16. The system according to claim 15 , further comprising:

a training frequency calculator configured to:

determine whether to retrain any one of the plurality of mini-specialist cluster models; and

cause the model trainer to retrain the mini-specialist cluster models according to the determination.

17. The system according to claim 15 , wherein the use case selector is further configured to recluster the plurality of mini-specialist cluster models after a predetermined number of requests have been received.

18. The system according to claim 15 , further comprising:

a training frequency calculator configured to receive an instruction to retrain the mini-specialist cluster models.

19. A computer system, comprising: one or more processors; and a non-transitory computer-readable storage medium storing instructions that when executed by the one or more processors cause the computer system to perform operations, comprising:

receiving a request from a client device among a plurality of client devices, the request including a representation of a current state of the client device;

determining a probability distribution across a plurality of models based on the current state of the client device, wherein each of the plurality of models corresponds to a particular use case and the probability distribution provides one or more use cases the client device is in;

selecting a specific use case from the probability distribution; and

obtaining a model from the plurality of models based on the specific use case.

20. The non-computer system medium of claim 19 , the non-transitory computer-readable storage medium further having stored thereon a sequence of instructions for causing the one or more processors to perform:

training, by a model trainer, a contextual bandit for each of the plurality of models on (1) a plurality of client-side feature vectors associated with the client device and (2) a plurality of server-side client feature vectors representing a set of features associated with a plurality of requests from the plurality of client devices, to predict the probability distribution.

21. The computer system of claim 20 ,

wherein training the contextual bandit for each of the plurality of models generates a plurality of advocate contextual bandits; and

wherein each model is associated with one of the plurality of advocate contextual bandits.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Feb 9, 2024
From: ANDERTON, JESSE; AZIZ, MARYAM; BOURGIN, DAVID; CARTERETTE, BENJAMIN AUSTIN
To: SPOTIFY AB
Reel/Frame 066429/0730 →
Continuity (2)
Continuation 17552874 · Dec 16, 2021
Related Publication 20240160643A1 · May 16, 2024
References Cited (25)
US 11036764B1 · Zelenov · 2021 [cited by examiner]
US 11853328B2 · Anderton · 2023 [cited by applicant]
US 20080114756A1 · Konig · 2008 [cited by applicant]
US 20180108048A1 · Yoon · 2018 [cited by applicant]
Agarwal, A. et al., “Taming the monster: A fast and simple algorithm for contextual bandits”, 2014, In International Conference on Machine Learning, pp. 1638-1646. [cited by applicant]
Agrawal, S. et al., “Thompson Sampling for Contextual Bandits with Linear Payoffs”, In Proceedings of the 30th International Conference on International Conference on Machine Learning, vol. 28, ICML'13, 2013, III-1220-I… [cited by applicant]
Auer, P. et al., “Finite-time analysis of the multiarmed bandit problem”, Machine Learning, 2002, 47(2-3): 235-256. [cited by applicant]
Bietti, A. et al., “A contextual bandit bake-off”, 2018, arXiv preprint arXiv:1802.04064, 49 pages. [cited by applicant]
Chapelle, O. et al., “An Empirical Evaluation of Thompson Sampling”, In Shawe-Taylor, et al. eds., Advances in Neural Information Processing Systems 24, 2249-2257. Curran Associates, Inc., URL http://papers.nips.cc/pape… [cited by applicant]
Chu, W. et al., “Contextual bandits with linear payoff functions”, 2011, In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208-214. [cited by applicant]
Dumitrascu, Bianca et al., “PG-TS: Improved Thompson Sampling for Logistic Contextual Bandits”, 32nd Conf. on Neural Information Processing Systems (NeurIPS 2018), Montreal, Canada, pp. 4624-4633. [cited by applicant]
Foster, D.J. et al., “Practical contextual bandits with regression oracles”, 2018, arXiv preprint arXiv:1803.01088, 10 pages. [cited by applicant]
Gentile, C. et al., “On context-dependent clustering of bandits”, 2017, In International Conference on Machine Learning, pp. 1253-1262. PMLR. [cited by applicant]
Gentile, Claudia et al., “Online Clustering of Bandits”, Proc. Of the 31st Int'l. Conference on Machine Learning, Beijing, China, 2014, JMLR; W&CP vol. 32, 9 pages. [cited by applicant]
Harper, F.M. et al., “The movielens datasets: History and context”, 2015, ACM transactions on inter active intelligent systems (TIIS) 5(4): 1-19. [cited by applicant]
Kaufmann, E. et al., “Thompson sampling: An asymptotically optimal finite-time analysis”, 2012, In International conference on algorithmic learning theory, Springer, 16 pgs. [cited by applicant]
Langford, J. et al., “The Epoch-Greedy Algorithm for Contextual Multi-Armed Bandits”, 2007, In Proceedings of the 20th International Conference on Neural Information Processing Systems, NIPS'07, 8 pgs. [cited by applicant]
Li, L. et al., “A contextual-bandit approach to personalized news article recommendation”, 2010, In Proceedings of the 19th international conference on World wide web, pp. 661-670. [cited by applicant]
Li, S. et al., “Improved algorithm on online clustering of bandits”, 2019, arXiv preprint arXiv:1902.09162, 7 pages. [cited by applicant]
Li, S. et al., “Collaborative filtering bandits”, 2016, In Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, pp. 539-548. [cited by applicant]
Maillard, O.-A. et al., “Latent Bandits”, 2014, In International Conference on Machine Learning, pp. 136-144. [cited by applicant]
Nguyen, Trong et al., “Dynamic Clustering of Contextual Multi-Armed Bandits”, (2014), CIKM'14: Proceedings of the 2014 ACM International Conference on Information and Knowledge Management: Nov. 3-7, 2014, Shanghai, Chin… [cited by applicant]
Pichl, Martin et al., “User models for multi-context-aware music recommendation”, Jun. 2021, Multimedia Tools and Applications 80(3): 1-23. [cited by applicant]
Thompson,W. R., “On the likelihood that one unknown probability exceeds another in view of the evidence of two samples”, 1933, Biometrika 25(3/4): 285-294. [cited by applicant]
Van Wieringen, W. N., “Lecture notes on ridge regression”, 2015, arXiv preprint arXiv:1509.09169, 56 pages. [cited by applicant]