线性支持向量机
💚

线性支持向量机

数据线性不可分
训练数据集中有一些特异点，除了这些特异点，剩下大部分的样本组成的集合是线性可分的；
这些特异点不能满足函数间隔大于等于1的约束条件；
引入松弛变量
  • 对每个样本点(x_i,y_i)引入一个松弛变量 𝝃_i≥0，其约束条件变为
      • yi(w⋅xi+b)≥1−ξiy_i(w\cdot x_i+b)\geq 1-\xi_i
  • 对每个松弛变量 𝝃_i 需支付一个代价 𝝃_i，则目标函数变为
      • 12∣∣w∣∣2+C∑i=1Nξi\frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i
      其中C为惩罚函数，C越大对误分类的惩罚越大
软间隔最大化问题（原始问题）
min⁡w,b,ξ12∣∣w∣∣2+C∑i=1Nξi s.t. yi(w⋅xi+b)≥1−ξi(∀i=1,2,…N)ξi≥0(∀i=1,2,…N)\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,ξ,α,μ)=12∥w∥22+C∑i=1mξi−∑i=1mαi[yi(wTxi+b)−1+ξi]−∑i=1mμiξiL(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,ξmax⁡αi≥0,μi≥0L(w,b,α,ξ,μ)\min_{w, b, \xi} \max _{\alpha_i \geq 0, \mu_i \geq 0} L(w, b, \alpha, \xi, \mu)
对偶问题为极大极小问题
max⁡αi≥0,μi≥0min⁡w,b,ξL(w,b,α,ξ,μ)\max _{\alpha_i \geq 0, \mu_i \geq 0} \min _{w, b, \xi} L(w, b, \alpha, \xi, \mu)
  1. 先求目标函数对w,b,𝝃的极小
      2. ∂L∂w=0⇒w=∑i=1Nαiyixi∂L∂b=0⇒∑i=1Nαiyi=0∂L∂ξ=0⇒C−αi−μi=0\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,ξL(w,b,α,ξ,μ)=−12∑i=1N∑j=1Nαiαjyiyjxi⋅xj+∑i=1Nαi\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的约束。
  1. 再求目标函数对𝛼，𝜇的极大
      2. min⁡α12∑i=1N∑j=1Nαiαjyiyjxi⋅xj−∑i=1Nαi s.t ∑i=1Nαiyi=00≤αi≤C(∀i=1,2,…n)\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条件有
{w∗=∑i=1Nαi∗yixiαi∗+μi∗=Cαi∗(yi(w∗⋅xi+b∗)−1+ξi∗)=0μi∗ξi∗=0yi(w∗⋅xi+b∗)−1+ξi∗≥0αi∗≥0,μi∗≥0,ξi∗≥0(∀i=1,2,…n)\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∗=yj−w∗⋅xj=yj−∑i=1Nαi∗yi(xi⋅xj)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*的解也不唯一。
支持向量和间隔边界
notion image
支持向量满足
yi(w⋅xi+b)=1−ξiy_i(w\cdot x_i+b)=1-\xi_i
notion image
正则化的合页损失
线性支持向量机的另一种解释是，极小化目标函数
min⁡w,b[1−yi(w∙x+b)]+⏟合页损失+λ∥w∥22⏟正则项\underbrace{\min _{w, b}\left[1-y_i(w \bullet x+b)\right]_{+}}_{\text{合页损失}}+\underbrace{\lambda\|w\|_2^2}_{\text{正则项}}
第一项是经验损失，称为合页损失；第二项是正则项
合页损失：如果点被正确分类，且函数间隔大于1，合页损失是0，否则损失是1-y_i(w·x+b)；
0-1损失：如果正确分类，损失是0，误分类损失1；
感知机损失：正确分类，损失是0，误分类损失是-y_i(w·x+b)。
min⁡w,b[−yi(w∙x+b)]+{\min _{w, b}\left[-y_i(w \bullet x+b)\right]_{+}}
notion image