您的位置: 首页  >  文章  >  统计学习方法（七）：支持向量机（SVM）

统计学习方法（七）：支持向量机（SVM）

分类: 文章 • 2023-03-26 08:55:38
  • 支持向量机：判别模型
  • 种类：硬间隔、软间隔、核函数
  • 思想：感知机是线性分类器，对线性可分的数据集可以有无穷多个超平面将其分开。而支持向量机选择其中分类最为靠谱的一个，而这个靠谱的依据是：（重要思想）：1.在分类准确的前提下，2.使得离超平面最近的点离超平面的距离最远，也就是说一个点可能是很多个超平面的最近点，但是我们对比这个点离其他超平面的距离，选择最远的那一个超平面作为最终的超平面。
  • 学习流程：输入空间映射特征空间，特征空间学习得到输出空间。
  • 硬间隔SVM：
    • 设超平面为：wx+b=0w x+b=0，当分类为1时，wx+b>0w x+b>0，当分类为0时，wx+b<0w x+b<0
    • 约束方程：
      • 首先保证分类正确，也就是满足以上假设条件，可以简写为： yi(wxi+b)>0y_{i}\left(w x_{i}+b\right)>0
      • 其次要找到距离超平面最近的点，使其到该超平面的距离为最大，也就是：max⁡w,bmin⁡x，i1∥w∥∣wxi+b∣\max _{w, b} \min _{x，i} \frac{1}{\|w\|}\left|w_{x i}+b\right|（用到了点到直线的距离公式）。为了给表达式去掉绝对值，将表达式等价替换为：max⁡(w,b)1∥w∥min⁡xiyi(wxi+b)\max _{(w, b)} \frac{1}{\|w\|} \min _{x_{i}} y_{i}\left(w x_{i}+b\right)
    • 简化约束方程：对于任意一条直线，将w、b同时缩放N倍，其直线还是那条直线，不会变化。所以总存在一个倍数n，使得min⁡xiyi(wxi+b)\min _{x_{i}} y_{i}\left(w x_{i}+b\right)为1，那么此时方程组变为：{max⁡w,b1∥w∥ s.t. yi(wxi+b)⩾1\left\{\begin{array}{ll} \max _{w, b} & \frac{1}{\|w\|} \\ \text { s.t. } & y_{i}\left(w x_{i}+b\right)\geqslant1 \end{array}\right.
      再将第一个方程的最大值问题转化为最小值问题：
      {min⁡u,b12∥w∥2 s.t. yi(wxi+b)⩾1\left\{\begin{array}{l}\min _{u, b} \frac{1}{2}\|w\|^{2} \\ \text { s.t. } \quad y_{i}\left(w x_{i}+b\right) \geqslant 1\end{array}\right.
      这个称为硬间隔SVM的原问题
    • 将带约束的原问题转换为不带约束的问题(拉格朗日函数)：
      L(w,b,λ)=12∥w∥2+∑i=1Nλi(1−yi(w∗xi+b))L(w, b, \lambda)=\frac{1}{2}\|w\|^{2}+\sum_{i=1}^{N} \lambda_{i}\left(1-y_{i}\left(w^{*} x_{i}+b\right)\right)
      按照拉格朗日乘子法的做法，求导不利于简化问题，所以原问题变为：
      {min⁡w,bmax⁡λL(w,b,λ) s.t. λi⩾0\left\{\begin{array}{l}\min _{w, b} \max _{\lambda} L(w, b, \lambda) \\ \text { s.t. } \quad \lambda_{i} \geqslant 0\end{array}\right.
      具体变化流程如下：
      统计学习方法（七）：支持向量机（SVM）
    • 对偶：根据拉格朗日对偶性，可以将上述方程再次变为：
      {max⁡λmin⁡w,bL(w,b,λ) s.t. λi⩾0\left\{\begin{array}{l}\max _{\lambda} \min _{w, b} L(w, b, \lambda) \\ \text { s.t. } \lambda_{i} \geqslant 0\end{array}\right.
    • 分别对上式min⁡w,bL(w,b,x)\min _{w, b} L(w, b, x)中w和b求偏导=0，得到两等式，代入LL中得：
      {max⁡λ(−12∑i=1N∑j=1NλiλjyiyjxiTxj+∑k=1Nλi) s.t. λi=0\left\{\begin{array}{l}\max _{\lambda}\left(-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \lambda_{i} \lambda_{j} y_{i} y_{j} x_{i}^{T} x_{j}+\sum_{k=1}^{N} \lambda_{i}\right) \\ \text { s.t. } \lambda_{i}=0\end{array}\right.
      再将上式中的最大值问题转换为最小值问题，然后求解λi\lambda_{i}
    • 根据KKT条件，代入λi\lambda_{i}得到w和b
      统计学习方法（七）：支持向量机（SVM）
      这样就得到了最终想要的超平面。
  • 软间隔SVM：
    • 再训练数据中噪声点或者非线性分割可以解决的情况存在，那么用到了软间隔。
    • 线性不可分意味着某些样本点 (xi,yi)\left(x_{i}, y_{i}\right) 不能满足函数间隔大于等于 1 的约束条 件 (7.14). 为了解决这个问题, 可以对每个样本点 (xi,yi)\left(x_{i}, y_{i}\right) 引进一个松他变量 ξi⩾0\xi_{i} \geqslant 0，使函数间隔加上松他变量大于等于 1。这样，约束条件变为
      yi(w⋅xi+b)⩾1−ξi y_{i}\left(w \cdot x_{i}+b\right) \geqslant 1-\xi_{i}
      同时，对每个松他变量 ξi,\xi_{i}, 支付一个代价 ξi.\xi_{i} . 目标函数由原来的 12∥w∥2\frac{1}{2}\|w\|^{2} 变成
      12∥w∥2+C∑i=1Nξi \frac{1}{2}\|w\|^{2}+C \sum_{i=1}^{N} \xi_{i}
      这里， C > 0 称为惩罚参数，一般由应用问题决定， C 值大时对误分类的惩罚增大, C 值小时对误分类的惩罚减小. 最小化目标函数包含两层含义: 使 12∥w∥2\frac{1}{2}\|w\|^{2} 尽量小即间隔尽量大，同时使误分类点的个数尽量小， C 是调和二者的系数。
  • 运用核函数的SVM
    统计学习方法（七）：支持向量机（SVM）
    • 将硬间隔推导过程中的x变量转换到z特征空间中。

相关推荐