机器学习笔记：支持向量机SVM基本原理

最原始的SVM是一个线性二分类器，它的根本目的是寻找一个可以将训练样本划分开的高维空间内的超平面。很明显，这种超平面有很多，但是哪一个是最好的呢？

评价作为边界的超平面优秀与否的判据是：这个超平面是否能产生鲁棒性最强的分类结果，泛化能力最强。

因此，在众多能划分开训练样本的超平面中，我们认为，距离各样本尽可能“远”^1的那个超平面是最好的分界超平面，我们要找到这个尽可能远的距离的表达式并优化它。这个超平面可由它所划分的两类训练样本中距离该平面最近的几个样本所确定，因此这几个样本得名支持向量（Support Vector），它们“支持”了分类超平面。

如何确定SVM的分类超平面

决策边界：最佳的分类超平面

怎么找到最佳的分类超平面呢？首先，我们列出要得到的超平面的几条性质，然后我们使用这些性质构建出超平面满足的约束关系，从而得到超平面。

分类超平面的性质：

• 它是一个超平面，可以用线性组合表示
• 它距离它所划分的两类训练样本中支持向量的距离一样远
• 它距离它所划分的两类训练样本中的支持向量尽可能远

于是我们可以得出关于超平面的约束如下，首先要满足是个平面，一般我们称其为“决策边界”(Decision Boundary)：
$$DB: \mathbf{w}^T\mathbf{x} + b = 0$$

上式中，$\mathbf{w}$为权重向量（SVM中我们要优化的目标），$\mathbf{x}$为训练样本的输入向量，b为偏差值。满足上式描述的输入向量$\mathbf{x}$全部存在于以$\mathbf{w}$为唯一参数决定的超平面上。

我们要衡量训练样本到超平面的距离，使用点到超平面距离公式描述任意一个训练样本（我们使用编号i表示这个样本）到超平面的距离：
$$d_i = \frac{|\mathbf{w}^T\mathbf{x}_i+b|}{||\mathbf{w}||}$$

注意上式中$\mathbf{x}_i$表示第i个训练样本的输入向量。

间隔和最大间隔假设

要继续推导SVM的原理，还要明确两个概念：间隔和最大间隔假设。

上文提到，决策边界要离支持向量尽可能远，且两类的支持向量距离决策边界距离相等，这说明被分类的两类支持向量分别存在于两个平行于决策边界的超平面上，它们距决策边界的距离相同。于是，决策边界和两个由支持向量构成的超平面划分出了一个不存在训练样本的区域，这个区域的大小称为“间隔”（Margin），我们用$\gamma$表示它。

由于决策边界和两个支持向量超平面距离相同，确定一个支持向量超平面距离决策边界的距离乘以二即可得到$\gamma$。可是，根据不同的训练样本情况，一个支持向量超平面和决策边界的距离似乎可以是任意实数c，这为$\gamma$的确定引入了新的未知量c。

不过，可以证明[^2]无论c取多少，都可以通过缩放变换将其变为1，这就为确定$\gamma$提供了计算上的方便。

[^2]: 如果没记错，AndrewNg在他的机器学习讲义中证明了，此处不赘述。（实际上是我忘了2333）

c取1，也就是说我们确定了两个由支持向量确定的超平面，它们刻画了训练样本的正确分类：
$$\begin{cases}
\mathbf{w}^T\mathbf{x}+ + b \ge 1,\space{} y+ = 1 \
\mathbf{w}^T\mathbf{x}- + b \le 1,\space{} y- = -1
\end{cases}$$

上式中，训练样本分为正类和负类，正确分类时，正类结果为1，负类结果为-1，支持向量所在平面即为取等号是对应的两个超平面。上式即为“最大间隔假设”。

还记得我们最开始的目的吗？让决策边界离训练样本尽可能远，现在我们有了$\gamma$来衡量“远近”，因此我们目的就是使$\gamma$尽可能大。上文提到了点到超平面距离，我们将其用在支持向量上，于是我们得到间隔的表达式：
$$\gamma = \frac{2}{||\mathbf{w}||}$$

可喜可贺，至此我们已经得到了要优化的表达式了！

如何优化$\gamma$

SVM的构建至此已经基本完成，剩下的就是数学上的处理了。

整理一下我们推导出的结论，我们目前要做的是：
$$\begin{gathered}\max_{\mathbf{w}, b} \frac{2}{||\mathbf{w}||} \
s.t.\space{} y_i(\mathbf{w}^T\mathbf{x}_i+b) \ge 1, \space{} i = 1,2,…n
\end{gathered}$$

其中，第二个式子是最大间隔假设的两个式子的合在一起写的形式。下标i表示第i个样本，我们假设一共n个样本，因此一共有n条限制条件，其含义为全部n个样本全部被正确分类。

很明显，我们需要尽量使第一个式子的分母小，为了优化方便，我们考虑优化下面等价的式子，SVM的本质就是这两个式子：
$$\begin{gathered}\min_{\mathbf{w}, b} \frac{1}{2} ||\mathbf{w}||^2 \
s.t.\space{}y_i(\mathbf{w}^T\mathbf{x}_i+b) \ge 1, \space{} i = 1,2,…n
\end{gathered}$$

怎么优化呢？乍一看，这是个凸二次规划问题，是有固定解法的，不过对于SVM还有更高效的解法。对于所有约束条件优化问题，我们可以使用SMO算法进行优化^3，这点让我们当做这篇文章的题外话吧。

对偶问题

上述待优化的问题可以转换成对偶问题求解，使原函数尽可能小的对偶问题是使得对偶的函数（拉格朗日函数）尽可能大。构建拉格朗日函数：
$$L(\mathbf{w}, b, \mathbf{\alpha}) = \frac{1}{2} ||\mathbf{w}||^2 + \sum_{i=1}^{n}\alpha_i(1-y_i(\mathbf{w}^T\mathbf{x}_i+b))$$

将$L$对$\mathbf{w}$和$b$求偏导数，并令偏导数等于零，对于每一个分量：
$$\begin{aligned}
\frac{\partial{L}}{\partial{w_j}} &= w_j - \alpha_iy_ix_i^{(j)} = 0 \
\frac{\partial{L}}{\partial{b}} &= \alpha_iy_i = 0
\end{aligned}$$

写成向量表示：
$$\begin{aligned}
\mathbf{w} &= \sum_{i=1}^n\alpha_iy_i\mathbf{x}i \
0 &= \sum{i=1}^n\alpha_iy_i
\end{aligned}$$

将上述两式代回$L$，消去$\mathbf{w}$和$b$，得到：
$$L = \sum_{i=1}^n\alpha_i - \frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j\mathbf{x}_i^T\mathbf{x}_j, \space{} \alpha_i \ge 0$$

接下来我们要做的就是求使得$L$最大化的$\mathbf{\alpha_i}$，进而可得$\mathbf{w}$和$b$，此处就用到参考中的SMO算法。

再进一步

我们已经推导得出基本的线性可分二分类硬间隔SVM的数学表达了，接下来我们来看看怎么让这个模型更加贴近实用，我们还需要补充一些内容。

核函数（Kernel Function）

核函数的引入帮助我们将SVM从只支持线性可分拓展到支持线性不可分。

对非线性可分问题，我们将原特征空间中线性不可分的样本点通过某类映射$\phi(\cdot)$映射到高维特征空间中，在这个特征空间中它们是线性可分的。之前的推导中需要计算特征向量的内积$\mathbf{x}_i^T\mathbf{x}_j$，经过映射后对应高维特征向量也需要计算内积$\phi(\mathbf{x}_i)^T\phi(\mathbf{x}_j)$，可是因为向量维数增多，直接计算高维向量内积很困难，于是我们构想一个函数$\kappa(\cdot, \cdot)$使其能在原始特征空间中使用原始特征向量直接计算高维特征向量内积的结果，即$\kappa(\mathbf x_i, \mathbf x_j) = \phi(\mathbf{x}_i)^T\phi(\mathbf{x}_j)$这种函数$\kappa$称作核函数，是一种隐式映射，起到升维的作用。

将核函数加入到SVM表达式中，得到：

$$
L = \sum_{i=1}^n\alpha_i - \frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j \kappa\left(\mathbf x_i, \mathbf x_j \right), \space{} \alpha_i \ge 0
$$

同样用SMO去求$\alpha_i$即可。

哪些函数可以作核函数？

核函数种类有很多，可以用作核函数的映射需要遵循一定的性质：核矩阵半正定。核矩阵定义在训练样本集合$\mathbf D = {\mathbf x_1, \mathbf x_2, \dots, \mathbf x_m}$上，即：

$$
\mathbf D = \begin{bmatrix}
\kappa(\mathbf x_1, \mathbf x_1) & \cdots & \kappa(\mathbf x_1, \mathbf x_m) \
\vdots & \ddots & \vdots \
\kappa(\mathbf x_m, \mathbf x_1) & \cdots & \kappa(\mathbf x_m, \mathbf x_m)
\end{bmatrix}
$$

上述矩阵半正定。同时还要求$\kappa$满足对称性，即：

$$
\kappa(\mathbf x_i, \mathbf x_j) = \kappa(\mathbf x_j, \mathbf x_i)
$$

举几个例子：

• 高斯核：$\kappa(\mathbf x, \mathbf y) = \exp{\left(-\frac{||\mathbf x - \mathbf y||^2}{2\sigma^2}\right)}$，$\sigma>0$，称带宽（非叫方差也无所谓，反正表示一个范围的大小）
• 多项式核：$\kappa(\mathbf x, \mathbf y) = \left(\mathbf x^T \mathbf y\right)^d$， $d$为多项式次数

软间隔

核函数似乎已经解决了线性不可分问题，实际上在真实环境下，只用核函数可能会导致过拟合的问题，因此我们要向SVM中加入正则项进行泛化，这样才能尽可能表达数据的真实分布情况，而非仅拟合出学习样本数据的分布，这种思想下SVM的决策平面称为软间隔。

“软间隔”正则化可以被我们表示为不满足SVM约束条件：
$$
y_i(\mathbf{w}^T\mathbf{x}_i+b) \ge 1
$$

于是我们将优化目标修改为：
$$
\min_{\mathbf{w},b}\frac{1}{2}||\mathbf{w}||^2+C\sum_{i=1}^nloss(y_i(\mathbf{w}^T\mathbf{x}_i+b)-1)
$$

$C > 0$，在这里是一个超参数，用来调节软间隔添加的强度。

我们使用$loss(\cdot)$决定“错误”判断的样本点，根据这个函数的不同选择，我们可以得到不同的SVM。使用对率损失函数$l_{log}=log(1+e^{-z})$可以得到多分类SVM的雏形。如果只考虑二分类，更多使用hinge损失函数$l_{hinge}=\max{(0, 1-z)}$。

使用hinge损失函数的情况中，我们一般将损失函数的每一项记作松弛变量$\xi_i$，因此优化目标写为：
$$
\min_{\mathbf{w},b}\frac{1}{2}||\mathbf{w}||^2+C\sum_{i=1}^n\xi_i
$$

$$
\xi_i = \max{\left(0, 1-y_i(\mathbf{w}^T\mathbf{x}_i+b)\right )}
$$

接下来和前面的推导一样，转换为对偶问题求参数即可。