L'ambition du présent mémoire est la présentation d'un ensemble de principes appelés la théorie PAC-Bayes. L'approche offre des garanties de type PAC aux algorithmes d'apprentissage bayésiens généralisés. Le mémoire traite essentiellement des cas où la distribution prior dépend des données. Le mémoire est divisé en trois chapitres. Le premier chapitre détaille les notions de base en apprentissage automatique. Il s'agit d'idées nécessaires à la bonne compréhension des deux chapitres subséquents. Le deuxième chapitre présente et discute de la théorie PAC-Bayes. Finalement, le troisième chapitre aborde l'idée d'une garantie PAC-Bayes où le prior dépend des données. Il y a deux contributions principales. La première contribution est une formulation analytique du risque empirique espéré pour les distributions elliptiques. La seconde contribution est une extension du travail de Parrado-Hernández et al. (34). En effet, il s'agit du développement d'une garantie PAC-Bayes avec un prior espérance non sphérique. / The ambition of this thesis is to present a set of principles called the PAC-Bayes theory. The approach provides PAC-like guarantees for generalised Bayesian learning algorithms. This thesis deals essentially with cases where the prior distribution is data dependent. The paper is divided into three chapters. The first chapter details the core concepts of machine learning. These are ideas that are necessary for a good understanding of the two subsequent chapters. The second chapter presents and discusses the PAC-Bayes theory. Finally, the third chapter addresses the idea of a PAC-Bayes guarantee where the prior depend on the data. There are two main contributions. The first contribution is an analytical formulation of the empirical expected risk for elliptical distributions. The second contribution is an extension of the work of Parrado-Hernández et al. (34). Indeed, it is the development of a PAC-Bayes guarantee with a non-spherical prior expectation.

L'ambition du présent mémoire est la présentation d'un ensemble de principes appelés la théorie PAC-Bayes. L'approche offre des garanties de type PAC aux algorithmes d'apprentissage bayésiens généralisés. Le mémoire traite essentiellement des cas où la distribution prior dépend des données. Le mémoire est divisé en trois chapitres. Le premier chapitre détaille les notions de base en apprentissage automatique. Il s'agit d'idées nécessaires à la bonne compréhension des deux chapitres subséquents. Le deuxième chapitre présente et discute de la théorie PAC-Bayes. Finalement, le troisième chapitre aborde l'idée d'une garantie PAC-Bayes où le prior dépend des données. Il y a deux contributions principales. La première contribution est une formulation analytique du risque empirique espéré pour les distributions elliptiques. La seconde contribution est une extension du travail de Parrado-Hernández et al. (34). En effet, il s'agit du développement d'une garantie PAC-Bayes avec un prior espérance non sphérique. / The ambition of this thesis is to present a set of principles called the PAC-Bayes theory. The approach provides PAC-like guarantees for generalised Bayesian learning algorithms. This thesis deals essentially with cases where the prior distribution is data dependent. The paper is divided into three chapters. The first chapter details the core concepts of machine learning. These are ideas that are necessary for a good understanding of the two subsequent chapters. The second chapter presents and discusses the PAC-Bayes theory. Finally, the third chapter addresses the idea of a PAC-Bayes guarantee where the prior depend on the data. There are two main contributions. The first contribution is an analytical formulation of the empirical expected risk for elliptical distributions. The second contribution is an extension of the work of Parrado-Hernández et al. (34). Indeed, it is the development of a PAC-Bayes guarantee with a non-spherical prior expectation.

Titre de l'écran-titre (visionné le 26 juin 2023) / En apprentissage automatique, des algorithmes sont utilisés pour apprendre des modèles mathématiques à partir de données recueillies afin de résoudre une tâche. Trouver une représentation appropriée pour décrire les données d'entrée est une étape essentielle pour obtenir un résultat favorable. Initialement, les données d'un problème spécifique étaient représentées par des attributs élaborés manuellement dans le cadre d'un processus long et ardu. Cette étape a été révolutionnée avec l'avènement de l'apprentissage de représentations, un ensemble de techniques permettant de construire automatiquement une représentation pour une tâche donnée. En pratique, les succès de l'apprentissage de représentations ont conduit à des percées remarquables dans divers domaines, notamment grâce aux méthodes d'apprentissage profond des dernières années. Cependant, ces réalisations empiriques manquent souvent d'analyse théorique solide pour fournir des garanties statistiques et une compréhension poussée. La théorie de l'apprentissage statistique, telle que la théorie PAC-Bayésienne, est un outil puissant pour étudier les algorithmes d'apprentissage automatique et les performances de généralisation des modèles. La théorie PAC-Bayésienne exprime des garanties de généralisation sur des prédicteurs qui sont construits comme une agrégation de plusieurs prédicteurs plus simples. Dans ce travail, nous nous concentrons sur l'utilisation de la théorie PAC-Bayésienne pour développer de nouvelles techniques d'apprentissage de représentations ayant des propriétés intéressantes. Tout d'abord, nous explorons l'apprentissage par noyau en nous appuyant sur la méthode des attributs aléatoires de Fourier interprétée comme un vote de majorité et analysée dans le cadre PAC-Bayésien. Nous proposons deux approches d'apprentissage : un algorithme d'alignement de noyaux et un apprentissage par mesure de similarité basée sur des points de repère. Ensuite, nous adaptons nos travaux d'apprentissage par noyau à un cadre non supervisé en utilisant des données non étiquetées avec des informations de similarité afin d'apprendre des représentations pertinentes. Finalement, nous analysons les réseaux de neurones profonds avec activation binaire en utilisant la théorie PAC-Bayésienne. Nous développons une approche pour apprendre de tels réseaux et nous obtenons des garanties de généralisation non triviales pour nos modèles. / In machine learning, algorithms are used to learn mathematical models from gathered data to solve a task. Finding a suitable representation to describe the input data is an essential step towards a favorable outcome. Originally, hand-crafted features were designed in a time-consuming process to represent data for a specific problem. This was revolutionized with the advent of representation learning, which is a set of techniques to automatically build a representation for a given task. The practical successes of representation learning led to remarkable breakthroughs in various domains, notably driven by deep learning methods in recent years. However, those empirical achievements often lack a sound theoretical analysis to provide statistical guarantees and in-depth insights. A powerful tool to study machine learning algorithms and the generalization performance of models is statistical learning theory, such as the PAC-Bayesian theory. PAC-Bayes express generalization guarantees on predictors that are built as an aggregation of multiple simpler predictors. In this work, we focus on leveraging the PAC-Bayesian theory to develop novel representation learning techniques with advantageous properties. First, we explore kernel learning by building upon the kernel random Fourier features method interpreted as a majority vote and analyzed in the PAC-Bayesian framework. We propose two learning approaches: a kernel alignment algorithm and a landmarks-based similarity measure learning. Then, we adapt our kernel learning work for an unsupervised setting using unlabeled data with similarity information to learn relevant representations. Finally, we analyze deep neural networks with binary activation using the PAC-Bayesian theory. We develop a framework to train such networks, and we obtain nonvacuous generalization bounds for our approach.

Bayesian inference is about recovering the full conditional posterior distribution of the parameters of a statistical model. This exercise, however, can be challenging to undertake if the model specification is not available a priori, as is typically the case. This thesis proposes a new framework to select the subset of regressors that are the relevant features that explain a target variable in linear regression models. We generalize Zellner's g-prior with a random matrix, and we present a likelihood-based search algorithm, which uses Bayesian tools to compute the posterior distribution of the model parameters over all possible models generated, based on the maximum a posteriori (MAP). We use Markov chain Monte Carlo (MCMC) methods to gather samples of the model parameters and specify all distributions underlying these model parameters. We then use these simulations to derive a posterior distribution for the model parameters by introducing a new parameter that allows us to control how the selection of variables is done. Using simulated datasets, we show that our algorithm yields a higher frequency of choosing the correct variables and has a higher predictive power relative to other widely used variable selection models such as adaptive Lasso, Bayesian adaptive Lasso, and relative to well-known machine learning algorithms. Taken together, this framework and its promising performance under various model environments highlight that simulation tools and Bayesian inference methods can be efficiently combined to deal with well-known problems that have long loomed the variable selection literature. / L'inférence bayésienne consiste à retrouver la distribution conditionnelle a posteriori complète des paramètres d'un modèle statistique. Cet exercice, cependant, peut être difficile à entreprendre si la spécification du modèle n'est pas disponible a priori, comme c'est généralement le cas. Cette thèse propose une nouvelle approche pour sélectionner le sous-ensemble de régresseurs qui sont les caractéristiques pertinentes qui expliquent une variable cible dans les modèles de régression linéaire. Nous généralisons le g-prior de Zellner avec une matrice aléatoire et nous présentons un algorithme de recherche basé sur la vraisemblance, qui utilise des outils bayésiens pour calculer la distribution a posteriori des paramètres du modèle sur tous les modèles possibles générés. La sélection du modèle se fera sur la base du maximum a posteriori (MAP). Nous utilisons les méthodes de Monte Carlo par chaînes de Markov pour échantillonner suivant les distributions a posteriori de ces paramètres du modèle. Nous utilisons ensuite ces simulations pour dériver une estimation a posteriori des paramètres du modèle en introduisant un autre paramètre qui nous permet de contrôler la manière dont la sélection de la variable est effectuée. À l'aide de données simulées, nous montrons que notre méthode donne une fréquence plus élevée de choix des variables importantes et a un pouvoir prédictif plus élevé par rapport à d'autres modèles de sélection de variables largement utilisés tels que le Lasso adaptatif, le Lasso adaptatif bayésien, et par rapport aux algorithmes d'apprentissage automatique bien connus. Pris ensemble, cette approche et ses performances prometteuses dans divers scénarios de données mettent en évidence le fait que les outils de simulation et les techniques d'inférence bayésienne puissent être efficacement combinés pour traiter des problèmes bien connus qui ont longtemps pesé sur la littérature de la sélection de variables (en particulier en grande dimension).

Les méthodes d'inférence causale sont utiles pour répondre à plusieurs questions de recherche dans différents domaines, notamment en épidémiologie. Les graphes acycliques orientés sont des outils importants pour l'inférence causale. Entre autres, ils peuvent être utilisés pour identifier les variables confondantes utilisées dans l'ajustement de modèles statistiques afin d'estimer sans biais l'effet d'un traitement. Ces graphes sont construits à partir des connaissances du domaine d'application. Pourtant, ces connaissances sont parfois insuffisantes pour supposer que le graphe construit est correct. Souvent, un chercheur peut proposer divers graphiques correspondants à une même problématique. Dans ce projet, on développe une alternative au modèle moyen bayésien traditionnel qui se base sur un ensemble de graphes proposés par un utilisateur. Pour sa mise en œuvre, on estime d'abord la vraisemblance des données sous les modèles impliqués par chacun des graphes afin de déterminer la probabilité a posteriori de chaque graphe. On identifie, pour chaque graphe, un ensemble de covariables d'ajustement suffisant pour éviter le biais de confusion et on estime l'effet causal à partir d'approches appropriées en ajustant pour ces covariables. Finalement, l'effet causal global est estimé comme une moyenne pondérée des estimations correspondantes à chacun des graphes. La performance de cette approche est étudiée à l'aide d'une étude de simulation où le mécanisme de génération des données est inspiré de l'étude Study of Osteoporotic Fractures (SOF). Différents scénarios sont présentés selon les liens considérés entre les variables. L'étude de simulation démontre une bonne performance générale de notre méthode par comparaison au modèle moyen bayésien traditionnel. L'application de cette approche est illustrée à l'aide de données de l'étude SOF dont l'objectif est l'estimation de l'effet de l'activité physique sur le risque de fractures de la hanche. / Causal inference methods are useful for answering several research questions in different fields, including epidemiology. Directed acyclic graphs are important tools for causal inference. Among other things, they can be used to identify confounding variables used in fitting statistical models to unbiasedly estimate the effect of a treatment. These graphs are built from the knowledge of the domain of application. However, this knowledge is sometimes insufficient to assume that the constructed graph is correct. Often, a researcher can propose various graphs corresponding to the same problem. In this project, we develop an alternative to the traditional Bayesian model averaging which is based on a set of graphs proposed by a user. For its implementation, we first estimate the likelihood of the data under the models implied by each graph to determine the posterior probability of each graph. A set of adjustment covariates sufficient to control for confounding bias is identified for each graph and the causal effect is estimated using appropriate approaches by adjusting for these covariates. Finally, the overall causal effect is estimated as a weighted average of the graph-specific estimates. The performance of this approach is studied using a simulation study in which the data generation mechanism is inspired by the Study of Osteoporotic Fractures (SOF). Different scenarios varying in their relationships between the variables are presented. The simulation study shows a good overall performance of our method compared to the traditional Bayesian model averaging. The application of this approach is illustrated using data from the SOF, whose objective is to estimate the effect of physical activity on the risk of hip fractures.

La science des réseaux est notamment à la recherche de modèles mathématiques capables de reproduire le comportement de systèmes complexes empiriques. Cependant, la représentation usuelle, le graphe, est parfois inadéquate étant donné sa limitation à encoder uniquement les relations par paires. De nombreux travaux récents suggèrent que l'utilisation de l'hypergraphe, une généralisation décrivant les interactions d'ordre supérieur (plus de deux composantes), permet d'expliquer des phénomènes auparavant incompris avec le graphe. Or, la structure de ces réseaux complexes est rarement ou difficilement observée directement. De fait, on mesure plutôt une quantité intermédiaire, comme la fréquence de chaque interaction, pour ensuite reconstruire la structure originale. Bien que de nombreuses méthodes de reconstruction de graphes aient été développées, peu d'approches permettent de retrouver les interactions d'ordre supérieur d'un système complexe. Dans ce mémoire, on développe une nouvelle approche de reconstruction pouvant déceler les interactions connectant trois noeuds parmi des observations dyadiques bruitées. Basée sur l'inférence bayésienne, cette méthode génère la distribution des hypergraphes les plus plausibles pour un jeu de données grâce à un algorithme de type Metropolis-Hastings-within-Gibbs, une méthode de Monte-Carlo par chaînes de Markov. En vue d'évaluer la pertinence d'un modèle d'interactions d'ordre supérieur pour des observations dyadiques, le modèle d'hypergraphe développé est comparé à un second modèle bayésien supposant que la structure sous-jacente est un graphe admettant deux types d'interactions par paires. Les résultats obtenus pour des hypergraphes synthétiques et empiriques indiquent que la corrélation intrinsèque à la projection d'interactions d'ordre supérieur améliore le processus de reconstruction lorsque les observations associées aux interactions dyadiques et triadiques sont semblables. / Network science is looking for mathematical models capable of reproducing the behavior of empirical complex systems. However, the usual representation, the graph, is sometimes inadequate given its limitation to encode only pairwise relationships. Many recent works suggest that the use of the hypergraph, a generalization describing higher-order interactions (more than two components), allows to explain phenomena previously not understood with graphs. However, the structure of these complex networks is seldom or hardly observed directly. Instead, we measure an intermediate quantity, such as the frequency of each interaction, and then reconstruct the original structure. Although many graph reconstruction methods have been developed, few approaches recover the higher-order interactions of a complex system. In this thesis, we develop a new reconstruction approach which detects interactions connecting three vertices among noisy dyadic observations. Based on Bayesian inference, this method generates the distribution of the most plausible hypergraphs for a dataset using a Metropolis-Hastings-within-Gibbs algorithm, a Markov chain Monte Carlo method. In order to evaluate the relevance of a higher-order interaction model for dyadic observations, the developed hypergraph model is compared to a second Bayesian model assuming that the underlying structure is a graph admitting two types of pairwise interactions. Results for synthetic and empirical hypergraphs indicate that the intrinsic correlation to the projection of higher-order interactions improves the reconstruction process when observations associated with dyadic and triadic interactions are similar.

L’apprentissage (machine) de modèle et l’estimation d’état sont cruciaux pour interpréter les phénomènes sous-jacents à de nombreuses applications du monde réel. Toutefois, il est souvent difficile d’apprendre le modèle d’un système et de capturer les états latents, efficacement et avec précision, en raison du fait que la connaissance du monde est généralement incertaine. Au cours des dernières années, les approches d’estimation et de modélisation bayésiennes ont été extensivement étudiées afin que l’incertain soit réduit élégamment et de manière flexible. Dans la pratique cependant, différentes limitations au niveau de la modélisation et de l’estimation bayésiennes peuvent détériorer le pouvoir d’interprétation bayésienne. Ainsi, la performance de l’estimation est souvent limitée lorsque le modèle de système manque de souplesse ou/et est partiellement inconnu. De même, la performance de la modélisation est souvent restreinte lorsque l’estimateur Bayésien est inefficace. Inspiré par ces faits, nous proposons d’étudier dans cette thèse, les connections possibles entre modélisation bayésienne (via le processus gaussien) et l’estimation bayésienne (via le filtre de Kalman et les méthodes de Monte Carlo) et comment on pourrait améliorer l’une en utilisant l’autre. À cet effet, nous avons d’abord vu de plus près comment utiliser les processus gaussiens pour l’estimation bayésienne. Dans ce contexte, nous avons utilisé le processus gaussien comme un prior non-paramétrique des modèles et nous avons montré comment cela permettait d’améliorer l’efficacité et la précision de l’estimation bayésienne. Ensuite, nous nous somme intéressé au fait de savoir comment utiliser l’estimation bayésienne pour le processus gaussien. Dans ce cadre, nous avons utilisé différentes estimations bayésiennes comme le filtre de Kalman et les filtres particulaires en vue d’améliorer l’inférence au niveau du processus gaussien. Ceci nous a aussi permis de capturer différentes propriétés au niveau des données d’entrée. Finalement, on s’est intéressé aux interactions dynamiques entre estimation bayésienne et processus gaussien. On s’est en particulier penché sur comment l’estimation bayésienne et le processus gaussien peuvent ”travailler” de manière interactive et complémentaire de façon à améliorer à la fois le modèle et l’estimation. L’efficacité de nos approches, qui contribuent à la fois au processus gaussien et à l’estimation bayésienne, est montrée au travers d’une analyse mathématique rigoureuse et validée au moyen de différentes expérimentations reflétant des applications réelles. / Model learning and state estimation are crucial to interpret the underlying phenomena in many real-world applications. However, it is often challenging to learn the system model and capture the latent states accurately and efficiently due to the fact that the knowledge of the world is highly uncertain. During the past years, Bayesian modeling and estimation approaches have been significantly investigated so that the uncertainty can be elegantly reduced in a flexible probabilistic manner. In practice, however, several drawbacks in both Bayesian modeling and estimation approaches deteriorate the power of Bayesian interpretation. On one hand, the estimation performance is often limited when the system model lacks in flexibility and/or is partially unknown. On the other hand, the modeling performance is often restricted when a Bayesian estimator is not efficient and/or accurate. Inspired by these facts, we propose Interactions Between Gaussian Processes and Bayesian Estimation where we investigate the novel connections between Bayesian model (Gaussian processes) and Bayesian estimator (Kalman filter and Monte Carlo methods) in different directions to address a number of potential difficulties in modeling and estimation tasks. Concretely, we first pay our attention to Gaussian Processes for Bayesian Estimation where a Gaussian process (GP) is used as an expressive nonparametric prior for system models to improve the accuracy and efficiency of Bayesian estimation. Then, we work on Bayesian Estimation for Gaussian Processes where a number of Bayesian estimation approaches, especially Kalman filter and particle filters, are used to speed up the inference efficiency of GP and also capture the distinct input-dependent data properties. Finally, we investigate Dynamical Interaction Between Gaussian Processes and Bayesian Estimation where GP modeling and Bayesian estimation work in a dynamically interactive manner so that GP learner and Bayesian estimator are positively complementary to improve the performance of both modeling and estimation. Through a number of mathematical analysis and experimental demonstrations, we show the effectiveness of our approaches which contribute to both GP and Bayesian estimation.

Tableau d'honneur de la Faculté des études supérieures et postdorales, 2014-2015 / L’apprentissage automatique correspond à la science de l’apprentissage à partir d’exemples. Des algorithmes basés sur cette approche sont aujourd’hui omniprésents. Bien qu’il y ait eu un progrès significatif, ce domaine présente des défis importants. Par exemple, simplement sélectionner la fonction qui correspond le mieux aux données observées n’offre aucune garantie statistiques sur les exemples qui n’ont pas encore été observées. Quelques théories sur l’apprentissage automatique offrent des façons d’aborder ce problème. Parmi ceux-ci, nous présentons la modélisation bayésienne de l’apprentissage automatique et l’approche PACbayésienne pour l’apprentissage automatique dans une vue unifiée pour mettre en évidence d’importantes similarités. Le résultat de cette analyse suggère que de considérer les réponses de l’ensemble des modèles plutôt qu’un seul correspond à un des éléments-clés pour obtenir une bonne performance de généralisation. Malheureusement, cette approche vient avec un coût de calcul élevé, et trouver de bonnes approximations est un sujet de recherche actif. Dans cette thèse, nous présentons une approche novatrice qui peut être appliquée avec un faible coût de calcul sur un large éventail de configurations d’apprentissage automatique. Pour atteindre cet objectif, nous appliquons la théorie de Bayes d’une manière différente de ce qui est conventionnellement fait pour l’apprentissage automatique. Spécifiquement, au lieu de chercher le vrai modèle à l’origine des données observées, nous cherchons le meilleur modèle selon une métrique donnée. Même si cette différence semble subtile, dans cette approche, nous ne faisons pas la supposition que le vrai modèle appartient à l’ensemble de modèles explorés. Par conséquent, nous disons que nous sommes agnostiques. Plusieurs expérimentations montrent un gain de généralisation significatif en utilisant cette approche d’ensemble de modèles durant la phase de validation croisée. De plus, cet algorithme est simple à programmer et n’ajoute pas un coût de calcul significatif à la recherche d’hyperparamètres conventionnels. Finalement, cet outil probabiliste peut également être utilisé comme un test statistique pour évaluer la qualité des algorithmes sur plusieurs ensembles de données d’apprentissage. / Machine learning is the science of learning from examples. Algorithms based on this approach are now ubiquitous. While there has been significant progress, this field presents important challenges. Namely, simply selecting the function that best fits the observed data was shown to have no statistical guarantee on the examples that have not yet been observed. There are a few learning theories that suggest how to address this problem. Among these, we present the Bayesian modeling of machine learning and the PAC-Bayesian approach to machine learning in a unified view to highlight important similarities. The outcome of this analysis suggests that model averaging is one of the key elements to obtain a good generalization performance. Specifically, one should perform predictions based on the outcome of every model instead of simply the one that best fits the observed data. Unfortunately, this approach comes with a high computational cost problem, and finding good approximations is the subject of active research. In this thesis, we present an innovative approach that can be applied with a low computational cost on a wide range of machine learning setups. In order to achieve this, we apply the Bayes’ theory in a different way than what is conventionally done for machine learning. Specifically, instead of searching for the true model at the origin of the observed data, we search for the best model according to a given metric. While the difference seems subtle, in this approach, we do not assume that the true model belongs to the set of explored model. Hence, we say that we are agnostic. An extensive experimental setup shows a significant generalization performance gain when using this model averaging approach during the cross-validation phase. Moreover, this simple algorithm does not add a significant computational cost to the conventional search of hyperparameters. Finally, this probabilistic tool can also be used as a statistical significance test to evaluate the quality of learning algorithms on multiple datasets.

Dans ce mémoire de maîtrise, nous présentons dans un premier temps un algorithme de l'état de l'art appelé Forêts aléatoires introduit par Léo Breiman. Cet algorithme effectue un vote de majorité uniforme d'arbres de décision construits en utilisant l'algorithme CART sans élagage. Par après, nous introduisons l'algorithme que nous avons nommé SORF. L'algorithme SORF s'inspire de l'approche PAC-Bayes, qui pour minimiser le risque du classificateur de Bayes, minimise le risque du classificateur de Gibbs avec un régularisateur. Le risque du classificateur de Gibbs constitue en effet, une fonction convexe bornant supérieurement le risque du classificateur de Bayes. Pour chercher la distribution qui pourrait être optimale, l'algorithme SORF se réduit à être un simple programme quadratique minimisant le risque quadratique de Gibbs pour chercher une distribution Q sur les classificateurs de base qui sont des arbres de la forêt. Les résultasts empiriques montrent que généralement SORF est presqu'aussi bien performant que les forêts aléatoires, et que dans certains cas, il peut même mieux performer que les forêts aléatoires. / In this master's thesis, we present at first an algorithm of the state of the art called Random Forests introduced by Léo Breiman. This algorithm construct a uniformly weighted majority vote of decision trees built using the CART algorithm without pruning. Thereafter, we introduce an algorithm that we called SORF. The SORF algorithm is based on the PAC-Bayes approach, which in order to minimize the risk of Bayes classifier, minimizes the risk of the Gibbs classifier with a regularizer. The risk of Gibbs classifier is indeed a convex function which is an upper bound of the risk of Bayes classifier. To find the distribution that would be optimal, the SORF algorithm is reduced to being a simple quadratic program minimizing the quadratic risk of Gibbs classifier to seek a distribution Q of base classifiers which are trees of the forest. Empirical results show that generally SORF is almost as efficient as Random forests, and in some cases, it can even outperform Random forests.

Tableau d’honneur de la Faculté des études supérieures et postdoctorales, 2010-2011 / L’objet principale de cette thèse est l’étude théorique et la conception d’algorithmes d’apprentissage concevant des classificateurs par vote de majorité. En particulier, nous présentons un théorème PAC-Bayes s’appliquant pour borner, entre autres, la variance de la perte de Gibbs (en plus de son espérance). Nous déduisons de ce théorème une borne du risque du vote de majorité plus serrée que la fameuse borne basée sur le risque de Gibbs. Nous présentons également un théorème permettant de borner le risque associé à des fonctions de perte générale. À partir de ce théorème, nous concevons des algorithmes d’apprentissage construisant des classificateurs par vote de majorité pondérés par une distribution minimisant une borne sur les risques associés aux fonctions de perte linéaire, quadratique, exponentielle, ainsi qu’à la fonction de perte du classificateur de Gibbs à piges multiples. Certains de ces algorithmes se comparent favorablement avec AdaBoost. / The main purpose of this thesis is the theoretical study and the design of learning algorithms returning majority-vote classifiers. In particular, we present a PAC-Bayes theorem allowing us to bound the variance of the Gibbs’ loss (not only its expectation). We deduce from this theorem a bound on the risk of a majority vote tighter than the famous bound based on the Gibbs’ risk. We also present a theorem that allows to bound the risk associated with general loss functions. From this theorem, we design learning algorithms building weighted majority vote classifiers minimizing a bound on the risk associated with the following loss functions : linear, quadratic and exponential. Also, we present algorithms based on the randomized majority vote. Some of these algorithms compare favorably with AdaBoost.