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

在计算机科学中，学习通常被定义为代理的能力(可以是算法、机器人、机器……)根据经验改进自己的行为。一般来说，人们可以说，机器学习的主要目标是设计算法，允许机器通过对经验数据的分析来修改他们的行为。设计了一种学习算法来识别复杂的模式，并基于数据或示例做出智能决策。重要的是要指出，给定所有可能的输入，所有可能的行为的集合太大，不能被观察到的训练样本的集合所覆盖。因此，学习者必须以这样一种方式“概括”它的观察，即使面对新的例子，它也会以很高的概率继续表现良好。有许多策略是为了设计能够很好地“推广”的算法；有些是简单的特别启发式的，有些是建立在所谓的学习理论之上的。本研究项目是基于第二种方法。**PAC-贝叶斯理论是一个框架，用于推导一些可用的最严格的泛化保证。这些保证是预测误差概率的上限。许多成熟的学习算法，如支持向量机(SVM)，可以在PAC-贝叶斯框架中得到证明：它们对应于寻找最小化PAC-贝叶斯界的预测器。核岭回归和Adaboost算法的正则化版本也可以被视为特定PAC-贝叶斯界的最小化。此外，最近也通过这种方式发现了新的分类算法。PAC-贝叶斯界限最初适用于分类，但在过去几年中，该理论已扩展到回归、结构化输出预测、密度估计和基于非独立同分布数据(非IID)的问题。这为新的PAC-贝叶斯界最小化算法家族开辟了道路。该建议的第一个目标是开发新的PAC-贝叶斯界限，特别是在更复杂的设置，如结构化输出设置或在非IID设置中，以便提供将在实际学习算法不能应用的情况下应用的新学习算法。*在这项提案中，这些新算法将特别为生物信息学应用而设计。例如，我们对蛋白质和配体之间的结合亲和力的预测感兴趣，这是基因组学、蛋白质组学和药理学中的核心问题。注意，如果有一个快速而准确的蛋白质-多肽结合能预测器(只使用序列信息)，我们可以使用这个预测器来寻找给定任何目标蛋白质的强结合多肽。在这个项目中，我们将利用我们在机器学习方面的强大专业知识，特别是在PAC-贝叶斯理论方面，从可用的数据中构建这样的绑定亲和力预测器。*此外，我们将使用核方法(已证明与PAC-贝叶斯方法兼容)。这些方法是利用相似性函数(称为核)来学习如何预测的学习算法。这是一种将一些关于预测任务的知识包含到算法中的方法。在我们的蛋白质-配体亲和力预测示例中，我们将不得不寻找编码蛋白质和/或配体的某些(物理化学)属性的核。已经有一些现有的内核被提议用于生物信息学应用；我们将使用它们，但我们也打算设计我们自己的内核。我们还打算以同样的方式开发学习算法，以解决与基因组学和蛋白质组学相关的其他大数据问题。

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.