支持向量机

硬间隔SVM

问题定义

考虑下图二维的二分类问题，如果要寻找一条直线对数据进行分类，那么可以找到很多条符合条件的直线，如 $H_2, H_3$H2​,H3​。在这些直线中，如何选择一个最优的直线呢？

一个直观的感受是，一个较好的直线应该具有以下条件：

• 直线能够对所有样本正确分类。
• 直线应该尽可能地在这两类样本的 “中间”。

直线应该在这两类点的 “中间” (如 $H_3$H3​)，而不是过于靠近样本点 (如$H_2$H2​)，从而当数据产生细小波动时，直线仍能正确分类。那么如何表示 直线应该在这两类点的 “中间” ？

我们定义一个间隔，表示样本中距离直线最近的点，这个点到直线的距离。那么，对于每一条直线，都可以用间隔来衡量直线与样本的靠近程度。那么，直线应该在这两类点的 “中间”，也就是要最大化直线与样本点之间的间隔。

对于二维的数据，需要寻找直线进行划分，对于更高维的数据，寻找的是一个超平面进行划分。超平面由法向量 $w$w 和截距 $b$b 组成，形式为：
$w^Tx + b = 0$wTx+b=0

如果可以寻找到一个超平面对数据全部正确分类，那么我们称这些数据是线性可分的。

考虑线性可分的训练数据 $D = \{(x_1, y_1), (x_2, y_2), ..., (x_m, y_m)\}$D={(x1​,y1​),(x2​,y2​),...,(xm​,ym​)}，其中 $y_i \in \{-1, 1\}$yi​∈{−1,1} ，这里用 $\{-1, 1\}${−1,1} 而不是 $\{0, 1\}${0,1} 表示负样本和正样本，主要是为了之后的计算方便。我们的目标是寻找一个最优的超平面 $w^Tx + b = 0$wTx+b=0 进行分类。根据之前我们的条件:

• 超平面能够对所有样本正确分类。

我们使用超平面对 $x_i$xi​ 分类时，如果 $w^Tx_i + b < 0$wTxi​+b<0，则认为 $y_i = -1$yi​=−1；如果 $w^Tx_i + b > 0$wTxi​+b>0，则认为 $y_i = 1$yi​=1。因此，对于一个样本 $x_i$xi​，如果 $y_i(w^Tx_i+b) > 0$yi​(wTxi​+b)>0，那么该样本被正确分类。 因此，如果超平面能够对所有样本正确分类，那么其需要满足

$y_i(w^Tx_i + b) > 0, i = 1, 2, ..., m$yi​(wTxi​+b)>0,i=1,2,...,m

• 超平面应该尽可能地在这两类样本的 “中间”。

点到超平面的距离 $d = \frac{|w^Tx+b|}{\|w\|}$d=∥w∥∣wTx+b∣​，根据间隔的定义，间隔等于
$margin = \min_{i=1, 2, ..., m} \frac{|w^Tx_i+b|}{\|w\|}$margin=i=1,2,...,mmin​∥w∥∣wTxi​+b∣​
而 $y_i(w^Tx_i + b) > 0$yi​(wTxi​+b)>0， $|y_i| = 1$∣yi​∣=1，因此 $|w^Tx+b| = y_i(w^Tx+b)$∣wTx+b∣=yi​(wTx+b)，即可把绝对值符号去掉。那么，最大化间隔：

$\max_{w, b} margin = \max_{w, b} \min_{i=1, 2, ..., m} \frac{y_i(w^Tx_i + b) }{\|w\|}$w,bmax​margin=w,bmax​i=1,2,...,mmin​∥w∥yi​(wTxi​+b)​

综上所述，我们要寻找超平面即转化为了以下的优化问题
$\max_{w, b} \min_{i=1, 2, ..., m} \frac{y_i(w^Tx_i + b) }{\|w\|} \\ \, \\ \text{s.t.} \quad y_i(w^Tx_i + b) > 0, i = 1, 2, ..., m$w,bmax​i=1,2,...,mmin​∥w∥yi​(wTxi​+b)​s.t.yi​(wTxi​+b)>0,i=1,2,...,m

对于 $y_i(w^Tx_i + b) > 0, i = 1, 2, ..., m$yi​(wTxi​+b)>0,i=1,2,...,m，我们令 $\gamma = \min_{i=1, 2, ..., m} y_i(w^Tx_i + b)$γ=mini=1,2,...,m​yi​(wTxi​+b)，那么有 $y_i(w^Tx_i + b) \geq \gamma > 0, i = 1, 2, ..., m$yi​(wTxi​+b)≥γ>0,i=1,2,...,m，即 $y_i(\frac{w^T}{\gamma} x_i+ \frac{b}{\gamma}) \geq 1, i = 1, 2, ..., m$yi​(γwT​xi​+γb​)≥1,i=1,2,...,m。

对于 $\min_{i=1, 2, ..., m} \frac{y_i(w^Tx_i + b) }{\|w\|}$mini=1,2,...,m​∥w∥yi​(wTxi​+b)​，有 $\min_{i=1, 2, ..., m} \frac{y_i(w^Tx_i + b) }{\|w\|} = \frac{1}{\|w\|}\min_{i=1, 2, ..., m} y_i(w^Tx_i + b) = \frac{1}{\|w\|}\gamma = \frac{1}{\|\frac{w}{\gamma}\|}$mini=1,2,...,m​∥w∥yi​(wTxi​+b)​=∥w∥1​mini=1,2,...,m​yi​(wTxi​+b)=∥w∥1​γ=∥γw​∥1​

对于超平面 $w^Tx+b=0$wTx+b=0，$(w^T, b)$(wT,b) 无论以什么比例等比例变大或者变小时，其在几何上表示的仍然是同一个超平面。因此超平面 $(w, b)$(w,b) 和 $(\frac{w}{\gamma}, \frac{b}{\gamma})$(γw​,γb​)表示的是一个超平面。我们令新的 $(w, b)$(w,b) 代替 $(\frac{w}{\gamma}, \frac{b}{\gamma})$(γw​,γb​)，原优化问题表示为：

$\max_{w, b} \frac{1}{\|w\|} \\ \,\\ \text{s.t.} \quad y_i(w^Tx_i + b) \geq 1, i = 1, 2, ..., m$w,bmax​∥w∥1​s.t.yi​(wTxi​+b)≥1,i=1,2,...,m

又因为 $\max \frac{1}{\|w\|}$max∥w∥1​ 等价于 $\min\frac{\|w\|^2}{2} = \min \frac{1}{2}w^Tw$min2∥w∥2​=min21​wTw，因此，寻找最优的超平面，最终简化成了以下的优化问题：

$\max_{w, b} \frac{1}{2}w^Tw\\ \,\\ \text{s.t.} \quad 1 - y_i(w^Tx_i + b) \leq 0, i = 1, 2, ..., m$w,bmax​21​wTws.t.1−yi​(wTxi​+b)≤0,i=1,2,...,m

对偶问题

对于线性可分的数据集，上述优化问题的解是存在且唯一的（证明略）。求解上述优化问题需要借助拉格朗日函数和对偶问题。

支持向量机的 $f = \frac{1}{2}w^Tw$f=21​wTw 和 $g_i = 1 - y_i(w^Tx_i+b)$gi​=1−yi​(wTxi​+b) 均为凸函数，因此原优化问题等价于其拉格朗日函数的对偶问题。

原优化问题：
$\max_{w, b} \frac{1}{2}w^Tw\\ \,\\ \text{s.t.} \quad 1 - y_i(w^Tx_i + b) \leq 0, i = 1, 2, ..., m$w,bmax​21​wTws.t.1−yi​(wTxi​+b)≤0,i=1,2,...,m

构建拉格朗日函数：

$L(w, b, \alpha) = \frac{1}{2}w^Tw + \sum_{i=1}^{m}\alpha_i(1 - y_i(w^Tx_i + b))$L(w,b,α)=21​wTw+i=1∑m​αi​(1−yi​(wTxi​+b))

原优化问题等价于：

$\min_{w, b}\max_{\alpha} L(w, b, \alpha) \\ \, \\ \text{s.t.} \quad \alpha_i \geq 0, i=1, 2, ..., m$w,bmin​αmax​L(w,b,α)s.t.αi​≥0,i=1,2,...,m

再转化为对偶问题：
$\max_{\alpha}\min_{w, b} L(w, b, \alpha) \\ \, \\ \text{s.t.} \quad \alpha_i \geq 0, i=1, 2, ..., m$αmax​w,bmin​L(w,b,α)s.t.αi​≥0,i=1,2,...,m

对上述问题求解 $\min_{w, b} L(w, b, \alpha)$minw,b​L(w,b,α)，即

再代入到对偶问题中，得到

原问题最终转化成了上述的优化对偶问题。该问题仍然是一个二次规划问题，可以采用通用的QP算法求解，但求解规模正比于训练样本数。当样本数较大时，求解复杂度难以接受。序列最小化 Sequential Minimal Optimization (SMO) 算法是一种高效的求解算法。

序列最小化 SMO 算法

SMO算法流程如下：

利用SMO算法可以求解得到 $\alpha$α，从而得到 $w = \sum_{i=1}^{m}\alpha_iy_ix_i$w=∑i=1m​αi​yi​xi​，然后利用KKT条件求解 $b$b ：

根据KKT条件 $\alpha_i(1 - y_i(w^Tx_i+b)) = 0$αi​(1−yi​(wTxi​+b))=0，当 $\alpha_i \not = 0$αi​​=0 时，必然有 $1 - y_i(w^Tx_i+b) = 0$1−yi​(wTxi​+b)=0；而当 $1 - y_i(w^Tx_i+b) \not= 0$1−yi​(wTxi​+b)​=0 时，有 $\alpha_i = 0$αi​=0。原优化问题存在解且唯一，$w = \sum_{i=1}^{m}\alpha_iy_ix_i \not = 0$w=∑i=1m​αi​yi​xi​​=0， 所以必然存在 $\alpha_s\not = 0$αs​​=0，即 $y_s(w^Tx_s+b) = 0$ys​(wTxs​+b)=0，那么可以求解出 $b$b

$b = y_s - w^Tx_s$b=ys​−wTxs​

支持向量

进一步考虑 $w = \sum_{i=1}^{m}\alpha_iy_ix_i$w=∑i=1m​αi​yi​xi​，可以看出 $w$w 实际上是训练集样本的线性组合。并且，由约束条件：

$w$w 仅与那些满足 $1 - y_i(w^Tx_i + b ) = 0$1−yi​(wTxi​+b)=0 的样本有关。这些样本被称为支持向量，因此该模型也被称作支持向量机。

而这些支持向量恰好是落在决策边界上的点：

最终我们将上述结果代入到最初的模型中得到支持向量机的表示如下：
$h(x) = sign(\sum_{i \in SV}\alpha_iy_ix_i^Tx + b)$h(x)=sign(i∈SV∑​αi​yi​xiT​x+b)
其中， $sign(x)$sign(x) 是一个符号函数，$x<0$x<0 时 $sign(x) = -1$sign(x)=−1，$x>0$x>0 时 $sign(x) = 1$sign(x)=1。

核函数

支持向量机需要样本是线性可分的，从而可以寻找一个超平面分开。但是很多情况下，样本并非是线性可分的，而非线性可分的样本可以映射到一个更高维的线性空间中，使得样本在高维线性空间中是线性可分的。

令 $\phi (x)$ϕ(x) 表示 $x$x 映射到高维空间中的特征向量，那么SVM的基本型和对偶型为:

注意到，在支持向量的对偶型中，被映射到高维的特征向量总是以成对内积的形式存在，即 $\phi (x_i)^T \phi (x_j)$ϕ(xi​)Tϕ(xj​)。在求解确定支持向量的形式后：
$h(x) = sign(\sum_{i \in SV}\alpha_iy_i\phi (x_i)^T\phi (x) + b)$h(x)=sign(i∈SV∑​αi​yi​ϕ(xi​)Tϕ(x)+b)
在分类时也是使用待分类的特征向量的高维形式与支持向量的内积。那么实际上，我们没有必要知道每个样本 $x$x 或者其映射到高维空间的特征向量 $\phi(x)$ϕ(x)，只需要知道样本之间两两的内积即可。令核函数为：

$K(x_i, x_j) = \phi(x_i)^T\phi(x_j)$K(xi​,xj​)=ϕ(xi​)Tϕ(xj​)

映射到高维空间的函数 $\phi$ϕ 会比较难以确定，而且映射后两个高维特征的内积计算开销又非常大。那么是否可以直接定义一个核函数如 $K(x_i, x_j) = e^{-\|x_i - x_j\|^2}$K(xi​,xj​)=e−∥xi​−xj​∥2，使其能够代表两个样本映射到高维空间后的内积呢？

借助核函数，相当于使用一个隐式的高维映射函数，将数据转换到高维空间中进行分类。

软间隔SVM

不管直接在原特征空间，还是在映射的高维空间，我们都假设样本是线性可分的。虽然理论上我们总能找到一个高维映射使数据线性可分，但在实际任务中，寻找到这样一个合适的核函数通常很难。此外，由于数据中通常有噪声存在，我们放宽对样本的要求，即允许有少量样本分类错误。之前要求全部样本都要正确分类的SVM被称为硬间隔SVM，允许分类错误的样本成为软间隔SVM。

软间隔SVM允许一部分样本可以分类错误，但是这类样本应该尽可能少:

其中，$I()$I() 是指示函数, C 是个可调节参数，用于权衡优化间隔和少量分类错误样本这两个目标。$I()$I() 只能取值0/1，是离散的。为了能使优化问题继续保持为二次规划问题，我们需要引入一个取值为连续值的变量，刻画样本满足约束的程度：

那么：

上述等价于：

上面式子的前面部分即为 hinge loss，后面部分相当于正则化项。求解过程仍然可以用SMO求解，支持向量落在最大间隔边界、内部、被错误分类的样本上。