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

一些用于 (SMO)方法可在John C.Platt的本文中找到: Fast Training of Support Vector Machines using Sequential Minimal Optimization . 还有一个SMO算法的Java实现,它是为研究和教育目的而开发的( SVM-JAVA ).

• 约束共轭梯度
• 内点法
• 活动集方法

但要知道,理解这些东西需要一些数学知识(拉格朗日乘数、卡鲁什库恩塔克条件等)。

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

显式算法不使用内核,但可以修改;然而,无论是在代码还是在运行时复杂性方面,它都会更加复杂。

在libsvm上查看liblinear和非线性SVM

以下论文“Pegasos:SVM的原始估计次梯度解算器”第11页顶部描述了Pegasos算法的内核。该算法可从 http://ttic.uchicago.edu/~nati/Publications/PegasosMPB.pdf

我想补充一点关于普拉特原创作品的答案。 Stanford Lecture Notes ,但所有公式的推导应在其他地方找到(例如。 this random notes I found on the Internet ).

如果可以偏离最初的实现,我可以向您推荐我自己的SMO算法变体。

class SVM:
  def __init__(self, kernel='linear', C=10000.0, max_iter=100000, degree=3, gamma=1):
    self.kernel = {'poly':lambda x,y: np.dot(x, y.T)**degree,
                   'rbf':lambda x,y:np.exp(-gamma*np.sum((y-x[:,np.newaxis])**2,axis=-1)),
                   'linear':lambda x,y: np.dot(x, y.T)}[kernel]
    self.C = C
    self.max_iter = max_iter

  def restrict_to_square(self, t, v0, u):
    t = (np.clip(v0 + t*u, 0, self.C) - v0)[1]/u[1]
    return (np.clip(v0 + t*u, 0, self.C) - v0)[0]/u[0]

  def fit(self, X, y):
    self.X = X.copy()
    self.y = y * 2 - 1
    self.lambdas = np.zeros_like(self.y, dtype=float)
    self.K = self.kernel(self.X, self.X) * self.y[:,np.newaxis] * self.y
    
    for _ in range(self.max_iter):
      for idxM in range(len(self.lambdas)):
        idxL = np.random.randint(0, len(self.lambdas))
        Q = self.K[[[idxM, idxM], [idxL, idxL]], [[idxM, idxL], [idxM, idxL]]]
        v0 = self.lambdas[[idxM, idxL]]
        k0 = 1 - np.sum(self.lambdas * self.K[[idxM, idxL]], axis=1)
        u = np.array([-self.y[idxL], self.y[idxM]])
        t_max = np.dot(k0, u) / (np.dot(np.dot(Q, u), u) + 1E-15)
        self.lambdas[[idxM, idxL]] = v0 + u * self.restrict_to_square(t_max, v0, u)
    
    idx, = np.nonzero(self.lambdas > 1E-15)
    self.b = np.sum((1.0-np.sum(self.K[idx]*self.lambdas, axis=1))*self.y[idx])/len(idx)
  
  def decision_function(self, X):
    return np.sum(self.kernel(X, self.X) * self.y * self.lambdas, axis=1) + self.b

在简单的情况下,它并不比sklearn.svm.SVC有多大价值,比较如下所示(我已经在上面发布了生成这些图像的代码) GitHub )

我使用了完全不同的方法来推导公式,您可能想检查一下 my preprint on ResearchGate