1700534018
1700534019
1700534020
1700534021
图3.8 魔鬼视角下分球问题3的解
1700534022
1700534023
后来，“无聊”的科学家们把这些球称为“数据”，把木棍称为“分类面”，找到最大间隔的木棒位置的过程称为“优化”，拍桌子让球飞到空中的念力叫“核映射”，在空中分隔球的纸片称为“分类超平面”。这便是SVM的童话故事。
1700534024
1700534025
在现实世界的机器学习领域，SVM涵盖了各个方面的知识，也是面试题目中常见的基础模型。本节的第1个问题考察SVM模型推导的基础知识；第2题～第4题则会侧重对核函数（Kernel Function）的理解。
1700534026
1700534027
知识点
1700534028
1700534029
SVM模型推导，核函数，SMO（Sequential Minimal Optimization）算法
1700534030
1700534031
问题1 在空间上线性可分的两类点，分别向SVM分类的超平面上做投影，这些点在超平面上的投影仍然是线性可分的吗？
1700534032
1700534033
难度：★★★☆☆
1700534034
1700534035
分析与解答
1700534036
1700534037
首先明确下题目中的概念，线性可分的两类点，即通过一个超平面可以将两类点完全分开，如图3.9所示。假设绿色的超平面（对于二维空间来说，分类超平面退化为一维直线）为SVM算法计算得出的分类面，那么两类点就被完全分开。我们想探讨的是：将这两类点向绿色平面上做投影，在分类直线上得到的黄棕两类投影点是否仍然线性可分，如图3.10所示。
1700534038
1700534039
1700534040
1700534041
1700534042
图3.9 支持向量机分类面
1700534043
1700534044
1700534045
1700534046
1700534047
图3.10 样本点在分类面上投影
1700534048
1700534049
显然一眼望去，这些点在分类超平面（绿色直线）上相互间隔，并不是线性可分的。考虑一个更简单的反例，设想二维空间中只有两个样本点，每个点各属于一类的分类任务，此时SVM的分类超平面（直线）就是两个样本点连线的中垂线，两个点在分类面（直线）上的投影会落到这条直线上的同一个点，自然不是线性可分的。
1700534050
1700534051
但实际上，对于任意线性可分的两组点，它们在SVM分类的超平面上的投影都是线性不可分的。这听上去有些不可思议，我们不妨从二维情况进行讨论，再推广到高维空间中。
1700534052
1700534053
由于SVM的分类超平面仅由支持向量决定（之后会证明这一结论），我们可以考虑一个只含支持向量SVM模型场景。使用反证法来证明。假设存在一个SVM分类超平面使所有支持向量在该超平面上的投影依然线性可分，如图3.11所示。根据简单的初等几何知识不难发现，图中AB两点连线的中垂线所组成的超平面（绿色虚线）是相较于绿色实线超平面更优的解，这与之前假设绿色实线超平面为最优的解相矛盾。考虑最优解对应的绿色虚线，两组点经过投影后，并不是线性可分的。
1700534054
1700534055
1700534056
1700534057
1700534058
图3.11 更优的分类超平面
1700534059
1700534060
我们的证明目前还有不严谨之处，即我们假设了仅有支持向量的情况，会不会在超平面的变换过程中支持向量发生了改变，原先的非支持向量和支持向量发生了转化呢？下面我们证明SVM的分类结果仅依赖于支持向量。考虑SVM推导中的KKT条件要求
1700534061
1700534062
1700534063
，
1700534064
1700534065
（3.1）
1700534066
1700534067
