支持向量机（Support Vector Machine,SVM）是众多监督学习方法中十分出色的一种，SVM涵盖了各个方面的知识。第一节为SVM模型推导的基础知识，第二~第四节则侧重对核函数（Kernel Function）的理解。

1、在空间上线性可分的两类点，分别向SVM分类的超平面上做投影，这些点在超平面上的投影仍然是线性可分的吗？

线性可分的两类点，即通过一个超平面可以将两类点完全分开。

将这两类点向绿色平面上做投影，在分类直线上得到的两类投影是否仍然线性可分？

显然，在分类超平面的投影在超平面上相互间隔，并不是线性可分的。考虑一个更简单的反例，设想二维空间中只有两个样本点，每个点各属于一类的分类任务，此时SVM的分类超平面（直线）就是两个样本点连线的中垂线，两个点在分类面（直线）上的投影会落到这条直线上的同一个点，自然不是线性可分的。

但实际上，对于任意线性可分的两组点，它们在SVM分类的超平面上的投影都是线性不可分的。

由于SVM的分类超平面仅由支持向量决定，则可以考虑一个只含支持向量SVM模型场景，用反证法来证明。假设存在一个SVM分类超平面使所有支持向量在该超平面上的投影依然线性可分。根据简单的初等几何知识可以发现，比起之前假设的超平面最优解，其实拥有另一个更优的解法，这就与之前的假设矛盾。如图：

该证明有不严谨之处，假设了仅有支持向量的情况，会不会在超平面的变换过程中支持向量发生了改变，原先的非支持向量和支持向量发生了转化呢？下面证明SVM的分类结果仅依赖于支持向量。

考虑SVM推导中的KKT条件要求。

$$\nabla_ωL(ω^{*},β^{*},α^{*})= ω^{*} - \sum^N_i α_i^{*}y_ix_i=0 \tag{1}$$

其中求和下$i=1$，为$\sum_{i=1}^N$，不知为何在代码里写入$i=1$就显示不正常，只能写$i$。

$$\nabla_βL(ω^{*},β^{*},α^{*})= -\sum^N_i α_i^{*}y_i=0 \tag{2}$$

其中求和下$i=1$，为$\sum_{i=1}^N$，不知为何在代码里写入$i=1$就显示不正常，只能写$i$。

$$α_i^{*}g_i(ω^{*})=0,i=1,…,N \tag{3}$$

$$g_i(ω^{*})≤0,i=1,…,N \tag{4}$$

$$α_i^{*}≥0,i=1,…,N \tag{5}$$

结合3和4两个条件，当$ g_i(ω^{*})<0 $时，必有$α_i^{*}=0 $，将这一结果与拉格朗日对偶优化问题的公式进行比较。

$$L(ω^{*},α^{*},β^{*})=\frac{1}{2}ω^{*2}+\sum_{i=1}^Nα_i^{*}g_i(ω^{*}) \tag{6}$$

其中

$$g_i(ω^{*})=-y_i(ω^{*}·x_i+β^{*})+1 \tag{7}$$

可见，除支持向量外，其他西数均为0，因此SVM的分类结果与仅支持向量的分类结果一致，说明SVM的分类结果仅依赖于支持向量，这也是SVM拥有极高运行效率的关键之一。这证明了对于任意线性可分的两组点，它们在SVM分类的超平面上的投影都是线性不可分的。

该问题也可以通过凸优化理论中的超平面分离定理（Separating Hyperplane Theorem,SHT）更加轻巧解决。该定理描述的是，对于不相交的两个凸集，存在一个超平面，将两个凸集分离。对于二维情况，两个凸集间距离最短两点连线的中垂线就是一个将它们分离的超平面。

借助此定理，可以先对线性可分的两组点求各自的凸包。SVM求得的超平面就是两个凸包上距离最短的两点连线的中垂线，也就是SHT定理二维情况中所阐释的分类超平面。根据凸包的性质容易知道，凸包上的点要么是样本点，要么处于两个样本点的连线上。因此，两个凸包间距离最短的两个点可以分为三种情况：两边的点均为样本点；两边的点均在样本点的连线上；一边的点为样本点，另一边的点在样本点的连线上。从几何分析可以知道，无论哪种情况，两类点的投影均是线性不可分。

2、是否存在一组参数使SVM训练误差为0

一个使用高斯核（$K(x,z)=e^{\frac{-||x-z||^2}{γ^2}}$）训练的SVM中，试证明若给定训练集中不存在两个点在同一位置，则存在一组参数{$α_1,…,α_m,b$}以及参数γ使得该SVM的训练误差为0。

根据SVM的原理，可以将SVM的预测公式写为

$$f(x)=\sum_{i=1}^mα_iy^{(i)}K(x^{(i)},x)+b \tag{8}$$

其中{$(x^{(1)},y^{(1)}),…,(x^{(m)},y^{(m)})$}为训练样本，而{$α_1,…,α_m,b$}以及高斯核参数γ为训练样本的参数。由于不存在两个点在同一位置，因此对于任意的$i≠j$，有$||x^{(i)}-x^{(j)}||≥ε$。可以对任意$i$，固定$α_i=1$以及$b=0$，只保留参数$γ$，则有

$$f(x)=\sum_{i=1}^mα_iy^{(i)}K(x^{(i)},x)+b$$

$$=\sum_{i=1}^my^{(i)}K(x^{(i)},x) \tag{9}$$

$$=\sum_{i=1}^my^{(i)}e^{\frac{-||x-z||^2}{γ^2}}$$

将任意$x{(j)}$代入式9则有

$$f(x^{(j)})=\sum_{i=1}^my^{(i)}e^{\frac{-||x-z||^2}{γ^2}} \tag{10}$$

$$f(x^{(j)})-y^{(j)}=\sum_{i=1,i≠j}^my^{(i)}e^{\frac{-||x-z||^2}{γ^2}} \tag{11}$$

$$||f(x^{(j)})-y^{(j)}||≤\sum_{i=1,i≠j}^my^{(i)}e^{\frac{-||x-z||^2}{γ^2}} \tag{12}$$

由问题得知$||f(x^{(j)})-y^{(j)}||≥ε$，取$γ=\frac{ε}{\sqrt{logm}}$，可将式(12)重写为

$$||f(x^{(j)})-y^{(j)}||≤||\sum_{i=1,i≠j}^my^{(i)}e^{\frac{-||x-z||^2}{γ^2}}||$$

$$≤||\sum_{i=1,i≠j}^me^{-logm}||=\frac{m-1}{m}＜1 \tag{13}$$

所以，对于任意x^{(j)}，预测结果$f(x^{(j)})$与样本真实标签$y^{(j)}$的距离小于1。注意到，$y^{(j)}\in${ $1,-1$},当训练样本为正例，即$y^{(j)}=1$时，预测结果$f(x^{(j)})＞0$，样本被预测为正例；而当训练样本为负例，即$y^{(j)}=-1$时，预测结果$f(x^{(j)})＜0$，样本被预测为负例。因此所有样本的类别都被正确预测，训练误差为0。

3、训练误差为0的SVM分类器一定存在吗？

虽然在第二节中找到一组参数{$α_1,…,α_m,b$}以及$γ$使得SVM的训练误差为0，但这组参数不一定是满足SVM条件的一个解。在实际训练一个不加入松弛变量的SVM模型时，是否能保证得到的SVM分类器满足训练误差为0呢？

此问题旨在找到一组参数满足训练误差为0，且是SVM模型的一个解。

考虑SVM模型中解的限制条件$y^{(j)}f(x^{(j)})≥1$。已经得到了一组参数使得当$y^{(j)}=1$时，$f(x^{(j)})＞0$；而当$y^{(j)}=-1$时，$f(x^{(j)})＜0$，因此$y^{(j)}·f(x^{(j)})＞0$。现在需要找到一组参数满足更强的条件，即$y^{(j)}·f(x^{(j)})≥1$。

仍然固定$b=0$，于是预测公式$$f(x)=\sum_{i=1}^mα_iy^{(i)}K(x^{(i)},x)$$，将$y^{(j)}·f(x^{(j)})$展开，有

$$y^{(j)}·f(x^{(j)})=y^{(j)}\sum_{i=1}^mα_iy^{(i)}K(x^{(i)},x^{(j)})$$

$$=α_jy^{(j)}y^{(j)}K(x^{(i)},x^{(j)})+\sum_i^mα_iy^{(i)}y^{(j)}K(x^{(i)},x^{(j)})$$

$$=α_j+\sum_i^mα_iy^{(i)}y^{(j)}K(x^{(i)},x^{(j)}) \tag{14}$$

其中求和下$i=1$，为$\sum_{i=1,i≠j}^N$，不知为何在代码里写入$i=1$就显示不正常，只能写$i$。

观察式(14)，可以把每个$α_j$都选择一个很大的值，同时取一个非常小的$γ$，使得核映射项$K(x^{(i)},x^{(j)})$非常小，于是$α_j$在上式中占据绝对主导地位。这样就保证对任意$j$有$y^{(j)}·f(x^{(j)})＞1$，满足SVM解的条件。因此SVM最优解也满足上述条件，同时一定使模型分类误差为0。

4、加入松弛变量的SVM的训练误差可以为0吗？

在实际应用中，如果使用SMO(Sequential Minimal Optimization)算法来训练一个加入松弛变量的线性SVM模型，并且惩罚因子$C$为任一未知常数，是否能得到训练误差为0的模型呢？

使用SMO算法模型的线性分类器并不一定能得到训练误差为0的模型。这是由于我们的优化目标改变了，并不再是使训练误差最小。考虑带松弛变量的SVM模型优化的目标函数锁包含的两项：$C\sum_{i=1}^mζ_1$和$\frac{1}{2}||w||^2$，当我们的参数$C$选取较小的值时，后一项（正则项）将占据优化的较大比重。这样，一个带有训练误差，但是参数较小的点将成为更优的结果。一个简单的特例是，当$C$取0时，$w$也取0即可达到优化目标，但是显然此时我们的训练误差不一定能达到0。