支持向量机

机器学习 CS229

---

本文将会大量参考支持向量机通俗导论的$\LaTeX$版本，进行了简单的删减，需要进一步了解SVM可以参考原文。

前言

       支持向量机是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略便是间隔最大化，最终可转化成一个凸二次规划问题的求解。

相关概念

       在描述支持向量机的概念之前，我们需要引入几个简单的但却帮助我们思考的概念。

函数间隔与几何间隔

       在超平面$w^Tx + b = 0$确定时，我们可以通过$y(w^Tx + b)$来判断分类是否正确。这就引出了函数间隔的定义：

$$\bar\gamma = y(w^Tx + b) = yf(x)$$
       但是，采用函数间隔去衡量距离会受到系数$w$和$b$的影响，函数间隔大小会随着系数的增加而增加，所以采用函数间隔衡量距离并不是一种很好的选择。
       为了解决系数对距离的影响，我们可以采用归一化的方式，将它们都转换为单位向量就可以避免这种情况了，这就引入了几何间隔的概念：
$$\tilde\gamma = \frac{y(w^Tx + b)}{\parallel w \parallel} = \frac{yf(x)}{\parallel w \parallel} = \frac{\bar\gamma}{\parallel w \parallel}$$
       其实这就是在中学学过的点到直线距离的公式，就是最基本的欧式几何上的距离（不考虑正负）。

最大间隔分类器

       当对一个数据点进行分类，当超平面离数据点的几何间隔越大，分类的置信度就越高，所以我们希望能够选择一个可以最大化这一间隔的超平面（如下图所示）。

       因此，最大间隔分类器的目标函数可以定义为：

$$\hat\gamma = \max\tilde\gamma = \max\frac{y(w^Tx + b)}{\parallel w \parallel}$$
       实际上，这并不是一个很简洁的函数，我们可以增加一些简单的约束条件来减少我们在求解的时候需要付出的努力，我们可以简单的令函数间隔$\bar\gamma = 1$，那么则会有$\tilde \gamma = 1/\parallel w \parallel$，那么我们上述那个相对复杂的目标函数可以简化为：
$$\hat\gamma = \max\frac{1}{\parallel w \parallel} \\ s.t. y_i(w^Tx_i + b) \ge 1, i = 1,...,n$$
       原来的复杂的目标函数转化为了一个简单的目标函数和一个约束条件，而对于约束条件我们可以很容易的通过一些数学技巧来解决。

线性可分问题求解

       对于一个几何空间上的二分类问题，其情况也不外乎两种，线性可分以及线性不可分，对于线性可分的问题相对来说比较容易解决，所以我们下来介绍线性可分问题的求解方式。

拉格朗日对偶性

       我们继续考虑上述的目标函数，对于这种问题，我们可以通过拉格朗日对偶性进行求解。上述函数可以转换为拉格朗日函数：

$$L(w, b, \alpha) = \frac{1}{2}\parallel w \parallel ^2 - \sum_{i = 1}^{n}\alpha_i(y_i(w^Tx_i + b) - 1)$$
       然后令：
$$\theta_P(w) = \max_{\alpha_i \ge 0}L(w, b, \alpha)$$
       当某个约束条件未得到满足时，很显然会有$\theta_P(w) = + \infty$，那么显然会有$\theta_P(w) = \frac{1}{2}\parallel w \parallel ^2$，便是最初时希望最小化的值。所以我们的目标函数变为：
$$p^* = \min_{w, b} \theta(w) = \min_{w, b} \max_{\alpha_i \ge 0} L(w, b, \alpha)$$
       通过拉格朗日对偶性，我们可以得出：
$$p^* = \min_{w, b} \max_{\alpha_i \ge 0} L(w, b, \alpha) \\ \le \max_{\alpha_i \ge 0} \min_{w, b} L(w, b, \alpha) =\ d^*$$

KTT条件

       对于上式，我们希望找到等式成立的情况，对于下述模型：

$$\min f(x) \\ s.t. c_i(x) \le 0, i = 1, 2, ..., k \\ h_j(x) = 0, j = 1, 2, ..., l$$
       我们的$KTT$条件为：
$$\nabla_xL = 0 \\ h_j(x) = 0, j = 1, 2, ..., l \\ c_i(x) \le 0, i = 1, 2, ..., k \\ \alpha_i \ge 0, i = 1, 2, ..., k \\ \alpha_i c_i(x) = 0 , i = 1, 2, ..., k \\ $$
       关于这部分的内容，可以参考我之前的blog，在这里就不重复叙述了。

对偶问题求解过程

       对于对偶问题，我们在求解过程中，首先固定$\alpha$，然后让$L$关于$w$和$b$最小化，分别对$w$和$b$求偏导数：

$$\frac{\partial L}{\partial w} \implies w = \sum_{i = 1}^{n} \alpha_i y_i x_i$$
$$\frac{\partial L}{\partial b} \implies \sum_{i = 1}^{n} \alpha_i y_i = 0$$
       将上式带入到$L(w, b, \alpha)$中，则会有：

       最后，可以得到：
$$L(w, b, \alpha) = \sum_{i = 1}^{n}\alpha_i - \frac{1}{2}\sum_{i, j = 1}^{n}\alpha_i\alpha_jy_iy_jx_i^Tx_j$$
       此时，我们只剩余一个变量$\alpha$，我们现在需要的最优化问题转变成了：
$$\max_{\alpha} \left[ \sum_{i = 1}^{n}\alpha_i - \frac{1}{2}\sum_{i, j = 1}^{n}\alpha_i\alpha_jy_iy_jx_i^Tx_j\right] \\ s.t. \ \alpha_i \ge 0, i = 1, 2, ... , n \\ \sum_{i = 1}^{n}\alpha_iy_i = 0$$
       如果我们可以求出$\alpha_i$，从而我们可以确定$w$和$b$的值（不会b的推导，疑问为什么不把$b$变成$w_0$）：
$$w^* = \sum_{i = 1}^{n}\alpha_iy_ix_i$$
$$b^* = -\frac{\max_{i:y_i = -1}w^{*T}x_i + \min_{i:y_i = 1}w^{*T}x_i}{2}$$
       这样既可推导出$w$和$b$的值，从而确定最优超平面以及分类决策函数，至于$\alpha$如何去求解最优值，可以参考论文《Sequential Minimal Optimization：A Fast Algorithm for Training Support Vector Machines》，关于这篇论文中的内容，将会整理在之后的blog中。

线性不可分问题求解

       根据之前的推导我们得到了：

$$w^* = \sum_{i = 1}^{n}\alpha_iy_ix_i$$
       我们可以将其带入分类函数，那么会有：
$$f(x) = \left(\sum_{i = 1}^n \alpha_iy_ix_i\right)^Tx + b \\ = \sum_{i = 1}^{n}\alpha_iy_i\langle x_i,x \rangle + b$$
       上式中有一个有一个很关键的地方，在对于新的$x$预测时，我们只需要计算它与训练数据点的内积即可，这对于我们在使用核函数时有比较重要的意义。这里还有一个有意思的地方，实际上除了支持向量对应的点的系数$\alpha$不为零以外，其他的点对应的$\alpha$均为零，详细内容可以参见之前关于拉格朗日对偶性的博客。

核函数

       对于数据分布非线性的情况，SVM中采用的通常方法则是选择一个核函数$K(·, ·)$，通过将数据映射到高纬空间进行求解。在线性不可分的情况下，支持向量机首先在低维空间中完成计算，然后通过核函数将输入空间映射到高维特征空间，最终在高维空间中构建出最优分离超平面，从而把平面上无法线性分割的数据分隔开，如下图所示。

       在遇到核函数之前，我们需要一个非线性映射函数，将数据映射到特征空间，我们假设$\phi:\ \mathcal{X} \rightarrow \mathcal{F}$为非线性映射函数，那么我们的分类函数变为：

$$f(x) = w\phi(x) + b$$
       实际上，上述过程可以分为两步：

1. 使用非线性映射函数将数据变换到一个新的特征空间$\mathcal{F}$；
2. 在特征空间执行线性学习分类器

       与我们之前的知识相结合，那么决策规则可以表示为：

$$f(x) = \sum_{i = 1}^l \alpha_i y_i \langle \phi(x_i), \phi(x) \rangle + b$$
       但是，如果直接采用这种步骤进行求解是不合理的，假设我们有一个数据集如下：

       对于平面上的这个分布，很明显如果我们采用一个“圆”进行分类是十分合理，那么我们的分类函数可以写成：
$$a_1X_1 + a_2X_1^2 + a_3X_2 + a_4X_2^2 + a_5X_1X_2 + a_6 = 0$$
       这样，我们就可以将其映射到一个五维空间进行简单的求解，所以上式可以表示为：
$$\sum_{i = 1}^5a_iZ_i + a_6 = 0$$
       我们可以很容易的对新坐标$Z$进行线性分类，好像这也没什么问题。但是，如果原始空间是三维的，那么新空间是原始空间的一阶、二阶和三阶的全部组合，那么会得到一个19维的空间，这是一个指数级别的增长速度，这给$\phi(·)$的计算带来的极大的困难，如果遇到无穷维的情况也无法进行计算，所以这时就需要核函数$K(·, ·)$的帮助来完成非线性分类的问题。
       还是以上图为例，我们设两个点$x^{(1)} = (\eta_1, \eta_2)$和$x^{(2)} = (\zeta_1, \zeta_2)$，还是采用原来的$\phi(·)$映射到五维空间，那么映射以后的内积为：
$$\langle \phi(x^{(1)}), \phi(x^{(2)}) \rangle = \eta_1\zeta_1 + \eta_1^2\zeta_1^2 + \eta_2\zeta_2 + \eta_2^2\zeta_2^2 + \eta_1\zeta_1\eta_2\zeta_2$$
       另外，我们还可以注意到：
$$(\langle x^{(1)}, x^{(2)} \rangle + 1) ^2 = 2\eta_1\zeta_1 + \eta_1^2\zeta_1^2 + 2\eta_2\zeta_2 + \eta_2^2\zeta_2^2 + 2\eta_1\zeta_1\eta_2\zeta_2 + 1$$
       我们只需要对我们的映射进行一下简单的缩放，就可以得到（这里为了清晰就不采用$x_1$表示特征的方式了，这与前面的有一点冲突，有时间重新整理下）：
$$\phi(x^{(1)}) = (\sqrt 2 \eta_1, \eta_1^2, \sqrt 2 \eta_2, \eta_2^2, \sqrt 2 \eta_1\eta_2, 1)$$
       然后，我们可以发现$( \langle x^{(1)}, x^{(2)} \rangle + 1 ) ^2$与$\langle \phi(x^{(1)}), \phi(x^{(2)}) \rangle$是相等的，那么它们的区别在什么地方呢？

1. 映射到高维空间，然后根据内积公式进行计算；
2. 直接在低维空间进行计算，并不实际上计算高维空间的映射结果。

定义：核函数是一个函数$K$，对于多有的$x, z \in \mathcal{X}$，满足$K(x, z) = \langle \phi(x), \phi(z) \rangle$，这里$\phi$是从$\mathcal{X}$到内积特征空间$\mathcal{F}$的映射。

       根据上面的例子，我们的核函数为：

$$K(x^{(1)}, x^{(2)}) = ( \langle x^{(1)}, x^{(2)} \rangle + 1 ) ^2$$
       所以，我们的分类函数为：
$$f(x) = \sum_{i = 1}^l \alpha_i y_i K(x_i, x) + b$$
       同样，我们的目标函数也进行了转换，避免了直接在高维空间中进行运算，它们产生的结果是等价的。

常见的核函数类型

       通常人们会根据问题和数据的不同，选择不同的参数，从一些常用的核函数中选择一些核函数，下面介绍最常见的三种核函数：

• 多项式核函数$K(x_1,x_2) = ( \langle x_1, x_2 \rangle + R ) ^d$：这个核函数对应的映射空间维度是可以求导出来的，该空间维度为$C_{d + m}^d$，其中$m$表示原始空间的维度，也就是所谓$x$的特征数目。我们之前选择的核函数则是多项式核函数的特例$(R = 1, d = 2)$，而$C_4^2 = 6$，与我们之后采用的非线性映射函数的映射结果是一致的。
• 高斯核函数$K(x_1,x_2) = exp(- \parallel x_1 - x_2 \parallel ^2 / 2\sigma^2)$：该核函数就是前面提及到的，会将原始空间映射到无穷维度空间的映射函数，如下图所示。不过需要提及的是，如果$\sigma$选择的很大的话，高次特征的权重实际上是衰减的非常快的，所以在数值上近似于一个低维子空间，反之，如果$\sigma$选择的很小的话，那么可以将任意数据映射为线性可分的空间，当然这也会导致很严重的过拟合问题。不过，总而言之，通过合理的调节参数$\sigma$，高斯核函数实际上具有很高的灵活性，也是最常用的核函数之一。

• 线性核函数$K(x_1,x_2) = \langle x_1, x_2 \rangle$：这个核函数实际上就是原始空间的内积。这个函数实际上就是可以同意一下书写形式，其他的意义应该并不是很大了。

  

       我们在之前列举了一些常见的核函数，但是核函数的存在性应该如何判断呢？核函数应该如何构造呢？在实际使用中，我们并不会关心高维空间的映射情况，那么我们应该如何判断一个函数是否是核函数呢？

$\mathcal{Mercer}$定理：任何半正定的函数都可以作为核函数。所谓半正定函数$f(x_i, x_j)$，是指拥有训练数据集合$(x_1, x_2, ... , x_n)$，我们定义一个矩阵，其中的元素$a_{ij} = f(x_i, x_j)$，很显然，这个矩阵是一个$n \times n$矩阵，只要这个矩阵是半正定矩阵，那么我们就可以将函数$f(x_i, x_j)$是半正定函数。

       需要注意的是，$\mathcal{Mercer}$定理只是一个充分条件，某些不满足$\mathcal{Mercer}$定理的函数也可能可以作为核函数。
       总而言之，如果我们采用了合适的核函数，那么理论上讲，我们就可以将在原始空间线性不可分的数据可分，这样我们就可以实现对线性不可分数据的分割。

松弛处理

       在之前我们讨论线性不可分的情况，只要使用高斯核函数实际上无论什么样的数据都是可分的，如果数据本身是线性可分的，但是存在一定的噪声，如下图可视，如果我们通过将之映射到无限维使其被线性可分，那么就会会造成严重的过拟合现象，所以我们可能需要其他的处理方法。

       对于这些偏离正常位置很远的点，我们称之为outlier，在目前为止的SVM模型中是会造成极大影响的。正如前文所述，超平面是由少数的支持向量构成的，如果这些向量中存在outlier，如上右图，那就会对超平面产生极大影响了。如果新增的点位于右上角，那就更恐怖了，整个数据并不再满足线性可分了，只能映射到高维空间进行求解。
       为了处理这类情况，SVM允许数据点适当的偏离超平面，这样少数噪音就不会对超平面产生太大的影响了。那么现在我们的约束条件发生了小小的变化：

$$y_i(w^Tx_i + b) \ge 1 - \zeta_i, i = 1, ..., n$$
       其中$\zeta_i$称为松弛变量，也就是对应的数据点可以偏离的量。增加了松弛变量以后，我们的目标函数也要进行相应的改变：
$$\min \frac{1}{2} \parallel w \parallel + C\sum_{i = 1}^n\zeta_i$$
       其中，$C$是一个常数，用于控制目标函数中的两项之间的权重。所以，现在我们的问题变为了：
$$\min \frac{1}{2} \parallel w \parallel + C\sum_{i = 1}^n\zeta_i \\ s.t. \ y_i(w^Tx_i + b) \ge 1 - \zeta_i, i = 1, ..., n \\ \zeta_i \ge 0, i = 1, ..., n$$
       分析方式还是与原来相同，我们可以得到新的拉格朗日函数：
$$L(w, b, \zeta, \alpha, r) = \frac{1}{2}\parallel w \parallel ^2 + C\sum_{i = 1}^n\zeta_i - \sum_{i = 1}^{n}\alpha_i(y_i(w^Tx_i + b) - 1 + \zeta_i) - \sum_{i = 1}^n r_i \zeta_i$$
       $L$分别对$w$、$b$和$\zeta$求偏导数，可以得到：
$$w = \sum_{i = 1}^{n} \alpha_i y_i x_i \\ \sum_{i = 1}^{n} \alpha_i y_i = 0 \\ C - \alpha_i - r_i = 0$$
       将上述条件带入$L$中进行化简，很容易得到和原来一样的目标函数：
$$L(w, b, \alpha) = \sum_{i = 1}^{n}\alpha_i - \frac{1}{2}\sum_{i, j = 1}^{n}\alpha_i\alpha_jy_iy_jx_i^Tx_j$$
       只不过我们现在的条件发生了一点小小的改变，现在我们有$C - \alpha_i - r_i = 0$，同时又有$r_i \ge 0$，因此可以很显然的知道会有$\alpha_i \le C$，所以现在整个对偶问题可以写作：
$$L(w, b, \alpha) = \sum_{i = 1}^{n}\alpha_i - \frac{1}{2}\sum_{i, j = 1}^{n}\alpha_i\alpha_jy_iy_jx_i^Tx_j \\ s.t. \ 0 \le \alpha_i \le C, i = 1, ..., n \\ \sum_{i = 1}^{n} \alpha_i y_i = 0$$
       对于这个函数也可以通过SMO算法进行求解，关于SMO算法的内容会在以后的blog中进行。

总结

       SVM是一个十分重要的分类方法，它与感知机相似但不相同。对于这个算法还需要进一步的研究与学习。

参考
支持向量机通俗导论