サポートベクターマシン

機械学習において、サポートベクターマシン（SVM、サポートベクターネットワーク^[1]とも呼ばれる）は、分類と回帰分析のためにデータを分析する学習アルゴリズムを備えた教師あり 最大マージンモデルです。AT &Tベル研究所で開発された^{[1] [2] SVMは、} Vapnik（1982、1995）とChervonenkis （1974）によって提案されたVC理論の統計学習フレームワークに基づいており、最も研究されているモデルの1つです。

SVMは、線形分類の実行に加えて、カーネルトリックを使用して非線形分類を効率的に実行できます。カーネルトリックでは、カーネル関数を使用して元のデータポイント間の一連のペアワイズ類似性比較のみでデータを表し、カーネル関数はそれらを高次元の特徴空間の座標に変換します。したがって、SVMはカーネルトリックを使用して、入力を線形分類を実行できる高次元の特徴空間に暗黙的にマッピングします。^[3]最大マージンモデルであるSVMは、ノイズの多いデータ（誤分類された例など）に対して耐性があります。SVMは、目的がに敏感になる回帰タスク にも使用できます。 ${\displaystyle \epsilon }$

Hava SiegelmannとVladimir Vapnikによって開発されたサポートベクタークラスタリング^[4]アルゴリズムは、サポートベクターマシンアルゴリズムで開発されたサポートベクターの統計を適用して、ラベルなしデータを分類します。^[要出典]これらのデータセットには、データの自然なグループへのクラスタリングを見つけ、それらのクラスタに従って新しいデータをマッピングしようとする教師なし学習 アプローチが必要です。

SVM が人気なのは、理論的分析への適応性と、構造化予測問題を含むさまざまなタスクに適用できる柔軟性によるものと考えられます。SVM がロジスティック回帰や線形回帰などの他の線形モデルよりも優れた予測性能を持っているかどうかは明らかではありません。^[要出典]

データの分類は、機械学習における一般的なタスクです。いくつかのデータ ポイントがそれぞれ 2 つのクラスのいずれかに属していると仮定し、新しい データ ポイントがどちらのクラスに属するかを決定することが目標です。サポート ベクター マシンの場合、データ ポイントは- 次元ベクトル (数値のリスト) として表示され、そのようなポイントを- 次元超平面で分離できるかどうかを知りたいと考えます。これは線形分類器と呼ばれます。データを分類できる超平面は多数あります。最適な超平面として妥当な選択の 1 つは、2 つのクラス間の最大の分離、つまりマージンを表す超平面です。したがって、各側で最も近いデータ ポイントまでの距離が最大になるように超平面を選択します。このような超平面が存在する場合、それは最大マージン超平面と呼ばれ、それが定義する線形分類器は最大マージン分類器と呼ばれます。または、最適安定性のパーセプトロンとも呼ばれます。^{[引用が必要]}${\displaystyle p}$${\displaystyle p}$${\displaystyle (p-1)}$

より正式には、サポートベクターマシンは、高次元または無限次元空間に超平面または超平面の集合を構築し、分類、回帰、または外れ値検出などの他のタスクに使用できます。^[5]直感的には、任意のクラスの最も近いトレーニングデータポイントまでの距離が最大になる超平面（いわゆる機能マージン）によって良好な分離が達成されます。これは、一般にマージンが大きいほど、分類器の一般化誤差が低くなるためです。^[6]一般化誤差が低いということは、実装者が過剰適合を経験する可能性が低いことを意味します。

元の問題は有限次元空間で表現されるかもしれませんが、判別する集合がその空間内で線形に分離できないことがよくあります。このため、元の有限次元空間をはるかに高次元の空間にマッピングし、その空間内での分離を容易にすることが提案されました^{[7] 。計算負荷を妥当なレベルに抑えるために、SVM 方式で使用されるマッピングは、問題に合わせて選択された}カーネル関数で定義することにより、入力データ ベクトルのペアのドット積を元の空間の変数で簡単に計算できるように設計されています。^[8]高次元空間の超平面は、その空間のベクトルとのドット積が一定である点の集合として定義されます。このようなベクトルの集合は、超平面を定義する直交 (したがって最小) のベクトルの集合です。超平面を定義するベクトルは、データベースに出現する特徴ベクトルの画像のパラメータとの線形結合になるように選択できます。この超平面の選択により、超平面にマッピングされる特徴空間内の点は、関係式によって定義されます。が から遠ざかるにつれて が小さくなる 場合、合計の各項は、テスト ポイントが対応するデータベース ポイント にどれだけ近いかを表します。このように、上記のカーネルの合計を使用して、判別するセットのいずれかに由来するデータ ポイントに対する各テスト ポイントの相対的な近さを測定できます。結果として、任意の超平面にマッピングされる点の集合は非常に複雑になる可能性があり、元の空間ではまったく凸ではないセット間のより複雑な判別が可能になることに注意してください。 ${\displaystyle k(x,y)}$${\displaystyle \alpha _{i}}$ ${\displaystyle x_{i}}$${\displaystyle x}$${\displaystyle \textstyle \sum _{i}\alpha _{i}k(x_{i},x)={\text{constant}}.}$${\displaystyle k(x,y)}$${\displaystyle y}$${\displaystyle x}$${\displaystyle x}$${\displaystyle x_{i}}$${\displaystyle x}$

SVM はさまざまな現実世界の問題を解決するために使用できます。

• SVMはテキストとハイパーテキストの分類に役立ちます。SVMの適用により、標準的な帰納的設定とトランスダクティブ設定の両方でラベル付けされたトレーニングインスタンスの必要性が大幅に削減されるからです。^[9]浅い意味解析のためのいくつかの方法は、サポートベクターマシンに基づいています。^[10]
• 画像の分類もSVMを使って実行できます。実験結果によると、SVMは、関連性フィードバックを3～4回行うだけで、従来のクエリ絞り込み方式よりも大幅に高い検索精度を達成します。これは、 Vapnikが提案した特権アプローチを使用する修正版SVMを使用するシステムを含む画像セグメンテーションシステムにも当てはまります。^{[11] [12]}
• 教師ありSVMを用いたSARデータなどの衛星データの分類。^[13]
• 手書き文字はSVMを用いて認識することができる。^{[14] [15]}
• SVMアルゴリズムは、生物学やその他の科学で広く適用されています。タンパク質の分類に使用されており、化合物の最大90％が正しく分類されています。SVMの重みに基づく順列検定は、SVMモデルの解釈のメカニズムとして提案されています。^{[16] [17]}サポートベクターマシンの重みは、過去にSVMモデルの解釈にも使用されていました。^[18]サポートベクターマシンモデルの事後解釈は、モデルが予測を行うために使用する特徴を識別するための比較的新しい研究分野であり、生物学において特別な意味を持っています。

オリジナルの SVM アルゴリズムは、1964 年にVladimir N. VapnikとAlexey Ya. Chervonenkisによって発明されました。 ^{[引用が必要]} 1992 年に、Bernhard Boser、Isabelle Guyon、Vladimir Vapnik は、最大マージン超平面にカーネル トリックを適用して非線形分類器を作成する方法を提案しました。 ^[7]ソフトウェア パッケージで一般的に使用されている「ソフト マージン」の実現は、1993 年にCorinna Cortesと Vapnik によって提案され、1995 年に公開されました。 ^[1]

形式の点 のトレーニング データセットが与えられます。 ここで、 は1 または -1 で、それぞれが点が属するクラスを示します。それぞれは次元の実数ベクトルです。 の点のグループを の点のグループから分割する「最大マージン超平面」を見つけます。これは、超平面といずれかのグループの最も近い点との間の距離が最大になるように定義されます。 ${\displaystyle n}$$${\displaystyle (\mathbf {x} _{1},y_{1}),\ldots ,(\mathbf {x} _{n},y_{n}),}$$${\displaystyle y_{i}}$${\displaystyle \mathbf {x} _{i}}$${\displaystyle \mathbf {x} _{i}}$${\displaystyle p}$${\displaystyle \mathbf {x} _{i}}$${\displaystyle y_{i}=1}$${\displaystyle y_{i}=-1}$${\displaystyle \mathbf {x} _{i}}$

任意の超平面は、を満たす 点の集合として表すことができます。ここ で、 は超平面への法線ベクトル(必ずしも正規化されているとは限りません)です。これは、が必ずしも単位ベクトルではないことを除いて、ヘッセ正規形 によく似ています。パラメータ は、法線ベクトル に沿った原点からの超平面のオフセットを決定します。 ${\displaystyle \mathbf {x} }$$${\displaystyle \mathbf {w} ^{\mathsf {T}}\mathbf {x} -b=0,}$$${\displaystyle \mathbf {w} }$${\displaystyle \mathbf {w} }$${\displaystyle {\tfrac {b}{\|\mathbf {w} \|}}}$${\displaystyle \mathbf {w} }$

注意：このテーマに関する文献のほとんどは、バイアスを次のように定義しています。 $${\displaystyle \mathbf {w} ^{\mathsf {T}}\mathbf {x} +b=0.}$$

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

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

そして

${\displaystyle \mathbf {w} ^{\mathsf {T}}\mathbf {x} -b=-1}$(この境界上または境界下にあるものはすべて、ラベルが -1 である他のクラスです)。

幾何学的には、これら2つの超平面間の距離は、^[19]なので、平面間の距離を最大化するには を最小化する必要があります。距離は、点から平面までの距離の方程式を使用して計算されます。また、データポイントがマージンに入らないようにする必要があるため、次の制約を追加します。 またはの それぞれ に対して、 これらの制約は、各データポイントがマージンの正しい側になければならないことを規定しています。 ${\displaystyle {\tfrac {2}{\|\mathbf {w} \|}}}$${\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).}$$

はi番目のターゲット（この場合は 1 または -1）であり、はi番目の出力であることに注意してください。 ${\displaystyle y_{i}}$${\displaystyle \mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i}-b}$

この関数は、 （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}}}$$

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

1963 年に Vapnik によって提案された元の最大マージン超平面アルゴリズムは、線形分類器を構築しました。しかし、1992 年に Bernhard Boser、Isabelle Guyon、およびVladimir Vapnik は、カーネル トリック(元々は Aizerman らによって提案されました^[20] ) を最大マージン超平面に適用することで、非線形分類器を作成する方法を提案しました^{[7] 。}ドット積をカーネルに置き換えるカーネル トリックは、SVM 問題のデュアル表現で簡単に導き出されます。これにより、アルゴリズムは変換された特徴空間で最大マージン超平面を適合させることができます。変換は非線形で、変換された空間は高次元である可能性があります。つまり、分類器は変換された特徴空間では超平面ですが、元の入力空間では非線形である可能性があります。

注目すべきは、高次元の特徴空間で作業するとサポートベクターマシンの一般化誤差が増加するが、十分なサンプルが与えられればアルゴリズムは依然として良好なパフォーマンスを発揮するということである。^[21]

一般的なカーネルには次のようなものがあります。

• 多項式（同次）：特に、のとき、これは線形カーネルになります。${\displaystyle k(\mathbf {x} _{i},\mathbf {x} _{j})=(\mathbf {x} _{i}\cdot \mathbf {x} _{j})^{d}}$${\displaystyle d=1}$
• 多項式（非同次）：.${\displaystyle k(\mathbf {x} _{i},\mathbf {x} _{j})=(\mathbf {x} _{i}\cdot \mathbf {x} _{j}+r)^{d}}$
• ガウス放射基底関数:の場合。 を使用してパラメーター化されることもあります。${\displaystyle k(\mathbf {x} _{i},\mathbf {x} _{j})=\exp \left(-\gamma \left\|\mathbf {x} _{i}-\mathbf {x} _{j}\right\|^{2}\right)}$${\displaystyle \gamma >0}$${\displaystyle \gamma =1/(2\sigma ^{2})}$
• シグモイド関数(双曲正接) :いくつかの (すべてではない)およびに対して。${\displaystyle k(\mathbf {x_{i}} ,\mathbf {x_{j}} )=\tanh(\kappa \mathbf {x} _{i}\cdot \mathbf {x} _{j}+c)}$${\displaystyle \kappa >0}$${\displaystyle c<0}$

カーネルは、方程式 によって変換に関連付けられます。値wも変換された空間にあり、 です。分類のためのwとのドット積は、カーネル トリックによって再び計算できます。つまり、 です。 ${\displaystyle \varphi (\mathbf {x} _{i})}$${\displaystyle k(\mathbf {x} _{i},\mathbf {x} _{j})=\varphi (\mathbf {x} _{i})\cdot \varphi (\mathbf {x} _{j})}$${\textstyle \mathbf {w} =\sum _{i}\alpha _{i}y_{i}\varphi (\mathbf {x} _{i})}$${\textstyle \mathbf {w} \cdot \varphi (\mathbf {x} )=\sum _{i}\alpha _{i}y_{i}k(\mathbf {x} _{i},\mathbf {x} )}$

（ソフトマージン）SVM分類器を計算することは、次の形式の式を最小化することに相当する。

上で述べたように、十分に小さい値を選択すると、線形分類可能な入力データに対してハードマージン分類器が得られるため、ここではソフトマージン分類器に焦点を当てます。 (2)を二次計画問題に還元する古典的なアプローチについては、以下で詳しく説明します。次に、より最近のアプローチである亜勾配降下法や座標降下法について説明します。 ${\displaystyle \lambda }$

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

それぞれに対して変数を導入します。は、以下を満たす最小の非負数であることに注意してください。${\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}}}$$

これは双対問題と呼ばれます。双対最大化問題は線形制約の対象となる 2 次関数であるため、 2 次計画アルゴリズムによって効率的に解決できます。 ${\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}}}$$

係数は、前と同様に、2次計画法を使用して解くことができます。ここでも、が変換された空間のマージンの境界上にある ようなインデックスを見つけて、${\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 分類子を見つけるための最近のアルゴリズムには、亜勾配降下法と座標降下法があります。どちらの手法も、大規模でスパースなデータセットを扱う際に従来のアプローチに比べて大きな利点があることが実証されています。亜勾配法はトレーニング例が多い場合に特に効率的であり、座標降下法は特徴空間の次元が高い場合に効果的です。

SVMの 劣勾配降下アルゴリズムは、次の式を直接処理します。

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

はおよびの凸関数であることに注意する。そのため、従来の勾配降下法（SGD法）を適応させることができ、関数の勾配の方向にステップを踏む代わりに、関数のサブ勾配から選択されたベクトルの方向にステップを踏む。このアプローチの利点は、特定の実装では、反復回数がデータポイントの数（ ）に比例しないという点である。^[22]${\displaystyle f}$${\displaystyle \mathbf {w} }$${\displaystyle b}$${\displaystyle n}$

SVMの 座標降下アルゴリズムは双対問題から成り立つ

$${\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}(x_{i}\cdot 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}}}$$

各 について、係数はの方向に繰り返し調整されます。次に、結果として得られる係数のベクトルは、与えられた制約を満たす最も近い係数のベクトルに投影されます。（通常はユークリッド距離が使用されます。）このプロセスは、ほぼ最適な係数のベクトルが得られるまで繰り返されます。結果として得られるアルゴリズムは実際には非常に高速ですが、パフォーマンスの保証はほとんど証明されていません。^[23]${\displaystyle i\in \{1,\,\ldots ,\,n\}}$${\displaystyle c_{i}}$${\displaystyle \partial f/\partial c_{i}}$${\displaystyle (c_{1}',\,\ldots ,\,c_{n}')}$

上で説明したソフトマージン サポート ベクター マシンは、ヒンジ損失の経験的リスク最小化(ERM) アルゴリズムの例です。このように見ると、サポート ベクター マシンは統計的推論のアルゴリズムの自然なクラスに属し、その独自の機能の多くはヒンジ損失の動作によるものです。この観点から、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})).}$$

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

最小化問題が明確に定義された解を持つためには、検討する仮説の集合に制約を課す必要がある。 がノルム空間である場合（SVMの場合のように）、となる仮説のみを検討することが特に効果的な手法である。 これは、正規化ペナルティを課すことと同等であり、新しい最適化問題を解く。 ${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {H}}}$${\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}).}$$

ヒンジ損失とこれら他の損失関数との違いは、ターゲット関数、つまり与えられたランダム変数のペアの期待リスクを最小化する関数の観点から説明するのが最も適切です。 ${\displaystyle X,\,y}$

特に、が というイベントを条件として表すものとします。分類設定では、次のようになります。 ${\displaystyle y_{x}}$${\displaystyle y}$${\displaystyle X=x}$

$${\displaystyle y_{x}={\begin{cases}1&{\text{with probability }}p_{x}\\-1&{\text{with probability }}1-p_{x}\end{cases}}}$$

したがって、最適な分類器は次のようになります。

$${\displaystyle f^{*}(x)={\begin{cases}1&{\text{if }}p_{x}\geq 1/2\\-1&{\text{otherwise}}\end{cases}}}$$

平方損失の場合、ターゲット関数は条件付き期待値関数 です。ロジスティック損失の場合、ターゲット関数はロジット関数 です。これらのターゲット関数は両方とも として正しい分類子を生成しますが、必要以上の情報を提供します。実際、 の分布を完全に記述するのに十分な情報を提供します。 ${\displaystyle f_{sq}(x)=\mathbb {E} \left[y_{x}\right]}$${\displaystyle f_{\log }(x)=\ln \left(p_{x}/({1-p_{x}})\right)}$${\displaystyle \operatorname {sgn}(f_{sq})=\operatorname {sgn}(f_{\log })=f^{*}}$${\displaystyle y_{x}}$

一方、ヒンジ損失のターゲット関数が正確に で あることを確認できます。したがって、十分に豊富な仮説空間では、または同等に、適切に選択されたカーネルでは、SVM分類器はデータを正しく分類する最も単純な関数（ に関して）に収束します。これはSVMの幾何学的解釈を拡張します。線形分類の場合、経験的リスクはサポートベクトルの間にマージンがある任意の関数によって最小化され、その中で最も単純なのは最大マージン分類器です。^[24]${\displaystyle f^{*}}$${\displaystyle {\mathcal {R}}}$

SVMは一般化線形分類器のファミリーに属し、パーセプトロンの拡張として解釈することができます。^{[25]また、} Tikhonov正則化の特殊なケースと見なすこともできます。特別な特性は、経験的分類誤差を最小化すると同時に幾何学的マージンを最大化することです。そのため、最大マージン分類器としても知られています。

SVMと他の分類器との比較は、Meyer、Leisch、Hornikによって行われている。^[26]

SVM の有効性は、カーネルの選択、カーネルのパラメータ、およびソフトマージンパラメータ に依存します。一般的な選択肢は、単一のパラメータ を持つガウスカーネルです。 と の最適な組み合わせは、およびの指数関数的に増加するシーケンスを使用したグリッド検索によって選択されることがよくあります(例: ; ) 。通常、パラメータ選択の各組み合わせはクロス検証を使用してチェックされ、クロス検証の精度が最も高いパラメータが選択されます。あるいは、ベイズ最適化の最近の研究を使用してと を選択することもできます。この場合、グリッド検索よりもはるかに少ないパラメータの組み合わせの評価が必要になることがよくあります。テストや新しいデータの分類に使用される最終的なモデルは、選択されたパラメータを使用してトレーニングセット全体でトレーニングされます。^[27]${\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 }$

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

• 入力データの完全なラベル付けが必要
• 較正されていないクラス所属確率- SVMは、有限データ上の確率の推定を避けるVapnikの理論に由来する。
• SVM は 2 クラス タスクにのみ直接適用できます。したがって、マルチクラス タスクを複数のバイナリ問題に縮小するアルゴリズムを適用する必要があります。マルチクラス SVM セクションを参照してください。
• 解決されたモデルのパラメータを解釈するのは困難です。

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

これを行うための主なアプローチは、単一の多クラス問題を複数の二値分類問題に縮小することです。 ^[28]このような縮小の一般的な方法は次のとおりです。^{[28] [29]}

• ラベルの 1 つと残り ( 1 対全) またはすべてのクラスのペア ( 1 対 1 ) を区別するバイナリ分類子を構築します。1 対全の場合の新しいインスタンスの分類は、勝者総取り戦略によって行われます。この戦略では、出力関数が最も高い分類子がクラスを割り当てます (出力関数は比較可能なスコアを生成するように調整することが重要です)。1 対 1 アプローチの場合、分類は最大勝者投票戦略によって行われます。この戦略では、すべての分類子がインスタンスを 2 つのクラスのいずれかに割り当て、割り当てられたクラスへの投票が 1 票増加し、最後に投票数が最も多いクラスがインスタンスの分類を決定します。
• 有向非巡回グラフSVM（DAGSVM）^[30]
• 誤り訂正出力コード^[31]

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

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

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

分類すべきテスト例の数。正式には、トランスダクティブサポートベクターマシンは次の基本最適化問題によって定義される：^[36]

最小化 (in ) ${\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 年に Vladimir N. Vapnik によって導入されました。

構造化サポートベクターマシンは、従来のSVMモデルの拡張版です。SVMモデルは主にバイナリ分類、多クラス分類、回帰タスク用に設計されていますが、構造化SVMは、構文解析木、分類法による分類、配列アライメントなど、一般的な構造化出力ラベルの処理にも応用されています。^[37]

回帰用のSVMのバージョンは、1996年にVladimir N. Vapnik、Harris Drucker、Christopher JC Burges、Linda Kaufman、Alexander J. Smolaによって提案されました。^[38]この方法はサポートベクター回帰（SVR）と呼ばれます。サポートベクター分類（上記）によって生成されたモデルは、モデル構築のコスト関数がマージンを超えるトレーニングポイントを考慮しないため、トレーニングデータのサブセットのみに依存します。同様に、SVRによって生成されたモデルは、モデル構築のコスト関数がモデル予測に近いトレーニングデータを無視するため、トレーニングデータのサブセットのみに依存します。最小二乗サポートベクターマシン（LS-SVM）として知られる別のSVMバージョンは、SuykensとVandewalleによって提案されました。^[39]

オリジナルのSVRを訓練することは、^{[40]を解決することを意味する。}

最小化する${\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年にポルソンとスコットは、SVMがデータ拡張の技術を通じてベイズ解釈を許容することを示した。^[41]このアプローチでは、SVMはグラフィカルモデル（パラメータが確率分布を介して接続される）として見られる。この拡張された見方により、柔軟な特徴モデリング、自動ハイパーパラメータチューニング、予測不確実性の定量化など、ベイズ技術をSVMに適用することができる。最近、ベイズSVMのスケーラブルバージョンがフロリアン・ウェンゼルによって開発され、ベイズSVMをビッグデータに適用できるようになった。^[42]フロリアン・ウェンゼルは、ベイズカーネルサポートベクターマシン（SVM）用の変分推論（VI）スキームと線形ベイズSVM用の確率バージョン（SVI）の2つの異なるバージョンを開発した。^[43]

最大マージン超平面のパラメータは、最適化を解くことによって導出されます。SVMから生じる二次計画法(QP) 問題を迅速に解決するための特殊なアルゴリズムがいくつか存在しますが、そのほとんどは、問題をより小さく、より扱いやすいチャンクに分割するためのヒューリスティックに依存しています。

もう一つのアプローチは、ニュートン法のような反復法を用いて主問題と双対問題のカルシュ・キューン・タッカー条件の解を求める内点法を使うことである。 ^[44] このアプローチは、一連の分解された問題を解くのではなく、問題全体を直接解く。大きなカーネル行列を含む線形システムを解くことを避けるために、カーネルトリックでは行列の低ランク近似がよく使われる。

もう一つの一般的な方法は、プラットの逐次最小最適化（SMO）アルゴリズムです。これは、問題を2次元のサブ問題に分割して解析的に解決するため、数値最適化アルゴリズムと行列ストレージが不要になります。このアルゴリズムは概念的にシンプルで、実装が容易で、一般的に高速で、困難なSVM問題に対するスケーリング特性が優れています。^[45]

線形サポートベクターマシンの特殊なケースは、その近縁種であるロジスティック回帰を最適化するために使用されるのと同じ種類のアルゴリズムによって、より効率的に解決できます。このクラスのアルゴリズムには、亜勾配降下法（PEGASOS ^[46]な​​ど）と座標降下法（LIBLINEAR ^[47]など）が含まれます。LIBLINEARには魅力的なトレーニング時間特性があります。各収束反復には、トレーニングデータの読み取りにかかる時間に線形の時間がかかり、反復にはQ線形収束特性もあるため、アルゴリズムが非常に高速になります。

一般的なカーネルSVMは、特に並列化が許可されている場合、サブ勾配降下法（例：P-packSVM ^[48]）を使用してより効率的に解くこともできます。

カーネル SVM は、LIBSVM 、 MATLAB、SAS、SVMlight、kernlab、scikit-learn、Shogun、Weka、Shark、JKernelMachines、OpenCVなど、 多くの機械学習ツールキットで利用できます。

分類の精度を高めるために、データの前処理（標準化）が強く推奨されます。^[49]標準化には、最小最大、小数スケーリングによる正規化、Zスコアなど、いくつかの方法があります。^[50] SVMでは、通常、各特徴の平均減算と分散による除算が使用されます。^[51]

• 現場適応型集計
• カーネルマシン
• フィッシャーカーネル
• プラットスケーリング
• 多項式カーネル
• 予測分析
• サポートベクターマシンにおける正規化の観点
• 関連性ベクトルマシン、SVMと機能形式が同一の確率的スパースカーネルモデル
• 連続最小最適化
• 空間マッピング
• 選別（アルゴリズム）