SVM面试题

作者: 0过把火0 | 来源:发表于2018-10-11 22:22 被阅读33次

    SVM的面试题目相对有章可循,本次记录一下常见的几个面试题

    一句话介绍SVM

    SVM是一种二分类模型,他的基本模型是定义在特征空间上的间隔最大的线性分类器,间隔大使它有别于普通的感知机,通过核技巧隐式的在输入空间直接求解映射空间中特征向量的内积,使其成为一个非线性分类器。SVM的学习策略是间隔最大化,可形式化为一个求解凸二次规划问题。

    SVM中的几个核心概念

    1 确定超平面及函数间隔

    由空间上的平面公式确定超平面 wx+b = 0,且 |wx+b| 表示点 x 到平面上的距离。正类负例位于分割平面两侧,因此y(wx+b) 可同时表示分类正确性以及距离确信度。这也就是函数间隔,其被定义为训练集中所有点到超平面距离的最小值。

    2 几何间隔

    由于成比例地缩放w和b会使得 |wx+b| 跟着成比例缩放,因此,需要对法向量w加上约束,使得间隔是确定的,也就是函数间隔整体除以 ||w||,也就得到了几何间隔

    3 间隔最大化(硬间隔)

    分为硬间隔最大和软间隔最大
    SVM的基本思想就是求解可以正确划分数据集并且几何间隔最大的分离超平面,其原因是线性可分超平面有无数个,但是间隔最大超平面是唯一的。

    间隔最大化的意思就是以充分大的确信度对训练数据进行分类,也就是说,不仅将正负实例分开,同时对最难分的实例点(距离超平面最近的点)也有足够大的确信度将其分离。
    此处推出约束优化问题的原始形式(见上一篇博客)

    4 支持向量

    与超平面最近的点被称为支持向量,也就是使得原始问题约束项成立的点。
    实际上离超平面很远的点已经被正确分类,我们让它离超平面更远并没有意义。反而我们最关心是那些离超平面很近的点,这些点很容易被误分类。如果我们可以让离超平面比较近的点尽可能的远离超平面,那么我们的分类效果会好有一些

    5 核函数

    注意,核函数本质不是将特征映射到高维空间,而是找到一种直接在低位空间对高维空间中向量做点积运算的简便方法。
    其证明以及案例可参考李航-统计学习方法 P117

    6 为何将原始问题转为对偶问题

    总是说对偶问题更容易求解,道理在哪呢?

    之所以说换为对偶问题更容易求解,其原因在于降低了算法的计算复杂度。在原问题下,算法的复杂度与样本维度相关,即等于权重w的维度,而在对偶问题下,算法复杂度与样本数量有关,即为拉格朗日算子的个数。
    因此,如果你是做线性分类,且样本维度低于样本数量的话,在原问题下求解就好了,Liblinear之类的线性SVM默认都是这样做的;但如果你是做非线性分类,那就会涉及到升维(比如使用高斯核做核函数,其实是将样本升到无穷维),升维后的样本维度往往会远大于样本数量,此时显然在对偶问题下求解会更好。

    另一方面,我们有分析过,只有在支持向量上的样本对应的拉格朗日算子λ才大于0,其余的λ都是=0,而转为对偶问题的计算对象仅有λ,所以大大降低了计算复杂度。

    为什么SVM对缺失值敏感

    SVM与LR的联系

    1)损失函数
        SVM是hinge损失
        LR是log损失
    2)输出
        LR给出了后验概率
        SVM只给出0或1,也就是属于哪一个类别
    3)异常值
        LR对异常值敏感;SVM相对不敏感,泛化能力好
    4)训练集大小
        较小的训练集更适合SVM。
        SVM的参数优化方法是先转为对偶问题再使用SMO算法,最坏情况下的时间复杂度是O(n^2),并不适合在大规模数据集上做分类。
        另外,在使用核技巧,例如RBF时,特征会升高至无限维,因此其计算量也变得很大。
    5)LR用到所有的样本点来寻找分割面;SVM只用到少数靠近支持面的几个点。
    6)非线性处理方式
        LR靠特征组合高次项;SVM也可以组合,但更多使用核函数
    7)LR较为简单,可以适用于大规模线性分类;SVM较复杂,但是理论支撑完备,
    8)SVM只考虑支持向量
    

    SVM优缺点

    优点:
        1、可以有效解决高维特征的分类和回归问题
        2、无需依赖全体样本,只依赖支持向量
        3、有大量的核技巧可以使用,从而可以应对线性不可分
        4、样本量中等偏小照样有较好的效果
    缺点:
        1、如果特征维度远大于样本个数,SVM表现一般
        2、SVM在样本巨大且使用核函数时计算量很大
        3、非线性数据的核函数选择依旧没有标准
        4、SVM对缺失数据敏感
        5、特征的多样性导致很少使用svm,因为 svm 本质上是属于一个几何模型,这个模型需要去定义 instance 之间的 kernel 或者 similarity(线性svm中的内积),而我们无法预先设定一个很好的similarity。这样的数学模型使得 svm 更适合去处理 “同性质”的特征
    

    为什么SVM的分割超平面方程为 wx + b = 0?

    1)这个超平面的公式是假设。
    2)其中w和x均为向量,b是一个实数。
    3)在三维空间中一个法向量w,一个位移b能够唯一确定一个平面,因此作出如上公式假设。
    而x向量可以看作是原点到平面上任一点的连线向量,而w就是原点垂直于平面的那个向量,因此,w的大小就是原点到超平面的最短距离。
    4)为什么要设其=0?
    为了方便,假设两类样本点的边界到超平面的距离是相等的,因此就设为0,这样的话,wx + b > 0就表示样本点在分割平面上方,wx + b < 0的话就代表在其下方。

    超平面方程与 ax+b=y的直线方程有何联系?

    几何角度解释如何寻找最优超平面

    1)给出一个中间超平面H0,并且其满足wx - b = 0,给出另外两个超平面H1:wx - b = m;H1:wx - b = -m,设定为正负m的目的是为了让H1到H0的距离 = H2到H0的距离。
    2)w和b都是可以进行同步缩放的,因此我们为了简化问题,将m缩放为1,那么两个超平面的方程为:



    3)上述两个超平面的中间是没有数据的,这句话是对超平面的一个约束,转化为数学描述就是:



    上述两个约束可以合并为:其中yi是两类样本中的点

    4)假设:


    上图中其实可以看出,如果X0距离另外一个超平面距离为m的话,那么岂不是X0+m可以求得另一个超平面上的点。
    但是X0是可以看作一个向量,而m只是一个标量,因此需要将m转化为标量,换句话说,也就是想得到一个垂直于H1的且长度为m的一个向量。
    其实对于H1来说,w就是其上的法向量那么:



    那么K就是我们要寻找的向量。

    ok,现在向量k找到了,可以与X0进行相加,可以得到z0 = X0 + k,如下图所示:

    经过上面式子的推导就将m的求法得到了。


    SVM参数C的选择

    SVM核函数的选择

    转载注明:https://www.jianshu.com/p/fa02098bc220

    相关文章

      网友评论

        本文标题:SVM面试题

        本文链接:https://www.haomeiwen.com/subject/bkviaftx.html