支持向量机（SVM）
基础的SVM
了解SVM之前，先让我们来思考一个问题，有下图所示的两类样本点，我们需要找到一条直线（一个平面）来把这两类样本点区分开，在图中可以看到有很多条直线都满足条件，但是哪条直线的分类效果更好呢？
直观上看，图中加粗的那条直线分类效果更好，该分类方法对于新样本的泛化能力也是最强的，下面让我们来看一下具体应该如何确定这条直线。
假定给一个特征空间上的训练数据集
其中：
此时当y i = + 1 时
是正例，此时当
时xi是负例，特征空间中的( x i , y i ) 就是样本点。
对于线性可分的问题我们可以得到一条直线，
该直线将特征空间划分为了两个部分，一部分是正类，一部分是负类，SVM中我们可以称这条直线为分离超平面。
此时设有一个通过间隔最大化得到的分离超平面：
得到了分离超平面我们又要如何去进行分类呢？此时我们对分离超平面添加一个决策函数，得到如下的形式：
此时该函数我们就可以称之为线性可分支持向量机。sign函数的图像表示如下：
这就是我们简单的线性SVM的思想，那么我们又如何通过间隔最大化来确定分离超平面呢？让我们再来看一下下面的间隔问题。
间隔问题
函数间隔
上图中是一个简单的圆与三角的分类问题，我们来讨论一下圆这个类，图中有框出的红、绿、蓝三种颜色的圆，他们都落在圆类的一侧，但是红球距离超平面的距离较远，如果我们把红圆预测为圆类，就比较确信我们的预测是正确的；同理，相对于蓝色的圆，我们就不是很确信；而对于绿色的圆，我们可以认为确信度在二者之间。
我们可以用如下的形式来表示函数间隔：
几何间隔
我们对超平面中的法向量w进行一定的约束得到：
对于几何间隔上面是用函数间隔来推出的过程，如果不是很理解，可以把它认定是点到直线的距离（二维空间内）或者点到平面的距离（三维空间内）。
再对几何间隔添加上我们之前提到的表示分类正确性的y一项得到几何间隔的具体表达式：
间隔最大化
在一种我们提到过间隔最大化得到的分类超平面经过sign函数后可以得到线性可分支持向量机，下面我们来说一下间隔最大化具体是怎么回事。
第二节中我们提到了确信度的问题，为了保证更高的确信度我们是不是应该尽量让每一个点到分类超平面的几何间隔都达到最大化，这样做的目的是对于新的数据点，我们不仅能将它分到正负类别中，同时离分类超平面很近的点我们也可以将它很好的分类，并且能够保证有很大的确信度，我们就可以说这个超平面对新数据有很好的预测能力。
我们将间隔最大化的问题转换为约束最优化问题我们希望最大化几何间隔γ 的同时又希望超平面对于每个测试样本点的几何间隔至少是γ 。
则有如下的形式(s.t.表示约束条件）：
根据上节末尾提到的几何间隔和函数间隔之间的关系我们可以把上述问题进一步转化：
此时我们便转化成了一个凸二次规划问题：
凸优化我们可以看做是一个凸函数去找最低点的问题（例如梯度下降法的过程）。
而二次规划是指目标函数为变量的二次函数和约束条件为变量的线性函数。
为了便于求解此类问题我们可以通过求解对偶问题得到原始问题的最优解，这样既可以简单的求解又可以引入后续对非线性分类问题的讨论（后面我们将会讨论对偶问题的求解）。
支持向量
如下图所示，距离超平面最近的几个点使得上述的等号成立，这几个点我们就称之为支持向量。
对偶问题求解
上面我们提到了间隔最大化的求解问题，本节让我们继续来讨论间隔最大化章节中转化为对偶问题的求解。
首先需要明确一下对偶问题的由来，对偶问题是一种应用拉格朗日对偶性，通过求解对偶问题得到原始问题的最优解。
原始问题：
求极小
求极大
引入松弛变量的SVM
上文中我们讲述的内容全都是在样本分类很均匀的情况下，而实际问题中这种状况经常是不存在的，那么有噪声点存在的时候应该怎么办呢？
此时的间隔最大化我们称之为软间隔最大化
此时对于每一个松弛变量，我们目标函数同时也要添加一个ξ i，则目标函数变为：
这里的C我们称之为乘法系数（C>0），C越小时对误分类的惩罚越小，越大时惩罚也就越大，当C取到无穷时，可以认为给了误分类项足够大的惩罚（导致ξ i 变得极小），此时的最大间隔也自然又回到了硬间隔最大化上。
此时我们可以根据上两式得到原始问题，求解依然可以使用上文中的对偶问题，结果不发生变化，这里不再赘述。
损失函数
SVM中常用的损失函数是(hinge)合页损失函数。
而完整的SVM的损失函数其实就是在合页函数的后面多加了一个L2正则项：
加入L2正则项的目的：使求解稳定快速，防止过拟合。
非线性SVM
上文中我们首先提到了线性可分支持向量机，后来又引入了松弛变量说了一下线性支持向量机，下面我们再来说一下非线性支持向量机。
核技巧
对于非线性支持向量机，我们需要用核技巧将线性支持向量机推广到非线性支持向量机，不仅是SVM其他的一些类似问题也可以用该方式来解答。
所谓核技巧其实就是使得在原空间内不可分的数据映射到更高维度的空间上，然后再使用线性的方法将他们分开的一种思想，用下图来表示一下：
可以看到图左的数据在二维空间内不能用一条直线将他们分开，我们将它映射到一个三维的空间内，此时就会存在一个平面（黄色的部分）将两类分离开来，对于这种思想我们就可以称之为核技巧。
核函数
说了核技巧我们就不得不说它的重要部分——核函数。
核函数的定义：
常用的核函数
多项式核函数
高斯核函数：
