一、什么是支持向量机
支持向量机（SVM）
主要用于解决模式识别领域中的数据分类问题；找到一个最优超平面（Hyperplane），不仅能正确分类样本，还能让两类样本到超平面的间隔最大化（Margin）。
图中黑色实线称为决策超平面，两边的黑色虚线称为正负超平面，虚线上面的点称为支持向量。
二、线性SVM模型
超平面表达
设训练数据集为；
\left\{\left(x_{i}, y_{i}\right)\right\}_{i=1}^{m}, \quad x_{i} \in \mathbb{R}^{n}, \quad y_{i} \in\{+1,-1\}
SVM要找的超平面
w^Tx+b=0
w：超平面法向量、b：偏置项
间隔最大化
对于一个数据点x_i，它到决策面的距离可以表示为：
Distance=\frac{|w^Tx_i+b|}{\lVert w \rVert}
\max_{w,b}\frac{1}{\lVert w \rVert} \iff \min_{w,b}\frac{1}{2}{\lVert w \rVert}^2
分类条件
对于存在分类间隔的两类样本点，我们一定可以找到一些决策面，使其对于所有的样本点均满足下面的条件：
\begin{cases} w^Tx_i+b \ge 1 &\text{for } y_i=1 \\ w^Tx_i+b \le -1 &\text{for } y_i=-1 \end{cases}
把类别标签和两个不等式左边相乘，形成统一的表述：
y_i(w^Tx_i+b) \ge 1 \space \forall x_i
SVM问题最优化数学描述
\min_{w,b}\frac{1}{2}{\lVert w \rVert}^2 \\ s.t. \space y_i(w^Tx_i+b) \ge 1 \space i=1,2,...,m
SVM优化步骤
一、构造拉格朗日函数
引入拉格朗日算子 \lambda_i \ge 0，构造拉格朗日函数。
L(w,b,\lambda)=\frac{1}{2}\lVert w \rVert^2 + \sum_{i=1}^m\lambda_i[1-y_i(w^Tx_i+b)]
上面问题满足KKT条件，故原问题具有强对偶性，故原问题变为：
\min_{w,b}\max_{\lambda}L(w,b,\lambda) \\ s.t. \space \lambda_i \ge 0
原问题对偶问题：
\max_{\lambda}\min_{w,b}L(w,b,\lambda) \\ s.t. \space \lambda_i \ge 0
二、计算偏导
对w,b求偏导：
\frac{\partial L}{\partial w}=w-\sum_{i=1}^m\lambda_ix_iy_i=0 \\ \rightarrow w=\sum_{i=1}^m\lambda_ix_iy_i\\ \frac{\partial L}{\partial w}=\sum_{i=1}^m\lambda_iy_i=0 \\
回带拉格朗日函数
\begin{aligned} &=\frac{1}{2}w^Tw+\sum_{i=1}^m\lambda_i-\sum_{i=1}^m\lambda_iy_iw^Tx_i-\sum_{i=1}^m\lambda_iy_ib \\ &=\frac{1}{2}w^T\sum_{i=1}^m\lambda_ix_iy_i+\sum_{i=1}^m\lambda_i-w^T\sum_{i=1}^m\lambda_iy_ix_i \\ &=\sum_{i=1}^m\lambda_i-\frac{1}{2}w^T\sum_{i=1}^m\lambda_ix_iy_i \\ &=\sum_{i=1}^m\lambda_i-\frac{1}{2}(\sum_{j=1}^m\lambda_jx_jy_j)^T\sum_{i=1}^m\lambda_ix_iy_i \\ &=\sum_{i=1}^m\lambda_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\lambda_i\lambda_jy_iy_jx_j^Tx_i \\ &=\sum_{i=1}^m\lambda_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\lambda_i\lambda_jy_iy_j(x_i \cdot x_j) \end{aligned}
根据之前对偶问题的转换也就是
\min_{w,b}L(w,b,\lambda)=\sum_{i=1}^m\lambda_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\lambda_i\lambda_jy_iy_j(x_i \cdot x_j)
继而求 min_{w,b}L(w,b,\lambda)对\lambda的最大
\max_\lambda[\min_{w,b}L(w,b,\lambda)=\sum_{i=1}^m\lambda_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\lambda_i\lambda_jy_iy_j(x_i \cdot x_j)] \\ s.t. \space \sum_{i=1}^m\lambda_iy_i=0 \\ \lambda_i \ge 0,i=1,2,...,m
求出最优的\lambda_i^*值，可以求出对应w和b的值
w^*=\sum_{i=1}^m\lambda^*_ix_iy_i \\ b^*=y_i-(w^*)^Tx_i
最后的分类决策函数为
f(x)=sign((w^*)^Tx_i+b^*)