[機械学習]サポートベクトルマシン(SVM)の気持ちを説明する(ハードマージン編)

はじめに

今回の記事は機械学習と数理最適化 Advent Calendar 2023の11日目の記事です。

機械学習のアルゴリズムとして入門書でもよく取り上げられるサポートベクトルマシンについて解説します。今回はデータが線形分離可能(ex.1つの直線でデータを2つに分けられる)なケースについて説明します。次回以降の記事で線形分離不可能なケースも解説していく予定です。

サポートベクトルマシンとは

サポートベクトルマシンは、機械学習アルゴリズムの1つで教師あり学習に該当するアルゴリズムです。サポートベクトルマシンでは、マージン最大化という考え方を基にデータを分離するための関数を定義します(詳しい理論は後述)。データを分離するための関数が定義できたら、その関数を基に未知のデータを分類します。サポートベクトルマシンは、主に2値分類に使用されますが、多クラス分類や回帰問題へも応用可能です。
また、サポートベクトルの弱点として、学習時の計算コストが高く、大規模なデータセットには向いていないという点があります。

サポートベクトルマシンの気持ち

ここで、データの分離に関して簡単な事例を出しながら、説明していきたいと思います。×のクラスに属するデータと〇のクラスに属するデータがある時、境界線を引いてデータを分けるとしたらどう境界線を引きますか？今回は境界線の引き方として2つの例を図に示します。

図の場合だと、おそらく直感的に右の分け方をするのではないでしょうか。例えば、新しいデータ★が追加された時、左の境界線だと★は×クラスに属しますが、右の分け方だと〇クラスに属します。

★は〇クラスに近い位置にあるので、〇クラスに属するのが自然なように見えます。
ここで、図の右と左の分け方の違いは、境界線と境界線に一番近いデータとの距離です。サポートベクトルマシンでは、境界線(決定境界)に一番近いデータをサポートベクトル、サポートベクトルと決定境界の距離をマージンといいます。サポートベクトルマシンではマージンが最大化するように決定境界を決めます。

サポートベクトルマシンを数式で理解する

ここからは数式を使ってサポートベクトルマシンについて説明していきます。
話を簡単にするために、まずは2次元で考える。座標平面上の点をx=[$x_1$, $x_2$]とすると、xを通る直線は下記の関数であらわすことができます。

$$f(x)=w_1x_1 + w_2x_2 + b$$

$w$は変数に対する重みで$b$はバイアスです。
また、クラス$K_1$のサポートベクトルを通る時に1, $K_2$のサポートベクトルを通る時に-1になるように重みを調整したとすると下図のように表すことができます。

また、サポートベクトルと決定境界との距離は、高校数学で習った点と直線の距離の公式を使うと下式で求めらます。(参考)

$$d=\frac{|w_1x_1+w_2x_2+b|}{\sqrt{w_1^2+w_2^2}}$$

また、マージン=決定境界とクラスK1のサポートベクトルとの距離+決定境界とクラスK2のサポートベクトルとの距離かつ、($x_1$, $x_2$)がサポートベクトルの場合、|w_1x_1+w_2x_2+b|=|1|=|-1|=1であることから、マージンMは下式で表せる。

$$M=\frac{1}{\sqrt{w_1^2+w_2^2}}+\frac{1}{\sqrt{w_1^2+w_2^2}} = \frac{2}{\sqrt{w_1^2+w_2^2}}$$

SVMの目的はマージンを最大化することであるため、数式で表すと下式になります。

$$\max_{w} \frac{2}{||w||} =\min_{w} ||w||$$

ここで、$||w||=\sqrt{w_1^2+w_2^2}$で、$\frac{2}{||w||}$を最大化するということは、$||w||$を最小化することと同義となります。

また、マージンを最大化すればよいだけではなく、$y_i=1$の時(クラス$K_1$の時)、$w_1x_1+w_2x_2+b \ge 1$となり、$y_i=-1$の時(クラス$K_2の時)、$w_1x_1+w_2x_2+b \le 1$となる必要がある。

つまり、以下の2条件を満たすように、$w$, $b$を調整する最適化問題と捉えることができます。

$$\min_{w} ||w|| \\ y_i(w_1x_1+w_2x_2+b) \ge 1 (i=1, 2...N)$$

この制約付き最適化の問題を解くためには、Lagrange の未定乗数法という手法を使うのですが、話が複雑になるので機会があれば別記事で書きたいと思います。

SVMについて、$w$, $b$を調整して制約を満たしつつ、マージンを最大にしているんだということが伝わればよいと思います。

おわりに

サポートベクトルマシンについて、理論と数式について説明しました。どんなモチベーション(気持ち)でデータを分離しようとしているのかが伝われば幸いです。
　また、今回はハードマージンのSVMについて解説しました。つまり、データが直線で分離できる場合についての解説です。下記のような直線では分離できない場合は、どう扱えばよいのでしょうか。この場合は、ソフトマージンや高次元空間への射影といった考え方を用います。これらについては、次回以降の記事で解説していきたいと思います。