最小二乗サポートベクターマシン

統計学および統計モデリングにおける最小二乗サポートベクターマシン（LS-SVM）は、データを分析しパターンを認識する一連の関連する教師あり学習法であるサポートベクターマシン（SVM）の最小二乗バージョンであり、分類および回帰分析に使用されます。このバージョンでは、古典的なSVMの凸二次計画問題（QP）の代わりに、一連の線形方程式を解くことによって解を見つけます。最小二乗SVM分類器は、 Johan SuykensとJoos Vandewalleによって提案されました。^{[ 1 ]} LS-SVMは、カーネルベースの学習法のクラスです。

トレーニングセットが与えられた場合${\displaystyle \{x_{i},y_{i}\}_{i=1}^{N}}$入力データ付き${\displaystyle x_{i}\in \mathbb {R} ^{n}}$および対応するバイナリクラスラベル$\displaystyle y_{i}\in \{-1,+1\}}$ヴァプニックの元の定式化によれば、SVM ^{[ 2 ]分類器は次の条件を満たす。}

${\displaystyle {\begin{cases}w^{T}\phi (x_{i})+b\geq 1,&{\text{if }}\quad y_{i}=+1,\\w^{T}\phi (x_{i})+b\leq -1,&{\text{if }}\quad y_{i}=-1,\end{cases}}}$

これは以下と同等です

${\displaystyle y_{i}\left[{w^{T}\phi (x_{i})+b}\right]\geq 1,\quad i=1,\ldots ,N,}$

どこ${\displaystyle \phi (x)}$これは、元の空間から高次元または無限次元の空間への非線形写像である。

切り離せないデータ

このような分離超平面が存在しない場合、いわゆるスラック変数を導入する。$\displaystyle \xi _{i}}$そのため

${\displaystyle {\begin{cases}y_{i}\left[{w^{T}\phi (x_{i})+b}\right]\geq 1-\xi _{i},&i=1,\ldots ,N,\\\xi _{i}\geq 0,&i=1,\ldots ,N.\end{cases}}}$

構造的リスク最小化原理によれば、リスク境界は以下の最小化問題によって最小化される。

${\displaystyle \min J_{1}(w,\xi )={\frac {1}{2}}w^{T}w+c\sum \limits _{i=1}^{N}\xi _{i},}$

${\displaystyle {\text{制約条件 }}{\begin{cases}y_{i}\left[{w^{T}\phi (x_{i})+b}\right]\geq 1-\xi _{i},&i=1,\ldots ,N,\\\xi _{i}\geq 0,&i=1,\ldots ,N,\end{cases}}}$

この問題を解決するために、ラグランジュ関数を構築することができます。

${\displaystyle L_{1}(w,b,\xi ,\alpha ,\beta )={\frac {1}{2}}w^{T}w+c\sum \limits _{i=1}^{N}{\xi _{i}}-\sum \limits _{i=1}^{N}\alpha _{i}\left\{y_{i}\left[{w^{T}\phi (x_{i})+b}\right]-1+\xi _{i}\right\}-\sum \limits _{i=1}^{N}\beta _{i}\xi _{i},}$

どこ${\displaystyle \alpha _{i}\geq 0,\ \beta _{i}\geq 0\ (i=1,\ldots ,N)}$はラグランジュ乗数です。最適点はラグランジュ関数の鞍点にあり、その後、次の式が得られます。

置換により${\displaystyle w}$適切な目的関数と制約条件から構成されるラグランジアンにおける表現により、以下の二次計画問題が得られます。

${\displaystyle \max Q_{1}(\alpha )=-{\frac {1}{2}}\sum \limits _{i,j=1}^{N}{\alpha _{i}\alpha _{j}y_{i}y_{j}K(x_{i},x_{j})}+\sum \limits _{i=1}^{N}\alpha _{i},}$

どこ${\displaystyle K(x_{i},x_{j})=\left\langle \phi (x_{i}),\phi (x_{j})\right\rangle }$はカーネル関数と呼ばれます。この QP 問題を ( 1 )の制約の下で解くと、高次元空間の超平面が得られ、それによって元の空間の分類器が得られます。

最小二乗SVM定式化

SVM分類器の最小二乗バージョンは、最小化問題を次のように再定式化することによって得られます。

${\displaystyle \min J_{2}(w,b,e)={\frac {\mu }{2}}w^{T}w+{\frac {\zeta }{2}}\sum \limits _{i=1}^{N}e_{i}^{2},}$

等式制約に従う

${\displaystyle y_{i}\left[{w^{T}\phi (x_{i})+b}\right]=1-e_{i},\quad i=1,\ldots ,N.}$

上記の最小二乗SVM（LS-SVM）分類器の定式化は、暗黙のうちに二値ターゲットを用いた回帰解釈に対応している。${\displaystyle y_{i}=\pm 1}$。

使用$\displaystyle y_{i}^{2}=1}$、 我々は持っています

${\displaystyle \sum \limits _{i=1}^{N}e_{i}^{2}=\sum \limits _{i=1}^{N}(y_{i}e_{i})^{2}=\sum \limits _{i=1}^{N}e_{i}^{2}=\sum \limits _{i=1}^{N}\left(y_{i}-(w^{T}\phi (x_{i})+b)\right)^{2},}$

と${\displaystyle e_{i}=y_{i}-(w^{T}\phi (x_{i})+b).}$なお、この誤差は最小二乗法によるデータフィッティングにおいても妥当なものであり、回帰分析の場合も同様の最終結果が得られることに注意してください。

したがって、LS-SVM分類器の定式化は以下と同等である。

${\displaystyle J_{2}(w,b,e)=\mu E_{W}+\zeta E_{D}}$

と${\displaystyle E_{W}={\frac {1}{2}}w^{T}w}$そして${\displaystyle E_{D}={\frac {1}{2}}\sum \limits _{i=1}^{N}e_{i}^{2}={\frac {1}{2}}\sum \limits _{i=1}^{N}\left(y_{i}-(w^{T}\phi (x_{i})+b)\right)^{2}.}$

両方${\displaystyle \mu }$そして${\displaystyle \zeta }$これらは、正則化の量と二乗誤差の合計を調整するためのハイパーパラメータとして考慮されるべきである。解は比率のみに依存する。${\displaystyle \gamma =\zeta /\mu }$したがって、元の処方では${\displaystyle \gamma }$チューニングパラメータとして。${\displaystyle \mu }$そして${\displaystyle \zeta }$LS-SVMにベイズ解釈を与えるためのパラメータとして。

LS-SVM回帰器の解は、ラグランジュ関数を構築した後に得られます。

${\displaystyle {\begin{cases}L_{2}(w,b,e,\alpha )\;=J_{2}(w,e)-\sum \limits _{i=1}^{N}\alpha _{i}\left\{{\left[{w^{T}\phi (x_{i})+b}\right]+e_{i}-y_{i}}\right\},\\\quad \quad \quad \quad \quad \;={\frac {1}{2}}w^{T}w+{\frac {\gamma }{2}}\sum \limits _{i=1}^{N}e_{i}^{2}-\sum \limits _{i=1}^{N}\alpha _{i}\left\{\left[w^{T}\phi (x_{i})+b\right]+e_{i}-y_{i}\right\},\end{cases}}}$

どこ${\displaystyle \alpha _{i}\in \mathbb {R} }$ラグランジュ乗数は、最適性の条件は

${\displaystyle {\begin{cases}{\frac {\partial L_{2}}{\partial w}}=0\quad \to \quad w=\sum \limits _{i=1}^{N}\alpha _{i}\phi (x_{i}),\\{\frac {\partial L_{2}}{\partial b}}=0\quad \to \quad \sum \limits _{i=1}^{N}\alpha _{i}=0,\\{\frac {\partial L_{2}}{\partial e_{i}}}=0\quad \to \quad \alpha _{i}=\gamma e_{i},\;i=1,\ldots ,N,\\{\frac {\partial L_{2}}{\partial \alpha _{i}}}=0\quad \to \quad y_{i}=w^{T}\phi (x_{i})+b+e_{i},\,i=1,\ldots ,N.\end{cases}}}$

排除${\displaystyle w}$そして${\displaystyle e}$二次計画問題ではなく、線形システムが得られる。

${\displaystyle \left[{\begin{matrix}0&1_{N}^{T}\\1_{N}&\Omega +\gamma ^{-1}I_{N}\end{matrix}}\right]\left[{\begin{matrix}b\\\alpha \end{matrix}}\right]=\left[{\begin{matrix}0\\Y\end{matrix}}\right],}$

と${\displaystyle Y=[y_{1},\ldots ,y_{N}]^{T}}$、${\displaystyle 1_{N}=[1,\ldots ,1]^{T}}$そして${\displaystyle \alpha =[\alpha _{1},\ldots ,\alpha _{N}]^{T}}$。 ここ、${\displaystyle I_{N}}$は${\displaystyle N\times N}$単位行列、および${\displaystyle \Omega \in \mathbb {R} ^{N\times N}}$カーネル行列は次のように定義されます。${\displaystyle \Omega _{ij}=\phi (x_{i})^{T}\phi (x_{j})=K(x_{i},x_{j})}$。

SVMのベイズ解釈はSmolaらによって提案された。彼らは、SVMにおける異なるカーネルの使用は、関数空間上の異なる事前確率分布を定義することとみなせることを示した。${\displaystyle P[f]\propto \exp \left({-\beta \left\|{{\hat {P}}f}\right\|^{2}}\right)}$。 ここ${\displaystyle \beta >0}$は定数であり、${\displaystyle {\hat {P}}}$は、選択されたカーネルに対応する正則化演算子です。

一般的なベイズ証拠フレームワークはMacKayによって開発され、^{[ 3 ] [ 4 ] [ 5 ]} MacKayはそれを回帰、順方向ニューラルネットワーク、分類ネットワークの問題に適用した。提供されたデータセット${\displaystyle D}$モデル${\displaystyle \mathbb {M} }$パラメータベクトル付き${\displaystyle w}$そして、いわゆるハイパーパラメータまたは正則化パラメータ${\displaystyle \lambda }$ベイズ推論は、3つのレベルの推論で構成されています。

• レベル 1 では、特定の値に対して${\displaystyle \lambda }$推論の第1レベルでは、事後分布を推論します。${\displaystyle w}$ベイズルールにより

${\displaystyle p(w|D,\lambda ,\mathbb {M} )\propto p(D|w,\mathbb {M} )p(w|\lambda ,\mathbb {M} ).}$

• 推論の第2レベルでは、${\displaystyle \lambda }$最大化することで

${\displaystyle p(\lambda |D,\mathbb {M} )\propto p(D|\lambda ,\mathbb {M} )p(\lambda |\mathbb {M} ).}$

• 証拠フレームワークにおける第3レベルの推論では、事後確率を調べることによって異なるモデルをランク付けします。

${\displaystyle p(\mathbb {M} |D)\propto p(D|\mathbb {M} )p(\mathbb {M} ).}$

ベイズ証拠フレームワークは、モデル学習とモデル選択のための統一理論であることがわかります。Kwokは、ベイズ証拠フレームワークを用いてSVMの定式化とモデル選択を解釈しました。また、サポートベクター回帰にもベイズ証拠フレームワークを適用しました。

さて、データポイントが与えられた${\displaystyle \{x_{i},y_{i}\}_{i=1}^{N}}$そしてハイパーパラメータ${\displaystyle \mu }$そして${\displaystyle \zeta }$モデル${\displaystyle \mathbb {M} }$モデルパラメータ${\displaystyle w}$そして${\displaystyle b}$事後確率を最大化することによって推定される${\displaystyle p(w,b|D,\log \mu ,\log \zeta ,\mathbb {M} )}$ベイズの定理を適用すると、次のようになります。

${\displaystyle p(w,b|D,\log \mu ,\log \zeta ,\mathbb {M} )={\frac {p(D|w,b,\log \mu ,\log \zeta ,\mathbb {M} )p(w,b|\log \mu ,\log \zeta ,\mathbb {M} )}{p(D|\log \mu ,\log \zeta ,\mathbb {M} )}},}$

どこ${\displaystyle p(D|\log \mu ,\log \zeta ,\mathbb {M} )}$は、すべての可能な範囲にわたる積分のような正規化定数です。${\displaystyle w}$そして${\displaystyle b}$は 1 に等しいと仮定します。${\displaystyle w}$そして${\displaystyle b}$ハイパーパラメータに依存しない${\displaystyle \zeta }$、およびは条件付き独立である、つまり、

${\displaystyle p(w,b|\log \mu ,\log \zeta ,\mathbb {M} )=p(w|\log \mu ,\mathbb {M} )p(b|\log \sigma _{b},\mathbb {M} ).}$

いつ${\displaystyle \sigma _{b}\to \infty }$分布${\displaystyle b}$は一様分布に近似する。さらに、我々は${\displaystyle w}$そして${\displaystyle b}$はガウス分布であるため、事前分布は次のようになります。${\displaystyle w}$そして${\displaystyle b}$と${\displaystyle \sigma _{b}\to \infty }$である

${\displaystyle {\begin{array}{l}p(w,b|\log \mu ,)=\left({\frac {\mu }{2\pi }}\right)^{\frac {n_{f}}{2}}\exp \left({-{\frac {\mu }{2}}w^{T}w}\right){\frac {1}{\sqrt {2\pi \sigma _{b}}}}\exp \left({-{\frac {b^{2}}{2\sigma _{b}}}}\right)\\\quad \quad \quad \quad \quad \quad \quad \propto \left({\frac {\mu }{2\pi }}\right)^{\frac {n_{f}}{2}}\exp \left({-{\frac {\mu }{2}}w^{T}w}\right)\end{array}}.}$

ここ${\displaystyle n_{f}}$は特徴空間の次元であり、${\displaystyle w}$。

確率${\displaystyle p(D|w,b,\log \mu ,\log \zeta ,\mathbb {M} )}$のみに依存すると想定される${\displaystyle w,b,\zeta }$そして${\displaystyle \mathbb {M} }$データポイントは独立同分布（iid）であると仮定します。

${\displaystyle p(D|w,b,\log \zeta ,\mathbb {M} )=\prod \limits _{i=1}^{N}{p(x_{i},y_{i}|w,b,\log \zeta ,\mathbb {M} )}.}$

最小二乗コスト関数を求めるために、データ点の確率は以下に比例すると仮定する。

${\displaystyle p(x_{i},y_{i}|w,b,\log \zeta ,\mathbb {M} )\propto p(e_{i}|w,b,\log \zeta ,\mathbb {M} ).}$

誤差にはガウス分布が用いられる。${\displaystyle e_{i}=y_{i}-(w^{T}\phi (x_{i})+b)}$として：

${\displaystyle p(e_{i}|w,b,\log \zeta ,\mathbb {M} )={\sqrt {\frac {\zeta }{2\pi }}}\exp \left({-{\frac {\zeta e_{i}^{2}}{2}}}\right).}$

と想定されるのは${\displaystyle w}$そして${\displaystyle b}$クラスの中心が${\displaystyle {\hat {m}}_{-}}$そして${\displaystyle {\hat {m}}_{+}}$それぞれターゲット-1と+1にマッピングされる。${\displaystyle w^{T}\phi (x)+b}$クラス要素の${\displaystyle \phi (x)}$多変量ガウス分布に従い、分散は${\displaystyle 1/\zeta }$。

前述の式を組み合わせ、すべての定数を無視すると、ベイズの定理は次のようになる。

${\displaystyle p(w,b|D,\log \mu ,\log \zeta ,\mathbb {M} )\propto \exp(-{\frac {\mu }{2}}w^{T}w-{\frac {\zeta }{2}}\sum \limits _{i=1}^{N}{e_{i}^{2}})=\exp(-J_{2}(w,b)).}$

最大事後密度推定値${\displaystyle w_{MP}}$そして${\displaystyle b_{MP}}$式(26)の負の対数を最小化することで式(10)が得られる。

• JAK Suykens、T. Van Gestel、J. De Brabanter、B. De Moor、J. Vandewalle、最小二乗サポート ベクター マシン、World Scientific Pub. Co.、シンガポール、2002 年。ISBN 981-238-151-1
• Suykens J. A. K.、Vandewalle J.、「最小二乗サポートベクターマシン分類器」、Neural Processing Letters、第9巻、第3号、1999年6月、pp.  293–300。
• ウラジミール・ヴァプニク著『統計的学習理論の本質』シュプリンガー・フェルラーク、1995年。ISBN 0-387-98780-0
• MacKay, DJC、「可能性のあるネットワークともっともらしい予測 ― 教師ありニューラルネットワークのための実用的なベイズ法のレビュー」、Network: Computation in Neural Systems、第6巻、1995年、469～505ページ 。

• www.esat.kuleuven.be/sista/lssvmlab/「最小二乗サポートベクターマシンラボ（LS-SVMlab）ツールボックスには、多数のLS-SVMアルゴリズムのMatlab/C実装が含まれています。」
• www.kernel-machines.org「サポートベクターマシンとカーネルベースの手法（Smola & Schölkopf）」
• www.gaussianprocess.org「ガウス過程：回帰と分類のための関数に対するガウス過程事前分布を用いたデータモデリング（マッケイ、ウィリアムズ）」
• www.support-vector.net「サポートベクターマシンとカーネルベースの手法（クリスティアニーニ）」
• dlib：大規模データセット向けの最小二乗SVM実装が含まれています。