线性可分支持向量机
❤️

线性可分支持向量机

线性可分支持向量机要求数据是线性可分的
函数间隔vs几何间隔
样本点到超平面的函数间隔
γ^i=yi(w⋅xi+b)\hat{\gamma}_i=y_i\left(w\cdot x_i+b\right)
训练数据集到超平面的函数间隔
γ^=min⁡iyi(w⋅xi+b)\hat{\gamma}=\min_{i}y_i\left(w\cdot x_i+b\right)
样本点到超平面的几何间隔
γi=1∣∣w∣∣yi(w⋅xi+b)\gamma_i=\frac{1}{||w||}y_i\left(w\cdot x_i+b\right)
训练数据集到超平面的几何间隔
γ=min⁡i1∣∣w∣∣yi(w⋅xi+b)\gamma=\min_{i}\frac{1}{||w||}y_i\left(w\cdot x_i+b\right)
支持向量机的优化问题
所有样本点到超平面的几何距离最远
max⁡w,b γ s.t yi(w∣∣w∣∣⋅xi+b∣∣w∣∣)≥γ(∀i=1,2,…n)\begin{aligned}\max_{w,b} &\ \gamma\\\text { s.t } & y_i\left(\frac{w}{||w||}\cdot x_i+\frac{b}{||w||}\right)\geq\gamma(\forall i=1,2, \ldots n)\end{aligned}
同理为
max⁡w,bγ^∣∣w∣∣ s.t yi(w⋅xi+b)≥γ^(∀i=1,2,…n)\begin{aligned}\max_{w,b} & \frac{\hat{\gamma}}{||w||}\\\text { s.t } & y_i\left(w\cdot x_i+b\right)\geq\hat{\gamma}(\forall i=1,2, \ldots n)\end{aligned}
由于函数间隔的取值并不影响最优化问题，故取函数间隔为1，等价为
凸二次规划问题
min⁡w,b12∣∣w∣∣2 s.t yi(w⋅xi+b)−1≥0(∀i=1,2,…n)\begin{aligned}\min_{w,b} & \frac{1}{2}||w||^2\\\text { s.t } & y_i\left(w\cdot x_i+b\right)-1\geq 0(\forall i=1,2, \ldots n)\end{aligned}
 
支持向量和间隔边界
notion image
支持向量满足
yi(w⋅xi+b)=1y_i(w\cdot x_i+b)=1
notion image
对于线性可分数据集，最大间隔分离超平面存在且唯一。
 
线性可分支持向量机学习算法（原始形式）
  • 输入：线性可分训练数据集T
  • 输出：最大间隔分类器和分类决策函数
  1. 构造并求解约束最优化问题（凸二次规划问题）
      2. min⁡w,b12∣∣w∣∣2 s.t yi(w⋅xi+b)−1≥0(∀i=1,2,…n)\begin{aligned}\min_{w,b} & \frac{1}{2}||w||^2\\\text { s.t } & y_i\left(w\cdot x_i+b\right)-1\geq 0(\forall i=1,2, \ldots n)\end{aligned}
      得到最优解w*，b*
  1. 得到分离超平面
      2. w∗⋅x+b=0w^*\cdot x+b=0
      和分类决策函数
      f(x)=sign(w∗⋅x+b)f(x)=sign(w^*\cdot x+b)
 
利用拉格朗日对偶性求解凸二次规划
引入拉格朗日乘子 𝛼_i≥0（i=1,2,…,N)
L(w,b,α)=12∣∣w∣∣2+∑i=1Nαi[1−yi(w⋅xi+b)]L(w,b,\alpha)=\frac{1}{2}||w||^2+\sum_{i=1}^N\alpha_i\left[1-y_i(w\cdot x_i+b)\right]
原始问题等价于极小极大问题
min⁡w,bmax⁡αi≥0L(w,b,α)\min_{w,b}\max_{\alpha_i\geq 0}L(w,b,\alpha)
对偶问题为极大极小问题
max⁡αi≥0min⁡w,bL(w,b,α)\max_{\alpha_i\geq 0}\min_{w,b}L(w,b,\alpha)
  1. 先求L(w,b,𝛼)关于w,b的极小
      2. ∂L∂w=0⇒w=∑i=1Nαiyixi∂L∂b=0⇒∑i=1Nαiyi=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\end{gathered}min⁡w,bL(w,b,α)=−12∑i=1N∑j=1Nαiαjyiyjxi⋅xj+∑i=1Nαi\min_{w,b}L(w,b,\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
  1. 再求minL(w,b,𝛼)关于𝛼的极大
      2. min⁡α12∑i=1N∑j=1Nαiαjyiyjxi⋅xj−∑i=1Nαi s.t ∑i=1Nαiyi=0αi≥0(∀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\\ &\alpha_i\geq 0(\forall i=1,2, \ldots n)\end{aligned}
      通过SMO算法得到最优解𝛼*。
原始问题和对偶问题解的关系——KKT条件
若得到对偶问题的最优解𝛼*，则由KKT条件得
{w∗=∑i=1Nαi∗yixiαi∗(yi(w∗⋅xi+b∗)−1)=0yi(w∗⋅xi+b∗)−1≥0\left\{\begin{array}{l}w^*=\sum_{i=1}^N \alpha_i^* y_i x_i \\\alpha_i^*\left(y_i(w^*\cdot x_i+b^*)-1\right)=0\\y_i(w^*\cdot x_i+b^*)-1\geq0\end{array}\right.
若存在分量𝛼*_j>0，对此j有
yj(w∗⋅xj+b∗)−1=0y_j(w^*\cdot x_j+b^*)-1=0b∗=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)
线性可分支持向量机学习算法（对偶形式）
  • 输入：线性可分训练数据集T
  • 输出：最大间隔分类器和分类决策函数
  1. 构造并求解约束最优化问题
      2. min⁡α12∑i=1N∑j=1Nαiαjyiyjxi⋅xj−∑i=1Nαi s.t ∑i=1Nαiyi=0αi≥0(∀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\\ &\alpha_i\geq 0(\forall i=1,2, \ldots n)\end{aligned}
      利用SMO算法得到最优解𝛼*
  1. 计算w*
      2. w∗=∑i=1Nαi∗yixiw^*=\sum_{i=1}^N \alpha_i^* y_i x_i
  1. 计算b*
      2. 找出满足𝛼_j>0的支持向量(x_j,y_j)（j=1,2,…,J)，计算出
      b∗=yj−∑i=1Nαi∗yi(xi⋅xj)b^*=y_j-\sum_{i=1}^N \alpha_i^* y_i \left(x_i\cdot x_j\right)
  1. 分离超平面和分类决策函数为
      2. w∗⋅x+b=0，f(x)=sign(w∗⋅x+b∗)w^*\cdot x+b=0，f(x)=sign(w^*\cdot x+b^*)