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

This article is available in: English

はじめに

　サポートベクターマシン（SVM）とは、パターン識別用の教師あり機械学習アルゴリズムの１種です。

「マージンを最大化する」というアイデアで汎化能力も高く、局所解収束の問題が無いという長所もあり、優秀な２クラス分類のアルゴリズムとなっています。

線形分離可能なデータを前提とした「ハードマージン」、線形分離不可能なデータを前提として誤分類をある程度許容する「ソフトマージン」があり、この記事ではハードマージンのサポートベクターマシンの理論を説明します。

▼ソフトマージンSVMの理論はこちら

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

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

laid-back-scientist.com

2022.05.31

\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

　ハードマージンのサポートベクターマシンの目的は、2クラスのデータを完全に分離する「最適」な超平面 $\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*}

2クラスのデータを完全に分離する超平面はいくらでも引くことができますが、「最適」な超平面とは、マージンを最大とする分離超平面のことです。

ここでは、分離超平面とその分離超平面に最も近いデータとの距離をマージンと呼びます。

マージン $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

2022.01.20

最適な分離分離超平面$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 がついているのは微分した後の式をキレイにするため、2乗となっているのは2次計画問題の形にもっていくためです）

ラグランジュの未定乗数法を用いた変形

　ラグランジュの未定乗数法を用いて、条件付き最適化問題を解きます。今回は不等式の制約条件なので、KKT条件が適応できます。

▼ KKT条件については、こちらの記事で解説しています。

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

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

laid-back-scientist.com

2022.05.04

制約条件の数はデータ数の $n$ 個ありますから、ラグランジュ乗数 $\alpha_1, \alpha_2, \dots, \alpha_n$ を用いて、ラグランジュ関数 $L$ を下記と定義します。

すると、$\bm{w}$ の最適解においてはKKT条件から次式が成立します。

式 (☆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

2022.01.20

以上より、未定乗数 $\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}$ の和にてサポートベクトルでないデータのindexでは $\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}$ を求めることで分離超平面を決定することができます。

サポートベクターマシンの実装はこちら▼

ハードマージンのサポートベクターマシン（SVM）の解説 pythonによる実装と例題

ハードマージンのサポートベクターマシンをフルスクラッチとscikit-learnで実装します。 ここでは、Pythonを用いた実装をおこなっていきます。

laid-back-scientist.com

2022.05.05