c++ - 用于大型/超大型数据集的支持 vector 机 (SVM)

Question

我想知道支持 vector 机 (SVM) 对于大型/超大型数据集(5-15M+ 行)具有非线性决策边界(例如高斯核)？

我知道两种特殊的方法:一方面，这个使用随机梯度下降等的调查: http://cseweb.ucsd.edu/~akmenon/ResearchExam.pdf

另一方面，有这些核心 vector 机/球 vector 机方法: http://www.c2i.ntu.edu.sg/ivor/cvm.html

在哪个页面上我们可能会找到两篇描述核心和球 vector 机的论文。

换句话说，我相信 SVM 对于手头的问题来说是非常合理的，但如果我使用标准 SVM 实现(可能高达 n^3 复杂度)，我会受到样本量的限制。我正在寻找一种“近似”实现，该实现相当准确，同时时间复杂度低于 n^2。最快的此类实现是什么？它们在经验上工作得很好还是在准确度上接近原始 SVM？

Answer 1

我曾经试过FaLK-SVM结果很有希望。该方法类似于核心 vector 机/球 vector 机，但使用 k 最近邻树(覆盖树)来分离数据。 link 上有一个 libSVM 实现. corresponding paper描述了核心和球方法，但指出 k-最近邻(只是为了分离!)更好。