硬间隔支持向量机 (SVM) 原理详解：理论篇

前言

　支持向量机（SVM）是一种用于模式识别的监督式机器学习算法。

它基于“最大化间隔”的思想，具有泛化能力强、不存在陷入局部最优解问题等优点，是一种优秀的二分类算法。

SVM 分为以线性可分数据为前提的“硬间隔”，以及以线性不可分数据为前提、允许一定程度误分类的“软间隔”。本文将解释硬间隔支持向量机的理论。

▼软间隔 SVM 的理论请见此处

ソフトマージンのサポートベクターマシン（SVM）の解説 理論編

サポートベクターマシン（SVM）とは、パターン識別用の教師あり機械学習アルゴリズムの１種です。線形分離可能なデータを前提とした「ハードマージン」、線形分離不可能なデータを前提として誤分類をある程度許容する「ソフトマージン」があります。今回の...

laid-back-scientist.com

\begin{align*}
\newcommand{\mat}[1]{\begin{pmatrix} #1 \end{pmatrix}}
\newcommand{\f}[2]{\frac{#1}{#2}}
\newcommand{\pd}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\d}[2]{\frac{{\rm d}#1}{{\rm d}#2}}
\newcommand{\T}{\mathsf{T}}
\newcommand{\(}{\left(}
\newcommand{\)}{\right)}
\newcommand{\{}{\left\{}
\newcommand{\}}{\right\}}
\newcommand{\[}{\left[}
\newcommand{\]}{\right]}
\newcommand{\dis}{\displaystyle}
\newcommand{\eq}[1]{{\rm Eq}(\ref{#1})}
\newcommand{\n}{\notag\\}
\newcommand{\t}{\ \ \ \ }
\newcommand{\tt}{\t\t\t\t}
\newcommand{\argmax}{\mathop{\rm arg\, max}\limits}
\newcommand{\argmin}{\mathop{\rm arg\, min}\limits}
\def\l<#1>{\left\langle #1 \right\rangle}
\def\us#1_#2{\underset{#2}{#1}}
\def\os#1^#2{\overset{#2}{#1}}
\newcommand{\case}[1]{\{ \begin{array}{ll} #1 \end{array} \right.}
\newcommand{\s}[1]{{\scriptstyle #1}}
\definecolor{myblack}{rgb}{0.27,0.27,0.27}
\definecolor{myred}{rgb}{0.78,0.24,0.18}
\definecolor{myblue}{rgb}{0.0,0.443,0.737}
\definecolor{myyellow}{rgb}{1.0,0.82,0.165}
\definecolor{mygreen}{rgb}{0.24,0.47,0.44}
\newcommand{\c}[2]{\textcolor{#1}{#2}}
\newcommand{\ub}[2]{\underbrace{#1}_{#2}}
\end{align*}

硬间隔 SVM

　硬间隔支持向量机的目标是求解能够完全分离两类数据的“最优”超平面 $\bm{w}^\T \bm{x} + b = 0$。

这里，$\bm{x}, \bm{w}$ 分别是 $p$ 维数据向量和 $p$ 维参数向量。

\begin{align*}
\bm{x} = \mat{x_1 \\ x_2 \\ \vdots \\ x_p},\t \bm{w} = \mat{w_1 \\ w_2 \\ \vdots \\ w_p}.
\end{align*}

虽然可以画出无数个完全分离两类数据的超平面，但所谓的“最优”超平面，是指使间隔最大化的分离超平面。

在这里，我们将分离超平面与距离该超平面最近的数据点之间的距离称为间隔。

间隔 $d$ 可由点与超平面的距离计算求得如下：

\begin{align*}
d = \f{|\bm{w}^\T\bm{x}_{+} + b|}{\|\bm{w}\|} = \f{|\bm{w}^\T\bm{x}_{-} + b|}{\|\bm{w}\|}.
\end{align*}

点と超平面の距離の計算公式の導出

点と直線の距離の一般形である、点と超平面の距離を導出します。

laid-back-scientist.com

在求解最优分离超平面 $H: \hat{\bm{w}}^\T \bm{x} + \hat{b} = 0$ 时，利用如上图所示在超平面 $H_{+}, H_{-}$ 之间不存在数据这一事实。

也就是说，硬间隔支持向量机的问题可以归结为“在所有数据点到超平面的距离至少为 $d$ 的条件下，求解使间隔 $d$ 最大化的 $\bm{w}, b$”的问题。

不过，上式的约束条件中使用了绝对值，处理起来稍显麻烦。由于本次的前提是线性可分数据，我们引入标签变量 $y^{(i)}$ 来去掉绝对值。

\begin{align*}
y^{(i)} = \case{1 & (\bm{x}^{(i)} \in G_1) \\ -1 & (\bm{x}^{(i)} \in G_2)}
\end{align*}

如下图所示，标签变量 $y^{(i)}$ 是一个当数据 $\bm{x}^{(i)}$ 属于 $G_1$ 组（蓝色）时取 $y=1$，当数据属于 $G_2$ 组（红色）时取 $y=-1$ 的变量。

对于数据 $\bm{x}^{(i)}$ 所属的组，以下关系成立：

\begin{align*}
\bm{x}^{(i)} \in G_1 \Leftrightarrow \bm{w}^\T \bm{x}^{(i)} + b > 0 \n
\bm{x}^{(i)} \in G_2 \Leftrightarrow \bm{w}^\T \bm{x}^{(i)} + b < 0
\end{align*}

因此，对于任意数据，

均成立。因此 $\eq{eq:cond}$ 可以变形为如下去掉了绝对值的形式。

　接下来，我们再稍微整理一下上式。

上式的条件部分，即使进行 $\bm{w} \to c \bm{w},\ b \to c b$ 这样的常数倍变换，

结果依然不变，因此对于 $\bm{w}, b$ 的任意常数缩放具有不变性。

因此，我们可以对条件部分进行变形，

\begin{align*}
&\f{y^{(i)}(\bm{w}^\T \bm{x}^{(i)} + b)}{\| \bm{w} \|} \geq d \n
\n
&\downarrow \textstyle\t \s{两边同除以 d} \n
\n
&y^{(i)} \bigg( \underbrace{\f{1}{d \| \bm{w} \|} \bm{w}^\T}_{=\bm{w}^{*\T}} \bm{x}^{(i)} + \underbrace{\f{1}{d \| \bm{w} \|} b}_{=b^*} \bigg) \geq 1 \n
\n
&\downarrow \textstyle\t \s{令 \bm{w}^{*\T} = \f{1}{d \| \bm{w} \|} \bm{w}^\T,\ b^* = \f{1}{d \| \bm{w} \|} b} \n
\n
&y^{(i)} \( \bm{w}^{*\T} \bm{x}^{(i)} + b^* \) \geq 1
\end{align*}

可知进行这样的缩放也是可以的。

这里，使 $y^{(i)} \( \bm{w}^{*\T} \bm{x}^{(i)} + b^* \) \geq 1$ 等号成立的数据 $\bm{x}^{(i)}$，是距离分离超平面最近的数据，即支持向量 $\bm{x}_{+}, \bm{x}_{-}$。

因此，缩放后的间隔 $d^*$ 为：

于是，$\eq{eq:cond2}$ 可以表示为如下形式：

使 $1/ \| \bm{w}^* \|$ 最大化的 $\bm{w}^*, b^*$ 等价于使 $\| \bm{w}^* \|^2$ 最小化的 $\bm{w}^*, b^*$。接下来我们将 $\bm{w}^*, b^*$ 重新记作 $\bm{w}, b$，可得以下结论。

（这里，$\|\bm{w}\|$ 前面加上 1/2 是为了使微分后的式子更简洁，取平方是为了将其转化为二次规划问题的形式）

利用拉格朗日乘数法进行变形

　利用拉格朗日乘数法求解条件优化问题。由于本次是包含不等式的约束条件，因此适用 KKT条件。

▼ 关于 KKT条件，在这篇文章中有详细讲解。

不等式条件下におけるラグランジュの未定乗数法（KKT条件）

制約条件が不等式である際の、ラグランジュの未定乗数を用いた解の求め方を解説します。この問題はKKT条件と呼ばれる条件を考慮すれば良いことが知られています。

laid-back-scientist.com

约束条件的数量为数据个数 $n$，因此引入拉格朗日乘数 $\alpha_1, \alpha_2, \dots, \alpha_n$，定义拉格朗日函数 $L$ 如下：

于是，根据 KKT条件，在 $\bm{w}$ 的最优解处成立以下关系式：

由式 (☆1), (☆2) 分别可得：

综上，将 $\eq{eq:lag1},(\ref{eq:lag2})$ 代入 $L(\bm{w}, b, \alpha_1, \dots, \alpha_n)$ 消去 $\bm{w}, b$，

如此，拉格朗日函数 $L$ 变形为了仅含 $\alpha$ 的函数 $\tilde{L}(\alpha_1, \dots, \alpha_n)$。此外，从其形式可以看出 $\tilde{L}$ 是关于 $\alpha$ 的上凸函数。

　根据以上讨论，代替 $\f{1}{2} \|\bm{w} \|^2$ 的最小化问题，我们通过求解 $\tilde{L}(\bm{\alpha})$ 的最大化问题求得最优解 $\hat{\bm{\alpha}}$，即可得到原始解 $\hat{\bm{w}}$（这一讨论称为对偶问题）。

　将至今为止的讨论总结如下。

利用最速下降法估计 $\hat{\bm{\alpha}}$

　作为求解最优解 $\hat{\bm{\alpha}}$ 的方法，这里我们使用最速下降法。在最速下降法中，随机设定参数的初始值 $\bm{\alpha}^{[0]}$，由于是最大化问题，如下所示朝着梯度向量的方向即上升方向更新参数。

\begin{align}
\bm{\alpha}^{[t+1]} = \bm{\alpha}^{[t]} + \eta \pd{\tilde{L}(\bm{\alpha})}{\bm{\alpha}}.
\label{eq:kouka}
\end{align}

为了执行最速下降法，我们需要计算梯度向量 $\pd{\tilde{L}(\bm{\alpha})}{\bm{\alpha}}$ 的值。

---

　作为计算准备，首先用向量形式重写 $\eq{eq:L_tilde}$。

将观测到的 $n$ 个 $p$ 维数据用矩阵表示如下：

此外，将 $n$ 个标签变量 $y^{(i)}$ 和未定乘数 $\alpha_i$ 分别用列向量表示如下：

\begin{align*}
\us \bm{y}_{[n \times 1]} = \mat{y^{(1)} \\ y^{(2)} \\ \vdots \\ y^{(n)}},
\t
\us \bm{\alpha}_{[n \times 1]} = \mat{\alpha_1 \\ \alpha_2 \\ \vdots \\ \alpha_n}.
\end{align*}

这里，定义新的矩阵 $H$ 为：

\begin{align*}
\us H_{[n \times n]} \equiv \us \bm{y}_{[n \times 1]} \us \bm{y}^{\T}_{[1 \times n]} \odot \us X_{[n \times p]} \us X^{\T}_{[p \times n]}
\end{align*}

（其中 $\odot$ 为阿达玛积）。
也就是说，上述矩阵的元素为 $(H)_{ij} = y^{(i)}y^{(j)} \bm{x}^{(i)\T} \bm{x}^{(j)}$，且 $H$ 是对称矩阵。

于是，$\eq{eq:L_tilde}$ 变为：

从而可以用向量来表示。

因此，梯度向量 $\pd{\tilde{L}(\bm{\alpha})}{\bm{\alpha}}$ 可以利用向量微分公式计算如下：

\begin{align*}
\pd{\tilde{L}(\bm{\alpha})}{\bm{\alpha}} &= \pd{}{\bm{\alpha}} \| \bm{\alpha} \| -\f{1}{2} \pd{}{\bm{\alpha}} \bm{\alpha}^\T H \bm{\alpha} \n
&= \bm{1}\, – H \bm{\alpha}.
\end{align*}

这里，$\bm{1}$ 是所有分量均为 1 的 $n$ 维列向量 $ \bm{1} = (1, 1, \dots, 1)^\T $。

「ベクトルで微分」公式導出

機械学習の理論を勉強すると「スカラーをベクトルで微分」する操作をよく目にします。この記事では「スカラーをベクトルで微分」の公式を導出します。

laid-back-scientist.com

综上所述，未定乘数 $\bm{\alpha}$ 的更新规则 $\eq{eq:kouka}$ 为：

\begin{align*}
\bm{\alpha}^{[t+1]} = \bm{\alpha}^{[t]} + \eta \( \bm{1}\, – H \bm{\alpha}^{[t]} \)
\end{align*}

计算分离超平面的参数 $\hat{\bm{w}}, \hat{b}$

　硬间隔 SVM 的目的是求解使间隔最大化的分离超平面，换句话说，就是求解分离超平面的参数 $\hat{\bm{w}}, \hat{b}$。

现在，如果能用最速下降法计算出未定乘数的最优解 $\hat{\bm{\alpha}}$，就可以顺势求出 $\hat{\bm{w}}, \hat{b}$。

求解 $\hat{\bm{w}}$

　一旦求得未定乘数的最优解 $\hat{\bm{\alpha}}$，根据 $\eq{eq:lag1}$ 即可计算 $\hat{\bm{w}}$。

\begin{align}
\hat{\bm{w}} = \sum_{i=1}^n \hat{\alpha}_i y^{(i)} \bm{x}^{(i)}.
\label{eq:w}
\end{align}

　接下来，我们再深入考察一下上式。根据 KKT条件中的 (☆4)，$\hat{\alpha}_i$ 与 $\bm{x}^{(i)}$ 之间成立如下关系：

\begin{align*}
\hat{\alpha_i} = 0,\ \s{或者}\ \ y^{(i)}(\bm{w}^\T \bm{x}^{(i)} + b) – 1 = 0
\end{align*}

另一方面，数据 $\bm{x}^{(i)}$ 满足：

因此可以得出：

\begin{align*}
\case{
\hat{\alpha}_i \neq 0 \Leftrightarrow \bm{x}^{(i)} \s{是支持向量}, \\
\hat{\alpha}_i = 0 \Leftrightarrow \bm{x}^{(i)} \s{不是支持向量}. \\
}
\end{align*}

因此，在 $\eq{eq:w}$ 的求和中，非支持向量数据的索引对应的 $\hat{\alpha}_i = 0$，对求和没有贡献。也就是说，只需对支持向量进行求和即可，从而节省了计算量。

\begin{align*}
\hat{\bm{w}} = \sum_{\bm{x}^{(i)} \in S} \hat{\alpha}_i y^{(i)} \bm{x}^{(i)}.
\end{align*}

（这里，$S$ 是支持向量的集合）

求解 $\hat{b}$

　根据上述求得 $\hat{\bm{w}}$ 后，利用 $\bm{x}^{(i)}$ 为支持向量时的关系式 $y^{(i)}(\hat{\bm{w}}^\T \bm{x}^{(i)} + \hat{b}) – 1 = 0$，即可计算 $\hat{b}$。

\begin{align*}
\hat{b} &= \f{1}{y^{(i)}} – \hat{\bm{w}}^\T \bm{x}^{(i)} \n
&= y^{(i)} – \hat{\bm{w}}^\T \bm{x}^{(i)} \t (\because y^{(i)} = 1, -1).
\end{align*}

虽然只要有一个支持向量就可以计算 $\hat{b}$，但实际上为了减小误差，通常会对所有支持向量取平均来计算：

\begin{align*}
\hat{b} = \f{1}{|S|} \sum_{\bm{x}^{(i)} \in S} (y^{(i)} – \hat{\bm{w}}^\T \bm{x}^{(i)}).
\end{align*}

（这里，$|S|$ 是支持向量的个数）

综上所述，通过求解 $\hat{\bm{w}}, \hat{b}$，我们就可以确定分离超平面。

支持向量机的实现请见此处▼

https://laid-back-scientist.com/svm-imple