サポートベクターマシン

トレーニングデータが線形分離可能であれば、2つのデータクラスを分離する2つの平行な超平面を選択し、それらの間の距離が最大になるようにします。これら2つの超平面で囲まれた領域を「マージン」と呼び、最大マージン超平面はそれらの中間にある超平面です。正規化または標準化されたデータセットの場合、これらの超平面は次の式で表すことができます。

${\displaystyle \mathbf {w} ^{\mathsf {T}}\mathbf {x} -b=1}$（この境界線上または境界線より上にあるものはすべて、ラベル1のクラスに属します）

そして

${\displaystyle \mathbf {w} ^{\mathsf {T}}\mathbf {x} -b=-1}$（この境界線上または境界線より下にあるものはすべて別のクラスに属し、ラベルは-1です。）

幾何学的に、これら2つの超平面間の距離は${\displaystyle {\tfrac {2}{\|\mathbf {w} \|}}}$[ ^{21 ]平面間の距離を最大化するには、}最小化したい${\displaystyle \|\mathbf {w} \|}$距離は、点から平面までの距離の式を使用して計算されます。また、データ点が余白に落ちないようにする必要があるため、次の制約を追加します。各${\displaystyle i}$どちらか $${\displaystyle \mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b\geq 1\,,{\text{ if }}y_{i}=1,}$$ または $${\displaystyle \mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b\leq -1\,,{\text{ if }}y_{i}=-1.}$$ これらの制約は、各データポイントがマージンの正しい側に位置しなければならないことを規定している。

これは次のように書き換えることができます。

これらを組み合わせると、最適化問題が得られます。

${\displaystyle {\begin{aligned}&{\underset {\mathbf {w} ,\;b}{\operatorname {minimize} }}&&{\frac {1}{2}}\|\mathbf {w} \|^{2}\\&{\text{subject to}}&&y_{i}(\mathbf {w} ^{\top }\mathbf {x} _{i}-b)\geq 1\quad \forall i\in \{1,\dots ,n\}\end{aligned}}}$

の${\displaystyle \mathbf {w} }$そして${\displaystyle b}$この問題を解決する最終的な分類器を決定する${\displaystyle \mathbf {x} \mapsto \operatorname {sgn}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} -b)}$、 どこ${\displaystyle \operatorname {sgn}(\cdot )}$は符号関数です。

この幾何学的記述の重要な帰結は、最大マージン超平面がそれらによって完全に決定されるということである。${\displaystyle \mathbf {x} _{i}}$それに最も近いもの（下記参照）。${\displaystyle \mathbf {x} _{i}}$これらはサポートベクターと呼ばれます。

データが線形分離可能でないケースにSVMを拡張するには、ヒンジ損失関数が役立ちます。 $${\displaystyle \max \left(0,1-y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b)\right).}$$

ご了承ください$\displaystyle y_{i}}$はi番目のターゲット（つまり、この場合は 1 または -1）であり、${\displaystyle \mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b}$これはi番目の出力です。

この関数は、 (1)の制約が満たされる場合、つまり、${\displaystyle \mathbf {x} _{i}}$データは余白の正しい側に位置する。余白の間違った側に位置するデータの場合、関数の値は余白からの距離に比例する。

最適化の目標は、以下を最小化することです。

$${\displaystyle \lVert \mathbf {w} \rVert ^{2}+C\left[{\frac {1}{n}}\sum _{i=1}^{n}\max \left(0,1-y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b)\right)\right],}$$

パラメータ${\displaystyle C>0}$マージンサイズを増やすことと、${\displaystyle \mathbf {x} _{i}}$余白の正しい側に位置する（上記の式ではどちらの項にも重みを追加できることに注意してください）。ヒンジ損失を分解することで、この最適化問題は次のように定式化できます。

$${\displaystyle {\begin{aligned}&{\underset {\mathbf {w} ,\;b,\;\mathbf {\zeta } }{\operatorname {minimize} }}&&\|\mathbf {w} \|_{2}^{2}+C\sum _{i=1}^{n}\zeta _{i}\\&{\text{subject to}}&&y_{i}(\mathbf {w} ^{\top }\mathbf {x} _{i}-b)\geq 1-\zeta _{i},\quad \zeta _{i}\geq 0\quad \forall i\in \{1,\dots ,n\}\end{aligned}}}$$

したがって、大きな値の場合${\displaystyle C}$入力データが線形に分類可能であれば、ハードマージンSVMと同様の動作をしますが、分類ルールが有効かどうかを学習します。

（２）を最小化する問題は、微分可能な目的関数を持つ制約付き最適化問題として次のように書き換えることができる。

各${\displaystyle i\in \{1,\,\ldots ,\,n\}}$変数を導入します${\displaystyle \zeta _{i}=\max \left(0,1-y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b)\right)}$。 ご了承ください${\displaystyle \zeta _{i}}$を満たす最小の非負数${\displaystyle y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b)\geq 1-\zeta _{i}.}$

したがって、最適化問題を次のように書き換えることができます。

$${\displaystyle {\begin{aligned}&{\text{minimize }}{\frac {1}{n}}\sum _{i=1}^{n}\zeta _{i}+\lambda \|\mathbf {w} \|^{2}\\[0.5ex]&{\text{subject to }}y_{i}\left(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b\right)\geq 1-\zeta _{i}\,{\text{ and }}\,\zeta _{i}\geq 0,\,{\text{for all }}i.\end{aligned}}}$$

これは原始問題と呼ばれる。

上記の問題のラグランジュ双対を解くことにより、簡略化された問題が得られる。

$${\displaystyle {\begin{aligned}&{\text{maximize}}\,\,f(c_{1}\ldots c_{n})=\sum _{i=1}^{n}c_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}c_{i}(\mathbf {x} _{i}^{\mathsf {T}}\mathbf {x} _{j})y_{j}c_{j},\\&{\text{subject to }}\sum _{i=1}^{n}c_{i}y_{i}=0,\,{\text{and }}0\leq c_{i}\leq {\frac {1}{2n\lambda }}\;{\text{for all }}i.\end{aligned}}}$$

これは双対問題と呼ばれます。双対最大化問題は、${\displaystyle c_{i}}$線形制約条件の下では、二次計画法アルゴリズムによって効率的に解くことができる。

ここでは、変数${\displaystyle c_{i}}$は次のように定義される。

$${\displaystyle \mathbf {w} =\sum _{i=1}^{n}c_{i}y_{i}\mathbf {x} _{i}.}$$

さらに、${\displaystyle c_{i}=0}$正確にはいつ${\displaystyle \mathbf {x} _{i}}$余白の正しい側に位置し、${\displaystyle 0<c_{i}<(2n\lambda )^{-1}}$ いつ${\displaystyle \mathbf {x} _{i}}$は境界上に位置する。したがって、${\displaystyle \mathbf {w} }$これは、サポートベクトルの線形結合として表すことができる。

オフセット、${\displaystyle b}$は、${\displaystyle \mathbf {x} _{i}}$マージンの境界上で解決する $${\displaystyle y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b)=1\iff b=\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-y_{i}.}$$

（ご了承ください${\displaystyle y_{i}^{-1}=y_{i}}$以来${\displaystyle y_{i}=\pm 1}$）

ここで、変換されたデータポイントに対する線形分類ルールに対応する非線形分類ルールを学習したいと仮定します。${\displaystyle \varphi (\mathbf {x} _{i}).}$さらに、カーネル関数が与えられている。${\displaystyle k}$これは以下を満たす${\displaystyle k(\mathbf {x} _{i},\mathbf {x} _{j})=\varphi (\mathbf {x} _{i})\cdot \varphi (\mathbf {x} _{j})}$。

分類ベクトルはわかっています${\displaystyle \mathbf {w} }$変換された空間では、

$${\displaystyle \mathbf {w} =\sum _{i=1}^{n}c_{i}y_{i}\varphi (\mathbf {x} _{i}),}$$

そこで、${\displaystyle c_{i}}$最適化問題を解くことによって得られる

$${\displaystyle {\begin{aligned}{\text{maximize}}\,\,f(c_{1}\ldots c_{n})&=\sum _{i=1}^{n}c_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}c_{i}(\varphi (\mathbf {x} _{i})\cdot \varphi (\mathbf {x} _{j}))y_{j}c_{j}\\&=\sum _{i=1}^{n}c_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}c_{i}k(\mathbf {x} _{i},\mathbf {x} _{j})y_{j}c_{j}\\{\text{subject to }}\sum _{i=1}^{n}c_{i}y_{i}&=0,\,{\text{and }}0\leq c_{i}\leq {\frac {1}{2n\lambda }}\;{\text{for all }}i.\end{aligned}}}$$

係数${\displaystyle c_{i}}$以前と同様に、二次計画法を用いて解くことができます。ここでも、いくつかのインデックスを見つけることができます。${\displaystyle i}$そのため${\displaystyle 0<c_{i}<(2n\lambda )^{-1}}$、 となることによって${\displaystyle \varphi (\mathbf {x} _{i})}$変換された空間の境界上に位置し、そして解決する

$${\displaystyle {\begin{aligned}b=\mathbf {w} ^{\mathsf {T}}\varphi (\mathbf {x} _{i})-y_{i}&=\left[\sum _{j=1}^{n}c_{j}y_{j}\varphi (\mathbf {x} _{j})\cdot \varphi (\mathbf {x} _{i})\right]-y_{i}\\&=\left[\sum _{j=1}^{n}c_{j}y_{j}k(\mathbf {x} _{j},\mathbf {x} _{i})\right]-y_{i}.\end{aligned}}}$$

ついに、

$${\displaystyle \mathbf {z} \mapsto \operatorname {sgn}(\mathbf {w} ^{\mathsf {T}}\varphi (\mathbf {z} )-b)=\operatorname {sgn} \left(\left[\sum _{i=1}^{n}c_{i}y_{i}k(\mathbf {x} _{i},\mathbf {z} )\right]-b\right).}$$

SVM分類器を見つけるための最近のアルゴリズムには、劣勾配降下法と座標降下法があります。これらの手法はどちらも、大規模で疎なデータセットを扱う際に、従来の手法に比べて大きな利点があることが証明されています。劣勾配法は訓練例が多い場合に特に効率的であり、座標降下法は特徴空間の次元が高い場合に有効です。

教師あり学習では、一連の訓練例が与えられる。${\displaystyle X_{1}\ldots X_{n}}$ラベル付き${\displaystyle y_{1}\ldots y_{n}}$予測したい${\displaystyle y_{n+1}}$与えられた${\displaystyle X_{n+1}}$そのために仮説を立てる。${\displaystyle f}$、したがって${\displaystyle f(X_{n+1})}$は「良い」近似値である${\displaystyle y_{n+1}}$「良い」近似は通常、損失関数を用いて定義される。${\displaystyle \ell (y,z)}$これは、どれほど悪いかを表しています${\displaystyle z}$予測として${\displaystyle y}$そこで、期待リスクを最小化する仮説を選択したいと思います。

$${\displaystyle \varepsilon (f)=\mathbb {E} \left[\ell (y_{n+1},f(X_{n+1}))\right].}$$

ほとんどの場合、私たちは同時分布を知りません${\displaystyle X_{n+1},\,y_{n+1}}$率直に。このような場合、一般的な戦略は、実証的リスクを最小限に抑える仮説を選択することである。

$${\displaystyle {\hat {\varepsilon }}(f)={\frac {1}{n}}\sum _{k=1}^{n}\ell (y_{k},f(X_{k})).}$$

確率変数のシーケンスに関する特定の仮定の下で${\displaystyle X_{k},\,y_{k}}$（例えば、有限マルコフ過程によって生成されるなど）、検討されている仮説の集合が十分に小さい場合、経験的リスクの最小値は期待リスクの最小値に非常に近い値になります。${\displaystyle n}$規模が大きくなる。このアプローチは経験的リスク最小化、またはERMと呼ばれる。

最小化問題が明確な解を持つためには、集合に制約を設ける必要がある。${\displaystyle {\mathcal {H}}}$検討されている仮説の。${\displaystyle {\mathcal {H}}}$がノルム空間である場合（SVMの場合と同様）、特に効果的な手法は、仮説のみを考慮することです。${\displaystyle f}$そのために${\displaystyle \lVert f\rVert _{\mathcal {H}}<k}$これは正規化ペナルティを課すことと同等である。${\displaystyle {\mathcal {R}}(f)=\lambda _{k}\lVert f\rVert _{\mathcal {H}}}$そして、新しい最適化問題を解決する

$${\displaystyle {\hat {f}}=\mathrm {arg} \min _{f\in {\mathcal {H}}}{\hat {\varepsilon }}(f)+{\mathcal {R}}(f).}$$

この手法はチホノフ正則化と呼ばれます。

より一般的には、${\displaystyle {\mathcal {R}}(f)}$仮説の複雑さの尺度となり得る${\displaystyle f}$そのため、より単純な仮説が好まれる。

(ソフトマージン)SVM分類器を思い出してください${\displaystyle {\hat {\mathbf {w} }},b:\mathbf {x} \mapsto \operatorname {sgn}({\hat {\mathbf {w} }}^{\mathsf {T}}\mathbf {x} -b)}$次の式を最小化するように選択されます。

$${\displaystyle \left[{\frac {1}{n}}\sum _{i=1}^{n}\max \left(0,1-y_{i}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} -b)\right)\right]+\lambda \|\mathbf {w} \|^{2}.}$$

上記の議論を踏まえると、SVM手法は、チホノフ正則化を用いた経験的リスク最小化と同等であり、この場合、損失関数はヒンジ損失となることがわかる。

$${\displaystyle \ell (y,z)=\max \left(0,1-yz\right).}$$

この観点から、SVMは正則化最小二乗法やロジスティック回帰などの他の基本的な分類アルゴリズムと密接に関連している。3つの違いは損失関数の選択にある。正則化最小二乗法は二乗損失による経験的リスク最小化に相当する。 ${\displaystyle \ell _{sq}(y,z)=(y-z)^{2}}$; ロジスティック回帰では対数損失を採用します。

$${\displaystyle \ell _{\log }(y,z)=\ln(1+e^{-yz}).}$$

SVMの有効性は、カーネルの選択、カーネルのパラメータ、およびソフトマージンパラメータに依存します。${\displaystyle \lambda }$一般的な選択肢はガウスカーネルであり、これは単一のパラメータを持つ。${\displaystyle \gamma }$最高の組み合わせ${\displaystyle \lambda }$そして${\displaystyle \gamma }$は、指数関数的に増加するシーケンスによるグリッドサーチによって選択されることが多い。${\displaystyle \lambda }$そして${\displaystyle \gamma }$、 例えば、${\displaystyle \lambda \in \{2^{-5},2^{-3},\dots ,2^{13},2^{15}\}}$;${\displaystyle \gamma \in \{2^{-15},2^{-13},\dots ,2^{1},2^{3}\}}$通常、パラメータ選択の各組み合わせは交差検証を使用してチェックされ、交差検証精度が最も高いパラメータが選択されます。あるいは、ベイズ最適化の最近の研究を使用して選択することもできます。${\displaystyle \lambda }$そして${\displaystyle \gamma }$グリッドサーチよりもはるかに少ないパラメータの組み合わせを評価するだけで済む場合が多い。テストや新しいデータの分類に使用される最終モデルは、選択されたパラメータを使用してトレーニングセット全体でトレーニングされる。^{[ 29 ]}

SVMの潜在的な欠点としては、以下の点が挙げられます。

• 入力データの完全なラベル付けが必要です
• 未較正のクラス帰属確率― SVMは、有限データ上で確率を推定することを避けるVapnikの理論に由来する。
• SVMは2クラス分類タスクにのみ直接適用可能です。そのため、多クラス分類タスクを複数の二値分類問題に分解するアルゴリズムを適用する必要があります。詳細については、多クラスSVMのセクションを参照してください。
• 解かれたモデルのパラメータは解釈が難しい。

多クラスSVMは、サポートベクターマシンを用いてインスタンスにラベルを割り当てることを目的としており、ラベルは有限個の要素の集合から抽出されます。

そのための主流のアプローチは、単一の多クラス問題を複数の二値分類問題に縮小することです。^{[ 30 ]}このような縮小の一般的な方法には、次のものがあります。^{[ 30 ] [ 31 ]}

• ラベルの 1 つと残りのラベルを区別する ( 1 対 全員) またはクラスのすべてのペアを区別する ( 1 対 1 ) バイナリ分類器を構築します。1 対 全員の場合、新しいインスタンスの分類は勝者総取り戦略によって行われ、出力関数が最も高い分類器がクラスを割り当てます (出力関数が同等のスコアを生成するように調整されていることが重要です)。1 対 1 アプローチの場合、分類は最大勝利投票戦略によって行われ、各分類器がインスタンスを 2 つのクラスのいずれかに割り当て、割り当てられたクラスの投票が 1 つ増加し、最終的に最も多くの票を獲得したクラスがインスタンスの分類を決定します。
• 有向非巡回グラフSVM（DAGSVM）^{[ 32 ]}
• エラー訂正出力コード^{[ 33 ]}

CrammerとSingerは、多クラス分類問題を複数の二値分類問題に分解するのではなく、単一の最適化問題に変換する多クラスSVM手法を提案した。^{[ 34 ] Lee、Lin、Wahba [ 35 ] [ 36 ]}およびVan den BurgとGroenen ^{[ 37 ]}も参照のこと。

トランスダクティブサポートベクターマシンは、トランスダクションの原理に従うことで、半教師あり学習において部分的にラベル付けされたデータも扱うことができるという点で、SVMを拡張したものです。ここでは、トレーニングセットに加えて、${\displaystyle {\mathcal {D}}}$学習者には、セットも与えられます

$${\displaystyle {\mathcal {D}}^{\star }=\{\mathbf {x} _{i}^{\star }\mid \mathbf {x} _{i}^{\star }\in \mathbb {R} ^{p}\}_{i=1}^{k}}$$

分類されるテスト例の数。形式的には、トランスダクティブサポートベクターマシンは、次の主最適化問題によって定義されます。^{[ 38 ]}

最小化する（${\displaystyle \mathbf {w} ,b,\mathbf {y} ^{\star }}$）

$${\displaystyle {\frac {1}{2}}\|\mathbf {w} \|^{2}}$$

（いかなる場合でも）${\displaystyle i=1,\dots ,n}$そしてどんな${\displaystyle j=1,\dots ,k}$）

$${\displaystyle {\begin{aligned}&y_{i}(\mathbf {w} \cdot \mathbf {x} _{i}-b)\geq 1,\\&y_{j}^{\star }(\mathbf {w} \cdot \mathbf {x} _{j}^{\star }-b)\geq 1,\end{aligned}}}$$

そして

$${\displaystyle y_{j}^{\star }\in \{-1,1\}.}$$

トランスダクティブサポートベクターマシンは、1998年にウラジミール・N・ヴァプニクによって導入された。

構造化サポートベクターマシンは、従来のSVMモデルの拡張です。SVMモデルは主に二値分類、多クラス分類、回帰タスク向けに設計されていますが、構造化SVMは、構文解析ツリー、分類体系による分類、配列アライメントなど、一般的な構造化出力ラベルを扱うようにその適用範囲を広げています。^{[ 39 ]}

回帰のためのSVMのバージョンは、1996年にウラジミール・N・ヴァプニク、ハリス・ドラッカー、クリストファー・J・C・バージェス、リンダ・カウフマン、アレクサンダー・J・スモラによって提案されました。^{[ 40 ]}この方法はサポートベクター回帰（SVR）と呼ばれます。サポートベクター分類（上記で説明したとおり）によって生成されるモデルは、トレーニングデータのサブセットのみに依存します。これは、モデルを構築するためのコスト関数が、マージンを超えたトレーニングポイントを考慮しないためです。同様に、SVRによって生成されるモデルは、トレーニングデータのサブセットのみに依存します。これは、モデルを構築するためのコスト関数が、モデル予測に近いトレーニングデータを無視するためです。最小二乗サポートベクターマシン（LS-SVM）として知られる別のSVMバージョンが、スイケンスとヴァンデウォールによって提案されています。^{[ 41 ]}

元のSVRをトレーニングすることは、^{[ 42 ]を解くことを意味します。}

最小限に抑える${\displaystyle {\tfrac {1}{2}}\|w\|^{2}}$

対象${\displaystyle |y_{i}-\langle w,x_{i}\rangle -b|\leq \varepsilon }$

どこ${\displaystyle x_{i}}$目標値を持つトレーニングサンプルです${\displaystyle y_{i}}$内積＋切片${\displaystyle \langle w,x_{i}\rangle +b}$これはそのサンプルに対する予測値であり、${\displaystyle \varepsilon }$は閾値として機能する自由パラメータです。すべての予測は の範囲内である必要があります。${\displaystyle \varepsilon }$真の予測値の範囲。通常、上記の式には、誤差を許容し、上記の問題が実行不可能な場合に近似を可能にするために、スラック変数が追加されます。

2011年にPolsonとScottは、データ拡張の手法によってSVMがベイズ的解釈を許容することを示した。^{[ 43 ]}このアプローチでは、SVMはグラフィカルモデル（パラメータが確率分布を介して接続されている）として見なされる。この拡張されたビューにより、柔軟な特徴モデリング、自動ハイパーパラメータチューニング、予測不確実性定量化などのベイズ的手法をSVMに適用できる。2017年に、 Florian WenzelによってスケーラブルなベイズSVMが開発され、ベイズSVMをビッグデータに適用できるようになった。^{[ 44 ]} Florian Wenzelは、ベイズカーネルサポートベクターマシン（SVM）の変分推論（VI）スキームと線形ベイズSVMの確率的バージョン（SVI）の2つの異なるバージョンを開発した。^{[ 45 ]}