A Mean Field Games model for finite mixtures of Bernoulli and categorical distributions

Laura Aquilanti; Simone Cacace; Fabio Camilli; Raul De Maio

doi:10.3934/jdg.2020033

Article Contents

2021, Volume 8, Issue 1: 35-59. Doi: 10.3934/jdg.2020033

This issue Previous Article Permanence in polymatrix replicators Next Article A note on the lattice structure for matching markets via linear programming

A Mean Field Games model for finite mixtures of Bernoulli and categorical distributions

1.
SBAI, Sapienza Università di Roma, Via A. Scarpa 16, 00161 Roma, Italy
2.
Dip. di Matematica e Fisica, Università degli Studi Roma Tre, Largo S. L. Murialdo 1, 00146 Roma, Italy
3.
IConsulting, Via della Conciliazione 10, 00193 Roma, Italy

^* Corresponding author: Fabio Camilli
^* Corresponding author: Fabio Camilli

Received: April 30, 2020

Revised: October 31, 2020

Early access: December 2020

Published: January 2021

Abstract Full Text(HTML) Figure(9) Related Papers Cited by

Abstract

Finite mixture models are an important tool in the statistical analysis of data, for example in data clustering. The optimal parameters of a mixture model are usually computed by maximizing the log-likelihood functional via the Expectation-Maximization algorithm. We propose an alternative approach based on the theory of Mean Field Games, a class of differential games with an infinite number of agents. We show that the solution of a finite state space multi-population Mean Field Games system characterizes the critical points of the log-likelihood functional for a Bernoulli mixture. The approach is then generalized to mixture models of categorical distributions. Hence, the Mean Field Games approach provides a method to compute the parameters of the mixture model, and we show its application to some standard examples in cluster analysis.

Keywords:

Mathematics Subject Classification: 62H30, 60J10, 49N80, 91C20.

Citation:

Full Text(HTML)

Figure 1. Samples of hand-written digits from the MNIST database

Download: Full-size image PowerPoint slide

Figure 2. Different samples of hand-written digits from the MNIST database

Download: Full-size image PowerPoint slide

Figure 3. Clusterization histogram for digits $ \mathbf{1},\mathbf{3} $ and the corresponding Bernoulli parameters

Download: Full-size image PowerPoint slide

Figure 4. Clusterization histogram for digits $ \mathbf{3},\mathbf{5} $ and the corresponding Bernoulli parameters

Download: Full-size image PowerPoint slide

Figure 5. Clusterization histogram for even digits and the corresponding Bernoulli parameters

Download: Full-size image PowerPoint slide

Figure 6. Samples of fashion products from the Fashion-MNIST database

Download: Full-size image PowerPoint slide

Figure 7. Averaged categorical distributions for the Fashion-MNIST database

Download: Full-size image PowerPoint slide

Figure 8. Clusterization histogram for types T-shirt, Trouser and the corresponding categorical parameters

Download: Full-size image PowerPoint slide

Figure 9. Clusterization histogram for types Dress, Sneaker, Bag, Boot and the corresponding categorical parameters

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	L. Aquilanti, S. Cacace, F. Camilli and R. De Maio, A mean field games approach to cluster analysis, Applied Math. Optim., (2020). doi: 10.1007/s00245-019-09646-2.
[2]	R. Bellman, Dynamic Programming, Princeton Landmarks in Mathematics, Princeton University Press, Princeton, NJ, 1957.
[3]	J. A. Bilmes, A gentle tutorial of the EM algorithm and its application to parameter estimation for Gaussian mixture and hidden Markov model, CTIT Technical Reports Series, 1998.
[4]	C. M. Bishop, Pattern Recognition and Machine Learning, Information Science and Statistics, Springer, New York, 2006.
[5]	A. Biswas, Mean Field Games with ergodic cost for discrete time Markov processes, preprint, arXiv: 1510.08968.
[6]	S. Cacace, F. Camilli and A. Goffi, A policy iteration method for Mean Field Games, preprint, arXiv: 2007.04818.
[7]	R. Carmona and M. Lauriere, Convergence analysis of machine learning algorithms for the numerical solution of mean field control and games: I – The ergodic case, preprint, arXiv: 1907.05980.
[8]	J. L. Coron, Quelques Exemples de Jeux à Champ Moyen, Ph.D. thesis, Université Paris-Dauphine, 2018. Available from: https://tel.archives-ouvertes.fr/tel-01705969/document.
[9]	W. E, J. Han and Q. Li, A mean-field optimal control formulation of deep learning, Res. Math. Sci., 6 (2019), 41pp. doi: 10.1007/s40687-018-0172-y.
[10]	B. S. Everitt, S. Landau, M. Leese and D. Stahl, Cluster Analysis, Wiley Series in Probability and Statistics, John Wiley & Sons, Ltd., Chichester, 2011. doi: 10.1002/9780470977811.
[11]	Fashion-MNIST., Available from: https://github.com/zalandoresearch/fashion-mnist.
[12]	W. H. Fleming, Some Markovian optimization problems, J. Math. Mech., 12 (1963), 131-140.
[13]	D. A. Gomes, J. Mohr and R. R. Souza, Discrete time, finite state space mean field games, J. Math. Pures Appl. (9), 93 (2010), 308-328. doi: 10.1016/j.matpur.2009.10.010.
[14]	D. A. Gomes and J. Saúde, Mean field games models–A brief survey, Dyn. Games Appl., 4 (2014), 110-154. doi: 10.1007/s13235-013-0099-2.
[15]	R. A. Howard, Dynamic Programming and Markov Processes, The Technology Press of MIT, Cambridge, Mass.; John Wiley & Sons, Inc., New York-London, 1960. doi: 10.1126/science.132.3428.667.
[16]	M. Huang, R. P. Malhamé and P. E. Caines, Large population stochastic dynamic games: Closed-loop McKean-Vlasov systems and the Nash certainty equivalence principle, Commun. Inf. Syst., 6 (2006), 221-251. doi: 10.4310/CIS.2006.v6.n3.a5.
[17]	J.-M. Lasry and P.-L. Lions, Mean field games, Jpn. J. Math., 2 (2007), 229-260. doi: 10.1007/s11537-007-0657-8.
[18]	G. McLachlan and D. Peel, Finite Mixture Models, Wiley Series in Probability and Statistics: Applied Probability and Statistics, Wiley-Interscience, New York, 2000. doi: 10.1002/0471721182.
[19]	The MNIST Database of Handwritten Digits., Available from: http://yann.lecun.com/exdb/mnist/.
[20]	K. Pearson, Contributions to the mathematical theory of evolution, Philosophical Trans. Roy. Soc., 185 (1894), 71-110. doi: 10.1098/rsta.1894.0003.
[21]	S. Pequito, A. Pedro Aguiar, B. Sinopoli and D. A. Gomes, Unsupervised learning of finite mixture models using mean field games, 49$^th$ Annual Allerton Conference on Communication, Control and Computing, Monticello, IL, 2011. doi: 10.1109/Allerton.2011.6120185.
[22]	M. L. Puterman, On the convergence of policy iteration for controlled diffusions, J. Optim. Theory Appl., 33 (1981), 137-144. doi: 10.1007/BF00935182.
[23]	M. L. Puterman and S. L. Brumelle, On the convergence of policy iteration in stationary dynamic programming, Math. Oper. Res., 4 (1979), 60-69. doi: 10.1287/moor.4.1.60.
[24]	M. E. Tarter and M. D. Lock, Model-Free Curve Estimation, Monographs on Statistics and Applied Probability, 56, Chapman & Hall, New York, 1993.
[25]	D. M. Titterington, A. F. M. Smith and U. E. Makov, Statistical Analysis of Finite Mixture Distributions, Wiley Series Probability and Mathematical Statistics: Applied Probability and Statistics, John Wiley & Sons, Ltd., Chichester, 1985.
[26]	M. Wedel and W. A. Kamakura, Market Segmentation: Conceptual and Methodological Foundations, International Series in Quantitative Marketing, 8, Springer, Boston, MA, 2000. doi: 10.1007/978-1-4615-4651-1.