arrays - 大规模数据集的核方法

Question

由于两个实例之间的内积计算，基于内核的分类器通常需要 O(n^3) 的训练时间。为了加快训练速度，可以预先计算内积值并将其存储在二维数组中。然而当没有。的实例非常大，例如超过 100,000，将没有足够的内存来执行此操作。

那么有什么更好的主意吗？

Answer 1

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

我建议你在内核机器论坛上问这个问题。我认为你更有可能得到比 Stack Overflow 更好的答案，后者更像是一个通用编程网站。

Answer 2

相关向量机具有顺序训练模式，您无需将整个内核矩阵保存在内存中。您基本上可以一次计算一列，确定它是否相关，否则将其丢弃。不过，我自己的运气并不好，而且 RVM 还有一些其他问题。在高斯过程领域很可能有更好的解决方案。我并没有真正坐下来，但我已经看到有人提到它的在线算法。

Answer 3

我不是数值分析师，但是你需要做普通最小二乘线性回归的QR 分解不是也是 O(n^3) 吗？

无论如何，您可能想要搜索文献（因为这是相当新的东西）以查找您正在使用的算法的在线学习或主动学习版本。一般的想法是要么丢弃远离决策边界的数据，要么首先不包括它们。危险在于您可能会被锁定在一个糟糕的局部最大值中，然后您的在线/主动算法将忽略可以帮助您退出的数据。