支持向量机（5）总结

一、支持向量机 SVM

SVM 是一个非常优雅的算法，具有完善的数学理论，虽然如今工业界用到的不多，但还是决定花点时间去写篇文章整理一下。

本质：SVM 想要的就是找到各类样本点到超平面的距离最远，也就是找到最大间隔超平面。为了对数据中的噪声有一定的容忍能力。以几何的角度，在丰富的数据理论的基础上，简化了通常的分类和回归问题。

几何意义：找到一个超平面将特征空间的正负样本分开，最大分隔（对噪音有一定的容忍能力）；

间隔表示：划分超平面到属于不同标记的最近样本的距离之和；

二、优缺点

2.1 优点

• 有严格的数学理论支持，可解释性强，不依靠统计方法，从而简化了通常的分类和回归问题；
• 能找出对任务至关重要的关键样本（即：支持向量）；
• 采用核技巧之后，可以处理非线性分类/回归任务；
• 最终决策函数只由少数的支持向量所确定，计算的复杂性取决于支持向量的数目，而不是样本空间的维数，这在某种意义上避免了“维数灾难”。

2.2 缺点

• 训练时间长：当采用 SMO 算法时，由于每次都需要挑选一对参数，因此时间复杂度为\(O(N^2)\) ，其中 N 为训练样本的数量；
• 存储空间大：当采用核技巧时，如果需要存储核矩阵，则空间复杂度为\(O(N^2)\) ；
• 预测时间长：模型预测时，预测时间与支持向量的个数成正比。当支持向量的数量较大时，预测计算复杂度较高。

因此支持向量机目前只适合小批量样本的任务，无法适应百万甚至上亿样本的任务。

三、SVM Q&A

https://zhuanlan.zhihu.com/p/93715996

1、原理：

• 简单介绍SVM（详细原理）：从分类平面，到求两类间的最大间隔，到转化为求间隔分之一，等优化问题，然后就是优化问题的解决办法，首先是用拉格拉日乘子把约束优化转化为无约束优化，对各个变量求导令其为零，得到的式子带入拉格朗日式子从而转化为对偶问题， 最后再利用SMO（序列最小优化）来解决这个对偶问题。svm里面的超参数c有啥用：软间隔SVM去权衡优化目标和少量分错样本的目标。
• SVM的推导，解释原问题和对偶问题，SVM原问题和对偶问题的关系，KKT限制条件，KKT条件用哪些，完整描述；软间隔问题，解释支持向量、核函数（哪个地方引入、画图解释高维映射，高斯核可以升到多少维，如何选择核函数），引入拉格朗日的优化方法的原因，最大的特点，损失函数解释
  • KKT限制：主问题可行、对偶问题可行、主变量最优、互补松弛
• 对偶问题：因为原问题是凸二次规划问题，转换为对偶问题更加高效。为什么求解对偶问题更加高效？因为只用求解alpha系数，而alpha系数只有支持向量才非0，其他全部为0.alpha系数有多少个？样本点的个数

2、SVM与LR最大区别，LR和SVM对于outlier的敏感程度分析，逻辑回归与SVM的区别？

3、SVM如何解决多分类问题、可以做回归吗，怎么做？

4、机器学习有很多关于核函数的说法，核函数的定义和作用是什么？

https://www.zhihu.com/question/24627666

5、Linear SVM 和 LR 有什么异同？

SVM和LR相同点：

• SVM和LR都属于机器学习的监督学习中的判别式模型（判别式模型对\(p(y|x)\)进行建模或直接基于x预测y，生成模型：\(p(x|y)\)和\(p(y)\)进行建模,预测后验概率）。
• SVM和LR都是线性二分类模型，分类边界为一个超平面。
• 线性SVM和对数几率回归都可以基于表示定理和核技巧处理非线性可分问题。
• SVM的基本型和对数几率函数都属于参数模型。SVM的对偶性和核化对数几率回归都属于非参数模型。
• SVM和LR优化目标都表示成：经验风险+结构风险（正则项）的形式；均是0，1损失的替代函数。风险结构都是L2正则化。
• SVM和LR都是凸优化问题，都能收敛到全局最优解。
• SVM和对数几率函数的优化目标相似，性能相当。
• SVM多分类：多分类SVM；LR多分类：Softmax回归。

SVM和LR的区别：

算法	SVM	LR
思想	SVM 想要的就是找到各类样本点到超平面的距离最远，也就是找到最大间隔超平面。	逻辑回归是使用线性回归模型的预测值逼近分类任务真实标记的对数几率。
输出	非概率方法；	概率方法；需要对\(p(y|x)\)进行假设，具有概率意义。
经验损失函数	合页损失函数；有一段平的零区域、使得SVM的对偶性有稀疏性。	交叉熵损失函数
训练样本	支持向量（少数样本），SVM的参数和假设函数只和支持向量有关。	全样本
优化方法	次梯度下降和坐标梯度下降 【SMO算法】	梯度下降
多分类	多分类SVM	Softmax回归
敏感程度	SVM考虑分类边界线附近的样本（决定分类超平面的样本）。在支持向量外添加或减少任何样本点对分类决策面没有任何影响；	LR受所有数据点的影响。直接依赖数据分布，每个样本点都会影响决策面的结果。如果训练数据不同类别严重不平衡。

https://www.zhihu.com/question/26768865

6、支持向量机(SVM)是否适合大规模数据？【速度】

https://www.zhihu.com/question/19591450

7、SVM和逻辑斯特回归对同一样本A进行训练，如果某类中增加一些数据点，那么原来的决策边界分别会怎么变化？

https://www.zhihu.com/question/30123068

8、各种机器学习的应用场景分别是什么？例如，k近邻,贝叶斯，决策树，svm，逻辑斯蒂回归和最大熵模型。

https://www.zhihu.com/question/26726794

9、SVM与感知器的联系和优缺点比较

感知机用误分类样本点的几何距离之和来表示模型的损失函数，用梯度下降算法优化，直至没有误分类点。 \[ L(w, b)=-\sum_{x^{(i)} \in M} y^{(i)}\left(w^{T} x^{(i)}+b\right) \]

感知机与SVM区别

SVM可以视为对感知器的二阶改进：第一阶改进是加入了松弛系数获得hinge loss，从而具备了产生大间隔的潜质；第二阶改进是加入了权向量的L2正则化项，从而避免产生无意义的大函数间隔，而是产生大的几何间隔。

算法	感知机	SVM
思想	分离超平面基于误分类的损失函数 \(\min _{w, b} \frac{1}{n} \sum_{i=1}^n \max \left(0,-y_i\left(w^T x_i+b\right)\right.\)	\(\min _{w, b} \frac{1}{n} \sum_{i=1}^n \max \left(0,1-y_i\left(w^T x_i+b\right)\right)+\alpha\|w\|_2^2\)
超平面	因采用的初值不同而得到不同的超平面	让离划分超平面最近的样本到划分超平面距离尽可能远
关键样本	每步的分错样本	支持向量
非线性问题	无	核化