L’algorithme EM (Dempster et al., 1977) permet de construire une séquence d’estimateurs qui converge vers l’estimateur de vraisemblance maximale pour des modèles à données manquantes pour lesquels l’estimateur du maximum de vraisemblance n’est pas calculable. Cet algorithme est remarquable compte tenu de ses nombreuses applications en apprentissage statistique. Toutefois, il peut avoir un lourd coût computationnel. Les auteurs Cappé et Moulines (2009) ont proposé une version en ligne de cet algorithme pour les modèles appartenant à la famille exponentielle qui permet de faire des gains d’efficacité computationnelle importants en présence de grands jeux de données. Cependant, le calcul de l’espérance a posteriori de la statistique exhaustive, qui est nécessaire dans la version de Cappé et Moulines (2009), est rarement possible pour des modèles complexes et/ou lorsque la dimension des données manquantes est grande. On doit alors la remplacer par un estimateur. Plusieurs questions se présentent naturellement : les résultats de convergence de l’algorithme initial restent-ils valides lorsqu’on remplace l’espérance par un estimateur ? En particulier, que dire de la normalité asymptotique de la séquence des estimateurs ainsi créés, de la variance asymptotique et de la vitesse de convergence ? Comment la variance de l’estimateur de l’espérance se reflète-t-elle sur la variance asymptotique de l’estimateur EM? Peut-on travailler avec des estimateurs de type Monte-Carlo ou MCMC? Peut-on emprunter des outils populaires de réduction de variance comme les variables de contrôle ? Ces questions seront étudiées à l’aide d’exemples de modèles à variables latentes. Les contributions principales de ce mémoire sont une présentation unifiée des algorithmes EM d’approximation stochastique, une illustration de l’impact au niveau de la variance lorsque l’espérance a posteriori est estimée dans les algorithmes EM en ligne et l’introduction d’algorithmes EM en ligne permettant de réduire la variance supplémentaire occasionnée par l’estimation de l’espérance a posteriori.

Les méthodes de Monte Carlo par chaînes de Markov (MCMC) utilisent généralement des chaînes de Markov réversibles. Jusqu’à récemment, une grande partie de la recherche théorique sur les chaînes de Markov concernait ce type de chaînes, notamment les théorèmes de Peskun (1973) et de Tierney (1998) qui permettent d’ordonner les variances asymptotiques de deux estimateurs issus de chaînes réversibles différentes. Dans ce mémoire nous analysons des algorithmes simulants des chaînes qui ne respectent pas cette condition. Nous parlons alors de chaînes non réversibles. Expérimentalement, ces chaînes produisent souvent des estimateurs avec une variance asymptotique plus faible et/ou une convergence plus rapide. Nous présentons deux algorithmes, soit l’algorithme de marche aléatoire guidée (GRW) par Gustafson (1998) et l’algorithme de discrete bouncy particle sampler (DBPS) par Sherlock et Thiery (2017). Pour ces deux algorithmes, nous comparons expérimentalement la variance asymptotique d’un estimateur avec la variance asymptotique en utilisant l’algorithme de Metropolis-Hastings. Récemment, un cadre théorique a été introduit par Andrieu et Livingstone (2019) pour ordonner les variances asymptotiques d’une certaine classe de chaînes non réversibles. Nous présentons leur analyse de GRW. De plus, nous montrons que le DBPS est inclus dans ce cadre théorique. Nous démontrons que la variance asymptotique d’un estimateur peut théoriquement diminuer en ajoutant des propositions à cet algorithme. Finalement, nous proposons deux modifications au DBPS. Tout au long du mémoire, nous serons intéressés par des chaînes issues de propositions déterministes. Nous montrons comment construire l’algorithme du delayed rejection avec des fonctions déterministes et son équivalent dans le cadre de Andrieu et Livingstone (2019).