支持向量机（SVM）[toc]1.什么是支持向量机？支持向量机在高纬度或无限维空间中构建超平面或超平面集，可用于分类、回归或其他任务。直观上，分类边界离最近的训练数据点越远越好，因为这样可以减少分类器的泛化误差。https://zh.wikipedia.org/zh-cn/%E6%94%AF%E6%8C%81%E5%90%91%E9...涉及到几个概念：1.超平面；2、泛化错误；3、支持向量什么是超平面？假设我们正在使用支持向量机来处理两个分类问题。让我们想象一下，如果笛卡尔坐标系中有两个不同的类别：黑点和紫点。现在我们需要将它们分开，你会怎么做？你可能会说：画一条线，很快就结束不简单吗？看来你明白什么是超平面了。好吧，我们来看下图：那么蓝色呢？还是黄色？这就是我们要提的第二个概念——泛化误差。什么是泛化误差？如果你仔细看图片，它可能是绝对的蓝色。为什么？因为箭头所指的点是最短的距离！听起来很有道理。但是，我们通常会抽取一些样品进行测试。由于训练集或噪声因素的限制，训练集外的样本可能比图中的训练样本更接近两类的分离，这会导致许多划分超平面出现错误，黄色超平面受到的影响最小。这就是我们要考虑的——泛化误差！直观的理解是：当加入新的样本点时，超平面仍然可以很好的划分数据点。什么是支持向量？我们在超平面上加减一个常数C，这样我们的超平面就会移动，但是移动多少呢？当我们移动去触摸样本数据点的时候，而这些样本数据点决定了我们的分离距离（卖个把戏），它们叫做支持向量，说了那么多，这个超平面方程怎么求呢？（可能会涉及到很多数学知识，如果想直接看懂代码，这部分可以跳过）2.数学理论机器学习算法和数学知识是密不可分的。我尽量简化数学知识。当然，如果你只是想要代码，但是有必要知道如何调整SVM的参数。支持向量机的有效性取决于核函数、核参数和软区间参数的选择C??2.1数学预备知识假定两条直线之间的距离$$存在于两条平行直线中：A_0x+B_0y+b_0=0;A_0x+B_0y+b_1=0；则它们之间的距离为：\\d=\frac{|b_1-b_0|}{\sqrt{A_0^2+B_0^2}}$$二次规划问题如下：$$min\;\;c^Tx+\frac{1}{2}x^TQx\\subject\;to:Dx\geqslantd\\Ax=b$$若Q≥0，则为凸优化问题拉格朗日乘数远拉格朗日乘数法为一种将约束优化问题转化为无约束优化问题的方法。我们现在需要解决如下优化（最小化）问题：$$minf(x)\;\;s.t.\;g(x)=0$$就是求解f(x)在约束条件g(x)=0。那么我们可以引入拉格朗日函数：$$L(x,\alpha)=f(x)+\alphag(x)\;\;\;\alpha记为拉格朗日乘数$$image理解拉格朗日乘数法-知乎（zhihu.com）KKT约束Karush-Kuhn-Tucker（KKT）条件-知乎（zhihu.com）2.2线性可分支持向量机什么是线性可分离？先不说概念，直观的理解就是：我们可以直接通过直线或者平面来划分数据集，那么这就叫线性可分支持向量机！例如：我们有一个训练数据集：$T=[(x_1,y_1),(x_2,y_2)]$现在我们要找一条直线来划分它们，我想你马上就会想到$ax+by+c=0$这个等式。很好，那我们泛化到n个点的情况。给定训练数据集：$$T=[(x_1,y_1)...(x_n,y_n)]$$这种情况下怎么办？同理，我们假设超平面方程为：$$w^Tx+b=0\\其中w和b为模型参数。注意此时w不是一个数字而是一个向量！$$那么我们就有方程了，然后问题转化为求解$w,b$参数的具体取值问题。再次回顾我们的2元素点到线距离公式：$d=\frac{|ax+by+c|}{\sqrt{a^2+b^2}}$与我们推到multi的原因相同-dimensionalsituation:$$d=\frac{|w^Tx+b|}{||w||}$$不要忘记我们的出发点是什么：二元分类！也就是说，我们要分我们的分。这样一来，超平面的一侧是a类，另一侧是b类吗？还记得我们之前提到的间隔距离吗？我们设置：$$\begin{cases}w^Tx_i+b\geqslant1,y_i=1\\w^Tx_i+b\leqslant1,y_i=-1\end{cases}\\\text{在这种情况下，两个super平面距离为}r=\frac{2}{||w||}$$超平面距离可以类比为两条平行直线之间的距离。在这种情况下，我们找到最大的“间隔”，即计算：$$max\frac{2}{||w||}简化计算记为min\frac{1}{2}||w||^2\\subject\;to\;y_i(w^Tx_i+b)\geqslant1,\;i=1,2....n$$用拉格朗日乘数法求解：$$公式1\;\;L(w,b,\alpha)=\frac{1}{2}||w||^2+\sum_{i=1}^{m}\alpha_i(1-y_i(w^Tx_i+b))\\||w||^2=w^Tw$$这时我们分别对w和b求偏导数，令其为0得到：$$公式2\;\;w=\sum_{i=1}^{m}\alpha_iy_ix_i\;\;\sum_{i=1}^{m}\alpha_iy_i=0$$将公式2代入公式1得到：$$公式3\;\;max\sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_iy_ix^T_i\alpha_jy_jx_j$$计算步骤如下：以上过程需要满足KKT条件：$$\begin{cases}\alpha_i\ge0\\y_if(x_i)-1\ge0\\\alpha_i(y_if(x_i)-1)=0\end{cases}$$后续更新内核函数，python代码，算法流程，以及如何解决，我忙着准备考试和没有时间更新它。在我忙完这部分之后，我将完成所有的机器学习算法。3.Python代码先上传到sklearn代码，后续手册源码https://scikit-learn.org/stable/modules/svm.html4.评估优势可以解决高维问题，即大特征空间；解决小样本下的机器学习问题；线性特征的相互作用；没有局部最小问题；（相对于神经网络等算法）不需要依赖整个数据；泛化能力比较强；缺点是当观测样本较多时，效率不是很高；无非线性问题的通用解，有时很难找到合适的核函数；核函数的高维映射不是很好解释，尤其是径向基函数；常规SVM只支持二分类；它对丢失的数据很敏感；5.算法过程7.参考https://zhuanlan.zhihu.com/p/440297403李航《统计学学习方法(第二版)》《西瓜书》
