Partition adaptative de l’espace dans un algorithme MCMC avec adaptation régionale

Abstract

La simulation de variables aléatoires provenant de lois multimodales par des méthodes MCMC présente des défis particuliers. Les algorithmes adaptatifs utilisés pour faire face à ces distributions cherchent à faire le bon compromis entre efficacité asymptotique et vitesse d'exécution. Nous proposons dans ce mémoire une amélioration d'un algorithme MCMC avec adaptation régionale (RAPT) de Craiu et al. (2009), qui consiste à ajouter à ce dernier une partition adaptative régularisée de l'espace échantillonnal. Précisément, la partition est déterminée en construisant un hyperplan perpendiculaire à la droite joignant les moyennes échantillonnales cumulées dans chaque région, et passant par le point équidistant des deux moyennes selon la distance de Mahalanobis. Le but de cet ajout est de conférer plus de robustesse par rapport à la partition initiale des régions, tout en ajoutant un coût computationnel minimal à la procédure.

Nous détaillons le fonctionnement de l'algorithme et de ses variantes, et situons celui-ci dans le cadre général des méthodes MCMC adaptatives, incluant une revue des principaux algorithmes avec adaptation régionale compétiteurs. L'ergodicité du processus généré par ce nouvel algorithme est démontrée à l'aide des conditions suffisantes d'ergodicité de Roberts et Rosenthal (2007).

Nous présentons des illustrations graphiques du processus d'adaptation de la partition. Puis, nous comparons les performances de notre algorithme à celles des algorithmes RAPT et RAPTOR à l'aide de nombreuses simulations inspirées de la littérature et dégageons les forces et faiblesses de ces trois options. En général, notre algorithme a offert des résultats comparables à ceux de ses compétiteurs et s'est avéré dans certains cas le meilleur choix, surtout lorsque l'on tient compte de l'effort computationnel requis.

Sampling from multimodal distributions using MCMC methods is an ongoing challenge. Most adaptive algorithms aim to find a good compromise between asymptotic efficiency and actual computation time. In this masters thesis, we propose an improvement to the regional adaptive(RAPT) MCMC algorithm of Craiu et al. (2009), that consists in adding a constrained adaptive partitionning of the sample space. Precisely, the adaptive partition is defined as the hyperplane that is orthogonal to the line joining the cumulative sample means in each region, and which passes through the equidistant point between those two means, according to the Mahalanobis distance. We thus obtain an algorithm that is robust to the choice of the initial partition, at a mimimal computational cost.

The workings of the algorithm and its variants are detailed and set in the general framework of adaptive MCMC. A review of some widely used regional adaptation algorithms is also included. The ergodicity of the generated sampler is proved using the sufficient ergodicity conditions of Roberts et Rosenthal (2007).

Graphical illustrations of the adaptive partitionning are presented. Our approach is then compared to the RAPT and RAPTOR algorithms through many examples inspired by MCMC litterature. Our new algorithm yields satisfactory results and is in some cases the best choice among those considered, especially when taking into account the computational effort.