📂機械学習

サポートベクターマシン

モデル ¹

簡単な定義

二値分類^{binary Classification}が可能なデータを最もよく区別する直線や平面を見つける方法をサポートベクターマシンという。

難しい定義

内積空間 $X = \mathbb{R}^{p}$ とラベリング^labeling $Y = \left\{ -1, +1 \right\}$ に対し、$n$ 個のデータを集めた学習データセット^{training Dataset}を $D = \left\{ \left( \mathbf{x}_{k} , y_{k} \right) \right\}_{k=1}^{n} \subset X \times Y$ とし、 $$ \begin{align*} X^{+} :=& \left\{ \mathbf{x}_{k} \in X : y_{k} = +1 \right\} \\ X^{-} :=& \left\{ \mathbf{x}_{k} \in X : y_{k} = -1 \right\} \end{align*} $$

とする。あるウェイト^weight $\mathbf{w} \in \mathbb{R}^{p}$ とバイアス^bias $b \in \mathbb{R}$ を持つ線形関数 $f \left( \mathbf{x} \right) = \mathbf{w}^{T} \mathbf{x} + b$ によって作られる超平面を $H : \mathbf{w}^{T} \mathbf{x} + b = 0$ とするとき、$H$ と最も距離が近い $\mathbf{x}^{+} \in X^{+}$ と $\mathbf{x}^{-} \in X^{-}$ をサポートベクター^{support Vector}といい、これらの間の距離 $\delta$ をマージン^marginという。これに対して $$ \begin{align*} f \left( \mathbf{x}^{+} \right) =& +1 \\ f \left( \mathbf{x}^{-} \right) =& -1 \end{align*} $$

を満たしながらマージンが最大になるような $\mathbf{w} , b$ を見つける機械学習技術をサポートベクターマシン^{sVM, Support Vector Machine}という。

---

• $\mathbb{R}$ は実数の集合であり、$\mathbb{R}^{p}$ は$p$次元ユークリッド空間である。
• $X \times Y$ は二つの集合のデカルト積を意味する。
• $\mathbf{w}^{T}$ は $\mathbf{w}$ の転置行列であり、$\mathbf{w}^{T} \mathbf{x}$ は二つのベクトル $\mathbf{w}, \mathbf{x}$ の内積 $\left< \mathbf{w} , \mathbf{x} \right>$ である。

説明

簡単に言えば、次の図のようにオレンジ色と空色のデータを二分する線や平面を見つけることである。平面図では赤い矢印で示されているのがサポートベクターに該当する。

図では $2$次元なので線を見つけ、$3$次元なので平面を見つけたが、さらに大きな$p$次元になると超平面を見つけなければならず、図示するのは難しくなる。しかし、このように空間を二つに分けるという点は変わらない。学習データセットで二値分類が完了すれば、新しいデータを受け取ったときも$f$ に入れて線形分類器^{linear Classifier}として使えばよい。

当然ながら、同じデータを二値分類しても、左側が右側よりも良い。右側の場合、空色のデータに対するマージンが過度である。具体的にこれを求める方法は、いずれにせよパッケージがすべて自動で処理するため、知らなくてもよい。

学部生レベルであれば、ここまでの簡単な定義を受け入れて図で大まかに理解するだけでも、今後実際に使用する際や用語を理解する上で大きな問題はない。これより少し難しい内容、実践的な要点の要約、Pythonの例示コードなどは、国内のウェブでもよく整理された文書がたくさんある。 ^{2 3 4}

内積空間

ご覧の通り、SVM自体は概念的にそれほど難しくはないが、数学的な定義を引き出し数式を記述した理由は、今後具体的に、理論的に話すことが多いためである。

ユークリッド空間 $\mathbb{R}^{p}$ はもちろんベクトル空間であり、内積空間でもあり、内積空間は距離空間であるため距離空間でもある。これを強調するのは、実際のデータの世界で内積空間というのが思ったよりも良い仮定であるためである。例えば、画像や文書、分子構造などをSVMにそのまま入れてもいいのか、頭を悩ませることになる。定義では暗黙のうちに「距離が近い」やベクトルの内積が含まれる線形関数 $f$ を使用しているが、理論に近づくほど、これらの仮定を当然とすることはできない。

サポートベクター

元々このような幾何問題では、境界^boundary上にあるものをサポートと呼ぶが、例えば最小包含円問題でも円を決定する円周上の点をサポートとする。SVMの起源となったサポートベクターも同様で、$\mathbf{x}^{+}, \mathbf{x}^{-}$ は二つの集合 $X^{+}, X^{-}$ の観点から見ても、$\delta/2$ から$X^{+}, X^{-}$ の距離に位置する境界上にある。

サポートベクターが$H$ それぞれで一意である保証はないが、今後の議論で一意性が重要ではないため、一般性を失わずに一意であると仮定しよう。$\left\{ \mathbf{x}_{k} \right\}_{k=1}^{n}$ のマージンにはデータが存在せず、 $$ f \left( \mathbf{x} \right) \begin{cases} \ge +1 & , \text{if } \mathbf{x} \in X^{+} \\ \le -1 & , \text{if } \mathbf{x} \in X^{-} \end{cases} $$ であるため、すべての$\left| f \left( \mathbf{x}_{k} \right) \right| \ge 1$ に対して$H$ でなければならない。

マージンの最大化

サポートベクターは$H$ と最も近い点であるため、$\delta/2$ との距離$H$ はサポートベクターが$\mathbf{w}$ 方向に垂直に離れたときの距離である。このマージンは$\mathbf{x}^{+}$ でも$\mathbf{x}^{-}$ でも同じであり、両方とも超平面$H$ との距離が$\delta/2$ であることは、二つのサポートベクター間の距離が $$ \delta \mathbf{w} = \mathbf{x}^{+} - \mathbf{x}^{-} $$ として表されることを意味する。ここで$\mathbf{x}^{+} - \mathbf{x}^{-}$ のような演算は$X$ がベクトル空間であるという仮定に基づいて許可される。$\delta \mathbf{w} = \mathbf{x}^{+} - \mathbf{x}^{-}$ の両辺に$\mathbf{w}$ と内積を取ると、つまり$\mathbf{w}^{T}$ を左側に掛けると$f$ の定義に従って $$ \begin{align*} & \delta \mathbf{w} = \mathbf{x}^{+} - \mathbf{x}^{-} \\ \implies & \delta \mathbf{w}^{T} \mathbf{w} = \mathbf{w}^{T} \mathbf{x}^{+} - \mathbf{w}^{T} \mathbf{x}^{-} \\ \implies & \delta \left\| \mathbf{w} \right\|_{2}^{2} = \left( \mathbf{w}^{T} \mathbf{x}^{+} + b \right) - \left( \mathbf{w}^{T} \mathbf{x}^{-} + b \right) \\ \implies & \delta \left\| \mathbf{w} \right\|_{2}^{2} = +1 - (-1) \\ \implies & \delta \left\| \mathbf{w} \right\|_{2}^{2} = 2 \\ \implies & \delta = {{ 2 } \over { \left\| \mathbf{w} \right\|_{2}^{2} }} \end{align*} $$ を得る。つまり、マージンを最大化することは目的関数 $\left\| \mathbf{w} \right\|_{2}^{2} / 2$ を最小化することであり、要約するとSVMとは次のような最適化問題を解くオプティマイザー^optimizerである。 $$ \begin{matrix} \text{Minimize} & {{ 1 } \over { 2 }} \left\| \mathbf{w} \right\|_{2}^{2} \\ \text{subject to} & \left| f \left( \mathbf{x}_{k} \right) \right| \ge 1 \end{matrix} \\ k = 1, \cdots , n $$

派生モデル

難しい定義に従えば、SVMは直線であれ超平面であれ、いずれにしても線形関数を見つける線形回帰モデルであるが、当然ながらここで満足するわけがない。

ソフトマージンSVM

例えば、次のようなデータが入ってきたとしよう。SVMはデータが混在している中央部分のために、これを完全に二値分類することができない。

ここで、サポートベクターのマージンにデータが存在できないという制約のもとで$\left| f \left( \mathbf{x}_{k} \right) \right| \ge 1$ という条件を満たさなければならなかったことに注目してみよう。この不等式を$1$ より小さい値に許容すれば、完全な二値分類ではないにしても、完全に諦めるよりは良い結果をもたらすだろう。そして、この許容を各データごとに$\xi_{k} \ge 0$ とすると、新たな制約条件$\left| f \left( \mathbf{x}_{k} \right) \right| \ge 1 - \xi_{k}$ を得る。このように条件が緩和されたマージンをソフトマージン^{soft Margin}という。

もちろん、制約が少し緩和されたとはいえ、すべてを$\xi_{l} = \cdots = \xi_{n} = 1$ にしてしまうとSVM自体を放棄してしまうことになる。これを防ぐためには、目的関数に$\sum_{k} \xi_{k}$ のような項を加えることがある。これは不可能な二値分類を可能にしたことに対する代償^penaltyである。もちろん、このような単純なペナルティはデータのスケールによっては全く意味がなかったり、逆に過敏に反応したりするため、$0 \le \sum_{k} \xi_{k} \le n$ そのままではなく、適切な正の数$\lambda > 0$ を掛けて追加することにしよう。 $$ \begin{matrix} \text{Minimize} & {{ 1 } \over { 2 }} \left\| \mathbf{w} \right\|_{2}^{2} + \lambda \sum_{k=1}^{n} \xi_{k} \\ \text{subject to} & \left| f \left( \mathbf{x}_{k} \right) \right| \ge 1 - \xi_{k} \\ & \xi_{k} \ge 0 \end{matrix} \\ k = 1, \cdots , n $$

カーネルトリック

例えば、上のようなデータが与えられた場合、ソフトマージンであろうとなかろうと、SVMでは決して二値分類することができないように見える。しかし、よく見ると$0$ に近い側には空色の点が集まっており、外側にはオレンジ色の点が現れていることが明らかである。この情報を活用するために、次のように$z$ 軸を新たに作ってみよう。 $$ \phi (x,y) := (x,y, x^{2} + y^{2}) $$

上の図は、下の図を適切にキャプチャしたものである。下はマウスで対話可能な3D空間なので、いろいろと回して見てみてください。

元の$\mathbb{R}^{2}$ ではデータを二分する直線を見つけるのが難しかったが、このようにデータを説明する次元を増やした$\mathbb{R}^{3}$ では、適切な平面でデータを分類するSVMを使用できるようになった。ここで自然に思い浮かぶ疑問は、「それでは、このように便利な変換$\phi$ をカーネル^kernelと呼び、カーネルを使用する方法をカーネルトリック^{kernel Trick}と呼ぶのか？」ということである。半分正しく、半分間違っている。$\phi$ にさらに一歩進んで、内積まで含まれたものがカーネルである。

再びマージンの最大化に戻って、我々に与えられた最適化問題を再検討してみよう。 $$ \begin{matrix} \text{Minimize} & {{ 1 } \over { 2 }} \left\| \mathbf{w} \right\|_{2}^{2} \\ \text{subject to} & \left| f \left( \mathbf{x}_{k} \right) \right| \ge 1 \end{matrix} \\ k = 1, \cdots , n $$

制約条件$\left| f \left( \mathbf{x}_{k} \right) \right| \ge 1$ は見た目はすっきりしているが、実際にこの問題を解く際にはあまり役に立たない。元の学習データセットでの形に戻すと、$k = 1 , \cdots , n$ に対して $$ \begin{cases} f \left( \mathbf{x}_{k} \right) \ge 1 & , \text{if } y_{k} = 1 \\ f \left( \mathbf{x}_{k} \right) \le -1 & , \text{if } y_{k} = -1 \end{cases} \\ \implies \begin{cases} y_{k} \left( \mathbf{w}^{T} \mathbf{x}_{k} + b \right) \ge 1 & , \text{if } y_{k} = 1 \\ y_{k} \left( \mathbf{w}^{T} \mathbf{x}_{k} + b \right) \ge 1 & , \text{if } y_{k} = -1 \end{cases} \\ \implies y_{k} \left( \mathbf{w}^{T} \mathbf{x}_{k} + b \right) \ge 1 $$ でなければならない。このような制約条件自体を目的関数に反映させて、制約条件がないかのように扱う方法がラグランジュ乗数法である。$y_{k} \left( \mathbf{w}^{T} \mathbf{x}_{k} + b \right) - 1 \ge 0$ に$\alpha_{k} \ge 0$ を掛けた項を元の目的関数から引いた$L(\mathbf{w}, b)$ に対して、次の最適化問題を得る。 $$ \begin{matrix} \text{Minimize} & {{ 1 } \over { 2 }} \left\| \mathbf{w} \right\|_{2}^{2} - \sum_{k=1}^{n} \alpha_{k} \left[ y_{k} \left( \mathbf{w}^{T} \mathbf{x}_{k} + b \right) - 1 \right] \\ \text{subject to} & \alpha_{k} \ge 0 \end{matrix} \\ k = 1, \cdots , n $$

再び強調するが、我々の目的はこの目的関数を最小化する$\mathbf{w}, b$ を見つけることであった。$\mathbf{w}, b$ に対する目的関数の偏微分が$0$ となる条件は次の通りである。 $$ \begin{align*} {{ \partial L } \over { \partial \mathbf{w} }} = 0 \implies & \mathbf{w} = \sum_{k=1}^{n} \alpha_{k} y_{k} \mathbf{x}_{k} \\ {{ \partial L } \over { \partial b }} = 0 \implies & 0 = \sum_{k=1}^{n} \alpha_{k} y_{k} \end{align*} $$

これをそのまま$L$ に代入してみると $$ \begin{align*} & L(\mathbf{w},b) \\ =& {{ 1 } \over { 2 }} \left\| \mathbf{w} \right\|_{2}^{2} - \sum_{k=1}^{n} \alpha_{k} \left[ y_{k} \left( \mathbf{w}^{T} \mathbf{x}_{k} + b \right) - 1 \right] \\ =& {{ 1 } \over { 2 }} \mathbf{w}^{T} \mathbf{w} - \sum_{k=1}^{n} \alpha_{k} y_{k} \left( \mathbf{w}^{T} \mathbf{x}_{k} + b \right) + \sum_{k=1}^{n} \alpha_{k} \\ =& {{ 1 } \over { 2 }} \mathbf{w}^{T} \sum_{k=1}^{n} \alpha_{k} y_{k} \mathbf{x}_{k} - \sum_{k=1}^{n} \alpha_{k} y_{k}\mathbf{w}^{T} \mathbf{x}_{k} - b \sum_{k=1}^{n} \alpha_{k} y_{k} - \sum_{k=1}^{n} \alpha_{k} \\ =& - {{ 1 } \over { 2 }} \sum_{k=1}^{n} \alpha_{k} y_{k} \mathbf{w}^{T} \mathbf{x}_{k} - b \cdot 0 + \sum_{k=1}^{n} \alpha_{k} \\ =& \sum_{k=1}^{n} \alpha_{k} - {{ 1 } \over { 2 }} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} y_{i} a_{j} y_{j} \mathbf{x}_{i}^{T} \mathbf{x}_{j} \\ =& \sum_{k=1}^{n} \alpha_{k} - {{ 1 } \over { 2 }} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} a_{j} y_{i} y_{j} \mathbf{x}_{i}^{T} \mathbf{x}_{j} \\ =& L \left( \alpha_{1} , \cdots , \alpha_{n} \right) \end{align*} $$

を得る。当然ながら、具体的な$\mathbf{w}$ と$b$ を計算するためには、学習データ$\left\{ \left( \mathbf{x}_{k}, y_{k} \right) \right\}_{k=1}^{n}$ が必要である。

ここで注目すべき点は、数式で$\mathbf{x}_{i}$ と$\mathbf{x}_{j}$ の内積が使用されていることである。結局のところ、最終的に、我々は内積を取らなければならず、$X$ が内積空間でなければ、このように順調に進む保証はない。逆に言えば、$X$ が内積空間でなくても、変換$\phi$ が$X$ を内積空間に送ることができれば、その目的関数が $$ \sum_{k=1}^{n} \alpha_{k} - {{ 1 } \over { 2 }} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} a_{j} y_{i} y_{j} \phi \left( \mathbf{x}_{i} \right) ^{T} \phi \left( \mathbf{x}_{j} \right) $$ であるSVMを検討する価値がある。機械学習では、このように二つのベクトルに対する変換、内積まで含まれた関数 $$ K \left( \mathbf{x}_{i}, \mathbf{x}_{j} \right) := \left< \phi \left( \mathbf{x}_{i} \right) , \phi \left( \mathbf{x}_{j} \right) \right> $$ をカーネル^kernelと呼ぶこともある。[ 注: データサイエンスでは、これと混同される別のカーネルも存在する。元々、数学全般でのカーネルは、名前は同じでも全く異なる機能の関数である。 ]

数式的にここまでの内容を受け入れることができれば、なぜカーネルではなく変換$\phi$ を導入することをカーネルトリックと呼び、変換後に内積空間であることが保証されることが重要なのかを理解したことになる。

条件を満たす限り、カーネルはいくつかの種類を考えることができる。特に元のSVMも線形カーネル^{linear Kernel} $$ K \left( \mathbf{x}_{i}, \mathbf{x}_{j} \right) = \left< \mathbf{x}_{i}, \mathbf{x}_{j} \right>^{1} = \mathbf{x}_{i}^{T} \mathbf{x}_{j} $$ を使用したものと見なすことができる。

参照

カーネルトリックの部分で数学的に簡単な内容を扱ったが、より深い理論に興味がある場合は、SVMを超えて以下の内容を学ぶことをお勧めする。

• 機械学習におけるカーネルと再生カーネルヒルベルト空間
• 表現者定理の証明

コード

以下はカーネルトリックを実装したJuliaのコードである。

struct Sphere
    d::Int64
end
Sphere(d) = Sphere(d)

import Base.rand
function rand(Topology::Sphere, n::Int64)
    direction = randn(Topology.d, n)
    boundary = direction ./ sqrt.(sum(abs2, direction, dims = 1))
    return boundary
end

using Plots
A = 0.3rand(Sphere(2), 200) + 0.1randn(2, 200)
B = rand(Sphere(2), 200) + 0.1randn(2, 200)

scatter(A[1,:],A[2,:], ratio = :equal, label = "+1")
scatter!(B[1,:],B[2,:], ratio = :equal, label = "-1")
png("raw.png")

Plots.plotly()
ϕ(z) = z[1]^2 + z[2]^2
scatter(A[1,:],A[2,:],ϕ.(eachcol(A)), ms = 1, label = "+1")
scatter!(B[1,:],B[2,:],ϕ.(eachcol(B)), ms = 1, label = "-1")
savefig("kernel.html")