一、线性SVM
思想
寻找一个超平面，使得支撑向量到该超平面(决策边界)的距离最大。
Hard Margin
在n维空间中，超平面的表达式为
$$
w^{T}x+b=0
$$
支撑向量到该超平面的距离为
$$
\frac {|w^{T}x+b|}{||w||}
$$
以二维空间为例，设某一类支撑向量到超平面的距离为d，两个类别分别用1和-1来表示，则有
$$
\frac {w^{T}x^{(i)}+b}{||w||}\geq d,\forall y^{(i)}=1
$$
$$
\frac {w^{T}x^{(i)}+b}{||w||}\leq -d,\forall y^{(i)}=-1
$$
上下同除以d，得
$$
\frac {w^{T}x^{(i)}+b}{||w||d}\geq 1,\forall y^{(i)}=1
$$
$$
\frac {w^{T}x^{(i)}+b}{||w||d}\leq -1,\forall y^{(i)}=-1
$$
记
$$
\frac {w^{T}}{||w||d}=w_d^{T}
$$
$$
\frac{b}{||w||d}=b_d
$$
则有
$$
w_d^{T}x^{(i)}+b_d\geq 1,\forall y^{(i)}=1
$$
$$
w_d^{T}x^{(i)}+b_d\leq -1,\forall y^{(i)}=-1
$$
为了后续方便书写，这里再记
$$
w_d=w
$$
$$
b_d=b
$$
于是得到
$$
w^{T}x^{(i)}+b\geq 1,\forall y^{(i)}=1
$$
$$
w^{T}x^{(i)}+b\leq -1,\forall y^{(i)}=-1
$$
上面得式子又可以合并为一个式子
$$
y^{(i)}(w_d^{T}x^{(i)}+b_d)\geq 1
$$
这便是优化目标的限制条件
现在，我们已经得到了优化目标和限制条件，即
$$
max\ \ \ \frac{|w^{T}x+b|}{||w||}
$$
$$
s.t. \ \ \ y^{(i)}(w_d^{T}x^{(i)}+b_d)\geq 1
$$
其中x是支撑向量的位置坐标，并且当x为支撑向量时，满足
$$
|w^Tx+b|=1
$$
所以我们的优化目标又可以写成
$$
max \ \ \ \frac{1}{||w||}
$$
也就是
$$
min \ \ \ ||w||
$$
为了便于求解，写为
$$
min \ \ \ \frac12||w||^2
$$
我们得到了最终的优化目标和限制条件
$$
min \ \ \ \frac12||w||^2
$$
$$
s.t. \ \ \ y^{(i)}(w_d^{T}x^{(i)}+b_d)\geq 1
$$
这是一个有条件的最优化问题
Soft Margin
上面的数学推导是关于Hard Margin的，但是在实际的应用中，为了提高模型的泛化能力，要求SVM模型对训练数据集要有一定的容错能力(也就是牺牲一部分预测精度，以获得较强的泛化能力)。
在Hard Margin的基础上，增加正则化项$\zeta_i$，便得到了Soft Margin的优化目标和限制条件
$$
min \ \ \ \frac12||w||^2+C\sum_{i=1}^{m}\zeta_i
$$
$$
s.t. \ \ \ y^{(i)}(w_d^{T}x^{(i)}+b_d)\geq 1-\zeta_i
$$
$$
\zeta \geq 0
$$
或者
$$
min \ \ \ \frac12||w||^2+C\sum_{i=1}^{m}\zeta_i^2
$$
$$
s.t. \ \ \ y^{(i)}(w_d^{T}x^{(i)}+b_d)\geq 1-\zeta_i
$$
$$
\zeta_i \geq 0
$$
前者是L1正则，后者为L2正则。
二、非线性SVM
核函数
在求解
$$
min \ \ \ \frac12||w||^2+C\sum_{i=1}^{m}\zeta_i
$$
$$
s.t. \ \ \ y^{(i)}(w_d^{T}x^{(i)}+b_d)\geq 1-\zeta_i
$$
$$
\zeta \geq 0
$$
的过程中，可以通过变换，得到其等价形式
$$
max \ \ \ \sum_{i=1}^{m}\alpha_i-\frac12\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_ix_j
$$
$$
s.t.\ \ \ 0\leq \alpha_i \leq C
$$
$$
\sum_{i=1}^{m} \alpha_i y_i=0
$$
上面的形式是求解线性SVM的
只要改变$x_iy_i$，便可以转化为非线性SVM，这里的转化便使用了核函数
$$
K(x_i,y_i)
$$
于是我们得到了更一般的优化目标和限制条件
$$
max \ \ \ \sum_{i=1}^{m}\alpha_i-\frac12\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jK(x_ix_j)
$$
$$
s.t.\ \ \ 0\leq \alpha_i \leq C
$$
$$
\sum_{i=1}^{m} \alpha_i y_i=0
$$
若核函数取
$$
K(x_i,y_i)=xy
$$
便得到了前面推导的线性SVM
当核函数取其他函数时，便可以得到非线性SVM的优化目标和限制条件了。
常用核函数
- 多项式核函数
$$
K(x,y)={(xy+c)}^d
$$
其中c和d是超参数
- 高斯核函数
$$
K(x,y)=e^{-\gamma {||x-y||}^2}
$$
其中$\gamma$是超参数
基本思想就是将低维的数据映射到高维（m*n–>m*m），使得在低维空间中线性不可分的情况在高维空间中变得线性可分了。
