サポート ベクター マシン回帰について

SVM 回帰の数学的形成化

概要

サポート ベクター マシン (SVM) 分析は分類と回帰のための一般的な機械学習ツールで、Vladimir Vapnik らが 1992 年にはじめて提案しました[5]。SVM 回帰はカーネル関数に依存するので、ノンパラメトリックな手法と考えられます。

Statistics and Machine Learning Toolbox™ では、L1 損失としても知られる、線形のイプシロン不感応 SVM (ε-SVM) 回帰を実装しています。ε-SVM 回帰では、一連の学習データに予測子変数と観測された応答値が含まれています。目標は、各学習点 x において y_n からの逸脱が ε を超えない、可能な限りフラットな関数 f(x) を求めることです。

線形 SVM 回帰: 主問題の式

一連の学習データがあり、x_n は、観測した応答変数 y_n と N 個の観測値が含まれている多変量のセットであるとします。

次の線形関数を求めるとします。

$$f(x)=x\prime \beta +b,$$

そして、この関数を可能な限りフラットにするとします。これには、ノルムの値 (β′β) が最小になる f(x) を求める必要があります。これは、次を最小化する凸最適化問題として定式化されます。

$$J\left(\beta \right)=\frac{1}{2}\beta \prime \beta$$

これには、すべての残差が ε より小さいという条件があり、方程式の形式では次のようになります。

$$\forall n:\left|y_n-\left(x_n\prime \beta +b\right)\right|\le \epsilon .$$

すべての点についてこれらの制約を満たす関数 f(x) は存在しない可能性があります。実行不可能制約に対処するには、各点にスラック変数 ξ_n および ξ^*_n を導入します。スラック変数は必要な条件を満たしたまま ξ_n と ξ^*_n の値まで回帰誤差の存在を許容するので、このアプローチは SVM 分類における "ソフト マージン" の概念に似ています。

スラック変数を含めると、目的関数は次のようになります。これは、主問題の式としても知られています[5]。

$$J\left(\beta \right)=\frac{1}{2}\beta \prime \beta +C{\displaystyle \sum _{n=1}^N\left({\xi }_n+{\xi }_n^{*}\right)},$$

これには、次の条件が適用されます。

$$\begin{array}{l}\forall n:y_n-\left(x_n\prime \beta +b\right)\le \epsilon +{\xi }_n\\ \forall n:\left(x_n\prime \beta +b\right)-y_n\le \epsilon +{\xi }_n^{*}\\ \forall n:{\xi }_n^{*}\ge 0\\ \forall n:{\xi }_n\ge 0.\end{array}$$

定数 C はボックス制約で、イプシロンのマージン (ε) の範囲外にある観測値に課されるペナルティを制御する正の数値であり、過適合の防止 (正則化) に役立ちます。この値は、f(x) のフラットさと、ε より大きい逸脱を許容する最大量の間のトレードオフを決定します。

線形の ε 許容損失関数は、観測値からの距離が ε 以内である誤差を、ゼロに等しいものとして扱うことにより無視します。損失は、観測値 y と ε 境界の間の距離に基づいて測定されます。正式な表記は次のとおりです。

$$L_{\epsilon }=\{\begin{array}{ll}0\hfill & \text{if }\left|y-f\left(x\right)\right|\le \epsilon \hfill \\ \left|y-f\left(x\right)\right|-\epsilon \hfill & \text{otherwise}\hfill \end{array}$$

線形 SVM 回帰: 双対問題の式

前述した最適化問題は、ラグランジュ双対形式化で解くと計算が簡単になります。双対問題の解は、主 (最小化) 問題の解に対する下限を与えます。主問題と双対問題の最適値は同じである必要はありません。この差は "双対性ギャップ" と呼ばれます。問題が凸型で制約適格性条件を満たす場合、主問題に対する最適な解の値は双対問題の解によって与えられます。

双対問題の式を得るには、各観測値 x_n について非負の乗数 α_n および α^*_n を導入することにより、主問題の関数からラグランジュ関数を作成します。これにより双対問題の式が得られ、次を最小化することになります。

$$L\left(\alpha \right)=\frac{1}{2}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{j=1}^N\left({\alpha }_i-{\alpha }_i^{*}\right)\left({\alpha }_j-{\alpha }_j^{*}\right)x_i\prime x_j+\epsilon {\displaystyle \sum _{i=1}^N\left({\alpha }_i+{\alpha }_i^{*}\right)}}}+{\displaystyle \sum _{i=1}^N{y}_i\left({\alpha }_i^{*}-{\alpha }_i\right)}$$

以下の制約に従います。

$$\begin{array}{l}{\displaystyle \sum _{n=1}^N\left({\alpha }_n-{\alpha }_n^{*}\right)=0}\\ \forall n:0\le {\alpha }_n\le C\\ \forall n:0\le {\alpha }_n^{*}\le C.\end{array}$$

次の方程式を使用すると、パラメーター β を学習観測値の線形結合として完全に表すことができます。

$$\beta ={\displaystyle \sum _{n=1}^N\left({\alpha }_n-{\alpha }_n^{*}\right)x_n.}$$

新しい値の予測に使用する関数は、サポート ベクターのみに依存します。

$$f\left(x\right)={\displaystyle \sum _{n=1}^N\left({\alpha }_n-{\alpha }_n^{*}\right)\left(x_n\prime x\right)+b.}$$

(1)

カルーシュ・キューン・タッカー (KKT) 相補性条件は、最適な解を得るために必要な最適化制約です。線形 SVM 回帰の場合、これらの条件は次のようになります。

$$\begin{array}{l}\forall n:{\alpha }_n\left(\epsilon +{\xi }_n-y_n+x_n\prime \beta +b\right)=0\\ \forall n:{\alpha }_n^{*}\left(\epsilon +{\xi }_n^{*}+y_n-x_n\prime \beta -b\right)=0\\ \forall n:{\xi }_n\left(C-{\alpha }_n\right)=0\\ \forall n:{\xi }_n^{*}\left(C-{\alpha }_n^{*}\right)=0.\end{array}$$

これらの条件は、完全にイプシロン チューブの内部にあるすべての観測値にラグランジュ乗数 α_n = 0 および α_n^* = 0 があることを示します。α_n または α_n^* のいずれかがゼロではない場合、対応する観測値は "サポート ベクター" と呼ばれます。

学習済み SVM モデルの Alpha プロパティには、サポート ベクターの 2 つのラグランジュ乗数の差 α_n – α_n^* が格納されます。SupportVectors プロパティと Bias プロパティには、それぞれ x_n と b が格納されます。

非線形 SVM 回帰: 主問題の式

一部の回帰問題は、線形モデルを使用して適切に表すことはできません。このような場合は、ラグランジュ双対形式を使用して、前述した手法を非線形関数に拡張できます。

非線形 SVM 回帰モデルを得るには、ドット積 x₁′x₂ を非線形カーネル関数 G(x₁,x₂) = <φ(x₁),φ(x₂)> に置き換えます。ここで、φ(x) は x を高次元空間にマッピングする変換です。Statistics and Machine Learning Toolbox には、次の半正定値カーネル関数が組み込まれています。

カーネル名	カーネル関数
線形 (ドット積)	$$G(x_j,x_k)=x_j\prime x_k$$
ガウス	$$G\left(x_j,x_k\right)=\exp \left(-{\Vert x_j-x_k\Vert }^2\right)$$
多項式	$$G(x_j,x_k)={(1+x_j\prime x_k)}^q$$。ここで、q は集合 {2,3,...} に含まれます。

"グラム行列" は、g_i,_j = G(x_i,x_j) という要素が含まれている n 行 n 列の行列です。各要素 g_i,_j は、φ で変換した予測子の内積と等しくなります。しかし、カーネル関数を使用して直接グラム行列を生成できるので、φ が既知である必要はありません。非線形 SVM では、この方法を使用して、変換した予測子空間で最適な関数 f(x) を求めます。

非線形 SVM 回帰: 双対問題の式

非線形 SVM 回帰の双対問題の式では、予測子の内積 (x_i′x_j) をグラム行列の対応する要素 (g_i,_j) に置き換えます。

非線形 SVM 回帰では、次を最小化する係数を求めます。

$$L\left(\alpha \right)=\frac{1}{2}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{j=1}^N\left({\alpha }_i-{\alpha }_i^{*}\right)\left({\alpha }_j-{\alpha }_j^{*}\right)G\left(x_i,x_j\right)+\epsilon {\displaystyle \sum _{i=1}^N\left({\alpha }_i+{\alpha }_i^{*}\right)-{\displaystyle \sum _{i=1}^N{y}_i\left({\alpha }_i-{\alpha }_i^{*}\right)}}}}$$

これには、次の条件が適用されます。

$$\begin{array}{l}{\displaystyle \sum _{n=1}^N\left({\alpha }_n-{\alpha }_n^{*}\right)}=0\\ \forall n:0\le {\alpha }_n\le C\\ \forall n:0\le {\alpha }_n^{*}\le C.\end{array}$$

新しい値の予測に使用される関数は以下に等しくなります。

$$f\left(x\right)={\displaystyle \sum _{n=1}^N\left({\alpha }_n-{\alpha }_n^{*}\right)G\left(x_n,x\right)+b}.$$

(2)

KKT 相補性条件は次のようになります。

$$\begin{array}{l}\forall n:{\alpha }_n\left(\epsilon +{\xi }_n-y_n+f\left(x_n\right)\right)=0\\ \forall n:{\alpha }_n^{*}\left(\epsilon +{\xi }_n^{*}+y_n-f\left(x_n\right)\right)=0\\ \forall n:{\xi }_n\left(C-{\alpha }_n\right)=0\\ \forall n:{\xi }_n^{*}\left(C-{\alpha }_n^{*}\right)=0.\end{array}$$

SVM 回帰の最適化問題を解く

ソルバーのアルゴリズム

最小化問題は、標準的な二次計画法の形式で表し、一般的な二次計画法の手法を使用して解くことができます。しかし、特にグラム行列が大きくなりすぎてメモリに格納できなくなる場合があるので、二次計画法のアルゴリズムを使用すると計算コストが高くなる可能性があります。代わりに分解法を使用すると、計算が高速になり、メモリ不足を回避できます。

"分解法" ("チャンクおよびワーキング セット法" とも呼ばれます) では、すべての観測値をワーキング セットおよび残りのセットという 2 つの互いに素な集合に分割します。そして、各反復でワーキング セットの要素のみを修正します。したがって、各反復ではグラム行列の一部の列のみが必要になり、必要なストレージの量が少なくなります。

"逐次最小最適化法" (SMO) は、SVM 問題を解くための最も一般的なアプローチです[4]。SMO では、一連の 2 点最適化を実行します。各反復では、2 つの点のワーキング セットが、2 次情報を使用する選択規則に基づいて選択されます。そして、[2]と[1]に記載されているアプローチを使用して、このワーキング セットのラグランジュ乗数を解析的に解きます。

SVM 回帰では、各反復後にアクティブ セットの勾配ベクトル $$\nabla L$$ が更新されます。勾配ベクトルについて分解した方程式は、次のようになります。

$${\left(\nabla L\right)}_n=\{\begin{array}{c}{\displaystyle \sum _{i=1}^N\left({\alpha }_i-{\alpha }_i^{*}\right)G\left(x_i,x_n\right)+\epsilon -y_n,n\le N}\\ -{\displaystyle \sum _{i=1}^N\left({\alpha }_i-{\alpha }_i^{*}\right)G\left(x_i,x_n\right)+\epsilon +y_n,n>N}\end{array}.$$

"反復単一データ アルゴリズム" (ISDA) では、各反復で 1 つのラグランジュ乗数を更新します[3]。多くの場合、ISDA は小さい正の定数 a をカーネル関数に加算することにより、バイアス項 b を使用せずに実行されます。b がなくなると双対問題の方程式における総和制約がなくなり、

$${\displaystyle \sum _{n=1}^N\left({\alpha }_i-{\alpha }^{*}\right)=0}$$

次のようになります。これにより各反復で 1 つのラグランジュ乗数を更新できるので、外れ値を削除することが SMO の場合より簡単になります。ISDA では、更新するワーキング セットとして、すべての α_n および α_n^* の値から最悪の KKT 違反値を選択します。

収束基準

これらのソルバー アルゴリズムでは、指定された収束基準が満たされるまで繰り返し計算を行います。収束基準には、いくつかのオプションがあります。

• "実行可能性ギャップ" ― 実行可能性ギャップは、次のように表されます。

  $$\Delta =\frac{J\left(\beta \right)+L\left(\alpha \right)}{J\left(\beta \right)+1},$$

  ここで、J(β) は主目的、L(α) は双対目的です。各反復後、実行可能性ギャップが評価されます。GapTolerance で指定した値より実行可能性ギャップが小さくなった場合、収束基準が満たされ、解が返されます。

• "勾配差分" ― 各反復後、勾配ベクトル $$\nabla L$$ が評価されます。現在の反復と前回の反復における勾配ベクトルの値の差分が DeltaGradientTolerance で指定した値より小さくなった場合、収束基準が満たされ、解が返されます。

• KKT 違反の最大値 — 各反復後、すべての α_n および α_n^* の値について KKT 違反値が評価されます。違反の最大値が KKTTolerance で指定した値より小さくなった場合、収束基準が満たされ、解が返されます。

参照

[1] Fan, R.E. , P.H. Chen, and C.J. Lin. "A Study on SMO-Type Decomposition Methods for Support Vector Machines." IEEE Transactions on Neural Networks, Vol. 17:893–908, 2006.

[2] Fan, R.E. , P.H. Chen, and C.J. Lin. "Working Set Selection Using Second Order Information for Training Support Vector Machines." The Journal of Machine Learning Research, Vol. 6:1871–1918, 2005.

[3] Huang, T.M., V. Kecman, and I. Kopriva. Kernel Based Algorithms for Mining Huge Data Sets: Supervised, Semi-Supervised, and Unsupervised Learning. Springer, New York, 2006.

[4] Platt, J. Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines. Technical Report MSR-TR-98–14, 1999.

[5] Vapnik, V. The Nature of Statistical Learning Theory. Springer, New York, 1995.

参考

RegressionSVM | fitrsvm | predict | resubPredict

関連するトピック

• 線形サポート ベクター マシン回帰モデルの学習
• サポート ベクター マシン回帰モデルの学習
• SVM 回帰モデルの交差検証
• SVM 回帰の最適化