一、什么是支持向量机

支持向量机（SVM）

主要用于解决模式识别领域中的数据分类问题；找到一个最优超平面（Hyperplane），不仅能正确分类样本，还能让两类样本到超平面的间隔最大化（Margin）。

图中黑色实线称为决策超平面，两边的黑色虚线称为正负超平面，虚线上面的点称为支持向量。

二、线性SVM模型

超平面表达

设训练数据集为；

{(xi,yi)}i=1m,xi∈Rn,yi∈{+1,−1}\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要找的超平面

wTx+b=0w^Tx+b=0

ww：超平面法向量、bb：偏置项

间隔最大化

对于一个数据点xix_i，它到决策面的距离可以表示为：

Distance=∣wTxi+b∣∥w∥Distance=\frac{|w^Tx_i+b|}{\lVert w \rVert}
max⁡w,b1∥w∥  ⟺  min⁡w,b12∥w∥2\max_{w,b}\frac{1}{\lVert w \rVert} \iff \min_{w,b}\frac{1}{2}{\lVert w \rVert}^2

分类条件

对于存在分类间隔的两类样本点，我们一定可以找到一些决策面，使其对于所有的样本点均满足下面的条件：

{wTxi+b≥1for yi=1wTxi+b≤−1for yi=−1\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}

把类别标签和两个不等式左边相乘，形成统一的表述：

yi(wTxi+b)≥1 ∀xiy_i(w^Tx_i+b) \ge 1 \space \forall x_i

SVM问题最优化数学描述

min⁡w,b12∥w∥2s.t. yi(wTxi+b)≥1 i=1,2,...,m\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优化步骤

一、构造拉格朗日函数

引入拉格朗日算子 λi≥0\lambda_i \ge 0，构造拉格朗日函数。

L(w,b,λ)=12∥w∥2+∑i=1mλi[1−yi(wTxi+b)]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,bmax⁡λL(w,b,λ)s.t. λi≥0\min_{w,b}\max_{\lambda}L(w,b,\lambda) \\ s.t. \space \lambda_i \ge 0

原问题对偶问题：

max⁡λmin⁡w,bL(w,b,λ)s.t. λi≥0\max_{\lambda}\min_{w,b}L(w,b,\lambda) \\ s.t. \space \lambda_i \ge 0

二、计算偏导

对w,b求偏导：

∂L∂w=w−∑i=1mλixiyi=0→w=∑i=1mλixiyi∂L∂w=∑i=1mλiyi=0\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 \\

回带拉格朗日函数

=12wTw+∑i=1mλi−∑i=1mλiyiwTxi−∑i=1mλiyib=12wT∑i=1mλixiyi+∑i=1mλi−wT∑i=1mλiyixi=∑i=1mλi−12wT∑i=1mλixiyi=∑i=1mλi−12(∑j=1mλjxjyj)T∑i=1mλixiyi=∑i=1mλi−12∑i=1m∑j=1mλiλjyiyjxjTxi=∑i=1mλi−12∑i=1m∑j=1mλiλjyiyj(xi⋅xj)\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,bL(w,b,λ)=∑i=1mλi−12∑i=1m∑j=1mλiλjyiyj(xi⋅xj)\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)

继而求 minw,bL(w,b,λ)min_{w,b}L(w,b,\lambda)对λ\lambda的最大

max⁡λ[min⁡w,bL(w,b,λ)=∑i=1mλi−12∑i=1m∑j=1mλiλjyiyj(xi⋅xj)]s.t. ∑i=1mλiyi=0λi≥0,i=1,2,...,m\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

求出最优的λi∗\lambda_i^*值，可以求出对应ww和bb的值

w∗=∑i=1mλi∗xiyib∗=yi−(w∗)Txiw^*=\sum_{i=1}^m\lambda^*_ix_iy_i \\ b^*=y_i-(w^*)^Tx_i

最后的分类决策函数为

f(x)=sign((w∗)Txi+b∗)f(x)=sign((w^*)^Tx_i+b^*)