大型数据集的内核方法

Question

由于两个实例之间的内积计算，基于内核的分类器通常需要O（n^3）个训练时间。为了加速训练，可以预先计算内积值并将其存储在二维数组中。但是，当没有。的例子非常大，比如说超过10万，这样做的内存不足。

那么对此有什么更好的想法？

Answer 1

相关向量机具有顺序训练模式，在这种模式下，您不需要将整个内核矩阵保留在内存中。你基本上可以一次计算一列，确定它是否显得相关，否则就把它扔掉。尽管如此，我自己也没有多少运气，而且RVM还有其他一些问题。高斯过程领域中最有可能有更好的解决方案。我并没有真正坐在那里，但我已经看到提及它的在线算法。

Answer 2

我不是一个数值分析师，但不是QR decomposition你需要做普通最小二乘线性回归也O（n^3）？

无论如何，你可能会想要搜索文献（因为这是相当新的东西）在线学习或你正在使用的算法的主动学习版本。总的想法是丢弃远离决策边界的数据，或者不把它们放在首位。危险在于你可能被锁定在一个糟糕的本地最大值，然后你的在线/主动算法将忽略可以帮助你脱身的数据。

Answer 3

对于支持向量机的现代实现，训练算法的缩放取决于许多因素，例如您正在使用的训练数据和内核的性质。 O（n^3）的缩放因子是分析结果，并且在预测SVM训练如何在现实世界情况下缩放时不是特别有用。例如，SVMLight使用的训练算法的经验估计将训练集大小的缩放比例设为approximately O(n^2)。

我建议你在kernel machines forum问这个问题。我认为你比Stack Overflow更可能得到更好的答案，Stack Overflow更像是一个通用编程站点。