2.12 支持向量机SVM与核方法

1.从一条最稳的分界线说起：最大间隔

说起来，前面十几章我们几乎都在聊神经网络，这一章不妨换个口味，回头看一眼经典机器学习里那些顶梁柱一般的方法。其中最有代表性的，大概要数支持向量机（SVM）。这方法在二十世纪九十年代末到2010年前后，一度是工业界和学术界的默认选择，文本分类、图像识别、生物信息里到处都能见到它的身影。深度学习兴起之后，它在很多大数据集上被神经网络盖过风头，可一旦遇到小样本高维的任务，SVM依然稳得很，很多医学诊断和金融风控的场合，大家仍然爱用它。

那SVM到底在做什么呢。我们从最简单的二分类讲起。想象平面上散着两类点，一类是圆圈，一类是叉，我们要找一条直线把它们分开。说穿了，只要两类能被一条直线分开，这样的直线一般有无穷多条，每一条都能在训练数据上做到零误差。问题就在于，这么多条直线里，到底该挑哪一条。

SVM给出的答案特别干净。它挑的那条直线，是离两边样本都最远的那条。我们把这条分界直线记作 $w^T x + b = 0$，其中 $x$ 是输入特征向量（描述一个样本的一串数字），$w$ 是和直线方向有关的权重向量，$b$ 是一个偏置常数，决定直线离原点的远近。这条直线本身只是一个分界，真正关键的是它两边的那片缓冲地带。

我们关心的，是这条直线离最近的样本有多远，这个距离就叫做间隔（margin），记作 $m$，全文用 $m$ 这个字母专指间隔。SVM要做的事，就是在所有能把两类分开的直线里，挑出间隔 $m$ 最大的那一条。直觉上这样选是有道理的，间隔越大，分界线离两边的样本都越远，新来的点稍微有点扰动，也不容易跨到另一边去，泛化（在没见过的数据上的表现）自然就稳。说起来这道理和开车有点像，路两边留的余地越宽，方向盘抖一抖也不至于冲下路基。

讲到这里得提一下支持向量（support vector）这个词。一条最大间隔的直线，通常只有很少的几个样本离它最近，正是这几个点撑起了间隔的两条边界。这些点就叫支持向量。说穿了，分界线的位置其实就是被这几个支持向量决定的，其他离得远的样本，多一点少一点，对结果完全没有影响。这一点和逻辑回归很不一样，逻辑回归的参数会被所有样本一起推着走，而SVM只盯住那几个关键的边界点。我之前看过一本讲统计学习的书，里面形容支持向量是站在国境线两侧的哨兵，剩下的样本都在后方安然度日，边界怎么画，全看哨兵站在哪儿。

2.把最大间隔变成一个优化问题

光说挑间隔最大的直线还不够，得把它写成一个数学上能解的问题。先把分类标签约定好，正类记作 $+1$，负类记作 $-1$，一个样本 $(x_i, y_i)$ 被正确分类并且落在间隔边界之外，意味着要满足 $y_i (w^T x_i + b) \ge 1$，其中下标 $i$ 是样本编号，$y_i$ 是这个样本的真实标签（取值为 $+1$ 或 $-1$），$x_i$ 是它的特征向量。这个不等式其实就是在说，正类样本要被分到直线正的一侧足够远的地方，负类样本要被分到负的一侧足够远的地方。

在这个约束下，间隔 $m$ 可以推出 $m = \frac{2}{|w|}$，其中 $|w|$ 是权重向量 $w$ 的长度（也就是L2范数，1.3 节讲正则化的时候细聊过）。这个 $m=\frac{2}{|w|}$ 是怎么来的，我们推一下。 取正好落在间隔边界上的两个点：一个正类 $x_+$ 满足 $w^\top x_+ + b=1$，一个负类 $x_-$ 满足 $w^\top x_- + b=-1$。间隔全宽就是这两个点到分界超平面 $w^\top x+b=0$ 的距离之和。一点 $x_0$ 到超平面 $w^\top x+b=0$ 的距离公式是 $\frac{|w^\top x_0+b|}{|w|}$，所以：

$$m=\frac{|w^\top x_+ + b|}{|w|}+\frac{|w^\top x_- + b|}{|w|}=\frac{1}{|w|}+\frac{1}{|w|}=\frac{2}{|w|}$$

要让 $m$ 最大，等价于让 $|w|$ 最小，平方一下再去掉常数，等价于最小化下面这个目标函数：

$$\frac{1}{2} |w|^2$$

前头那个 $\frac{1}{2}$ 纯粹是为了求导之后式子好看，对结果没有实质影响。所以SVM的训练，就变成了一个带约束的优化问题：在所有样本都被正确分类（$y_i (w^T x_i + b) \ge 1$）的前提下，把 $\frac{1}{2} |w|^2$ 压到最小。这种带二次目标函数和线性约束的问题，叫二次规划，有成熟的求解方法，数学上性质非常好。

到这里我们一直假设两类能被一条直线干净分开，这种情况叫线性可分。可现实里的数据哪有那么干净，噪声和异常点几乎总会出现。举个例子，某家电商想根据用户的浏览时长和购买金额，把高意向客户和低意向客户分开，绝大部分人分得很清楚，可总有那么几个乱入的样本，比如有人浏览了很久却没下单，特征看起来像高意向，标签却是低意向。要是为了这种点硬把间隔压到零甚至负数，模型就被一两个噪声带歪了。

于是就有了软间隔（soft margin）的说法。软间隔的意思是允许个别样本越界，但每越界一点都要付代价。我们给每个样本引入一个松弛变量 $\xi_i$（希腊字母 $\xi$ 读作ksi），$\xi_i$ 表示第 $i$ 个样本违反间隔约束的程度，$\xi_i = 0$ 表示老老实实呆在间隔边界外头，$\xi_i$ 越大表示越界越严重。约束就放宽成了 $y_i (w^T x_i + b) \ge 1 - \xi_i$。

光放宽约束还不够，得在目标函数里加一笔惩罚，免得模型一股脑把所有样本都松过去。目标函数变成：

$$\frac{1}{2} |w|^2 + C \sum_{i=1}^{n} \xi_i$$

其中 $C$ 是一个由我们设定的惩罚系数，$n$ 是样本总数，$\sum$ 是求和符号，意思是从第 $1$ 个样本到第 $n$ 个样本的 $\xi_i$ 全部加起来。$C$ 这个参数特别关键，它直接决定了模型对越界的容忍程度。$C$ 设得很大，惩罚狠，模型几乎不允许样本越界，间隔会很窄，容易把噪声也当真，这叫过拟合。$C$ 设得很小，模型对越界很宽容，间隔很宽，可分界可能太粗放，这叫欠拟合。$C$ 的取值通常靠交叉验证（在验证集上反复试）来确定，常用值在 $0.01$ 到 $100$ 这个量级里挑。记得有一次，小张在调一个垃圾邮件分类的SVM，$C$ 一上来设成了 $1000$，训练集上一条没错，验证集上却崩得厉害，这就是间隔太窄把训练数据里的噪声也背了进去，后来把 $C$ 压到 $1$ 附近才稳下来。

3.对偶问题：为什么 SVM 只用到内积

前面我们把 SVM 写成了一个带约束的优化，但直接解它（原始问题）有个麻烦：算出来的 $w$ 维度跟特征一样高，高维数据下很难算。SVM 真正的威力藏在它的对偶形式里——对偶形式不仅好解，还只用到样本之间的内积，这正是后面核技巧能登场的前提。这一节把对偶推导从头走一遍，它是 SVM 整套理论的枢纽。

我们从硬间隔（线性可分）的原始问题出发：最小化 $\frac{1}{2}\|w\|^2$，受约束 $y_i(w^\top x_i+b)\geq 1$。用 1.5 节的拉格朗日乘子法，给每个约束配一个乘子 $\alpha_i\geq 0$，构造拉格朗日函数：

$$\mathcal L(w,b,\alpha)=\frac{1}{2}\|w\|^2-\sum_{i=1}^{n}\alpha_i\bigl[y_i(w^\top x_i+b)-1\bigr]$$

对偶的做法是先对 $w$ 和 $b$ 求最小。分别令偏导为零：

$$\nabla_w\mathcal L=w-\sum_i\alpha_i y_i x_i=0\;\Longrightarrow\;w=\sum_i\alpha_i y_i x_i$$ $$\frac{\partial\mathcal L}{\partial b}=-\sum_i\alpha_i y_i=0$$

把这两个结果代回 $\mathcal L$，经过一番代数化简（$w^\top w=\sum_{i,j}\alpha_i\alpha_j y_i y_j x_i^\top x_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^\top x_j$$

受约束 $\alpha_i\geq 0$ 且 $\sum_i\alpha_i y_i=0$。注意这个对偶问题里，数据只以 $x_i^\top x_j$ 这种内积的形式出现，单个样本的坐标本身不再单独出现。 这一点是核技巧能成立的关键。

解完对偶问题得到每个 $\alpha_i$，再用 $w=\sum_i\alpha_i y_i x_i$ 还原 $w$。预测一个新点 $x$ 时：

$$f(x)=w^\top x+b=\sum_i\alpha_i y_i(x_i^\top x)+b$$

也是只用到内积。

KKT 互补松弛：为什么只有支持向量起作用

对偶问题的解满足 1.5 节讲过的 KKT 条件，其中最关键的一条是互补松弛：

$$\alpha_i\bigl[y_i(w^\top x_i+b)-1\bigr]=0$$

这一条说：对每个样本，要么 $\alpha_i=0$，要么 $y_i(w^\top x_i+b)-1=0$（也就是这个样本正好落在间隔边界上）。换句话说，只有那些正好踩在间隔边界上的样本（也就是支持向量），对应的 $\alpha_i$ 才大于零；离边界远的样本 $\alpha_i=0$，在 $w=\sum_i\alpha_i y_i x_i$ 里根本不出现，对模型毫无贡献。

这就从数学上严格解释了开头那个直觉——分界线只由支持向量决定，其他样本多一个少一个都无所谓。这也是 SVM 在小样本上稳的原因：它只认几个关键点，不被海量普通样本带偏。

4.线性不可分的时候：核技巧登场

最大间隔讲完了，可很多数据从根子上就不是一条直线能分开的。最经典的例子就是异或（XOR），四个点交叉排开，你怎么画直线都分不开。再比如医学里判断一个肿瘤是良性还是恶性，仅靠半径和纹理这两个特征画一条直线，多半是分不开的。怎么办呢，SVM的招数是把数据从原来的空间映射到一个更高维的空间里去，在那个高维空间里，数据往往就线性可分了。

不妨拿一个二维的小例子来感受。平面上有一圈圆圈把一个叉围在中间，无论你怎么画直线都分不开。可要是我们再加一个维度，把每个点 $(x_1, x_2)$ 映射成 $(x_1, x_2, x_1^2 + x_2^2)$，其中 $x_1$ 和 $x_2$ 是原来的两个坐标，新加的第三维是前两维的平方和。映射之后，外圈那些点因为离原点远，平方和大，被顶到了高处，中间那个叉平方和小，留在低处。这时候只要拿一个平面（高维空间里的直线）横着切一刀，就能把两类分开了。这便是核技巧（kernel trick）背后的直觉：升维之后，原本缠在一起的数据就被拉开了。

可是真要把每个样本都显式映射到高维空间去算，维度一高，计算量就吃不消了，有时候目标空间甚至是无穷维的，根本没法显式表示。这里有个非常巧妙的发现，SVM的训练和预测从头到尾只用到样本之间的内积（两个向量点乘得到的一个数），并不需要单独算每个样本在高维空间里的坐标。上一节推出来的对偶问题里，数据恰恰只以 $x_i^\top x_j$ 的形式出现——我们只要把对偶目标和预测公式里所有的 $x_i^\top x_j$ 直接替换成 $K(x_i,x_j)$，就等于隐式地在一个高维空间里求解，而根本不用算出那个高维坐标。于是我们直接定义一个核函数 $K(x_i, x_j)$，让它返回两个样本在映射之后的高维空间里的内积，这样就省去了显式映射这一步。这就是所谓的核技巧——它的合法性完全建立在上节对偶形式"只用内积"这个性质上。

常用的核函数有这么几种。第一种是线性核 $K(x_i, x_j) = x_i^T x_j$，其实就是不升维，直接用原空间的内积，适合本身就比较容易线性分开的数据，比如某些文本分类里把词频当特征的高维稀疏向量。第二种是多项式核 $K(x_i, x_j) = (x_i^T x_j + c)^d$，其中 $c$ 是一个常数项，$d$ 是多项式的次数，能刻画特征之间一定程度的组合关系。最常用的大概是第三种，RBF核，又叫高斯核：

$$K(x_i, x_j) = \exp(-\gamma |x_i - x_j|^2)$$

其中 $\exp$ 是指数函数（$e$ 的多少次方），$|x_i - x_j|^2$ 是两个样本在原空间里的欧氏距离平方，$\gamma$（gamma）是一个由我们设定的参数，控制核函数随距离衰减的快慢。$\gamma$ 设得大，核函数衰减快，只有离得很近的样本才算得上关系密切，决策边界会很弯曲，容易过拟合。$\gamma$ 设得小，核函数衰减慢，远处样本也互相影响，决策边界会很平滑，可能欠拟合。$\gamma$ 通常和前头的 $C$ 一起调，sklearn这个库里SVM默认的 $\gamma$ 取 $\frac{1}{\text{特征数}}$ 这个量级。RBF核的好处是把数据隐式映射到一个无穷维的空间里，能力很强，同时又不用真的去算那个无穷维的坐标，这是它受欢迎的根本原因。说起来这一招挺有江南园林的味道，方寸之间见丘壑，看似在原空间里没动地方，实则早就把数据请到了一个看不见的高维空间里完成分类。

5.SVM的特点和适用场景

讲完原理，我们再来看看SVM到底适合用在哪些地方。

SVM最大的长处，是在小样本高维的场景里特别稳。所谓小样本高维，就是样本数不多，可每个样本的特征数却很多。文本分类就是典型，一段文本可能用几千上万个词的词频来表示，可带标签的训练文本却只有几百篇，这种场景下逻辑回归和神经网络往往容易过拟合，SVM靠着最大间隔的约束，反而能把分界画得很稳。基因诊断也是类似，几千个基因表达量作特征，样本却只有几十例，SVM几乎是默认选择。

我之前看过一份二十多年前的经典论文，讲到SVM在手写数字识别（MNIST数据集）上，错误率能做到百分之几，和当年的神经网络不相上下。在文本分类上更是大放异彩，新闻分类、垃圾邮件过滤，很长一段时间里工业界的标准方案就是SVM。某个很有名的连续剧里，男主角是个数学天才，剧里反复出现他在白板上画分隔超平面的镜头，倒也意外地贴近SVM这门手艺的气质。说到体育，网球里判断一记发球会不会出界，要是有球员历史发球的落点数据，做一个二分类，SVM往往比逻辑回归更扛得住特征多而样本少这种局面。

不过SVM也有它吃力的地方。最大的问题是训练慢，尤其是用核函数之后，复杂度往往随样本数平方甚至立方增长，几万样本还能扛，到了百万级别就明显力不从心了，这种规模的数据，工业上一般交给树模型（XGBoost、LightGBM、CatBoost那一族）或者神经网络去处理。SVM的另一个不便之处，是它直接给出的只是个分类结果，不像逻辑回归那样天然有概率解释，要拿概率得另外用Platt缩放这种后处理。

和逻辑回归对比一下，更能看清它的位置。逻辑回归靠对数损失训练，所有样本一起推参数，输出是概率，可解释性好，大规模数据下训练快，是工业界排序和分类的基础款。SVM靠铆定间隔训练，只关心支持向量，泛化稳，小样本高维更出彩，输出是到分界的距离而非概率。两者背后各有各的道理，没有谁绝对更好，看手头数据说话。我之前在一家做金融风控的小组里待过一阵，他们做欺诈检测，先用逻辑回归跑一个基线，再用RBF核SVM在小样本的欺诈子集上做精修，两套模型配合着用，效果比单独跑任何一个都好。

6.一个完整的小例子

最后我们用一个二维的小数据集把整条流程走一遍。假设有六个样本，正类三个，坐标分别是 $(1, 1)$、$(2, 1)$、$(2, 2)$，负类三个，坐标是 $(4, 4)$、$(5, 4)$、$(5, 5)$。先用线性核SVM试试。这六个点很明显在平面上能被一条斜着的直线分开，最大间隔直线大约落在正类那一团和负类那一团中间，离两边最近的几个点（也就是支持向量）大概是 $(2, 2)$ 和 $(4, 4)$ 这一带，间隔 $m$ 大约是 $2$ 到 $3$ 这个量级（约 $2\sqrt{2}$，和第2节 $m = \frac{2}{|w|}$ 的全宽定义一致）。这种数据线性可分，线性核就够用了，根本用不着升维。

可要是把样本换成异或那种排布，比如正类是 $(1, 1)$ 和 $(3, 3)$，负类是 $(1, 3)$ 和 $(3, 1)$，直线就彻底没辙了。这时候换成RBF核SVM，把 $\gamma$ 设在 $0.5$ 左右，$C$ 设在 $1$ 左右，决策边界会自动弯成两条贴合对角线的弧，把两个正类抱在中间，两个负类挡在外头。这就是核技巧在二维上的直观效果，无需我们手动加什么 $x_1^2$、$x_2^2$ 这种特征，RBF核自己就把这件事办了。

讲到这里，最大间隔、支持向量、软间隔、惩罚系数 $C$、核函数、RBF核的 $\gamma$，这一串SVM最核心的概念都串起来了。面试的时候被问到SVM，能把这条主线从头讲到尾，再把 $C$ 和 $\gamma$ 各自大一点小一点的后果说清楚，基本就能过关。要是再能补一句支持向量和逻辑回归在样本利用方式上的差别，那就是加分项了。说起来信息熵那一套我们在1.4 节聊过，它管的是决策树怎么挑分裂点，而SVM管的是分界线离两边有多远，两条路子虽然不同，但都把分类问题落到了一个清晰的数学目标上。

练习

Q1. SVM 为什么挑"离两边样本都最远"的那条分界线？支持向量在其中起什么作用？

间隔越大，分界线离两边样本越远，新来的点稍有扰动也不容易跨过去，泛化更稳。通常只有离分界线最近的少数几个样本撑起间隔的边界，它们就是支持向量，分界线的位置完全由这几个点决定，其余样本多一点少一点都不影响。这也解释了 SVM 在小样本上稳——它只认几个关键点，不被海量普通样本带偏。

Q2. 硬间隔 SVM 里间隔写成 $m=\frac{2}{|w|}$，请按"两个边界点到分界超平面的距离之和"把它推一遍。

取正好落在间隔边界上的正类点 $x_+$（满足 $w^\top x_+ + b=1$）和负类点 $x_-$（满足 $w^\top x_-+b=-1$）。一点到超平面 $w^\top x+b=0$ 的距离是 $\frac{|w^\top x+b|}{|w|}$，所以间隔全宽 $m=\frac{1}{|w|}+\frac{1}{|w|}=\frac{2}{|w|}$。要让 $m$ 最大等价于让 $|w|$ 最小，于是目标变成最小化 $\frac12|w|^2$。

Q3. 软间隔里惩罚系数 $C$ 设大设小分别会怎样？RBF 核的 $\gamma$ 呢？

$C$ 越大对越界罚得越狠，间隔越窄、容易过拟合；$C$ 越小越宽容，间隔越宽但可能欠拟合，常用值在 $0.01$ 到 $100$ 量级。$\gamma$ 越大核函数衰减越快，只有很近的样本才算关系密切，决策边界很弯曲、易过拟合；$\gamma$ 越小衰减慢、边界平滑、可能欠拟合。两者通常一起靠交叉验证调。

Q4.（面试题） 为什么 SVM 能用核技巧隐式映射到高维空间却不用真去算高维坐标？请从对偶形式说起。

SVM 的对偶问题和预测公式里，数据都只以样本内积 $x_i^\top x_j$ 的形式出现，单个样本的坐标不单独出现（KKT 互补松弛也说明只有支持向量的 $\alpha_i>0$ 起作用）。既然只用内积，我们就能定义一个核函数 $K(x_i,x_j)$ 直接返回两个样本在映射后高维空间里的内积，把公式里的 $x_i^\top x_j$ 全部替换掉，等于隐式地在高维空间求解，而根本不必显式算出那个高维（甚至无穷维）的坐标。合法性完全建立在"对偶只用内积"这条性质上。