サポートベクターマシン - yuuk1's Digital Garden

# サポートベクターマシン ## 定義サポートベクターマシン(SVM)とは、2クラス分類において間隔(margin)を最大化する超平面 $f(x)=x^T\beta+\beta_0$ を求める手法であり、非分離データにはスラック変数 $\xi_i$ を許した緩和形($\min\frac12\|\beta\|^2+C\sum_i\xi_i$ s.t. $y_i(x_i^T\beta+\beta_0)\ge1-\xi_i$、式12.8)として定式化される。解は $\hat\beta=\sum_i\hat\alpha_iy_ix_i$(式12.17)の形を取り、非零の $\hat\alpha_i$ を持つ観測(サポートベクター)だけが解を規定する。基底展開 $h(x)$ による特徴空間の拡大と組み合わせ、内積 $\langle h(x),h(x')\rangle$ をカーネル関数 $K(x,x')$ で置き換える**カーネルトリック**により、$h$ を陽に計算せずに非線形決定境界を得る(式12.19-12.24)。この定式化はVapnikによる(Vapnik, 1996)。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 12 Support Vector Machines and Flexible Discriminants]] §12.2, §12.3.1) ## 主問題の2通りの導出とラグランジュ双対(Mathematics for Machine Learning) [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 12 Classification with Support Vector Machines]]は、ESLが式12.8として天下り的に与える主問題を、独立な2通りの経路から導出し両者が同一の凸二次計画に一致することを示す。第一の経路は幾何的マージン最大化で、分離超平面 $f(x)=\langle w,x\rangle+b$ からの最近傍点までの距離(マージン)を最大化する。マージンをスケール固定 $\langle w,x_a\rangle+b=1$ の下で表すと $r=1/\|w\|$ となり(式12.14)、主問題は $\min_{w,b}\frac12\|w\|^2$ s.t. $y_n(\langle w,x_n\rangle+b)\ge1$(式12.18-12.19)に帰着する。第二の経路はヒンジ損失 $\max\{0,1-t\}$ による経験リスク最小化 $\frac12\|w\|^2+C\sum_n\max\{0,1-y_nf(x_n)\}$(式12.31)であり、スラック変数 $\xi$ を $\min_\xi\xi$ s.t. $\xi\ge0,\xi\ge1-t$ と書き直すことで、幾何的定式化(式12.26)と数式的に厳密に等価であることが示される(式12.32-12.33、Theorem 12.1)。続いてラグランジュ乗数 $\alpha_n,\gamma_n$ によって主問題を双対化すると、解の表現定理 $w=\sum_n\alpha_ny_nx_n$(式12.38、ESLの式12.17と同じ形)が主変数 $w,b,\xi$ の偏微分をゼロと置くだけの機械的操作から導かれ、双対目的関数 $\frac12\sum_{i,j}y_iy_j\alpha_i\alpha_j\langle x_i,x_j\rangle-\sum_i\alpha_i$(式12.41)が訓練例間の内積のみに依存する構造が明示される。この双対はさらに、正例・負例それぞれの凸包(convex hull)間の最短距離を求める幾何問題としても等価に定式化できる(§12.3.2)。(Source: [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 12 Classification with Support Vector Machines]] §12.2.1-§12.2.5, §12.3.1-§12.3.2) ## 横断的知見 - **ESLは主問題(式12.8)を天下り的に与えるのに対し、MMLはその主問題を独立な2つの経路(幾何的マージン最大化、ヒンジ損失+正則化)から導出し両者の等価性を証明する**: この非対称性は、ESLが統計的機械学習の応用・比較実験(損失関数の選択が与える性能差、カーネル選択の次元の呪いへの脆弱性、§12.3.4)に重心を置くのに対し、MMLはその手前にある「なぜこの最適化問題が妥当なマージン最大化器なのか」という数学的正当化そのものを主題とすることに対応する。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 12 Support Vector Machines and Flexible Discriminants]] §12.2, [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 12 Classification with Support Vector Machines]] §12.2.1-§12.2.5) - **表現定理 $w=\sum_n\alpha_ny_nx_n$ はESL(式12.17)とMML(式12.38)で同じ形に到達するが、導出経路が異なる**: ESLはこれを[[カーネル法]]の一般論(RKHS上の罰則付き損失最小化の解は常に有限次元カーネル展開に定まる、第5章§5.8のkernel property)の1インスタンスとして提示するのに対し、MMLはラグランジュ双対性という[[凸最適化]]の一般的な手続き(ラグランジアンを主変数で偏微分してゼロと置く)から独立に導く。同じ結論(解がサポートベクターの線形結合で書ける)が、正則化理論(Tikhonov正則化+表現定理)と凸最適化理論(ラグランジュ双対性)という異なる数学的経路から導かれる点が、SVMという1つの手法の理論的基盤の厚みを示している。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 12 Support Vector Machines and Flexible Discriminants]] §12.3.1, [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 12 Classification with Support Vector Machines]] §12.3.1) - **カーネルトリックの正当化根拠がESLとMMLで異なる**: ESLはカーネル置換を「特徴写像 $h(x)$ による内積 $\langle h(x),h(x')\rangle$ を計算上カーネル関数 $K(x,x')$ で置き換えられる」という(RKHS正則化理論に基づく)一般原理の応用として導入するのに対し、MMLは双対SVMの目的関数が主変数 $w$ を含まず訓練例間の内積のみに依存するという構造(式12.41)を明示的に導出したうえで、その内積をカーネル関数に置き換える操作として導入する(§12.4)。後者は「なぜ内積だけを置き換えればよいのか」という問いに、双対化という具体的な計算の帰結として直接答えている点で、ESLの一般原理からの天下り的適用より一段具体的な正当化を与える。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 12 Support Vector Machines and Flexible Discriminants]] §12.3.1, [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 12 Classification with Support Vector Machines]] §12.3.1, §12.4) - **SVMは「損失+罰則」という正則化の一般形の1インスタンスであり、罰則の側ではなく損失関数の側で他の手法と分岐する**: ridge回帰([[縮小推定]])は二乗誤差損失+L2罰則、平滑化スプライン([[基底展開]])は二乗誤差損失+曲率罰則であるのに対し、SVMは**ヒンジ損失** $[1-yf(x)]_+$ + L2罰則($\min\sum_i[1-y_if(x_i)]_++\frac{\lambda}{2}\|\beta\|^2$、式12.25、$\lambda=1/C$)という同型の枠組みに属する。3者はいずれも「損失+罰則」の一般形の特殊ケースであり、SVMを他の縮小推定と分ける唯一の要素は損失関数の選択(ヒンジ損失)である。ヒンジ損失は分類器 $G(x)=\mathrm{sign}[\Pr(Y=+1|x)-\frac12]$ そのものを推定するのに対し、二乗誤差・二項逸脱度はクラス事後確率の変換を推定するという質的な違いがある(Table 12.1)。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 12 Support Vector Machines and Flexible Discriminants]] §12.3.2) - **カーネルトリックはSVMに固有の性質ではなく、RKHS上の正則化された関数推定一般が共有する性質である**: [[カーネル法]]が既に第5章§5.8で確立していた「罰則付き損失最小化の解は常に有限次元の核展開 $f(x)=\sum_i\alpha_iK(x,x_i)$ に一意に定まる」というkernel propertyは、損失関数をヒンジ損失に取り替えたSVM(式12.27-12.29)でもまったく同じ形で成立する。第12章はこの一般性を明示的に検証し、「カーネルの性質はSVMに固有で次元の呪いを回避できる」という初期の主張が誤りであることを示す実験(§12.3.4、後述)まで用意している。SVMが特別なのはカーネルではなく損失関数の選択である。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 12 Support Vector Machines and Flexible Discriminants]] §12.3.1, §12.3.3) - **カーネル法は次元の呪いを自動的には回避しない――カーネルが部分空間構造に適応できないため、加法モデルより頑健性が低い**: 4変数の分離可能なデータに6個のノイズ変数を加えた実験(Table 12.2)では、多項式SVMはノイズ変数の混入とカーネル次数の誤選択に敏感に劣化するのに対し、変数選択能力を持つ加法スプラインモデル(BRUTO)・MARSは性能をほぼ維持する。[[次元の呪い]]が第6章で確立した「構造化された仮定(加法性等)が次元の呪いを回避する」という知見が、SVM/カーネル法という第12章の文脈でも(構造化されていないカーネルでは)成り立たないことが裏付けられた形になる。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 12 Support Vector Machines and Flexible Discriminants]] §12.3.4) ## 未解決の問い - ヒンジ損失以外の「間隔最大化損失関数」(二項逸脱度・Huber化二乗ヒンジ損失)は、分離可能なデータで $\lambda\to0$ のとき最適分離超平面に収束する(§12.3.2脚注)。この収束の速さや、有限 $N$ での近似誤差はヒンジ損失とどう異なるか。 - SVM回帰(§12.3.6)の $\epsilon$-非感応損失は、Huber損失や絶対誤差損失とどのような場合に実務上異なる推定結果を与えるか。第10章のロバスト損失(Huber)との比較が体系的に必要。 - 多クラスSVM(全ペア分解、あるいは多項損失+カーネル)は、多クラスLDA/FDA/MDA(第12章後半)とどのような理論的関係にあるか。両者とも第12章内で扱われるが、章内で明示的な比較はされていない。 - MML第12章§12.5はSVMの主問題・双対問題がいずれも凸二次計画の標準形に落とし込めるとしつつ、LIBSVM・SVM-lightなど実務上の主要な実装はこの標準形QPを直接解くわけではないと述べるに留まる。SMO(Sequential Minimal Optimization)などの実務的な数値解法と、この標準形QP・劣勾配法との関係は本章の範囲外であり、確認が必要。 ## 関連 - 概念: [[カーネル法]](カーネルトリックの一般理論) / [[縮小推定]](損失+罰則の一般形) / [[基底展開]](特徴空間拡大の一般論) / [[次元の呪い]](カーネル選択と次元の呪い) / [[凸最適化]](主問題→双対問題の一般的な導出手続き) - ソース: [[@2009__Springer__The Elements of Statistical Learning - Chapter 12 Support Vector Machines and Flexible Discriminants]](応用・比較実験の視点) / [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 12 Classification with Support Vector Machines]](幾何的導出とラグランジュ双対性による数学的基盤) ## 出典 - Hastie, T., Tibshirani, R., Friedman, J., *The Elements of Statistical Learning*, 2nd Edition, Springer, 2009, Chapter 12, §12.2-12.3. - Deisenroth, M. P., Faisal, A. A., Ong, C. S., *Mathematics for Machine Learning*, Cambridge University Press, 2020, Chapter 12, §12.2-§12.4.