《西瓜书》第六章 SVM支持向量机 笔记

2024-09-04 00:08

本文主要是介绍《西瓜书》第六章 SVM支持向量机 笔记,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

    • 6.1 间隔与支持向量
      • 6.1.1 超平面
      • 6.1.2 支持向量
      • 6.1.3 间隔
      • 6.1.4 最大间隔
    • 6.2 对偶问题
      • 6.2.1 凸二次规划
      • 6.2.2 对偶问题
      • 6.2.3 支持向量机的一个重要性质
    • 6.3 核函数
      • 6.3.1 支持向量展开式
      • 6.3.2 核函数定理
      • 6.3.3 常用的核函数
      • 6.3.4 核函数特点
    • 6.4 软间隔与正则化
      • 6.4.1 硬间隔
      • 6.4.2 软间隔
      • 6.4.3 替代损失
      • 6.4.4 松弛变量
    • 6.5 支持向量回归
    • 6.6 核方法
      • 6.6.1 表示定理
      • 核函数的巨大威力
      • 核方法定义
      • 核方法的常见用法
    • 6.7 总结
    • 6.8 参考资料

6.1 间隔与支持向量

6.1.1 超平面

样本空间中,任意点x到超平面(w,b)的距离公式为: 推导过程
r = ∣ w T x + b ∣ ∣ ∣ w ∣ ∣ ( 西 瓜 书 , 6.2 ) r = \frac{|w^Tx+b|} {||w||} \quad (西瓜书,6.2) r=wwTx+b(西,6.2)

超平面可以理解为一维空间中的点,二维空间中的线,三维空间中的平面的扩展,是分类的决策边界。支持向量机(Support Vector Machine, SVM)是针对二分类任务设计的,其思想是基于训练样本集D在样本空间找到一个划分超平面,将不同类别的样本划分开。在选择超平面时,应该选择使超平面到离两种类别的样本点尽量远。

6.1.2 支持向量

距离超平面最近的几个训练样本点被称为支持向量

6.1.3 间隔

两个异类支持向量到超平面的距离之和为间隔

6.1.4 最大间隔

间隔最大化:SVM的直观目的就是找到最小函数间隔的样本点(即支持向量),然后最大化它的几何间隔。

要找到最大间隔的超平面,就是要找到满足约束条件的参数w 和 b,使得 r 最大,
即: max ⁡ w , b 2 ∣ ∣ w ∣ ∣ , s . t . y i ( w T x i + b ) ≥ 1 , i = 1 , 2 , . . . , m . ( 西 瓜 书 , 6.5 ) \max_{w,b} \frac{2}{||w||} ,\quad s.t.y_i(w^Tx_i+b)\geq1,\quad i=1,2,...,m. \quad (西瓜书,6.5) w,bmaxw2,s.t.yi(wTxi+b)1,i=1,2,...,m.(西,6.5)

亦即: min ⁡ w , b 1 2 ∣ ∣ w ∣ ∣ 2 , s . t . y i ( w T x i + b ) ≥ 1 , i = 1 , 2 , . . . , m . ( 西 瓜 书 , 6.6 ) \min_{w,b} \frac{1}{2} ||w||^2 ,\quad s.t.y_i(w^Tx_i+b)\geq1,\quad i=1,2,...,m. \quad (西瓜书,6.6) w,bmin21w2,s.t.yi(wTxi+b)1,i=1,2,...,m.(西,6.6)
这就是SVM的基本型

6.2 对偶问题

6.2.1 凸二次规划

公式6.6 本身是一个凸二次规划(convex quadratic programming)问题

6.2.2 对偶问题

更高效求解参数w和b的方法:拉格朗日乘子法
对SVM基本型式子的每条约束添加大于等于零的拉格朗日乘子,得到该问题的拉格朗日函数
L ( w , b , a ) = 1 2 ∣ ∣ w ∣ ∣ 2 + ∑ i = 1 m a i ( 1 − y i ( w T x i + b ) ) ( 西 瓜 书 , 6.8 ) L(w,b,a) =\frac {1}{2}||w||^2 + \sum_{i=1}^ma_i(1-y_i(w^Tx_i+b)) \quad(西瓜书,6.8) L(w,b,a)=21w2+i=1mai(1yi(wTxi+b))(西,6.8)

令L(w,b,α)对w和b的偏导为零:
w = ∑ i = 1 m a i y i x i ( 西 瓜 书 , 6.9 ) w=\sum_{i=1}^m a_iy_ix_i \quad(西瓜书,6.9) w=i=1maiyixi(西,6.9)
0 = ∑ i = 1 m a i y i ( 西 瓜 书 , 6.10 ) 0=\sum_{i=1}^m a_iy_i \quad(西瓜书,6.10) 0=i=1maiyi(西,6.10)

将L(w,b,α)中的w和b消去,得到SVM基本型式子的对偶问题:
max ⁡ a ∑ i = 1 m a i − 1 2 ∑ i = 1 m ∑ j = 1 m a i a j y i y j x i T x j , ( 西 瓜 书 , 6.5 ) \max_{a}\sum_{i=1}^m a_i - \frac {1}{2} \sum_{i=1}^m\sum_{j=1}^m a_i a_j y_i y_j x_i^Tx_j, \quad (西瓜书,6.5) amaxi=1mai21i=1mj=1maiajyiyjxiTxj,(西,6.5) s . t . ∑ i = 1 m a i y i = 0 , a i ≥ 0 , i = 1 , 2 , . . . , m . \quad s.t.\sum_{i=1}^m a_iy_i=0,a_i\geq0,\quad i=1,2,...,m. s.t.i=1maiyi=0,ai0,i=1,2,...,m.

KKT(Karush-Kuhn-Tucker)条件
在这里插入图片描述
求解对偶问题中的α
思路:当做二次规划问题求解
算法

  • 二次规划算法
    缺点:问题的规模正比于训练样本数,开销大
  • SMO(Sequential Minimal Optimization)算法
    先固定αi之外的所有参数,再求αi上的极值,不断执行,直到收敛。

确定偏移项b
思路:使用所有支持向量求解的平均值
在这里插入图片描述

6.2.3 支持向量机的一个重要性质

训练完成后,大部分的训练样本都不用保留,最终模型只与支持向量有关。

6.3 核函数

6.3.1 支持向量展开式

模型最优解可通过训练样本的核函数展开:
在这里插入图片描述

6.3.2 核函数定理

  1. 核矩阵(kernel matrix)K总是半正定的
  2. 只要一个对称函数所对应的核矩阵半正定,就能用作核函数
  3. 对于一个半正定矩阵,总能找到一个与之对应的映射
  4. 任何一个核函数都隐式地定义了一个称谓“再生核希尔伯特空间”(RKHS)的特征空间

特征空间的好坏对支持向量机的性能至关重要。
“核函数的选择”成为支持向量机的最大变数。

6.3.3 常用的核函数

在这里插入图片描述

6.3.4 核函数特点

  1. 两个核函数的线性组合结果也是核函数,即核函数加核函数也是核函数。
  2. 两个核函数的直积也是核函数,即核函数乘核函数也是核函数。
  3. k 1 0 k_10 k10为核函数,则对于任意函数 g ( x ) g(x) g(x) k ( x , z ) = g ( x ) k 1 ( x , z ) g ( z ) k(x,z)=g(x)k1(x,z)g(z) k(x,z)=g(x)k1(x,z)g(z)也是核函数。

6.4 软间隔与正则化

6.4.1 硬间隔

hard margin,要求所有样本都必须划分正确,完全线性可分。

6.4.2 软间隔

soft margin,近似线性可分,允许某些样本划分错误。
解决现实问题:
很难确定合适的核函数使得训练样本在特征空间中线性可分。
缓解方法:

  1. 允许支持向量机在一些样本上出错
  2. 允许某些样本不满足约束: y i ( w T x i + b ) ≥ 1 y_i(w^Tx_i+b)≥1 yi(wTxi+b)1
  3. 在最大化间隔的同时,使不满足约束的样本尽可能少

软间隔支持向量机的优化目标函数变为:
在这里插入图片描述
其中, l 0 / 1 ( z ) l_{0/1}(z) l0/1(z)是0/1损失函数,当z<0时,取值为1;否则为0。
关于常数C,其取无穷大时,约束条件就相当于原SVM条件;
而C取有限值时,允许一些样本出现不满足约束。

6.4.3 替代损失

替代损失(surrogate loss)函数比0/1损失函数一般具有较好的数学性质:

  1. 凸的连续函数
  2. 0/1损失函数的上界

常用的替代损失函数:
在这里插入图片描述

6.4.4 松弛变量

引入松弛变量(slack variables) ξ i ≥ 0 ξ_i≥0 ξi0 后,新的目标函数:
min ⁡ w , b , ξ 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 m ξ i , ( 西 瓜 书 , 6.35 ) \min_{w,b,ξ}\frac {1}{2} ||w||^2 + C\sum_{i=1}^mξ_i, \quad (西瓜书,6.35) w,b,ξmin21w2+Ci=1mξi,(西,6.35)
限制条件:
y i ( w T x i + b ) ≥ 1 − ξ i , ξ i ≥ 0 , i = 1 , 2 , . . . , m y_i(w^Tx_i+b)≥1-ξ_i,ξ_i≥0,i=1,2,...,m yi(wTxi+b)1ξiξi0i=1,2,...,m
这就是常用的“软间隔支持向量机”。

6.5 支持向量回归

支持向量机中的原始样本空间不一定存在符合条件的超平面,但是如果原始空间是有限维,则总存在一个高维特征空间使样本线性可分.核函数就是用来简化计算高维特征空间中的内积的一种方法.核函数选择是支持向量机的最大变数.常用的核函数有线性核,多项式核,高斯核(RBF核),拉普拉斯核,Sigmoid核.对文本数据常用线性核,情况不明时可先尝试高斯核.

SVR问题形式
支持向量回归可以容忍预测输出f(x)和真实输出y之间存在ε的偏差,仅当偏差绝对值大于ε时才计算损失.

支持向量机中许多规划问题都使用拉格朗日对偶算法求解,原因在于改变了算法复杂度.原问题的算法复杂度与样本维度有关,对偶问题的样本复杂度与样本数量有关.如果使用了升维的方法,则此时样本维度会远大于样本数量,在对偶问题下求解会更好.

6.6 核方法

6.6.1 表示定理

在这里插入图片描述

核函数的巨大威力

  1. 表示定理对损失函数没有限制
  2. 对正则化项Ω仅要求单调递增,不要求是凸函数

核方法定义

基于核函数的学习方法

核方法的常见用法

通过“核化”(引入核函数)将线性学习器拓展为非线性学习器
核线性判别分析(Kernelized Linear Discriminant Analysis, KLDA)

6.7 总结

1. SVM框架步骤:
(1)收集数据:可以用任意方法
(2)准备数据:需要数值型数据
(3)分析数据:有助于可视化分隔超平面
(4)训练算法:主要实现两个参数的调优
(5)测试算法:简单的计算过程就可以实现
(6)使用算法:几乎所有分类算法都可以用SVM

2. 向量机中的原始样本空间不一定存在符合条件的超平面,但是如果原始空间是有限维,则总存在一个高维特征空间使样本线性可分.核函数就是用来简化计算高维特征空间中的内积的一种方法.核函数选择是支持向量机的最大变数.常用的核函数有线性核,多项式核,高斯核(RBF核),拉普拉斯核,Sigmoid核.对文本数据常用线性核,情况不明时可先尝试高斯核.

3. 软间隔是缓解支持向量机过拟合的主要手段,软间隔允许某些样本不满足约束.

4. 支持向量回归可以容忍预测输出f(x)和真实输出y之间存在ε的偏差,仅当偏差绝对值大于ε时才计算损失.
支持向量机中许多规划问题都使用拉格朗日对偶算法求解,原因在于改变了算法复杂度.原问题的算法复杂度与样本维度有关,对偶问题的样本复杂度与样本数量有关.如果使用了升维的方法,则此时样本维度会远大于样本数量,在对偶问题下求解会更好.

在这里插入图片描述

6.8 参考资料

《机器学习》(周志华)西瓜书读书笔记(完结)
机器学习 Week 3
西瓜书理解之支持向量机
约束规划问题与凸二次规划
MLb-006 47《机器学习》周志华 第六章:支持向量机
【西瓜书笔记】——支持向量机(SVM)

这篇关于《西瓜书》第六章 SVM支持向量机 笔记的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

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

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络(1)sklearn

系列文章目录 监督学习:参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归(SAheart.csv) 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

论文阅读笔记: Segment Anything

文章目录 Segment Anything摘要引言任务模型数据引擎数据集负责任的人工智能 Segment Anything Model图像编码器提示编码器mask解码器解决歧义损失和训练 Segment Anything 论文地址: https://arxiv.org/abs/2304.02643 代码地址:https://github.com/facebookresear

数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划 非线性规划1. 模型原理1.1 非线性规划的标准型1.2 非线性规划求解的Matlab函数 2. 典型例题3. matlab代码求解3.1 例1 一个简单示例3.2 例2 选址问题1. 第一问 线性规划2. 第二问 非线性规划 非线性规划 非线性规划是一种求解目标函数或约束条件中有一个或几个非线性函数的最优化问题的方法。运筹学的一个重要分支。2

【C++学习笔记 20】C++中的智能指针

智能指针的功能 在上一篇笔记提到了在栈和堆上创建变量的区别,使用new关键字创建变量时,需要搭配delete关键字销毁变量。而智能指针的作用就是调用new分配内存时,不必自己去调用delete,甚至不用调用new。 智能指针实际上就是对原始指针的包装。 unique_ptr 最简单的智能指针,是一种作用域指针,意思是当指针超出该作用域时,会自动调用delete。它名为unique的原因是这个

查看提交历史 —— Git 学习笔记 11

查看提交历史 查看提交历史 不带任何选项的git log-p选项--stat 选项--pretty=oneline选项--pretty=format选项git log常用选项列表参考资料 在提交了若干更新,又或者克隆了某个项目之后,你也许想回顾下提交历史。 完成这个任务最简单而又有效的 工具是 git log 命令。 接下来的例子会用一个用于演示的 simplegit

记录每次更新到仓库 —— Git 学习笔记 10

记录每次更新到仓库 文章目录 文件的状态三个区域检查当前文件状态跟踪新文件取消跟踪(un-tracking)文件重新跟踪(re-tracking)文件暂存已修改文件忽略某些文件查看已暂存和未暂存的修改提交更新跳过暂存区删除文件移动文件参考资料 咱们接着很多天以前的 取得Git仓库 这篇文章继续说。 文件的状态 不管是通过哪种方法,现在我们已经有了一个仓库,并从这个仓

忽略某些文件 —— Git 学习笔记 05

忽略某些文件 忽略某些文件 通过.gitignore文件其他规则源如何选择规则源参考资料 对于某些文件,我们不希望把它们纳入 Git 的管理,也不希望它们总出现在未跟踪文件列表。通常它们都是些自动生成的文件,比如日志文件、编译过程中创建的临时文件等。 通过.gitignore文件 假设我们要忽略 lib.a 文件,那我们可以在 lib.a 所在目录下创建一个名为 .gi

取得 Git 仓库 —— Git 学习笔记 04

取得 Git 仓库 —— Git 学习笔记 04 我认为, Git 的学习分为两大块:一是工作区、索引、本地版本库之间的交互;二是本地版本库和远程版本库之间的交互。第一块是基础,第二块是难点。 下面,我们就围绕着第一部分内容来学习,先不考虑远程仓库,只考虑本地仓库。 怎样取得项目的 Git 仓库? 有两种取得 Git 项目仓库的方法。第一种是在本地创建一个新的仓库,第二种是把其他地方的某个