SVM（面试准备）

2020-02-26 本文已影响0人单调不减

1、手推SVM

整体思路：

定义样本点到目标超平面的几何距离：
$\frac{y_i(wx_i+b)}{||w||}$
定义间隔（margin）为各样本点到超平面的最小距离：
$margin=\min_{w,b}\frac{y_i(wx_i+b)}{||w||}$
根据间隔最大化的目标写出规划：
$\begin{equation*} \begin{array} \text{ max} & r\\ \text{s.t.} & \min_{w,b}\frac{y_i(wx_i+b)}{||w||} \ge r \\ \end{array} \end{equation*}$
由于 $(w,b)$ 和 $(\lambda w,\lambda b)$ 对应超平面相同，故令 $\min_{w,b}y_i(wx_i+b)=1$ ，得到：
$\begin{equation*} \begin{array} \text{ max} &\frac{1}{||w||} \\ \text{s.t.} &y_i(wx_i+b)\ge 1 \\ \end{array} \end{equation*}$

变形得到：
$\begin{equation*} \begin{array} \text{ min} &\frac{1}{2}{||w||}^2 \\ \text{s.t.} &y_i(wx_i+b) - 1 \ge 0\\ \end{array} \end{equation*}$

构建拉格朗日函数：
$L(w,b,\alpha)= \frac{1}{2}{||w||}^2+\sum_{i=1}^{N}\alpha_i[1-y_i(wx_i+b)]$

原问题转化为：
$\min_{w,b}\max_{\alpha}L(w,b,\alpha)$
写出其对偶：
$\max_{\alpha}\min_{w,b}L(w,b,\alpha)$
解对偶内层最优化问题，即令 $L(w,b,\alpha)$ 对 $w$ 和 $b$ 偏导数为0，得到：
$\begin{aligned} &w =\sum_{ i=1}^{N}\alpha_i y_i x_i \\ &\sum_{i=1}^{N}\alpha_i y_i = 0 \\ \end{aligned}$
带入 $L(w,b,\alpha)$ 得到：
$L(w,b,\alpha)=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_j y_i y_j (x_i \cdot x_j)+\sum_{i=1}^N \alpha_i$
从而对偶问题变成：
$\begin{aligned} \max_{\alpha}&\ \ -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_j y_i y_j (x_i \cdot x_j)+\sum_{i=1}^N \alpha_i \\ s.t.&\ \ \sum_{i=1}^{N}\alpha_i y_i = 0 \\ &\ \ \alpha_i \ge 0 \\ \end{aligned}$

即：

$\begin{aligned} \min_{\alpha}&\ \ \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_j y_i y_j (x_i \cdot x_j)-\sum_{i=1}^N \alpha_i \\ s.t.&\ \ \sum_{i=1}^{N}\alpha_i y_i = 0 \\ &\ \ \alpha_i \ge 0 \\ \end{aligned}$

求解此规划得到 $\alpha^*=(\alpha^*_1,\alpha^*_2,\dots,\alpha^*_N)^T$ 。

写出KKT条件：

(1) 原始可行(满足约束)：
$y_i(w^* \cdot x_i+b^*)-1\ge 0$

(2) 对偶可行(满足约束)：
$\alpha^*\ge 0$

(3) 原始内层最优：
$\alpha_i[y_i(w^* \cdot x_i+b^*)-1]=0$

(4) 对偶内层最优：
$\begin{aligned} &w^* - \sum_{ I=1 }^N \alpha^*_i y_i x_i=0 \\ &\sum_{ I=1 }^{N}\alpha_i y_i = 0 \\ \end{aligned}$

由 $\alpha^*$ 得到 $w^*$ 和 $b^*$ ：
$w^*=\sum_{i=1}^N \alpha^*_i y_i x_i$

找到任意 $\alpha^*_j>0$ (必定存在)，由(3)可得：
$y_j(w^* \cdot x_j+b^*)-1=0$

两边同乘 $y_j$ 可得：
$(w^* \cdot x_j+b^*)-y_j=0$

故：
$\begin{aligned} b^* & =y_j-w^* \cdot x_j \\ & = y_j-\sum_{i=1}^N \alpha^*_i y_i (x_i \cdot x_j) \\ \end{aligned}$

若把硬间隔替换为软间隔，则大体推导过程相同，唯一区别是对偶问题变成：
$\begin{aligned} \max_{\alpha}&\ \ -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_j y_i y_j (x_i \cdot x_j)+\sum_{i=1}^N \alpha_i \\ s.t.& \ \ \sum_{i=1}^{N}\alpha_i y_i = 0 \\ & \ \ 0 \le \alpha_i \le C \\ \end{aligned}$

即约束由 $\alpha_i\ge 0$ 变成 $0 \le \alpha_i \le C$ 。

相应的，在求解 $b^*$ 的时候要选择满足 $0<\alpha^*_j<C$ 的 $\alpha_j^*$ 。

若由线性推广到非线性，则把最优解表达式中的 $(x_i \cdot x_j)$ 替换成 $\phi(x_i)\cdot \phi(x_j)$ 来进行求解，这一过程具体说来就是将特征通过 $\phi$ 映射到高维空间，然后将映射后的结果做内积，由于高维空间的内积计算量较大，因此我们考虑核技巧，将两步合为一步，即找到合适的 $K(x_i,x_j)$ 使得：

$K(x_i,x_j)=\phi(x_i)\cdot \phi(x_j)$

这样一来，就可以不显示的写出映射的高维空间而达成同样的目的，既实现了非线性又简化了计算。

2、简述SVM 原理

SVM 是一种二类分类模型。它的基本模型是在特征空间中寻找间隔最大化的分离超平面的线性分类器。

当训练样本线性可分时，通过硬间隔最大化，学习一个线性分类器，即线性可分支持向量机；
当训练数据近似线性可分时，引入松弛变量，通过软间隔最大化，学习一个线性分类器，即线性支持向量机；
当训练数据线性不可分时，使用核技巧及软间隔最大化，学习非线性支持向量机。

3、SVM 为什么采用间隔最大化

当训练数据线性可分时，存在无穷多个分离超平面可以将两类数据正确分开。

线性可分支持向量机利用间隔最大化求得最优分离超平面，间隔最大化能够使得样本都尽量远离分类决策超平面，这会使得模型的结构风险最小，降低模型对数据扰动的敏感性，也就意味着模型有着更强的泛化能力。

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

改变了问题的复杂度。在原问题中，参数数量与样本的维度（即 $w$ 的维度）有关。在对偶问题中，参数数量只与样本数量 $N$ 有关。所以 SVM 对于高维空间中较稀疏的样本表现较好。
求解更高效。因为只用求解 $\alpha$ 系数，而只有支持向量的 $\alpha$ 系数才非0，其它全部为0。求得最优的 $\alpha^*$ 后， $w^*,b^*$ 都可由 $\alpha^*$ 得到。
方便核函数的引入。只有通过求解对偶问题，先消去 $w,b$ ，才能得到内积的形式，从而运用核技巧自然地将线性支持向量机推广到非线性支持向量机。

5、为什么 SVM 要引入核函数

当样本在原始空间线性不可分时，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。

因为特征空间维数可能很高，甚至可能是无穷维，因此直接计算 $ϕ(x)·ϕ(y)$ 是困难的。相反，直接计算 $K(x,y)$ 比较容易（即直接在原来的低维空间中进行计算，而不需要显式地写出映射后的结果）。

核函数的定义： $K(x,y)=<ϕ(x),ϕ(y)>$ ，即在特征空间的内积等于它们在原始样本空间中通过核函数 $K$ 计算的结果。

除了 SVM 之外，任何将计算表示为数据点的内积的方法，都可以使用核方法进行非线性扩展。

P.S.核函数还有一个特点：对于给定的核函数，高维空间 $H$ 和映射函数 $ϕ$ 的取法并不唯一，也就是说，某种程度上，一个核函数的选取可以同时检验多种特征映射的效果。

6、列举几个常用核函数并简要说明优缺点

线性核函数： $K(u,v) = u\cdot v$
多项式核函数： $K(u,v) = (\gamma\cdot u\cdot v + \epsilon)^p$
高斯核函数： $K(u,v) = e^{(-\gamma||u-v||^2)}$

最常用的是Linear核与RBF核。

Linear核：主要用于线性可分的情形。参数少，速度快，对于一般数据，分类效果已经很理想了。
RBF核：RBF核函数可以将一个样本映射到一个更高维的空间，主要用于线性不可分的情形。参数多，分类结果非常依赖于参数。
核函数参数的多少直接影响函数的复杂程度。多项式函数参数数量较多，且多项式的阶数比较高时，核矩阵的元素值将趋于无穷大或无穷小，造成数值计算上的困难。与多项式核函数相比，RBF需要确定的参数要少，且会减少数值计算的困难。

具体实践中，如果特征维数很高，往往线性可分（SVM解决非线性分类问题的思路就是将样本映射到更高维的特征空间中），可以采用线性核函数；如果样本数量很多，由于求解最优化问题的时候，目标函数涉及两两样本计算内积，使用高斯核等非线性核函数计算量会明显大于线性核，所以可以手动添加一些特征，使得线性可分，然后再使用线性核函数；如果不满足上述两点，即特征维数少，样本数量正常，可以使用高斯核函数。

7、为什么 SVM 对缺失值敏感，对异常值不敏感

这里说的缺失数据是指缺失某些特征数据。

首先，SVM 没有处理缺失值的策略（决策树有）。其次，SVM 是基于距离的算法，而距离的计算要求数据各个维度都不能有缺失。类似的，KNN 也是基于距离的算法，因此对缺失值也很敏感。
异常值也就是所谓的离群点。SVM 的解只由支持向量决定，也就是由分类超平面附近的点决定，因此离群点并不会改变 SVM 产生的分类超平面。

8、SVM 如何处理多分类问题

直接法：直接在目标函数上修改，将多个分类面的参数求解合并到一个最优化问题里面。看似简单但是计算量却非常的大。
间接法：对训练器进行组合。比较典型的有一对一和一对多。

一对多，就是对每个类都训练出一个分类器，由于 SVM 是二分类，所以将此而分类器的两类设定为目标类为一类，其余类为另外一类。这样针对 $k$ 个类可以训练出 $k$ 个分类器，训练时第 $i$ 个分类器时取训练集中第 $i$ 类为正类，其余类别点为负类进行训练。判别时，输入信号分别经过 $k$ 个分类机共得到 $k$ 个输出值 $f_i(x)=sgn(g_i(x))$ ，若只有一个+1出现，则其对应类别为输入信号类别；若输出不只一个+1(不只一类声称它属于自己)，或者没有一个输出为+1(即没有一个类声称它属于自己)，则比较 $g_i(x)$ 输出值，最大者对应类别为输入的类别。这种方法的优点是，对 $k$ 类问题，只需要训练 $k$ 个二分类支持向量机；缺点是，各分类器训练时样本类别不均衡，bias 比较高。

一对一，就是针对任意两个类训练出一个分类器，如果有 $k$ 类，一共训练出 $C_k^2$ 个分类器，这样当有一个新的样本要来的时候，用这 $C_k^2$ 个分类器来测试，每当被判定属于某一类的时候，该类票数就加一，最后票数最多的类别被认定为该样本所属的类。

9、SVM 怎么防止过拟合

软间隔的支持向量机中，我们为各个样本引入的松弛变量 $\epsilon_i$ 就是用来防止过拟合的。

10、SVM 的优缺点

优点：

有严格的数学理论支持，可解释性强。
能找出对任务至关重要的关键样本（即：支持向量）。
由于SVM是一个凸优化问题，所以求得的解一定是全局最优而不是局部最优。
不仅适用于线性线性问题还适用于非线性问题(用核技巧)。
高维数据也能用 SVM，这是因为 SVM 对偶形式求解的复杂度与样本数量而不是维数相关，因此 SVM 很擅长解决高维稀疏的问题。

缺点：

二次规划问题求解将涉及 $N$ 阶矩阵的计算( $N$ 为样本的个数), 因此 SVM 不适用于超大数据集。
训练时间长。当采用 SMO 算法时，由于每次都需要挑选一对参数，因此时间复杂度为 $O(N^2)$ ，其中 $N$ 为样本的个数，也就是训练样本的数量。
模型预测时，预测时间与支持向量的个数成正比。当支持向量的数量较大时，预测计算复杂度较高。因此支持向量机目前只适合小批量样本的任务，无法适应百万甚至上亿样本的任务。
只适用于二分类问题(可以通过多个SVM的组合来解决多分类问题)。