A New Class of Stochastic EM Algorithms. Escaping Local Maxima and Handling Intractable Sampling

Autor: Stéphanie Allassonnière, Juliette Chevallier
Přispěvatelé: Centre de Recherche des Cordeliers (CRC (UMR_S_1138 / U1138)), École pratique des hautes études (EPHE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Sorbonne Université (SU)-Université de Paris (UP), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Modèles et algorithmes pour l’intelligence artificielle (MAASAI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Laboratoire Jean Alexandre Dieudonné (JAD), Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Scalable and Pervasive softwARe and Knowledge Systems (Laboratoire I3S - SPARKS), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS), Ce travail bénéficie d'un financement public Investissement d'avenir, réference ANR-11-LABX-0056-LMH. This work was supported by a public grant as part of the Investissement d'avenir, project reference ANR-11-LABX-0056-LMH., Ce travail a été soutenu en partie par le gouvernement français sous la direction de l'Agence Nationale de la Recherche, dans le cadre du programme 'Investissements d'avenir', référence ANR19-P3IA-0001 (Institut PRAIRIE 3IA). This work was supported in part the French government under management of Agence Nationale de la Recherche as part of the 'Investissements d’avenir' program, reference ANR19-P3IA-0001 (PRAIRIE 3IA Institute)., ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), ANR-11-LABX-0056,LMH,LabEx Mathématique Hadamard(2011), École Pratique des Hautes Études (EPHE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Sorbonne Université (SU)-Université Paris Cité (UPCité), Health data- and model- driven Knowledge Acquisition (HeKA), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche des Cordeliers (CRC (UMR_S_1138 / U1138)), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Sorbonne Université (SU)-Université Paris Cité (UPCité)-École Pratique des Hautes Études (EPHE), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Laboratoire Jean Alexandre Dieudonné (LJAD), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Scalable and Pervasive softwARe and Knowledge Systems (Laboratoire I3S - SPARKS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Sorbonne Université (SU)-Université Paris Cité (UPCité)-École pratique des hautes études (EPHE), Chevallier, Juliette, PaRis Artificial Intelligence Research InstitutE - - PRAIRIE2019 - ANR-19-P3IA-0001 - P3IA - VALID, Centres d'excellences - LabEx Mathématique Hadamard - - LMH2011 - ANR-11-LABX-0056 - LABX - VALID
Jazyk: angličtina
Rok vydání: 2021
Předmět:
Statistics and Probability
Computer science
Posterior probability
02 engineering and technology
Stochastic approximation
01 natural sciences
010104 statistics & probability
EM-like algorithm
[STAT.ML]Statistics [stat]/Machine Learning [stat.ML]
[MATH.MATH-ST]Mathematics [math]/Statistics [math.ST]
Convergence (routing)
stochastic approximation
0202 electrical engineering
electronic engineering
information engineering
tempered distribution
Limit (mathematics)
0101 mathematics
[MATH.MATH-ST] Mathematics [math]/Statistics [math.ST]
[STAT.ME] Statistics [stat]/Methodology [stat.ME]
[STAT.TH] Statistics [stat]/Statistics Theory [stat.TH]
Applied Mathematics
Sampling (statistics)
020206 networking & telecommunications
[STAT.TH]Statistics [stat]/Statistics Theory [stat.TH]
stochastic optimization
[INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation
[STAT.ML] Statistics [stat]/Machine Learning [stat.ML]
[STAT] Statistics [stat]
Statistics::Computation
Maxima and minima
[STAT]Statistics [stat]
Computational Mathematics
Computational Theory and Mathematics
theoretical convergence
Stochastic optimization
[INFO.INFO-MO] Computer Science [cs]/Modeling and Simulation
Maxima
Algorithm
[STAT.ME]Statistics [stat]/Methodology [stat.ME]
Zdroj: Computational Statistics and Data Analysis
Computational Statistics and Data Analysis, Elsevier, 2021, 159, pp.107159. ⟨10.1016/j.csda.2020.107159⟩
Computational Statistics and Data Analysis, 2021, 159, pp.107159. ⟨10.1016/j.csda.2020.107159⟩
ISSN: 0167-9473
DOI: 10.1016/j.csda.2020.107159⟩
Popis: International audience; The expectation-maximization (EM) algorithm is a powerful computational technique for maximum likelihood estimation in incomplete data models. When the expectation step cannot be performed in closed form, a stochastic approximation of EM (SAEM) can be used. The convergence of the SAEM toward critical points of the observed likelihood has been proved and its numerical efficiency has been demonstrated. However, sampling from the posterior distribution may be intractable or have a high computational cost. Moreover, despite appealing features, the limit position of this algorithm can strongly depend on its starting one. To cope with this two issues, we propose here a new stochastic approximation version of the EM in which we do not sample from the exact distribution in the expectation phase of the procedure. We first prove the convergence of this algorithm toward critical points of the observed likelihood. Then, we propose an instantiation of this general procedure to favor convergence toward global maxima. Experiments on synthetic and real data highlight the performance of this algorithm in comparison to the SAEM and the EM when feasible.
Databáze: OpenAIRE
Externí odkaz: