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

在计算机科学中，学习通常被定义为代理的能力（可以是算法，机器人，机器......）根据经验来改进它的行为。一般来说，可以说机器学习的主要目标是设计算法，允许机器通过分析经验数据来修改其行为。学习算法旨在识别复杂的模式，并根据数据或示例做出智能决策。重要的是要指出，给定所有可能的输入，所有可能的行为集太大，无法被观察到的训练示例集覆盖。因此，学习者必须“概括”其观察结果，以这样一种方式，即使面对新的例子，它也很可能继续表现良好。存在许多策略，以设计算法，将“泛化”好;一些是简单的特设启发式，一些是建立在什么是所谓的学习理论。本研究项目基于第二种方法。PAC-Bayesian理论是一个框架，用于导出一些最严格的泛化保证。这些保证是预测误差概率的上限。许多成熟的学习算法，如支持向量机（SVM），可以在PAC-Bayesian框架中得到证明：它们对应于找到最小化PAC-Bayesian边界的预测器。核岭回归和Adaboost算法的正则化版本也可以被视为特定PAC-贝叶斯边界的最小化。此外，最近还发现了新的分类算法。PAC-Bayesian边界最初适用于分类，但在过去几年中，该理论已扩展到回归，结构化输出预测，密度估计以及基于非独立和同分布（非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.