1. 线性SVM

线性可分SVM对训练数据集的要求过于理想化。
对于有线性关系但线性不可分的数据，要做一些改进，即线性SVM。

1.1. 模型

$\begin{aligned} \min_{w,b,\xi} \quad \frac{1}{2}||w||^2 + C \sum_{i=1}^N\xi_i && {1} \\ s.t. \quad y_i(w\cdot x_i+b)\ge 1-\xi_i \\ \quad \quad \xi_i \ge 0, i = 1,2,\cdots,N && {2} \end{aligned}$

公式说明：
$\xi_i$：松弛变量。给样本增加一个松弛变量，使它能够满足约束。
公式（2）说明样本加上松弛变量后就$\ge$1
公式（1）说明对每个松弛变量都要支付一个$\xi_i$大小的代价。
C：代表约束条件与松弛变量之间的平衡。

1.2. 策略

对于给定的线性不可分的训练数据集，通过求解凸二次规划问题，即公式（1）、（2）软件间隔最大化问题

得到的分离超平面为：
$w^* \cdot x + b^* = 0$ 相应的分类决策函数为：
$f(x) = sign(w^* \cdot x + b^*)$

1.3. 算法

公式（1）（2）是凸二次规划问题，求得过程与线性可分SVM的凸二次规划问题求解过程类似。

1. 将要求解的带约束最优化问题转化为对偶最优化问题link
2. 对偶最优化问题解出a∗w∗和b∗link
3. 得到分离超平面和分类决策函数。