Approximation efficace de mélanges bootstrap d’arbres de Markov pour l’estimation de densité

in Bougrain, Laurent (Ed.) Actes de la 14e Conférence Francophone sur l'Apprentissage Automatique (CAp 2012) (2012, May 23)

Nous considérons des algorithmes pour apprendre des Mélanges bootstrap d'Arbres de Markov pour l'estimation de densité. Pour les problèmes comportant un grand nombre de variables et peu d'observations ... [more ▼]

Nous considérons des algorithmes pour apprendre des Mélanges bootstrap d'Arbres de Markov pour l'estimation de densité. Pour les problèmes comportant un grand nombre de variables et peu d'observations, ces mélanges estiment généralement mieux la densité qu'un seul arbre appris au maximum de vraisemblance, mais sont plus coûteux à apprendre. C'est pourquoi nous étudions ici un algorithme pour apprendre ces modèles de manière approchée, afin d'accélérer l'apprentissage sans sacrifier la précision. Plus spécifiquement, nous récupérons lors du calcul d'un premier arbre de Markov les arcs qui constituent de bons candidats pour la structure, et ne considérons que ceux-ci lors de l'apprentissage des arbres suivants. Nous comparons cet algorithme à l'algorithme original de mélange, à un arbre appris au maximum de vraisemblance, à un arbre régularisé et à une autre méthode approchée. [less ▲]

Sub-quadratic Markov tree mixture learning based on randomizations of the Chow-Liu algorithm

in Myllymäki, Petri; Roos, Antoine; Jaakkola, Tommi (Eds.) Proceedings of the Fifth European Workshop on Probabilistic Graphical Models (PGM-2010) (2010, September)

The present work analyzes different randomized methods to learn Markov tree mixtures for density estimation in very high-dimensional discrete spaces (very large number n of discrete variables) when the ... [more ▼]

The present work analyzes different randomized methods to learn Markov tree mixtures for density estimation in very high-dimensional discrete spaces (very large number n of discrete variables) when the sample size (N ) is very small compared to n. Several sub- quadratic relaxations of the Chow-Liu algorithm are proposed, weakening its search proce- dure. We first study na¨ıve randomizations and then gradually increase the deterministic behavior of the algorithms by trying to focus on the most interesting edges, either by retaining the best edges between models, or by inferring promising relationships between variables. We compare these methods to totally random tree generation and randomiza- tion based on bootstrap-resampling (bagging), of respectively linear and quadratic com- plexity. Our results show that randomization becomes increasingly more interesting for smaller N/n ratios, and that methods based on simultaneously discovering and exploiting the problem structure are promising in this context. [less ▲]

Estimation de densité par ensemble aléatoire de poly-arbres

(2008)

La notion de mélange de modèles simples aléatoires est de plus en plus utilisée et avec succès dans la littérature de l’apprentissage supervisé ces dernières années. Parmi les avantages de ces méthodes ... [more ▼]

La notion de mélange de modèles simples aléatoires est de plus en plus utilisée et avec succès dans la littérature de l’apprentissage supervisé ces dernières années. Parmi les avantages de ces méthodes, citons l’amélioration du passage à l’échelle des algorithmes d’apprentissage grâce à leur aspect aléatoire et l’amélioration de l’exactitude de la prédiction des modèles induits grâce à une flexibilité plus élevée en ce qui concerne le compromis biais/variance. Dans le présent travail, nous proposons d’explorer cette idée dans le contexte de l’estimation de la densité. Nous proposons une nouvelle famille de méthodes d’apprentissage non-supervisé à base de mélange de grands ensembles aléatoires de poly-arbres. La caractéristique spécifique de ces méthodes est leur passage à l’échelle, aussi bien en terme de nombre de variables que de données à traiter. Cette étude, exploratoire, compare empiriquement ces méthodes sur un ensemble de problèmes de test discrets de taille et de complexité croissantes et ouvre de nombreuses perspectives auxquelles nous prévoyons de nous intéresser. [less ▲]