一文读懂SVM（支持向量机：硬间隔最大化，软间隔最大化，核函数，SMO算法）

丝瓜蛋汤

已于 2025-04-27 08:59:09 修改

阅读量1k

点赞数 21

文章标签：支持向量机算法机器学习

于 2025-04-26 23:50:24 首次发布

本文链接：https://blog.csdn.net/kexin197/article/details/147521437

版权

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

SVM是最大间隔分类器，在线性可分的情况下，不存在误分类点。用数学语言表示最大间隔分类器：

约束条件的意思是模型求得的值和真实值相乘大于零说明是正确分类的点。

这边由于w只和max中有关系，所以可以从后面的式子提到前面来，距离公式可以参见感知机算法部分SVM基础：感知机梳理-CSDN博客

由可知：

这里涉及了函数间隔和几何间隔的概念，如果超平面参数w和b成比例地改变（超平面没有改变），函数间隔也按此比例改变，而几何间隔不变。既然函数间隔会随w和b变化，那不妨设r=1，这样，式子可以写成：

再进一步变形，得到：

从而变成一个凸二次规划问题，其具体含义可以参见下文

凸优化理论，凸二次规划问题，对偶问题及KKT条件-CSDN博客

将式子转化成拉格朗日函数形式：

其中，如果此项大于0，则解会趋于无意义的无穷解，所以约束条件必然满足。

由于式子满足强对偶关系，（强弱对偶关系，slater条件，KKT条件可以参见下文）

什么是KKT 条件（Karush-Kuhn-Tucker 条件）_kkt条件-CSDN博客

强对偶性、弱对偶性以及KKT条件的证明（对偶问题的几何证明）_强对偶关系-CSDN博客

求原问题

可以转化成求其对偶问题：

接下来对式子中的w,b分别求偏导为0，得到：

代入原式，得到

由于KKT条件成立，根据KKT条件可得：

设是对偶最优化问题的解，则存在，使得按照下式能求得原始最优化问题的解

从而可得分离超平面

和分类决策函数

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

证明定理内容：若训练数据集T线性可分，则可将训练数据集中的样本点完全正确分开的最大间隔分离超平面存在且唯一。

（1）存在性

由线性可分；目标函数有下界；训练集有正类点和负类点，所以（w,b）=（0,b）不是最优化的可行解可知

（2）唯一性

反证法：假设有两个最优解,C是一个常数。

令

将w和b代入可知，w和b是问题可行解。

是最优解，w是可行解，所以下式必然成立

这说明这两个向量必然同方向

下证

假设是决定的超平面使得问题不等号成立的点，是决定的超平面使得问题不等号成立的点，且属于集合{xi|yi=+1}，属于集合{xi|yi=-1}

从而有

所以

代入上式可得

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

软间隔最大化允许一点点错误（一部分误分类点）

引入hinge loss

令（松弛变量）可得

这里，C>0 称为惩罚参数，最小化目标函数包含两层含义，让间隔尽量大，同时误分类点的个数尽量小。

将式子转化成拉格朗日函数形式：

$\mathcal{L}(w,b,\xi,\alpha,\mu)=\frac{1}{2}w^Tw+{\rm C}\sum_{i=1}^{N}\xi_{i}-\sum_{i=1}^N\alpha_i(y_i(w^Tx_i+b)-1+\xi_{i})-\sum_{i=1}^N\mu_{i}\xi_{i}$

对偶问题是朗格朗日函数的极大极小问题，先求内层的极小问题，分别对w,b,求偏导等于0，得到

将上式代入拉格朗日函数后对求极大，

由于KKT条件成立，根据KKT条件可得：

设是对偶最优化问题的解，则存在，使得按照下式能求得原始最优化问题的解

从而可得分离超平面

和分类决策函数

将的样本点(xi,yi)的实例xi称为支持向量。软间隔的支持向量或者在间隔边界上，或者在间隔边界和分离超平面之间，或者在分离超平面误分一侧。

根据条件

可知，

若

四种情况

非线性支持向量机与核函数

Cover's Theorem 阐述了这样一个事实：在高维空间中，几乎所有的分类问题都是线性可分的。

核技巧：线性分类方法求解非线性分类问题分为两步：首先使用一个变换将原空间的数据映射到新空间；然后在新空间里用线性分类学习方法从训练数据中学习分类模型。核技巧的想法是，在学习与预测中只定义核函数K（x,z），而不显式地定义映射函数ϕ。

核函数(Kernel function)-CSDN博客

SMO算法（序列最小最优化算法）

SMO算法是一种启发式算法，其基本思路是：如果所有变量的解都满足此最优化问题的KKT条件（Karush-Kuhn-Tucker conditions），那么这个最优化问题的解就得到了。因为KKT条件是该最优化问题的充分必要条件。否则，选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题。这个二次规划问题关于这两个变量的解应该更接近原始二次规划问题的解，因为这会使得原始二次规划问题的目标函数值变得更小。重要的是，这时子问题可以通过解析方法求解，这样就可以大大提高整个算法的计算速度。子问题有两个变量，一个是违反KKT条件最严重的那一个，另一个由约束条件自动确定。如此，SMO算法将原问题不断分解为子问题并对子问题求解，进而达到求解原问题的目的。注意，子问题的两个变量中只有一个是自由变量，另一个由约束条件自动确定。

根据得到

SMO解如下对偶问题：

只保留两个,化简得到：

由于只有两个变量，约束条件可以用二维空间中的图形表示，分析y1=y2和y1!=y2的两种情况

y1=y2

同理可得y1!=y2时

接下来，先求未剪辑的最优解，再求剪辑后的最优解。

为了叙述简单，记

引进记号

将代入

得到，然后对求导，令其为零，

将

代入，得到

剪辑后的解

$\alpha_{1}^{new}=\alpha_{2}^{old}+y_{1}y_{2}(\alpha_2^{old}-\alpha_2^{new})$

从而得到最优化问题的解。

手推序列最小优化（sequential minimal optimization，SMO）算法_smo算法-CSDN博客

变量的选择方法

SMO方法选取变量的核心思想是选择一个变量违反KKT条件的.

首先看满足的KKT条件

软间隔最大化的原问题的拉格朗日函数是:

$\mathcal{L}(w,b,\xi,\alpha,\mu)=\frac{1}{2}w^Tw+{\rm C}\sum_{i=1}^{N}\xi_{i}-\sum_{i=1}^N\alpha_i(y_i(w^Tx_i+b)-1+\xi_{i})-\sum_{i=1}^N\mu_{i}\xi_{i}$

KKT条件是:

$\frac{L'}{w'}=w-\sum_{i=1}^N\alpha_{i}y_{i}x_{i}=0~(1)\\ \frac{L'}{b'}=-\sum_{i=1}^N\alpha_{i}y_{i}=0~(2)\\ \frac{L'}{\varepsilon'}=C-\alpha_{i}-\mu_{i}=0\Rightarrow 0\leq \alpha_{i}\leq C~(3)\\ 1-\varepsilon_{i}-y_{i}(wx_{i}+b)\leq 0~(4)\\ \alpha_{i}\geq 0,\mu_{i}\geq 0~(5)\\ \alpha_{i}(1-\varepsilon_{i}-y_{i}(wx_{i}+b))=0~(6)\\ \mu_{i}\varepsilon_{i}=0~(7)\\$