SVM支持向量机面试整理

发表于 | 分类于 | 阅读次数:

口述 SVM

SVM 叫做支持向量机，它是一种二分类模型。它的基本模型是定义在特征空间的间隔最大的线性分类器。

根据训练数据的不同，SVM 主要分为三种情况：

第一种情况就是，当训练数据线性可分的时候，我们是通过硬间隔最大化，来学习一个线性分类器，也就是线性可分的支持向量机。硬间隔就是说，硬性要求所有的样本点都满足和分类平面间的距离必须大于某个值，也就是说都要满足函数间隔 >= 1 的约束条件。（那什么是函数间隔呢？—— $y_i (w \cdot x_i + b)$，几何间隔？——$y_i (\frac w {||w||}\cdot x_i + \frac b {||w||})$）

SVM 的第二种情况就是，当线性可分的数据中存在一些异常点的时候，也就是数据近似线性可分的时候，这个时候就是利用软间隔最大化，来学习一个线性分类器，也就是线性支持向量机。软间隔就是加入了一个松弛变量，也就是引入了容错性，让部分样本可以不满足上面的约束，也就是让每个样本点满足 函数间隔 >= 1-松弛变量 就可以了，但是我们需要让不满足的样本尽可能的少，所以要为加上相应的惩罚，也就是损失函数要加上 这些松弛变量*C系数。 （其实化简之后最终的对偶问题，软间隔和硬间隔的区别在于，软间隔的拉格朗日系数 $0 \le \alpha_i$，硬间隔的是 $0 \le \alpha_i \le C$）

SVM 还有一种情况就是，当训练数据不线性可分的时候，这个时候的解决办法就是将线性不可分的数据映射到线性可分的高维空间中，通过求解高维中的线性问题来求解原来的非线性问题。这里会用到核技巧，也就是在计算的过程中，不会去显式的定义映射函数，因为这个会特别麻烦，我们只是定义核函数，核函数满足 $K(x, z) = \phi(x) \cdot \phi(z)$

SVM 求解过程：

求解的目标就是，最大化几何间隔，我们是通过求解对偶问题来求解原问题的。因为对偶问题更加容易求解，而且可以后面比较方便引入核函数。然后使用 SMO 算法来求解出模型的参数值（SMO 算法是支持向量机学习的一种快速算法，其特点是不断将原来的问题分类为只有两个参数子问题，并对子问题进行求解，直到所有的变量都满足 KKT 条件为止。因为每个子问题都有解析解，所以每个子问题就能很快得到结果，所以 SMO 还是比较快的）。

SVM 的目标求解目标是在每个样本都满足函数间隔 >= 1的条件下，最大化函数间隔，这个目标函数也可以看作是合页损失函数 $\min_{w, b} \sum _{i=1} ^N [1 - y_i(w \cdot x_i + b)]_+ + \lambda ||w||^2$ .

SVM 特点：

  1. SVM 其实只考虑局部边界线附近的点（也就是支持向量）
  2. SVM 的损失函数自带 L2 正则，有防止过拟合的作用

SVM 缺点：

  1. 如果样本数量太大，SVM 计算会比较困难，因为 SVM 是借助二次规划来求解支持向量的

  2. 解决多分类问题比较麻烦

    SVM 解决多分类主要是两种方法：

    1. 一是 one vs one：任意两类样本之间训练一个 SVM，所有 K 类的话就需要训练 K(K-1)/2 个SVM，在测试的时候，把对应的数据分别对每个 SVM 进行测试，然后统计属于每个类别的个数，最后给个数最多的那个类别
    2. 而是 one vs rest：对 K 个类别，训练的时候依次将某个样本的数据归位一类，其他所有的数据归为一类，这样训练 K 个 SVM。预测的时候，对这 K 个SVM 都去计算 f(x) （也就是wx+b），最后选出这最大的 f 值对应的类别即是最后的类别

1. 介绍 SVM

SVM也叫支持向量机，是一种二分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器。

根据训练数据的不同，主要分为三种情况：

  1. 当训练数据线性可分时，通过硬间隔最大化，学习一个线性分类器，即线性可分支持向量机；

  2. 当训练数据近似线性可分时，引入松弛变量，通过软间隔最大化，学习一个线性分类器，即线性支持向量机；

  3. 当训练数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性支持向量机。

2. SVM 为什么要采用间隔最大化

当训练数据线性可分时，存在无穷个分离超平面可以将两类数据正确分开，如果利用间隔最大化求得最优分离超平面，这时，解时唯一的，并且此时分离超平面所产生的分类结果是最鲁棒的，对未知实例的泛化能力最强。

3. SVM 的损失函数是什么？

SVM 的损失函数等价于合页损失函数：

$$ \min_{w, b} \sum _{i=1} ^N [1 - y_i(w \cdot x_i + b)]_+ + \lambda ||w||^2$$

第一项为合页损失函数, 其中，$[z]_+$ 表示的是，当 z > 0 时，为 z，否则为 0 .

所以原式表示，当样本点被正确分类时，且函数间隔（置信度） $y_i(w \cdot x_i) + b > 0$ 时的损失为 0，否则是 $1 - y_i(w \cdot x_i + b)$

SVM 损失函数的第二项为正则化项，是系数为 $\lambda$ 的 w 的 L2 范数

4. 为什么要将求解SVM的原始问题转换为其对偶问题

  1. 因为对偶问题更容易求解（因为以前新来的要分类的样本首先根据 w 和 b 做一次线性运算，以前的分类决策函数为 $f(x) = sign(w\cdot x + b)$，然后看求的结果是 >0 还是 <0，来判断是正例还是负例；现在只需要将新来的样本与支持向量做内积，现在的分类决策函数为 $f(x) = sign(\sum _{i=1}^N \alpha_i^{*} \cdot y_i \cdot (x \cdot x_i) + b^{*})$，然后运算即可）；
  2. 自然引入核函数，自然推广到非线性分类问题（因为对于非线性分类问题，是将线性SVM的对偶问题中x之间的内积替换为核函数K(xi, xj)）

5. 为什么引进核函数

如果样本在原始空间线性不可分时，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。（也就是核技巧）

引入映射之后的对偶函数为：

$$\max _ \lambda -\frac 1 2 \sum_{i=1}^N \sum _{j=1}^N \lambda_i \lambda_j y_i y_j \phi^T(x_i) \phi(x_j) + \sum _{i=1}^N \lambda_i$$

$$s.t. \sum _{i=1}^N \lambda_i y_i = 0, 0 \le \lambda \le C, i=1,2,…,N$$

由于特征空间的维度一般是高维的，甚至是无穷维的，所以直接计算上面的两个映射函数的内积比较困难的。

（或者说，由于从输入空间到特征空间的这种映射会使得维度发生爆炸式的增长，因此上面的Fai(x)·Fai(z)的运算会非常大，计算很困难，所以通常会构造一个核函数来解决这个问题，从而避免了在特征空间的内积运算，只需要在输入空间内进行内积运算）

而核函数 $K(x,z) = \phi(x) \cdot \phi(z)$，计算核函数 $K(x,z)$ 相对比较容易，可以直接在低维空间计算，而且不需要显式写出映射之后的结果，所以 SVM 引进了核函数。

6. SVM 如何做回归 —— SVR

给定数据集，希望学到一个 $f(x) = w \cdot x + b$ 这样的回归模型，使得 f(x) 和 y 之间尽量接近。

传统的回归模型，通常是直接基于模型输出 f(x) 与真实输出 y 之间的差别来计算损失，当且仅当 f(x) 与 y 完全相同的时候，损失才为 0.

但是 SVR 是能容忍 f(x) 与 y 之间最多有 $\epsilon$ 的偏差，当且仅当 f(x) 与 y 之间的差别大于 $\epsilon$ 时才计算损失。也就是中间有宽度为 $2\epsilon$ 宽度的间隔带，若样本落入这个间隔带，则被认为是预测正确的。

同样，对于两侧的松弛带，跟前面的 SVM 一样，也会引入一个松弛变量，两个的松弛程度可以不同，所以两侧的松弛变量分为是 $\xi _i$ 和 $\hat \xi _{i}$ , 所以SVR的目标为:

$$\min_{w,b,\xi,\hat \xi _i} \frac 1 2||w||^2 + C \sum _{i=1} ^m (\xi _i + \hat \xi _i) $$

$$s.t.f(x_i) - y_i \le \epsilon + \xi_i$$

$$y_i - f(x_i) \le \epsilon + \hat \xi _i $$

$$\epsilon_i \ge 0, \hat \xi_i \ge 0, i = 1,2,…,m.$$

同样采用对偶算法，最后得到的 SVR 的对偶问题为：

$$\max_{\alpha, \hat \alpha} \sum_{i=1}^m y_i(\hat \alpha_i - \alpha) - \epsilon (\hat \alpha_i + \alpha) - \frac {1} {2} \sum {i=1}^m \sum{j=1}^m(\hat \alpha _{i} - \alpha _{i})(\hat\alpha _{j} - \alpha {j}) x{i}^{T} x_{j}$$

$$s.t. \sum_{i=1}^m(\hat\alpha_i - \alpha_i) = 0$$

$$0 \le \alpha_i, \hat\alpha_i \le C.$$

最后，SVR 的解的形式为：$f(x) = \sum _{i=1}^m(\hat\alpha_i - \alpha_i)x_i^Tx+b$ .

落在间隔带之外的点就是支持向量，由于 SVR 最后解的形式仍然有 x 与 x 之间的内积，所以仍然可以使用核函数。

7. SVM 与感知机的区别和联系

什么是感知机？

感知机是二类分类的线性分类模型，输出是 -1，+1。感知机 $f(x) = sign(w \cdot x + b)$，当 $f(x) \ge 0$ 时，为+1，<0 时为 -1.

损失函数时：误分类点到超平面的总距离

误分类点，即 $y \cdot (w \cdot x + b) < 0$，故所有误分类点到分离超平面的距离，也就是感知机的损失函数为：
$$
L(w, b) = - \sum_{x_i \in M} y_i(w \cdot x_i + b)
$$
M 是误分类点的集合。然后利用 SGD 进行求解。

8. SVM 与 感知机的区别和联系？

感知机会因为采用不同的初值而得到不同的超平面，而且得到的超平面不一定是最优的。SVM 试图找到一个最优的超平面，这个最优，SVM 利用间隔最大化来衡量。主要区别是：

  1. 感知机追求最大程度分类正确，最小化错误，比较容易造成过拟合；SVM 在追求正确分类的同时，还要求间隔最大，在一定程度上避免了过拟合；
  2. 感知机的学习方法是梯度下降，SVM 的学习方法是对偶。

9. Linear SVM 与 LR 的区别是什么？

Linear SVM 就是书上讲的线性可分 SVM，不加 Kernel 的。

  • Linear SVM 与 LR 都是线性分类模型
  • Linear SVM 不直接依赖数据分布，分类平面不受一类点影响；LR 受所有数据点的影响，如果不同的类别之间数据不平衡，一般要先对数据做 balancing
  • Linear SVM 依赖距离度量

10. SVM 和 LR 对同一样本 A 进行训练，如果某类中增加一些数据点，那么原来的决策边界分别会怎么变

假设在增加了一个 “+” 例点：

对于 SVM，如果这个点在间隔之外，则原来的决策边界不受影响。

如果这个数据点在间隔内部，或者在“-”的那一侧，那么这个点会成为新的支持向量。但是，决策边界不一定会发生变化，因为这个数据点也可能被容错项处理掉了。

对于 LR，w 与 $x_{n+1}$ 之间的夹角会变小，也就是说 决策边界 会发生旋转，使其发现更加接近 $x_{n+1}$ 的方向。

11. 常见的核函数

  1. 线性核函数

    $k(x, z) = x \cdot z$

    主要用于线性可分的情况，特征空间和输入空间的维度是一样的，其参数少速度快，对于线性可分数据，其分类效果很理想，因此我们通常首先用线性核函数来做分类，如果效果不行再尝试其他

  2. 多项式核函数

    $k(x, z) = (a(x \cdot z) + c)^d$

    多项式核函数可以实现将低维的输入空间映射到高维的特征空间，但是多项式核函数参数多，当多项式的阶数比较高的时候，核矩阵的元素将趋近无穷，计算复杂度会大到无法计算

  3. 高斯核函数（径向基函数RBF）

    $k(x, z) = \exp(-\frac {||x - z ||^2} {2\sigma ^2})$

    高斯径向基函数是一种局部性强的函数，其可以将一个样本映射到一个更高维的空间内，该核函数是应用最广的一个，无论大样本还是小样本都有比较好的性能，而且其相对多项式核函数参数要少，因此大多数情况下在不知道用什么核函数的时候，优先使用高斯核函数

    变种：

    • 指数核函数：$k(x, z) = \exp(-\frac {||x - z ||} {2\sigma ^2})$

      仅仅将高斯核函数中向量之间的L2距离调整为L1距离，这样的改动会对参数的依赖性降低，但是适用范围相对窄

    • 拉普拉斯核函数：$k(x, z) = \exp(-\frac {||x - z ||} {\sigma})$

      完全等价于指数核，唯一的区别在于拉普拉斯核函数对参数的敏感性降低了

  4. sigmoid核函数

    $k(x, z) = \tanh (\alpha(x \cdot z) + c)$

    采用sigmoid核函数，支持向量机实现的就是一种多层神经网络

在选择核函数的时候，如果对数据分布有一定的先验知识，就利用先验知识来选择符合数据分布的核函数；如果不知道的话，就使用交叉验证的方法，来试用不同的核函数，误差最小的即为最好的核函数，或者也可以将多个核函数混合起来，形成混合核函数。

吴恩达的课上，给出的选择核函数的方法：

  1. 如果特征数量大到和样本数量差不多，则选择LR或者线性核函数的SVM或者无核的SVM
  2. 如果特征数量小，样本的数量正常，则选用高斯核函数的SVM
    . 如果特征数量小，而样本的数量很大，则需要手工添加一些特征，从而变成第一种情况

12. SVM如何处理多分类的问题

一般有两种做法，一种是直接法，一种是间接法

  • 直接法：直接在目标函数上面进行修改，将多个分类面的参数求解合并到一个最优化问题中，通过求解该最优化问题“一次性”实现多分类。但是！这个问题看似简单，但是计算复杂度比较高，实现起来很困难，只适用于小型问题；

  • 间接法，主要是通过组合多个二分类器来实现多分类器的构造，常见的有 one-vs-one 和 one-vs-rest（一对一 和 一对多）

    1. one-vs-one，一对一法（OVO SVMs）：在任意两类样本之间设计一个SVM，因此 K 类就需要 K(K-1)/2 个 SVM。

      当对一个未知样本进行分类时，最后得票最多的类别即为未知样本的类别。

      libsvm 中的多分类就是这样实现的。

      • 例子

      假设有四类A, B, C, D四类。在训练的时候，选择 A and B; A and C; A and D; B and C; B and D; C and D，共 4*(4-1)/2=6 组数据作为训练集，得到 6 个训练结果，即 6 个二分类器。

      在测试的时候，把对应的测试数据分类对这6个二分类器进行测试，然后采取投票的形式，最后得到分类结果：

      计数器 a = b= c = d = 0：

      对 (A, B) 分类器：若属于A，则a+=1；else：b+=1；

      对 (A, C) 分类器：若属于A，则a+=1；else：c+=1；

      ……

      最后的分类结果即为：Max(a, b, c, d) 对应的类别。

      • 评价：当类别很多的时候，model 的个数 n*(n-1)/2 个，代价还是比较大

    2. one-vs-rest，一对多法（OVR SVMs）：训练时依次将某个类别的样本归为一类，其他剩余的归为一类，这样 K 个类别的样本就构造出 K 个二分类SVM。

      当对一个未知样本进行分类时，具有最大分类函数值的类别即为未知样本的类别。

      • 例子

      假设有四类A, B, C, D四类。在训练的时候抽取：

      1. A 为正类，BCD共同为负类
      2. B为正类，ACD共同为负类
      3. C为正类，ABD共同为负类
      4. D为正类，ABC共同为负类

      使用这四个训练集分别进行训练，得到4个二分类SVM。

      在测试的时候，那对应的测试数据分别利用这4个二分类器进行测试，最后每个测试都有一个结果：f1(x), f2(x), f3(x), f4(x).

      最后的分类结果即为：Max( f1(x), f2(x), f3(x), f4(x) ) 对应的类别。

      • 评价：

      这种方法有种缺陷：因为训练集是 1:M，这种情况下存在 biased，因而不是很实用。可以在抽取数据集的时候，从完成的负集中抽取1/3作为训练负集。

Reference

https://applenob.github.io/svm.html#3.2-%E8%BD%AF%E9%97%B4%E9%9A%94%E6%9C%80%E5%A4%A7%E5%8C%96 （关于推导）

https://blog.csdn.net/szlcw1/article/details/52259668 （关于整体的介绍）

https://www.cnblogs.com/CheeseZH/p/5265959.html （关于SVM多分类）

https://blog.csdn.net/batuwuhanpei/article/details/52354822 （关于常用核函数）

https://blog.csdn.net/wsj998689aa/article/details/47027365 （关于其他补充核函数）