SVM常见面试问答 | Swift's Blog

记录一下SVM的常见面试问答：

1. SVM原理

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

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

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

唯一解：当训练数据线性可分时，存在无穷多个超平面可以将两类数据正确分开。线性可分支持向量利用间隔最大化求得最优超平面，此时，解是唯一的。
强泛化性：划分超平面所产生的分类结果是最鲁棒的，对未见示例的泛化能力最强。

3. SVM为什么要从原始问题变为对偶问题来求解？

原问题：

$\min _{w, b} \max _{\lambda} L(w, b, \lambda)=\frac{1}{2}\|w\|^{2}+\sum_{i=1}^{n} \lambda_{i}\left[1-y_{i}\left(w^{T} x_{i}+b\right)\right]$

对偶问题：

$\max _{\lambda} \min _{w, b} L(w, b, \lambda)=\frac{1}{2}\|w\|^{2}+\sum_{i=1}^{n} \lambda_{i}\left[1-y_{i}\left(w^{T} x_{i}+b\right)\right]$

对偶问题往往更易求解：
- 问题复杂度降低：由求特征向量 $w$ 转化为求比例系数 $\lambda$，在原始问题下，求解的复杂度与 $w$ 的维度有关。在对偶问题下，只与样本数量 $n$ 有关；
- 求解更高效：因为只用求解比例系数 $\lambda$ ，而 $\lambda$ 只有支持向量才为非0，其他全为0；
可以自然引入核函数，进而推广到非线性分类问题。

4. KKT条件的作用

$d^{*}=\max _{\alpha, \beta: \alpha_{i} \geq 0} \min _{w} \mathcal{L}(w, \alpha, \beta) \leq \min _{w} \max _{\alpha, \beta: \alpha_{i} \geq 0} \mathcal{L}(w, \alpha, \beta)=p^{*}$

5. SMO基本原理

SMO每次选择两个变量 $\alpha_i$ 和 $\alpha_j$ ，并固定其它参数。在参数初始化后，SMO不断执行如下两个步骤直至收敛：

选取一对需更新的变量 $\alpha_i$ 和 $\alpha_j$ ；
固定 $\alpha_i$ 和 $\alpha_j$ 以外的参数，求解对偶问题 $max_{\alpha} (\sum_{i=1}^{n} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j} x_{i}^{T} x_{j})$ 以获得更新后的 $\alpha_i$ 和 $\alpha_j$ .

至于如何选取，SMO采用了启发式方法：使选取的两变量所对应的样本之间的间隔最大。直观解释：这样的两变量有很大的差别，与对两个相似的变量进行更新相比，对它们进行更新会带给目标函数值更大的变化。

6. 什么是软间隔支持向量机？

当训练数据近似线性可分时，软间隔最大化允许出现分类错误，此时超平面不能将所有训练数据点都分类正确。

引入松弛变量 $\xi$ 来量化分类器的违规行为：

$\begin{aligned} &\min _{W, b, \xi} \frac{1}{2}\|W\|^{2}+C \sum_{i=1}^{n} \xi_{i} \\ &\text { s.t. } y_{i}\left(X_{i}^{T} W+b\right) \geq 1-\xi_{i} \\ &\xi_{i} \geq 0, i=1,2, \ldots n \end{aligned}$

$C$ 是惩罚参数，越小对误分类惩罚越小，容易欠拟合；越大对误分类惩罚越大，容易过拟合。

7. 核函数作用以及如何选取核函数？

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

核函数有如下几种：

线性核
多项式核
高斯核（RBF核）
Sigmoid核

核函数选取技巧：

如果特征的数量大到和样本数量差不多，则选用LR或者线性核函数；
如果特征的数量小，样本的数量正常，则选用高斯核函数；