多类支持向量机损失（SVM）

Description

支持向量机（Support Vector Machine）是一种二类分类模型。 它的基本模型是定义在特征空间上的间隔最大的线性分类器。 它是最好的 “off-the-shelf” 监督学习算法。

问题假设

假设给定一个特征空间上的训练数据集

$$T=(x_1,y_1),(x_2,y_2),\cdots ,(x_N,y_N)$$

其中， $x_i\in \mathcal{X}={\mathbf{R}}^n$ ， $y_i\in \mathcal{Y}=+1,-1,i=1,2,\cdots ,N$ 。 $x_i$ 表示第 $i$ 个实例， $y_i$ 是 $x_i$ 的类标记。 当 $y=+1$ 时，称 $x_i$ 为正例；当 $y=-1$ 时，称 $x_i$ 为负例。 $(x_i,y_1)$ 称为样本点。 假设训练数据集是线性可分的。

我们的目标是在特征空间中找到一个分离超平面（Separating Hyperplane），能将实例分到不同的类。 分离超平面 $w\dot{x}+b=0$ ，由法向量 $w$ 和截距 $b$ 决定。

一般的，当训练数据集是线性可分时，存在无穷个分离超平面可将两类数据分离开。 线性可分支持向量机利用间隔最大化求最优分离超平面，这时的解是唯一的。

函数间隔和几何间隔

函数间隔

在上图中，有 $A,B,C$ 三个点，表示三个实例，均在分离超平面的正类一侧。 点 $A$ 距分离超平面较远，若预测该点为正类，就比较确定预测是正确的； 点 $C$ 距分离超平面较近，则预测该点确信为正类就不那么自信。

一般来说，一个点距离分离超平面的远近可以表示分类预测的确定程度。 在超平面 $w\cdot x+b=0$ 确定的情况下， $|w\cdot x+b|$ 能够相对的表示点 $x$ 距离超平面的远近。 而 $w\cdot x+b$ 的符号可以表示预测的准确性，因此我们使用 $y(w\cdot x+b)$ 来表示分类的 准确性和确信度。这就是函数间隔（Functional Margin）。

对于给定的训练数据集 $T$ 和超平面 $(w,b)$ ，定义超平面关于样本点 $(x_i,y_i)$ 的函数间隔为

$${\hat{\gamma }}_i=y_i(w\cdot x+b)$$

定义超平面 $(w,b)$ 关于训练数据集 $T$ 中的函数间隔为超平面关于 $T$ 中所有样本点的函数间隔的最小值，即

$$\hat{\gamma }=\underset{i=1,\cdots ,N}{\min }{\hat{\gamma }}_i$$

虽然函数间隔可以表示分类预测的正确性及确定度，但是选择分离超平面时，只有函数间隔还不够。 只要成比例的改变 $w$ 和 $b$ ，例如将他们改成 $2w$ 和 $2b$ ， 分离超平面没有发生变化，但它们的函数间隔却成了原来的两倍。 这个事实启示我们，如果对函数变量加以约束，使函数间隔变成确定的，这样就可以找到最佳的分离超平面。

几何间隔

可知， $w/||w||$ 是在 $w$ 方向上的单位向量。 假设 $A$ 表示 $x_i$ ， ${\gamma }_i$ 表示几何间隔，那么 $B$ 可以表示为 $x_i-{\gamma }_i\cdot w/||w||$ 。 $B$ 点在超平面上，满足超平面方程

$$w^T(x_i-{\gamma }_i\frac{w}{||w||})+b=0$$

求解得：

$${\gamma }_i=\frac{w}{||w||}\cdot x_i+\frac{b}{||w||}$$

由于 $A$ 在超平面上方，所以其几何间隔为正，因此，更一般的， 当样本 $(x_i,y_i)$ 被正确分类时，点 $x_i$ 与超平面的几何距离为

$${\gamma }_i=y_i(\frac{w}{||w||}\cdot x_i+\frac{b}{||w||})$$

定义超平面 $(w,b)$ 关于训练数据集 $T$ 的几何间隔为超平面关于 $T$ 中所有样本点的几何间隔的最小值，即

$$\gamma =\underset{i=1,\cdots ,N}{\min }{\gamma }_i$$

从上面的分析可以看出，函数间隔和几何间隔之间的关系为：

$${\gamma }_i=\frac{{\hat{\gamma }}_i}{||w||}$$

硬间隔最大化

对线性可分的训练数据集而言，线性可分分离超平面有无穷多个， 但是几何间隔最大的分离超平面是唯一的。 间隔最大化的最直观解释是，对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。 也就是说，对于最难分的实例点（距离超平面最近的点）也有足够大的确定度将它们分开， 这样的超平面对未知的实例具有很好的分类预测能力。

下面我们的问题就转换为了：如何求一个最大间隔分离超平面。 可以表示为下面的约束最优化问题：

\begin{aligned} \max_{w,b}\quad & \gamma \\ s.t. \quad & y_{i}\left(\frac{w}{||w||}\cdot x_i+ \frac{b}{||w||}\right)\geq\gamma,i=1,\cdots,N \end{aligned}

考虑几何间隔和函数间隔的关系，

\begin{aligned} \max_{w,b}\quad & \frac{\hat{\gamma}}{||w||} \\ s.t.\quad & y_{i}(w\cdot x_i+b)\geq\hat{\gamma},i=1,2,\cdots,N \end{aligned}

又因为函数间隔 $\hat{\gamma }$ 的改变对不等式约束没有影响，对目标函数的优化也没有影响， 我们令 $\hat{\gamma }=1$ ，这样最优化问题就转换成了：

\begin{aligned} \min_{w,b}\quad & \frac{1}{2}||w||^2 \\ s.t.\quad & y_{i}(w\cdot x_{i}+b)-1\geq 0,i=1,2\cdots,N \end{aligned}

这个最优化问题我们称为原始最优化问题。 这是一个凸二次规划问题。

支持向量和间隔边界

在线性可分的情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量（Support Vector）。

线性可分支持向量机的对偶算法

为了求解线性可分支持向量机的最优化问题，将它作为原始最优化问题，应用拉格朗日对偶性，通过求解对偶问题 得到原始问题的最优解，这就是线性可分支持向量机的对偶算法。 这样做的优点，一是对偶问题往往更容易求解；二是自然引入核函数，进而推广到非线性分类问题。

构建拉格朗日函数，对每个约束引入拉格朗日乘子 ${\alpha }_i\ge 0,i=1,2,\cdots ,N$ 。 定义拉格朗日函数得：

$$L(w,b,\alpha )=\frac{1}{2}||w|{|}^2-\sum _{i=1}^N{\alpha }_i{y}_i(w\cdot x_i+b)+\sum _{i=1}^N{\alpha }_i$$

其中， $\alpha =({\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_N{)}^T$ 为拉格朗日乘子向量。

原始问题的对偶问题是极大极小问题：

$$\underset{\alpha }{\max }\underset{w,b}{\min }L(w,b,\alpha )$$

我们需要先求 $L$ 关于 $w,b$ 的极小，再求对 $\alpha$ 的极大。

1. 求 ${\min }_{w,b}L(w,b,\alpha )$

   将拉格朗日函数 $L(w,b,\alpha )$ 分别对 $w,b$ 求偏导数并令其等于 0。

   \begin{aligned} \nabla_{w}L(w,b,\alpha)&=w-\sum_{i=1}^{N}\alpha_{i}y_{i}x_{i}=0 \\ \nabla_{b}L(w,b,\alpha)&=-\sum_{i=1}^{N}\alpha_iy_i=0 \end{aligned}

   得：

   \begin{aligned} w&=\sum_{i=1}^{N}\alpha_{i}y_{i}x_{i} \\ \sum_{i=1}^{N}\alpha_iy_i&=0 \end{aligned}

   代入 $L$ 中得：

   $$L(w,b,\alpha )=\sum _{i=1}^N{\alpha }_i-\frac{1}{2}\sum _{i,j=1}^n{y}_i{y}_j{\alpha }_i{\alpha }_j(x_i\cdot x_j)$$

2. 求 ${\max }_{\alpha }{\min }_{w,b}L(w,b,\alpha )$

   我们的问题变成了

   \begin{aligned} \max_{\alpha}\quad &\sum_{i=1}^{N}\alpha_{i}-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_{i}\alpha_{j}y_iy_j(x_{i}\cdot x_{j}) \\ s.t.\quad &\sum_{i}^{N}\alpha_{i}y_i=0 \end{aligned}

   考虑原始优化问题和对偶最优化问题，原始问题满足定理的条件， 所以存在 $w^{\text{*}},{\alpha }^{\text{*}},{\beta }^{\text{*}}$ ，使 $w^{\text{*}}$ 是原始问题的解， ${\alpha }^{\text{*}},{\beta }^{\text{*}}$ 为对偶问题的解，这意味着求解原始问题可以转换为求解对偶问题。

假设上述优化问题的最优解为 ${\alpha }^{\text{*}}=({\alpha }_1^{\text{*}},{\alpha }_2^{\text{*}},\cdots ,{\alpha }_N^{\text{*}})$ 。 根据拉格朗日对偶定理，KKT 条件成立，即：

\begin{aligned} \nabla_{w}L(w^*,b^*,\alpha^*)&=w^*-\sum_{i=1}^{N}\alpha_{i}^{N}y_ix_i=0 \\ \nabla_{b}L(w^*,b^*,\alpha^*)&=-\sum_{i=1}^{N}\alpha_{i}^*y_i=0 \\ \alpha_i^*(y_i(w^*\cdot x_i+b^*)-1)&=0 \\ y_i(w^*\cdot x_i+b^*)-1&\geq0 \\ \alpha_i&\geq0 \end{aligned}

得

$$w^{\text{*}}=\sum _i{\alpha }_i^{\text{*}}{y}_i{x}_i$$

其中至少有一个 ${\alpha }_j^{\text{*}}>0$ ，对此 $j$ ：

$$y_i(w^{\text{*}}\cdot x_j+b^{\text{*}})-1=0$$

解得：

$$b^{\text{*}}=y_j-\sum _{i=1}^N{\alpha }_i^{\text{*}}{y}_i(x_i\cdot x_j)$$

这样我们就得到了分离超平面和分离决策函数。 可见，分离决策函数只依赖于输入 $x$ 和训练样本输入的内积。

线性支持向量机（不可分）和软间隔最大化

如果训练数据不是线性可分的呢？

通常情况下，训练数据中有一些特异点，将这些特异点去除后，剩下大部分的样本点组成的集合是线性可分的。

线性不可分通常意味着某些样本点不能满足函数间隔大于等于 1 的约束条件。 为了解决这个问题，可以对每个样本点 $(x_i,y_i)$ 引入一个松弛变量 ${\xi }_i\ge 0$ ， 使函数间隔加上松弛变量大于等于 1。这样，约束条件变为：

$$y_i(w\cdot x_i+b)\ge 1-{\xi }_i$$

同时，对每个松弛变量 ${\xi }_i$ ，支付一个代价。目标函数由原来的 $\frac{1}{2}||w|{|}^2$ 变成：

$$\frac{1}{2}||w|{|}^2+C\sum _{i=1}^N{\xi }_i$$

其中， $C>0$ 作为惩罚参数。 这里的目标函数可以表示：使 $\frac{1}{2}||w|{|}^2$ 尽可能小，即间隔尽可能大； 同时使 ${\xi }_i$ 尽可能小，即误分类点的个数尽可能小。 这里的 ${\xi }_i$ 其实就是合页损失函数。 区别于之前的硬间隔最大化算法，数据集线性不可分的学习问题的解决方法被称为软间隔最大化。

我们的原始问题为：

\begin{aligned} \min_{w,b,\xi} \quad &\frac{1}{2}||w||^2+C\sum_{i=1}^{N}\xi_i \\ s.t. \quad & y_{i}(w\cdot x_i + b)\geq 1-\xi_i, \quad i=1,2,\cdots,N \\ & \xi_i \geq 0 \quad i=1,2,\cdots,N \end{aligned}

原始问题是一个凸二次规划问题，因而关于 $(w,b,\xi )$ 的解是存在的，可以证明 $w$ 的解是唯一的， 但 $b$ 的解可能不唯一，而是存在一个区间。

拉格朗日对偶求解原始问题

原始问题的拉格朗日函数是：

$$L(w,b,\xi ,\alpha ,\mu )=\frac{1}{2}||w|{|}^2+C\sum _{i=1}^N{\xi }_i-\sum _{i=1}^N{\alpha }_i(y_i(w\cdot x_i+b)-1+{\xi }_i)-\sum _{i=1}^N{\mu }_i{\xi }_i$$

其中 ${\alpha }_i\ge 0,{\mu }_i\ge 0$ 。

其对偶问题是拉格朗日函数的极大极小问题。

1. 求 ${\min }_{w,b,\xi }L$

   分别对 $w,b,\xi$ 求导：

   \begin{aligned} \nabla_{w}L(w,b,\xi,\alpha,\mu)&=w-\sum_{i=1}^{N}\alpha_{i}y_{i}x_{i}=0 \\ \nabla_{b}L(w,b,\xi,\alpha,\mu)&=-\sum_{i=1}^{N}\alpha_{i}y_{i}=0 \\ \nabla_{\xi_i}L(w,b,\xi,\alpha,\mu)&=C-\alpha_i-\mu_i=0 \\ \end{aligned}

   得：

   \begin{aligned} w=\sum_{i=1}^{N}\alpha_iy_ix_i \\ \sum_{i=1}^{N}\alpha_iy_i=0 \\ C-\alpha_i-\mu_i=0 \end{aligned}

   将上式代回原拉格朗日函数得：

   $$\underset{w,b,\xi }{\min }L(w,b,\xi ,\alpha ,\mu )=\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\cdot x_j)$$

2. 求 ${\max }_{\alpha ,\mu }{\min }_{w,b,\xi }L$

   我们的优化问题变成了：

   \begin{aligned} \max_{\alpha} \quad &\sum_{i=1}^{N}\alpha_i-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j) \\ s.t. \quad &\sum_{i=1}^{N}\alpha_iy_i=0 \\ &C - \alpha_i - \mu_i = 0 \\ & \alpha_i \geq 0 \\ & \mu_i \geq 0, \quad i=1,2,\cdots,N \end{aligned}

   将 ${\mu }_i$ 用 ${\alpha }_i$ 表示之后，可以将约束条件简化为

   $$0\le {\alpha }_i\le C,i=1,2,\cdots ,N$$

   设 ${\alpha }^{\text{*}}=({\alpha }_1^{\text{*}},{\alpha }_2^{\text{*}},\cdots ,{\alpha }_N^{\text{*}}{)}^T$ 是对偶问题的一个解， 若存在 ${\alpha }^{\text{*}}$ 的一个分量 ${\alpha }_j^{\text{*}}$ ， $0<{\alpha }_j^{\text{*}}<C$ ，则原始问题的解为

   \begin{aligned} w^*=\sum_{i=1}^{N}\alpha_i^*y_ix_i \\ b^*=y_j-\sum_{i=1}^{N}y_i\alpha_i^*(x_i\cdot x_j) \end{aligned}

   证明方法可以参考之前线性可分支持向量机学习算法。

支持向量

软间隔的支持向量 $x_i$ 或者在间隔边界上，或者在间隔边界与分离超平面之间， 或者在分离超平面误分一侧。

• 若 ${\alpha }_i^{\text{*}}<C$ ，则 ${\xi }_i=0$ ，支持向量恰好落在间隔边界上；
• 若 ${\alpha }_i^{\text{*}}=C,0<{\xi }_i<1$ ，则分类正确，在间隔边界和分离超平面之间；
• 若 ${\alpha }_i^{\text{*}}=C,{\xi }_i=1$ ，则 $x_i$ 正好在分离超平面上；
• 若 ${\alpha }_i^{\text{*}}=C,{\xi }_i>1$ ，则 $x_i$ 被分离超平面误分。

合页损失函数

线性支持向量机原始最优化问题等价于

$$\underset{w,b}{\min }\sum _{i=0}^N{\left[1-y_i(w\cdot x_i+b)\right]}_{+}+\lambda ||w|{|}^2$$

证明： 合页损失函数（hinge loss function）为：

\begin{equation*} [z]_{+}=\left\{ \begin{array}{rcl} z,\;&z>0 \\ 0,\;&z\leq0 \end{array} \right. \end{equation*}

令 $[1-y_i(w\cdot x_i+b){]}_{+}={\xi }_i$ ，可知 ${\xi }_i\ge 0$ 。 当 $1-y_i(w\cdot x_i+b)>0$ ， $y_i(w\cdot x_i+b)=1-{\xi }_i$ ； 当 $1-y_i(w\cdot x_i+b)\le 0$ ， ${\xi }_i=0$ ，即 $y_i(w\cdot x_i+b)\ge 1-{\xi }_i$

因此，约束条件成立。

最优化问题可以写成：

$$\underset{w,b}{\min }=\sum _{i=1}^N{\xi }_i+\lambda ||w|{|}^2$$

与线性支持向量机的原始最优化问题等价。

非线性支持向量机和核函数

序列最小最优算法

Ref

• 《统计学习方法》——李航
• cs229-note3