第6章 支持向量机
2024-05-09m.verywind.com
~
支持向量机 是一类按监督学习方式对数据进行 二元分类 的广义线性分类器，它的目的是寻找一个 超平面 来对样本进行分割，分割的原则是 间隔最大化 ，最终转化为一个 凸二次规划 问题来求解。
优点：
1.有严格的数学理论支持，可解释性强
2.能找出对任务至关重要的关键样本（即支持向量）
3.采用核技巧后，可以处理非线性分类/回归任务
4.最终决策函数只由少数的支持向量所确定，计算的复杂度取决于支持向量的数目，而不是样本空间的维数，在某种意义上避免了“维数灾难”
缺点：
1.训练时间长
2.当采用核技巧时，如果需要存储核矩阵，空间复杂度大
3.模型预测时，支持向量数目较大，预测计算复杂度高
本文重点对基于硬间隔的线性可分支持向量机、基于核函数的非线性支持向量机、基于软间隔的线性支持向量机这三类进行介绍。
给定训练样本集D={（ ， ）,（ ， ）,...,（ , ）}， {-1，+1}，分类学习基于训练集D在样本空间中找到一个划分超平面将不同类别的样本分开，但能将训练样本分开的划分超平面有很多，而我们要努力找到位于两类训练样本“ 正中间 ”的划分超平面（如图中的粗线），它对训练样本局部扰动的“容忍”性最好，即它产生的分类效果是 最鲁棒 的，对未见示例的 泛化能力最强 。
在样本空间中，划分超平面可通过线性方程来描述：
样本空间任意点x到超平面（w,b）的距离为
假设超平面（w,b）能将训练样本正确分类，则 约束 条件为：
使式子等号成立的训练样本点被称为“ 支持向量 ”（如图带圈圈的标记）。
两个异类支持向量到超平面的距离之和（ 间隔 ）为：
“ 最大间隔 ”的划分超平面条件：满足式（6.3）中对参数w和b，使得 最大，即：
可改写为（支持向量机 SVM的基本型 ）：
对 凸二次规划 问题使用 拉格朗日乘子法 可得到对偶问题，具体是对每条约束 添加拉格朗日乘子 0, 从而得出拉格朗日函数后，令对w和b的偏导为零，将得出的式子带入拉格朗日函数后可得到原式对应的 对偶问题 ，用 SMO算法 对对偶问题求解后，即可得到最大间隔划分超平面所对应的模型（上述过程需满足 KKT条件 ）。
在线性可分的假设下，希望得到的最大间隔划分超平面所对应的 模型 为：
由KKT条件，对任意训练样本（ ， )，总有 = 0 或 = 0 。
若 = 0，则该样本将不会在式（6.12）的求和中出现，也就不会对模型有任何影响；
若 > 0 ,则必有 = 0，所对应的样本点位于最大间隔边界上，是一个支持向量。
这显示出支持向量机的一个重要性质： 训练完成后，大部分的训练样本都不需保留，最终模型仅与支持向量有关。
在现实任务中，原始样本空间内也许并不存在一个能正确划分为两类样本的超平面。这时，可 将样本从原始空间映射到一个更高维的特征空间 ，使得样本 在这个特征空间内线性可分 。
那么，在特征空间中划分超平面所对应的 模型 表示为：
类似式（6.6），有原始 目标函数 ：
用拉格朗日乘子法得到其对偶问题为：
为避开计算困难，可以通过设想一个 核函数 ：
核函数的作用 ：核函数可以用 原始样本空间上的点内积 的方式，经过运算转化为高维空间点内积，而不必完全由高维空间上的点进行内积计算，这样达到了降低运算复杂度的作用。即从先升维度再算内积变成了 先算内积再升维度 。
在低纬空间（原始样本空间）中对于内积的运算则被定义为“ 核函数 ”， 在原始样本空间经过核函数计算的内积会等于高维空间的内积。
由此，原始目标函数经过改写求解出特征空间中划分超平面所对应的模型：
几种常用的核函数：
核函数的引入一方面减少了计算量，另一方面减少了存储数据的内存使用量。
在现实任务中往往难确定合适的核函数使得训练样本在特征空间中线性可分，即使恰好找到了也很难断定这个 貌似线性可分 的结果不是由于过拟合所造成的。为缓解这一问题是 允许支持向量机在一些样本上出错 。
软间隔 ：数据样本不是实际的线性可分，而是 近似线性可分 ，即 允许某些样本不满足约束 ：
由此，原始目标函数中增加了一个 损失函数 可写为：
三种常用的替代损失函数：
若采用hinge损失，则目标函数变成：
为度量这个间隔软到何种程度，引入“松弛变量” （即用以表示该样本不满足约束的程度），将上式改写得到“ 软间隔支持向量机 ”：
通过拉格朗日乘子法得到目标函数的拉格朗日函数并得到其对偶问题过程如下：
上述过程需满足 KKT条件 要求：
对于任意训练样本（ , ），总有 或 .
若 ，则样本不会对模型有任何影响；
若 , 则必有 , 即该样本是支持向量：
由式（6.39）可知,
若 ，则 ，进而有 ，即该样本恰在最大间隔边界上，
若 ，则 ，此时若 ，则该样本落在最大间隔内部，
若 ，则该样本被错误分类。
由此可看出： 软间隔支持向量机的最终模型仅与支持向量有关。
把目标函数中的0/1损失函数换成别的替代损失函数可得到其他学习模型，这些模型具有一个 共性 ：优化目标中的第一项用来描述划分超平面的间隔大小（ 结构风险 ），另一项用来表述训练集上的误差（ 经验风险 ），所以加了损失函数的线性支持向量机优化目标的 一般形式 为：
正则化 ：对不希望得到的结果施以惩罚，从而使得优化过程趋向于希望目标。
上式是“正则化”问题， 称为正则化项，C称为正则化常数， 范数是常用的正则化项。
SVR与SVM的区别：
SVM是要使到超平面 最近 的样本点的“距离” 最大 ；
SVR则是要使到超平面 最远 的样本点的“距离” 最小 。
传统回归模型与支持向量回归计算损失的区别 ：
传统回归模型直接基于模型输出 与真实输出 之间的差别来计算损失，当且仅当 与 完全相同时，损失才为零。
支持向量回归假设 能容忍 与 之间最多有 的偏差 ，仅当 与 之间的差别绝对值 大于 时 才计算损失，这相当于以 为中心，构建了一个 宽度为 的间隔带 ，若训练样本落入此间隔带，则以为是被预测正确的。
于是， SVR问题的目标函数 为：
加入 松弛变量 和 ，改写为：
再用拉格朗日乘子法得到 SVR的对偶问题 ：
求解后得到 SVR模型 ：
能使式（6.53）中的 的样本即为 SVR的支持向量 ，它们 必落在间隔带之外 。
上述过程需满足 KKT条件 ：
若考虑 特征映射形 式， SVR模型 为：
核函数定理 ：令 为输入空间， 是定义在 上的 对称函数 ，则 是核函数当且仅当对于任意数据D={ }，“ 核矩阵 ”总是 半正定 的：
表示定理 ：令H为核函数 对应的再生核希尔伯特空间， 表示H空间中关于h的范数，对于任意单调递增函数 和任意非负损失函数 ，优化问题
表示定理对损失函数 没有限制 ，对正则化项 仅要求 单调递增 ，即对于一般的损失函数和正则化项，优化问题的最优解 都可以表示为核函数 的线性组合。
引入核函数能将线性学习器扩展为非线性学习器。
这里我们使用sklearn的 乳腺癌数据 对以下5种模型的准确度进行预测，重点放在SVC上。
SVC主要调节的参数有： C （正则化参数）、 kernel （核函数）、 degree （多项式维度）、 gamma （核函数参数）、 coef0 （核函数的常数项）。
第一次我用SVC的默认参数，此时的核函数是 高斯核函数（kernel=‘rbf’） ，结果测试集的准确度为62.9%，太低了！说明存在严重的 过拟合 情况。
第二次我选择 改变核函数
用维度为2的 多项式核函数（kernel=‘poly’degree=2） 试试，测试集准确度变为95.1%，感觉比高斯核函数好多了！
线性核函数（kernel=‘linear’） 也来试试，多项式核函数当维度为1时 （kernel=‘poly’，degree=1） 退化为线性核。咦，测试集的准确度提升到了95.8%，但是测试集和训练集的准确度太过于接近，可能会有 欠拟合 的情况。
sigmoid核函数（kernel=‘sigmoid’） 也来试试，真的是太太太低了吧，算了果断抛弃。
第三次，对于常用的 高斯核函数 ，就这么被PK下去了感觉不太好，我决定试试 改变正则化参数 C 看看能不能挽救它，默认下的是C=1.0. 乳腺癌数据集的特征具有完全不同的数量级，这对SVC模型影响比较大，所以先进行 归一化处理 ，对每 个特征进行缩放 ，使其缩放到 0 和 1 之间 。归一化处理后，默认参数下的SVC模型测试集的准确率已经高达96.5%了。
改变C值 试试，当C值为1000时，测试集准确度又提高了，达到了97.4%，说明 增大C值可以优化模型。
第一次我先用了决策树里面默认的参数，其中 max_depth=None ，即树的深度是无穷的，此时出现了训练集的准确度为100%，说明出现了 过拟合 情况。
对于上述过拟合情况我采取的是 限制树的深度 。限制树的深度可以 减少过拟合 。这会 降低训练集的精度，但可以提高测试集的精度。
从 max_depth=3 开始，发现训练集的准确率下降了，但是测试集的准确度从93%提高到了94.4%，明显泛化性能提高了。
再用 max_depth=4 试试，测试集准确度为95.1%，泛化性能又提高了。可！
优点：
1.有严格的数学理论支持，可解释性强
2.能找出对任务至关重要的关键样本（即支持向量）
3.采用核技巧后，可以处理非线性分类/回归任务
4.最终决策函数只由少数的支持向量所确定，计算的复杂度取决于支持向量的数目，而不是样本空间的维数，在某种意义上避免了“维数灾难”
缺点：
1.训练时间长
2.当采用核技巧时，如果需要存储核矩阵，空间复杂度大
3.模型预测时，支持向量数目较大，预测计算复杂度高
本文重点对基于硬间隔的线性可分支持向量机、基于核函数的非线性支持向量机、基于软间隔的线性支持向量机这三类进行介绍。
给定训练样本集D={（ ， ）,（ ， ）,...,（ , ）}， {-1，+1}，分类学习基于训练集D在样本空间中找到一个划分超平面将不同类别的样本分开，但能将训练样本分开的划分超平面有很多，而我们要努力找到位于两类训练样本“ 正中间 ”的划分超平面（如图中的粗线），它对训练样本局部扰动的“容忍”性最好，即它产生的分类效果是 最鲁棒 的，对未见示例的 泛化能力最强 。
在样本空间中，划分超平面可通过线性方程来描述：
样本空间任意点x到超平面（w,b）的距离为
假设超平面（w,b）能将训练样本正确分类，则 约束 条件为：
使式子等号成立的训练样本点被称为“ 支持向量 ”（如图带圈圈的标记）。
两个异类支持向量到超平面的距离之和（ 间隔 ）为：
“ 最大间隔 ”的划分超平面条件：满足式（6.3）中对参数w和b，使得 最大，即：
可改写为（支持向量机 SVM的基本型 ）：
对 凸二次规划 问题使用 拉格朗日乘子法 可得到对偶问题，具体是对每条约束 添加拉格朗日乘子 0, 从而得出拉格朗日函数后，令对w和b的偏导为零，将得出的式子带入拉格朗日函数后可得到原式对应的 对偶问题 ，用 SMO算法 对对偶问题求解后，即可得到最大间隔划分超平面所对应的模型（上述过程需满足 KKT条件 ）。
在线性可分的假设下，希望得到的最大间隔划分超平面所对应的 模型 为：
由KKT条件，对任意训练样本（ ， )，总有 = 0 或 = 0 。
若 = 0，则该样本将不会在式（6.12）的求和中出现，也就不会对模型有任何影响；
若 > 0 ,则必有 = 0，所对应的样本点位于最大间隔边界上，是一个支持向量。
这显示出支持向量机的一个重要性质： 训练完成后，大部分的训练样本都不需保留，最终模型仅与支持向量有关。
在现实任务中，原始样本空间内也许并不存在一个能正确划分为两类样本的超平面。这时，可 将样本从原始空间映射到一个更高维的特征空间 ，使得样本 在这个特征空间内线性可分 。
那么，在特征空间中划分超平面所对应的 模型 表示为：
类似式（6.6），有原始 目标函数 ：
用拉格朗日乘子法得到其对偶问题为：
为避开计算困难，可以通过设想一个 核函数 ：
核函数的作用 ：核函数可以用 原始样本空间上的点内积 的方式，经过运算转化为高维空间点内积，而不必完全由高维空间上的点进行内积计算，这样达到了降低运算复杂度的作用。即从先升维度再算内积变成了 先算内积再升维度 。
在低纬空间（原始样本空间）中对于内积的运算则被定义为“ 核函数 ”， 在原始样本空间经过核函数计算的内积会等于高维空间的内积。
由此，原始目标函数经过改写求解出特征空间中划分超平面所对应的模型：
几种常用的核函数：
核函数的引入一方面减少了计算量，另一方面减少了存储数据的内存使用量。
在现实任务中往往难确定合适的核函数使得训练样本在特征空间中线性可分，即使恰好找到了也很难断定这个 貌似线性可分 的结果不是由于过拟合所造成的。为缓解这一问题是 允许支持向量机在一些样本上出错 。
软间隔 ：数据样本不是实际的线性可分，而是 近似线性可分 ，即 允许某些样本不满足约束 ：
由此，原始目标函数中增加了一个 损失函数 可写为：
三种常用的替代损失函数：
若采用hinge损失，则目标函数变成：
为度量这个间隔软到何种程度，引入“松弛变量” （即用以表示该样本不满足约束的程度），将上式改写得到“ 软间隔支持向量机 ”：
通过拉格朗日乘子法得到目标函数的拉格朗日函数并得到其对偶问题过程如下：
上述过程需满足 KKT条件 要求：
对于任意训练样本（ , ），总有 或 .
若 ，则样本不会对模型有任何影响；
若 , 则必有 , 即该样本是支持向量：
由式（6.39）可知,
若 ，则 ，进而有 ，即该样本恰在最大间隔边界上，
若 ，则 ，此时若 ，则该样本落在最大间隔内部，
若 ，则该样本被错误分类。
由此可看出： 软间隔支持向量机的最终模型仅与支持向量有关。
把目标函数中的0/1损失函数换成别的替代损失函数可得到其他学习模型，这些模型具有一个 共性 ：优化目标中的第一项用来描述划分超平面的间隔大小（ 结构风险 ），另一项用来表述训练集上的误差（ 经验风险 ），所以加了损失函数的线性支持向量机优化目标的 一般形式 为：
正则化 ：对不希望得到的结果施以惩罚，从而使得优化过程趋向于希望目标。
上式是“正则化”问题， 称为正则化项，C称为正则化常数， 范数是常用的正则化项。
SVR与SVM的区别：
SVM是要使到超平面 最近 的样本点的“距离” 最大 ；
SVR则是要使到超平面 最远 的样本点的“距离” 最小 。
传统回归模型与支持向量回归计算损失的区别 ：
传统回归模型直接基于模型输出 与真实输出 之间的差别来计算损失，当且仅当 与 完全相同时，损失才为零。
支持向量回归假设 能容忍 与 之间最多有 的偏差 ，仅当 与 之间的差别绝对值 大于 时 才计算损失，这相当于以 为中心，构建了一个 宽度为 的间隔带 ，若训练样本落入此间隔带，则以为是被预测正确的。
于是， SVR问题的目标函数 为：
加入 松弛变量 和 ，改写为：
再用拉格朗日乘子法得到 SVR的对偶问题 ：
求解后得到 SVR模型 ：
能使式（6.53）中的 的样本即为 SVR的支持向量 ，它们 必落在间隔带之外 。
上述过程需满足 KKT条件 ：
若考虑 特征映射形 式， SVR模型 为：
核函数定理 ：令 为输入空间， 是定义在 上的 对称函数 ，则 是核函数当且仅当对于任意数据D={ }，“ 核矩阵 ”总是 半正定 的：
表示定理 ：令H为核函数 对应的再生核希尔伯特空间， 表示H空间中关于h的范数，对于任意单调递增函数 和任意非负损失函数 ，优化问题
表示定理对损失函数 没有限制 ，对正则化项 仅要求 单调递增 ，即对于一般的损失函数和正则化项，优化问题的最优解 都可以表示为核函数 的线性组合。
引入核函数能将线性学习器扩展为非线性学习器。
这里我们使用sklearn的 乳腺癌数据 对以下5种模型的准确度进行预测，重点放在SVC上。
SVC主要调节的参数有： C （正则化参数）、 kernel （核函数）、 degree （多项式维度）、 gamma （核函数参数）、 coef0 （核函数的常数项）。
第一次我用SVC的默认参数，此时的核函数是 高斯核函数（kernel=‘rbf’） ，结果测试集的准确度为62.9%，太低了！说明存在严重的 过拟合 情况。
第二次我选择 改变核函数
用维度为2的 多项式核函数（kernel=‘poly’degree=2） 试试，测试集准确度变为95.1%，感觉比高斯核函数好多了！
线性核函数（kernel=‘linear’） 也来试试，多项式核函数当维度为1时 （kernel=‘poly’，degree=1） 退化为线性核。咦，测试集的准确度提升到了95.8%，但是测试集和训练集的准确度太过于接近，可能会有 欠拟合 的情况。
sigmoid核函数（kernel=‘sigmoid’） 也来试试，真的是太太太低了吧，算了果断抛弃。
第三次，对于常用的 高斯核函数 ，就这么被PK下去了感觉不太好，我决定试试 改变正则化参数 C 看看能不能挽救它，默认下的是C=1.0. 乳腺癌数据集的特征具有完全不同的数量级，这对SVC模型影响比较大，所以先进行 归一化处理 ，对每 个特征进行缩放 ，使其缩放到 0 和 1 之间 。归一化处理后，默认参数下的SVC模型测试集的准确率已经高达96.5%了。
改变C值 试试，当C值为1000时，测试集准确度又提高了，达到了97.4%，说明 增大C值可以优化模型。
第一次我先用了决策树里面默认的参数，其中 max_depth=None ，即树的深度是无穷的，此时出现了训练集的准确度为100%，说明出现了 过拟合 情况。
对于上述过拟合情况我采取的是 限制树的深度 。限制树的深度可以 减少过拟合 。这会 降低训练集的精度，但可以提高测试集的精度。
从 max_depth=3 开始，发现训练集的准确率下降了，但是测试集的准确度从93%提高到了94.4%，明显泛化性能提高了。
再用 max_depth=4 试试，测试集准确度为95.1%，泛化性能又提高了。可！
