我有这个与内核svm有关的困惑 . 我读到内核svm，保留的支持向量的数量很大 . 这就是为什么难以训练并且耗时的原因 . 我没有得到这个部分为什么很难优化 . 好吧我可以说噪声数据需要大量的支持向量 . 但是它与训练时间有什么关系呢 .
此外，我正在阅读另一个article，他们试图将非线性SVM内核转换为线性SVM内核 . 在线性内核的情况下，它只是原始特征本身的点积 . 但在非线性的情况下，它是RBF和其他 . 我没有这样做 . 对于线性内核，它只是原始特征的点积 . 在RBF的情况下，它使用高斯核 . 所以我只需要计算一次，然后我就完成了操作和瓶颈思考的问题 .
Support Vector Machine (SVM) (Cortes and Vap- nik, 1995) as the state-of-the-art classification algo- rithm has been widely applied in various scientific do- mains. The use of kernels allows the input samples to be mapped to a Reproducing Kernel Hilbert S- pace (RKHS), which is crucial to solving linearly non- separable problems. While kernel SVMs deliver the state-of-the-art results, the need to manipulate the k- ernel matrix imposes significant computational bottle- neck, making it difficult to scale up on large data.
1 回答
这是因为核矩阵是一个矩阵，其大小为N行×N列，其中N是训练样本的数量 . 所以想象你有500,000个训练样本，那就意味着矩阵需要500,000 * 500,000 * 8字节（1.81太字节）的RAM . 这是巨大的，需要某种并行计算集群以任何合理的方式处理 . 更不用说计算每个元素所需的时间 . 例如，如果您的计算机需要1微秒来计算1个内核评估，那么计算整个内核矩阵需要69.4小时 . 相比之下，一个好的线性求解器可以在常规桌面工作站上的几分钟或一小时内处理这种大小的问题 . 这就是线性SVM首选的原因 .
要理解为什么它们如此快速，你必须退后一步，思考这些优化器的工作原理 . 在最高级别，您可以将它们视为搜索在所有训练样本上提供正确输出的函数 . 此外，大多数求解器是迭代的，因为它们对当前函数应该是最佳猜测，并且在每次迭代中，他们在训练数据上测试它并看它有多好 . 然后他们以某种方式更新功能以改进它 . 他们一直这样做，直到找到最好的功能 .
记住这一点，线性求解器如此快速的主要原因是因为它们所学习的功能只是固定大小的权重向量和训练样本之间的点积 . 因此，在优化的每次迭代中，它只需要计算当前权重向量和所有样本之间的点积 . 这需要O（N）时间，而且，无论您拥有多少训练样本，良好的求解器只需几次迭代即可收敛 . 因此，求解器的工作记忆只是存储单个权重向量和所有训练样本所需的内存 . 这意味着整个过程只需要O（N）个时间和O（N）个字节的RAM .
另一方面，非线性求解器正在学习的函数不仅仅是权重向量和训练样本之间的点积 . 在这种情况下，它是一个函数，它是测试样本和所有其他训练样本之间的一堆内核评估的总和 . 因此，在这种情况下，仅评估您正在学习的针对一个训练样本的功能需要O（N）时间 . 因此，针对所有训练样本评估它需要O（N ^ 2）时间 . 已经设计了各种巧妙的技巧来试图保持非线性功能紧凑以加快速度 . 但在某种意义上，所有这些都至少有一点启发式或近似，而良好的线性求解器找到了精确的解 . 这就是线性求解器普及的部分原因 .