サポートベクターマシン（SVM）

🎓 レベル：発展　|　重要度：A（必須）

📎 前提：ロジスティック回帰・正則化（Ridge・Lasso・Elastic Net）・汎化と過学習・バイアスバリアンス分解　|　数理：SVM・非線形回帰・プロビット分析（統計）

要点（BLUF）

SVM は「2クラスを分ける直線（超平面）」のうち、境界から最も近いデータ点までの距離（マージン）が最大になるものを選ぶ分類器です。境界をどちらのクラスからもなるべく遠ざけることで、未知データに頑健な=汎化しやすい境界を狙います。
解くべき問題は $\min \frac12\|w\|^2$ s.t. $y_i(w^\top x_i+b)\ge1$ という凸2次計画。これを双対問題に直すと、境界を決めるのは境界ギリギリにいる一部の点（サポートベクター）だけだと分かります。
双対問題ではデータが内積でしか現れないため、その内積をカーネル関数 $K(x,x')$ に置き換えるだけで、高次元へ実際に写像せずに非線形な境界を引けます（カーネルトリック）。

1. マージン最大化という発想

ロジスティック回帰は確率 $P(y=1\mid x)$ をシグモイドでモデル化し、交差エントロピーを最小化して境界を引きました。SVM は発想が違います。確率を一切モデル化せず、純粋に幾何学的な余白だけを基準にします。

2クラスが直線（一般には超平面）で分けられるとき、分け方は無数にあります。どれも訓練データは完璧に分けますが、境界が片方のクラスにギリギリ寄っていると、新しい点がわずかにズレただけで誤分類されます。

graph LR
    subgraph BAD["境界が偏っている（マージン小）"]
        B1["境界が片側に寄る<br/>→ 少しのズレで誤分類<br/>→ 汎化に弱い"]
    end
    subgraph GOOD["マージン最大（SVM）"]
        G1["両クラスから等距離で最遠<br/>→ ズレに頑健<br/>→ 汎化に強い"]
    end
    BAD --> GOOD

SVM の主張：分けられる超平面のうち、両クラスの最近接点との余白（マージン）が最大のものが最も安全。これは「分けられる中で最も保守的な境界を選ぶ」という構造的リスク最小化の考え方に対応します。

要するに：きれいに分けるだけでなく、境界を両クラスから最大限に遠ざける。これが SVM の核心です。

2. マージンを数式にする

分離超平面を $w^\top x + b = 0$ と書きます（ $w$ は境界に直交する法線ベクトル、 $b$ は切片）。クラスラベルは $y_i \in \{+1,-1\}$ を使います（ロジスティック回帰の $\{0,1\}$ ではなく $\pm1$ にするのが SVM の流儀で、後で式が一本にまとまります）。

点 $x_i$ から超平面までの距離は、線形代数の公式で

\frac{w^\top x_i + b}{\|w\|}

です（ $w/\|w\|$ が単位法線だから、超平面の式に点を代入して法線の長さで割ると距離になります）。

ここで $(w,b)$ を定数倍しても表す超平面は同じ（ $cw^\top x + cb = 0$ も同じ平面）なので、このスケールの自由度を使い、両クラスの最近接点でちょうど $w^\top x_i + b = \pm1$ になるように目盛りを決めます。すると最近接点から境界までの距離は左右とも $1/\|w\|$ になり、マージン全幅は

\text{マージン} = \frac{2}{\|w\|}

要するに：境界から最も近い点までの余白（の両側合計）は $2/\|w\|$ 。法線 $w$ が短いほどマージンが広い、という関係です。（この導出の詳細は統計側 SVM・非線形回帰・プロビット分析に同じ式があります。）

3. ハードマージン SVM の最適化問題

マージン $2/\|w\|$ を最大化することは、分母 $\|w\|$ を最小化することと同じ。さらに $\|w\|$ の最小化は $\|w\|^2$ の最小化と同値（ $\|w\|\ge0$ なので単調）です。微分を楽にするため係数 $\frac12$ を付けて目的関数を $\frac12\|w\|^2$ とします。

制約は「すべての点を正しく分類し、かつマージンの外側に置く」こと。正例（ $y_i=+1$ ）は $w^\top x_i+b\ge+1$ 、負例（ $y_i=-1$ ）は $w^\top x_i+b\le-1$ 。 $y_i$ を掛けると一本にまとまり、

\min_{w,b}\ \frac12\|w\|^2 \quad \text{s.t.}\quad y_i(w^\top x_i + b)\ge 1\ \ (i=1,\dots,n)

要するに：マージン最大化を「目的=法線を短く、制約=全点を正しく $\pm1$ の外に置く」と書き直したもの。目的関数は2乗ノルムで凸、制約は線形なので、これは凸2次計画問題です。局所最適に捕まる心配がなく、大域最適が一意に求まります（多峰になりうる尤度最大化との大きな違い）。

この $\frac12\|w\|^2$ を小さく保つ部分は、正則化（Ridge・Lasso・Elastic Net）の L2 ペナルティ（Ridge）とまったく同じ形です。後で見るように、SVM はこの正則化の視点でも読み解けます。

4. ラグランジュ双対とサポートベクター

制約付き最適化なのでラグランジュ未定乗数法で解きます。各制約に乗数 $\alpha_i\ge0$ を当てると、

L(w,b,\alpha)=\frac12\|w\|^2 - \sum_{i=1}^{n}\alpha_i\big[y_i(w^\top x_i+b)-1\big]

$w,b$ で偏微分して0と置く（停留条件）と、

w=\sum_i \alpha_i y_i x_i, \qquad \sum_i \alpha_i y_i = 0

要するに：最適な法線 $w$ は、データ点 $x_i$ を $\alpha_i y_i$ で重みづけた和です。これを $L$ に代入すると $w,b$ が消え、 $\alpha$ だけの双対問題になります。

\max_{\alpha}\ \sum_i \alpha_i - \frac12\sum_i\sum_j \alpha_i\alpha_j\,y_i y_j\,x_i^\top x_j \quad \text{s.t.}\quad \alpha_i\ge0,\ \ \sum_i\alpha_i y_i=0

要するに：「 $w,b$ を探す問題」を「乗数 $\alpha$ を探す問題」に置き換えました。ここで重要なのは、データが $x_i^\top x_j$ という内積の形でしか現れないこと。これが後でカーネルを効かせる鍵になります。

サポートベクター（境界を決めるのは一部の点だけ）

最適解では相補性条件（KKT条件の一つ）

\alpha_i\big[y_i(w^\top x_i+b)-1\big]=0

が成り立ちます。「 $\alpha_i$ 」と「制約の余り」の積がゼロ、つまりどちらかが必ず0です。ここから点が2種類に分かれます。

マージンの外側の点（ $y_i(w^\top x_i+b)>1$ ）：括弧が正なので $\alpha_i=0$ 。 $w=\sum\alpha_i y_i x_i$ の和に一切寄与しない。
マージン境界ちょうどの点（ $y_i(w^\top x_i+b)=1$ ）： $\alpha_i>0$ になりうる。これがサポートベクター。

したがって

w=\sum_{i:\ \alpha_i>0} \alpha_i y_i x_i \quad(\text{和は実質サポートベクターのみ})

要するに：境界を決めるのは、境界ギリギリにいる少数のサポートベクターだけ。遠くの点は何個あっても境界に影響しません。サポートベクター以外を削除して再学習しても、得られる境界はまったく同じです。これは「全データの平均・分散で境界を動かす」判別分析やロジスティック回帰と根本的に違う、SVM の際立った特徴です。

flowchart TD
    A["全データ点"] --> B{"KKT相補性条件<br/>αᵢ・（制約の余り）= 0"}
    B -->|"マージン外側<br/>余りが正"| C["αᵢ = 0<br/>境界に寄与しない"]
    B -->|"マージン境界上<br/>余りが0"| D["αᵢ > 0<br/>サポートベクター"]
    D --> E["w = Σ αᵢ yᵢ xᵢ<br/>（サポートベクターだけで決まる）"]

5. ソフトマージン（スラック変数とハイパーパラメータ C）

現実のデータは完全には分離できない（クラスが少し混じる、外れ値がある）のが普通です。そのままハードマージンを課すと、たった1点の外れ値のために境界が大きく歪んだり、そもそも解が存在しなかったりします。

そこでスラック変数 $\xi_i\ge0$ を導入し、「制約をどれだけ破ったか」を許す代わりに、破った総量にペナルティ $C$ を課します。

\min_{w,b,\xi}\ \frac12\|w\|^2 + C\sum_{i=1}^{n}\xi_i \quad \text{s.t.}\quad y_i(w^\top x_i+b)\ge 1-\xi_i,\ \ \xi_i\ge0

要するに：マージンの内側へ $\xi_i$ だけ食い込むのを許すが、その総量に料金 $C$ を払わせる。 $\xi_i=0$ なら正しくマージン外、 $0<\xi_i<1$ ならマージン内だが正しい側、 $\xi_i>1$ なら誤分類です。

C の役割（マージンの広さと誤分類のトレードオフ）

$C$ は「制約違反をどれだけ嫌うか」を決めるつまみです。

$C$ が大きい：違反に重いペナルティ。多少マージンを狭めても全点を正しく分けようとする → ハードマージンに近づき、過学習しやすい。
$C$ が小さい：違反に寛容。多少の誤分類を許してでもマージンを広く・境界を滑らかに → 汎化重視だが学習誤差は増える。

これは汎化と過学習・バイアスバリアンス分解のバイアス・バリアンスの綱引きそのもの。 $C$ は交差検証で選ぶハイパーパラメータです。

ヒンジ損失との等価性（正則化としての SVM）

制約を最良に埋める $\xi_i = \max\{0,\ 1-y_i(w^\top x_i+b)\}$ を代入すると、ソフトマージン SVM は

\min_{w,b}\ \underbrace{\sum_i \max\{0,\ 1-y_i(w^\top x_i+b)\}}_{\text{ヒンジ損失}} + \underbrace{\frac{1}{2C}\|w\|^2}_{L_2\text{正則化}}

の形に書けます。要するに：SVM は「ヒンジ損失＋ L2 正則化」の最小化と等価です。ヒンジ損失は「マージン内に入ったら線形に罰し、十分外なら罰しない」損失で、 $\frac{1}{2C}\|w\|^2$ は正則化（Ridge・Lasso・Elastic Net）の Ridge とまったく同じ罰則項です。ここで $C$ が小さいほど罰則が強い= $C$ は正則化の強さの逆数に当たる点に注意してください。

ロジスティック回帰（交差エントロピー損失＋正則化）と SVM（ヒンジ損失＋正則化）は、「損失関数だけが違う、同じ正則化付き線形分類器の兄弟」と見ることができます。

6. カーネルトリック（非線形分離）

線形では分けられないデータも、高次元の特徴空間に写像 $\phi(x)$ すれば線形分離できることがあります（例：同心円状の2クラスは $z=x_1^2+x_2^2$ の軸を足せばある半径で平面分離できる）。しかし $\phi(x)$ を陽に計算するのは高次元では重く、無限次元では不可能です。ここで4節の双対問題を思い出すと、データは内積 $x_i^\top x_j$ の形でしか現れませんでした。写像後も必要なのは内積 $\phi(x_i)^\top\phi(x_j)$ だけ。そこでこの内積をカーネル関数

K(x_i,x_j)=\phi(x_i)^\top\phi(x_j)

で丸ごと置き換えます。要するに：高次元へ飛ばした後の内積を、元の空間の関数 $K$ 一発で計算する。写像 $\phi$ 自体は作らない。これがカーネルトリックです。

flowchart LR
    A["元の空間<br/>線形分離できない"] --> B["内積を K（x, x'）に置換<br/>（φ は陽に計算しない）"]
    B --> C["高次元の特徴空間で<br/>暗黙に線形分離"]
    C --> D["元の空間では<br/>非線形な境界"]

双対問題と判別式は、 $x_i^\top x_j$ を $K(x_i,x_j)$ に差し替えるだけです。

\max_\alpha \sum_i\alpha_i - \frac12\sum_{i,j}\alpha_i\alpha_j y_iy_j K(x_i,x_j), \quad f(x)=\operatorname{sign}\!\Big(\sum_i \alpha_i y_i K(x_i,x) + b\Big)

代表的なカーネル

多項式カーネル $K(x,x')=(x^\top x'+c)^d$ ： $d$ 次までの多項式的な特徴の相互作用に対応します。次数 $d$ を上げるほど複雑な境界を表現できますが、過学習しやすくなります。
ガウス（RBF）カーネル $K(x,x')=\exp(-\gamma\|x-x'\|^2)$ ：無限次元の特徴空間に対応し、非常に柔軟な境界を引けます。 $\gamma$ は「近さの効く範囲」を決め、 $\gamma$ が大きいほど各点の影響が局所的になり（境界が点に貼りつき）過学習しやすい、小さいほど滑らかになります。最も汎用的でまず試される定番です。

要するに：カーネルは「内積の差し替え」であって、特徴ベクトルを実際に作るわけではありません。RBF は無限次元の $\phi$ に対応しますが、計算は元空間の関数1発で済みます。なお、 $K$ が本当にある $\phi$ の内積として書けるには、 $K$ が**正定値（Mercer 条件）**を満たす必要がある、という理論的な前提だけ覚えておけば十分です。

RBF SVM では $C$ （正則化）と $\gamma$ （カーネル幅）の2つを同時に交差検証で調整します。両方が複雑さを上げる向きに効くので、グリッドサーチで一緒に探すのが定石です（→ 汎化と過学習・バイアスバリアンス分解の複雑さ調整）。

⚠️ よくある誤解

「マージン最大化なのに最小化問題なのはおかしい」ではない。マージンは $2/\|w\|$ で、分子は定数。最大化したいので分母 $\|w\|$ を最小化し、結果として目的関数は $\min\frac12\|w\|^2$ （最小化）になります。符号と分母の向きを混同しがちです。
「SVM は全データで境界を決める」は誤り。境界を決めるのはサポートベクター（ $\alpha_i>0$ ）だけ。マージン外の点（ $\alpha_i=0$ ）は何個消しても境界は不変です。「全データの重心で動く」のは判別分析の話です。
「カーネルで高次元ベクトルを実際に作っている」は誤り。作るのは内積 $K(x_i,x_j)$ だけ。RBF は無限次元 $\phi$ に対応しますが、計算は元空間の関数1発で、次元の高さは計算量に響きません。
C の向きを逆に覚えがち。 $C$ 大 → 違反に厳しい → ハードマージン寄り → 過学習しやすい。 $C$ 小 → 違反に寛容 → マージン広く滑らか。 $C$ は正則化の強さの逆数に近い役割なので、「 $C$ が大きいほど正則化が強い」と思うと逆になります。
「SVM は確率を出す」は半分誤り。素の SVM の出力は符号（どちら側か）だけで、確率は出しません。確率が欲しい場合はプラットスケーリング等で後付けします。確率モデルが本体なのはロジスティック回帰の方です。
標準化を忘れる・ $\gamma$ を大きくしすぎる。RBF も多項式も内積・距離に依存するため、標準化が前提です。また $\gamma$ が大きすぎる RBF は訓練点に貼りつく過学習境界になり、 $C$ ・ $\gamma$ を調整しないと線形 SVM に負けます。

対応するシミュレーション

simulations/svm_kernel.py：同心円状（線形分離できない）データで 線形カーネルと RBFカーネルの SVM を比較します。線形カーネルは直線でしか分けられず正解率0.5付近で失敗するのに対し、RBFカーネルはカーネルトリックで曲線の境界を引いて分離できることを可視化し、境界を支えるサポートベクターを強調表示します。

線形 vs RBFカーネル・マージン・サポートベクター