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  January 2021 Early access  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 and 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.

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

[6]

S. Cacace, F. Camilli and A. Goffi, A policy iteration method for Mean Field Games, preprint, arXiv: 2007.04818.

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

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

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

[12]

W. H. Fleming, Some Markovian optimization problems, J. Math. Mech., 12 (1963), 131-140. 

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

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

[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/.

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

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

[6]

S. Cacace, F. Camilli and A. Goffi, A policy iteration method for Mean Field Games, preprint, arXiv: 2007.04818.

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

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

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

[12]

W. H. Fleming, Some Markovian optimization problems, J. Math. Mech., 12 (1963), 131-140. 

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

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

[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/.

[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 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]

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]

Pierre Cardaliaguet, Jean-Michel Lasry, Pierre-Louis Lions, Alessio Porretta. Long time average of mean field games. Networks and Heterogeneous Media, 2012, 7 (2) : 279-301. doi: 10.3934/nhm.2012.7.279

[4]

Josu Doncel, Nicolas Gast, Bruno Gaujal. Discrete mean field games: Existence of equilibria and convergence. Journal of Dynamics and Games, 2019, 6 (3) : 221-239. doi: 10.3934/jdg.2019016

[5]

Yves Achdou, Manh-Khang Dao, Olivier Ley, Nicoletta Tchou. A class of infinite horizon mean field games on networks. Networks and Heterogeneous Media, 2019, 14 (3) : 537-566. doi: 10.3934/nhm.2019021

[6]

Fabio Camilli, Elisabetta Carlini, Claudio Marchi. A model problem for Mean Field Games on networks. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 4173-4192. doi: 10.3934/dcds.2015.35.4173

[7]

Martin Burger, Marco Di Francesco, Peter A. Markowich, Marie-Therese Wolfram. Mean field games with nonlinear mobilities in pedestrian dynamics. Discrete and Continuous Dynamical Systems - B, 2014, 19 (5) : 1311-1333. doi: 10.3934/dcdsb.2014.19.1311

[8]

Adriano Festa, Diogo Gomes, Francisco J. Silva, Daniela Tonon. Preface: Mean field games: New trends and applications. Journal of Dynamics and Games, 2021, 8 (4) : i-ii. doi: 10.3934/jdg.2021025

[9]

Marco Cirant, Diogo A. Gomes, Edgard A. Pimentel, Héctor Sánchez-Morgado. On some singular mean-field games. Journal of Dynamics and Games, 2021, 8 (4) : 445-465. doi: 10.3934/jdg.2021006

[10]

Lucio Boccardo, Luigi Orsina. The duality method for mean field games systems. Communications on Pure and Applied Analysis, 2022, 21 (4) : 1343-1360. doi: 10.3934/cpaa.2022021

[11]

Zhilin Kang, Xingyi Li, Zhongfei Li. Mean-CVaR portfolio selection model with ambiguity in distribution and attitude. Journal of Industrial and Management Optimization, 2020, 16 (6) : 3065-3081. doi: 10.3934/jimo.2019094

[12]

I-Lin Wang, Shiou-Jie Lin. A network simplex algorithm for solving the minimum distribution cost problem. Journal of Industrial and Management Optimization, 2009, 5 (4) : 929-950. doi: 10.3934/jimo.2009.5.929

[13]

Kevin Ford. The distribution of totients. Electronic Research Announcements, 1998, 4: 27-34.

[14]

Ming Yan, Alex A. T. Bui, Jason Cong, Luminita A. Vese. General convergent expectation maximization (EM)-type algorithms for image reconstruction. Inverse Problems and Imaging, 2013, 7 (3) : 1007-1029. doi: 10.3934/ipi.2013.7.1007

[15]

Akram Aldroubi, Rocio Diaz Martin, Ivan Medri, Gustavo K. Rohde, Sumati Thareja. The Signed Cumulative Distribution Transform for 1-D signal analysis and classification. Foundations of Data Science, 2022, 4 (1) : 137-163. doi: 10.3934/fods.2022001

[16]

Martino Bardi. Explicit solutions of some linear-quadratic mean field games. Networks and Heterogeneous Media, 2012, 7 (2) : 243-261. doi: 10.3934/nhm.2012.7.243

[17]

Diogo A. Gomes, Gabriel E. Pires, Héctor Sánchez-Morgado. A-priori estimates for stationary mean-field games. Networks and Heterogeneous Media, 2012, 7 (2) : 303-314. doi: 10.3934/nhm.2012.7.303

[18]

Yves Achdou, Victor Perez. Iterative strategies for solving linearized discrete mean field games systems. Networks and Heterogeneous Media, 2012, 7 (2) : 197-217. doi: 10.3934/nhm.2012.7.197

[19]

Matt Barker. From mean field games to the best reply strategy in a stochastic framework. Journal of Dynamics and Games, 2019, 6 (4) : 291-314. doi: 10.3934/jdg.2019020

[20]

Olivier Guéant. New numerical methods for mean field games with quadratic costs. Networks and Heterogeneous Media, 2012, 7 (2) : 315-336. doi: 10.3934/nhm.2012.7.315

 Impact Factor: 

Metrics

  • PDF downloads (192)
  • HTML views (348)
  • Cited by (0)

[Back to Top]