Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Université Laval

$46,000.00

A PAC-Bayesian Analysis of Machine Learning and its Applications to Bioinformatics

EF 2019-20

Résumé
In Computer Science, learning is often defined as the ability of an agent (which can be an algorithm, a robot, a machine...) to improve its behavior based on experience. Generally speaking, one can say that Machine Learning's main goal is the design of algorithms that allow machines to modify their behavior from the analysis of empirical data. A learning algorithm is designed to recognize complex patterns and make intelligent decisions based on data, or examples. It is important to point out that the set of all possible behaviors, given all possible inputs, is too large to be covered by the set of observed training examples. Hence the learner must ""generalize"" its observations, in such a way that, with high probability, it will continue to perform well, even when confronted with new examples. Many strategies exist in order to design algorithms that will ""generalize"" well; some are simple ad hoc heuristic, some are founded on what is called Learning Theory. This research project is based on the second approach. **PAC-Bayesian theory is a framework for deriving some of the tightest generalization guarantees available. These guarantees are upper bounds on the probability of error of prediction. Many well established learning algorithms, such as the Support Vector Machine (SVM), can be justified in the PAC-Bayesian framework: they correspond to finding the predictor that minimizes a PAC-Bayesian bound. The kernel Ridge Regression and a regularized version of the Adaboost algorithm can also be viewed as minimizers of particular PAC-Bayesian bounds. Moreover, recently, new classification algorithms also have been discovered that way. PAC-Bayesian bounds were originally applicable to classification, but over the last few years the theory has been extended to regression, structured output prediction, density estimation, and problems based on data that are not independent and identically distributed (non-iid). This opens the way to new families of PAC-Bayesian bound minimization types of algorithms. The first objective of this proposal is to develop new PAC-Bayesian bounds, particularly in more complex setting, like the structured output setting or in the non-iid setting, in order to provide new learning algorithms that will apply in situations actual learning algorithms do not. *In this proposal, those new algorithms will be particularly designed for Bioinformatics applications. As example, we are interested in the prediction of binding affinities between proteins and ligands, a problem of central importance in genomics, proteomics and pharmacology. Note that, if a fast and accurate protein-peptide binding energy predictor (that uses only sequence information) was available, we could use that predictor to find a strong binding peptide given any target protein. In this project, we will make use of our strong expertise in Machine Learning, notably in PAC-Bayesian theory, to, among other things, construct such binding affinity predictors from the available data. *Moreover, we will use kernel methods (proven to be compatible with the PAC-Bayesian approach). These methods are learning algorithms that make use of similarity functions (called kernel) to learn how to predict. It is a way to include some knowledge about the prediction task into the algorithm. In our protein-ligand affinity prediction example, we will have to look for kernels that encode some (physicochemical) properties of the protein and/or the ligand. There are already some existing kernels that were proposed for Bioinformatics applications; we will use them, but we also intend to design our own. We also intend to develop in the same way learning algorithms that tackle other Big Data problems related to genomics and proteomics.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2014-03991
Name nom
Laviolette, François
Department département
Informatique et de génie logiciel
Organization id
51
Institution établissement
Université Laval
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2019
Competition year année de concours
2014
Award amount
46000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1201
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Life sciences (including biotechnology)
Area of application fr
Sciences de la vie (y compris biotechnologie)
Research subject code
2805
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Learning and inference theories
Research subject fr
Théories de l'apprentissage et l'inférence
Installment
inst:6 - 6
Partie
6
Nb partie
6
Application title
A PAC-Bayesian Analysis of Machine Learning and its Applications to Bioinformatics
Keyword
NSERC
Application summary
In Computer Science, learning is often defined as the ability of an agent (which can be an algorithm, a robot, a machine...) to improve its behavior based on experience. Generally speaking, one can say that Machine Learning's main goal is the design of algorithms that allow machines to modify their behavior from the analysis of empirical data. A learning algorithm is designed to recognize complex patterns and make intelligent decisions based on data, or examples. It is important to point out that the set of all possible behaviors, given all possible inputs, is too large to be covered by the set of observed training examples. Hence the learner must ""generalize"" its observations, in such a way that, with high probability, it will continue to perform well, even when confronted with new examples. Many strategies exist in order to design algorithms that will ""generalize"" well; some are simple ad hoc heuristic, some are founded on what is called Learning Theory. This research project is based on the second approach. **PAC-Bayesian theory is a framework for deriving some of the tightest generalization guarantees available. These guarantees are upper bounds on the probability of error of prediction. Many well established learning algorithms, such as the Support Vector Machine (SVM), can be justified in the PAC-Bayesian framework: they correspond to finding the predictor that minimizes a PAC-Bayesian bound. The kernel Ridge Regression and a regularized version of the Adaboost algorithm can also be viewed as minimizers of particular PAC-Bayesian bounds. Moreover, recently, new classification algorithms also have been discovered that way. PAC-Bayesian bounds were originally applicable to classification, but over the last few years the theory has been extended to regression, structured output prediction, density estimation, and problems based on data that are not independent and identically distributed (non-iid). This opens the way to new families of PAC-Bayesian bound minimization types of algorithms. The first objective of this proposal is to develop new PAC-Bayesian bounds, particularly in more complex setting, like the structured output setting or in the non-iid setting, in order to provide new learning algorithms that will apply in situations actual learning algorithms do not. *In this proposal, those new algorithms will be particularly designed for Bioinformatics applications. As example, we are interested in the prediction of binding affinities between proteins and ligands, a problem of central importance in genomics, proteomics and pharmacology. Note that, if a fast and accurate protein-peptide binding energy predictor (that uses only sequence information) was available, we could use that predictor to find a strong binding peptide given any target protein. In this project, we will make use of our strong expertise in Machine Learning, notably in PAC-Bayesian theory, to, among other things, construct such binding affinity predictors from the available data. *Moreover, we will use kernel methods (proven to be compatible with the PAC-Bayesian approach). These methods are learning algorithms that make use of similarity functions (called kernel) to learn how to predict. It is a way to include some knowledge about the prediction task into the algorithm. In our protein-ligand affinity prediction example, we will have to look for kernels that encode some (physicochemical) properties of the protein and/or the ligand. There are already some existing kernels that were proposed for Bioinformatics applications; we will use them, but we also intend to design our own. We also intend to develop in the same way learning algorithms that tackle other Big Data problems related to genomics and proteomics.