论文部分内容阅读
支持向量机(SVM)一直都是机器学习领域里的热点研究课题，在产业界也得到了广泛的应用。它建立在统计学习的VC维理论和结构风险最小理论的基础之上，泛化能力好，在很多任务中表现出优秀的性能。当遇到非线性问题的时候，我们常常训练一个kernel SVM分类器，它利用核技巧将原始低维空间映射到一个高维特征空间。虽然kernel SVM通常情况下能够取得比较好的分类结果，但是它的计算复杂度很高，尤其在处理大规模非线性数据集的时候更是如此。这是因为kernel SVM的复杂度依赖于产生的支持向量的数目，而支持向量的数目与训练集的大小大致成线性关系。另一方面，linear SVM效率比较高，但是在处理非线性数据的时候，往往得不到满意的分类结果。因而研究基于SVM的快速非线性分类算法对于将SVM应用于大规模数据上具有重要的意义。 本文提出了三种基于SVM的快速非线性分类算法，第四个工作将SVM的思想拓展到度量学习，使度量学习能够应用于大数据上。本文的主要研究内容与创新点可归纳如下: (1)我们提出了一种集成多个linear SVM的快速非线性分类方法。我们首先使用高斯混合模型对数据进行聚类，然后在每个聚类上训练一个linearSVM。我们使用一个产生式图模型将数据聚类和linear SVM的学习纳入到一个统一的框架下。同时，每个linear SVM不是分开学习的，我们将每个linearSVM的学习看作一个任务，然后使用多任务学习的方法同时学习所有的linearSVM。实验结果表明多任务学习能够有效地避免在单个任务学习时容易出现的过拟合现象。该算法的预测复杂度和linear SVM的数目成正比，而kernelSVM的复杂度和支持向量的数目成正比，所以该算法在测试时，速度比kernelSVM快很多。同时，我们将局部一致聚类引入到高斯混合模型的聚类过程中，从而在聚类的过程中，考虑局部流形结构，使得聚类效果更好。我们还将该算法推广到了半监督学习，从而同时使用有标签数据和无标签数据来估计高斯混合模型的参数，避免了高维数据下高斯混合模型协方差矩阵容易出现奇异的问题。 (2)我们提出了一种基于局部软分配编码的局部线性分类器。该算法将局部软分配编码融入到linear SVM的决策函数中，从而形成了局部线性分类器的决策函数。另外，它采用完全监督的方法同时学习编码所用的锚点(anchorpoints)与局部线性分类器。通过将锚点与分类器变量纳入到一个统一的优化问题中，不断优化锚点和分类器，从而学习出更优的分类器。该算法的测试复杂度与锚点的数目成正比，通常锚点的数目比支持向量的数目少很多，所以该算法在测试时比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进行加速，使之能够应用到大数据上。