こんにちは、(株)日立製作所 Lumada Data Science Lab. の中川です。普段は人工知能を制御に適用する研究に従事しています。近年、機械学習が注目される中、機械学習理論および機械学習を使った技術開発環境は急速に進歩すると共に、多くの方がデータサイエンスに関わるようになってきました。すでにデータサイエンスに携わっている方や、これからデータサイエンスに関わってみようと思っている方の中で、理論の大切さをあらためて知りたいあるいは感じたいという方がいらっしゃいましたら、それをできるだけわかりやすく伝えられたら、という思いから基本的な内容で記事を書きます。今回は、SVM(Support Vector Machine)をおさらいします。
表１は、代表的なSVMをまとめています。SVMはクラス分類器ですが、データの種類、データの分布、分類方式に応じて、適切なSVMを選ぶことができます。また、SVMは、説明性に優れる一方で、ディープラーニングなどのカッティング・エッジな手法と比較しますとその精度は劣るというのが一般的な評価ではないかと思います。しかし、SVMは前記のように説明性に優れることに加え、その学習は、凸問題に帰着することから、大域最適解であることが保証されるなど、理論的には魅力的なところが多々あります。表中のSVMから、今回は２クラスハードマージン線形SVMと呼ばれるSVMについておさらいします。
1. はじめに
SVMには、いくつかの種類があります。以下に簡単にまとめます。
・分類と回帰の機能がある。
・分類機能には下記がある。
－ 線形SVMと非線形SVMがある。
－ 1クラス SVMと2クラスSVMがある。
－ 2クラスSVMには、ハードマージンSVMとソフトマージンSVMがある。
・回帰機能には下記がある。
－ 線形SV回帰と非線形SV回帰がある。
非線形SVMおよび非線形SV回帰は、カーネル関数を用いますので、カーネルマシンとして扱われることもあります。以上を図１にまとめてみました。
SVMを体系的に理解するには、次の順序で進めて行くのが良いのではないかと思います。
1. 分類器としての２クラスハードマージン線形SVM
↓
2. 分類器としての２クラスソフトマージン線形SVM
↓
3. 分類器としての２クラス非線形SVM
↓
4. 分類器としての１クラス非線形SVM
↓
5. 回帰としての線形SV回帰/非線形SV回帰
今回は、「1. 分類器としての２クラスハードマージン線形SVM」について、おさらいします。
2. どのような分類を考えるのか？
分類器としての２クラスハードマージン線形SVMは、どのような分類を考えるのか、を図２に示します。わかりやすいように２次元で表しています。直線 $f({\bf x})={\bf\omega}^{T} \cdot {\bf x} + \gamma=0$ によりデータが（○と×に）2分可能なデータの分布を考えます。ここで、データの分布は図２にありますように直線で分離可能な分布とします（ハードマージンは、このような分布を前提としています）。${\bf x}$ が○のときは$f({\bf x})>0$ となり、${\bf x}$ が×のときは$f({\bf x})<0$ となるような $f({\bf x})$ を求めること、すなわち、$\bf{\omega}$ と $\gamma$ を決めることを考えます。
3. パラメータ(ωとγ)を決めるための２つの条件
3-1. 条件１
図３で示されるような直線 $f({\bf x})=0$ であれば、全ての ${\bf x}^i$ に対して、正しく分類できたことになります。これを条件１とします。一方で、条件１を満たす直線は無数にあることがわかります。
3-2. 条件２
そこで、図４に示されるような直線 $f({\bf x})=0$ に対するマージンを考え、条件１を満たす無数の直線の中から、マージンを最大化するような直線を考えます。マージンを最大化するような直線 $f({\bf x})=0$ とは、直線 $f({\bf x})=0$ からもっとも近い○と×それぞれから直線 $f({\bf x})=0$ に垂線を下ろしたとき、双方の垂線の長さが同時に最大となる（＝等しくなる）ような直線 ${f({\bf x})=0}$ であり、このような直線は一意に決まります。このとき直線 ${f({\bf x})=0}$ をハードマージン線形SVMと呼びます。マージン最大化という考え方で分類線を定義することは、分類性能を高くする一つの合理的なアプローチではないでしょうか。
以上からハードマージン線形SVM（直線 $f({\bf x})＝０$）が満たす条件１と条件２を示しました。次章で、条件１と条件２を同時に満たす直線を酢学的に求めてみます。つまり、ハードマージン線形SVM（直線 $f({\bf x})＝０$）のパラメータ ${\bf\omega}_0$ と $\gamma_0$ を求めるための数式を導出してみます。
4. 条件１を数学的に表現してみる
まず、学習データ ${\bf x}^i$ に次のような正解ラベル $y^i$ を付与します。
$$
y^i=
\left\{
\begin{array}
+1&（,{\bf x}^iが○のとき,）\
-1&（,{\bf x}^iが×のとき,）
\end{array}
\right.
$$
このとき、条件１を満たすことを数式で表してみると、全ての ${\bf x}^i$に対して、(1)式が成立することであると言えます。
$$
y^i\cdot f({\bf x}^i)>0\hspace{1cm}・・・(1)
$$
(1)式は、正解ラベルの値である $y^i$ とハードマージン線形SVMの分類結果 $f({\bf x}^i)$ の符号が一致しているときに成立します。○のデータを正しく分類できているときは、直線 $f({\bf x})=0$ より上側に○が存在しているということですので、それを数式で表現すると、$y^i=1$ かつ $({\bf \omega}_0^T{\bf x}^i+\gamma_0)>0$ なので、(1)式が成立します。一方で、×のデータを正しく分類できているときは、直線 $f({\bf x})=0$ より下側に×が存在しているということですので、それを数式で表現すると、$y^i=-1$ かつ $({\bf \omega}_0^T{\bf x}^i+\gamma_0)<0$ なので、同じく(1)式が成立します。 つまり、ハードマージン線形SVMの分類結果 $f({\bf x}^i)$ が正解のときに、(1)式が成立します。したがって、全ての ${\bf x}^i$ （全ての○および×）に対して(1)式が成立すれば、直線 $f({\bf x})=0$ は全ての ${\bf x}^i$ （全ての○および×）に対して、正しく分類できたことになり、条件１を満たすことになります。また、
$$
f({\bf x}^i)={\bf\omega}_0^T{\bf x}^i + \gamma_0\hspace{1cm}・・・(2)
$$
なので、(1)式は(3)式のように表すこともできます。
$$
y^i\cdot({\bf \omega}_0^T{\bf x}^i+\gamma_0)>0 \hspace{1cm}・・・(3)
$$
5. 条件２を数学的に表現してみる
(3)式は、直線 $f({\bf x})=0$ を用いて ${\bf x}^i$ を正しく分類できたときを意味しました。しかし、条件１（(3)式）を満たす直線 $f({\bf x})=0$ は、図３でも示しましたように無数にあります。そこで、条件２では、条件１の中から直線を一意に決めるためにマージン最大化という考え方を追加することで、直線を一意に決めます。
図５に示すようなマージンを定義する直線すなわちマージン直線を(4)式、(5)式のように定義します。
$$
\begin{array}{l}
f({\bf x})={\bf \omega}_0^T\cdot{\bf x}+\gamma_0=+K \hspace{1cm}・・・(4)\
f({\bf x})={\bf \omega}_0^T\cdot{\bf x}+\gamma_0=-K \hspace{1cm}・・・(5)\
;;(K>0)
\end{array}
$$
図５は、(4)式で定義されるマージン直線上もしくはそれより上側に全ての○が存在しており、逆に(5)式で定義されるマージン直線上もしくはそれより下側に全ての×が存在している場合を示しています。なお、２つのマージン直線と線形ハードマージンSVMの関係は、図６に示されるようになります。（なお、$K>0$ なので、どんなに$K$の値が小さくても、すなわちどんなにマージンが小さくても、○と×は直線 $f({\bf x})=0$ 上には乗ってきません。）
(4)式で定義されるマージン直線上もしくはそれより上側に全ての○が存在しているということを数式で表現すると、○のデータを正しく分類できているときは、$y^i=1$ かつ $({\bf \omega}_0^T{\bf x}^i+\gamma_0)\geq K$ なので、(3)式を参考にして、(6)式で表されます。
$$
y^i\cdot({\bf \omega}_0^T{\bf x}^i+\gamma_0)\geq K \hspace{1cm}・・・(6)
$$
また、(5)式で定義されるマージン直線上もしくはそれより下側に全ての×が存在しているということを数式で表現すると、×のデータを正しく分類できているときは、$y^i=-1$ かつ $({\bf \omega}_0^T{\bf x}^i+\gamma_0)\leq-K$ なので、(3)式を参考にして、○のときと同じく(6)式で表されます。
以上から(6)式で２つのマージン直線のいわば外側に○と×がそれぞれ存在するマージン直線を数式で定義できました。(6)式は、直線 $f({\bf x})=0$ のパラメータである ${\bf \omega}_0$ と $\gamma_0$ の条件でもあるので、直線 $f({\bf x})=0$ も同時に定義しています。図６をみるとイメージが湧きやすいかもしれません。
しかし、(6)式を満たすマージン直線および 直線 $f({\bf x})=0$ は、図７でも示すように、やはり無数にあります（図７はマージン直線のみ図示。黒、緑、ピンクの線がそれぞれ一組のマージン直線を表しています）。
前述しましたように、マージンとは、図８で示しますように、直線 $f({\bf x})=0$ からもっとも近い○と×それぞれから直線 $f({\bf x})=0$ に垂線を下ろしたとき、双方の垂線の長さが同時に最大となる（＝等しくなる）ような○と×までの距離としました。ここまでの導出では、この条件がまだ考慮がされておりませんので、この条件を考慮することで、図８に示されるように一組のマージン直線と直線 $f({\bf x})=0$ が一意に決まることになります。次に、これを数式で表すことを考えます。
${\bf x}^i$ から直線 $f({\bf x})=0$ に下ろした垂線の長さを考えます。図９は、 ${\bf x}^i$ から直線 $f({\bf x})=0$ までの距離 $l^i$ （垂線の長さ）の例を示しています。任意の ${\bf x}^i$ における距離 $l^i$ は、点と直線の距離の公式から(7)式で表されます。
$$
l^i=\frac{|,{\bf \omega}_0^T{\bf x}^i+\gamma_0,|}{||{\bf \omega}_0||}\hspace{1cm}・・・(7)
$$
前述しましたマージンの定義から、全ての $l^i$ の中でもっとも小さい $l^i$ がマージンとなります。このとき、直線 $f({\bf x})=0$ に最も近い○と×のデータ番号 $i$ をそれぞれ $i\_min$ と $i\_min’$ とすると、
$$
l^{i\_min}=\frac{|,{\bf \omega}_0^T{\bf x}^{i\_min}+\gamma_0,|}{||{\bf \omega}_0||}\hspace{1cm}・・・(8)
$$
$$
l^{i\_min'}=\frac{|,{\bf \omega}_0^T{\bf x}^{i\_min'}+\gamma_0,|}{||{\bf \omega}_0||}\hspace{1cm}・・・(9)
$$
同じく、前述しましたようにマージンの定義から $l^{i\_min}$ と $l^{i\_min'}$ を同時に最大化するようにマージン直線および直線 $f({\bf x})=0$ を決めますので、このとき、$l^{i\_min} = l^{i\_min'}$ であり、その大きさはマージンの大きさ$M$に等しくなります。図１０に例を示しています。図においては、$i\_min=3$ であり、$i\_min'=6$ です。また、$l^3 = l^6=M$ です。
このマージン$M$（$＝l^{i\_min}=l^{i\_min'}$）を最大化するように、直線 $f({\bf x})=0$ の条件に加えれば良いので、この条件を定式化しますと(10)式となります。
$$
\underset{{\bf \omega}_0,;\gamma_0}{max};M=\underset{{\bf \omega}_0,;\gamma_0}{max};l^{i\_min}=\underset{{\bf \omega}_0,;\gamma_0}{max};l^{i\_min'}
\hspace{1cm}・・・(10)
$$
また、(10)式は、(8)式より、(11)式および(12)式のようにも表せます。
$$
\underset{{\bf \omega}_0,;\gamma_0}{max};\frac{|,{\bf \omega}_0^T{\bf x}^{i\_min}+\gamma_0,|}{||{\bf \omega}_0||}\hspace{1cm}・・・(11)
$$
$$
\underset{{\bf \omega}_0,;\gamma_0}{max};\frac{|,{\bf \omega}_0^T{\bf x}^{i\_min'}+\gamma_0,|}{||{\bf \omega}_0||}\hspace{1cm}・・・(12)
$$
(11)式もしくは(12)式をみたすような ${\bf \omega}_0$ と $\gamma_0$ を求めれば、(6)式を満たす無数のマージン直線と直線 $f({\bf x})=0$ の中から、マージン直線と直線 $f({\bf x})=0$を一意に決めることができます。
以上、まとめます。
条件１：図３で示されるような直線 $f({\bf x})=0$
⇒ (3)式を満たす ${\bf \omega}_0$ と $\gamma_0$ 。
条件２： 図４に示されるような直線 $f({\bf x})=0$ に対するマージンを考え、条件１を満たす無数の直線の中から、マージンを最大化するような直線 $f({\bf x})=0$ 。
⇒ (6)式と(11)式を満たす ${\bf \omega}_0$ と $\gamma_0$ 。
（(11)式と(12)式の解は、等しいので、(11)式のみに絞ってます。）
ここで、(3)式と(6)式を見比べますと、$K\geq0$ なので、(6)式が成立すれば、(3)式も成立することがわかります。条件２では、直線 $f({\bf x})=0$ の外側にマージン直線を設けて、その上側のマージン直線の外側（上側）に全ての○があるとし、下側のマージン直線の外側（下側）に全ての×があるとしました。これを数式で表したのが(6)式ですが、このとき、２つのマージン直線と平行でかつその真ん中に存在する直線 $f({\bf x})=0$ の上側に全ての○が存在し、下側に全ての×が存在するとした(3)式は必然的に成立するからです。
以上から、ハードマージン線形SVMを数学的に表すと(6)式と(11)式を同時に満たす ${\bf \omega}_0$ と $\gamma_0$ を求めれば良いことになります。
6. もう少し簡単化してみる
前章でハードマージン線形SVMを(6)式と(11)式で定式化しました。本章では、この２つの式をもう少し解きやすい形に簡単化してみることを考えます。そのために、ここで、(13)式と(14)式で示される ${\bf \omega}_1$ と $\gamma_1$ をあらたに、導入します。
$$
\begin{align}
,&{\bf \omega}_1=\frac{1}{M||{\bf\omega}_0||}{\bf\omega}_0\hspace{1cm}・・・(13)\
,&\
,&\gamma_1=\frac{1}{M||{\bf\omega}_0||}\gamma_0\hspace{1cm}・・・(14)
\end{align}
$$
(13)式をみると、${\bf\omega}_1$は、${\bf\omega}_0/||\omega_0||$に$1/M$を乗じた値となっています。${\bf\omega}_0/||\omega_0||$ は単位ベクトルですので、${\bf\omega}_1$は${\bf\omega}_0$と向きが同じで大きさがマージンの大きさMの逆数である$1/M$に等しいベクトルです。また、$\gamma_1$ も ${\bf \omega}_0$ に乗じた値と同じ値である $1/(M||\bf \omega_0||)$ を $\gamma_0$ に乗じることで得ています。このような ${\bf \omega}_1$ と $\gamma_1$を用いた直線を(15)式のように定義します。
$$
f({\bf x})={\bf \omega}_1^T{\bf x}+\gamma_1=0\hspace{1cm}・・・(15)
$$
(15)式で定義される直線は、前章までに議論してきた直線 $f(\bf x)={\bf \omega}_0^T{\bf x}+\gamma_0$ と同じ直線である一方で、その法線ベクトル ${\bf \omega}_1$の大きさは、マージンの大きさ$M$に応じて決まります。このような ${\bf \omega}_1$, $\gamma_1$ を用いて、以下の式変形を行うことで、前章で定式化したハードマージン線形SVMの式を少し簡単化していきます。
(8)式、(13)式、(14)式より
$$
\begin{align}
,&l^{i_min}=\frac{|,{\bf \omega}_0^T{\bf x}^{i_min}+\gamma_0,|}{||{\bf \omega}_0||}
=\frac{|,M||{\bf \omega}_0||{\bf \omega}_1^T{\bf x}^{i_min}+M||{\bf \omega}_0||\gamma_1,|}{||{\bf \omega}_0||}
=M\hspace{1cm}・・・(16)\
,&\
,&\therefore;|,{\bf \omega}_1^T{\bf x}^{i_min}+\gamma_1,|=1\
,&\therefore;{\bf \omega}_1^T{\bf x}^{i_min}+\gamma_1=+1\hspace{1cm}・・・(17)\
,&\hspace{1cm}もしくは、i=i_min'のときは\
,&\hspace{0.7cm}{\bf \omega}_1^T{\bf x}^{i_min'}+\gamma_1=-1\hspace{1cm}・・・(18)
\end{align}
$$
(17)式もしくは(18)式は、法線ベクトルが ${\bf \omega}_1$ で、${\bf x}^{i\_min}$もしくは${\bf x}^{i\_min'}$を通る直線を表しており、すなわち、図１１に示すように ${\bf \omega}_1$, $\gamma_1$ を用いて表した２つのマージン直線の式を表しています。(13)式および(14)式で定義される${\bf \omega}_1$, $\gamma_1$ を導入すると、マージン$M$の大きさに関わらず、(17)式もしくは(18)式に示すように、右辺は常に+1もしくは-1となります。
したがって、(6)式は、 ${\bf \omega}_1$, $\gamma_1$ を用いて表すと(19)式のようになります。
$$
y^i\cdot({\bf \omega}_1^T{\bf x}^i+\gamma_1)\geq 1 \hspace{1cm}・・・(19)
$$
蛇足かもしれませんが、補足説明しておきますと、(17)式で定義されるマージン直線上もしくはそれより上側に全ての○が存在しているということを数式で表現すると、$y^i=1$ かつ $({\bf \omega}_1^T{\bf x}^i+\gamma_1)\geq 1$ なので、(19)式で表されます。また、(18)式で定義されるマージン直線上もしくはそれより下側に全ての×が存在しているということを数式で表現すると、×のデータを正しく分類できているときは、$y^i=-1$ かつ $({\bf \omega}_1^T{\bf x}^i+\gamma_1)\leq-1$ なので、○のときと同じく(19)式で表されます。以上から、ハードマージン線形SVMを定式化した(6)式を(19)式に変換することで、少し簡単化できました。
次にハードマージン線形SVMを定式化した(11)式を簡単化してみます。直線 $f(\bf x)={\bf \omega}_0^T{\bf x}+\gamma_0$ と直線 $f(\bf x)={\bf \omega}_1^T{\bf x}+\gamma_1$は同一の直線を表してましたので、次が成り立ちます。
$$
\begin{align}
l^{i\_min}&=\frac{|,{\bf \omega}_0^T{\bf x}^{i\_min}+\gamma_0,|}{||{\bf \omega}_0||}\
&=\frac{|,{\bf \omega}_1^T{\bf x}^{i\_min}+\gamma_1,|}{||{\bf \omega}_1||}\
&=\frac{1}{||{\bf \omega}_1||}\hspace{1cm}・・・(20)\
&\
&\hspace{1cm}\because |,{\bf \omega}_1^T{\bf x}^{i\_min}+\gamma_1,|=1
\end{align}
$$
したがって、(11)式は、(21)式のように表せます。
$$
\underset{{\bf \omega}_1,;\gamma_1}{max};\frac{1}{||{\bf \omega}_1||}\hspace{1cm}・・・(21)
$$
さらに、(21)式を最小化問題に書き換えると(22)式が得られます。
$$
\underset{{\bf \omega}_1,;\gamma_1}{min};||{\bf \omega}_1||\hspace{1cm}・・・(22)
$$
さらに、(22)式を最適化問題として、扱いやすいように二次形式にして(23)式にします。
$$
\underset{{\bf \omega}_1,;\gamma_1}{min};||{\bf \omega}_1||^2\hspace{1cm}・・・(23)
$$
以上から(11)式を簡単化した(23)式が得られました。
(6)式を簡単化した(19)式と(11)式を簡単化した(23)式において、${\bf \omega}_1$ と $\gamma_1$ は任意性があるので、一般的な表現として${\bf \omega}_1$ を $\omega$ に $\gamma_1$ を $\gamma$ に書き直して、(19)式および(23)式は、それぞれ(24)式および(25)式となります。
$$
\begin{array}{l}
,&y^i\cdot({\bf \omega}^T{\bf x}^i+\gamma)\geq 1 \hspace{1cm}・・・(24)\
,&\underset{{\bf \omega},;\gamma}{min};||{\bf \omega}||^2\hspace{1cm}・・・(25)
\end{array}
$$
なお、制約条件（(24)式）から、２つのマージン直線上もしくはそれより（いわば）外側に全てのデータ ${\bf x}^i $ は存在するようにマージン直線および直線 $f({\bf x})=0$ は決められます。したがって、テストデータを適用したときは、$f(\bf x)\geq1$ のとき、そのテストデータは○に分類されたと判断し、$f({\bf x})\leq-1$ のとき、そのテストデータは、×に分類されたと判断することになります。２つのマージン直線に挟まれた領域に相当する $-1$<$f({\bf x})$<$1$ のときは、学習時にはデータが存在しない領域ですので、テストデータの結果がこの領域に分類されたときは、本来はグレーゾーンです。テストデータの結果が $0$<$f({\bf x})$<$1$ のとき、そのテストデータは○に分類されたと判断したり、あるいは、$-1$<$f({\bf x})$<$0$ のとき、そのテストデータは×に分類されと判断したりするような仕様にするときは、本来はグレーゾーンであることに留意しましょう。
以上で、ハードマージン線形SVMを(24)式と(25)式で定式化しました。(24)式と(25)式の形にした理由は、この２つの式が２次計画問題と言われる形をしているからです。２次計画問題とは、目的関数（ここでは(25)式）が２次形式であり、制約条件（ここでは(24)式）が１次関数である最適化問題です。２次計画問題には様々な解法がありますが、SVMの場合は、ラグランジュの双対問題として最適化するのが一般的です。SVMのパラメータ最適化をラグランジュの双対問題として解く手順については、本記事ではご紹介しませんが、ソフトマージン線形SVMの紹介の記事にてご紹介します。
7. おわりに
今回は、ハードマージン線形SVMと呼ばれるSVMについておさらいしました。ハードマージン線形SVMの定式化をできるだけわかりやすいアプローチで紹介したつもりです。ハードマージン線形SVMの機能は、イメージしやすいのではないかと思いますが、これを数式で表そうとすると複雑と思われた方もいらっしゃるのではないでしょうか。
今回も、理論の大切さをあらためて知りたいあるいは感じたいという方がいらっしゃいましたら、それをできるだけわかりやすく伝えられたら、という思いから記事を書かせて頂きました。より詳しく知りたいという方は、参考文献などをご参考頂ければと思います。また、SVMはハードマージン線形SVMの他に、ソフトマージン線形SVM、非線形SVMなど、様々な形があります。これらについては他の記事で紹介しますので、ご興味のある方はご参考下さい。
参考文献
竹内 一郎、鳥山昌幸：サポートベクトルマシン
赤穂昭太郎：カーネル多変量解析