从最优化间隔器到核函数---SVM的推论（上）

Nov.22-2016

本文以及接下来的一篇文章将尝试详细的去描述SVM（支持向量机）这一经典的分类算法。SVM曾经被认很多人认为是最好的离线监督学习算法（不需要做什么修改即可使用），可以说至少在CV识别领域，在2012年的ImageNet比赛Alex使用CNN横空出世夺得第一之前，有长达10来年一直是kernel methods的天下。

本文以及接下来的文章将由简入繁一步步引入最终模型：它们分别是线性可分支持向量机，线性支持向量机以及非线性支持向量机，最后还将引入讨论序列最小最优化（SMO）算法，它是一个求解SVM的解的高效算法，该算法在1998年由微软研究院的Platt提出。

本文将讨论线性可分支持向量机和线性支持向量机，并导出它们的对偶形式。下文将引入核方法，使得SVM可以应用到非线性可分的情况中去，并讨论SMO算法。

在正式讨论前，先来给定我们的数据情况。给定一个特征空间上的训练集

$S = \{(x^{i}, y^{i}), i=1,2,...m\}$

其中，$x^{i} \epsilon R^{n}, y^{i} \epsilon{+1,-1}$。称$(x^{i}, y^{i})$为一个样本点，当$y^{i}$为正时称$x^{i}$为正例，反之为负例。

一、线性可分支持向量机（硬间隔最大化）

我们首先来讨论线性可分的情况，对线性可分的一个很直观的解释即在特征空间内存在一个超平面可以将正负两类完全分开。下图展示了特征空间为2维的线性可分情况。 Alt text

图中的黑色实线为其中一个解，它将我们的正负例进行了分开。我们定义该直线的表达式为

$w^{T}x + b = 0$

可以得到叉叉表示的正例点$x^{i}$满足$w^{T}x^{i} + b > 0$，而圆圈表示的负例点$x^{i}$满足$w^{T}x^{i} + b < 0$。所以我们定义分类器为：

$h_{w,b} (x)= g(w^{T}x + b)$

这里$g(z)=1$, 如果$z \geq 0$；否则$g(z) = -1$。即直线上侧的点被标记为正例，下侧的点被标记为负例。

先结合上图来看一个关于该分类器的直观感受。我们知道当点距离超平面越远，将该点带入超平面方程后得到的值的绝对值$|w^{T}x + b|$就越大（因为有负，所以说绝对值）。所以我们可以用一个点到分类面的远近来表示我们对分类问题的确信度。反应到分类器上有样本点$(x^{i},y^{i})$的确性度以及正确性可以用$y^{i}(w^{T}x^{i} + b)$来表示，这是因为$w^{T}x^{i} + b$与$y^{i}$的符号可以表示我们的分类正确与否，而上述绝对值又可以表明我们在正确分类下的确性度。可以看到在上图中，因为紫色点距离分类面较近，所以预测不那么确信，对应的值也较小；而红色点距离分类面较远，我们比较确信，对应的值也就较大。由这个直观感受，我们引入函数间隔以及几何间隔的概念。

a、函数间隔与几何间隔

我们将之前的表述进行形式化，定义点$x^{i}$到分隔面$(w, b)$的函数间隔为:

$\widehat{\gamma^{i}} = y^{i}(w^{T}x^{i} + b)$

同时定义训练集的函数间隔为所以样本点中的最小函数间隔：

$\widehat{\gamma} = min(\widehat{\gamma^{i}})$

因为该间隔代表了我们对于分类的确信度。为了使得我们的分类器尽可能的健壮，一个很容易想到的idea是我们寻找$(w, b)$训练集的函数间隔最大化即可。但是注意到一个问题：分隔面$w^{T}x + b = 0$与$2w^{T}x + 2b = 0$是完全相同的，但是此时函数间隔却增大了2倍 — 即我们可以任意的同时缩放w和b，它不影响分类面却影响了函数间隔的值，即我们可以任意选择函数间隔的值却不影响分类面函数。这种效果显然不是我们想要的。

一个解决该问题的方法是，我们使得$|w|$始终为1，这种想法与下面引入的几何间隔不约而同。我们观察如图所示的分类面： plot 定义该点到分隔面的距离为几何间隔$\gamma^{i}$。注意间隔面的法相为$w$（这一点很好证明：在间隔面上任意选两点$x_0,x_1$，我们有$w^{T}x_0 + b = 0$以及$w^{T}x_1 + b = 0$那么可以得到：$w^{T}(x_1 - x_0) = 0$。因为$x_0-x_1$ 可以表示分割面上的任意向量，而$w$与之垂直，那么$w$便是该分隔面的法向量）。下面来计算该距离，我们假设该点在分隔面上的投影为$x_0$，那么有:

$x_0 = x - \gamma^{i} \frac{w}{\|w\|}$

而$x_0$在分隔面上，将其带入分割面方程，我们解得点$x^{i}$关于分隔面$(w,b)$几何间隔为:

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

同时定义训练集的几何间隔为整个集合里的最小值，即:

$\gamma = \frac{\widehat{\gamma}}{\|w\|}$

可以看到几何间隔与我们之前的想法不谋而合。至此我们的目标便是寻找$(w,b)$使得几何间隔最小化。下面来正式定义线性可分情况下的支持向量机（硬间隔最大化）

b、硬间隔最大化的原始问题

给定数据集$(x^{i}, y^{i}),i=1,…m$，我们假设分隔面为$w^{T}x + b = 0$。那么我们的优化目标为:

$max \space \gamma$
$s.t \space \frac{y^{i}(w^{T}x^{i} + b)}{\|w\|} \geq \gamma$

注意到上式并不是一个凸优化问题，我们对其做个修改，由于我们有$\gamma = \frac{\widehat{\gamma}}{|w|}$，优化目标修改为关于$\widehat{\gamma}$的函数：

$max \space \frac{\widehat{\gamma}}{\|w\|}$
$s.t \space y^{i}(w^{T}x^{i} + b) \geq \widehat{\gamma}$

前面我们讨论过，我们可以随意修改$\widehat{\gamma}$的值而不影响任何一般性，所以这里我们令$\widehat{\gamma} = 1$，同时有最大化$\frac{1}{|w|}$与最小化$\frac{1}{2}|w|^{2}$是一样的，所以得到最终的优化问题为:

$min \space \frac{1}{2} \|w\|^{2}$
$s.t \space y^{i}(w^{T}x^{i} + b) \geq 1$

注意到上述优化目标，目标函数为一个二次函数，为凸。而约束条件为一个仿射函数，根据前面我们讲过的凸优化，可以看到这是一个凸优化问题（实际上为QP问题）。利用一般的QP软件都可以进行求解。当解得$(w^{\ast}, b^{\ast} )$后，我们便可以根据$h(x) = g(w^{T}x + b)$对任意的样本点进行分类了。值得注意的是由于上述问题是一个严格的凸优化问题，它是存在唯一全局最优解的，那么解出的$(w, b)$必然是存在且唯一的。

下面我们给出线性可分支持向量机（硬间隔最大化）的正式定义

硬间隔最大化分类器的原始算法 输入：线性可分训练数据集$(x^{i}, y^{i}), i=0,1,…m$，其中$x \epsilon R^{n}$，$y \epsilon {+1,-1}$ 输出：线性分类超平面和分类函数构造凸优化问题:

$min \space \frac{1}{2} \|w\|^{2}$
$s.t \space y^{i}(w^{T}x^{i} + b) \geq 1$

解得$w^{\ast}, b^{\ast}$，我们便得分离超平面:

$w^{\ast \space T} x + b^{\ast} = 0$

以及分类函数:

$h_{w,b}(x) = g(w^{\ast \space T}x + b^{\ast})$

其中有$g(z) = +1$ 如果$z \geq 0$，否则$g(z) = -1$。

c、支持向量与间隔边界

下面来简单讨论下支持向量机这一名字的来源。看下图我们得到的最终的优化结果: svm 图中黑色的为我们的分隔面$w^{T}x + b = 0$，两条绿色的线为使得$y^{i}(w^{T}x^{i} + b) = 1$成立的情况。很容易得到这两条线之间的距离为$\frac{2}{|w|}$，它们和$w$相关。而分离超平面位于它们之间，与它们平行，到它们的距离相等。注意一点，我们可以随意移动这两条线以外的数据点而完全不影响超平面

我们称距离分离超平面最近的点即使得$y^{i}(w^{T}x^{i} + b) = 1$成立的点为支持向量，我们可以看到只有支持向量会影响到分离超平面，它们在支持向量机中起着决定性作用，我们称这种模型为支持向量机。支持向量的数量相对于整体训练样本数来说是很少的，所以支持向量机是由少数重要样本决定的。

d、硬间隔最大化的对偶问题

下面我们将以前讨论过的凸优化问题的对偶问题应用到硬间隔最大化的原始问题上，这么做的目的是往往对偶问题能更好的求解，同时我们可以自然地引入核方法。

对原始问题构建拉格朗日函数，有:

$\ L(w, b, \alpha) = \frac{1}{2}\|w\|^{2} + \sum_{i}^{m}\alpha_i(1 - y^{i}(w^{T}x^{i} + b))$

我们分别对$w,b$求导，并设为0，有:

$\frac{\partial L}{\partial w} = w - \sum_{i}^{m}\alpha_i y^{i} x^{i} = 0$
$\frac{\partial L}{\partial b} = -\sum_{i}^{m}\alpha_i y^{i} = 0$

将上述结果代入拉格朗日函数，有：

$min_{w,b} \space L(w, b, \alpha) = -\frac{1}{2} \sum_{i}^{m} \sum_{j}^{m}\alpha_i\alpha_j y^{i} y^{j}(x^{i}.x^{j}) + \sum_{i}^{m}\alpha_i$

上面$(x^{i}.x^{j})$表示求内积。然后求上式的关于$\alpha$的最大值，便得到了关于原始问题的对偶问题：

$max -\frac{1}{2} \sum_{i}^{m} \sum_{j}^{m}\alpha_i\alpha_j y^{i} y^{j}(x^{i}.x^{j}) + \sum_{i}^{m}\alpha_i$
$s.t. \space \sum_i^{m} \alpha_i y^{i} = 0$
$\alpha_i \geq 0$

下面考虑原始问题与该对偶问题的KKT条件，假设$(w^{\ast}, b^{\ast})$为原始问题的解，$\alpha_i^{\ast}$为对偶问题的解，那么有:

$\frac{\partial L}{\partial w^{\ast}} = w^{\ast} - \sum_i^{m}\alpha_i^{\ast} y^{i}x^{i} = 0$
$\frac{\partial L}{\partial b^{\ast}} = -\sum_i^{m}\alpha_i^{\ast}y^{i} = 0$
$\alpha_i^{\ast}(1-y^{i}(w^{\ast T}x^{i} + b^{\ast})) = 0$
$\alpha_i^{\ast} \geq 0$
$y^{i}(w^{\ast T}x^{i} + b) \geq 0$

所以当我们解得对偶问题的$\alpha^{\ast}$后，可以求得：

$w^{\ast} = \sum_{i}^{m}\alpha_i^{\ast}y^{i}x^{i}$

同时对于某个$\alpha_j^{\ast} > 0$，我们有:

$1 - y^{j}(w^{\ast T}x^{j} + b^{\ast}) = 0$

我们可以解得：

$b^{\ast} = y^{j} - w^{\ast T } x^{j} = y^{j} - \sum_i^{m}\alpha_i^{\ast}y^{i}(x^{i}.x^{j})$

那么我们便得到了利用$\alpha^{\ast}$表示的分离超平面:

$\sum_i^{m}\alpha_i^{\ast}y^{i}(x^{i}.x^{j}) + b^{\ast} = 0$

以及决策函数:

$h(x) = g(\sum_i^{m}\alpha_i^{\ast}y^{i}(x^{i}.x^{j}) + b^{\ast} )$

至此我们阐述完成了关于硬间隔最大的对偶学习算法。下面做出一个总结。

硬间隔最大化分类器的对偶算法 输入：线性可分训练数据集$(x^{i}, y^{i}), i=0,1,…m$，其中$x \epsilon R^{n}$，$y \epsilon {+1,-1}$ 输出：线性分类超平面和分类函数构造凸优化问题:

$max -\frac{1}{2}\sum_i^{m}\sum_j^{m}\alpha_i\alpha_jy^iy^j(x^i.x^j) + \sum_i^{m}\alpha_i$
$s.t. \space \sum_i^{m}\alpha_iy^{i} = 0$
$\alpha_i \geq 0$

求解得到最优解$\alpha^{\ast} = (\alpha_0^{\ast}, \alpha_i^{\ast},…\alpha_m^{\ast})$后，我们求解:

$w^{\ast} = \sum_{i}^{m}\alpha_i^{\ast}y^{i}x^{i}$

然后对于某个$\alpha_j > 0$，求解得到:

$b^{\ast} = y^{j} - w^{\ast T } x^{j} = y^{j} - \sum_i^{m}\alpha_i^{\ast}y^{i}(x^{i}.x^{j})$

最后得到分离超平面:

$w^{\ast \space T} x + b^{\ast} = 0$

以及分类函数:

$h_{w,b}(x) = g(w^{\ast \space T}x + b^{\ast})$

其中有$g(z) = +1$ 如果$z \geq 0$，否则$g(z) = -1$。

观察一下，这里支持向量对应于$\alpha_i > 0$的点，这是因为当$\alpha_i > 0$，根据KKT互补条件有$1 - y^{j}(w^{\ast T}x^{j} + b^{\ast}) = 0$，正是我们原始问题中间隔面上的点。

二、线性支持向量机与软间隔最大化

我们上面描述的是当数据完全线性可分的情况，当有的数据点并不能线性可分时，上面描述的方法便不适用了。这是因为原始问题中的不等式约束条件在这种情况下不适用了。所以这里的线性不可分意味着有的点不能满足间隔大于等于1的约束。

为了解决这个问题，我们为每个样本点$(x^{i}, y^{i})$引入一个松弛变量$\xi_i \geq 0$，使得函数间隔可以在加上松弛变量后大于等于1，约束条件相应的变为:

$y^{i}(w^{T}x^{i} + b) \geq 1 - \xi_i$

同时我们让每个松弛变量都在原目标函数上付出一个代价，使得目标函数由原来的$\frac{1}{2}|w|^{2}$变为:

$\frac{1}{2}\|w\|^{2} + C\sum_i^{m}\xi_i$

这里$C \geq 0$叫做惩罚参数，它用于对误分类点进行惩罚，$C$越大对误分类的惩罚越大，越小对误分类的惩罚越小。所以现在目标函数有两层含义，使$\frac{1}{2}|w|^{2}$尽量小，即函数间隔尽量大，同时使得误分类点数尽量小，$C$是对它们两者之间的调和。将这个思路引进，我们便可以直接用线性可分时的思路来考虑该问题了，相比于硬间隔最大化，该算法叫做软间隔最大化

软间隔最大化的原始问题 输入：线性可分训练数据集$(x^{i}, y^{i}), i=0,1,…m$，其中$x \epsilon R^{n}$，$y \epsilon {+1,-1}$ 输出：线性分类超平面和分类函数构建优化问题：

$min\frac{1}{2}\|w\|^{2} + C\sum_i^{m}\xi_i$
$s.t. \space y^{i}(w^{T}x^{i} + b) \geq 1 - \xi_i$
$\xi_i \geq 0$

解得$w^{\ast}, b^{\ast}$，我们便得分离超平面:

$w^{\ast \space T} x + b^{\ast} = 0$

以及分类函数:

$h_{w,b}(x) = g(w^{\ast \space T}x + b^{\ast})$

其中有$g(z) = +1$ 如果$z \geq 0$，否则$g(z) = -1$。

可以看到相比于硬间隔最大化，分离超平面以及分类函数并没有变化。注意到该原始问题仍然是一个凸优化问题，所以仍然是有解的。

同样的对于该原始问题，我们也构造出其对偶问题，原始问题对应的拉格朗日函数为:

$\ L (w, b, \xi, \alpha, \mu) = \frac{1}{2}\|w\|^{2} + C\sum_i^{m}\xi_i + \sum_i^{m}\alpha_i(1-\xi_i-y^{i}(w^{T}x^{i} + b)) - \sum_i^{m}\mu_i\xi_i$

同理，我们分别对$w,b,\xi$求偏导并赋零得到：

$\frac{\partial L}{\partial w} = w - \sum_{i}^{m}\alpha_i y^{i} x^{i} = 0$
$\frac{\partial L}{\partial b} = -\sum_{i}^{m}\alpha_i y^{i} = 0$
$C - \alpha_i - \mu_i = 0$

我们将其带回拉格朗日函数得到：

$min_{w,b,\xi} \space L(w, b, \alpha) = -\frac{1}{2} \sum_{i}^{m} \sum_{j}^{m}\alpha_i\alpha_j y^{i} y^{j}(x^{i}.x^{j}) + \sum_{i}^{m}\alpha_i$

所以我们得到该原始优化问题的对偶问题为:

$max -\frac{1}{2}\sum_i^{m}\sum_j^{m}\alpha_i\alpha_jy^iy^j(x^i.x^j) + \sum_i^{m}\alpha_i$
$s.t. \space \sum_i^{m}\alpha_iy^{i} = 0$
$C - \alpha_i - \mu_i = 0$
$\alpha_i \geq 0$
$\mu_i \geq 0$

将$C - \alpha_i - \mu_i = 0$带回最后一个不等式，我们可以消去$\mu_i$，得到只关于$\alpha_i$的约束条件: $0 \leq \alpha_i \leq C$。

在得到对偶问题的解$\alpha^{\ast}$后，我们便可以解得$w^{\ast}$以及利用KKT互补条件，对任意$0 \leq \alpha_i^{\ast} \leq C$，我们和以前一样可以解得$b^{\ast}$（为什么？读者可以和之前一样利用KKT互补条件来推导一下），然后将$w^{\ast}$和$b^{\ast}$带回便可以得到我们的分类面以及分类函数了。