LionKing数据科学专栏

购买普通会员高级会员可以解锁网站精华内容且享受VIP服务的优惠

想要查看更多数据科学相关的内容请关注我们的微信公众号知乎专栏

支持向量机(support vector machine)原理及算法实现

支持向量机的原理

支持向量机是一个适合二分类问题的模型。其思路是寻找一个超平面$\{w^Tx + b = 0\}$将空间分成两部分,其中一部分包含正例,另一部分包含负例。希望正例和负例到超平面的距离尽可能地远。

若数据线性可分,即存在一个超平面将正负例分在了其两侧,则我们希望找到这样的超平面中使得样本点到超平面的最小距离最大的那个超平面。

方便起见,假设$y^{(i)} = 1$表示样本$x^{(i)}$为正例,否则$y^{(i)} = -1$。

该问题可以化作一个凸优化问题:

$$\min\|w\|_2^2$$

s.t.$y^{(i)}[w^Tx^{(i)} + b] \geqslant 1$

需要购买普通会员高级会员登录后刷新该页面查看

若数据未必线性可分,则上述问题没有可行解。

此时引入一些松弛变量$\xi_1, \ldots, \xi_n \geqslant 0$,用来放宽$$y^{(i)}[w^Tx^{(i)} + b] \geqslant 1$$的限制:

$$y^{(i)}[w^Tx^{(i)} + b] \geqslant1 - \xi_i$$

引入松弛变量后原问题一定可解。我们希望松弛变量尽可能不要太大,从而数据尽可能地可以被$\{w^Tx + b = 0\}$分开。

将目标函数由$\|w\|_2^2$改为$$\frac{1}{2}\|w\|_2^2 + C\sum_{i=1}^{n}\xi_i$$

其中$C \gt 0$为超参数。

不加入松弛变量的问题被称为硬间隔最大化(hard-margin maximization),加入松弛变量的问题被称为软间隔最大化(soft-margin maximization)。

该问题的对偶问题是一个二次规划(quadratic programming)问题,其形式如下:

$$\min_{\alpha}\frac{1}{2}\sum_{1 \leqslant i, j \leqslant n}\alpha_i\alpha_jy^{(i)}y^{(j)}x^{(i)T}x^{(j)} - \sum_{i=1}^{n}\alpha_i$$

s.t.$$\sum_{i=1}^{n}\alpha_iy^{(i)} = 0, 0 \leqslant \alpha_i \leqslant C$$

可以使用SMO算法求解该问题,大概思路是每次固定$n - 2$个变量,并对剩下两个变量求解最优,反复迭代。固定其余变量时,相当于对一个带限制的单变量二次函数进行最小化,是一个很简单的问题。

算法

核函数(Kernel trick)

如果数据不适合使用线性分类器,则我们可以试图进行一些特征的变换,例如引入二次项和交叉项使得数据线性可分。

即我们将$x^{(i)}$变换为$\phi(x^{(i)}) \in \mathbb{R}^{q}$然后重复上述线性SVM的过程。

当特征变换的维数$q$不大时,这样做并没有什么问题,然而如果$q \gg n$,此时计算$\phi(x^{(i)})^T\phi(x^{(j)})$的时间复杂度较高。有时甚至我们需要$q$取正无穷。

为了克服这一问题,我们引入核函数$K$:

$$K(x, x') = \phi(x)^T\phi(x')$$

只要核函数满足一些技术条件,则存在映射$\phi$对应该核函数。

常见的核函数包括:

使用核函数后,只需要将原来的对偶问题中的$x^{(i)T}x^{(j)}$替换为$K(x^{(i)}, x^{(j)})$即可解得$\alpha$。

在预测阶段,我们需要计算$$w^T\phi(x) = \sum_{i=1}^{n}\alpha_iy^{(i)}\phi(x^{(i)})^T\phi(x) + b = \sum_{i=1}^{n}\alpha_iy^{(i)}K(x^{(i)}, x) + b$$

合页损失函数

SVM的另一种理解是最小化数据的合页损失(hinge loss)

考虑$L(y, \hat{y}) = \begin{cases} 0 & \text{如果}y\hat{y} \geqslant 1\\ 1 - y\hat{y} & \text{如果}y\hat{y} \lt 1 \end{cases}$

我们可以将SVM的优化问题重写为

$$\min_{w, b}\sum_{i=1}^{n}[1 - y^{(i)}(w^Tx^{(i)} + b)]_+ + \frac{1}{2C}\|w\|_2^2$$

$$\min_{w, b}\sum_{i=1}^{n}L(y^{(i)}, w^Tx^{(i)} + b) + \frac{1}{2C}\|w\|_2^2$$

对比错误样本个数对应0-1损失

$$L(y, \hat{y}) = \begin{cases} 0 & \text{如果}y\hat{y} \geqslant 0\\ 1 & \text{如果}y\hat{y} \lt 0 \end{cases}$$

逻辑回归对应对数损失

$$L(y, \hat{y}) = \log{\left[1 + \exp{(-y\hat{y})}\right]}$$

下图显示了各个损失函数的对比

Python实现

需要购买普通会员高级会员登录后刷新该页面查看

训练数据和支持向量机模型的决策边界(decision boundary)如下:

常见面试问题

Q:支持向量机有哪些优缺点?

需要购买普通会员高级会员登录后刷新该页面查看

Q:简述核函数原理。

需要购买普通会员高级会员登录后刷新该页面查看

Q:核函数有什么要求?

需要购买普通会员高级会员登录后刷新该页面查看

Q:对比逻辑回归和SVM。

需要购买普通会员高级会员登录后刷新该页面查看

Q:支持向量是什么?

需要购买普通会员高级会员登录后刷新该页面查看

Q:如何理解超参数$C$?

需要购买普通会员高级会员登录后刷新该页面查看

更多机器学习相关问题见本网站论坛机器学习理论版面机器学习实践版面

更多面试问题见面试真题汇总

想要查看更多数据科学相关的内容请关注我们的微信公众号知乎专栏