5.1支持向量的引入

对于一个分类问题，我们如果可以找到一个向量五、支持向量机SVM - 图1，使得对于数据集D中的任何样本x，如果x是正例(用+1表示)就有五、支持向量机SVM - 图2，如果x是反例(用-1表示)就有五、支持向量机SVM - 图3，那么我们就可以很好地对数据集进行分类，判断依据就是五、支持向量机SVM - 图4
我们也可以这样来考虑，将数据集D中的每个样本x投射到d维的空间上，如果我们可以找到一个d维空间里的超平面(hyperplane)五、支持向量机SVM - 图5将这个空间划分成两个部分，其中一个部分里的样本x全是正例，另一个空间里的样本x全是反例，那么这个数据集的分类问题就解决了，但是实际情况并不会这么好，对于d维空间里的点x，其到超平面的距离可以表示为：

五、支持向量机SVM - 图6

又为了能正确地进行分类，对于训练集中的数据，需要有：

五、支持向量机SVM - 图7

并且存在一些样本使得上面的等号成立，我们就称这些使得等号取到的点称为支持向量(support machine)，每个支持向量到超平面的距离是：

五、支持向量机SVM - 图8

则超平面两侧的两个支持向量到超平面的距离之和就是：

五、支持向量机SVM - 图9

这个量也被称为间隔(margin)，为了使得分类效果尽可能地好，我们应该让这个间隔尽可能地大，因此我们的目标可以转化为求五、支持向量机SVM - 图10的最小值，即

五、支持向量机SVM - 图11%5Cge%201%0A%5Cend%7Baligned%7D#card=math&code=%5Cbegin%7Baligned%7D%0A%26%20%5Cmin_%7B%5Comega%2Cb%7D%5Cfrac%7B1%7D%7B2%7D%7C%7C%5Comega%7C%7C%5E2%5C%5C%0A%26%20s.t.%20y_i%28%5Comega%5ETx_i%2Bb%29%5Cge%201%0A%5Cend%7Baligned%7D)

这个优化问题实际上就是支持向量机的基本形式

5.2松弛变量slack variable

  • 在SVM问题求解中我们一般选择整个数据集中最小的一组间隔作为整个数据集的间隔，而我们优化的目标就是让这个最小间隔最大化。但是现实往往没有这么美好，数据的分布不会像我们预想的那么完美，因此我们可以引入松弛变量(slack variable)，给间隔一个 上下浮动的空间，即可以将问题转化成：

五、支持向量机SVM - 图12%5Cge%201-%5Cxii%5Ccap%20%5Cxi_i%5Cge%200%0A%5Cend%7Baligned%7D#card=math&code=%5Cbegin%7Baligned%7D%0A%26%20%5Cmin%5Climits%7B%5Comega%2Cb%7D%20%5Cfrac%7B1%7D%7B2%7D%7C%7C%5Comega%7C%7C%5E2%2BC%5Csum%5Climits_%7Bi%3D1%7D%5En%5Cxi_i%5C%5C%0A%26%20y_i%28%5Comega%5ETx_i%2Bb%29%5Cge%201-%5Cxi_i%5Ccap%20%5Cxi_i%5Cge%200%0A%5Cend%7Baligned%7D)

我们可以将上面的约束条件转化为：

五、支持向量机SVM - 图13%5Ccap%20%5Cxi_i%5Cge%200%5C%5C%0A%5CRightarrow%20%5Cxi_i%20%3D%20%5Cmax%20%5Clbrace%201-%20y_i(%5Comega%5ETx_i%2Bb)%2C0%5Crbrace%5Cend%7Baligned%7D#card=math&code=%5Cbegin%7Baligned%7D%0A%5Cxi_i%5Cge%201-%20y_i%28%5Comega%5ETx_i%2Bb%29%5Ccap%20%5Cxi_i%5Cge%200%5C%5C%0A%5CRightarrow%20%5Cxi_i%20%3D%20%5Cmax%20%5Clbrace%201-%20y_i%28%5Comega%5ETx_i%2Bb%29%2C0%5Crbrace%5Cend%7Baligned%7D)

则优化的目标可以等价于：

五、支持向量机SVM - 图14%2C0)%2B%5Cfrac%7B1%7D%7B2C%7D%7C%7C%5Comega%7C%7C%5E2)%0A#card=math&code=%5Cmin%5Climits%7B%5Comega%2Cb%7D%28%5Csum%5Climits%7Bi%3D0%7D%5E%7Bn%7D%5Cmax%281-y%28%5Comega%5ETx_i%2Bb%29%2C0%29%2B%5Cfrac%7B1%7D%7B2C%7D%7C%7C%5Comega%7C%7C%5E2%29%0A)

  • 在求解SVM的过程中，可以将这个式子的前半部分作为loss function，后半部分作为regularizer

5.3线性模型的统一性

  • 我们可以把上面的损失函数记作：

五、支持向量机SVM - 图15%3D%5Cmax%20%5B1-yf%2C%200%5D%0A#card=math&code=l%28f%29%3D%5Cmax%20%5B1-yf%2C%200%5D%0A)

  • 我们称这种类型的损失函数为hinge loss(铰链损失函数)，因为其函数图像是一个类似于折线的形状。则我们的优化目标可以写成：

五、支持向量机SVM - 图16%2B%5Clambda%20R(f)%5Crbrace%0A#card=math&code=%5Cmin%5Clbrace%5Csum_%7Bi%3D0%7D%5Climits%5E%7Bn%7Dl%28f%29%2B%5Clambda%20R%28f%29%5Crbrace%0A)

其中R(f)是正则项。

  • 事实上前面的所有线性模型，包括线性回归和逻辑回归的优化目标都可以写成上面的形式，区别在于loss函数的选择不同，线性回归选择的loss是Square loss，而逻辑回归选择了Logistic loss，这几种loss函数的图像也各有特点：
  • 0-1 loss只有0和1两种值，在优化目标化简的时候特别方便
  • Square loss的波动幅度比较大，更能反映出极端情况下的损失
  • Logistic loss的变动比较平缓但是永远存在
  • Hinge loss在一定情况下会变成0，而在非0的时候比较平缓

5.4核Kernel

5.4.1核方法 Kernel Method

  • 支持向量机问题中，我们要求解的目标就是一个超平面五、支持向量机SVM - 图17，用这个超平面来对数据集D进行线性的分割，这时候就出现了一个问题：
    • 如果数据不能被线性分割该怎么办？
  • 事实上我们之前在SVM以及其他的线性模型中都默认了数据集D是线性可分的，如果实际情况中碰到的并非这么理想，我们就应该采取一定的办法使得现有的数据变得线性可分。
  • 核方法就可以解决这个问题，核方法通过将原始空间映射到一个更高维的特征空间中，使得数据集D中的样本x线性可分，而此时样本x也从一个d维向量映射成了一个更高维度的向量(可以假定高维特征空间的维度是五、支持向量机SVM - 图18)，用五、支持向量机SVM - 图19#card=math&code=%5Cphi%28x%29)，则我们需要求解的问题变成了：

五、支持向量机SVM - 图20%2Bb%0A#card=math&code=y%3D%5Comega%5ET%5Cphi%28x%29%2Bb%0A)

5.4.2核函数 Kernel Function

  • 而在使用核方法的时候经常会需要计算两个向量的内积，由于特征空间的维度可能很高甚至是无穷维，因此我们可以用一个求解简单的核函数来代替内积，使得两个向量在特征空间的内积等于其原本的形式通过函数五、支持向量机SVM - 图21#card=math&code=K%28x_i%2Cx_j%29)计算出来的结果，这就是kernel trick
  • 根据向量内积的性质我们可以推测出，和函数一定是对称的，并且运算的结果需要时非负数，即有：

五、支持向量机SVM - 图22%3DK(x_j%2Cx_i)%5Cge%200%0A#card=math&code=K%28x_i%2Cx_j%29%3DK%28x_j%2Cx_i%29%5Cge%200%0A)

而对于五、支持向量机SVM - 图23，五、支持向量机SVM - 图24#card=math&code=K%28x_i%2Cx_j%29)可以形成m维的半正定矩阵，这个矩阵也被称为再生核希尔伯特空间(RKHS)，常见的核函数有：

  • 线性核：五、支持向量机SVM - 图25%3Dx_i%5ETx_j#card=math&code=K%28x_i%2Cx_j%29%3Dx_i%5ETx_j)
  • 多项式核：五、支持向量机SVM - 图26%3D(x_i%5ETx_j)%5Ed#card=math&code=K%28x_i%2Cx_j%29%3D%28x_i%5ETx_j%29%5Ed)
  • 高斯核：五、支持向量机SVM - 图27%3D%5Cexp(-%5Cfrac%7B%7C%7Cx_i-x_j%7C%7C%5E2%7D%7B2%5Csigma%5E2%7D)#card=math&code=K%28x_i%2Cx_j%29%3D%5Cexp%28-%5Cfrac%7B%7C%7Cx_i-x_j%7C%7C%5E2%7D%7B2%5Csigma%5E2%7D%29)
  • 拉普拉斯核：五、支持向量机SVM - 图28%3D%5Cexp(-%5Cfrac%7B%7C%7Cx_i-x_j%7C%7C%7D%7B%5Csigma%7D)#card=math&code=K%28x_i%2Cx_j%29%3D%5Cexp%28-%5Cfrac%7B%7C%7Cx_i-x_j%7C%7C%7D%7B%5Csigma%7D%29)
  • Sigmoid核：五、支持向量机SVM - 图29%3D%5Ctanh%20(%5Cbeta%20x_i%5ETx_j%2B%5Ctheta)#card=math&code=K%28x_i%2Cx_j%29%3D%5Ctanh%20%28%5Cbeta%20x_i%5ETx_j%2B%5Ctheta%29)

借助核方法和核函数我们可以把线性分类器用到非线性分类的问题上，但是具体如何选择核函数是未知的，或许需要自己一个个去尝试。

5.5 SVM的代码实现

  1. import numpy as np
  2. from scipy.optimize import minimize
  4. def svm(X, y):
  5.     """
  6.     SVM Support vector machine.
  8.     INPUT:  X: training sample features, P-by-N matrix.
  9.             y: training sample labels, 1-by-N row vector.
  11.     OUTPUT: w: learned perceptron parameters, (P+1)-by-1 column vector.
  12.             num: number of support vectors
  14.     """
  15.     P, N = X.shape
  16.     w = np.zeros((P + 1, 1))
  17.     # 给X添加一行1，对应常数项
  18.     X = np.concatenate((np.ones((1, N)), X), axis=0)
  19.     constraint = []
  20.     for i in range(N):
  21.         single_constrain = {'type': 'ineq',
  22.                             'fun': lambda g,
  23.                             x = X[:, i].reshape(P + 1, 1),
  24.                             y = y[0][i]: np.matmul(g.T, x)[0] * y - 1}
  25.         constraint.append(single_constrain)
  26.     while True:
  27.         answer = minimize(lambda x: x[1:].T * x[1:], 
  28.                                 np.random.normal(0, 10, 3), 
  29.                                 method='COBYLA', constraints=constraint)
  30.         if answer.success:
  31.             break
  32.     w = answer.x
  33.     num = np.sum([np.abs(np.matmul(w.T, X[:, i].reshape((P + 1, 1))) 
  34.                             - y[0][i]) <= 1e-4 for i in range(N)])
  35.     # end answer
  36.     return w, num