点击最下面卡片链接就可以进入专栏，右上角有订阅选项，欢迎大家订阅～

前言

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

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

一、线性分类基础

一句话描述支持向量机SVM：SVM是一种二分类模型，其定义为特征空间上的间隔最大的线性分类器，其优化目标是最大化间隔，最终可转化为一个凸二次规划问题的求解。

我们先考虑一个最简单的线性分类的例子，如下图所示，现在有一个二维平面，平面上有两类数据，分别用圈和叉表示。由于这些数据是线性可分的，所以可以用一条直线将这两类数据分开，这条直线就相当于一个超平面，超平面一边的数据点所对应的全是-1 ，另一边所对应的全是1。

这个超平面可以用分类函数表示，当f(x)等于0的时候，x便是位于超平面上的点，而f(x)大于0的点对应的数据点，小于0的点对应的点，如下图所示：

理论上，存在无数个满足条件的分类超平面，那么如何确定这个超平面呢？从直观上而言，最适合分开两类数据的超平面应该使得离分割平面两边数据的间隔最大，所以，我们需要寻找有着最大间隔的超平面。

二、间隔的定义（函数间隔与几何间隔）

在超平面确定的情况下，能够表示点到距离超平面的远近，而通过观察的符号与类标记的符号是否一致可判断分类是否正确。函数间隔的定义为：

而超平面关于数据集中所有样本点的函数间隔最小值（其中是特征，是结果标签，表示第个样本），便为超平面关于训练数据集的函数间隔：

但这样定义的函数间隔有问题，即如果成比例的改变和（如将它们改成和），则函数间隔的值却变成了原来的2倍（虽然此时超平面没有改变），所以函数间隔有缺陷。

这时可以对法向量w加些约束条件，定义点到超平面的几何距离，即为几何间隔（geometrical margin）的概念。

假定对于一个点，令其垂直投影到超平面上的对应点为，是垂直于超平面的一个法向量，为样本到超平面的距离，如下图所示：

根据高中函数知识，可得：

，

因为几何间隔必然是正数，所以其定义为：

其实几何间隔就是函数间隔除以。

三、最大间隔分类器的定义

对一个数据点进行分类，当超平面离数据点的“间隔”越大，分类的置信度也越大。所以，为了使得分类的确信度尽量高，需要让所选择的超平面能够最大化这个“间隔”值，这个间隔就是下图中的Gap的一半。需要注意的是，这个间隔指的是几何间隔，而不是函数间隔，等比例地缩放w的长度和b的值不会改变几何间隔的值。几何间隔只会随着超平面的变动而变动，所以其可以唯一确定超平面。

最大间隔分类器的优化目标可以定义为：

由几何间隔的定义可知，等比例地缩放w的长度和b的值不会改变超平面，为了方便推导和优化，我们令函数间隔，则上述优化目标函数可以转化为：

如下图所示，中间的实线便是寻找到的最优超平面，其到两条虚线边界的距离相等，这个距离便是几何间隔，两条虚线间隔边界之间的距离等于，而虚线间隔边界上的点则是支持向量。由于这些支持向量刚好在虚线间隔边界上，所以它们满足，而对于所有不是支持向量的点，则显然有。

四、目标函数的优化求解

上一节已经定义了SVM的目标函数：

在这一节中，我们对该目标函数进行推导求解。

为了简化目标函数，我们可以对其进行等价变换，即：

优化的目标函数是二次的，约束条件是线性的，这是一个凸二次规划问题。这个问题可以通过拉格朗日对偶性变换到对偶