# 第7章 线性SVM

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

## 模型

$$
\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）软件间隔最大化问题

得到的分离超平面为：

$$
w^* \cdot x + b^* = 0
$$

相应的分类决策函数为：

$$
f(x) = sign(w^* \cdot x + b^*)
$$

## 算法

公式（1）（2）是凸二次规划问题，求得过程与线性可分SVM的凸二次规划问题求解过程类似。\
1\. 将要求解的带约束最优化问题转化为对偶最优化问题[link](https://windmising.gitbook.io/lihang-tongjixuexifangfa/7/8)\
2\. 对偶最优化问题解出a∗w∗和b∗[link](https://windmising.gitbook.io/lihang-tongjixuexifangfa/7/9)\
3\. 得到分离超平面和分类决策函数。
