实现线性二进制SVM(支持向量机)

Question

我想在高维二进制数据(文本)的情况下实现一个简单的SVM分类器,我认为一个简单的线性SVM是最好的.自己实现它的原因基本上是我想学习它是如何工作的,所以使用库不是我想要的.

问题是,大多数教程都可以解决一个可以解决为"二次问题"的方程式,但它们从未显示出实际的算法!那么你能指出一个我可以学习的非常简单的实现,或者(更好)一个一直到实现细节的教程吗？

非常感谢!

Answer 1

用于序列最小优化(SMO)方法的一些伪代码可以在John C.Platt的本文中找到:使用顺序最小优化的支持向量机的快速训练.还有一个SMO算法的Java实现,它是为研究和教育目的而开发的(SVM-JAVA).

解决QP优化问题的其他常用方法包括:

• 约束共轭梯度
• 内点法
• 有效集方法

但请注意,需要一些数学知识来理解这些事物(拉格朗日乘数,Karush-Kuhn-Tucker条件等).

Answer 2

您是否对使用内核感兴趣？没有内核,解决这些优化问题的最佳方法是通过各种形式的随机梯度下降.http://ttic.uchicago.edu/~shai/papers/ShalevSiSr07.pdf中描述了一个很好的版本,它有一个明确的算法.

显式算法不适用于内核,但可以修改; 但是,在代码和运行时复杂性方面,它会更复杂.