支持向量机（SVM）一直都是机器学习领域里的热点研究课题，在产业界也得到了广泛的应用。它建立在统计学习的VC维理论和结构风险最小理论的基础之上，泛化能力好，在很多任务中表现出优秀的性能。当遇到非线性问题的时候，我们常常训练一个 kernel SVM 分类器，它利用核技巧将原始低维空间映射到一个高维特征空间。虽然 kernel SVM 通常情况下能够取得比较好的分类结果，但是它的计算复杂度很高，尤其在处理大规模非线性数据集的时候更是如此。这是因为 kernel SVM 的复杂度依赖于产生的支持向量的数目，而支持向量的数目与训练集的大小大致成线性关系。另一方面，linear SVM 效率比较高，但是在处理非线性数据的时候，往往得不到满意的分类结果。因而研究基于 SVM 的快速非线性分类算法对于将 SVM 应用于大规模数据上具有重要的意义。

本文提出了三种基于 SVM 的快速非线性分类算法，第四个工作将 SVM 的思想拓展到度量学习，使度量学习能够应用于大数据上。本文的主要研究内容与创新点可归纳如下：

（1） 我们提出了一种集成多个linear SVM的快速非线性分类方法。我们首先使用高斯混合模型对数据进行聚类，然后在每个聚类上训练一个linear SVM。我们使用一个产生式图模型将数据聚类和 linear SVM 的学习纳入到一个统一的框架下。同时，每个linear SVM 不是分开学习的，我们将每个linear SVM 的学习看作一个任务，然后使用多任务学习的方法同时学习所有的linear SVM。实验结果表明多任务学习能够有效地避免在单个任务学习时容易出现的过拟合现象。该算法的预测复杂度和linear SVM 的数目成正比，而kernel SVM的复杂度和支持向量的数目成正比，所以该算法在测试时，速度比kernel SVM 快很多。同时，我们将局部一致聚类引入到高斯混合模型的聚类过程中，从而在聚类的过程中，考虑局部流形结构，使得聚类效果更好。我们还将该算法推广到了半监督学习，从而同时使用有标签数据和无标签数据来估计高斯混合模型的参数，避免了高维数据下高斯混合模型协方差矩阵容易出现奇异的问题。

（2） 我们提出了一种基于局部软分配编码的局部线性分类器。该算法将局部软分配编码融入到 linear SVM 的决策函数中，从而形成了局部线性分类器的决策函数。另外，它采用完全监督的方法同时学习编码所用的锚点（anchor points）与局部线性分类器。通过将锚点与分类器变量纳入到一个统一的优化问题中，不断优化锚点和分类器，从而学习出更优的分类器。该算法的测试复杂度与锚点的数目成正比，通常锚点的数目比支持向量的数目少很多，所以该算法在测试时比kernel SVM 快很多。该算法的分类准确率和 kernel SVM 差不多。

（3） 在大数据上训练 kernel SVM，计算复杂度很高，而且需要大量内存。我们提出了一种通过识别间隔（margin）上的支持向量来高效训练 kernel SVM 的算法。它首先对训练数据无放回随机采样几次，每次只采样训练数据的一个子集，然后在每个子集上训练 kernel SVM，通过这些训练得到的 kernel SVM 分类器来识别 margin 上的支持向量。然后通过求解一个优化问题来估算与这些支持向量对应的拉格朗日乘子，这样就得到了决策函数，从而可以对未分类数据进行测试了。对于比较大的训练数据集来说，在训练数据的子集上多次训练 kernel SVM 比在整个训练集上训练 kernel SVM 快很多，所以此算法大大缩短了kernel SVM 在大数据集上的训练时间。而且该算法很容易做到并行化，从而训练速度可以进一步提升。

（4） 现有的度量学习方法通常涉及复杂的优化算法，很难应用到大数据上。我们提出了一种算法从排序学习的角度来进行度量学习，并根据 representer theorem 和上述 anchor points 的思想对该算法进行了加速，使之能够在大数据上进行度量学习。该算法与上述三个支持向量机加速算法之间的联系是该算法所使用的损失函数是排序的 hinge loss，相当于把支持向量机的思想扩展到了度量学习。另一个共同点是，该算法使用了 representer theorem 和上述 anchor points 的思想进行了加速，从而可以应用到大数据上，前面三个算法的核心思想也是对 SVM 进行加速，使之能够应用到大数据上。