资料参考来源：

清华大学出版社 周志华 《机器学习》 第六章

清华大学出版社 李航 《统计学习方法》 第二章 感知机，第七章 支持向量机

第六讲：事件模型、函数间隔与几何间隔

第七讲：最优间隔分类器、拉格朗日对偶、支持向量机

cs229 lecture 3 support vector machine

支持向量机（support vector machine ,SVM）是一种二类分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；支持向量机还包括核技巧，这使它成为实质上的非线性分类器。

感知机

在学习支持向量机之前我们需要先引入感知机模型：

假设输入空间（特征空间）是$X \subseteq R^n$，输出空间是$y=\{+1,-1\}$，并且，由输入空间到输出空间的如下函数：

便称为感知机。

其中，w和b为感知机的模型参数，$w∈R^n$叫做权值（weight）或者权值向量（weight vector），$b∈R$叫做偏置（bias），$w·x$表示w和x的内积。sign是符号函数，即：

即函数的输入如果大于0，函数就输出+1，如果小于零，就输出-1.

感知机是一种线性分类模型，属于判别模型的一种。

感知机模型的假设空间是定义在特征空间中的所有线性分类模型（linear classification model）或线性分类器(linear classifier)，即函数集合$\{f\mid f(x)=wx+b\}$。

感知机的几何解释即为线性方程：

这个方程对应于特征空间$R^n$中的一个超平面(hyperplane)S，其中w是超平面的法向量，b是超平面的截距。这个超平面通过将特征空间分成两个部分，来达到分类的作用，其中分开的两部分一部分为正类，一部分为负类。因此，超平面S也被称为分离超平面（separating hyperplane），如图所示：

点到超平面的距离

另外，我们这里还要介绍一下如何计算点到超平面的距离，这个距离关系到我们在学习支持向量机中对间隔的计算，并且，我们在之前的学习中（Python 机器学习实战 第四章 kd树）中也有用到，因此我确实有必要详细地介绍一下这个内容。

我们在之前就已经知道了，点到超平面的欧氏距离公式为：

其中w为超平面法向量，b为超平面截距这个已经介绍过了，x则是点在特征空间中的坐标，$\mid\mid w\mid\mid$为w的$L_2$范数，即w的模。

这个式子的来源其实并不复杂，因为我们知道，在三维空间中，如果要计算一个点到平面的距离，我们有公式：

这个公式与上面一对比，我想我们已经可以猜出些什么了。超平面实际上在特征空间中也不过是一个平面，因此，我们若要计算点到超平面的距离，实际上就是计算多维空间中的一个点到这个多维空间中的平面的距离。

现在我们来简单推导一下如何计算点到平面的距离：

已知点$x_0$，超平面$w·x+b=0$，设点到平面的投影为$x_1$，则向量$\vec{x_0x_1}$的模即为点到平面的距离。

并且，我们知道超平面的法向量为w且该向量与向量$\vec{x_0x_1}$平行。另外，w标准化后的单位向量为$\frac{w}{\mid\mid w\mid\mid}$。单位方向向量的模为1，因此有等式：

其中d为点到超平面的距离，因为d是正数，所以有：

又因为$x_1$在超平面上，因此有：

所以代入得到距离公式：

线性可分支持向量机与硬间隔最大化

函数间隔和几何间隔

我们在开头说过，支持向量机的基本模型是定义在特征空间上的间隔最大的分类间隔器。支持向量机与感知机的区别就在于此：对于线性可分的训练数据集而言，线性可分分离超平面有无穷多个（感知机），但是几何间隔最大的分离超平面却是唯一的。这里的间隔最大化，又称为硬间隔最大化（与我们将要讨论的训练数据集近似线性可分时的软间隔最大化相对应）

间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。也即是说，间隔最大化不仅将明显的正负类样本点分开，而且对于最难分的样本点（那些离超平面最近的点）也能有足够的确信度将它们分开，这样的超平面应该对未知的测试样本有很好的分类预测能力，关于这点，我们后面再做详细讨论。

我们先来讨论一下如何求解间隔。

函数间隔

在下图中，有A，B，C三个点分别表示3个样本，它们均在分离超平面的一侧：

点A距离超平面较远，如果我们预测该点为正类，那么我们有很大的把握确信我们的预测是正确的；而点c距离分离超平面较近，如果我们叶预测该点为正类，相较于A就会不那么确信；点B在A点和C点之间，因此我们预测点B为正类的确信度就会在A与C之间。

为了描述这种情况，我们便要引入函数间隔的概念（functional margin）：

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

支持向量机中引用的感知机表示训练样本集的概念，因此这里的$y_i=1或-1$.

而方程$w·x+b$ 的绝对值则能够相对地表示点x距离分类超平面的远近，而它的符号与类标记y的符号是否一致反映了这个分类的正确与否。注意，这里的$wx+b$ 并不表示一个平面，它是一个基本输出函数，类似于$h_θ(x)=g(θ^Tx)$，但在这里只是将形式换成了$h_{w,b}=g(w^T·x+b)$，$b$与$θ_0$对应。

因此，$w·x_i+b$的值才会表示样本$(x_i,y_i)$距离超平面相对其它样本的距离的大小。

然后，我们定义超平面（w，b）关于训练样本集T的函数间隔为超平面（w，b）关于T中所有样本的函数间隔中的最小值：

(N为训练样本总数) 因此，函数间隔越大，往往就意味着越高的准确性和确信度。

但是，函数间隔有一个缺点：当我们在选择超平面时，如果等比例的增大超平面的w和b，它的超平面不会变，但它的函数间隔却会变大。举个例子，假设有超平面$w_1x+b_1=0$和超平面$2w_1x+2b_1=0$，我们可以很明显地看出第二个超平面实际上就是第一个超平面，但如果，我们分别用它们来计算函数间隔，那么用第二个方程算出来地函数间隔就会是第一个函数间隔的2倍。

为了解决这个问题，我们便需要引入几何间隔。

几何间隔

几何间隔（geometric margin）引入了对超平面法向量的约束条件，或者说，规范化了超平面的法向量w。

例如，我们规定$\mid\mid w\mid\mid=1$，这个时候，w和b就不能随意地倍增，因为如果我们倍增w会改变$\mid\mid w\mid\mid$，那么$\mid\mid w\mid\mid=1$就无法成立了。

因此，我们在将规范条件引入函数间隔后得到的几何间隔中样本点$x_i$与超平面的距离表达式就变为了：

将$\mid\mid w\mid\mid$提出来我们可以发现，这其实就是点到超平面欧氏距离的表达式。

藉此，我们还可以得到超平面（w，b）关于训练集T的几何间隔，为超平面（w，b）关于T中所有样本点$(x_i,y_i)$的几何间隔的最小值，即：

因此，我们还可以得到，函数间隔和几何间隔的关系：

如果$\mid\mid w\mid\mid=1$，那么函数间隔就会和几何间隔相等。

间隔最大化分类器

最大间隔分离超平面

下面我们来考虑如何求得一个几何间隔最大的分离超平面，即最大间隔分离平面。

具体地，这个问题可以表示为下面的约束最优化问题：

意思是，我们希望最大化超平面（w，b）关于训练集的几何间隔γ，约束条件（s.t. ，即subject to，表示“受限于”）表示的是超平面（w，b）关于每个训练样本点的几何间隔至少是γ。在这个式子中，我们曾对$\mid\mid w\mid\mid$做出$\mid\mid w\mid\mid=1$的假设以便约束w为标准化向量，或者说，让一个γ值只对应一个超平面。

但事实上，这是一个非常糟糕的假设。之所以这么说，是因为这是一个非凸性约束，即我们无法将这个假设提交给标准的凸优化软件（如梯度下降，牛顿法等）来解决问题。为了解释这段话，我想我得在这里先插入一点关于凸优化的内容：

凸优化

以下内容来源参考：

王业磊 知乎 在数学中一个非凸的最优化问题是什么意思？

凸优化 百度百科

“求解最优化问题”指对一个给定函数求让这个函数达到最大或最小值的解。

但是，这种问题在数学中大多数时候是无法被我们直接解决的，因为这些难以解决的优化问题的形式给出的函数是非凸的，这种凸函数的局部最优解不能代表全局最优解，这就使得我们对其求解的难度也会非常大。

凸优化问题则与非凸不同，凸优化问题给出的凸函数的局部最优解就是全局最优解，并且凸优化仅指求使凸函数达到最小值得参数，因此，梯度下降或者牛顿法这一类求解最优解的方法实际上只适合在凸优化问题中使用。

所以，为了解决非凸优化问题，人们往往需要找方法将非凸优化问题转化成凸优化问题，因为凸优化问题才是我们擅长求解的问题类型。

凸优化问题的数学解释：

1. 函数的参数x属于凸集X，即对任意$x_1,x_2∈X$都有$tx_1+(1-t)x_2∈X，t∈[0,1]$，也就是说，该集合中任意两点的连线都应该在集合内： 上面这就是一个非凸集，然后下面就是一个凸集
2. 给定的函数f是凸函数。即对于定义域X中任意两点有$f(tx_1+(1-t)x_2)≥tf(x_1)+(1-t)f(x_2),t∈[0,1]$ ，几何上看就是函数图形向下凸出:

实际中我们判断一个问题是不是凸优化问题看以下三点：

1. 目标函数f是否是凸优化函数，如果不是，则不是凸优化问题
2. 决策变量x中是否包含离散变量，如果是则不是凸优化问题
3. 约束条件写成$g(x)≤0$时，g如果不是凸函数，则不是凸优化问题。

《统计学习方法》上关于凸优化问题的解释：

凸优化问题指约束最优化问题

其中，目标函数f(w)和约束函数$g_i(w)$都是$R^n$上的连续可微的凸函数，约束函数$h_i(w)$是$R^n$上的仿射函数（如果一个函数$f(x)$满足$f(x)=a·x+b,a∈R^n,b∈R,x∈R^n$那么这个函数就被称为仿射函数）。

当目标函数f(w)是二次函数且约束函数$g_i(w)$是仿射函数时，上述凸最优化问题就会成为凸二次规划问题。

续 最大间隔分离超平面

因此，为了将问题转化为凸优化问题，我们通过函数间隔和几何间隔的关系，可以将这个式子改写成如下的形式：

函数间隔$\hat{γ}$的取值并不影响最优化问题的解。为什么这么说呢，因为事实上假设我们将w和b按比例改变为λw和λb，函数间隔就会变成$λ\hat{γ}$，这一改变对上面的最优化问题的不等式约束没有影响，也就是说，它产生一个等价的最优化问题。

这样，我们就可以取$\hat{γ}=1$，将$\hat{γ}=1$代入上面的最优化问题，注意到最大化$\frac{1}{\mid\mid w\mid\mid}$和最小化$\frac{1}{2}\mid\mid w\mid\mid^2$使等价的，于是，我们就可以得到下面的线性可分支持向量机学习的最优化问题：

这样，这个问题就转化为了一个凸二次规划(convex quadratic programming)问题。

如果我们求出了上述约束最优化问题的解$w^*,b^*$，那么就可以得到最大间隔分离超平面$w^*x+b^*=0$以及分类决策函数$f(x)=sign(w^*x+b^*)$，即线性可分支持向量机模型。

综上所述，我们就有了下面的线性可分支持向量机学习算法，最大间隔法(maximum margin method)

算法

输入：线性可分分训练数据集$T=\{(x_1,y_1),...,(x_N,y_N)\}$，其中，$x_i∈X=R^n$，$y_i∈Y=\{-1,+1\},i=1,2,...,N$

输出：最大间隔分离超平面和分类决策函数

步骤：

1.构造并求解约束最优化问题：

求得最优解$w^*,b^*$（求解的具体方法除了梯度下降或牛顿法，还有对偶算法，这个我们会在之后讨论）

2.由此得到分离超平面：

分类决策函数

最大间隔分离超平面的存在唯一性

我们知道，线性可分训练数据集的最大间隔分离超平面是i存在且唯一的。即：

下面我们来证明一下这个定理：

1.存在性

由于训练数据集线性可分，所以上面算法小节中的最优化问题一定存在可行解。又由于目标函数有下界， 所以该最优化问题必有解，我们将这个解记作$(w^*,b^*)$。又由于训练数据集中既有正类点和负类点，所以$(w,b)=(0,b)$不是最优化的可行解，因而最优解$(w^*,b^*)$必满足$w^*≠0$。由此得知分离超平面的存在性。

2.唯一性

我们首先要证明最优化问题的解中$w^*$的唯一性。假设上述最优化问题存在两个最优解$(w_1^*,b_1^*)$和$(w_2^*,b_2^*)$.显然$\mid\mid w^*_1\mid\mid=\mid\mid w^*_2\mid\mid=c$，其中c时一个常数。令$w=\frac{w_1^*+w_2^*}{2},b=\frac{b_1^*+b_2^*}{2}$，已知$(w,b)$是该优化问题的可行解，从而有

上式表明，式中的不等号可变为等号，即

从而有$w_1^*=λw_2^*$（因为$w=\frac{w_1^*+w_2^*}{2}$所以$\mid\mid \frac{w_1^*+w_2^*}{2}\mid\mid=c$，又因为$\mid\mid w^*_1\mid\mid=\mid\mid w^*_2\mid\mid=c$），且$\mid λ\mid=1$，若$λ=-1$，则$w=0$，$（w，b）$不是该最优化问题的可行解，矛盾，因此必有$λ=1$,即

这样我们就证明了$w$的唯一性，接下来我们藉由这个式子证明b的唯一性：

我们先把我们之前假设的最优解分别写为$(w^*,b_1^*)$和$(w^*,b_2^*)$，我们的目的时证明$b_1^*=b_2^*$。

设$x_1',x_2'$是集合$\{x_i\mid y_i=+1\}$中分别对应于$(w^*,b_1^*)$和$(w^*,b_2^*)$使得问题的不等式等号成立的点，$x_1''$和$x_2''$是集合$\{x_i\mid y_i=-1\}$ 中分别对应于$(w^*,b_1^*)$和$(w^*,b_2^*)$使得问题的不等式等号成立的点，（即分别设$x_1',x_2',x_1'',x_2''$为正类和负类中两个最接近两个分离超平面的点（离超平面的距离即为超平面距离数据集的几何间隔的距离的点）），则由$b_1^*=-\frac{1}{2}(w^*·x_1'+w^*·x_1'')$,$b_2^*=-\frac{1}{2}(w^*·x_2'+w^*·x_2'')$ （因为$y_i(w·x_i'+b)-1=0$），我们可以得到

又因为

（这里是因为我们假设两个解$(w_1^*,b_1^*)$和$(w_2^*,b_2^*)$不同，所以$x_1'$离分离超平面$(w_1^*,b_1^*)$最近，那么$x_2'$就应该离该超平面相对$x_1'$较远或者距离相同，第二条式子也是一样，只不过将第二个超平面作为讨论对象）

所以，$w^*·(x_1'-x_2')=0$。同理$w^*·(x_1''-x_2'')=0$,因此，

由此我们可以证明，两个最优解$(w_1^*,b_1^*)$和$(w_2^*,b_2^*)$是相同的，解的唯一性由此得证。

因此，分离超平面也是唯一的。又因为数据集是线性可分的，并且解满足问题的约束条件，所以这个分离超平面能够将训练数据集（注意只是训练数据集，不是测试数据集）中的两类点完全正确的分开。

支持向量和间隔边界

在线性可分的情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例（或说，输入向量）成为支持向量（support vector）。换句话说，支持向量就是使上述最优化问题中的约束条件式等号成立的点：

对$y_i=+1$的正例点，支持向量在超平面

上。

对$y_i=-1$的负例点，支持向量在超平面

上。

如图所示，在$H_1$和$H_2$上的点就是支持向量：

很显然，$H_1$和$H_2$平行，并且没有实例点可以落在它们中间。在$H_1$和$H_2$中间有一条长带，分离超平面与它们平行并且位于它们中央。长带的宽度，即$H_1$与$H_2$之间的距离便称为间隔（margin）。间隔由分离超平面的法向量w决定，间隔的值等于$\frac{2}{\mid\mid w\mid\mid}$，$H_1$和$H_2$称为间隔边界。

在决定分离超平面的时候只有支持向量起作用，也就是说，我们若改变间隔边界之外的点甚至是删除这些点，也是不会该bain解的。

正因此，支持向量在确定分离超平面中起着决定性的作用，所以我们价格你这种分类模型称为至此向量机。支持向量的个数一般很少，所以，支持向量机由很少的“重要的”训练样本确定。

例子

我们来看一个应用支持向量机简单例子

假设有一个数据集

，试求这个数据集的最大间隔分离超平面。

根据最大间隔算法，我们构造最优化问题为：

（$w=(w_1,w_2)^T$）

求得此最优化问题的解$w_1=w_2=\frac{1}{2},b=-2$，于是我们有最大间隔分离超平面：

其中，$x_1$与$x_3$为支持向量。

学习的对偶算法

要求解线性可分支持向量机的最优化问题，我们可以将它作为原始最优化问题，应用拉格朗日对偶性，通过求解对偶问题（dual problem）得到原始问题（primal problem）的最优解，这就是线性可分支持向量机的对偶算法（dual algorithm）。

这样做的优点有两个，一是对偶问题往往更容易求解；二是通过自然引入核函数，能够将线性分类问题进而推广到非线性分类问题。

为了能够理解上面这段话，我们先来了解一下拉格朗日对偶性的含义：

拉格朗日对偶性

以下内容来自 《统计学习方法》 附录C

在约束最优化问题中，我们常常利用拉格朗日对偶性（Lagrange duality）将院士问题转换为对偶问题，通过求解对偶问题来得到原始问题的解。

原始问题

我们首先了解一下什么是原始问题，并且如何将原始问题转化成拉格朗日的极小极大问题：

假设$f(x),c_i(x),h_j(x)$是定义在$R^n$上的连续可微函数。考虑约束最优化问题：

我们称此约束最优化问题为原始最优化问题或原始问题。

然后，我们引进广义拉格朗日函数（generalized Lagrange function）:

这里，$x=(x^{(1)},x^{(2)},...,x^{(n)})^T∈R^n$，$α_i,β_j$是拉格朗日乘子，$α_i≥0$。考虑x的函数：

其中，下标P表示原始问题。

假设给定某个x，如果x违反原始问题的约束条件，即存在某个i使得$c_i(w) > 0$或者存在某个j使得$h_j(w)≠0$，那么就有：

因为很显然，如果有$c_i(x) > 0$，那么我们可以另$α_i\rightarrow +\infty$，这个项就会趋向于无穷大，因此只有当所有的$c_i(x)≤0$时函数才符合条件；同理，若有$h_j(x)≠0$，我们就可以令$β_j\rightarrow +\infty$，那么就会有$β_jh_j(x)\rightarrow +\infty$。

相反地，如果x满足约束条件式(即$c_i(x)≤0,h_j(x)≠0$),则由上面两个函数（$L(x,α,β)，θ_P(x)$）的式子可知$θ_P(x)=f(x)$。因此，我们有

所以，如果考虑极小化问题

它是与原始约束最优化问题等价的（因为约束条件成立的时候$max_{α,β:α_i≥0}L(x,α,β)=f(x)$），也就是说，二者具有相同的解。

这样一来，我们就将原始问题表示为广义拉格朗日函数的极小极大问题（$min_xmax_{α,β:α_i≥0}L(x,α,β)=f(x)$）。为了方便，我们定义原始问题的最优值为

称为原始问题的值。

对偶问题

首先我们定义

再考虑极大化$θ_D(α,β)=min_xL(x,α,β)$,即

这个问题我们称为广义拉格朗日函数的++极大极小++问题。

我们可以将广义拉格朗日函数的极大极小问题表示为约束最优化问题：

这个最优化问题就称为原始问题的对偶问题。我们定义对偶问题的最优值

称为对偶问题的值。

原始问题和对偶问题的关系

下面我们讨论原始问题和对偶问题的关系：

如果原始问题和对偶问题都有最优值，则有定理：

现证明如下：

首先我们知道，对任意的α，β和x，有

即

由于原始问题和对偶问题均有最优值，所以：

展开就得到

由这条定理，我们得到一个推论：

推论C.1

设$x^*和α^*,β^*$分别是原始约束最优化问题

和对偶约束最优化问题

的可行解，并且两个问题的最优值$p^*=d^*$，则$x^*$和$α^*,β^*$就分别是原始问题和对偶问题的最优解。

因此，如果在某些条件下，原始问题和对偶问题的最优值相等，即$d^*=p^*$，这个时候，我们就可以通过解对偶问题替代解原始问题。

下面我们再藉此得到两个定理

定理C.2

对原始约束最优化问题和对偶约束最优化问题（就是推论C.1中我们讨论的那两个），假设函数f(x)和$c_i(x)$是凸函数（当f的海森矩阵半正定时，f是凸函数，海森矩阵的定义（也可以在我们讨论“牛顿法”的一章中查看）：

黑塞矩阵即海森矩阵），$h_j(x)$是仿射函数；并且假设不等式约束$c_i(x)$是严格可行的，即存在x对所有的i有$c_i(x) < 0$，

则存在$x^*,α^*,β^*$，使$x^*$是原始问题的解，$α^*,β^*$是对偶问题的解，并且

定理C.3 KKT

对原始约束最优化问题和对偶约束最优化问题，我们假设函数$f(x)$和$c_i(x)$是凸函数，$h_j(x)$是仿射函数，并且不等式约束$c_i(x)$是严格可行的，则存在$x^*,α^*,β^*$，使$x^*$是原始问题的解，$α^*,β^*$是对偶问题的解的充分必要条件是$x^*,α^*，β^*$满足下面的KKT（Karush-Kuhn-Tucker）条件：

特别指出，$α_i^*c_i(x^*)=0,i=1,2,...,k$称为KKT的对偶互补条件。由此条件可知：若$α^*_i > 0$，则$c_i(x^*)=0$

这个其实就是《高等数学》中求条件极值的拉格朗日乘数法的拓展。

续 学习对偶问题

现在我们来将拉格朗日对偶性引入到求解线性可分支持向量机的最优化问题：

首先我们要构建拉格朗日函数（Lagrange function）。 通过对每一个不等式约束引进拉格朗日乘子（Lagrange multiplier）$α_i≥0,i=1,2,...,N$，我们可以得到拉格朗日函数：

其中$α=(α_1,α_2,...,α_N)^T$为拉格朗日乘子向量。

根据拉格朗日对偶性，我们得到原始问题的对偶问题，即极大极小问题：

所以，为了得到对偶问题的解，我们需要先求$L(w,b,a)$对w,b的极小，再求对α的极大。

（1）求$min_{w,b}L(w,b,a)$

我们将拉格朗日函数$L(w,b,a)$对w,b分别求偏导数并令其等于0

得到

将上面关于w的等式代入拉格朗日函数，并利用$\sum^N_{i=1}α_iy_i=0$得到：

即

（2）求$min_{w,b}L(w,b,α)$对α的极大

也即是求对偶约束最优化问题：

我们做一点改变，将这个问题由求极大转换成等价的求极小的对偶最优化问题：

我们再看到原始最优化问题，因为原始最优化问题满足定理C.2（即$f(w)=\frac{1}{2}\mid\mid w\mid\mid^2$和$c_i(x)=1-y_i(wx_i+b)$是凸函数，对所有i有$c_i(x) < 0$），所以，存在$w^*,α^*,β^*$，使得$w^*$是原始问题的解，$α^*，β^*$是对偶问题的解。

此时，我们就可以将求解原始问题转换成求解上面的对偶问题。

对线性可分训练数据集，假设对偶最优化问题对α的解为$α^*=(α_1^*,...,α_N^*)^T$我们可以由$α^*$求得原始最优化问题对(w,b)的解$(w^*,b^*)$。并有下面的定理

定理7.2

设$α^*=(α^*_1,...,α_l^*)^T$是上述对偶最优化问题的解，则存在下标j，使得$α_j^* > 0$，并可按下式求得原始最优化问题的解$w^*,b^*$为：

我们可以通过定理C.3的KKT条件证明这个定理：

由此得到

其中至少有一个$α^*_j > 0$

（我们可以用反证法证明，首先假设$α^*=0$，由$\nabla_wL(w^*,b^*,α^*)=w^*-\sum^N_{i=1}α_i^*y_ix_i=0$可知$w^*=0$，但是$w^*=0$显然不能是原始最优化问题的解，产生矛盾）

，对这个j有

我们将$w^*=\sum^N_{i=1}α^*_iy_ix_i$代入到上面的式子中，我们就可以得到

(注意，$y^2_j=1$)

由此定理可知，分离超平面可以写成

分类决策函数便可以写成

从这里我们可以看出来分类决策函数仅由输入x和训练样本输入的内积决定。这个式子又称为线性可分支持向量机的对偶形式。

综上，对于给定的线性可分训练数据集，我们可以首先求对偶问题的解$α^*$，再利用$w^*=\sum^N_{i=1}α^*_iy_ix_i$和$b^*=y_j-\sum^N_{i=1}α^*_iy_i(x_i·x_j)$求得原始问题的解$w^*,b^*$；从而得到分离超平面与分类决策函数。

这种算法便称为线性可分支持向量机的对偶学习算法，是线性可分支持向量机的基本算法。

下面我们来看一下这个算法的基本流程

算法 线性可分支持向量机的对偶学习方法

输入：线性可分训练$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$，其中$x_i∈X=R^n,y_i∈Y=\{-1,+1\},i=1,2,...,N$

输出：分离超平面和决策函数

步骤：

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

求得最优解$α^*=(α^*_1,...,α^*_N)^T$

2.计算

并选择$α^*$的一个正分量$α^*_j > 0$计算

3.求得分离超平面

分类决策函数：

我们知道，$w^*,b^*$仅由训练数据中对应于$α_i^* > 0$的样本点$(x_i,y_i)$决定，而其它样本点对$w^*$和$b^*$没有影响。我们将这些能够造成影响的样本点（即对应于$α_i^* > 0$的实例点$x_i∈R$）称为支持向量。

根据这一个定义，我们可以知道支持想向量一定在间隔边界上。由KKT互补条件可知，

对应于$α^*_i > 0$的实例$x_i$，有

或者

就是$x_i$在间隔边界上的数学表示。

小结

一般来说，在这种信息量比较大的学习之后，我都有必要做个简单的总结：

1.问题

给定一个特征空间上的训练集$T=\{(x_1,y_1),...,(x_N,y_N)\}$,求能够将训练集以最大间隔分开的分离超平面与相应的分类决策函数。

2.原始问题

将问题转化成原始问题的形式：

由于该问题不是凸优化问题不方便解决，我们需要先转换其形式为函数间隔：

然后设$\hat{γ}=1$得到（因为函数间隔的数值不影响超平面的具体位置）

将$max_{w,b}~~~\frac{1}{\mid\mid w\mid\mid}$转换成求最小值的模式以转换成凸二次规划问题

最大间隔分离超平面存在且唯一。

3.对偶算法