Auswahl der wissenschaftlichen Literatur zum Thema „Algorithmes d'apprentissage automatique“

International audience It is well known that traditional Hidden Markov Models (HMM) systems lead to a considerable improvement when more training data or more parameters are used. However, using more data with hybrid Hidden Markov Models and Artificial Neural Networks (HMM/ANN) models results in increased training times without improvements in performance. We developed in this work a new method based on automatically separating data into several sets and training several neural networks of Multi-Layer Perceptrons (MLP) type on each set. During the recognition phase, models are combined using several criteria (based on data fusion techniques) to provide the recognized word. We showed in this paper that this method significantly improved the recognition accuracy. This method was applied in an Arabic speech recognition system. This last is based on the one hand, on a fuzzy clustering (application of the fuzzy c-means algorithm) and of another share, on a segmentation at base of the genetic algorithms. De nombreuses expériences ont déjà montré qu'une forte amélioration du taux de reconnaissance des systèmes MMC (Modèles de Markov Cachés) traditionnels est observée lorsque plus de données d'apprentissage sont utilisées. En revanche, l'augmentation du nombre de données d'apprentissage pour les modèles hybrides MMC/RNA (Modèles de Markov cachés/Réseaux de Neurones Artificiels) s'accompagne d'une forte augmentation du temps nécessaire à l'apprentissage des modèles, mais pas ou peu des performances du système. Pour pallier cette limitation, nous rapportons dans ce papier les résultats obtenus avec une nouvelle méthode d'apprentissage basée sur la fusion de données. Cette méthode a été appliquée dans un système de reconnaissance de la parole arabe. Ce dernier est basé d'une part, sur une segmentation floue (application de l'algorithme c-moyennes floues) et d'une autre part, sur une segmentation à base des algorithmes génétiques.

Dans un premier temps, ce mémoire présente un théorème PAC-Bayes général, duquel il est possible d'obtenir simplement plusieurs bornes PAC-Bayes connues. Ces bornes permettent de calculer une garantie sur le risque d'un classificateur à partir de ses performances sur l'ensemble de données d'entraînement. Par l'interprétation du comportement de deux bornes PAC-Bayes, nous énonçons les caractéristiques propres aux classificateurs qu'elles favorisent. Enfin, une spécialisation de ces bornes à la famille des classificateurs linéaires est détaillée. Dans un deuxième temps, nous concevons trois nouveaux algorithmes d'apprentissage automatique basés sur la minimisation, par la méthode de descente de gradient conjugué, de l'expression mathématique de diverses formulations des bornes PAC-Bayes. Le dernier algorithme présenté utilise une fraction de l'ensemble d'entraînement pour l'acquisition de connaissances a priori. Ces algorithmes sont aptes à construire des classificateurs exprimés par vote de majorité ainsi que des classificateurs linéaires exprimés implicitement à l'aide de la stratégie du noyau. Finalement, une étude empirique élaborée compare les trois algorithmes entre eux et révèle que certaines versions de ces algorithmes construisent des classificateurs compétitifs avec ceux obtenus par AdaBoost et les SVM.
At first, this master thesis presents a general PAC-Bayes theorem, from which we can easily obtain some well-known PAC-Bayes bounds. Those bounds allow us to compute a guarantee on the risk of a classifier from its achievements on the training set. We analyze the behavior of two PAC-Bayes bounds and we determine peculiar characteristics of classifiers favoured by those bounds. Then, we present a specialization of those bounds to the linear classifiers family. Secondly, we conceive three new machine learning algorithms based on the minimization, by conjugate gradient descent, of various mathematical expressions of the PAC-Bayes bounds. The last algorithm uses a part of the training set to capture a priori knowledges. One can use those algorithms to construct majority vote classifiers as well as linear classifiers implicitly represented by the kernel trick. Finally, an elaborated empirical study compares the three algorithms and shows that some versions of those algorithms are competitive with both AdaBoost and SVM.
Inscrit au Tableau d'honneur de la Faculté des études supérieures

This thesis addresses text-independent speaker verification from a machine learning point of view. We use the machine learning framework to better define the problem and to develop new unbiased performance measures and statistical tests to compare objectively new approaches. We propose a new interpretation of the state-of-the-art Gaussian Mixture Model based system and show that they are discriminant and equivalent to a mixture of linear classifiers. A general framework for score normalization is also given for both probability and non-probability based models. With this new framework we better show the hypotheses made for the well known Z- and T- score normalization techniques. Several uses of discriminant models are then proposed. In particular, we develop a new sequence kernel for Support Vector Machines that generalizes an other sequence kernel found in the literature. If the latter is limited to a polynomial form the former allows the use of infinite space kernels such as Radial Basis Functions. A variant of this kernel that finds the best match for each frame of the sequence to be compared, actually outperforms the state-of-the-art systems. As our new sequence kernel is computationally costly for long sequences, a clustering technique is proposed for reducing the complexity. We also address in this thesis some problems specific to speaker verification such as the fact that the classes are highly unbalanced. And the use of a specific intra- and inter-class distance distribution is proposed by modifying the kernel in order to assume a Gaussian noise distribution over negative examples. Even if this approach misses some theoretical justification, it gives very good empirical results and opens a new research direction
Dans cette thèse le problème de la vérification du locuteur indépendante du texte est abordée du point de vue de l'apprentissage statistique (machine learning). Les théories développées en apprentissage statistique permettent de mieux définir ce problème, de développer de nouvelles mesures de performance non-biaisées et de proposer de nouveaux tests statistiques afin de comparer objectivement les modèles proposés. Une nouvelle interprétation des modèles de l'état de l'art basée sur des mixtures de gaussiennes (GMM) montre que ces modèles sont en fait discriminants et équivalents à une mixture d'experts linéaires. Un cadre théorique général pour la normalisation des scores est aussi proposé pour des modèles probabilistes et non-probabilistes. Grâce à ce nouveau cadre théorique, les hypothèses faites lors de l'utilisation de la normalisation Z et T (T- and Z-norm) sont mises en évidence. Différents modèles discriminants sont proposés. On présente un nouveau noyau utilisé par des machines à vecteurs de support (SVM) qui permet de traîter des séquences. Ce noyau est en fait la généralisation d'un noyau déjà existant qui présente l'inconvénient d'être limité à une forme polynomiale. La nouvelle approche proposée permet la projection des données dans un espace de dimension infinie, comme c'est le cas, par exemple, avec l'utilisation d'un noyau gaussien. Une variante de ce noyau cherchant le meilleur vecteur acoustique (frame) dans la séquence à comparer, améliore les résultats actuellement connus. Comme cette approche est particulièrement coûteuse pour les séquences longues, un algorithme de regroupement (clustering) est utilisé pour en réduire la complexité. Finalement, cette thèse aborde aussi des problèmes spécifiques de la vé-ri-fi-ca-tion du locuteur, comme le fait que les nombres d'exemples positifs et négatifs sont très déséquilibrés et que la distribution des distances intra et inter classes est spécifique de ce type de problème. Ainsi, le noyau est modifié en ajoutant un bruit gaussien sur chaque exemple négatif. Même si cette approche manque de justification théorique pour l'instant, elle produit de très bons résultats empiriques et ouvre des perspectives intéressantes pour de futures recherches

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.

La découverte de composés pharmaceutiques est actuellement trop longue et trop coûteuse, et le taux d’échec, trop élevé. Les bases de données biochimiques et génomiques ne cessent de grossir et il est maintenant impraticable d’interpréter ces données. Un changement radical est nécessaire ; certaines étapes de ce processus doivent être automatisées. Les peptides jouent un rôle important dans le système immunitaire et dans la signalisation cellulaire. Leurs propriétés favorables en font des candidats de choix pour initier la conception de nouveaux médicaments et assister la production de nouveaux vaccins. De plus, les techniques de synthèse modernes permettent de rapidement synthétiser ces molécules à faible coût. Les algorithmes d’apprentissage statistique sont particulièrement bien adaptés pour apprendre de façon automatisée des modèles, possiblement biochimiques, à partir des données existantes. Ces méthodes et les peptides offrent donc une solution de choix aux défis auxquels fait face la recherche pharmaceutique. Nous proposons un noyau permettant l’apprentissage de modèles statistiques de phénomènes biochimiques impliquant des peptides. Celui-ci permet, entre autres, l’apprentissage d’un modèle universel pouvant raisonnablement quantifier l’énergie de liaison entre toute séquence peptidique et tout site de liaison d’une protéine cristallisée. De plus, il unifie la théorie de plusieurs noyaux existants tout en conservant une faible complexité algorithmique. Ce noyau s’avère particulièrement adapté pour quantifier l’interaction entre les antigènes et les complexes majeurs d’histocompatibilité. Nous proposons un outil pour prédire les peptides qui survivront au processus de présentation antigénique. Cet outil a gagné une compétition internationale et aura plusieurs applications en immunologie, dont la conception de vaccins. Ultimement, un peptide doit maximiser l’interaction avec une protéine cible ou maximiser la bioactivité chez l’hôte. Nous formalisons ce problème comme un problème de prédiction de structures. Puis, nous proposons un algorithme exploitant les plus longs chemins dans un graphe pour déterminer les peptides maximisant la bioactivité prédite par un modèle préalablement appris. Nous validons cette nouvelle approche en laboratoire par la découverte de peptides antimicrobiens. Finalement, nous fournissons des garanties de performance de type PAC-Bayes pour deux algorithmes de prédiction de structure dont un est nouveau.
The discovery of pharmaceutical compounds is currently too time-consuming, too expensive, and the failure rate is too high. Biochemical and genomic databases continue to grow and it is now impracticable to interpret these data. A radical change is needed; some steps in this process must be automated. Peptides are molecules that play an important role in the immune system and in cell signaling. Their favorable properties make them prime candidates for initiating the design of new drugs and assist in the design of vaccines. In addition, modern synthesis techniques can quickly generate these molecules at low cost. Statistical learning algorithms are well suited to manage large amount of data and to learn models in an automated fashion. These methods and peptides thus offer a solution of choice to the challenges facing pharmaceutical research. We propose a kernel for learning statistical models of biochemical phenomena involving peptides. This allows, among other things, to learn a universal model that can reasonably quantify the binding energy between any peptide sequence and any binding site of a protein. In addition, it unifies the theory of many existing string kernels while maintaining a low computational complexity. This kernel is particularly suitable for quantifying the interaction between antigens and proteins of the major histocompatibility complex. We provide a tool to predict peptides that are likely to be processed by the antigen presentation pathway. This tool has won an international competition and has several applications in immunology, including vaccine design. Ultimately, a peptide should maximize the interaction with a target protein or maximize bioactivity in the host. We formalize this problem as a structured prediction problem. Then, we propose an algorithm exploiting the longest paths in a graph to identify peptides maximizing the predicted bioactivity of a previously learned model. We validate this new approach in the laboratory with the discovery of new antimicrobial peptides. Finally, we provide PAC-Bayes bound for two structured prediction algorithms, one of which is new.

Différentes disciplines des sciences humaines telles la philologie ou la paléographie font face à des tâches complexes et fastidieuses pour l'examen des sources de données. La proposition d'approches computationnelles en humanités permet d'adresser les problématiques rencontrées telles que la lecture, l'analyse et l'archivage de façon systématique. Les modèles conceptuels élaborés reposent sur des algorithmes et ces derniers donnent lieu à des implémentations informatiques qui automatisent ces tâches fastidieuses. La première partie de la thèse vise, d'une part, à établir la structuration thématique d'un corpus, en construisant des espaces sémantiques de grande dimension. D'autre part, elle vise au suivi dynamique des thématiques qui constitue un réel défi scientifique, notamment en raison du passage à l'échelle. La seconde partie de la thèse traite de manière holistique la page d'un document numérisé sans aucune intervention préalable. Le but est d'apprendre automatiquement des représentations du trait de l'écriture ou du tracé d'un certain script par rapport au tracé d'un autre script. Il faut dans ce cadre tenir compte de l'environnement où se trouve le tracé : image, artefact, bruits dus à la détérioration de la qualité du papier, etc. Notre approche propose un empilement de réseaux de neurones auto-encodeurs afin de fournir une représentation alternative des données reçues en entrée
Different disciplines in the humanities, such as philology or palaeography, face complex and time-consuming tasks whenever it comes to examining the data sources. The introduction of computational approaches in humanities makes it possible to address issues such as semantic analysis and systematic archiving. The conceptual models developed are based on algorithms that are later hard coded in order to automate these tedious tasks. In the first part of the thesis we propose a novel method to build a semantic space based on topics modeling. In the second part and in order to classify historical documents according to their script. We propose a novel representation learning method based on stacking convolutional auto-encoder. The goal is to automatically learn plot representations of the script or the written language

La problématique de ce travail repose sur la qualité de modélisation de données (appelées observations) faite par des chaines de Markov cachées (CMC). Notre objectif est alors de proposer des algorithmes permettant d'améliorer cette qualité. Le critère retenu pour quantifier la qualité de la modélisation est la probabilité que la CMC génère des observations données. La résolution de ce problème fait appel à des techniques d'hybridation. Les outils employés conjointement aux CMC dans ce travail sont les algorithmes génétiques. Nous les utilisons ici pour répondre à une double attente. Premièrement, ils vont nous permettre d'explorer l'espace de recherche des CMC en évitant les optima locaux. Deuxièmement, l'algorithme génétique gère une caractéristique importante des CMC : leur nombre d'états. Au final, l'algorithme hybride le plus évolué détermine seul la meilleure CMC par rapport à un problème donné. C'est à dire qu'il conçoit une architecture (nombre d'états) et détermine les transitions nécessaires entre ces états. Différentes applications ont été réalisées dans le cadre de ce travail dans le domaine de la reconnaissance d'images, de la prévision de séries temporelles, de la ségmentation d'images et du suivi d'objets dans une séquence d'images. Les nouveaux algorithmes proposés par ce travail sont applicables à n'importe quel domaine, sous les hypothèses nécessaires aux CMC. Ils permettent un apprentissage rapide des modèles, et une détermination entièrement automatique de l'architecture (nombre d'états et transitions autorisées) des CMC
The main point of this work is based on the quality of modelization of data (called observations) made by hidden Markov models (HMMs). Our goal is to propose algorithms that improve this quality. The criterion used to quantify the quality of HMM is the probability that a given model generates a given observation. To solve this problem, we use a genetic hybridization of HMM. Using genetic algorithms (GAs) jointly to HMM permits two things. First, GAs let us to explore more efficiently the set of models, avoiding local optima. Second, GAs optimize an important characteristic of HMM : its number of hidden states. The most efficient hybrid algorithm finds the best HMM for a given problem, by itself. This means that the GA designs a set of states and the associated transition probabilities. Many explications have been done in the framework of this thesis, in many domains like image recognition, time series prediction, unsupervised image segmentation and object tracking in sequences of images. The new algorithms proposed here are appliable to all domains (peovided that hypothesis related to HMM are satisfied). They allow a fast and efficient training of HMM, and an entirely automatic determination of the architecture (number of states, transition probabilities) of the HMM

Tableau d’honneur de la Faculté des études supérieures et postdoctorales, 2018-2019
La compréhension du lien entre les caractéristiques génomiques d’un individu, le génotype, et son état biologique, le phénotype, est un élément essentiel au développement d’une médecine personnalisée où les traitements sont adaptés à chacun. Elle permet notamment d’anticiper des maladies, d’estimer la réponse à des traitements et même d’identifier de nouvelles cibles pharmaceutiques. L’apprentissage automatique est une science visant à développer des algorithmes capables d’apprendre à partir d’exemples. Ces algorithmes peuvent être utilisés pour produire des modèles qui estiment des phénotypes à partir de génotypes, lesquels peuvent ensuite être étudiés pour élucider les mécanismes biologiques sous-jacents aux phénotypes. Toutefois, l’utilisation d’algorithmes d’apprentissage dans ce contexte pose d’importants défis algorithmiques et théoriques. La haute dimensionnalité des données génomiques et la petite taille des échantillons de données peuvent mener au surapprentissage; le volume des données requiert des algorithmes adaptés qui limitent leur utilisation des ressources computationnelles; et finalement, les modèles obtenus doivent pouvoir être interprétés par des experts du domaine, ce qui n’est pas toujours possible. Cette thèse présente des algorithmes d’apprentissage produisant des modèles interprétables pour la prédiction de phénotypes à partir de génotypes. En premier lieu, nous explorons la prédiction de phénotypes discrets à l’aide d’algorithmes à base de règles. Nous proposons de nouvelles implémentations hautement optimisées et des garanties de généralisation adaptées aux données génomiques. En second lieu, nous nous intéressons à un problème plus théorique, soit la régression par intervalles, et nous proposons deux nouveaux algorithmes d’apprentissage, dont un à base de règles. Finalement, nous montrons que ce type de régression peut être utilisé pour prédire des phénotypes continus et que ceci mène à des modèles plus précis que ceux des méthodes conventionnelles en présence de données censurées ou bruitées. Le thème applicatif de cette thèse est la prédiction de la résistance aux antibiotiques, un problème de santé publique d’envergure mondiale. Nous démontrons que nos algorithmes peuvent servir à prédire, de façon très précise, des phénotypes de résistance, tout en contribuant à en améliorer la compréhension. Ultimement, nos algorithmes pourront servir au développement d’outils permettant une meilleure utilisation des antibiotiques et un meilleur suivi épidémiologique, un élément clé de la solution à ce problème.
A thorough understanding of the relationship between the genomic characteristics of an individual (the genotype) and its biological state (the phenotype) is essential to personalized medicine, where treatments are tailored to each individual. This notably allows to anticipate diseases, estimate response to treatments, and even identify new pharmaceutical targets. Machine learning is a science that aims to develop algorithms that learn from examples. Such algorithms can be used to learn models that estimate phenotypes based on genotypes, which can then be studied to elucidate the biological mechanisms that underlie the phenotypes. Nonetheless, the application of machine learning in this context poses significant algorithmic and theoretical challenges. The high dimensionality of genomic data and the small size of data samples can lead to overfitting; the large volume of genomic data requires adapted algorithms that limit their use of computational resources; and importantly, the learned models must be interpretable by domain experts, which is not always possible. This thesis presents learning algorithms that produce interpretable models for the prediction of phenotypes based on genotypes. Firstly, we explore the prediction of discrete phenotypes using rule-based learning algorithms. We propose new implementations that are highly optimized and generalization guarantees that are adapted to genomic data. Secondly, we study a more theoretical problem, namely interval regression. We propose two new learning algorithms, one which is rule-based. Finally, we show that this type of regression can be used to predict continuous phenotypes and that this leads to models that are more accurate than those of conventional approaches in the presence of censored or noisy data. The overarching theme of this thesis is an application to the prediction of antibiotic resistance, a global public health problem of high significance. We demonstrate that our algorithms can be used to accurately predict resistance phenotypes and contribute to the improvement of their understanding. Ultimately, we expect that our algorithms will take part in the development of tools that will allow a better use of antibiotics and improved epidemiological surveillance, a key component of the solution to this problem.

Internet ainsi que tous les moyens numériques modernes disponibles pour communiquer, s'informer ou se divertir génèrent des données en quantités de plus en plus importantes. Dans des domaines aussi variés que la recherche d'information, la bio-informatique, la linguistique computationnelle ou la sécurité numérique, des méthodes automatiques capables d'organiser, classifier, ou transformer des téraoctets de données apportent une aide précieuse. L'apprentissage artificiel traite de la conception d'algorithmes qui permettent d'entraîner de tels outils à l'aide d'exemples d'apprentissage. Utiliser certaines de ces méthodes pour automatiser le traitement de problèmes complexes, en particulier quand les quantités de données en jeu sont insurmontables pour des opérateurs humains, paraît inévitable. Malheureusement, la plupart des algorithmes d'apprentissage actuels, bien qu'efficaces sur de petites bases de données, présentent une complexité importante qui les rend inutilisables sur de trop grandes masses de données. Ainsi, il existe un besoin certain dans la communauté de l'apprentissage artificiel pour des méthodes capables d'être entraînées sur des ensembles d'apprentissage de grande échelle, et pouvant ainsi gérer les quantités colossales d'informations générées quotidiennement. Nous développons ces enjeux et défis dans le Chapitre 1. Dans ce manuscrit, nous proposons des solutions pour réduire le temps d'entraînement et les besoins en mémoire d'algorithmes d'apprentissage sans pour autant dégrader leur précision. Nous nous intéressons en particulier aux Machines à Vecteurs Supports (SVMs), des méthodes populaires utilisées en général pour des tâches de classification automatique mais qui peuvent être adaptées à d'autres applications. Nous décrivons les SVMs en détail dans le Chapitre 2. Ensuite, dans le Chapitre 3, nous étudions le processus d'apprentissage par descente de gradient stochastique pour les SVMs linéaires. Cela nous amène à définir et étudier le nouvel algorithme, SGD-QN. Après cela, nous introduisons une nouvelle procédure d'apprentissage : le principe du “Process/Reprocess”. Nous déclinons alors trois algorithmes qui l'utilisent. Le Huller et LaSVM sont présentés dans le Chapitre 4. Ils servent à apprendre des SVMs destinés à traiter des problèmes de classification binaire (décision entre deux classes). Pour la tˆache plus complexe de prédiction de sorties structurées, nous modifions par la suite en profondeur l'algorithme LaSVM, ce qui conduit à l'algorithme LaRank présenté dans le Chapitre 5. Notre dernière contribution concerne le problème récent de l'apprentissage avec une supervision ambigüe pour lequel nous proposons un nouveau cadre théorique (et un algorithme associé) dans le Chapitre 6. Nous l'appliquons alors au problème de l'étiquetage sémantique du langage naturel. Tous les algorithmes introduits dans cette thèse atteignent les performances de l'état-de-l'art, en particulier en ce qui concerne les vitesses d'entraînement. La plupart d'entre eux ont été publiés dans des journaux ou actes de conférences internationaux. Des implantations efficaces de chaque méthode ont également été rendues disponibles. Dans la mesure du possible, nous décrivons nos nouveaux algorithmes de la manière la plus générale possible afin de faciliter leur application à des tâches nouvelles. Nous esquissons certaines d'entre elles dans le Chapitre 7.

Cette étude se divise en deux parties distinctes. Dans la première, nous nous intéressons aux motifs pour lesquels plus de 50 % des détenus québécois choisissent de renoncer à leur droit de participer à une audience en vue d’une libération conditionnelle éventuelle. Cette décision est examinée à travers des régressions multivariées et des algorithmes d'apprentissage automatique, révélant que la renonciation est fortement influencée par les caractéristiques individuelles des détenus, leur profil criminogène et la nature du crime commis. L’analyse montre également que les détenus qui renoncent à une audience auraient probablement été soumis à des conditions plus strictes s'ils avaient été libérés sous condition, comparativement à ceux effectivement libérés. La seconde partie de l'étude se concentre sur la récidive criminelle des individus ayant bénéficié d'une libération conditionnelle « à la marge », c’est-à-dire pour lesquels l’octroi de la libération était surtout déterminé par l’historique des décisions des commissaires devant lesquels ils devaient se présenter. Pour ces individus, la libération conditionnelle diminue significativement le taux de récidive de plus de 8 points de pourcentage dans les cinq années suivant leur libération. La libération conditionnelle permet de réduire à la fois le temps d'incarcération actuel et futur de ces individus, tout en diminuant la probabilité de récidive.