基于随机投影的大规模非线性支持向量机的研究

Support Vector Machine (SVM) is a classic machine learning algorithm. It has both solid theoretical foundation and very good practical performance. Therefore, SVM is wildly used in many real-life classification and regression problems. While SVM is successfully used in many applications, a big challenge is the scalability of nonlinear SVM: How to efficiently train an accurate nonlinear SVM model on a large scale dataset (e.g, a dataset with billions of samples and millions of features)?. To address the scalability issue of nonlinear SVM, we propose to investigate this problem from the following three aspects: (1) We first propose to combine the advantages of Nystrom method and random projection to develop a new framework for large scale nonlinear SVM; Furthermore, we will deeply investigate the effect of random projection on both Nystrom method and nonlinear SVM; (2) We propose to design new column sampling methods to address the limitation of Subsampled Randomized Hadamard Transform which is data-independent sampling method; We propose to design new column sampling techniques that can fully exploit the data and therefore to improve the performance; (3) We propose to design new column combination methods to address the limitation of Sparse Embedding which is also a data-independent process; We propose to design new column combination techniques that can fully exploit the data and therefore to improve the performance. This proposal aims on addressing the scalability issues of nonlinear SVM on large scale data which has both important scientific and practical values.

支持向量机作为一种经典的机器学习方法，且其具有坚实的理论基础及非常好的实际使用效果，因此被广泛地应用到各种分类及回归问题上。然而，在支持向量机得到广泛应用的同时，一个巨大的挑战就是非线性支持向量机的扩展性：即如何在大规模数据集上（例如十亿样本百万特征的数据集上）快速训练得到准确的非线性支持向量机模型。本项目拟从以下三个方面深入研究该问题：(1) 结合Nystrom方法及随机投影的各自优点构建大规模非线性支持向量机模型；并深入分析随机投影对Nystrom方法及非线性支持向量机模型的影响。(2) 针对现有下采样随机阿达马变换的列采样机制与数据无关的缺陷，设计基于数据自身特点的的列采样机制，从而提高现有方法的效果；(3) 针对现有随机稀疏嵌入方法不考虑数据自身特点而进行随机的列组合机制的缺陷，设计更有效列线性组合机制。本项目旨在提高非线性支持向量机的扩展性，具有重要的科学意义及实用价值。

支持向量机作为一种经典的机器学习方法，且其具有坚实的理论基础及非常好的实际使用效果，因此被广泛地应用到各种分类及回归问题上。然而，在支持向量机在得到广泛应用的同时，一个巨大的挑战就是非线性支持向量机的扩展性：即如何在大规模数据集上快速训练得到准确的非线性支持向量机模型。针对这一问题，本项目在项目研究期间进行深入研究，并取得了预期结果。我们的研究结果包括: (1) 针对现有下采样随机阿达马变换(Subsampled Randomized Hadamard Transform)的缺陷，设计了更有效的列采样机制。我们通过理论分析下采样随机阿达马变换对于线性支持向量机结果的影响，设计三种不同非均匀采样的方法来进行列采样: (a) 重要性采样(importance sampling); (b) 对重要性进行排序, 选取最重要的列; (c)利用标签信息的监督式采样。我们的实验结果显示我们提出的方法比传统的下采样随机阿达马变化的效果要好； (2) 通过使用二值化特征嵌入(binary feature embedding)和三值化模型参数设计了一种内存消耗小，计算效率好的核支持向量机模型。我们设计了一种新的高效的方式对原始数据进行非线性二值化特征嵌入，该非线性二值化嵌入产生的特征表示可以用比特形式来表示，内存开销很小，之后我们在该二值化特征基础上建立线性分类模型。该线性分类模型的模型参数只可能是-1，0，1。通过非线性二值化特征嵌入及三值化线性模型参数，我们实现了内存开销小及计算高效的非线性支持向量机算法。(3)基于深度卷积神经网络与核支持向量机的关联，我们同时也研究了如果压缩现有深度卷积神经网络从而达到减少深度卷积神经网络模型在部署中的内存开销及进行高效预测。我们所开发的方法的原理是对深度卷积神经网络的每一个卷积层通过堆叠多个低维的二值化的卷积核来进行逼近。我们新设计的方法通过堆叠二值化的卷积核的操作能够克服二值化卷积神经网络的压缩率的上限为～32的缺陷。我们的实验方法显示我们的方法能够达到其它模型压缩方法接近的分类效果，同时在压缩率上有很大提升。