SVM概念

SVM是一种有监督学习（已知样本的类别标签）的二分类算法，类似于逻辑回归，均为通过一条直线（超平面）将样本划分为两类。
SVM的作用是找到一条最优的直线，将样本更好地划分。

将数据集分隔开来的直线成为分隔平面，在二维平面中即为一条直线，若数据集是1024维的，那就需要1023维的对象对数据进行分隔，这个对象称为超平面

最优化

前提，数据是线性可分

如下图两种均为线性不可分

图A的数据集为线性可分，且存在无数条直线能将其分为2类，图BCD中的直线，分别就是其中的一种。

我们希望找到离直线（超平面）最近的点，确保他们离直线的距离尽可能地远。

例如，若选择C中的分隔面作为分类器，由于训练集的有限性或噪声的干扰，训练集外的样本可能更接近两个类目前的分隔界，在分类决策的时候就会出现错误，为了使分类器抗干扰能力强，即使得点到分隔面的距离（间隔）尽可能地大。

寻找最大间隔

设：
直线（超平面）的参数向量：
$\begin{aligned} \mathbf{ w^{T}} &=\begin{bmatrix}w_{1}&w_{2}&...&w_{n}\end{bmatrix} \end{aligned}$wT​=[w1​​w2​​...​wn​​]​

特征向量：
$\begin{aligned} \mathbf{ x}&=\begin{bmatrix} x_{1}\\x_{2}\\...\\x_{n}\\ \end{bmatrix} \end{aligned}$x​=⎣⎢⎢⎡​x1​x2​...xn​​⎦⎥⎥⎤​​
分隔超平面的形式可以写为：$y=\mathbf{w^{T}x}+b$y=wTx+b

数据点A特征向量为：
$\begin{aligned} \mathbf{A}&=\begin{bmatrix} a_{1}\\a_{2}\\...\\a_{n}\\ \end{bmatrix} \end{aligned}$A​=⎣⎢⎢⎡​a1​a2​...an​​⎦⎥⎥⎤​​

则点A到分隔面的距离为：${\LARGE\frac{|\mathbf{w^{T}A}+b|}{||\mathbf{w}||}}$∣∣w∣∣∣wTA+b∣​
即：
${\LARGE =\frac{|w_{1}a_{1}+w_{2}a_{2}+...+w_{n}a_{n}+b|}{\sqrt{w_{1}^2+w_{2}^2+...+w_{n}^2}}}$=w12​+w22​+...+wn2​​∣w1​a1​+w2​a2​+...+wn​an​+b∣​

将类别分为+1和-1两个类，且距离最近的点函数间隔为1:
$\begin{array}{l} \left\{\begin{matrix} \mathbf{w^{T}x}+b \ge +1 ,{y_{i}=+1} \\ \mathbf{w^{T}x}+b \le -1 , {y_{i}=-1} \end{matrix}\right. \end{array}${wTx+b≥+1,yi​=+1wTx+b≤−1,yi​=−1​​

$y_{i}*(\mathbf{w^{T}x}+b) \ge 1$yi​∗(wTx+b)≥1 恒成立

所以${\large d=\frac{y_{i}*(\mathbf{w^{T}x}+b)}{||\mathbf{w}||}}$d=∣∣w∣∣yi​∗(wTx+b)​

进行代换后，离超平面最近的点，满足
$1、{\large d=\frac{1}{||\mathbf{w}||}}$1、d=∣∣w∣∣1​
$2、y_{i}*(\mathbf{w^{T}x}+b) = 1$2、yi​∗(wTx+b)=1
该点到直线的距离可以转换为
${\large d=\frac{y_{i}*(\mathbf{w^{T}x}+b)}{||\mathbf{w}||}}$d=∣∣w∣∣yi​∗(wTx+b)​

因此SVM的目标为
$\max \frac{\min y_{i}*(\mathbf{w^{T}x}+b)}{||\mathbf{w}||}$max∣∣w∣∣minyi​∗(wTx+b)​
求解满足以上公式的 $\mathbf {w}$w向量和$b$b参数

因为 $\min y_{i}*(\mathbf{w^{T}x}+b)=1$minyi​∗(wTx+b)=1
所以目标为：
$\begin{aligned} &{\large \max \frac{1}{||\mathbf{w}||}}\\ \\ &{\large s.t:y_{i}*(\mathbf{w^{T}x}+b) \ge 1} \end{aligned}$​max∣∣w∣∣1​s.t:yi​∗(wTx+b)≥1​

为了最大化间隔，仅需最小化$||\mathbf{w}||$∣∣w∣∣，即
$\begin{aligned} &{\large \min||\mathbf{w}||}\\ \\ &{\large s.t:y_{i}*(\mathbf{w^{T}x}+b) \ge 1} \end{aligned}$​min∣∣w∣∣s.t:yi​∗(wTx+b)≥1​
同时可将$\min||\mathbf{w}||$min∣∣w∣∣写为$\min \frac{1}{2} ||\mathbf{w}||^{2}$min21​∣∣w∣∣2
转换如下，变为一个二次优化问题
$\begin{aligned} &{\large \min \frac{1}{2} ||\mathbf{w}||^{2}}\\ \\ &{\large s.t:y_{i}*(\mathbf{w^{T}x}+b) \ge 1} \end{aligned}$​min21​∣∣w∣∣2s.t:yi​∗(wTx+b)≥1​

对偶问题

对于优化问题
$\begin{aligned} &{\large \min \frac{1}{2} ||\mathbf{w}||^{2}}\\ \\ &{\large s.t \qquad y_{i}*(\mathbf{w^{T}x}+b) \ge 1} \end{aligned}$​min21​∣∣w∣∣2s.tyi​∗(wTx+b)≥1​
可通过拉格朗日乘子法可得到其"对偶问题"