Figure 1.
Samples of hand-written digits from the MNIST database
-
Previous Article
A note on the lattice structure for matching markets via linear programming
- JDG Home
- This Issue
-
Next Article
Permanence in polymatrix replicators
January
2021, 8(1): 35-59.
doi: 10.3934/jdg.2020033
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 |
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:
Mixture models,
Bernoulli distribution,
categorical distribution,
cluster analysis,
Expectation-Maximization algorithm,
Mean Field Games.
Mathematics Subject Classification:
62H30, 60J10, 49N80, 91C20.
Citation:
Laura Aquilanti, Simone Cacace, Fabio Camilli, Raul De Maio. A Mean Field Games model for finite mixtures of Bernoulli and categorical distributions. Journal of Dynamics & Games,
2021, 8
(1)
: 35-59.
doi: 10.3934/jdg.2020033
![]()
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. Google Scholar |
| [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. Google Scholar |
| [6] |
S. Cacace, F. Camilli and A. Goffi, A policy iteration method for Mean Field Games, preprint, arXiv: 2007.04818. Google Scholar |
| [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. Google Scholar |
| [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. Google Scholar |
| [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. Google Scholar |
| [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/. Google Scholar |
| [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. |
show all references
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. Google Scholar |
| [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. Google Scholar |
| [6] |
S. Cacace, F. Camilli and A. Goffi, A policy iteration method for Mean Field Games, preprint, arXiv: 2007.04818. Google Scholar |
| [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. Google Scholar |
| [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. Google Scholar |
| [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. Google Scholar |
| [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/. Google Scholar |
| [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. |
Figure 2.
Different samples of hand-written digits from the MNIST database
Figure 3.
Clusterization histogram for digits $ \mathbf{1},\mathbf{3} $ and the corresponding Bernoulli parameters
Figure 4.
Clusterization histogram for digits $ \mathbf{3},\mathbf{5} $ and the corresponding Bernoulli parameters
Figure 5.
Clusterization histogram for even digits and the corresponding Bernoulli parameters
Figure 6.
Samples of fashion products from the Fashion-MNIST database
Figure 7.
Averaged categorical distributions for the Fashion-MNIST database
Figure 8.
Clusterization histogram for types T-shirt, Trouser and the corresponding categorical parameters
Figure 9.
Clusterization histogram for types Dress, Sneaker, Bag, Boot and the corresponding categorical parameters
| [1] |
Marc Bocquet, Julien Brajard, Alberto Carrassi, Laurent Bertino. Bayesian inference of chaotic dynamics by merging data assimilation, machine learning and expectation-maximization. Foundations of Data Science, 2020, 2 (1) : 55-80. doi: 10.3934/fods.2020004 |
| [2] |
Ross Callister, Duc-Son Pham, Mihai Lazarescu. Using distribution analysis for parameter selection in repstream. Mathematical Foundations of Computing, 2019, 2 (3) : 215-250. doi: 10.3934/mfc.2019015 |
| [3] |
Marco Cirant, Diogo A. Gomes, Edgard A. Pimentel, Héctor Sánchez-Morgado. On some singular mean-field games. Journal of Dynamics & Games, 2021 doi: 10.3934/jdg.2021006 |
| [4] |
Pierre Cardaliaguet, Jean-Michel Lasry, Pierre-Louis Lions, Alessio Porretta. Long time average of mean field games. Networks & Heterogeneous Media, 2012, 7 (2) : 279-301. doi: 10.3934/nhm.2012.7.279 |
| [5] |
Josu Doncel, Nicolas Gast, Bruno Gaujal. Discrete mean field games: Existence of equilibria and convergence. Journal of Dynamics & Games, 2019, 6 (3) : 221-239. doi: 10.3934/jdg.2019016 |
| [6] |
Yves Achdou, Manh-Khang Dao, Olivier Ley, Nicoletta Tchou. A class of infinite horizon mean field games on networks. Networks & Heterogeneous Media, 2019, 14 (3) : 537-566. doi: 10.3934/nhm.2019021 |
| [7] |
Fabio Camilli, Elisabetta Carlini, Claudio Marchi. A model problem for Mean Field Games on networks. Discrete & Continuous Dynamical Systems, 2015, 35 (9) : 4173-4192. doi: 10.3934/dcds.2015.35.4173 |
| [8] |
Martin Burger, Marco Di Francesco, Peter A. Markowich, Marie-Therese Wolfram. Mean field games with nonlinear mobilities in pedestrian dynamics. Discrete & Continuous Dynamical Systems - B, 2014, 19 (5) : 1311-1333. doi: 10.3934/dcdsb.2014.19.1311 |
| [9] |
Zhilin Kang, Xingyi Li, Zhongfei Li. Mean-CVaR portfolio selection model with ambiguity in distribution and attitude. Journal of Industrial & Management Optimization, 2020, 16 (6) : 3065-3081. doi: 10.3934/jimo.2019094 |
| [10] |
I-Lin Wang, Shiou-Jie Lin. A network simplex algorithm for solving the minimum distribution cost problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 929-950. doi: 10.3934/jimo.2009.5.929 |
| [11] |
Kevin Ford. The distribution of totients. Electronic Research Announcements, 1998, 4: 27-34. |
| [12] |
Ming Yan, Alex A. T. Bui, Jason Cong, Luminita A. Vese. General convergent expectation maximization (EM)-type algorithms for image reconstruction. Inverse Problems & Imaging, 2013, 7 (3) : 1007-1029. doi: 10.3934/ipi.2013.7.1007 |
| [13] |
Martino Bardi. Explicit solutions of some linear-quadratic mean field games. Networks & Heterogeneous Media, 2012, 7 (2) : 243-261. doi: 10.3934/nhm.2012.7.243 |
| [14] |
Diogo A. Gomes, Gabriel E. Pires, Héctor Sánchez-Morgado. A-priori estimates for stationary mean-field games. Networks & Heterogeneous Media, 2012, 7 (2) : 303-314. doi: 10.3934/nhm.2012.7.303 |
| [15] |
Yves Achdou, Victor Perez. Iterative strategies for solving linearized discrete mean field games systems. Networks & Heterogeneous Media, 2012, 7 (2) : 197-217. doi: 10.3934/nhm.2012.7.197 |
| [16] |
Matt Barker. From mean field games to the best reply strategy in a stochastic framework. Journal of Dynamics & Games, 2019, 6 (4) : 291-314. doi: 10.3934/jdg.2019020 |
| [17] |
Siting Liu, Levon Nurbekyan. Splitting methods for a class of non-potential mean field games. Journal of Dynamics & Games, 2021 doi: 10.3934/jdg.2021014 |
| [18] |
Olivier Guéant. New numerical methods for mean field games with quadratic costs. Networks & Heterogeneous Media, 2012, 7 (2) : 315-336. doi: 10.3934/nhm.2012.7.315 |
| [19] |
Juan Pablo Maldonado López. Discrete time mean field games: The short-stage limit. Journal of Dynamics & Games, 2015, 2 (1) : 89-101. doi: 10.3934/jdg.2015.2.89 |
| [20] |
Michael Herty, Lorenzo Pareschi, Giuseppe Visconti. Mean field models for large data–clustering problems. Networks & Heterogeneous Media, 2020, 15 (3) : 463-487. doi: 10.3934/nhm.2020027 |
Impact Factor:
Tools
Article outline
Figures and Tables
[Back to Top]