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

* Corresponding author: Fabio Camilli

Received  May 2020 Revised  November 2020 Published  December 2020

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.

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.  Google Scholar

[2]

R. Bellman, Dynamic Programming, Princeton Landmarks in Mathematics, Princeton University Press, Princeton, NJ, 1957.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[13]

D. A. GomesJ. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[16]

M. HuangR. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[24]

M. E. Tarter and M. D. Lock, Model-Free Curve Estimation, Monographs on Statistics and Applied Probability, 56, Chapman & Hall, New York, 1993.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[2]

R. Bellman, Dynamic Programming, Princeton Landmarks in Mathematics, Princeton University Press, Princeton, NJ, 1957.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[13]

D. A. GomesJ. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[16]

M. HuangR. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[24]

M. E. Tarter and M. D. Lock, Model-Free Curve Estimation, Monographs on Statistics and Applied Probability, 56, Chapman & Hall, New York, 1993.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

Figure 1.  Samples of hand-written digits from the MNIST database
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]

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

[2]

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

[3]

Jan Prüss, Laurent Pujo-Menjouet, G.F. Webb, Rico Zacher. Analysis of a model for the dynamics of prions. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 225-235. doi: 10.3934/dcdsb.2006.6.225

[4]

Michael Grinfeld, Amy Novick-Cohen. Some remarks on stability for a phase field model with memory. Discrete & Continuous Dynamical Systems - A, 2006, 15 (4) : 1089-1117. doi: 10.3934/dcds.2006.15.1089

[5]

Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781

[6]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327

[7]

Guido De Philippis, Antonio De Rosa, Jonas Hirsch. The area blow up set for bounded mean curvature submanifolds with respect to elliptic surface energy functionals. Discrete & Continuous Dynamical Systems - A, 2019, 39 (12) : 7031-7056. doi: 10.3934/dcds.2019243

[8]

Bin Pei, Yong Xu, Yuzhen Bai. Convergence of p-th mean in an averaging principle for stochastic partial differential equations driven by fractional Brownian motion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1141-1158. doi: 10.3934/dcdsb.2019213

[9]

Cicely K. Macnamara, Mark A. J. Chaplain. Spatio-temporal models of synthetic genetic oscillators. Mathematical Biosciences & Engineering, 2017, 14 (1) : 249-262. doi: 10.3934/mbe.2017016

[10]

Fernando P. da Costa, João T. Pinto, Rafael Sasportes. On the convergence to critical scaling profiles in submonolayer deposition models. Kinetic & Related Models, 2018, 11 (6) : 1359-1376. doi: 10.3934/krm.2018053

[11]

Jian Yang, Bendong Lou. Traveling wave solutions of competitive models with free boundaries. Discrete & Continuous Dynamical Systems - B, 2014, 19 (3) : 817-826. doi: 10.3934/dcdsb.2014.19.817

[12]

Tomáš Roubíček. An energy-conserving time-discretisation scheme for poroelastic media with phase-field fracture emitting waves and heat. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 867-893. doi: 10.3934/dcdss.2017044

[13]

Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265

[14]

Martial Agueh, Reinhard Illner, Ashlin Richardson. Analysis and simulations of a refined flocking and swarming model of Cucker-Smale type. Kinetic & Related Models, 2011, 4 (1) : 1-16. doi: 10.3934/krm.2011.4.1

[15]

Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367

[16]

Seung-Yeal Ha, Shi Jin. Local sensitivity analysis for the Cucker-Smale model with random inputs. Kinetic & Related Models, 2018, 11 (4) : 859-889. doi: 10.3934/krm.2018034

[17]

Shanshan Chen, Junping Shi, Guohong Zhang. Spatial pattern formation in activator-inhibitor models with nonlocal dispersal. Discrete & Continuous Dynamical Systems - B, 2021, 26 (4) : 1843-1866. doi: 10.3934/dcdsb.2020042

[18]

Alina Chertock, Alexander Kurganov, Mária Lukáčová-Medvi${\rm{\check{d}}}$ová, Șeyma Nur Özcan. An asymptotic preserving scheme for kinetic chemotaxis models in two space dimensions. Kinetic & Related Models, 2019, 12 (1) : 195-216. doi: 10.3934/krm.2019009

[19]

Carlos Fresneda-Portillo, Sergey E. Mikhailov. Analysis of Boundary-Domain Integral Equations to the mixed BVP for a compressible stokes system with variable viscosity. Communications on Pure & Applied Analysis, 2019, 18 (6) : 3059-3088. doi: 10.3934/cpaa.2019137

[20]

Mats Gyllenberg, Jifa Jiang, Lei Niu, Ping Yan. On the classification of generalized competitive Atkinson-Allen models via the dynamics on the boundary of the carrying simplex. Discrete & Continuous Dynamical Systems - A, 2018, 38 (2) : 615-650. doi: 10.3934/dcds.2018027

 Impact Factor: 

Metrics

  • PDF downloads (46)
  • HTML views (122)
  • Cited by (0)

[Back to Top]