支持向量机（三）——线性支持向量机
2024-05-12m.verywind.com
~
支持向量机(Support Vector Machine,SVM)是监督学习中非常经典的算法。笔者主要参考学习的是李航老师《统计学习方法（第二版）》[1]和周志华老师的西瓜书《机器学习》[2]。
一方面，线性可分支持向量机只适用于线性可分的训练数据集，对于线性不可分的训练数据集则是无能为力的。
另一方面，即使训练数据集线性可分，线性可分支持向量机强依赖于离分类超平面最近的样本[3]，过拟合的风险很大。
这时候就需要有一定容错能力的分类模型，线性支持向量机，或者叫软间隔支持向量机，就可以做到这样的容错性。
这里我采用周志华老师西瓜书[2]的思路来整理这部分。
对于线性可分支持向量机，要求所有样本满足以下约束
而软间隔则允许某些样本不满足这样的约束。
在最大化间隔的同时，不满足约束的样本要尽量少。此时，优化目标可以写为
其中， 是一般化的损失函数， 被称作惩罚参数，调节间隔最大化和参数惩罚这二者关系。
我们先看惩罚参数 。当 值较大时对误分类惩罚较大，特别地，当C取无穷大时，所有样本都要满足式 约束，模型等价于线性可分支持向量机[3]；当 取有限值时，模型允许一些样本不满足约束。
接下来讨论损失函数 。当 使用不同的损失函数时的模型状态，周志华老师的西瓜书[2]有简单讨论。当 是合页损失函数时，模型就是线性支持向量机。李航老师《统计学习方法（第二版）》[1]的相关章节证明了线性支持向量机和基于合页损失函数的优化问题的等价性。合页损失函数如下
图1[2]
当 时，式 可重写为
引入松弛变量 ，将上式再重写为
优化问题一：
与线性可分支持向量机类似，线性支持向量机（式 ）的拉格朗日对偶函数如下
原问题（式 ）是凸优化问题，则优化问题 与原问题等价。
第一步， 求 对 的极小值。
得
将式 代入式 ，可得
第二步， 求 对 的极大值，即得对偶问题。
这里需要注意，式 等号右边表达式没有 ，直接求解对 的极大值即可。对偶问题如下
上式中，因为 不在最优化表达式中，可以利用等式约束消去，简化约束。再把求极大转换成求极小，得到对偶问题如下
优化问题二：
第三步， 求解分类超平面和分类模型。
对于已求解出优化问题二（式 ）的最优解 ，则类似于线性可分支持向量机[3]的推导过程。
原问题（式 ）是凸优化问题，则满足KKT条件的点是原问题和对偶问题的最优解（具体请参见[4]）
根据式 可得
观察式 、 和 ，先看式 ，当 时，有
再看式 ，当 时，有
此时再看式 ，当 时，必有 ，综上讨论，当 时，有
再将式 代入上式，并于式 联立，可得线性支持向量机的最优分类超平面参数为
这里需要注意，在李航老师《统计学习方法（第二版）》[1]相关章节中，和式 相同表达的式子是不严谨的，如果没看到这一段，这句话略过。
线性支持向量机的支持向量会复杂一些。如下图
首先， 定义 的样本点 为支持向量。
其次， 每个支持向量 到其对应的间隔边界的距离为 。推导过程如下。
点到超平面的距离公式为：
先看正类，正类的间隔边界超平面为： ，对应的点到间隔边界超平面的距离公式为： 。对于正例的支持向量，有 ，根据式 ，有 ，代入距离公式，即可到结论。
负类推导过程类似。
再次， 根据以上结论，分析支持向量。
根据上面式 和 ，消去 ，则有
第一种情况， 当 时，则 ，则此支持向量到对应间隔边界的距离 ，即此支持向量在间隔边界超平面上。
第二种情况， 当 且 时，此支持向量到对应间隔边界的距离 ，此支持向量分类正确，在间隔边界与分离超平面之间。
第三种情况， 当 且 时，此支持向量到对应间隔边界的距离 ，此支持向量在分离超平面上。
第四种情况， 当 且 时，此支持向量到对应间隔边界的距离 ，此支持向量分类错误。
这里需要注意，有没有 和 同时成立的点，这里没有找到确定或否定的证据。如果谁有这方面的资料，还烦请告知笔者，先行谢过，联系邮箱：hpfhepf@gmail.com。
[1]、《统计学习方法（第二版）》，李航著，清华大学出版社
[2]、《机器学习》，周志华著，清华大学出版社
[3]、 《支持向量机（一）——线性可分支持向量机导出》
[4]、 《凸优化（八）——Lagrange对偶问题》
B、相关目录
[a]、 支持向量机（一）——线性可分支持向量机导出
[b]、 支持向量机（二）——线性可分支持向量机求解
[c]、支持向量机（三）——线性支持向量机
[d]、 支持向量机（四）——核方法
[e]、 支持向量机（五）——SMO算法
请简述线性可分svm的基本思想 答：核技巧）。support vector machineSVM，全称是support vector machine，中文名叫支持向量机。SVM是一个面向数据的分类算法，它的目标是为确定一个分类超平面，从而将不同的数据分隔开。扩展：支持向量机学习方法包括构建由简至繁的模型：线性可分支持向量机、线性支持向量机及非线性支持向量机 ...
SVM(支持向量机)原理及数学推导全过程详解(附MATLAB程序) 答：深入解析支持向量机(SVM)：理论推导与MATLAB实践 SVM作为强大的机器学习工具，凭借其严格的数学基础和在小样本、非线性高维模式识别中的卓越表现脱颖而出。它通过引入松弛变量和巧妙的核函数，巧妙地处理非线性问题，即使在数据维度过高时也能保持高效性。SVM以统计学习理论为基石，旨在寻找模型复杂性和泛化...
支持向量机 答：(1)线性可分支持向量机、硬间隔 (2)线性支持向量机、软间隔 (3)非线性支持向量机、Kernel SVM 支持向量机模型存在三宝: (1)间隔:是指样本点到超平面的距离。 硬间隔 是指对给定的样本数据集中所以的样本都能正确分类。对于线性不可分的样本集,无法满足线性可分支持向量机的不等式约束,也就是不存在对所有样...
支持向量机算法原理 答：支持向量机算法原理介绍如下：支持向量机（Support Vector Machine，简称SVM）是一种广泛应用的机器学习算法，主要用于解决支持向量机（Support Vector Machine，简称SVM）是一种广泛应用的机器学习算法，主要用于解决二分类问题。其基本模型是定义在特征空间上的间隔最大的线性分类器，这个间隔最大使它有别于...
什么是支持向量机? 答：向量机的概念和相关应用如下。向量机的概念。向量机(Support Vector Machine)是一种监督模式识别和机器学习方法，采用最大分类间隔准则实现有限训练样本情况下推广能力的优化。通过核函数间接实现非线性分类或函数回归，支持向量机通常简写作SVM。向量机的相关应用。SVM在各领域的模式识别问题中有广泛应用，包括...
什么是支持向量? 答：揭开支持向量机的神秘面纱 支持向量机(SVM)，一种强大的二分类工具，其核心理念在于寻找特征空间中划分数据的最优决策边界。让我们从线性分类器开始理解它的基础。理解线性分类器的威力想象一下二维空间中的线性可分数据，我们试图找到一个超平面，如H1、H2或H3，来区分两个类别。直观上，如H3所示，超平面...
【机器学习】支持向量机 SVM(非常详细) 答：一、优雅的数学之美：SVM基础 SVM以其数学理论的魅力著称，它在处理分类问题时，首要目标是找到线性可分的超平面。这个超平面不仅能够将两类样本清晰划分，而且力求找到与最近样本点保持最大间隔的决策边界，这些最近的样本点称为支持向量。SVM的优化问题就是寻找这个最大间隔，以实现最优化的决策参数。二、...
支持向量机(SVM) 答：非线性支持向量机学习算法: 支持向量机的学习问题可以形式化为求解凸二次规划问题。这样的凸二次规划问题具有全局最优解,并且有许多最优化算法可以用于这一一问题的求解。但是当训练样本容量很大时,这些算法往往变得非常低效,以致无法使用。所以,如何高效地实现支持向量机学习就成为一一个重要的问题。目前人们已提出许...
什么是支持向量机(SVM)以及它的用途? 答：SVM - support vector machine, 俗称支持向量机，为一种supervised learning算法，属于classification的范畴。在数据挖掘的应用中，与unsupervised的Clustering相对应和区别。广泛应用于机器学习(Machine Learning), 计算机视觉(Computer Vision) 和数据挖掘(Data Mining)当中。假设要通过三八线把实心圈和空心圈分成...
svm支持向量机原理 答：svm支持向量机原理 SVM简介 支持向量机（support vector machines, SVM）是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；SVM还包括核技巧，这使它成为实质上的非线性分类器。SVM的的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的...
一方面，线性可分支持向量机只适用于线性可分的训练数据集，对于线性不可分的训练数据集则是无能为力的。
另一方面，即使训练数据集线性可分，线性可分支持向量机强依赖于离分类超平面最近的样本[3]，过拟合的风险很大。
这时候就需要有一定容错能力的分类模型，线性支持向量机，或者叫软间隔支持向量机，就可以做到这样的容错性。
这里我采用周志华老师西瓜书[2]的思路来整理这部分。
对于线性可分支持向量机，要求所有样本满足以下约束
而软间隔则允许某些样本不满足这样的约束。
在最大化间隔的同时，不满足约束的样本要尽量少。此时，优化目标可以写为
其中， 是一般化的损失函数， 被称作惩罚参数，调节间隔最大化和参数惩罚这二者关系。
我们先看惩罚参数 。当 值较大时对误分类惩罚较大，特别地，当C取无穷大时，所有样本都要满足式 约束，模型等价于线性可分支持向量机[3]；当 取有限值时，模型允许一些样本不满足约束。
接下来讨论损失函数 。当 使用不同的损失函数时的模型状态，周志华老师的西瓜书[2]有简单讨论。当 是合页损失函数时，模型就是线性支持向量机。李航老师《统计学习方法（第二版）》[1]的相关章节证明了线性支持向量机和基于合页损失函数的优化问题的等价性。合页损失函数如下
图1[2]
当 时，式 可重写为
引入松弛变量 ，将上式再重写为
优化问题一：
与线性可分支持向量机类似，线性支持向量机（式 ）的拉格朗日对偶函数如下
原问题（式 ）是凸优化问题，则优化问题 与原问题等价。
第一步， 求 对 的极小值。
得
将式 代入式 ，可得
第二步， 求 对 的极大值，即得对偶问题。
这里需要注意，式 等号右边表达式没有 ，直接求解对 的极大值即可。对偶问题如下
上式中，因为 不在最优化表达式中，可以利用等式约束消去，简化约束。再把求极大转换成求极小，得到对偶问题如下
优化问题二：
第三步， 求解分类超平面和分类模型。
对于已求解出优化问题二（式 ）的最优解 ，则类似于线性可分支持向量机[3]的推导过程。
原问题（式 ）是凸优化问题，则满足KKT条件的点是原问题和对偶问题的最优解（具体请参见[4]）
根据式 可得
观察式 、 和 ，先看式 ，当 时，有
再看式 ，当 时，有
此时再看式 ，当 时，必有 ，综上讨论，当 时，有
再将式 代入上式，并于式 联立，可得线性支持向量机的最优分类超平面参数为
这里需要注意，在李航老师《统计学习方法（第二版）》[1]相关章节中，和式 相同表达的式子是不严谨的，如果没看到这一段，这句话略过。
线性支持向量机的支持向量会复杂一些。如下图
首先， 定义 的样本点 为支持向量。
其次， 每个支持向量 到其对应的间隔边界的距离为 。推导过程如下。
点到超平面的距离公式为：
先看正类，正类的间隔边界超平面为： ，对应的点到间隔边界超平面的距离公式为： 。对于正例的支持向量，有 ，根据式 ，有 ，代入距离公式，即可到结论。
负类推导过程类似。
再次， 根据以上结论，分析支持向量。
根据上面式 和 ，消去 ，则有
第一种情况， 当 时，则 ，则此支持向量到对应间隔边界的距离 ，即此支持向量在间隔边界超平面上。
第二种情况， 当 且 时，此支持向量到对应间隔边界的距离 ，此支持向量分类正确，在间隔边界与分离超平面之间。
第三种情况， 当 且 时，此支持向量到对应间隔边界的距离 ，此支持向量在分离超平面上。
第四种情况， 当 且 时，此支持向量到对应间隔边界的距离 ，此支持向量分类错误。
这里需要注意，有没有 和 同时成立的点，这里没有找到确定或否定的证据。如果谁有这方面的资料，还烦请告知笔者，先行谢过，联系邮箱：hpfhepf@gmail.com。
[1]、《统计学习方法（第二版）》，李航著，清华大学出版社
[2]、《机器学习》，周志华著，清华大学出版社
[3]、 《支持向量机（一）——线性可分支持向量机导出》
[4]、 《凸优化（八）——Lagrange对偶问题》
B、相关目录
[a]、 支持向量机（一）——线性可分支持向量机导出
[b]、 支持向量机（二）——线性可分支持向量机求解
[c]、支持向量机（三）——线性支持向量机
[d]、 支持向量机（四）——核方法
[e]、 支持向量机（五）——SMO算法
