第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 2. 对偶最优化问题解出a∗w∗和b∗link 3. 得到分离超平面和分类决策函数。