计算简单支持向量机的Lagrange多重算子

Question

首先,我是支持向量机的初学者,所以如果我以错误的方式解决这个问题,我很抱歉.我试图从头开始实现一个非常简单的SVM,它使用标识内核函数将线性可分离数据分类为两个类之一.作为我将使用的数据类型的示例,请考虑本文档中的下图:

使用点(1,0),(3,1)和(3,-1)作为支持向量,我们知道关于计算决策平面的情况如下(从同一文档截图):

在摆弄和重新排列时,我们分别给出拉格朗日乘数-3.5,0.75和0.75.

我理解这个代数是如何在纸上工作的,但是我不确定在实现时最好的方法.所以我的问题如下:在实践中如何计算SVM的拉格朗日乘数？是否有一个我遗漏的算法能够确定任意线性可分支持向量的这些值？我应该使用标准的数学库来解决线性方程式(我在java中实现SVM)？这样的数学库对大规模学习来说会慢吗？请注意,这是一个学习练习,所以我不只是在寻找一个现成的SVM库.

任何其他建议将不胜感激!

编辑1:LutzL提出了一个很好的观点,即问题的一半实际上是确定哪些点将被用作支持向量,因此为了这个问题的目的,假设它们已经被计算出来.

Answer 1

独立于核函数，系数的确定导致具有线性正性约束的二次优化问题。如果简单地测试所有边界组件，那么它的复杂性会非常大，因此您无法避免高级优化算法，例如屏障或信任区域方法。

还有一些启发式方法试图通过搜索靠近分离线的点集并消除最可能远离分离线的点来将优化问题保持在低维度。