Figure 1.
Samples of hand-written digits from the MNIST database
- Previous Article
- JDG Home
- This Issue
-
Next Article
New solutions of hyperbolic telegraph equation
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, 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] |
Illés Horváth, Kristóf Attila Horváth, Péter Kovács, Miklós Telek. Mean-field analysis of a scaling MAC radio protocol. Journal of Industrial & Management Optimization, 2021, 17 (1) : 279-297. doi: 10.3934/jimo.2019111 |
| [2] |
Kalikinkar Mandal, Guang Gong. On ideal $ t $-tuple distribution of orthogonal functions in filtering de bruijn generators. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020125 |
| [3] |
Daniele Bartolucci, Changfeng Gui, Yeyao Hu, Aleks Jevnikar, Wen Yang. Mean field equations on tori: Existence and uniqueness of evenly symmetric blow-up solutions. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3093-3116. doi: 10.3934/dcds.2020039 |
| [4] |
Alain Bensoussan, Xinwei Feng, Jianhui Huang. Linear-quadratic-Gaussian mean-field-game with partial observation and common noise. Mathematical Control & Related Fields, 2021, 11 (1) : 23-46. doi: 10.3934/mcrf.2020025 |
| [5] |
Jingrui Sun, Hanxiao Wang. Mean-field stochastic linear-quadratic optimal control problems: Weak closed-loop solvability. Mathematical Control & Related Fields, 2021, 11 (1) : 47-71. doi: 10.3934/mcrf.2020026 |
| [6] |
Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167 |
| [7] |
Aihua Fan, Jörg Schmeling, Weixiao Shen. $ L^\infty $-estimation of generalized Thue-Morse trigonometric polynomials and ergodic maximization. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 297-327. doi: 10.3934/dcds.2020363 |
| [8] |
Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005 |
| [9] |
George W. Patrick. The geometry of convergence in numerical analysis. Journal of Computational Dynamics, 2021, 8 (1) : 33-58. doi: 10.3934/jcd.2021003 |
| [10] |
Jian Zhang, Tony T. Lee, Tong Ye, Liang Huang. An approximate mean queue length formula for queueing systems with varying service rate. Journal of Industrial & Management Optimization, 2021, 17 (1) : 185-204. doi: 10.3934/jimo.2019106 |
| [11] |
Bixiang Wang. Mean-square random invariant manifolds for stochastic differential equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1449-1468. doi: 10.3934/dcds.2020324 |
| [12] |
Petr Pauš, Shigetoshi Yazaki. Segmentation of color images using mean curvature flow and parametric curves. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1123-1132. doi: 10.3934/dcdss.2020389 |
| [13] |
Anna Abbatiello, Eduard Feireisl, Antoní Novotný. Generalized solutions to models of compressible viscous fluids. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 1-28. doi: 10.3934/dcds.2020345 |
| [14] |
Xin Guo, Lexin Li, Qiang Wu. Modeling interactive components by coordinate kernel polynomial models. Mathematical Foundations of Computing, 2020, 3 (4) : 263-277. doi: 10.3934/mfc.2020010 |
| [15] |
Urszula Ledzewicz, Heinz Schättler. On the role of pharmacometrics in mathematical models for cancer treatments. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 483-499. doi: 10.3934/dcdsb.2020213 |
| [16] |
P. K. Jha, R. Lipton. Finite element approximation of nonlocal dynamic fracture models. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1675-1710. doi: 10.3934/dcdsb.2020178 |
| [17] |
Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251 |
| [18] |
Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018 |
| [19] |
Josselin Garnier, Knut Sølna. Enhanced Backscattering of a partially coherent field from an anisotropic random lossy medium. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1171-1195. doi: 10.3934/dcdsb.2020158 |
| [20] |
Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017 |
Impact Factor:
Tools
Article outline
Figures and Tables
[Back to Top]