电信保温杯笔记——《统计学习方法(第二版)——李航》第7章 支持向量机

本文主要是介绍电信保温杯笔记——《统计学习方法(第二版)——李航》第7章 支持向量机,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

电信保温杯笔记——《统计学习方法(第二版)——李航》第7章 支持向量机

  • 论文
  • 介绍
  • 数学基础
    • 拉格朗日对偶性
  • 线性可分的数据集的线性支持向量机
    • 线性可分的数据集的线性支持向量机的定义
    • 函数间隔和几何间隔
      • 函数间隔的定义
      • 几何间隔的定义
      • 函数间隔与几何间隔的关系
    • 间隔最大化
      • 最大间隔的超平面
        • 步骤
        • 最大间隔的超平面的唯一性证明
      • 支持向量和间隔边界
        • 支持向量的定义
        • 间隔边界的定义
        • 例子
    • 支持向量机的求解:拉格朗日对偶性
      • 步骤
      • 例子
  • 线性不可分的数据集的线性支持向量机
    • 线性不可分的数据集的线性支持向量机的定义
    • 支持向量机的求解:拉格朗日对偶性
      • 步骤
    • 支持向量
    • 合页损失函数
  • 线性不可分的数据集的非线性支持向量机
    • 核技巧
      • 核函数的定义
        • 例子
      • 核技巧在支持向量机中的应用
    • 正定核
      • 正定核的充要条件
    • 常用核函数
      • 多项式核函数( polynomial kernel function)
      • 高斯核函数(Gaussian kernel function)
      • 字符串核函数( string kernel function)
    • 非线性支持向量机的定义
    • 步骤
  • 序列最小最优化算法
  • 本章概要
  • 相关视频
  • 相关的笔记
  • 相关代码
    • pytorch
    • tensorflow
      • keras
  • pytorch API:
  • tensorflow API

论文

线性不可分的数据集的线性支持向量机:《Support-vector networks》
非线性支持向量机:《A training algorithm for optimal margin classifiers》
SMO算法:《Fast training support vector machines using parallel sequential minimal optimization》

介绍

电信保温杯笔记——《统计学习方法(第二版)——李航》
本文是对原书的精读,会有大量原书的截图,同时对书上不详尽的地方进行细致解读与改写。

支持向量机(support vector machines,SVM)是一种二类分类模型。它的基本模型是定义在特征空间上的线性分类器,要求特征空间上正例和负例的间隔最大,是感知机的一种特殊情况;支持向量机还包括核技巧,使它成为非线性分类器。支持向量机的学习策略就是间隔最大化,可形式化为一个求解凸二次规划(convex quadratic programming)的问题,也等价于正则化的合页损失函数的最小化问题。

支持向量机学习方法包含构建由简至繁的模型:

  1. 线性可分的数据集的线性支持向量机(linearsupport vector machine in linearly separable case):当训练数据线性可分时,通过硬间隔最大化(hard margin maximization),学习一个线性的分类器,即线性可分支持向量机,又称为硬间隔支持向量机;
  2. 线性不可分的数据集的线性支持向量机(linear supportvector machine):当训练数据线性不可分且只有少部分数据线性不可分时,通过软间隔最大化(soft margin maximization),学习一个线性的分类器,即线性支持向量机,又称为软间隔支持向量机;
  3. 线性不可分的数据集的非线性支持向量机(non-linear support vector machine):当训练数据线性不可分时,通过使用核技巧(kernel trick)及软间隔最大化,学习非线性支持向量机。

假设输入空间与特征空间为两个不同的空间。输入空间为欧氏空间或离散集合,特征空间为欧氏空间或希尔伯特空间。线性可分的数据集的线性支持向量机、线性不可分的数据集的线性支持向量机假设输入空间与特征空间的元素一一对应,并将输入空间中的输入映射为特征空间中的特征向量。非线性支持向量机利用一个从输入空间到特征空间的非线性映射将输入映射为特征向量。所以,输入都由输入空间转换到特征空间,支持向量机的学习是在特征空间进行的。
在这里插入图片描述

数学基础

拉格朗日对偶性

本书的附录C。

“拉格朗日对偶问题”如何直观理解?“KKT条件” “Slater条件” “凸优化”打包理解,这个视频讲解得非常直观。

线性可分的数据集的线性支持向量机

在这里插入图片描述
定义2.2:
在这里插入图片描述
在这里插入图片描述

线性可分的数据集的线性支持向量机的定义

在这里插入图片描述

在这里插入图片描述

函数间隔和几何间隔

在这里插入图片描述

函数间隔的定义

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

点到平面的距离公式:
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

几何间隔的定义

在这里插入图片描述

函数间隔与几何间隔的关系

在这里插入图片描述

间隔最大化

在这里插入图片描述

最大间隔的超平面

在这里插入图片描述

到目前为止,超平面的解不是唯一的,但它的解却有无穷多个。
在这里插入图片描述
γ ^ = 1 \hat{\gamma} = 1 γ^=1 就相对于给了一个约束, w , b w,b w,b 不能再按比例改变了,此时超平面的解是唯一的。

min ⁡ w , b 1 2 ∥ w ∥ 2 ( 7.13 ) s . t . 1 − y i ( w ⋅ x i + b ) ≤ 0 , i = 1 , 2 , . . . , N ( 7.14 ) \begin{aligned} &\underset {w,b}{\operatorname {min} } \quad \frac{1}{2}\rVert w \rVert^2 \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad (7.13)\\ &s.t. \quad 1 - y_i(w \cdot x_i + b) \leq 0 , i = 1,2,...,N \quad (7.14) \end{aligned} w,bmin21w2(7.13)s.t.1yi(wxi+b)0,i=1,2,...,N(7.14)
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

步骤

在这里插入图片描述
在这里插入图片描述

下面的唯一性证明感觉没有必要看。

最大间隔的超平面的唯一性证明

在这里插入图片描述

在这里插入图片描述

支持向量和间隔边界

支持向量的定义

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

间隔边界的定义

在这里插入图片描述
在这里插入图片描述

例子

在这里插入图片描述

在这里插入图片描述

支持向量机的求解:拉格朗日对偶性

在这里插入图片描述

min ⁡ w , b 1 2 ∥ w ∥ 2 ( 7.13 ) s . t . 1 − y i ( w ⋅ x i + b ) ≤ 0 , i = 1 , 2 , . . . , N ( 7.14 ) \begin{aligned} &\underset {w,b}{\operatorname {min} } \quad \frac{1}{2}\rVert w \rVert^2 \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad (7.13)\\ &s.t. \quad 1 - y_i(w \cdot x_i + b) \leq 0 , i = 1,2,...,N \quad (7.14) \end{aligned} w,bmin21w2(7.13)s.t.1yi(wxi+b)0,i=1,2,...,N(7.14)
在这里插入图片描述
w , x w,x w,x 都是列向量, w ⋅ x w \cdot x wx 指的是向量的点积, w T x w^T x wTx 指的是向量相乘,两个表示在本文中都是一样的,但后者在求导运算上会更加合适,所以下文有时候会对这种地方进行改写。
L ( w , b , α ) = 1 2 ∥ w ∥ 2 + ∑ i = 1 N α i ( 1 − y i ( w T x i + b ) ) ( 7.18 ) L(w,b,\alpha) = \frac{1}{2}\rVert w \rVert^2 +\sum\limits_{i = 1}^N \alpha_i \left( 1-y_i(w^T x_i + b) \right) \quad (7.18) L(w,b,α)=21w2+i=1Nαi(1yi(wTxi+b))(7.18)
在这里插入图片描述
在这里插入图片描述

L ( w , b , α ) = 1 2 ∥ w ∥ 2 + ∑ i = 1 N α i ( 1 − y i ( w T x i + b ) ) = 1 2 w T w + ∑ i = 1 N α i ( 1 − y i ( w T x i + b ) ) = 1 2 ∑ i = 1 N α i y i x i T ∑ j = 1 N α j y j x j + ∑ i = 1 N α i ( 1 − y i ( ∑ j = 1 N α j y j x j T x i + b ) ) = 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j x i T x j + ∑ i = 1 N α i − ∑ i = 1 N ∑ j = 1 N α i α j y i y j x i T x j + b ∑ i = 1 N α i y i = − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j x i T x j + ∑ i = 1 N α i \begin{aligned} L(w,b,\alpha) &= \frac{1}{2}\rVert w \rVert^2 +\sum\limits_{i = 1}^N \alpha_i \left( 1-y_i(w^T x_i + b) \right) \\ &= \frac{1}{2} w^Tw + \sum\limits_{i = 1}^N \alpha_i \left( 1-y_i(w^T x_i + b) \right) \\ &= \frac{1}{2} \sum\limits_{i = 1}^N \alpha_iy_ix_i^T \sum\limits_{j = 1}^N \alpha_jy_jx_j + \sum\limits_{i = 1}^N \alpha_i \left( 1-y_i(\sum\limits_{j = 1}^N \alpha_jy_jx_j^T x_i + b) \right) \\ &= \frac{1}{2} \sum\limits_{i = 1}^N \sum\limits_{j = 1}^N \alpha_i \alpha_j y_i y_j x_i^T x_j + \sum\limits_{i = 1}^N \alpha_i -\sum\limits_{i = 1}^N \sum\limits_{j = 1}^N \alpha_i \alpha_j y_i y_j x_i^T x_j + b \sum\limits_{i = 1}^N \alpha_iy_i \\ &= - \frac{1}{2} \sum\limits_{i = 1}^N \sum\limits_{j = 1}^N \alpha_i \alpha_j y_i y_j x_i^T x_j + \sum\limits_{i = 1}^N \alpha_i \end{aligned} L(w,b,α)=21w2+i=1Nαi(1yi(wTxi+b))=21wTw+i=1Nαi(1yi(wTxi+b))=21i=1NαiyixiTj=1Nαjyjxj+i=1Nαi(1yi(j=1NαjyjxjTxi+b))=21i=1Nj=1NαiαjyiyjxiTxj+i=1Nαii=1Nj=1NαiαjyiyjxiTxj+bi=1Nαiyi=21i=1Nj=1NαiαjyiyjxiTxj+i=1Nαi

min ⁡ w , b L ( w , b , α ) = − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j x i T x j + ∑ i = 1 N α i \underset {w,b}{\operatorname {min} } \, L(w,b,\alpha) = - \frac{1}{2} \sum\limits_{i = 1}^N \sum\limits_{j = 1}^N \alpha_i \alpha_j y_i y_j x_i^T x_j + \sum\limits_{i = 1}^N \alpha_i w,bminL(w,b,α)=21i=1Nj=1NαiαjyiyjxiTxj+i=1Nαi
在这里插入图片描述

上述求解过程可以归结为下面定理:
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

步骤

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

例子

在这里插入图片描述
在这里插入图片描述

线性不可分的数据集的线性支持向量机

在这里插入图片描述在这里插入图片描述

min ⁡ w , b , ξ 1 2 ∥ w ∥ 2 + C ∑ i = 1 N ξ i ( 7.32 ) s . t . 1 − ξ i − y i ( w ⋅ x i + b ) ≤ 0 , i = 1 , 2 , . . . , N ( 7.33 ) − ξ i ≤ 0 , i = 1 , 2 , . . . , N ( 7.34 ) \begin{aligned} &\underset {w,b,\xi}{\operatorname {min} } \quad \frac{1}{2}\rVert w \rVert^2 + C\sum\limits_{i = 1}^N \xi_i \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\,\,\, (7.32)\\ &s.t. \quad 1 - \xi_i - y_i(w \cdot x_i + b) \leq 0 , i = 1,2,...,N \quad (7.33) \\ & \quad\quad\, - \xi_i \leq 0 , i = 1,2,...,N \quad\quad\quad\quad\quad\quad\quad\quad\,\,\, (7.34) \\ \end{aligned} w,b,ξmin21w2+Ci=1Nξi(7.32)s.t.1ξiyi(wxi+b)0,i=1,2,...,N(7.33)ξi0,i=1,2,...,N(7.34)
在这里插入图片描述
这个 b b b 的解可能不唯一暂时没想明白。
在这里插入图片描述

线性不可分的数据集的线性支持向量机的定义

在这里插入图片描述

支持向量机的求解:拉格朗日对偶性

在这里插入图片描述

原始问题(7.32)~(7.34)
min ⁡ w , b , ξ 1 2 ∥ w ∥ 2 + C ∑ i = 1 N ξ i ( 7.32 ) s . t . 1 − ξ i − y i ( w ⋅ x i + b ) ≤ 0 , i = 1 , 2 , . . . , N ( 7.33 ) − ξ i ≤ 0 , i = 1 , 2 , . . . , N ( 7.34 ) \begin{aligned} &\underset {w,b,\xi}{\operatorname {min} } \quad \frac{1}{2}\rVert w \rVert^2 + C\sum\limits_{i = 1}^N \xi_i \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\,\,\, (7.32)\\ &s.t. \quad 1 - \xi_i - y_i(w \cdot x_i + b) \leq 0 , i = 1,2,...,N \quad (7.33) \\ & \quad\quad\, - \xi_i \leq 0 , i = 1,2,...,N \quad\quad\quad\quad\quad\quad\quad\quad\,\,\, (7.34) \\ \end{aligned} w,b,ξmin21w2+Ci=1Nξi(7.32)s.t.1ξiyi(wxi+b)0,i=1,2,...,N(7.33)ξi0,i=1,2,...,N(7.34)
原始最优化问题(7.32)~(7.34)的拉格朗日函数是
L ( w , b , ξ , α , μ ) = 1 2 ∥ w ∥ 2 + C ∑ i = 1 N ξ i + ∑ i = 1 N α i ( 1 − ξ i − y i ( w T x i + b ) ) − ∑ i = 1 N μ i ξ i = 1 2 w T w + C ∑ i = 1 N ξ i + ∑ i = 1 N α i ( 1 − ξ i − y i ( w T x i + b ) ) − ∑ i = 1 N μ i ξ i ( 7.40 ) \begin{aligned} L(w,b,\xi,\alpha,\mu) &= \frac{1}{2}\rVert w \rVert^2 + C\sum\limits_{i = 1}^N\xi_i +\sum\limits_{i = 1}^N \alpha_i \left( 1 - \xi_i -y_i(w^T x_i + b) \right) - \sum\limits_{i = 1}^N \mu_i \xi_i \quad \\ &= \frac{1}{2} w^Tw + C\sum\limits_{i = 1}^N\xi_i +\sum\limits_{i = 1}^N \alpha_i \left( 1 - \xi_i -y_i(w^T x_i + b) \right) - \sum\limits_{i = 1}^N \mu_i \xi_i \quad (7.40) \end{aligned} L(w,b,ξ,α,μ)=21w2+Ci=1Nξi+i=1Nαi(1ξiyi(wTxi+b))i=1Nμiξi=21wTw+Ci=1Nξi+i=1Nαi(1ξiyi(wTxi+b))i=1Nμiξi(7.40)
其中, α i ≥ 0 , μ i ≥ 0 \alpha_i \geq 0, \mu_i \geq 0 αi0,μi0
在这里插入图片描述

L ( w , b , ξ , α , μ ) = 1 2 w T w + C ∑ i = 1 N ξ i + ∑ i = 1 N α i ( 1 − ξ i − y i ( w T x i + b ) ) − ∑ i = 1 N μ i ξ i = 1 2 ∑ i = 1 N α i y i x i T ∑ j = 1 N α j y j x j + C ∑ i = 1 N ξ i + ∑ i = 1 N α i ( 1 − ξ i − y i ( ∑ j = 1 N α j y j x j T x i + b ) ) − ∑ i = 1 N μ i ξ i = 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j x i T x j + ∑ i = 1 N ( C − α i − μ i ) ξ i + ∑ i = 1 N α i − ∑ i = 1 N ∑ j = 1 N α i α j y i y j x i T x j + b ∑ i = 1 N α i y i = − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j x i T x j + ∑ i = 1 N α i \begin{aligned} L(w,b,\xi,\alpha,\mu) &= \frac{1}{2} w^Tw + C\sum\limits_{i = 1}^N\xi_i +\sum\limits_{i = 1}^N \alpha_i \left( 1 - \xi_i -y_i(w^T x_i + b) \right) - \sum\limits_{i = 1}^N \mu_i \xi_i \\ &= \frac{1}{2} \sum\limits_{i = 1}^N \alpha_iy_ix_i^T \sum\limits_{j = 1}^N \alpha_jy_jx_j + C\sum\limits_{i = 1}^N\xi_i + \sum\limits_{i = 1}^N \alpha_i \left( 1 - \xi_i -y_i(\sum\limits_{j = 1}^N \alpha_jy_jx_j^T x_i + b) \right) - \sum\limits_{i = 1}^N \mu_i \xi_i \\ &= \frac{1}{2} \sum\limits_{i = 1}^N \sum\limits_{j = 1}^N \alpha_i \alpha_j y_i y_j x_i^T x_j + \sum\limits_{i = 1}^N (C - \alpha_i - \mu_i) \xi_i + \sum\limits_{i = 1}^N \alpha_i -\sum\limits_{i = 1}^N \sum\limits_{j = 1}^N \alpha_i \alpha_j y_i y_j x_i^T x_j + b \sum\limits_{i = 1}^N \alpha_iy_i \\ &= - \frac{1}{2} \sum\limits_{i = 1}^N \sum\limits_{j = 1}^N \alpha_i \alpha_j y_i y_j x_i^T x_j + \sum\limits_{i = 1}^N \alpha_i \end{aligned} L(w,b,ξ,α,μ)=21wTw+Ci=1Nξi+i=1Nαi(1ξiyi(wTxi+b))i=1Nμiξi=21i=1NαiyixiTj=1Nαjyjxj+Ci=1Nξi+i=1Nαi(1ξiyi(j=1NαjyjxjTxi+b))i=1Nμiξi=21i=1Nj=1NαiαjyiyjxiTxj+i=1N(Cαiμi)ξi+i=1Nαii=1Nj=1NαiαjyiyjxiTxj+bi=1Nαiyi=21i=1Nj=1NαiαjyiyjxiTxj+i=1Nαi

min ⁡ w , b , ξ L ( w , b , ξ , α , μ ) = − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j x i T x j + ∑ i = 1 N α i \underset {w,b,\xi }{\operatorname {min} } \, L(w,b,\xi,\alpha,\mu) = - \frac{1}{2} \sum\limits_{i = 1}^N \sum\limits_{j = 1}^N \alpha_i \alpha_j y_i y_j x_i^T x_j + \sum\limits_{i = 1}^N \alpha_i w,b,ξminL(w,b,ξ,α,μ)=21i=1Nj=1NαiαjyiyjxiTxj+i=1Nαi
在这里插入图片描述
在这里插入图片描述

将上述过程记为如下定理:
在这里插入图片描述
在这里插入图片描述

步骤

在这里插入图片描述
这是一个落在间隔边界上的点,与线性可分的数据集的线性支持向量机求解 b b b 时相同。
在这里插入图片描述

支持向量

在这里插入图片描述
在这里插入图片描述

min ⁡ w , b , ξ L ( w , b , ξ , α , μ ) = 1 2 w T w + C ∑ i = 1 N ξ i + ∑ i = 1 N α i ( 1 − ξ i − y i ( w T x i + b ) ) − ∑ i = 1 N μ i ξ i s . t . 1 − ξ i − y i ( w ⋅ x i + b ) ≤ 0 , i = 1 , 2 , . . . , N − ξ i ≤ 0 , i = 1 , 2 , . . . , N α i ≥ 0 , i = 1 , 2 , . . . , N μ i ≥ 0 , i = 1 , 2 , . . . , N C − α i − μ i = 0 , i = 1 , 2 , . . . , N C > 0 \begin{aligned} & \underset {w,b,\xi }{\operatorname {min} } \, L(w,b,\xi,\alpha,\mu) = \frac{1}{2} w^Tw + C\sum\limits_{i = 1}^N\xi_i +\sum\limits_{i = 1}^N \alpha_i \left( 1 - \xi_i -y_i(w^T x_i + b) \right) - \sum\limits_{i = 1}^N \mu_i \xi_i \\ &s.t. \quad 1 - \xi_i - y_i(w \cdot x_i + b) \leq 0 , i = 1,2,...,N \\ & \quad\quad\, - \xi_i \leq 0 , i = 1,2,...,N \\ & \quad\quad\, \alpha_i \geq 0 , i = 1,2,...,N \\ & \quad\quad\, \mu_i \geq 0 , i = 1,2,...,N \\ & \quad\quad\, C - \alpha_i - \mu_i = 0 , i = 1,2,...,N \\ & \quad\quad\, C > 0 \end{aligned} w,b,ξminL(w,b,ξ,α,μ)=21wTw+Ci=1Nξi+i=1Nαi(1ξiyi(wTxi+b))i=1Nμiξis.t.1ξiyi(wxi+b)0,i=1,2,...,Nξi0,i=1,2,...,Nαi0,i=1,2,...,Nμi0,i=1,2,...,NCαiμi=0,i=1,2,...,NC>0
以正例为例:

类型 y i ( w T x i + b ) y_i(w^T x_i + b) yi(wTxi+b) α i \alpha_i αi ξ i \xi_i ξi μ i \mu_i μi位置
取值范围 ≥ 1 − ξ i \geq 1 - \xi_i 1ξi 0 ≤ α i ≤ C 0 \leq \alpha_i \leq C 0αiC ≥ 0 \geq 0 0 ≥ 0 \geq 0 0
A支持向量 = 1 − ξ i = 1 - \xi_i =1ξi 0 < α i < C 0<\alpha_i <C 0<αi<C,约束 = 0 =0 =0 0 < μ i < C 0<\mu_i < C 0<μi<C,约束在软间隔边界上
B支持向量 = 1 − ξ i = 1 - \xi_i =1ξi = C =C =C,约束 0 < ξ i < 1 0<\xi_i <1 0<ξi<1 = 0 =0 =0,松弛在软间隔边界与分离超平面之间
C支持向量 = 1 − ξ i = 1 - \xi_i =1ξi = C =C =C,约束 > 1 >1 >1 = 0 =0 =0,松弛在分离超平面误分一侧
D非支持向量 > 1 − ξ i > 1 - \xi_i >1ξi = 0 =0 =0,松弛 = 0 =0 =0 0 < μ i < C 0<\mu_i < C 0<μi<C,约束正确分类且在软间隔之外

合页损失函数

在这里插入图片描述
下面定理说明线性不可分的数据集的线性支持向量机求解等价于其关于合页损失函数+正则化的优化问题的求解:
在这里插入图片描述
在这里插入图片描述
不同位置的点造成的损失为:
在这里插入图片描述

线性不可分的数据集的非线性支持向量机

在这里插入图片描述

核技巧

在这里插入图片描述
在这里插入图片描述

核函数的定义

在这里插入图片描述

例子

在这里插入图片描述

核技巧在支持向量机中的应用

在这里插入图片描述
在这里插入图片描述

正定核

在这里插入图片描述
其实在机器学习,深度学习这一块,经常会用到向量空间的概念,这里涉及矩阵分析的一些概念,其中最常见的无非就是线性空间,内积空间,空间上两点间距离这几个概念。我们平时使用的这些概念,通常都是在欧氏空间上使用,比如加减乘、点积、2点间距离,但如果我们使用的空间不再是欧氏空间,而是其他空间,那么我们就要定义元素、向量在这些空间上的运算法则,下面那段话中的第一句,就是为上述概念的运算法则提供保障的。
在这里插入图片描述
以下是定义在这些构造的空间上的运算法则。不看其实具体证明其实也没什么关系,只需知道它就是定义了一个新的内积运算,用这个新内积运算去代替下面公式中的 x i T ⋅ x j x_i^T \cdot x_j xiTxj,从而得到非线性运算的支持向量机。可以直接跳到序列最小最优化算法的部分。
min ⁡ w , b , ξ L ( w , b , ξ , α , μ ) = − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j x i T x j + ∑ i = 1 N α i \underset {w,b,\xi }{\operatorname {min} } \, L(w,b,\xi,\alpha,\mu) = - \frac{1}{2} \sum\limits_{i = 1}^N \sum\limits_{j = 1}^N \alpha_i \alpha_j y_i y_j x_i^T x_j + \sum\limits_{i = 1}^N \alpha_i w,b,ξminL(w,b,ξ,α,μ)=21i=1Nj=1NαiαjyiyjxiTxj+i=1Nαi

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

正定核的充要条件

在这里插入图片描述
在这里插入图片描述

常用核函数

多项式核函数( polynomial kernel function)

在这里插入图片描述

高斯核函数(Gaussian kernel function)

在这里插入图片描述

字符串核函数( string kernel function)

在这里插入图片描述
在这里插入图片描述

如上所述,利用核技巧,可以将线性分类的学习方法应用到非线性分类问题中去。将线性支持向量机扩展到非线性支持向量机,只需将线性支持向量机对偶形式中的内积换成核函数。

非线性支持向量机的定义

在这里插入图片描述

步骤

在这里插入图片描述

序列最小最优化算法

先看这个视频,再看书上的推导:快速理解SMO算法
在这里插入图片描述
在这里插入图片描述

两个变量二次规划的求解方法

在这里插入图片描述
在这里插入图片描述
观察公式(7.101)和(7.102)可知, K 11 , K 22 > 0 K_{11},K_{22} > 0 K11,K22>0 α 1 = ς y 1 − α 2 y 1 y 2 \alpha_1 = \varsigma y_1 - \alpha_2 y_1y_2 α1=ςy1α2y1y2,将(7.102)带入(7.101)必然得到关于 α 2 \alpha_2 α2 的一元二次函数 f ( α 2 ) f(\alpha_2) f(α2),且开口向上:
f ( α 2 ) = a ⋅ α 2 2 + b ⋅ α 2 + c , a > 0 f(\alpha_2) = a\cdot \alpha_2^2 + b \cdot \alpha_2 + c,a>0 f(α2)=aα22+bα2+c,a>0
此时(7.102)这个子问题的最小值变成求一元二次函数 f ( α 2 ) f(\alpha_2) f(α2)的最小值了,接下来问题的关键就在于 α 2 \alpha_2 α2 的定义域了。令 ς y 1 = k \varsigma y_1 = k ςy1=k

y 1 = y 2 = 1 y_1 = y_2 = 1 y1=y2=1 时,
α 1 = ς y 1 − α 2 y 1 y 2 = k − α 2 , ∵ α 1 ∈ [ 0 , C ] , α 2 = k − α 1 , ∴ α 2 ∈ [ k − C , k ] , 又 ∵ α 2 ∈ [ 0 , C ] , ∴ α 2 ∈ [ m a x { k − C , 0 } , m i n { k , C } ] , 又 ∵ k = α 1 + α 2 , ∴ α 2 ∈ [ m a x { α 1 + α 2 − C , 0 } , m i n { α 1 + α 2 , C } ] . \begin{aligned} & \alpha_1 = \varsigma y_1 - \alpha_2 y_1y_2 = k - \alpha_2, \\ & \because \alpha_1 \in [0,C], \alpha_2 = k - \alpha_1, \\ & \therefore \alpha_2 \in [k - C,k], \\ & \text{又} \because \alpha_2 \in [0,C], \\ & \therefore \alpha_2 \in [ max\{k - C, 0\} , min\{k , C\} ], \\ & \text{又} \because k = \alpha_1 + \alpha_2, \\ & \therefore \alpha_2 \in [ max\{\alpha_1 + \alpha_2 - C, 0\} , min\{\alpha_1 + \alpha_2 , C\} ]. \end{aligned} α1=ςy1α2y1y2=kα2,α1[0,C],α2=kα1,α2[kC,k],α2[0,C],α2[max{kC,0},min{k,C}],k=α1+α2,α2[max{α1+α2C,0},min{α1+α2,C}].
L = m a x { α 1 + α 2 − C , 0 } , H = m i n { α 1 + α 2 , C } L = max\{\alpha_1 + \alpha_2 - C, 0\}, H = min\{\alpha_1 + \alpha_2 , C\} L=max{α1+α2C,0},H=min{α1+α2,C}

y 1 ≠ y 2 y_1 \neq y_2 y1=y2 时,
α 1 = ς y 1 − α 2 y 1 y 2 = k + α 2 , ∵ α 1 ∈ [ 0 , C ] , α 2 = α 1 − k , ∴ α 2 ∈ [ − k , C − k ] , 又 ∵ α 2 ∈ [ 0 , C ] , ∴ α 2 ∈ [ m a x { − k , 0 } , m i n { C − k , C } ] , 又 ∵ k = α 1 − α 2 , ∴ α 2 ∈ [ m a x { α 2 − α 1 , 0 } , m i n { C + α 2 − α 1 , C } ] . \begin{aligned} & \alpha_1 = \varsigma y_1 - \alpha_2 y_1y_2 = k + \alpha_2, \\ & \because \alpha_1 \in [0,C], \alpha_2 = \alpha_1 - k, \\ & \therefore \alpha_2 \in [-k, C - k], \\ & \text{又} \because \alpha_2 \in [0,C], \\ & \therefore \alpha_2 \in [ max\{-k, 0\} , min\{C - k , C\} ], \\ & \text{又} \because k = \alpha_1 - \alpha_2, \\ & \therefore \alpha_2 \in [ max\{\alpha_2 - \alpha_1 , 0\} , min\{C + \alpha_2 - \alpha_1 , C\} ]. \end{aligned} α1=ςy1α2y1y2=k+α2,α1[0,C],α2=α1k,α2[k,Ck],α2[0,C],α2[max{k,0},min{Ck,C}],k=α1α2,α2[max{α2α1,0},min{C+α2α1,C}].
L = m a x { α 2 − α 1 , 0 } , H = m i n { C + α 2 − α 1 , C } L = max\{\alpha_2 - \alpha_1 , 0\}, H = min\{C + \alpha_2 - \alpha_1 , C\} L=max{α2α1,0},H=min{C+α2α1,C}

此时, α 2 ∈ [ L , H ] \alpha_2 \in [ L , H ] α2[L,H]。我们知道一元二次函数 f ( α 2 ) f(\alpha_2) f(α2)在不考虑定义域时,最小值时的 α 2 \alpha_2 α2 是很容易求出的,记此时的 α 2 \alpha_2 α2 α 2 n e w , u n c \alpha_2^{new,unc} α2new,unc,缩写为:new,unclip,而考虑定义域时,一元二次函数 f ( α 2 ) f(\alpha_2) f(α2) 取得最小值时的 α 2 \alpha_2 α2 记为 α 2 n e w \alpha_2^{new} α2new,下图展示了各种情况时的变量关系:
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

上述过程可以记为如下定理:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

变量的选择方法

SMO 算法在每个子问题中选择两个变量优化,其中至少一个变量是违反KKT条件的。

1. 第1个变量的选择

在这里插入图片描述

以正例点为例:
点 | 类型 | y i ( w T x i + b ) y_i(w^T x_i + b) yi(wTxi+b) | α i \alpha_i αi | ξ i \xi_i ξi | μ i \mu_i μi | 位置
-------- | ----- | ----- | ----- | ----- | ----- | ----- | -----
取值范围 | | ≥ 1 − ξ i \geq 1 - \xi_i 1ξi | 0 ≤ α i ≤ C 0 \leq \alpha_i \leq C 0αiC| ≥ 0 \geq 0 0 | ≥ 0 \geq 0 0 |
A | 支持向量 | = 1 − ξ i = 1 - \xi_i =1ξi | 0 < α i < C 0<\alpha_i <C 0<αi<C,约束 | = 0 =0 =0 | 0 < μ i < C 0<\mu_i < C 0<μi<C,约束 | 在软间隔边界上
B | 支持向量 | = 1 − ξ i = 1 - \xi_i =1ξi | = C =C =C,约束 | 0 < ξ i < 1 0<\xi_i <1 0<ξi<1 | = 0 =0 =0,松弛 | 在软间隔边界与分离超平面之间
C | 支持向量 | = 1 − ξ i = 1 - \xi_i =1ξi | = C =C =C,约束 | > 1 >1 >1 | = 0 =0 =0,松弛 | 在分离超平面误分一侧
D | 非支持向量 | > 1 − ξ i > 1 - \xi_i >1ξi | = 0 =0 =0,松弛 | = 0 =0 =0 | 0 < μ i < C 0<\mu_i < C 0<μi<C,约束 | 正确分类且在软间隔之外
min ⁡ w , b , ξ L ( w , b , ξ , α , μ ) = 1 2 w T w + C ∑ i = 1 N ξ i + ∑ i = 1 N α i ( 1 − ξ i − y i ( w T x i + b ) ) − ∑ i = 1 N μ i ξ i s . t . 1 − ξ i − y i ( w ⋅ x i + b ) ≤ 0 , i = 1 , 2 , . . . , N − ξ i ≤ 0 , i = 1 , 2 , . . . , N α i ≥ 0 , i = 1 , 2 , . . . , N μ i ≥ 0 , i = 1 , 2 , . . . , N C − α i − μ i = 0 , i = 1 , 2 , . . . , N C > 0 \begin{aligned} & \underset {w,b,\xi }{\operatorname {min} } \, L(w,b,\xi,\alpha,\mu) = \frac{1}{2} w^Tw + C\sum\limits_{i = 1}^N\xi_i +\sum\limits_{i = 1}^N \alpha_i \left( 1 - \xi_i -y_i(w^T x_i + b) \right) - \sum\limits_{i = 1}^N \mu_i \xi_i \\ &s.t. \quad 1 - \xi_i - y_i(w \cdot x_i + b) \leq 0 , i = 1,2,...,N \\ & \quad\quad\, - \xi_i \leq 0 , i = 1,2,...,N \\ & \quad\quad\, \alpha_i \geq 0 , i = 1,2,...,N \\ & \quad\quad\, \mu_i \geq 0 , i = 1,2,...,N \\ & \quad\quad\, C - \alpha_i - \mu_i = 0 , i = 1,2,...,N \\ & \quad\quad\, C > 0 \end{aligned} w,b,ξminL(w,b,ξ,α,μ)=21wTw+Ci=1Nξi+i=1Nαi(1ξiyi(wTxi+b))i=1Nμiξis.t.1ξiyi(wxi+b)0,i=1,2,...,Nξi0,i=1,2,...,Nαi0,i=1,2,...,Nμi0,i=1,2,...,NCαiμi=0,i=1,2,...,NC>0
在这里插入图片描述
在这里插入图片描述

2. 第2个变量的选择

在这里插入图片描述
在这里插入图片描述

3. 计算阈值 b b b 和差值 E i E_i Ei

在这里插入图片描述

步骤

在这里插入图片描述

本章概要

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

相关视频

快速理解SMO算法

相关的笔记

hktxt /Learn-Statistical-Learning-Method

相关代码

Dod-o /Statistical-Learning-Method_Code

关于def isSatisfyKKT(self, i):
toler变量是SMO算法第1个变量的选择中的检验参数 ϵ \epsilon ϵ
math.fabs(self.alpha[i]) < self.toler 等价于 α i = 0 \alpha_i = 0 αi=0
math.fabs(self.alpha[i] - self.C) < self.toler 等价于 α i = C \alpha_i = C αi=C
self.alpha[i] > -self.toler) and (self.alpha[i] < (self.C + self.toler 等价于 0 < α i < C 0 < \alpha_i < C 0<αi<C
在这里插入图片描述
在这里插入图片描述

pytorch

tensorflow

keras

pytorch API:

tensorflow API

这篇关于电信保温杯笔记——《统计学习方法(第二版)——李航》第7章 支持向量机的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/550380

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

闲置电脑也能活出第二春?鲁大师AiNAS让你动动手指就能轻松部署

对于大多数人而言,在这个“数据爆炸”的时代或多或少都遇到过存储告急的情况,这使得“存储焦虑”不再是个别现象,而将会是随着软件的不断臃肿而越来越普遍的情况。从不少手机厂商都开始将存储上限提升至1TB可以见得,我们似乎正处在互联网信息飞速增长的阶段,对于存储的需求也将会不断扩大。对于苹果用户而言,这一问题愈发严峻,毕竟512GB和1TB版本的iPhone可不是人人都消费得起的,因此成熟的外置存储方案开

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

hdu1496(用hash思想统计数目)

作为一个刚学hash的孩子,感觉这道题目很不错,灵活的运用的数组的下标。 解题步骤:如果用常规方法解,那么时间复杂度为O(n^4),肯定会超时,然后参考了网上的解题方法,将等式分成两个部分,a*x1^2+b*x2^2和c*x3^2+d*x4^2, 各自作为数组的下标,如果两部分相加为0,则满足等式; 代码如下: #include<iostream>#include<algorithm

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

浅谈主机加固,六种有效的主机加固方法

在数字化时代,数据的价值不言而喻,但随之而来的安全威胁也日益严峻。从勒索病毒到内部泄露,企业的数据安全面临着前所未有的挑战。为了应对这些挑战,一种全新的主机加固解决方案应运而生。 MCK主机加固解决方案,采用先进的安全容器中间件技术,构建起一套内核级的纵深立体防护体系。这一体系突破了传统安全防护的局限,即使在管理员权限被恶意利用的情况下,也能确保服务器的安全稳定运行。 普适主机加固措施: