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] |
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 |
| [2] |
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 |
| [3] |
Jun Moon. Linear-quadratic mean-field type stackelberg differential games for stochastic jump-diffusion systems. Mathematical Control & Related Fields, 2021 doi: 10.3934/mcrf.2021026 |
| [4] |
Quan Hai, Shutang Liu. Mean-square delay-distribution-dependent exponential synchronization of chaotic neural networks with mixed random time-varying delays and restricted disturbances. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3097-3118. doi: 10.3934/dcdsb.2020221 |
| [5] |
Andrey Kovtanyuk, Alexander Chebotarev, Nikolai Botkin, Varvara Turova, Irina Sidorenko, Renée Lampe. Modeling the pressure distribution in a spatially averaged cerebral capillary network. Mathematical Control & Related Fields, 2021 doi: 10.3934/mcrf.2021016 |
| [6] |
Ricardo A. Podestá, Denis E. Videla. The weight distribution of irreducible cyclic codes associated with decomposable generalized Paley graphs. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021002 |
| [7] |
Seung-Yeal Ha, Jinwook Jung, Jeongho Kim, Jinyeong Park, Xiongtao Zhang. A mean-field limit of the particle swarmalator model. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2021011 |
| [8] |
Ritu Agarwal, Kritika, Sunil Dutt Purohit, Devendra Kumar. Mathematical modelling of cytosolic calcium concentration distribution using non-local fractional operator. Discrete & Continuous Dynamical Systems - S, 2021 doi: 10.3934/dcdss.2021017 |
| [9] |
René Aïd, Roxana Dumitrescu, Peter Tankov. The entry and exit game in the electricity markets: A mean-field game approach. Journal of Dynamics & Games, 2021 doi: 10.3934/jdg.2021012 |
| [10] |
Zhenquan Zhang, Meiling Chen, Jiajun Zhang, Tianshou Zhou. Analysis of non-Markovian effects in generalized birth-death models. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3717-3735. doi: 10.3934/dcdsb.2020254 |
| [11] |
Ruchika Sehgal, Aparna Mehra. Worst-case analysis of Gini mean difference safety measure. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1613-1637. doi: 10.3934/jimo.2020037 |
| [12] |
Tadeusz Kaczorek, Andrzej Ruszewski. Analysis of the fractional descriptor discrete-time linear systems by the use of the shuffle algorithm. Journal of Computational Dynamics, 2021 doi: 10.3934/jcd.2021007 |
| [13] |
Kehan Si, Zhenda Xu, Ka Fai Cedric Yiu, Xun Li. Open-loop solvability for mean-field stochastic linear quadratic optimal control problems of Markov regime-switching system. Journal of Industrial & Management Optimization, 2021 doi: 10.3934/jimo.2021074 |
| [14] |
İsmail Özcan, Sirma Zeynep Alparslan Gök. On cooperative fuzzy bubbly games. Journal of Dynamics & Games, 2021 doi: 10.3934/jdg.2021010 |
| [15] |
Takao Komatsu, Bijan Kumar Patel, Claudio Pita-Ruiz. Several formulas for Bernoulli numbers and polynomials. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021006 |
| [16] |
Zemer Kosloff, Terry Soo. The orbital equivalence of Bernoulli actions and their Sinai factors. Journal of Modern Dynamics, 2021, 17: 145-182. doi: 10.3934/jmd.2021005 |
| [17] |
Fang Li, Jie Pan. On inner Poisson structures of a quantum cluster algebra without coefficients. Electronic Research Archive, , () : -. doi: 10.3934/era.2021021 |
| [18] |
Tianhu Yu, Jinde Cao, Chuangxia Huang. Finite-time cluster synchronization of coupled dynamical systems with impulsive effects. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3595-3620. doi: 10.3934/dcdsb.2020248 |
| [19] |
Junichi Minagawa. On the uniqueness of Nash equilibrium in strategic-form games. Journal of Dynamics & Games, 2020, 7 (2) : 97-104. doi: 10.3934/jdg.2020006 |
| [20] |
J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]