BAT面试题1：请简要介绍下SVM
文末送惊喜
接下来，每天推送1道BAT的面试题，一般问到的这些知识点都是很重要的，所以知道的呢就再复习一下，不知道的赶紧弥补。日积月累，你会在不知不觉中就已入机器学习的大门，并且越走越深。同时，此方法不光帮你学知识，还能帮你顺利拿到OFFER.
今天BAT系列第一题 说说SVM
之前，关于支持向量机的文章已经推送过4篇了。今天再在这里全面汇总下。支持向量机的简称为SVM，能在已知样本点很少情况下，获得很好的分类效果。
SVM分类两个点。已知两个样本点，如果用SVM模型，决策边界就是线g，它的斜率为已知两个样本点斜率的垂直方向，并经过两个点的中点。
这条线g就是SVM认为的分类两个样本点的最好边界线。
SVM分类多个点
添加更多的样本点，但是有意识地让它们符合上面的分布，此时的最佳决策边界发生变化了吗？没有。样本点虽然多了，但是SVM认为起到支持作用的还是那两个点，support vector就是它们，名字得来了，当然因此决策边界也未变。以上这些都是直接观察出来的，计算机是如何做这个事的？
还启发我们，SVM建立决策边界时，只关心距离决策边界最近的那两个样本点，然后取距离它们都最远的决策边g ，认为g就是最佳决策边界。
有了以上基础，SVM目标函数的结构差不多就知道了：max ( min() )，SVM添加了一个约束，得到的好处是目标函数更精简了：
arg max 1/||w||
s.t., y*f(x)>=1
注意，这个更精简的目标函数，必须满足上面的约束，它们是共生关系，缺一不可。
最大值转化为求最小值。机器学习中，遇到目标函数求最大值的，都会转化为求最小值，常规套路，SVM也不例外。
它也很简单，分母最小，原式便能最大，即：
arg min 0.5*||w||^2
s.t., y * f(x)>=1
目标函数为什么带有系数0.5，没有特殊原因，只不过求导时，0.5*2化简方便。
这是常见的二次规划问题，求解方法有很多种，拉格朗日方法、Lemke方法、内点法、有效集法、椭球算法等。
SVM的以上目标函数求解选用了拉格朗日方法，可以查阅资料，了解此求解方法，里面还用到KKT，转化为先求w,b的最小值，然后再求alfa_i的最大值问题，进而求得参数w和b，至此完毕。
SVM还考虑了软间隔，核函数问题。噪音点出现了。如下图所示，有一个带圈的噪音点出现在了右下角，决策边界在哪里？
如果决策边界这样，可以看出它不是好的决策边界，因为噪音点是错误点，不应该拿它作为支持向量。
克服噪音：松弛因子。SVM适当地放宽了约束条件，将 yi * f(xi) >=1，放宽为 yi * f(xi) >=1-ei，这个间隔ei就是软间隔。为什么要减去ei，而不是加上ei，因为前者可能使得更多的样本点成立，比如第一幅图中，作为正的支持向量点可能不满足 yi * f(xi) >=1，但是可能满足 yi * f(xi) >=1-ei，这样即便噪音点出现了，我们仍然可能得到第一幅的分类决策边界。
ei在SVM中称为松弛因子，SVM中用控制因子C来控制ei，当C很大时，ei发挥的作用很小，也就是松弛的很小；C很小时，ei发挥的作用很大，可能松弛的作用更强些。
以上介绍了SVM参数求解和软间隔部分，它们还不是SVM最巧妙的部分SVM真正精彩之处在于将低维空间线性不可分问题转化为高纬空间线性可分问题，比如一个数据集有3个特征，此时线性不可分，但是转化成9个特征后，在此空间下可能就线性可分了，如下图所示，在二维空间下线性不可分，转化到三维下，就可以得到一个线性可分面。
这是如何做到的？核函数将低维下的原始特征映射到了高维下。
数据映射到高维空间后，是否求解的复杂度陡增呢？ 不会的。在低维空间下样本点求内积的结果，只需花费O(1)时间复杂度直接转化为高维下的内积结果。
至此，SVM就介绍完了，SVM的目标就是求出一个最胖的决策宽度，所有的样本点中，真正起到支持作用的点就是离着决策边界最近的点。大家可以拿两个点来求决策边界为例，想一下SVM的几何意义。
里面的理论涉及到，点到直线的距离，目标函数通过添加一个约束条件变得更加精简，此时变为了已知约束条件和目标函数的二次规划问题，采取了拉格朗日法求最佳决策边界，也就是w和b。
为了解决噪音点，约束条件做了一定的松弛。
核函数是添加的一个映射，将低维空间下的数据映射到高维下，并且计算的时间复杂度几乎未改变，这是核函数顺利实施的前提。
BAT系列第一题
说说SVM 目标函数和约束怎么得来的？
更容易理解SVM的目标函数和约束怎么得来的思路，因此，记录下来，与大家一起分享。设 g(x) = wx+b，则样本点到g(x)的距离为：
|g(x)| / ||w||
SVM 建立决策边界时，只关心距离决策边界最近的那两个样本点，然后取距离它们都最远的决策边，转化为数学公式为：
max(min(|g(x)| / ||w||))
将它化简为：
max( 1/||w||)
s.t. yi*g(xi) >=1
怎么想出来的？
如果设 |g(x)| >= 1 ，则 min( |g(x)| / ||w|| ) = 1 / ||w|| , 进一步地，max(min(|g(x)| / ||w||)) ，可以化简为：
max ( 1 / ||w|| )
那么， |g(x)| >= 1 ，如何化简为 yi * g(xi) >= 1 呢？ 注意到 yi 是 第 i 个样本的标签值，要么为 1， 要么为 -1. 当 g(x) >= 0，代表为正例，即 yi = 1，当 g(x) < 0，代表负例，即 yi = -1，因此，|g(x)| = yi * g(x) >= 1.
OK. 接下来便是求解如下最优化目标和约束的优化问题：
max( 1/||w||)
s.t. yi*g(xi) >=1
关于支持向量机更加全面的公式推导，请参考之前花几天时间写的文章：