サポートベクターマシン（Support Vector Machine, SVM）は、与えられたデータに対してマージン（分類境界とデータ点との最小距離）を最大化する超平面を求めることにより、高い汎化性能を実現する教師あり学習手法である。ここで、サポートベクターとは、分類境界（決定境界）に最も近いデータ点のことである。サポートベクターマシンの本質は凸最適化問題として定式化され、さらに双対化とカーネルトリックにより非線形分類へと自然に拡張される。また、RKHSにおける正則化経験リスク最小化として統一的に理解され、統計的学習理論とも深く結びついている。
ラベル付きデータ
\[\{(x_i, y_i)\}_{i=1}^n,\quad x_i \in \mathbb{R}^d,\; y_i \in \{-1,+1\}\]
を考える。分類関数は
\[f(x) = w^T x + b\]
で与えられ、その符号 $\mathrm{sign}(f(x))$ によりクラスを判定する。
データが線形分離可能な場合、SVMは幾何学的マージン
\[\gamma = \min_i \frac{y_i (w^T x_i + b)}{\|w\|}\]
を最大化する問題として定式化される。スケーリング不変性を用いて関数マージンを1に固定すると、次の凸最適化問題に帰着する：
\[\min_{w,b} \frac{1}{2}\|w\|^2\quad \text{s.t.} \quad y_i (w^T x_i + b) \ge 1\]
このとき幾何学的マージンは $2/\|w\|$ となる。
実際にはノイズや重なりが存在するため、スラック変数 $\xi_i \ge 0$ を導入して
\[\min_{w,b,\xi}\frac{1}{2}\|w\|^2 + C \sum_{i=1}^n \xi_i\]
\[\text{s.t.} \quad y_i (w^T x_i + b) \ge 1 - \xi_i\]
とする。これはヒンジ損失
\[\ell(y,f(x)) = \max(0,\,1 - y f(x))\]
を用いて
\[\min_{w,b}\frac{1}{2}\|w\|^2 + C \sum_{i=1}^n \ell(y_i,f(x_i))\]
と等価である。したがってSVMは正則化付き経験リスク最小化の一例である。
ラグランジュ関数を導入すると、双対問題は
\[\max_{\alpha}\sum_{i=1}^n \alpha_i- \frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j \langle x_i, x_j \rangle\]
\[\text{s.t.} \quad0 \le \alpha_i \le C,\quad\sum_{i=1}^n \alpha_i y_i = 0\]
となる。KKT条件により
\[w = \sum_{i=1}^n \alpha_i y_i x_i\]
が成立し、さらに補完スラック条件
\[\alpha_i \bigl( y_i f(x_i) - 1 + \xi_i \bigr)=0\]
から、$\alpha_i > 0$ の点のみが境界に寄与することが分かる。
$\alpha_i > 0$ を満たす点はサポートベクターと呼ばれ、決定関数に寄与する。多くの点で $\alpha_i=0$ となるため、解は疎であり、計算効率および解釈性に優れる。
双対解に基づく決定関数は
\[f(x) = \sum_{i=1}^n \alpha_i y_i \langle x_i, x \rangle + b\]
であり、$b$ はKKT条件を満たすサポートベクターから計算される。
\[b = y_i - \sum_{j} \alpha_j y_j \langle x_j, x_i \rangle\quad (\text{for } 0< \alpha_i < C)\]
双対問題では内積のみが現れるため、これをカーネル関数
\[k(x,x') = \langle \phi(x), \phi(x') \rangle\]
に置き換えることで、非線形分類が可能となる。決定関数は
\[f(x) = \sum_{i=1}^n \alpha_i y_i k(x_i, x) + b\]
となる。
特にRBFカーネルは無限次元RKHSに対応し、非常に高い表現力を持つ。
SVMはRKHS $\mathcal{H}$ 上で
\[\min_{f \in \mathcal{H}}\frac{1}{2}\|f\|_{\mathcal{H}}^2+ C \sum_{i=1}^n \ell(y_i,f(x_i))\]
という正則化問題として表される。表現定理により解は
\[f(x) = \sum_{i=1}^n \alpha_i k(x_i, x)\]
の形を持つ。ここでノルム $\|f\|_{\mathcal{H}}$ は関数の滑らかさ（複雑性）を制御する。
SVMは構造リスク最小化（SRM）に基づき、経験誤差とモデル複雑性のトレードオフを制御する。マージン最大化はVC次元の上界を小さくし、汎化誤差の上界を改善することが知られている。
SVMの目的関数は凸であり、制約も線形であるため、強双対性が成立する。したがって局所最適解は常に大域最適解である。この点はニューラルネットワークなどの非凸最適化と対照的である。
双対問題は二次計画問題（QP）であり、SMO（Sequential Minimal Optimization）などのアルゴリズムで効率的に解かれる。カーネルSVMは一般に $O(n^2)$ メモリ・$O(n^3)$ 計算を要するため、大規模データでは線形SVMや近似法が用いられる。
サポートベクターマシンは、マージン最大化という幾何学的原理と凸最適化に基づく厳密な理論を持つ分類手法である。双対問題により内積表現へと還元され、カーネルトリックにより非線形問題に拡張される。またRKHSにおける正則化問題として統一的に理解され、統計的学習理論と計算最適化の両面から強固な基盤を持つ、機械学習における最重要手法の一つである。
Mathematics is the language with which God has written the universe.