SVM最大间隔超平面学习笔记及对函数间隔设置为1的思考

SVM(支持向量机)最初是一种解决二分类的有监督学习算法，其目的在于：在给定两类样本的数据集的前提下，寻找一个将两类样本分隔开的超平面(separating hyperplane)，并且使得两类样本之间的边界间隔(margin)最大化。最终得到的超平面被称为决策边界(decision boundary)。

本文主要内容分为以下几点：

• 介绍什么是超平面
• 分隔超平面的定义
• 最大间隔超平面的介绍
• 为什么最小函数间隔设置为1

1 分隔超平面

首先给定一个样本集$D\in \R^{m\times (n+1)}$D∈Rm×(n+1)，$D=\{(\mathbf{x}^i,y^i)|i=1,2,....,m\}$D={(xi,yi)∣i=1,2,....,m}，其中，$\mathbf{x}^i\in \R^{1\times n},y^{i}\in\{-1, +1\}$xi∈R1×n,yi∈{−1,+1}。样本集$D$D由两类子样本集组成，我们可以将$D$D分为正负样本集$D_+$D+​和$D_-$D−​，正负样本集中的样本分别用$\mathbf{x_+}$x+​和$\mathbf{x}_-$x−​来表示。本文开头说过，支持向量机是一种有监督学习算法，为了区分正负样本，我们会事先给样本进行数据标记，如用$y=\{-1,1\}$y={−1,1}进行标记，如对于正样本$\mathbf{x}_+$x+​，$y_+=1$y+​=1，而负样本的标记$y_-=-1$y−​=−1，当然可以选用其余的标记，不过采用这种标记方法有利于计算。

假设正负样本线性可分，这意味着，可以找到一个超平面$w^Tx+b=0$wTx+b=0，使得正样本和负样本被其隔开。如下图所示：

能够将正负样本分隔开的超平面，我们可以称之为分隔超平面(Seperating Hyperplane)，它需要满足一些条件，这个我们在下面的内容继续介绍。首先先了解一下什么是超平面。

1.1 超平面

在$n$n维空间中，超平面是一个$n-1$n−1维的子空间，该子空间可将$n$n维空间分隔成为两部分。在二维和三维空间中超平面的几何表示比较直观，例如二维空间是一个面，那么其超平面就是一维的直线，而在三维立体空间中，超平面是将立体分隔成两部分的二维平面。

从数学表示的层面上来看，实数域$n$n维空间中的超平面定义如下：
$w_1 x_1 + w_2 x_2 +... + w_n x_n + b=0 \tag{1}$w1​x1​+w2​x2​+...+wn​xn​+b=0(1)
可以用线性代数的知识将该表达式改写为向量内积的形式：
$w^T\mathbf{x}+b=0 \tag{2}$wTx+b=0(2)
或者
$<w,\mathbf{x}>+b=0 \tag{3}$<w,x>+b=0(3)
其中$w\in \R^{1\times n}$w∈R1×n为超平面的法向量，$\mathbf{x} \in \R ^{1\times n}$x∈R1×n，$b\in \R$b∈R为偏置值(bias)。

超平面有以下几个性质：

​ 性质1：法向量和偏置项以任意相同的倍数放缩，新表达式描述的仍然是原来的超平面。假设放缩比例为$\lambda$λ，令$w=\lambda w, b=\lambda b$w=λw,b=λb后得到的超平面表达式为$\lambda(w^T\mathbf{x}+b)=0$λ(wTx+b)=0，显然，这个表达式表示的仍然是原来的超平面。举个浅显的例子，直线$2x_1+4x_2+4=0$2x1​+4x2​+4=0与直线$x_1+2x_2+2=0$x1​+2x2​+2=0是同一条直线，虽然他们的系数之比为2。

​ 性质2：点$\mathbf{x}$x到超平面的距离为
$d=\frac{|w^T\mathbf{x}+b|}{||w||} \tag{4}$d=∣∣w∣∣∣wTx+b∣​(4)
​ 性质3：超平面将$n$n维空间划分为3部分，分为是：i)点$\mathbf{x}$x在超平面里$\Leftrightarrow w^T\mathbf{x}+b=0$⇔wTx+b=0；ii)点$\mathbf{x}$x在超平面的“上方” $\Leftrightarrow w^T\mathbf{x}+b>0$⇔wTx+b>0；iii)点$\mathbf{x}$x在超平面的“下方”$\Leftrightarrow w^T\mathbf{x}+b<0$⇔wTx+b<0。可以通过图2加深理解。

需要注意的是，“上方”和“下方”并不是方位上的超平面上下方，而是以超平面的法向量$w$w的指向为准，$w$w指向的方向称为“上方”，反之则为“下方”。

1.2 分隔超平面

SVM中，分隔超平面是一个能够将正负样本恰好隔开的超平面，并且使得正样本在分隔超平面“上方”，负样本在分隔超平面”下方“。这就意味着，分隔超平面$w^T\mathbf{x}+b=0$wTx+b=0中的$w,b$w,b需要满足以下条件：
$w^T\mathbf{x_+}+b>0\\ w^T\mathbf{x_-}+b<0$wTx+​+b>0wTx−​+b<0
其中$\mathbf{x}_+$x+​为正样本点，$\mathbf{x}_-$x−​为负样本点，而正负样本对应的标记值为$y_+=+1,y_-=-1$y+​=+1,y−​=−1，所以这两个条件可以改写成下面两个式子：
$y_+w^T\mathbf{x_+}+b>0\\ y_-w^T\mathbf{x_-}+b>0$y+​wTx+​+b>0y−​wTx−​+b>0
其实，我们可以写成更一般的形式。对于线性可分的样本集，$D=\{(\mathbf{x}^i,y^i)|i=1,2,....,m\}$D={(xi,yi)∣i=1,2,....,m}，其中，$\mathbf{x}^i\in \R^{1\times n},y^{i}\in\{-1, +1\}$xi∈R1×n,yi∈{−1,+1}，分类正确的超平面$w^T\mathbf{x}+b=0$wTx+b=0需要满足的条件为:$y^i(w^T\mathbf{x}^i+b)>0$yi(wTxi+b)>0。令$\hat{\gamma}^i=y^i(w^T\mathbf{x}^i+b)>0$γ^​i=yi(wTxi+b)>0，我们可以得到更加紧凑的表达：“分类正确”$\Leftrightarrow$⇔$\hat{\gamma}^{i}>0,i=1,2,...,m$γ^​i>0,i=1,2,...,m。在SVM中，$\hat{\gamma}=y(w^T\mathbf{x}+b)$γ^​=y(wTx+b)被称为样本点到超平面的函数间隔。在我看来，函数间隔是人为定义的，其中好处之一是，方便推导和文字叙述。

根据上面的内容，我们得出结论，对于给定的线性可分的样本集合，必然存在分隔超平面可以将正负样本分开，该分类正确的超平面需要满足的条件为：样本点到超平面的函数间隔大于零。

实际上，根据函数间隔大于零这个条件，我们可以求得无数个分隔超平面。对于人来说，我们肯定想要求得一个“最好的分隔超平面”，那评价是否最好的指标是什么呢？在SVM算法中，其评价指标为几何间隔，即点到面的距离，可以根据1.1中超平面的性质2进行计算。以图3为例，大多数人都会本能地认为图3(a)中的分类效果比图3(b)和©要更好，我们做出这个判断的思维步骤为：寻找与线最近的样本点→人眼感知最近的样本点与直线的几何间距→根据前面两步获得的信息判断分隔效果，间距最大的即为最好。SVM就是遵循了这样一种判别思想，并在该思想的基础上发展出相应的理论。

在这里，可以很自然地引出SVM算法的计算目标之一：对于线性可分的样本集，在众多分隔面中，寻找出最优的那一个。最优的判定标准在于离分隔面最近的样本点与分隔面的几何间隔是否是最大的，最优的分隔面称为最大间隔分隔超平面。名字太长了，简短一点吧，最大间隔超平面(Large-margin Hyperplane)。在第2部分，对最大间隔超平面进行进一步描述。

2 最大间隔超平面

2.1 最大间隔超平面数学描述

首先将最大间隔超平面数学推导中的的数学定义名称、符号和表达式联系起来，具体如下：

线性可分的样本集 ——$D=\{(\mathbf{x}^i,y^i)|i=1,2,....,m\}$D={(xi,yi)∣i=1,2,....,m}，其中，$\mathbf{x}^i\in \R^{1\times n},y^{i}\in\{-1, +1\}$xi∈R1×n,yi∈{−1,+1}

超平面 —— $w^T\mathbf{x}+b=0$wTx+b=0

函数间隔 —— $\hat{\gamma}^i=y^i(w^T\mathbf{x}^i+b)$γ^​i=yi(wTxi+b)

几何间隔 —— $\tilde{y}^i=\frac{|w^T\mathbf{x}^i+b|}{||w||}=\frac{y^i(w^T\mathbf{x}^i+b)}{||w||}$y~​i=∣∣w∣∣∣wTxi+b∣​=∣∣w∣∣yi(wTxi+b)​

根据第1部分的叙述，最大间隔超平面需要满足两个约束条件：（1）能够将正负样本正确分类，或者说样本点到超平面的函数间隔大于零；（2）离超平面最近的样本点与超平面的几何间隔最大。

第一个条件的数学表达式为$\hat{\gamma}^i=y^i(w^T\mathbf{x}^i+b)>0$γ^​i=yi(wTxi+b)>0。

接着我们分析第二个条件。我们可以用式(5)所有样本点与超平面的最小几何间隔，因为我们的样本点$\mathbf{x}^i,y^i$xi,yi的数据是已知的，所以这个最小几何间隔是关于$w$w和$b$b的函数，用$d(w,b)$d(w,b)来表示，由于$||w||$∣∣w∣∣与$i$i无关，所以我们可以将其提出，放在最小化式子前面。接下来我们改变超平面的法向量方向和截距，即改变$w$w和$b$b，在这个改变的过程中，最小几何间隔可能发生变化也可能保持不变，（至于为什么会有不变的情况，看后面的讲解），我们需要的做的是，在最小几何间隔的所有变化值的集合中，寻找最大的那个值以及相应的$w$w和$b$b，这个过程可以用式（6）来表示。
$d(w,b)=\min_i\tilde{y}^i=\min_{i} \frac{y^i(w^T\mathbf{x}^i+b)}{||w||}=\frac{1}{||w||}\min_{i} y^i(w^T\mathbf{x}^i+b) ,i=1,2,...,m \tag{5}$d(w,b)=imin​y~​i=imin​∣∣w∣∣yi(wTxi+b)​=∣∣w∣∣1​imin​yi(wTxi+b),i=1,2,...,m(5)

$\max_{w,b}d(w,b)=\max_{w,b}\min_i\tilde{y}^i=\max_{w,b}\frac{1}{||w||} \min_{i} y^i(w^T\mathbf{x}^i+b),i=1,2,...,m \tag{6}$w,bmax​d(w,b)=w,bmax​imin​y~​i=w,bmax​∣∣w∣∣1​imin​yi(wTxi+b),i=1,2,...,m(6)

结合这两个约束条件，我们可以得到求解最大间隔超平面的求解公式：
$\max_{w,b}\frac{1}{||w||}\min_{i} y^i(w^T\mathbf{x}^i+b),i=1,2,...,m \\ subject \ to \quad y^i(w^T\mathbf{x}^i+b)>0 \tag{7}$w,bmax​∣∣w∣∣1​imin​yi(wTxi+b),i=1,2,...,msubject toyi(wTxi+b)>0(7)
到了这里，最大间隔超平面的问题似乎已经解决了，毕竟已经得到了它的求解公式，但是，我们仔细看一下式(7)，会发现事情远没有那么简单，$max$max中还包含了$min$min，这个$i$i还可以从1到$m$m取值，感觉求解太难了。

接下来，我们继续对式(7)进行简化。这个简化还需要从前面说的关于样本点与超平面最小几何间隔在$w$w和$b$b的变化过程中可能保持不变的内容讲起。

首先需要说的是，在最优化过程中，$w$w和$b$b的变化分为等比例变化和非等比例变化这两种。例如，我们将$w_k$wk​和$b_k$bk​表示原超平面的$w$w和$b$b，$w_{k+1}$wk+1​和$b_{k+1}$bk+1​表示变化后的超平面的$w$w和$b$b。变化前的超平面为$w_k^Tx+b_k=0$wkT​x+bk​=0，变化后的超平面为$w^T_{k+1}x+b_{k+1}=0$wk+1T​x+bk+1​=0。

假设$\lambda$λ和$s$s分别为$w$w和$b$b变化的比例因子，那么$w$w和$b$b等比例变化意味着$\lambda=s$λ=s，非等比例变化则有$\lambda\neq s$λ​=s。

当等比例变化时，变化后的超平面$w^T_{k+1}x+b_{k+1}=\lambda(w_k^Tx+b_k)=0$wk+1T​x+bk+1​=λ(wkT​x+bk​)=0，可以看到，变化后的超平面与变化前的超平面相同。以图4为例，图4三个表达式中的$w$w和$b$b虽然不同，但是对应成比例，所以表示的是同一条直线。实际上，如果我们将其中一个$w$w和$b$b等比例缩放的话，我们可以得到该直线的无数个表达式，拓展到超平面上，可以说某一确定的超平面对应无数个$w$w和$b$b。如果我们不将这个缩放对超平面表达式的影响消除的话，那么就算用式(7)能够求解，解出的最优超平面也对应有无数个$w$w和$b$b，解不唯一。

若是我们要求某一固定的超平面，其对应的$w$w和$b$b是唯一的，那么就要需要添加限制条件。限制条件可以有很多种，选取其中一种即可。如向量$w$w的模长为1，$||w||=1$∣∣w∣∣=1，也就是说，你只能用模长为1的法向量$w$w来表示超平面，这样就消除了等比例缩放的影响。但是，添加这样一个限制条件，虽然满足要求，但并不能对式(7)进行简化，所以我们需要换一种思路来添加限制条件。

SVM选用的限制条件为：$\min_{i} y^i(w^T\mathbf{x}^i+b)=1,i=1,2...,m$mini​yi(wTxi+b)=1,i=1,2...,m。这个式子将样本点和超平面联系起来，用以确定超平面的唯一表示参数$w$w和$b$b。

仔细思考一下这个限制条件是否合适。在所有的样本点都是已知的前提下，令最小的函数间隔等于1是否能够唯一确定超平面。可以从逻辑上思考这一点，当超平面固定，即$w$w和$b$b不会非等比例缩放，我们一定能找到，所有样本点中与超平面函数间隔最小的样本点，即$\min_{i} y^i(w^T\mathbf{x}^i+b)=1$mini​yi(wTxi+b)=1一定有解，不妨将这个解记为$\mathbf{x}^j$xj。在$\mathbf{x}^j$xj的数据值和超平面固定的条件下，令$y^j(w^T\mathbf{x}^j+b)=1$yj(wTxj+b)=1就相当于自适应缩放固定超平面的某一个$w$w和$b$b，以使得最终$w,b$w,b代入$y^j(w^T\mathbf{x}^j+b)$yj(wTxj+b)结果为1。比如，图4中，我们必然可以找到距离超平面最近的点，假设其坐标为$(5,6)$(5,6)，实际上，这也是函数间隔最小的点。我们可以选择等比例缩放图4中第二个式子的$w$w和$b$b,即$\left[1,1,-5\right]^T$[1,1,−5]T，使得$y^j(w^T\mathbf{x}^j+b)=5w_1+6w_2+b=1$yj(wTxj+b)=5w1​+6w2​+b=1，假设倍数为$l$l，那么$[w_1, w_2, b]^T=[l,l,-5l]^T$[w1​,w2​,b]T=[l,l,−5l]T ，所以$y(w^T\mathbf{x}+b)=5w_1+6w_2+b=5l+6l-5l=1$y(wTx+b)=5w1​+6w2​+b=5l+6l−5l=1，这样可以求得$l=1/6$l=1/6，于是我们可以得到满足条件的$w=[1/6, 1/6]^T, b=-5/6$w=[1/6,1/6]T,b=−5/6。我们可以放缩第三个式子的$w$w和$b$b来适应该限制条件，也是得到同一个结果。

因此，限制条件$\min_{i} y^i(w^T\mathbf{x}^i+b)=1$mini​yi(wTxi+b)=1是可以消除等比例缩放对解的影响的，尽管我们不知道离超平面最近的那个样本点具体是哪一个。当超平面改变时，在该限制条件的作用下，同样会经历一个缩放的过程，使得其对应的$w$w和$b$b一定是唯一的。尽管前面介绍了那么多，到这里可能大家还是会感觉有点抽象。这些数学概念我们只能尽可能去理解，很难将其详细地描绘出来。这里顺便提一下，我们可以令$\min_{i} y^i(w^T\mathbf{x}^i+b)$mini​yi(wTxi+b)等于任意常数$C$C作为限制条件，实际上效果与令其等于$1$1是一样的，都是为了消除缩放的影响。

同时，需要注意的是**$w$w和$b$b等比例缩放并不改变几何间隔**，如$\tilde{y}^i=\frac{y^i\lambda(w^T\mathbf{x}^i+b)}{||\lambda w||}=\frac{y^i(w^T\mathbf{x}^i+b)}{||w||}$y~​i=∣∣λw∣∣yiλ(wTxi+b)​=∣∣w∣∣yi(wTxi+b)​，其中$\lambda$λ为比例因子，因此，当添加限制条件$\min_{i} y^i(w^T\mathbf{x}^i+b)=1$mini​yi(wTxi+b)=1时，根据前两段的内容，我们可以知道，这包含一个动态放缩以适应条件的过程，在这个放缩过程中，与超平面最近的点，其与超平面的距离（几何间隔）并不发生变化。所以当把$\min_{i} y^i(w^T\mathbf{x}^i+b)$mini​yi(wTxi+b)缩放1时，与超平面最近的点到超平面的距离为$\min_{i} \frac{y^i(w^T\mathbf{x}^i+b)}{||w||}=\frac{1}{||w||}\min_{i}y^i(w^T\mathbf{x}^i+b)=\frac{1}{||w||}$mini​∣∣w∣∣yi(wTxi+b)​=∣∣w∣∣1​mini​yi(wTxi+b)=∣∣w∣∣1​。在满足$\min_{i} y^i(w^T\mathbf{x}^i+b)=1$mini​yi(wTxi+b)=1的条件下，其最小几何间隔就为$\frac{1}{||w||}$∣∣w∣∣1​.

接下来我们来看看，添加这个限制条件对于式(7)的改进。首先最优化目标函数变为：
$\max_{w,b}\frac{1}{||w||}$w,bmax​∣∣w∣∣1​
一下子简洁了好多。

然后约束条件也要变。条件$\min_{i} y^i(w^T\mathbf{x}^i+b)=1$mini​yi(wTxi+b)=1等价于$y^i(w^T\mathbf{x}^i+b)\geq 1$yi(wTxi+b)≥1，将其与原条件$y^i(w^T\mathbf{x}^i+b)>0$yi(wTxi+b)>0综合一下即为$y^i(w^T\mathbf{x}^i+b)\geq 1$yi(wTxi+b)≥1。

于是我们得到求解最大间隔超平面的最终表达式：
$\max_{w,b}\frac{1}{||w||} \tag{8}\\ subject \ to \quad y^i(w^T\mathbf{x}^i+b)\geq 1$w,bmax​∣∣w∣∣1​subject toyi(wTxi+b)≥1(8)
最大间隔超平面最优化过程可以参见图5。在满足条件的前提下，改变$w$w和$b$b，超平面位置也会随之发生变化。这个时候，才是真正的迭代求最优解。

以上为学习SVM最大间隔分隔面的学习笔记和思考，希望对大家有所帮助。

参考资料
超平面介绍的部分内容来自于[1]中，等比例缩放的内容部分参考了[2]中@Nine的回答。
[1] SVM的数学原理详解
[2] 机器学习SVM中关于函数间隔为什么可以设置为1？