数据线性不可分

训练数据集中有一些特异点，除了这些特异点，剩下大部分的样本组成的集合是线性可分的；

这些特异点不能满足函数间隔大于等于1的约束条件；

引入松弛变量

• 对每个样本点(x_i,y_i)引入一个松弛变量 𝝃_i≥0，其约束条件变为

  $$ y_i(w\cdot x_i+b)\geq 1-\xi_i $$

• 对每个松弛变量 𝝃_i 需支付一个代价 𝝃_i，则目标函数变为

  $$ \frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i $$

  其中C为惩罚函数，C越大对误分类的惩罚越大

软间隔最大化问题（原始问题）

$$ \begin{gathered}\min_{w,b,\xi}\frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i \\\text { s.t. } y_i(w\cdot x_i+b)\geq 1-\xi_i(\forall i=1,2, \ldots N) \\\xi_i \geq 0 \quad(\forall i=1,2, \ldots N)\end{gathered} $$

• 是一个凸二次规划问题，因而关于(w,b,𝝃)的解存在；
• 可以证明w的解唯一；
• b的解可能不唯一，而是存在于一个区间。

软间隔最大化问题（对偶算法）

引入拉格朗日函数

$$ L(w, b, \xi, \alpha, \mu)=\frac{1}{2}\|w\|2^2+C \sum{i=1}^m \xi_i-\sum_{i=1}^m \alpha_i\left[y_i\left(w^T x_i+b\right)-1+\xi_i\right]-\sum_{i=1}^m \mu_i \xi_i $$

其中拉格朗日乘子 𝛼_i≥0, 𝜇_i≥0

原始问题等价于极小极大问题

$$ \min_{w, b, \xi} \max _{\alpha_i \geq 0, \mu_i \geq 0} L(w, b, \alpha, \xi, \mu) $$

对偶问题为极大极小问题

$$ \max _{\alpha_i \geq 0, \mu_i \geq 0} \min _{w, b, \xi} L(w, b, \alpha, \xi, \mu) $$

1. 先求目标函数对w,b,𝝃的极小

   $$ \begin{gathered}\frac{\partial L}{\partial w}=0 \Rightarrow w=\sum_{i=1}^N \alpha_i y_i x_i \\\frac{\partial L}{\partial b}=0 \Rightarrow \sum_{i=1}^N \alpha_i y_i=0 \\\frac{\partial L}{\partial \xi}=0 \Rightarrow C-\alpha_i-\mu_i=0\end{gathered} $$

   $$ \min {w, b, \xi} L(w, b, \alpha, \xi, \mu)=-\frac{1}{2}\sum{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_j y_i y_j x_i\cdot x_j+\sum_{i=1}^N\alpha_i $$

   对比硬间隔最大化，仅仅多了C-𝛼_i-𝜇_i=0的约束。

2. 再求目标函数对𝛼，𝜇的极大

   $$ \begin{aligned}\min_{\alpha} & \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_j y_i y_j x_i\cdot x_j-\sum_{i=1}^N\alpha_i\\\text { s.t } & \sum_{i=1}^N \alpha_i y_i=0\\ &0\leq \alpha_i\leq C(\forall i=1,2, \ldots n)\end{aligned} $$

   通过SMO算法得到最优解𝛼*。

   对比硬间隔最大化，仅仅多了0≤𝛼_i≤C的约束。

原始问题和对偶问题解的关系——KKT条件

根据KKT条件有

$$ \left\{\begin{array}{l}w^=\sum_{i=1}^N \alpha_i^ y_i x_i \\ \alpha_i^+\mu_i^=C\\ \alpha_i^\left(y_i(w^\cdot x_i+b^)-1+\xi_i^\right)=0\\ \mu_i^\xi_i^=0\\ y_i(w^\cdot x_i+b^)-1+\xi_i^\geq0\\\alpha_i^\geq 0,\mu_i^\geq 0,\xi_i^\geq 0(\forall i=1,2, \ldots n)\end{array}\right. $$

若存在分量0≤𝛼*_j≤C，对此j有

$$ b^=y_j-w^\cdot x_j=y_j-\sum_{i=1}^N \alpha_i^* y_i \left(x_i\cdot x_j\right) $$

由于对j的选择不唯一，故b*的解也不唯一。

支持向量和间隔边界

支持向量满足

$$ y_i(w\cdot x_i+b)=1-\xi_i $$

正则化的合页损失

线性支持向量机的另一种解释是，极小化目标函数

$$ \underbrace{\min {w, b}\left[1-y_i(w \bullet x+b)\right]{+}}_{\text{合页损失}}+\underbrace{\lambda\|w\|2^2}{\text{正则项}} $$