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]

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: 

Metrics

  • PDF downloads (61)
  • HTML views (177)
  • Cited by (0)

[Back to Top]