Probabilistic graphical models for density estimation in high dimensional spaces: application of the Perturb & Combine principle with tree mixtures
Modèles Graphiques Probabilistes pour l'Estimation de Densité en grande dimension : applications du principe Perturb & Combine pour les mélanges d'arbres
Résumé
The dimensionality of current applications increases which makes the density estimation a difficult task. Indeed, the needed number of parameters to make estimation grows exponentially with respect to the dimension of the problem. Probabilistic graphical models can be used to solve this problem by providing a factorization of the joint distribution, but they suffer from a problem of scalability. The problem of high dimensional spaces is accentuated by the number of observations used to perform density estimation witch is not increased in the same proportions, and even remains extremely law in some applications. Factorization of the joint distribution is not sufficient to perform good density estimation with sparse data. The Perturb and Combine framework, first explored in classification, provide solutions for such problems. In this work, we explore and propose a generic algorithm for density estimation by applying the Perturb and Combine principle to a reduced family of simple probabilistic graphical models. These tree structures we proposed to use can be "manipulated" with at worst a quadratic complexity. Several variants of this algorithm are proposed by exploiting the Perturb and Combine principle according to two levels: perturbation of the tree generating procedure and perturbation of the learning dataset. Our initial approaches are conclusive regarding the quality of approximation, with a quadratic computational complexity, still insufficient in high dimensional spaces. Our second contribution concerns therefore a new application of the Perturb and Combine principle, which allows attending almost quasi-linear computational complexity, for the same quality of approximation.
Dans les applications actuelles, le nombre de variables continue d'augmenter, ce qui rend difficile l'estimation de densité. En effet, le nombre de paramètres nécessaire pour l'estimation croit exponentiellement par rapport à la dimension du problème. Les modèles graphiques probabilistes fournissent une aide non négligeable pour lutter contre ce problème en fournissant une factorisation de la loi jointe mais souffrent d'un problème de passage à l'échelle. Le problème de grande dimension s'accentue du fait que le nombre d'observations avec lequel on effectue l'estimation de densité n'augmente pas dans les mêmes proportions, et reste même extrêmement faible dans certains domaines d'applications. La factorisation de la loi jointe s'avère non suffisante pour effectuer une estimation de densité de qualité lorsqu'il y a très peu de données. Le principe du Perturb & Combine, initialement appliqué en classification, permet de lutter contre ce genre de problèmes. Dans le cadre de cette thèse, nous proposons un algorithme générique d'estimation de densité en appliquant le principe du Perturb et Combine à une famille de modèles graphiques probabilistes "simples" , les structures arborescentes "manipulables" avec une complexité au pire quadratique. Plusieurs variantes de cet algorithme sont proposées en exploitant à deux niveaux le principe de perturbation: perturbation de la génération des modèles simples et perturbation des données d'apprentissage. Les expérimentations effectuées lors de ce travail montrent que nos premières approches sont concluantes en ce qui concerne la qualité d'approximation, pour une complexité algorithmique quadratique encore insuffisante en grande dimension. Notre seconde contribution concerne donc une nouvelle application du principe de perturbation, permettant d'arriver à une complexité algorithmique proche du quasi-linéaire pour une même qualité d'approximation.
Loading...