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

点击翻译按钮获取中文摘要

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.