logo

サポートベクターマシン 📂機械学習

サポートベクターマシン

モデル 1

簡単な定義

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

難しい定義

内積空間 X=RpX = \mathbb{R}^{p} とラベリングlabeling Y={−1,+1}Y = \left\{ -1, +1 \right\} に対し、nn 個のデータを集めた学習データセットtraining Datasetを D={(xk,yk)}k=1n⊂X×YD = \left\{ \left( \mathbf{x}_{k} , y_{k} \right) \right\}_{k=1}^{n} \subset X \times Y とし、 X+:={xk∈X:yk=+1}X−:={xk∈X:yk=−1} \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 w∈Rp\mathbf{w} \in \mathbb{R}^{p} とバイアスbias b∈Rb \in \mathbb{R} を持つ線形関数 f(x)=wTx+bf \left( \mathbf{x} \right) = \mathbf{w}^{T} \mathbf{x} + b によって作られる超平面を H:wTx+b=0H : \mathbf{w}^{T} \mathbf{x} + b = 0 とするとき、HH と最も距離が近い x+∈X+\mathbf{x}^{+} \in X^{+} と x−∈X−\mathbf{x}^{-} \in X^{-} をサポートベクターsupport Vectorといい、これらの間の距離 δ\delta をマージンmarginという。これに対して f(x+)=+1f(x−)=−1 \begin{align*} f \left( \mathbf{x}^{+} \right) =& +1 \\ f \left( \mathbf{x}^{-} \right) =& -1 \end{align*}

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

説明

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

20220225_015438.png

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

20220225_014703.png

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

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

内積空間

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

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

サポートベクター

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

サポートベクターがHH それぞれで一意である保証はないが、今後の議論で一意性が重要ではないため、一般性を失わずに一意であると仮定しよう。{xk}k=1n\left\{ \mathbf{x}_{k} \right\}_{k=1}^{n} のマージンにはデータが存在せず、 f(x){≥+1,if x∈X+≤−1,if x∈X− 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} であるため、すべての∣f(xk)∣≥1\left| f \left( \mathbf{x}_{k} \right) \right| \ge 1 に対してHH でなければならない。

マージンの最大化

サポートベクターはHH と最も近い点であるため、δ/2\delta/2 との距離HH はサポートベクターがw\mathbf{w} 方向に垂直に離れたときの距離である。このマージンはx+\mathbf{x}^{+} でもx−\mathbf{x}^{-} でも同じであり、両方とも超平面HH との距離がδ/2\delta/2 であることは、二つのサポートベクター間の距離が δw=x+−x− \delta \mathbf{w} = \mathbf{x}^{+} - \mathbf{x}^{-} として表されることを意味する。ここでx+−x−\mathbf{x}^{+} - \mathbf{x}^{-} のような演算はXX がベクトル空間であるという仮定に基づいて許可される。δw=x+−x−\delta \mathbf{w} = \mathbf{x}^{+} - \mathbf{x}^{-} の両辺にw\mathbf{w} と内積を取ると、つまりwT\mathbf{w}^{T} を左側に掛けるとff の定義に従って δw=x+−x−  ⟹  δwTw=wTx+−wTx−  ⟹  δ∥w∥22=(wTx++b)−(wTx−+b)  ⟹  δ∥w∥22=+1−(−1)  ⟹  δ∥w∥22=2  ⟹  δ=2∥w∥22 \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*} を得る。つまり、マージンを最大化することは目的関数 ∥w∥22/2\left\| \mathbf{w} \right\|_{2}^{2} / 2 を最小化することであり、要約するとSVMとは次のような最適化問題を解くオプティマイザーoptimizerである。 Minimize12∥w∥22subject to∣f(xk)∣≥1k=1,⋯ ,n \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はデータが混在している中央部分のために、これを完全に二値分類することができない。

20220225_030646.png

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

もちろん、制約が少し緩和されたとはいえ、すべてをξl=⋯=ξn=1\xi_{l} = \cdots = \xi_{n} = 1 にしてしまうとSVM自体を放棄してしまうことになる。これを防ぐためには、目的関数に∑kξk\sum_{k} \xi_{k} のような項を加えることがある。これは不可能な二値分類を可能にしたことに対する代償penaltyである。もちろん、このような単純なペナルティはデータのスケールによっては全く意味がなかったり、逆に過敏に反応したりするため、0≤∑kξk≤n0 \le \sum_{k} \xi_{k} \le n そのままではなく、適切な正の数λ>0\lambda > 0 を掛けて追加することにしよう。 Minimize12∥w∥22+λ∑k=1nξksubject to∣f(xk)∣≥1−ξkξk≥0k=1,⋯ ,n \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

カーネルトリック

raw.png

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

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

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

再びマージンの最大化に戻って、我々に与えられた最適化問題を再検討してみよう。 Minimize12∥w∥22subject to∣f(xk)∣≥1k=1,⋯ ,n \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

制約条件∣f(xk)∣≥1\left| f \left( \mathbf{x}_{k} \right) \right| \ge 1 は見た目はすっきりしているが、実際にこの問題を解く際にはあまり役に立たない。元の学習データセットでの形に戻すと、k=1,⋯ ,nk = 1 , \cdots , n に対して {f(xk)≥1,if yk=1f(xk)≤−1,if yk=−1  ⟹  {yk(wTxk+b)≥1,if yk=1yk(wTxk+b)≥1,if yk=−1  ⟹  yk(wTxk+b)≥1 \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 でなければならない。このような制約条件自体を目的関数に反映させて、制約条件がないかのように扱う方法がラグランジュ乗数法である。yk(wTxk+b)−1≥0y_{k} \left( \mathbf{w}^{T} \mathbf{x}_{k} + b \right) - 1 \ge 0 にαk≥0\alpha_{k} \ge 0 を掛けた項を元の目的関数から引いたL(w,b)L(\mathbf{w}, b) に対して、次の最適化問題を得る。 Minimize12∥w∥22−∑k=1nαk[yk(wTxk+b)−1]subject toαk≥0k=1,⋯ ,n \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

再び強調するが、我々の目的はこの目的関数を最小化するw,b\mathbf{w}, b を見つけることであった。w,b\mathbf{w}, b に対する目的関数の偏微分が00 となる条件は次の通りである。 ∂L∂w=0  ⟹  w=∑k=1nαkykxk∂L∂b=0  ⟹  0=∑k=1nαkyk \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*}

これをそのままLL に代入してみると L(w,b)=12∥w∥22−∑k=1nαk[yk(wTxk+b)−1]=12wTw−∑k=1nαkyk(wTxk+b)+∑k=1nαk=12wT∑k=1nαkykxk−∑k=1nαkykwTxk−b∑k=1nαkyk−∑k=1nαk=−12∑k=1nαkykwTxk−b⋅0+∑k=1nαk=∑k=1nαk−12∑i=1n∑j=1nαiyiajyjxiTxj=∑k=1nαk−12∑i=1n∑j=1nαiajyiyjxiTxj=L(α1,⋯ ,αn) \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*}

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

ここで注目すべき点は、数式でxi\mathbf{x}_{i} とxj\mathbf{x}_{j} の内積が使用されていることである。結局のところ、最終的に、我々は内積を取らなければならず、XX が内積空間でなければ、このように順調に進む保証はない。逆に言えば、XX が内積空間でなくても、変換ϕ\phi がXX を内積空間に送ることができれば、その目的関数が ∑k=1nαk−12∑i=1n∑j=1nαiajyiyjϕ(xi)Tϕ(xj) \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(xi,xj):=<ϕ(xi),ϕ(xj)> 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(xi,xj)=<xi,xj>1=xiTxj 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")

  1. Jakkula. (2006). サポートベクターマシン（SVM）に関するチュートリアル. https://course.ccs.neu.edu/cs5100f11/resources/jakkula.pdf ↩︎

  2. https://ratsgo.github.io/machine%20learning/2017/05/23/SVM/ ↩︎

  3. https://bkshin.tistory.com/entry/%EB%A8%B8%EC%8B%A0%EB%9F%AC%EB%8B%9D-2%EC%84%9C%ED%8F%AC%ED%8A%B8-%EB%B2%A1%ED%84%B0-%EB%A8%B8%EC%8B%A0-SVM ↩︎

  4. https://hleecaster.com/ml-svm-concept/ ↩︎