Abstract :
[en] The rapid progress of data acquisition technologies, and in particular the improvements in measurement resolution, allows to observe a stochastic process through the simultaneous monitoring of thousands to millions of random variables. Multimedia, bioinformatics and industrial processes are a few domains where sets of variables of this size are increasingly encountered. Processing such a large quantity of observations can benefit from the use of automatic procedures, in order to create a predictive model or to obtain valuable information about the process.A widely used strategy to derive a model from observational data is the estimation of a multivariate probability density over the variables of the problem. Such a density can then be used to study the underlying stochastic phenomenon. When the number of variables to model is large, probabilistic graphical models can reduce the number of parameters necessary to encode a joint probability distribution by exploiting independence relationships between variables. However, when there are thousands of variables or more, the use of those models faces two problems. First, both learning these models from a set of observations and exploiting them is computationally problematic. Second, the number of recorded occurrences of the problem may be quite low with respect to the number of variables. This lack of observations might be a source of error when learning a model, because the model constructed may be influenced by the particular sampling of the realisations of the problem, and generalize badly on new, unseen realisations. This source of error is called the variance of the learning algorithm.Within this context, the problem considered in the present thesis is to study and improve the scaling of probabilistic graphical models on high-dimensional problems, in terms of the number of variables. The approach selected is to use mixtures of Markov trees. Markov trees are a class of probabilistic graphical models that are constrained in terms of the independence relationships they can encode. Therefore, they are limited in the probability distributions they can model, but both learning and answering queries with such a model is considered to be computationally tractable. A mixture or an ensemble model is a weighted average of models. Such a mixture can be constructed to reduce the variance of a learning algorithm. In particular, the present thesis explores the possibility to build mixtures of Markov trees by using the perturb and combine framework. This approach has been quite successful in some areas of machine learning, and consists in randomizing a learning algorithm and combining the outputs resulting from a repeated application of the randomized algorithm on a given learning set.There are three main parts in this thesis. In each part, algorithms are first developed and then tested on a set of problems. In the first one, I review existing algorithms for learning a single Markov tree and develop two new randomized algorithms for this task. In the second part, learning algorithms for mixtures of Markov trees are developed. Two different classes of algorithms are constructed. Algorithms of the first class construct a mixture of independent Markov trees. The best algorithm of this first class in terms of accuracy generates Markov trees by applying the Chow-Liu algorithm on bootstrap replicates of the original set of observations. Algorithms of the second class generate a sequence of trees, in the sense that each new Markov tree generated depends on previous models. These algorithms have been developed to approximate the best method of the first class, with the goal of reducing the computational complexity of learning without sacrificing accuracy. The third step of this thesis combines two types of mixtures of Markov trees: mixtures reducing the variance, and mixtures reducing the bias. The bias is another source of error, that originates from the inability of the learning algorithm to select, on average, the best possible model, e.g. because the class of models considered (here Markov trees) cannot encode the true model. In this third part, each tree of a bias-reducing mixture is replaced by a variance-reducing mixture of Markov trees. The objective is to reduce the variance of each term of the bias-reducing mixture, and hence of the bias-reducing mixture itself.Finally, the ideas developed in this thesis are applied to another class of probabilistic graphical models, called tree-structured conditional random fields. Those models encode a conditional probability distribution rather than a joint probability distribution. A meta-algorithm to learn a mixture of these models is proposed, with the goal of reducing the variance./Le progrès rapide des technologies d'acquisition de données, en particulier l'amélioration de la résolution, permet l'étude d'un système stochastique via l'observation simultanée de miliers voir millions de variables aléatoires. La bioinformatique, le multimédia ou les processus industriels sont quelques-uns des domaines où se rencontrent des problèmes de cet ordre de grandeur. Leur analyse peut être facilitée par des procédures automatiques, permettant l'obtention d'un modèle prédictif ou d'informations sur le système.Une stratégie répandue pour construire un modèle à partir de données observées est l'estimation d'une densité de probabilité multivariée sur les variables du problème. Celle-ci peut ensuite servir à l'étude du phénomène stochastique sous-jacent. Quand le nombre de variables est élevé, les modèles probabilistes graphiques permettent de réduire le nombre de paramètres nécessaires pour encoder une distribution de probabilité conjointe. Cependant, quand il y a des milliers de variables ou d'avantage, l'utilisation de ces modèles rencontre deux problèmes. Premièrement, tant leur apprentissage que leur utilisation posent des problèmes de complexité de calcul. Deuxièmement, le nombre d'observations du problème peut être faible par rapport au nombre de variables. Ce manque d'observations peut être source d'erreur lors de l'apprentissage : le modèle construit peut être influencé par l'échantillonnage des réalisations du problème, et mal se comporter sur de nouvelles réalisations. Cette source d'erreur est appelée la variance.Dans ce contexte, le problème considéré dans cette thèse est l'étude et l'amélioration du passage à l'échelle des modèles probabilistes graphiques pour un grand nombre de variables. L'approche choisie est l'utilisation des mélanges d'arbres de Markov. Les arbres de Markov sont une classe de modèles probabilistes graphiques fortement contraints en terme des relations d'indépendence qu'ils peuvent encoder. Ils sont donc limités dans les distributions de probabilité qu'ils peuvent modéliser, mais l'apprentissage et l'exploitation de ces modèles sont considérés comme faisables algorithmiquement. Un mélange ou un ensemble de modèles est une moyenne pondérée de modèles. Un mélange peut être construit pour réduire la variance d'un algorithme d'apprentissage. En particulier, la présente thèse explore la possibilité de construire des mélanges d'arbres de Markov selon la technique du perturb and combine. Cette approche a eu quelques succès dans certains domaines de l'apprentissage automatique. Elle consiste à rendre un algorithme en partie aléatoire, et à combiner plusieurs résultats obtenus en appliquant plusieurs fois cet algorithme aléatoire sur un ensemble de données fixé.Cette thèse comporte trois parties principales. Dans chacune, de nouveaux algorithmes sont développés et évalués empiriquement. Dans la première partie, je passe en revue les algorithmes de la littérature construisant un arbre de Markov, et puis j'en développe deux versions randomisées. Dans la seconde partie, des algorithmes pour apprendre un mélange d'arbres de Markov sont développés. Deux types d'algorithmes sont mis au point. Les algorithmes du premier type construisent un mélange d'arbres de Markov indépendants. Le meilleur algorithme de cette classe (en terme de précision) construit des arbres en appliquant l'algorithme de Chow-Liu sur des réplicats bootstrap de l'ensemble de données. Les algorithmes du second type construisent une séquences d'arbres, dans le sens où chaque nouvel arbre construit dépend des modèles précédemment obtenus. Ces algorithmes ont été développés pour approximer la meilleure méthode du premier type, dans le but de réduire le temps de calcul sans sacrifier la précision. La troisième partie de la thèse combine deux types de mélanges d'arbres de Markov : des mélanges réduisant la variance et des mélanges réduisant le biais. Le biais est une autre source d'erreur, causée par une incapacité de l'algorithme d'apprentissage à produire, en moyenne, le meilleur modèle, par exemple parce que la classe de modèles considérés (ici les arbres de Markov) ne peut encoder le vrai modèle. Dans cette troisième partie, chaque arbre d'un mélange réduisant le bias est remplacé par un mélange d'arbres de Markov réduisant la variance. Le but est de réduire la variance de chaque terme du mélange réduisant le biais, et donc la variance du mélange lui-même.Enfin, les idées développées dans cette thèse sont appliquées à une autre classe de modèles probabilistes graphiques, les champs de Markov conditionnels en forme d'arbre. Ces mélanges encodent une distribution de probabilité conditionnelle au lieu d'une distribution conjointe. Un méta-algorithme pour apprendre des mélanges de ces modèles est proposé, avec l'objectif d'une réduction de variance.
