从零开始认知支持向量机

1 引言

在前面几章中，掌柜已经陆续介绍了多种分类算法模型，相信各位读者朋友对于机器学习也算是有了一定的了解。在接下来的这一些列文章中，掌柜将开始逐步介绍下一个分类模型——支持向量机。支持向量机（Support Vector Machine, SVM）可以算得上是机器学习算法中最为经典的模型。之所以称之为经典是因为支持向量机的背后有着完美的数学推导与证明。当然，也正是因为这个原因使得学习SVM有着较高的门槛。因此，在接下来的内容中，掌柜将会尽可能以最通俗的表达来介绍SVM中的相关原理。

2 支持向量机

2.1 SVM思想

什么是支持向量机呢？初学者刚接触到这个算法时基本上都会被这个名字所困扰，到底什么叫“向量机”，听起来总觉得怪怪的。因此首先需要明白的是，支持向量机其实和“机”一点关系也没有，算法的关键在于“支持向量”。如图1所示为4种不同模型对同一个数据集分类后的决策边界图。可以看到尽管每个模型都能准确地将数据集分成两类，但是从各自的决策边界到两边样本点的距离来看却有着很大的区别。

图 1. 不同模型决策边界

为了能更加清楚的进行观察，下面将4个决策边界放到一张图中，如图2所示。

图 2. 决策边界图

如图2所示，图中左边从上到下分别为模型(d)(a)(b)(c)在数据集上的决策边界。可以发现模型(c)的泛化能力应该会是最差的，因为从数据的分布位置来看真实的决策面应该是一条左高右低倾斜的直线。其次是模型(b)的泛化能力，因为从图2可以看出模型(b)的决策面太过于偏向方块形的样本点。因为在评估分类决策面优劣的一个原则就是，当没有明确的先验知识告诉我们决策面应该偏向于哪边时，最好的做法应该是居于中间位置，也就是类似于模型(a)和模型(d)的决策面。那么模型(a)和模型(d)谁又更胜一筹呢？进一步，可以将(a)和(d)这两个模型各自到两侧样本点距离可视化出来，如图3所示。

图 3. 决策边界宽度图

从图3中一眼便可以看出，模型(d)的决策面要更居于“中间”（事实上就是在中间），而模型(a)的决策面也是略微偏向于方块形的样本点。因此在这4个模型中，模型(d)的泛化能力通常情况下都会是最强的。此时有读者可能就会问，假如把模型(a)中的决策面向上平移一点，使得其也居于两条虚线之间，那么此时应该选择谁呢？答案当然依旧是模型(d)，原因在于模型(d)的决策面还满足另外一个条件，到两条虚线的距离最大。换句话说也就是，模型(d)中两条虚线之间的距离要大于模型(a)中两条虚线之间的距离。

说到这里，相信各位读者已经猜到，模型(d)对应的就是支持向量机模型，同时虚线上的两个样本点就被称为支持向量。可以发现，最终对决策面其决定性作用的也只有这两个样本点，说得通俗点就是仅根据这两个点就能训练得到模型(d)。

因此，这里可以得出的结论就是，通过支持向量机我们便能够得到一个最优超平面，该超平面满足到左右两侧最近样本点的间隔相同，且离左右最近样本点的间隔最大。不过那又该如何来找到这个超平面呢？

2.2 SVM原理

2.2.1超平面的表达

在正式定义距离之前，这里先回顾一下超平面的表达式

w^{T} x + b = 0 (1)

$w$ $b$ $x$ $y=+1,y=-1$ 分别来表示正样本和负样本。

$w,b$ 后，也就代表确立了超平面。不过对于SVM建模来说，应该从哪个地方入手呢？答案是从SVM的核心思想：最大化间隔（Gap）入手。

2.2.2函数间隔

${{w}^{T}}x+b=0$ $|{{w}^{T}}x+b|$ $|{{w}^{T}}x+b|$ 这么多，但是它依旧遵循绝对值大的离超平面更远的原则，如图4所示。

图 4. 函数间隔图

$x_1+x_2-3=0$ $A,B$ $y^A=+1,y^B=-1$ $A$ $|{{w}^{T}}x+b|=|2+3-3|=2$ $B$ $|w^Tx+b|=|1+1-3|=1$ 。

${{y}^{(i)}}({{w}^{T}}x+b)>0$ ${{y}^{(i)}}({{w}^{T}}x+b)>0$ $y$ $\pm1$ 的原因。所以此时可以将训练集中所有样本点到超平面的函数间隔（Functional Margin）定义为[1]

{\hat{γ}}^{(i)} = y^{(i)} (w^{T} x^{(i)} + b) (2)

且定义训练集中样本点到超平面的函数间隔中的最小值为

\hat{γ} = min_{i = 1, 2, . . ., m} {\hat{γ}}^{(i)} (3)

$(1)$ $k(k\neq0)$ $k$ 倍。所以仅有函数间隔显然不能够唯一确定这一距离，还需要引入另外一种度量方式——几何间隔。

2.2.3 几何间隔

$AB$ $A$ 到直线的真实距离。

图 5. 几何间隔图

${{w}^{T}}x+b=0$ $A$ ${{x}^{(i)}}$ ${{\gamma }^{(i)}}$ $A$ $\vec{BA}$ $W$ $w^Tx+b=0$ $B$ 的坐标为

x^{(i)} - γ^{(i)} \cdot \frac{W}{| | W | |} (4)

$B$ 点在直线上，所以满足

w^{T} (x^{(i)} - γ^{(i)} \cdot \frac{W}{| | W | |}) + b = 0 (5)

$(5)$ $W$ 该怎么得到？

${{w}^{T}}x+b=0$ $w={{({{w}_{1}},{{w}_{2}})}^{T}}$ $w_1x_1+w_2x_2+b=0$ $k_1=-w_1/w_2$ $W$ $W$ $k_2=w_2/w_1$ $W$ $(1,k_2)$ $w_1$ $W=(w_1,w_2)=w$ $W$ $w$ ${{w}^{T}}x+b=0$ $w$ 就是该直线的其中一条法向量。

$(5)$ 有

w^{T} (x^{(i)} - γ^{(i)} \cdot \frac{w}{| | w | |}) + b = 0 (6)

因此几何距离计算公式为

γ^{(i)} = \frac{w^{T} x^{(i)} + b}{| | w | |} = {(\frac{w}{| | w | |})}^{T} x^{(i)} + \frac{b}{| | w | |} (7)

$A$ ${{y}_{A}}=+1$ 时的情况，更一般地几何距离的计算公式为

γ^{(i)} = y^{(i)} ({(\frac{w}{| | w | |})}^{T} x^{(i)} + \frac{b}{| | w | |}) (8)

$A,B$ $x_1+x_2-3=0$ 的距离分别为

\begin{aligned} γ^{A} = + 1 \cdot ({(\frac{w}{| | w | |})}^{T} x^{(A)} + \frac{b}{| | w | |}) = {(\frac{(1, 1)}{\sqrt{1 + 1}})}^{T} (2, 3) + \frac{- 3}{\sqrt{1 + 1}} = \sqrt{2} \\ γ^{B} = - 1 \cdot ({(\frac{w}{| | w | |})}^{T} x^{(A)} + \frac{b}{| | w | |}) = - {(\frac{(1, 1)}{\sqrt{1 + 1}})}^{T} (1, 1) + \frac{3}{\sqrt{1 + 1}} = \frac{1}{\sqrt{2}} \end{aligned} (9)

${{y}^{(i)}}\cdot {{\gamma }^{(i)}}>0$ 。进一步，定义训练集中样本点到超平面的几何间隔中最小值为

γ = min_{i = 1, 2, . . ., m} γ^{(i)} (10)

同时，函数间隔与几何间隔存在以下关系

γ = \frac{\hat{γ}}{| | w | |} (11)

可以发现，几何间隔其实就是在函数间隔的基础上施加了一个约束限制。此时我们已经有了对于间隔度量的方式，所以下一步自然就是最大化这个间隔来求得分类超平面。

2.2.4 最大间隔分类器

${{w}^{T}}x+b=0$ $g({{w}^{T}}x+b)$ $\{-1,+1\}$ $g({{w}^{T}}x+b)$ 就是一个分类器，又因为它是通过最大化几何间隔得来的，故将其称之为最大间隔分类器。

$(10)$ 中已经得到了几何间隔的表达式，所以再对其最大化即可

\begin{aligned} max_{w, b} γ \\ s . t . y^{(i)} ({(\frac{w}{| | w | |})}^{T} x^{(i)} + \frac{b}{| | w | |}) \geq γ, i = 1, 2, . . . m \end{aligned} (12)

$s.t.$ $(12)$ $w,b$ ，使得满足以下条件：

$\gamma$ $\gamma$ ;

$\gamma$ $(10)$ $\gamma$ 是所有间隔中的最小值；

$(11)$ $(12)$ 中的优化问题转化为

\begin{aligned} max_{w, b} \frac{\hat{γ}}{| | w | |} \\ s . t . y^{(i)} (w^{T} x^{(i)} + b) \geq \hat{γ}, i = 1, 2, . . . m \end{aligned} (13)

$\hat{\gamma}=1$ 自然也不会影响最终的优化结果。

$(13)$ 中的优化问题便可以再次转化为如下形式

\begin{aligned} max_{w, b} \frac{1}{| | w | |} \\ s . t . y^{(i)} (w^{T} x^{(i)} + b) \geq 1, i = 1, 2, . . . m \end{aligned} (14)

$(14)$ $f(x)>0$ $\max 1/f(x)$ $\min f(x)$ $\min {{(f(x))}^{2}}$ $x$ $(14)$ 可以将式化简为

\begin{aligned} min_{w, b} \frac{1}{2} | | w | |^{2} \\ s . t . y^{(i)} (w^{T} x^{(i)} + b) \geq 1, i = 1, 2, . . . m \end{aligned} (15)

$1/2$ 是为了后面求导时方便，同时这也不会影响优化结果。到这一步，我们就算是搞清楚了SVM的基本思想，以及它需要求解的优化问题。

2.2.5 函数间隔的性质

在2.2.1节优化问题的化简过程中掌柜直接将函数间隔设置为了1，不过相信对于不少读者来说在这一点上仍旧比较疑惑。当然，这也是一个在学习SVM中最典型的问题，因此接下来就这点进行一个简要的说明。

假设现在有如下函数间隔

\hat{γ} = y^{(i)} (w^{T} x^{(i)} + b) (16)

$(16)$ $\hat{\gamma}$ 便有

y^{(i)} ({(\frac{w}{\hat{γ}})}^{T} x^{(i)} + \frac{b}{\hat{γ}}) = 1 (17)

$W=\frac{w}{{\hat{\gamma }}},B=\frac{b}{{\hat{\gamma }}}$ $(17)$ 转化为

y^{(i)} (W^{T} x^{(i)} + B) = 1 (18)

$(18)$ $W,B$ $w,b$ 即可得到

y^{(i)} (w^{T} x^{(i)} + b) = 1 (19)

$(16)$ $(19)$ $w,b$ 并不是同一个。

例如现有如下平面方程

2 x_{1} + 4 x_{2} - 8 = 0 (20)

${{y}^{(k)}}=+1$ ${{\hat{\gamma }}^{(k)}}=2$ ，所以有

+ 1 (2 x_{1}^{(k)} + 4 x_{2}^{(k)} - 8) = 2 (21)

$(21)$ 两边同时除以2有

x_{1}^{(k)} + 2 x_{2}^{(k)} - 4 = 1 (22)

$w,b$ $1$ $2x_1+4x_2-8=0$ $x_1+2x_2-4=0$ ${{w}^{T}}{{x}^{(i)}}+b=0$ ${{W}^{T}}{{x}^{(i)}}+B=0$ $(16)$ $(19)$ ，也就是说同一个平面与用什么字母表示无关。因此可以将函数间隔直接设为1（实质是同时除以了函数间隔）。

2.2.6 小结

在本节中，掌柜首先通过一个引例介绍了支持向量机的核心思想；接着介绍了支持向量机中衡量间隔的两种度量方式，即函数间隔和几何间隔；然后介绍了如何通过结合函数间隔与几何间隔来建模支持向量机的优化问题；最后还介绍了SVM中的一个经典问题，函数间隔为什么可以设为1。

3 SVM示例代码与线性不可分

在前面两节内容中，掌柜介绍了支持向量机的基本思想以及对应的数学原理。不过说一千道一万，还是不如自己亲手来做一做。在接下来的内容中，掌柜将首先介绍如何通过sklearn来搭建相应的SVM分类模型，然后将接着介绍如何处理SVM中的线性不可分问题。

3.1 线性SVM示例代码

在sklearn中可以通过from sklearn.svm import SVC这句代码就能够导入SVM分类模型了。有读者可能会觉得奇怪，为什么导入的是一个叫SVC的东西？这是因为其实SVM不仅可以用来分类，它同样也能用于回归问题，因此SVC其实就是支持向量分类的意思。

点击进入SVC定义的地方便可以发现里面有很多超参数可以进行设置


xxxxxxxxxx
7
1
1  def __init__(self,
2
2     C=1.0, 
3
3     kernel='rbf', 
4
4     degree=3, 
5
5     gamma='scale',
6
6     coef0=0.0,
7
7     decision_function_shape='ovr'):

在上述代码中只列举了SVM中常见的一些超参数。不过这里暂时只对kernel这个参数进行介绍，其它的参数等介绍完相关原理后再进行解释。根据前面两节内容可知SVM是一个线性分类器，因此这里只需要将参数kernel设置为kernel='linear'便能达到这一目的。

在完成SVC的导入工作后，根据如下代码便可以使用线性SVM进行分类建模，完整实例代码参见Book/Chapter09/01_linear_svm.py文件。


xxxxxxxxxx
6
1
1 def train(x_train, x_test, y_train, y_test):
2
2     model = SVC(kernel='linear')
3
3     model.fit(x_train, y_train)
4
4     y_pre = model.predict(x_test)
5
5     print(f"准确率为：{model.score(x_test, y_test)}")
6
6     # 准确率为：0.975925925925926

上述代码就是通过sklearn实现线性SVM的全部代码。可以看出，在sklearn中使用一个模型的步骤依旧是掌柜在5.3.1节中总结的3步走：建模、训练和预测。同时，由于这里的超参数kernel暂时只有一个取值，因此也不需要进行模型选择。从最后在测试集上的结果来看，线性SVM分类器的表现在准确率上有着不错的结果。

3.2 从线性不可分谈起

根据2节内容中SVM的思想来看，到目前为止谈到的情况都是线性可分的，也就是说总能找到一个超平面将数据集分开。可事实上却是，在大多数场景中各个类别之间都是线性不可分的，即类似如图6所示的情况。

图 6. SVM线性不可分图

对于图6中这种情况应该怎么才能将其分开呢？在4.2.4节中掌柜介绍过，这类问题可以使用特征映射的方法将原来的输入特征映射到更高维度的空间，然后再找寻一个超平面将数据集中不同类别的样本进行分类，如图7所示。

图 7. SVM特征映射图

${{x}^{(i)}}$ $\hat{x}^{(i)}$ $\hat{x}^{(i)}$ ${{x}^{(i)}}$ 进行分类。

在介绍完特征映射的基本思想后，下面掌柜就来介绍如何在SVM中将低维特征映射到高维空间中。

3.3 将低维特征映射到高维空间

$\phi(x)$ $x$ $x,{{x}^{2}},{{x}^{3}}$ $w$ 的计算解析式，其具体由来可参见后续内容。

w = \sum_{i = 1}^{m} α_{i} y^{(i)} x^{(i)} (23)

$(23)$ ${{\alpha }_{i}}$ $b$ ，那么对一个新输入的样本点其预测结果为

\begin{aligned} w^{T} x + b = \sum_{i = 1}^{m} α_{i} y^{(i)} x^{(i)} x + b \\ = \sum_{i = 1}^{m} α_{i} y^{(i)} ⟨ x^{(i)}, x ⟩ + b \end{aligned} (24)

${{x}^{(i)}}$ $x$ $\langle a,b\rangle$ $a,b$ $(24)$ $x$ $y=1$ 。

$\phi(x)$ $x$ $\phi(x)$ ，则此时有

\begin{aligned} y = \sum_{i = 1}^{m} α_{i} y^{(i)} ⟨ x^{(i)}, x ⟩ + b \\ = \sum_{i = 1}^{m} α_{i} y^{(i)} ⟨ ϕ (x^{(i)}), ϕ (x) ⟩ + b \end{aligned} (25)

虽然这样一来算是一定程度上解决了SVM中线性不可分的难题，但是又出现了一个新的问题——“维度爆炸”。

$X$ ${{x}^{(i)}}$ $x_{1}^{(i)},x_{2}^{(i)},x_{3}^{(i)}$ ${{x}_{1}},{{x}_{2}},{{x}_{3}}$ $\phi(x)$ $x_1x_1,x_1x_2,x_1x_3,x_2x_1,x_2x_2,$ $x_2x_3,$ $x_3x_1,$ ${{x}_{3}}{{x}_{2}},$ $x_3x_3$ $z$ $\langle \phi(x),\phi(z)\rangle$ 进行计算

\begin{aligned} ϕ (x) = {[x_{1} x_{1}, x_{1} x_{2}, x_{1} x_{3}, x_{2} x_{1}, x_{2} x_{2}, x_{2} x_{3}, x_{3} x_{1}, x_{3} x_{2}, x_{3} x_{3}]}^{T} \\ ϕ (z) = {[z_{1} z_{1}, z_{1} z_{2}, z_{1} z_{3}, z_{2} z_{1}, z_{2} z_{2}, z_{2} z_{3}, z_{3} z_{1}, z_{3} z_{2}, z_{3} z_{3}]}^{T} \\ ⟨ ϕ (x), ϕ (z) ⟩ = [x_{1} x_{1} z_{1} z_{1} + x_{1} x_{2} z_{1} z_{2} + \dots + x_{3} x_{3} z_{3} z_{3}] \end{aligned} (26)

$o({{n}^{2}})$ $o({{n}^{2}}),o({{n}^{2}}),o(n)$ $n$ $\langle \phi(x),\phi(z)\rangle$ ，但说穿了它就是一个值。不管最后采用的是什么样的映射规则，在预测时都只需要计算这么一个值。因此，假如能通过某种“黑箱”直接计算出这一个值岂不最好？那有没有这样的黑箱呢？当然有，这一“黑箱”操作就称为核函技巧（Kernel Trick）。

3.4 SVM中的核技巧

$\mathcal{X}$ $R^n$ $\mathcal{H}$ $\mathcal{X}$ $\mathcal{H}$ $\phi (x):\mathcal{X}\to \mathcal{H}$ $x,z\in\mathcal{X}$ $K(x,z)$ $K(x,z)=\phi(x)\cdot\phi(z)$ $K(x,z)$ $\phi(x)$ 称为映射函数[2]。

$K(x,z)$ $\langle \phi(x),\phi(z)\rangle$ ，从而避免了上面出现“维度爆炸”的问题。因此，核函数可以看作是实现“黑箱”操作（核技巧）的工具。

$(26)$ $x=(1,2,3),z=(2,3,4)$ ，则此时有