机器学习算法的margin理论

From computational biology to search engine problems, machine learning algorithms have emerged as the dominant and ubiquitous tool in computer science. Statistical learning theory can not only provide insights to the performance of existing learning algorithms, but also help design new or improved algorithms. From neural networks to support vector machines (SVM) and boosting, the margin theory plays a key role in the design and the analysis of these algorithms. This project aims at the study of margin theory from the three aspects: (1) Generalization bound for boosting based on the margin distribution, (2) PAC-Bayesian margin bound for linear classifiers like SVM, (3) the effects of margin on the label complexity for active learning algorithms. The main clue of this project is the margin theory, which is applied to several learning algorithms and is corroborated through extensive experiments. Our goal is to seek ground breakthroughs and innovative ideas in statistical learning theory.

从计算生物学到搜索引擎，机器学习算法已经成为计算机科学中占据主导地位、并且无处不在的强大工具。统计学习理论不但能对现有学习算法的性质提供理论分析，也能用于推导新的或者改进的学习算法。从神经网络、支撑向量机(SVM)到boosting，margin理论都起到了关键性的作用。因此本项目拟从如下三个方面，对margin理论进行深入研究：(1) 基于margin分布的boosting泛化界，(2) PAC-贝叶斯框架下线性分类器（如SVM）的margin界，(3) 主动学习算法中margin对标签复杂度的作用。本项目将以margin理论为研究主线，紧密联系多种学习算法，并通过实验来验证理论的正确性，力争在统计学习理论方面取得突破与创新。

Margin理论在机器学习中占据了重要地位，例如神经网络、支撑向量机SVM、和boosting都需要利用margin理论来给予解释。该项目的主要研究内容是：（1）基于margin分布的boosting泛化界；（2）PAC-贝叶斯框架下的线性分类器如SVM的margin上界；（3）主动学习算法中margin对标签复杂度的作用。根据研究学术前沿动态变化，我们对研究内容做了适当调整，取得重要结果如下：（1）在SVM的margin上界方面，我们提出了基于欧拉弹性杆的几何正则项，给出了求解算法，并理论证明了该算法的Bayes统计相合性。（2）在流形学习上，我们提出了保持局部正交性的对齐方法LOPA。（3）在疾病诊断和基因关联检验的应用方面，我们利用以margin为基础的机器学习算法，得到了较好的实验结果。