DataWhale—PumpkinBook（TASK07支持向量机）

课程开源地址及相关视频链接：（当然这里也希望大家支持一下正版西瓜书和南瓜书图书，支持文睿、秦州等等致力于开源生态建设的大佬✿✿ヽ(°▽°)ノ✿）

Datawhale-学用 AI,从此开始

【吃瓜教程】《机器学习公式详解》（南瓜书）与西瓜书公式推导_哔哩哔哩_bilibili

支持向量机：https://www.bilibili.com/video/BV1Mh411e7VU?p=9

软间隔与支持向量回归：https://www.bilibili.com/video/BV1Mh411e7VU?p=10

正文部分

支持向量机主要解决二分类问题，通过学习高维空间的线性分割边界解决原始数据线性不可分问题。
基础的模型输入是原始数据，输出是高维分割超平面，预测时通过某条数据在超平面的哪一侧表达类别归属。

SVM同时也能应用于多分类、回归及单分类异常检测等问题。 

直觉上，线性可分二分类，最好的分类边界应该是使靠的最近的不同类别的数据分开的越远越好。接近边界的数据能被良好地分开，远离边界的数据，分类自然更没问题。
SVM就是尝试寻找这个分割边界，也就是最大化上图中的红色边界和虚线之间的距离，由于是线性关系，系数可以缩放，为方面处理，令m=1，可得最大化的目标函数是1 / ||w||，等价于：

 注意：y ϵ {+1, -1}，m=1，不等式约束表达数据都在上图边界构成的管道外，保证w是最优化边界的参数。

考虑不等式约束，根据拉格朗日乘子法，目标函数变为：

拉格朗日对偶问题：

结合KKT条件，最终的目标函数为：

注意最终目标函数的形式：

• 目标函数的变量是拉格朗日乘子α，且只和数据集(x, y)有关，可以通过SMO(sequential minimal optimization)最优化方法方便求解α。

• 根据KKT约束：α_i * g_i(w) = 0，g_i(w) ≤ 0，可知当g_i = 0，α_i > 0，即在上图最近虚线边界上时；当g_i < 0，α_i = 0。

• α_i > 0 对应的样本点，称为支持向量，少量的数据参与训练，能有效降低学习的复杂度。

• 目标函数样本间仅以<内积>形式出现，这是转换为对偶问题后，比较吸引人的形式。

• 内积形式可以方便地将x打包映射到Φ(x)，而不影响之前的整个推导，边界关于Φ(x)是线性的；Φ(x)一般是个向量，映射后的空间以向量为基本元素的希尔伯特空间，暂且称之为“内积空间”。

• 内积空间中可以通过核函数技巧，使映射后空间变得更高维复杂，但计算复杂度和原始低维一致。

• 映射x->Φ(x)的动机来自于低维线性不可分的数据，高维可能可以。

常见的核函数有四种：

以上核函数的计算复杂度都在原始x空间内。RBF即高斯核函数，示意图如下：

不同核函数，分类效果，大致如下：

给定一个样本，预测的时候，SVC如何确定属于哪一个分类呢？

其实就是将样本数据代入映射后的高维空间，按照位置，线性判别即可。

SVC只能输出样本属于哪一个分类，而不能像其他分类器一样输出概率。

想到只有支持向量参与学习，SVM的速度应该很快，这是一个小误区，因为确定支持向量本身也是学习的一部分。

以主流的libsvm的复杂度为例：
 

复杂度大概为o(n^2) ~ o(n^3)，随着样本的增加，SVM的速度会变得很慢。

基础的SVM算法通过拉格朗日相关最优化方法，将欧拉空间线性不可分问题映射到希尔伯特空间线性可分，并通过核函数技巧及支持向量选择，在高维空间有效解决二分类问题。

参考文献

scikit-learn: machine learning in Python — scikit-learn 1.5.2 documentation

scikit-learn (sklearn) 官方文档中文版 - sklearn