参考资料:
李航《统计学习方法》
《机器学习实战》
sklearn的教程——1.4. Support Vector Machines

1. 线性可分问题与最大间隔

对于一个二分类问题来说,假设给定一个特征空间上的训练数据集,如果能够找到一个超平面将数据集分开,这个问题就叫做线性可分问题。以二维特征空间的分类问题为例,如下图所示,左图就是线性可分问题,右图就是线性不可分问题。将数据分隔开的直线就称作分隔超平面

定义——函数间隔(functional margin)

对于给定的训练数据集T和超平面(w,b),定义超平面(w,b)关于样本点(x_i,y_i)的函数间隔为

\hat{\gamma_i}=y_i(wx_i+b)

定义超平面(w,b)关于训练数据集T的函数间隔为超平面(w,b)关于T中所有样本点(x_i,y_i)的函数间隔之最小值。即

\hat{\gamma}=\min_{i=1,2,\cdots,N}\hat{\gamma_i}

函数间隔可以表示分类预测的正确性及确信度。从图上看,可以知道,为了使分类更加准确,应该使分类点原理这个超平面。因此,我们需要找到训练样本中离超平面函数间隔最小的那个点,且使其函数间隔最大化。

但是,在选择分离超平面时,只有函数间隔还不够。因为只要成比例地改变wb,例如将它们变为2w2b,超平面并没有改变,但是函数间隔却成为原来的2倍。因此,我们引入几何间隔(geometric maigin)的概念。

定义——几何间隔

对于给定的训练数据集T和超平面(w,b),定义超平面(w,b)关于样本点(x_i,y_i)的几何间隔为

\gamma_i=y_i(\frac{w}{||w||}\cdot x_i + \frac{b}{||w||})

定义超平面(w,b)关于训练数据集T的几何间隔为超平面(w,b)关于T中所有样本点(x_i,y_i)的几何间隔之最小值。即:

\gamma=\min_{i=1,2,\cdots,N}\gamma_i

那么,我们的目的就是寻找一个最大间隔分离超平面。寻找最大间隔分离超平面的问题可以表示为下面的约束最优化问题:

\max_{w,b} \gamma

\text{s.t.\quad} y_i(\frac{w}{||w||}\cdot x_i + \frac{b}{||w||}) \ge \gamma \text{, \quad} i=1,2,\cdots,N

考虑几何间隔和函数间隔的关系,可以将问题改写成:

\max_{w,b} \frac{\hat{\gamma}}{||w||}

\text{s.t.\quad} y_i(w \cdot x_i + b) \ge \hat{\gamma} \text{, \quad} i=1,2,\cdots,N

代入\hat{\gamma}=1,得到:

\max_{w,b} \frac{1}{||w||}

\text{s.t.\quad} y_i(w \cdot x_i + b)-1 \ge 0 \text{, \quad} i=1,2,\cdots,N

注意到,最大化\frac{1}{||w||}的最小化\frac{1}{2}||w||^2是等价的,因此,优化问题可以改写成:

\min_{w,b} \frac{1}{2}||w||^2

\text{s.t.\quad} y_i(w \cdot x_i + b)-1 \ge 0 \text{, \quad} i=1,2,\cdots,N

这就是一个凸二次规划(convex quadratic programming)问题。对于该问题的求解可以看:最优化方法(十五)有效集法解凸二次规划。因此,我们可以得到线性可分支持向量机学习算法——最大间隔法。首先构造并求解上述的约束最优化问题,得到最优解w^{\ast}b^{\ast};由此得到分离超平面w^{\ast} \cdot x+b^{\ast}=0,以及分类决策函数f(x0=sign (w^{\ast} \cdot x+b^{\ast})

为了求解该最优化问题,构造拉格朗日函数(这个应该是高数的内容,可以参考这篇文章理解拉格朗日方法对最优化问题的求解——约束优化问题(拉格朗日乘子法求解))。对于每一个不等式约束,引进拉格朗日乘子\alpha_i \ge 0,\quad i=1,2,\cdots, N,定义拉格朗日函数:

L(w,b,\alpha)=\frac{1}{2}||w||^2-\sum_{i=1}^N \alpha_i y_i(w \cdot x_i +b) + \sum_{i=1}^N \alpha_i

其中,\alpha=(\alpha_1,\alpha_2,\cdots,\alpha_N)^T为拉格朗日乘子向量。

根据拉格朗日对偶性,原始问题的对偶问题是极大极小问题:

\max_{\alpha} \min_{w,b} L(w,b,\alpha)

所以,为了得到对偶问题的解,需要先求L(w,b,\alpha)wb极小,再求对\alpha极大。

(1)求L(w,b,\alpha)wb极小

求极值,我们自然而然就可以想到导数。我们将拉格朗日函数L(w,b,\alpha)分别对wb求偏导并令其等于0。

\nabla_w L(w,b,\alpha)=w-\sum_{i=1}^N \alpha_i y_i x_i=0

\nabla_b L(w,b,\alpha)=-\sum_{i=1}^N \alpha_i y_i=0

可以得到:

w=\sum_{i=1}^N \alpha_i y_i x_i

\sum_{i=1}^N \alpha_i y_i=0

w=\sum_{i=1}^N \alpha_i y_i x_i\sum_{i=1}^N \alpha_i y_i=0代入拉格朗日函数L(w,b,\alpha),可以得到:


\begin{aligned}
L(w,b,\alpha) &= \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j)-\sum_{i=1}^N \alpha_i y_i((\sum_{j=1}^N \alpha_j y_j x_j) \cdot x_i +b) + \sum_{i=1}^N \alpha_i \\
&= \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j)-\sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - b\sum_{i=1}^N \alpha_i y_i + \sum_{i=1}^N \alpha_i \\
&= -\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j)+ \sum_{i=1}^N \alpha_i
\end{aligned}

所以,

\min_{w,b}L(w,b,\alpha) = \min_{w,b} -\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j)+ \sum_{i=1}^N \alpha_i

(2)求\min_{w,b}L(w,b,\alpha)\alpha的极大,即是对偶问题

\max_{\alpha} \quad -\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j)+ \sum_{i=1}^N \alpha_i

\text{s.t.} \quad \sum_{i=1}^N \alpha_i y_i=0, \quad \alpha_i \ge 0, \quad i=1,2,\cdots,N

将目标函数的极大转为极小,则等价于:

\min_{\alpha} \quad \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j)- \sum_{i=1}^N \alpha_i

\text{s.t.} \quad \sum_{i=1}^N \alpha_i y_i=0, \quad \alpha_i \ge 0, \quad i=1,2,\cdots,N

那么,线性可分支持向量机学习算法可如下所示:

输入:线性可分训练集T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\},其中x_i \in \chi=R^ny_i \in \mathcal{Y}=\{-1,+1\},\quad i=1,2,\cdots,N

输出:分类超平面和分类决策函数。

(1)构造并求解约束最优化问题

\min_{\alpha} \quad \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j)- \sum_{i=1}^N \alpha_i

\text{s.t.} \quad \sum_{i=1}^N \alpha_i y_i=0, \quad \alpha_i \ge 0, \quad i=1,2,\cdots,N

得到最优解\alpha^{\ast}=(\alpha_1^{\ast},\alpha_2^{\ast},\cdots,\alpha_N^{\ast})^T

(2)计算

w^{\ast}=\sum_{i=1}^N \alpha_i^{\ast} y_i x_i

并选择\alpha^{\ast}的一个正分量\alpha_j^{\ast} >0,计算

b^{\ast}=y_j-\sum_{i=1}^N \alpha_i^{\ast} y_i (x_i \cdot x_j)

(3)求得分离超平面

w^{\ast} \cdot x + b^{\ast}=0

以及分类决策函数

f(x)=sign (w^{\ast} \cdot x + b^{\ast})

2. 支持向量(support vector)、间隔边界和支持向量机

在线性可分情况下,训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量。

支持向量是使约束条件式y_i(w_i \cdot x+b)=0等号成立的点.如图所示,在H_1H_2上的点就是支持向量。可以看到,在H_1H_2中间形成了一条长带,这条长带中没有任何的样本点。则长带的宽度,即H_1H_2之间的距离,称为间隔(margin)。间隔依赖于分离超平面的法向量w,等于\frac{2}{||w||}H_1H_2称为间隔边界。

可以看到,在决定分离超平面时,只有支持向量起作用,其他实例点并不起作用,所以将这种分类模型称为支持向量机。支持向量的个数一般很少,所以支持向量机由很少的“重要的”训练样本确定

支持向量机的意思就是使超平面和支持向量之间的间隔尽可能的大,这样才可以使两类样本准确地分开。——什么是支持向量?

训练SVM的算法——SMO

SMO(序列最小优化,Sequential Minimal Optimization)算法是1966年John Platt发布的一个算法,用于训练SVM。Platt的SMO算法是将大优化问题分解为多个小优化问题来求解的。这些小优化问题往往很容易求解,并且对它们进行顺序求解的结果与将它们作为整体来求解的结果是完全一致的。在结果完全相同的同时,SMO算法的求解时间短很多。

SMO算法的目标是求出一系列\alphab,一旦求出了这些\alpha,就很容易计算出权重向量w并得到分隔超平面。

SMO算法的工作原理是:每次循环中选择两个\alpha进行优化处理。一旦找到一对合适的\alpha,那么就增大其中一个同时减小另一个。这里所谓的“合适”就是指两个\alphaa必须要符合一定的条件,条件之一就是这两个\alpha必须要在间隔边界之外,而其第二个条件则是这两个\alpha还没有进行过区间化处理或者不在边界上。

3. sklearn 线性支持向量机的使用

参考资料:
SVM: Maximum margin separating hyperplane
sklearn-核函数使用对比(常用kernel
sklearn自定义svm核函数(外部和内部定义)

首先先导入需要用到的包

import numpy as np
import matplotlib.pyplot as plt
from sklearn import svm
from sklearn.datasets import make_blobs

创建数据集:

X, y = make_blobs(n_samples=40, centers=2, random_state=4)

make_blobs函数是为聚类产生数据集
产生一个数据集和相应的标签
n_samples:表示数据样本点个数,默认值100
n_features:表示数据的维度,默认值是2
centers:产生数据的中心点,默认值3
cluster_std:数据集的标准差,浮点数或者浮点数序列,默认值1.0
center_box:中心确定之后的数据边界,默认值(-10.0, 10.0)
shuffle :洗乱,默认值是True
random_state:官网解释是随机生成器的种子
转载自:sklearn里的make_blobs

模型训练:

clf = svm.SVC(kernel='linear', C=1000)
clf.fit(X, y)

SVC表示Support Vector Classification,即用支持向量机处理分类问题。kernal表示核函数的选择,设置为linear表示该支持向量机为线性支持向量机。在sklearn中,核函数有以下几种选择——linear(线性核)、poly(多项式核)、rbf(径向基核函数)、sigmoid(Sigmoid核)、precomputed(如果使用precomputed模式,也就是不传入函数,而直接传入计算后的核,那么参与这个核计算的数据集要包含训练集和测试集),默认为rbf(高斯核)。

如果选择多项式核,则需要进一步设置多项式的次数这个参数——degree,默认为3。

在使用SVM时,还有两个十分重要的参数——Cgamma

C是惩罚系数,即对误差的宽容度。c越高,说明越不能容忍出现误差,容易过拟合。C越小,容易欠拟合。C过大或过小,泛化能力变差。C的默认取值为1.0。

gamma是选择RBF函数作为kernel后,该函数自带的一个参数。隐含地决定了数据映射到新的特征空间后的分布,gamma越大,支持向量越少,gamma值越小,支持向量越多。支持向量的个数影响训练与预测的速度。

我们可以通过这个案例中的数据来看一下C的影响。

C的值 拟合结果
0.1
1
1000

可以看到,C越大,拟合的就越准确。

4. 核技巧——核函数

我们前面讲到的都是线性可分问题,对于非线性分类问题,可以使用非线性支持向量机。对于这类SVM,有一个很重要的技巧就是核技巧——kernal trick。核技巧最主要的目的是通过核函数进行一个非线性变化,将非线性问题变换为线性问题,以方便对问题的求解。

假设核函数为K(x_i,x_j)=\phi(x_i) \cdot \phi (x_j),代入对偶问题的目标函数,即:

W(\alpha)=\frac{1}{2}\sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j K(x_i,x_j)-\sum_{i=1}^N \alpha_i

同样,分类决策函数中的内积也可以用核函数来代替,则分类决策函数式称为:

f(x)=sign(\sum_{i=1}^{N_s} \alpha_i^{\ast}y_i \cdot \phi(x_i)+b^{\ast})=sign(\sum_{i=1}^{N_s}\alpha_i^{\ast}y_iK(x_i,x)+b^{\ast})

这等价于经过映射函数\phi将原来的输入空间变换到一个新的特征空间,将输入空间中的内积x_i \cdot x_j变换为特征空间中的内积\phi(x_i) \cdot \phi(x_j),在新的特征空间里从训练样本中学习线性支持向量机。当映射函数是非线性函数时,学习到的含有核函数的支持向量机是非线性分类模型。

也就是说,在核函数K(x,z)给定的条件下,可以利用解线性分类问题的方法求解非线性分类问题的支持向量机。学习是隐式地在特征空间进行的,不需要显式地定义特征空间和映射函数。这样的技巧称为核技巧,它是巧妙地利用线性分类学习方法与核函数解决非线性问题的技术。

常用的核函数可以看——用实验理解SVM的核函数和参数。

5. 在sklearn中使用非线性支持向量机

参考资料
Non-linear SVM

首先还是导入需要的包:

import numpy as np
import matplotlib.pyplot as plt
from sklearn import svm

数据生成:

xx, yy = np.meshgrid(np.linspace(-3, 3, 500),
                     np.linspace(-3, 3, 500))
np.random.seed(0)
X = np.random.randn(300, 2)
Y = np.logical_xor(X[:, 0] > 0, X[:, 1] > 0)

数据的分布如下图所示。可以看到,这是一个明显的线性不可分问题。

SVM的训练:

clf = svm.SVC(kernel='rbf', C=1000, gamma = 10)
clf.fit(X, Y)

前面说到,Cgamma是SVM的两个十分重要的参数,我们可以以高斯核为例,感受一下这两个参数的影响:

取值 gamma = 0.5 gamma = 5 gamma = 50
C=0.5
C=10.0
C=100.0
C=1000.0

可以看到,Cgamma越大,拟合的效果相对较好,但是要注意过拟合的情况。所以找到一对合适的Cgamma在调参过程中极其重要。

另外,在sklearn官方还有很多教程,就不一一列举了。教程比较简单易懂,可以解决大部分情况:

(1)多分类问题:Plot different SVM classifiers in the iris dataset
(2)考虑样本权重——SVM: Separating hyperplane for unbalanced classesSVM: Weighted samples
(3)SVR,支持向量回归——将SVM扩展到回归问题——Support Vector Regression (SVR) using linear and non-linear kernels

6. 核技巧的另一应用——岭回归与核岭回归

6.1 岭回归

我们知道,最简单的线性回归是通过线性函数f(x)=w^T+b来拟合函数的,损失函数通过UI小二乘法来确定,即\min_w ||wX-y||_2^2。岭回归即在最小二乘法上增加一个正则项:

\min_w ||wX-y||_2^2 + \alpha ||w||_2^2

同样可以利用最小二乘法求解。借用机器学习库sklearn,可以通过linear_model.Ridge()函数来确定。

from sklearn.linear_model import Ridge
import numpy as np

n_samples, n_features = 10, 5
rng = np.random.RandomState(0)
y = rng.randn(n_samples)
X = rng.randn(n_samples, n_features)

clf = Ridge(alpha=1.0)
clf.fit(X, y)

该函数的具体参数可以看官网的解释,函数中的各种参数的解释可以看——Ridge回归 sklearn API参数速查手册岭回归详解 从零开始 从理论到实践

在sklearn中,Ridge模型中的相关函数如下图所示:

6.2. KRR——核岭回归

内核岭回归解释将岭回归方法和核技巧结合起来了。同样的,在sklearn里面调用也特别简单:

from sklearn.kernel_ridge import KernelRidge
reg = KernelRidge(alpha=5.0)
reg.fit(X_train, y_train)

相关的参数和岭回归的基本是一致的。这里的“核技巧”和支持向量机中的“核技巧”是一样的含义,也就是用核函数来解决非线性问题。

6.3. 使用GridSearch来进行模型选择

from sklearn.kernel_ridge import KernelRidge
from sklearn.model_selection import GridSearchCV
from sklearn.gaussian_process.kernels import ExpSineSquared

param_grid = {"alpha": [1e0, 1e-1, 1e-2, 1e-3]}

reg = GridSearchCV(KernelRidge(), param_grid=param_grid)
stime = time.time()
reg.fit(X_train, y_train)
print("Time for KRR fitting: %.3f" % (time.time() - stime))

7. 核函数技巧——高斯过程

在高斯过程回归【Gaussian process regression(GPR)】中,也有用到核函数技巧,具体的可以看【看得见的高斯过程:这是一份直观的入门解读】这篇文章,讲的比较清楚、形象生动。