- SVM与感知机的区别？
- 如何理解SVM的优化目标：间隔最大化？
- 松弛变量的作用？
- 为什么核函数必须是正定核？
支持向量机是对感知机算法的改进。原始的感知机算法对于分类超平面没有更多的约束，只要能够正确分类正负实例即可，因此感知机算法求出的分类决策面是不唯一的。而SVM加入了最大化间隔这一条件，使超平面被唯一地确定下来，也使其具有很好的泛化性能。
然而，原始的SVM算法（硬间隔SVM）只能求解线性可分的情况，当数据集线性不可分时，原始算法就失效了。线性不可分又分为两种情况：数据集大体上是线性可分的，但有一些噪点；数据集中输入和输出明显不满足线性关系。对于第一种情况，改进的模型是软间隔SVM，它通过一个松弛变量$\xi$，允许算法在求解最优超平面时，忽略掉一些为正确分类的点。对于第二种情况，改进的模型是核SVM，它将输入数据通过非线性变换映射到特征空间，从而将输入空间的非线性分类问题转化为了特征空间的线性分类问题。可以这么做的原因，得益于SVM的对偶算法，原始问题的求解等价于对偶问题的求解，而对偶问题中只包含输入向量之间的内积，因此我们可以使用核技巧，将特征空间的内积转化为输入空间的内积。
SVM具有极其对称和美观的形式，被认为是完美的机器学习算法。
首先，我们来考虑数据集线性可分的情况。我们从感知机算法说起 $$ f(x)=sign(wx+b) $$ 上式是感知机模型的定义，它对模型参数只有一个限制：能够正确分类正负样本点，因此，如下图所示的多条直线，都可能是感知机算法的结果。但是，比起最下面的一条直线，我们更愿意将中间的直线作为分类决策边界，因为前者只是“将将分类对了两类样本点”，但正负类的界限并不是那么明显，我们希望数据点的“间隔”较大。
如何用数学的语言表达上述想法？这里我们引入了函数间隔和几何间隔的概念。
- 函数间隔
函数间隔综合考虑了分类正确性和到超平面的距离：函数间隔>0时，表明样本点被正确分类，反之亦然；$\parallel wx_i+b \parallel$正比于样本点$(x_i,y_i)$到超平面的距离。
- 几何间隔
函数间隔可以表示分类预测的正确性及确信度，但只用函数间隔还无法唯一地确定w和b。因为只要成比例地改变w和b，分离超平面没有改变，函数间隔却变为原来的2倍。因此我们引入几何间隔 $$ \gamma_i = \frac{wx_i+b}{\parallel w\parallel}\ \gamma=\min_{i=1,2,...,N}{\gamma_i} $$
有了度量的准则之后，我们可以定义最优化问题 $$ \max_{w,b}{\gamma}\ s.t.\quad y_i(\frac{wx_i+b}{\parallel w\parallel})\geq \gamma,\quad i=1,2,...,N $$ 这个最大化问题等价于以下最小化问题 $$ \min_{w,b}{\frac{1}{2}\parallel w\parallel^2}\ s.t.\quad y_i(wx_i+b)-1\geq 0,\quad i=1,2,...,N $$ 可以证明，求解以上问题得到的最大间隔分离超平面是存在且唯一的。
正如我们在文章一开始提到的，SVM的对偶形式给求解和扩展SVM算法带来了便利。本小节介绍SVM的对偶形式 $$ \min_\alpha{\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N{\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N{\alpha_i}}}\ s.t.\quad \sum_{i=1}^N{\alpha_iy_i}=0\ \alpha_i\geq 0,\quad i=1,2,...,N $$ 设对偶最优化问题的解为$\alpha^=(\alpha_1^,\alpha_2^,...,\alpha_l^)$，存在下标$j$，使得$\alpha_j>0$，我们可以求得原始最优化问题的解 $$ w^*=\sum_{i=1}^N{\alpha_i^y_ix_i}\ b^=y_j-\sum_{i=1}^N{\alpha_i^*y_i(x_i\cdot x_j)} $$ KKT条件为 $$ \alpha_i(y_i(wx_i+b)-1)=0,\quad i=1,2,...,N $$ 由于$\alpha_i\geq0$和$y_i(wx_i+b)-1\geq0$这两个限制条件的存在，可以得出，对于任意的i，$\alpha_i=0$和$y_i(wx_i+b)-1=0$至少有一个成立。对于远离分离间隔平面$y_i(wx_i+b)=1$的点，有$y_i(wx_i+b)-1\gt0$，因此$\alpha_i=0$，因此对参数的求解是没有作用的。对于$\alpha_i\gt0$的点，必有$y_i(wx_i+b)-1=0$，也即它们落在分离间隔平面上，而且对参数的求解是有影响的，这些点被称为支持向量。
然而，硬间隔SVM不能处理所有的情况。
上图展示了第一种情况，有一个正类的噪点跑到了负类里，导致数据无法被超平面分开。
这张图展示了第二种情况，虽然我们可以通过调整分界线使数据勉强分开，但正负类的间隔缩小了很多，而且，我们有足够的把握相信新加入的正类样本点只是一个离群点，忽略这个点可以获得更好的分界线。
以上两种问题都是由于SVM对支持向量过于敏感造成的，为了解决这个问题，我们引入松弛变量$\xi$，得到软间隔SVM $$ \min_{w,b}{\frac{1}{2}\parallel w\parallel^2+C\sum_{i=1}^N{\xi_i}}\ s.t.\quad y_i(wx_i+b)\geq 1-\xi_i,\quad i=1,2,...,N\ \xi_i\geq0,\quad i=1,2,...,N $$ 同样可以得到对偶问题 $$ \min_\alpha{\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N{\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N{\alpha_i}}}\ s.t.\quad \sum_{i=1}^N{\alpha_iy_i}=0\ 0\leq\alpha_i\leq C,\quad i=1,2,...,N $$ KKT条件为 $$ \alpha_i(y_i(wx_i+b)-1)=0,\quad i=1,2,...,N\ \mu_i\xi_i=0 $$ 类似地，$\alpha_i>0$的点被称为支持向量。由于第二个等式的存在，现在情况发生了一些改变：若$\alpha_i<C$，$\mu_i=C-\alpha_i>0$，因此必有$\xi_i=0$，$x_i$落在间隔分界上。若$\alpha_i=C$，$\mu_i=C-\alpha_i=0$，那么必有$\xi_i>0$，当$\xi_i<1$时，落在间隔分解与分离超平面之间；当$\xi_i=1$时，正好落在分离超平面上；当$\xi_i>1$时，落在分离超平面另一侧，没有被正确分类。
软间隔SVM解决了一部分问题，但无法解决这种完全线性不可分的数据，因此我们想到对原始输入做一个非线性变换，将其映射到高维空间中。原始空间中的非线性问题在高维空间下是线性的，那么就能用之前得到的线性SVM来求解了。
由于对偶问题中只涉及两个数据点之间的内积$x_i\cdot x_j$，因此我们甚至不需要显式地进行特征映射，而是借助于核函数 $$ W(\alpha)=\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N{\alpha_i\alpha_jy_iy_jK(x_i,x_j)}-\sum_{i=1}^N{\alpha_i}\ K(x_i,x_j)=\phi(x_i)\cdot \phi(x_j) $$ 这里的核函数$K(x_i,x_j)$是半正定的，被称为正定核（惊天骗局！正定核其实是半正定的）。原因是我们必须保证特征空间是完备的内积空间（Hilbert空间），上述转换才有意义。有如下定理（书P136-P138）保证
Mercer定理. 对称核函数$K(x,z)$具有Hilbert空间中内积形式的充要条件是：
$\int{K(x,z)g(x)g(z)dxdz\geq0}$ 对任何平方可积函数$g$成立，$K(x,z)$称为Mercer核。
SMO是解对偶问题的一种启发式方法。如果所有变量的解都能满足KKT条件，那么这个最优化问题的解就得到了。因此，我们可以每次取m个最不满足KKT条件的点，更新相应的$\alpha$以使其满足KKT条件（类似于梯度下降）。但是，由于约束条件$\sum_{i=1}^{N}{\alpha_iy_i}=0$的存在，如果我们每次只取一个点进行更新，无法保证满足约束条件，所以我们取m=2，即两个样本点$x_1$和$x_2$。其中，$x_1$是严重违反KKT条件的点，而$x_2$是为了满足约束条件多加的样本点。
（推导过程略）
根据上面的分析，我们其实很容易构建出选择$x_1$和$x_2$的启发式方法：
-
$x_1$ 选取违反KKT条件最严重的样本点 -
$x_2$ 选取能使$\alpha_2$有足够大的变化的样本点。在寻找$x_2$时，往往先从间隔边界上的支持向量点开始，若找不到则便利训练数据集，若还是找不到，则要回退到上一步，重新选取$x_1$