前言

大家好，我是鬼仔，今天带来《机器学习高频面试题详解》专栏的第1.8节：支持向量机（下）。支持向量机 (support vector machine-SVM) 是机器学习中最基础的分类算法之一，很多同学可能都很熟悉，但是一部分同学可能只理解了较为浅层的知识，可以应付一些常见的八股文面试题，但如果面试官不按常规套路出牌，问一些比较冷门或者比较底层的原理问题，很多同学可能就招架不住了。

支持向量机的内容较多，分为上下两篇解读：上篇主要讲算法的原理，下篇主要解析高频面试真题。目前这篇是试读，后续的文章需要订阅才能查看哦，专栏预计更新30+篇文章（只增不减），具体内容可以看专栏介绍，大家的支持是鬼仔更新的动力！

面试真题

一、SVM为什么采用间隔最大化的策略？

如下图所示，给定的训练数据是线性可分的，则存在很多个分类平面可以将训练数据正确地分离，我们需要确定一个最优的分类平面。SVM提出了间隔的概念，对一个数据点进行分类，当分类平面离数据点的“间隔”越大（这个间隔就是下图中的Gap的一半），分类的置信度也越大。利用间隔最大化得到的分类平面，对现实中未知实例的泛化能力最强。

二、SVM为什么通常求解对偶问题而不求解原问题？

1. 对偶问题可以简化原问题的求解

SVM原问题中，优化的目标函数是二次的，约束条件是线性的，这是一个凸二次规划问题，约束的存在虽然减小了需要搜寻的范围，但是却使问题变得更加复杂。原问题的求解严重依赖于数据集的维度，如果维度太高会使得求解效率极速地下降。

为了使问题变得易于处理，可以通过拉格朗日对偶性变换到对偶变量的优化问题，即通过求解与原问题等价的对偶问题得到原始问题的最优解。具体的做法是把目标函数和约束全部融入一个新的函数，即拉格朗日函数，再通过这个函数来寻找最优点。对偶问题把SVM从依赖全体数据集转变到只依赖N个数据点（支持向量），最后计算时只有支持向量有意义，所以计算量比原问题小很多。

2. 方便为非线性分类问题引入核函数

为了解决非线性分类问题，SVM结合对偶问题的特性引入了核函数的定义。因为对偶问题只涉及到数据的内积计算，所以可以将核函数直接定义为特征空间中的内积。

三、SVM中的KKT条件指的是什么？

简要地说，KKT条件是求解有不等式约束优化问题的一种方法，可以理解为是拉格朗日乘子法的一种泛化。

1. 优化问题是凸优化的话，KKT条件就是极小值点（而且是全局极小）存在的充要条件；

2. 不是凸优化的话，KKT条件只是极小值点的必要条件，不是充分条件，KKT点是驻点，是可能的极值点。也就是说，就算求得的满足KKT条件的点，也不一定是极小值点，只是说极小值点一定满足KKT条件。

更详细的拉格朗日乘子法和KKT条件解读，可以参考这篇博客，写的很不错：https://www.cnblogs.com/liaohuiqiang/p/7805954.html

四、为什么SVM要引入核函数？

当样本在原始空间线性不可分时，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。这类映射函数往往非常复杂，而且高维特征空间的维度可能是超级高的，甚至是无穷的，在这种情况下，计算复杂度也难以接受。

但是我们SVM可以通过对偶问题来求解，无需求解出真正的映射函数，而只需要知道其核函数即可完成计算。

核函数就是特征映射至高维空间后的内积，即在特征空间的内积等于它们在原始样本空间中通过核函数计算的结果。在学习和预测中只需要