はじめに
サポートベクターマシン（SVM）は、分類と回帰に用いられる教師あり学習手法です。クラス間のマージン（余裕）を最大化する決定境界を求めることで、汎化性能の高い分類器を構築します。
本記事では、このマージン最大化問題がなぜ「双対問題」と呼ばれる別の最適化問題に姿を変えるのか、そしてその過程で現れるKKT条件が何を意味するのかを、ラグランジュ関数の停留条件から省略なく導出します。導出結果は sklearn.svm.SVC で実際に学習したモデルの内部変数と突き合わせ、理論と実装が一致することを数値で確認します。カーネルトリックの数学的正当性（Mercerの定理）やRBFカーネルの無限次元性については、発展編の
SVMのカーネル設計
に譲り、本記事はマージン最大化・双対導出・ソフトマージンという基礎理論に焦点を絞ります。
線形SVM
ハードマージン
2クラスの学習データ \(\{(\mathbf{x}_i, y_i)\}_{i=1}^{n}\) （\(y_i \in \{-1, +1\}\) ）が線形分離可能な場合、決定境界は次の最適化問題で求まります。
\[\min_{\mathbf{w}, b} \frac{1}{2} \|\mathbf{w}\|^2 \tag{1}\] \[\text{subject to} \quad y_i(\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1, \quad \forall i \tag{2}\]点 \(\mathbf{x}_i\) から超平面 \(\mathbf{w}\cdot\mathbf{x}+b=0\) までの符号付き距離は \((\mathbf{w}\cdot\mathbf{x}_i+b)/\|\mathbf{w}\|\) で与えられます。制約(2)により、この距離の絶対値は少なくとも \(1/\|\mathbf{w}\|\) 以上になるため、両クラスを合わせたマージンの幅は \(2/\|\mathbf{w}\|\) です。したがって \(\|\mathbf{w}\|\) を最小化することはマージンの最大化に等しく、式(1)(2)は「マージンを最大にする超平面を求める」という目的を凸二次計画問題として書き下したものになっています。
ソフトマージン
線形分離不可能な場合、スラック変数 \(\xi_i \geq 0\) を導入します。
\[\min_{\mathbf{w}, b, \xi} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^{n} \xi_i \tag{3}\] \[\text{subject to} \quad y_i(\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1 - \xi_i, \quad \xi_i \geq 0 \tag{4}\]\(C\) は正則化パラメータで、マージンの大きさと誤分類のトレードオフを制御します。\(\xi_i\) の値は各サンプルの状態を表します。
- \(\xi_i = 0\) ：マージンの外側で正しく分類されている
- \(0 < \xi_i \leq 1\) ：マージンの内側だが正しく分類されている
- \(\xi_i > 1\) ：誤分類されている
ハードマージン (1)(2) は、ソフトマージンで \(C \to \infty\) とした極限（誤分類を一切許容しない）に相当します。以下の双対導出はソフトマージンの一般形で行い、ハードマージンはその特殊ケースとして含まれます。
ラグランジュ双対問題とKKT条件の導出
ラグランジュ関数
主問題(3)(4)の不等式制約に対し、マージン制約 \(y_i(\mathbf{w}\cdot\mathbf{x}_i+b) - 1 + \xi_i \geq 0\) 用の未定乗数 \(\alpha_i \geq 0\) と、非負制約 \(\xi_i \geq 0\) 用の未定乗数 \(\mu_i \geq 0\) を導入し、ラグランジュ関数を作ります。
\[ L(\mathbf{w}, b, \xi, \alpha, \mu) = \frac{1}{2}\|\mathbf{w}\|^2 + C\sum_{i=1}^{n}\xi_i - \sum_{i=1}^{n}\alpha_i\big[y_i(\mathbf{w}\cdot\mathbf{x}_i+b) - 1 + \xi_i\big] - \sum_{i=1}^{n}\mu_i\xi_i \tag{5} \]主問題は \(\min_{\mathbf{w},b,\xi}\max_{\alpha\geq 0,\mu\geq 0} L\) と等価です。双対問題は \(\max \min\) の順序を入れ替えたもので、内側の \(\min_{\mathbf{w},b,\xi} L\) を解析的に求めることで得られます。
停留条件（KKT条件の第一部）
\(L\) を \(\mathbf{w}, b, \xi_i\) について偏微分し0とおきます（内側の最小化の一階条件）。
\[ \frac{\partial L}{\partial \mathbf{w}} = \mathbf{w} - \sum_{i=1}^{n}\alpha_i y_i \mathbf{x}_i = 0 \quad\Longrightarrow\quad \mathbf{w} = \sum_{i=1}^{n}\alpha_i y_i \mathbf{x}_i \tag{6} \] \[ \frac{\partial L}{\partial b} = -\sum_{i=1}^{n}\alpha_i y_i = 0 \quad\Longrightarrow\quad \sum_{i=1}^{n}\alpha_i y_i = 0 \tag{7} \] \[ \frac{\partial L}{\partial \xi_i} = C - \alpha_i - \mu_i = 0 \quad\Longrightarrow\quad \mu_i = C - \alpha_i \tag{8} \]式(6)は「決定境界の法線ベクトル \(\mathbf{w}\) が学習データの重み付き和で表せる」ことを、式(7)は双対変数に対する等式制約を、式(8)は \(\mu_i \geq 0\) と合わせて \(\alpha_i \leq C\) という上限を与えます。
KKT条件のまとめ
式(6)〜(8)の停留条件に、以下を合わせたものがKKT（Karush-Kuhn-Tucker）条件です。
- 主問題の実行可能性：\(y_i(\mathbf{w}\cdot\mathbf{x}_i+b) - 1 + \xi_i \geq 0\) 、\(\xi_i \geq 0\)
- 双対の実行可能性：\(\alpha_i \geq 0\) 、\(\mu_i \geq 0\) （式(8)と合わせて \(0 \leq \alpha_i \leq C\) ）
- 相補性条件（complementary slackness）： \( \alpha_i\big[y_i(\mathbf{w}\cdot\mathbf{x}_i+b) - 1 + \xi_i\big] = 0, \qquad \mu_i\xi_i = 0 \tag{9} \)
主問題が凸二次計画問題（目的関数が凸、制約が全てアフィン）であるため、KKT条件は大域最適解の必要十分条件になります。相補性条件(9)は「制約が余裕を持って満たされている（不等号が厳密）なら対応する乗数は0、乗数が正なら制約は等号で満たされる」ことを意味し、次節のサポートベクターの分類の根拠になります。
双対問題への代入
式(6)〜(8)を式(5)に代入し、\(\mathbf{w}, b, \xi\) を消去します。\(\xi_i\) を含む項は
\[ C\xi_i - \alpha_i\xi_i - \mu_i\xi_i = \xi_i(C - \alpha_i - \mu_i) = 0 \quad (\because \text{式(8)}) \]としてすべて消え、\(b\) を含む項は式(7)により \(-b\sum_i \alpha_i y_i = 0\) で消えます。残る \(\mathbf{w}\) の項は、式(6)を使うと
\[ \frac{1}{2}\|\mathbf{w}\|^2 - \sum_{i=1}^n \alpha_i y_i(\mathbf{w}\cdot\mathbf{x}_i) = \frac{1}{2}\mathbf{w}\cdot\mathbf{w} - \mathbf{w}\cdot\mathbf{w} = -\frac{1}{2}\sum_{i,j}\alpha_i\alpha_j y_i y_j(\mathbf{x}_i\cdot\mathbf{x}_j) \]と整理できます。以上より、双対問題は次の形になります。
\[\max_{\alpha} \sum_{i=1}^{n} \alpha_i - \frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j (\mathbf{x}_i \cdot \mathbf{x}_j) \tag{10}\] \[\text{subject to} \quad 0 \leq \alpha_i \leq C, \quad \sum_{i=1}^{n} \alpha_i y_i = 0 \tag{11}\]主問題(3)(4)が \(\mathbf{w} \in \mathbb{R}^d\) （特徴次元）についての最適化だったのに対し、双対問題(10)(11)は \(\alpha \in \mathbb{R}^n\) （サンプル数）についての最適化であり、データは内積 \(\mathbf{x}_i \cdot \mathbf{x}_j\) を通じてのみ現れます。この性質が次章のカーネルトリックを可能にします。
サポートベクターの3分類
相補性条件(9)から、最適解における各サンプルは \(\alpha_i\) の値に応じて3種類に分類できます。
| \(\alpha_i\) の値 | \(\mu_i\) （式8より） | \(\xi_i\) （相補性より） | 意味 | 幾何的な位置 |
|---|---|---|---|---|
| \(\alpha_i = 0\) | \(\mu_i = C > 0\) | \(\xi_i = 0\) | 非サポートベクター | マージンの外側（\(y_i(\mathbf{w}\cdot\mathbf{x}_i+b) > 1\) ） |
| \(0 < \alpha_i < C\) | \(\mu_i = C-\alpha_i>0\) | \(\xi_i = 0\) | 自由サポートベクター | マージン境界上ちょうど（\(y_i(\mathbf{w}\cdot\mathbf{x}_i+b) = 1\) ） |
| \(\alpha_i = C\) | \(\mu_i = 0\) | \(\xi_i \geq 0\) は任意 | 境界サポートベクター | マージン内部または誤分類側（\(y_i(\mathbf{w}\cdot\mathbf{x}_i+b) \leq 1\) ） |
サポートベクターとは、\(\alpha_i > 0\) を満たす点全体（自由サポートベクター＋境界サポートベクター）のことです。式(6)より決定境界の法線ベクトル \(\mathbf{w}\) は \(\alpha_i=0\) の点を一切参照せず、サポートベクターのみの線形結合で書けます。これがSVMの疎性（sparsity）の理論的根拠です。
切片 \(b\) は、自由サポートベクター（\(0 < \alpha_i < C\) ）が厳密にマージン境界上にあること（\(y_i(\mathbf{w}\cdot\mathbf{x}_i+b)=1\) ）を使い、\(b = y_i - \mathbf{w}\cdot\mathbf{x}_i\) を自由サポートベクター全体で平均して求めます。エッジケースとして、自由サポートベクターが1つも存在しない（全ての \(\alpha_i\) が \(0\) か \(C\) のどちらか）場合は \(b\) が一意に定まらず、libsvm/scikit-learnはKKT条件を満たす区間の中点を採用するなどの実装上の工夫を行っています。
数値実験：KKT条件を実際に検証する
上記の導出が実装と一致することを、sklearn.svm.SVC の内部変数を使って検証します。
import numpy as np
from sklearn.svm import SVC
from sklearn.datasets import make_blobs
# 重なりのある2クラスタ（ソフトマージンが必要なケース）を生成
X, y = make_blobs(n_samples=40, centers=[[-1.0, 0.0], [1.0, 0.0]],
cluster_std=1.35, random_state=42)
y = np.where(y == 0, -1, 1)
C = 1.0
clf = SVC(kernel='linear', C=C)
clf.fit(X, y)
w = clf.coef_[0]
b = clf.intercept_[0]
# dual_coef_ = alpha_i * y_i （サポートベクターのみ）から alpha_i を復元
dual_coef = clf.dual_coef_[0]
sv_idx = clf.support_
alpha_sv = dual_coef * y[sv_idx]
# (1) 停留条件: w = sum(alpha_i * y_i * x_i)
w_from_sv = (dual_coef[:, None] * X[sv_idx]).sum(axis=0)
# (2) 双対の等式制約: sum(alpha_i * y_i) = 0
sum_alpha_y = np.sum(dual_coef)
# (3) alpha_i で3分類し、functional margin y_i(w.x_i+b) の範囲を確認
functional_margin = y * (X @ w + b)
alpha_full = np.zeros(len(X))
alpha_full[sv_idx] = alpha_sv
tol = 1e-6
non_sv = alpha_full <= tol
free_sv = (alpha_full > tol) & (alpha_full < C - tol)
bound_sv = alpha_full >= C - tol
このコードを実際に実行した結果は次の通りでした。
n_samples = 40, n_support_vectors = 19, C = 1.0
[stationarity] w (sklearn clf.coef_) : [0.957959 0.211655]
[stationarity] w (sum alpha_i y_i x_i) : [0.957959 0.211655]
max abs diff: 0.0
[dual feasibility] sum(alpha_i * y_i) = 0.0
alpha_i = 0 (非サポートベクター) : 21点, functional margin range = [1.0500, 3.0717]
0 < alpha_i < C (自由サポートベクター): 3点, functional margin range = [1.0000, 1.0001]
alpha_i = C (境界サポートベクター): 16点, functional margin range = [-1.9175, 0.9701]
free SVのalpha値: [0.834443, 0.105135, 0.939578]
free SVのfunctional marginと理論値1.0との最大絶対差: 5.97e-05
式(6)の \(\mathbf{w} = \sum \alpha_i y_i \mathbf{x}_i\)
は clf.coef_ と完全に一致（差0.0）し、式(7)の \(\sum \alpha_i y_i = 0\)
も厳密に成立しています。さらに相補性条件が予言する通り、自由サポートベクター（\(0 < \alpha_i < C\)
）3点はfunctional marginがほぼ厳密に \(1.0\)
（数値誤差 \(6\times10^{-5}\)
程度、SMOソルバーの収束許容誤差 tol に起因）であり、境界サポートベクター（\(\alpha_i=C\)
）はマージン内部から誤分類側まで幅広く分布し、非サポートベクター（\(\alpha_i=0\)
）は全てマージンの外側（functional margin \(> 1\)
）に収まっています。理論から導いた3分類が、学習済みモデルの中で寸分違わず再現されていることが確認できました。
下図はこの検証結果を可視化したものです。
左図(a)は決定境界とマージン境界、および3種類のサポートベクター（灰色=非SV、青=自由SV、赤=境界SV）を示しています。自由SV（青）がちょうどマージン境界の破線上に並んでいることが視覚的にも確認できます。右図(b)は横軸をfunctional margin \(y_i(\mathbf{w}\cdot\mathbf{x}_i+b)\) 、縦軸を \(\alpha_i\) として全40点をプロットしたもので、非SVは \(\alpha_i=0\) の水平線上（margin \(>1\) ）に、自由SVはmargin \(=1\) の垂直線上に、境界SVは \(\alpha_i=C=1\) の水平線上に整列する様子が一目でわかります。これは相補性条件(9)が定める3つの領域そのものです。
カーネルトリック
双対問題(10)(11)ではデータが内積 \(\mathbf{x}_i \cdot \mathbf{x}_j\) を通じてのみ現れることを利用し、内積をカーネル関数 \(K(\mathbf{x}_i, \mathbf{x}_j) = \phi(\mathbf{x}_i) \cdot \phi(\mathbf{x}_j)\) で置き換えることで、高次元空間への写像 \(\phi\) を明示的に計算せずに非線形分類を実現します。
| カーネル | 定義 | 特徴 |
|---|---|---|
| 線形 | \(K(\mathbf{x}, \mathbf{y}) = \mathbf{x} \cdot \mathbf{y}\) | 線形分離可能なデータ |
| RBF（ガウス） | \(K(\mathbf{x}, \mathbf{y}) = \exp(-\gamma\|\mathbf{x}-\mathbf{y}\|^2)\) | 最も汎用的 |
| 多項式 | \(K(\mathbf{x}, \mathbf{y}) = (\gamma \mathbf{x} \cdot \mathbf{y} + r)^d\) | 特徴の交互作用 |
任意の2変数関数をカーネルとして使えるわけではなく、有限個のデータ点に対するグラム行列が半正定値であること（Mercerの定理）が必要十分条件です。この妥当性判定の数値的検証、RBFカーネルが無限次元特徴写像に対応することのRandom Fourier Featuresによる実証、\(\gamma\) の過学習・未学習遷移の定量評価は、発展編の SVMのカーネル設計：Mercerの定理・グラム行列の正定値性とRandom Fourier Features で詳しく扱っています。
Python実装
import numpy as np
import matplotlib.pyplot as plt
from sklearn.svm import SVC
from sklearn.datasets import make_moons, make_circles
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import accuracy_score
# --- データ生成 ---
X, y = make_moons(n_samples=300, noise=0.2, random_state=42)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3,
random_state=42)
scaler = StandardScaler()
X_train = scaler.fit_transform(X_train)
X_test = scaler.transform(X_test)
# --- 各カーネルの比較 ---
kernels = ['linear', 'rbf', 'poly']
fig, axes = plt.subplots(1, 3, figsize=(15, 4))
for ax, kernel in zip(axes, kernels):
clf = SVC(kernel=kernel, C=1.0, gamma='scale')
clf.fit(X_train, y_train)
acc = accuracy_score(y_test, clf.predict(X_test))
# 決定境界の描画
xx, yy = np.meshgrid(np.linspace(-3, 3, 200), np.linspace(-3, 3, 200))
Z = clf.decision_function(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)
ax.contourf(xx, yy, Z, levels=[-1, 0, 1], alpha=0.2, colors=['blue', 'red'])
ax.contour(xx, yy, Z, levels=[-1, 0, 1], colors='k', linestyles=['--', '-', '--'])
ax.scatter(X_train[:, 0], X_train[:, 1], c=y_train, cmap='bwr', s=20, alpha=0.6)
# サポートベクターを強調
sv = clf.support_vectors_
ax.scatter(sv[:, 0], sv[:, 1], s=80, facecolors='none', edgecolors='k', linewidths=1.5)
ax.set_title(f'{kernel} (acc={acc:.3f})')
ax.set_xlim(-3, 3)
ax.set_ylim(-3, 3)
plt.tight_layout()
plt.show()
make_moons の三日月型データに対して、テストデータでの精度は線形カーネルが0.900、RBFカーネルが0.933、多項式カーネルが0.889でした。線形カーネルは直線的な境界しか引けないため三日月の湾曲部で誤分類が生じる一方、RBFカーネルはデータの非線形構造に沿った滑らかな境界を学習でき、この設定では最も高い精度を達成しています。
ハイパーパラメータ
C（正則化パラメータ）
- 大きいC: マージンが小さく、訓練データの誤分類を厳しく罰する → 過学習のリスク
- 小さいC: マージンが大きく、一部の誤分類を許容 → 未学習のリスク
式(8)の \(\mu_i = C - \alpha_i\) からもわかる通り、\(C\) は \(\alpha_i\) の上限そのものであり、境界サポートベクター（\(\alpha_i=C\) ）になり得る割合を直接制御しています。
gamma（RBFカーネル）
- 大きいgamma: 各サンプルの影響範囲が狭い → 複雑な決定境界、過学習のリスク
- 小さいgamma: 各サンプルの影響範囲が広い → 滑らかな決定境界
from sklearn.model_selection import GridSearchCV
param_grid = {'C': [0.1, 1, 10, 100], 'gamma': [1, 0.1, 0.01, 0.001]}
grid = GridSearchCV(SVC(kernel='rbf'), param_grid, cv=5, scoring='accuracy')
grid.fit(X_train, y_train)
print(f"Best params: {grid.best_params_}, Score: {grid.best_score_:.3f}")
発展的話題：ソフトマージンの損失関数を頑健化する研究
ソフトマージンのペナルティ項 \(C\sum_i \xi_i\) は、本質的にヒンジ損失 \(\max(0, 1 - y_i f(\mathbf{x}_i))\) の総和です。ヒンジ損失は外れ値から離れるほど無限に増大するため、ラベルノイズや外れ値の影響を受けやすいという弱点があります。Zhang & Yang (2023) は、この損失関数を有界化した Bounded Quantile Loss を提案し、これに基づく分類器（BQ-SVM）と回帰器（BQ-SVR）がFisher一貫性と汎化誤差の上界を持つことを理論的に示しました。損失自体が非凸になるため、凸関数の差として問題を分解し局所最適解に収束させるCCCP（concave-convex procedure）で最適化しています。ソフトマージンの \(C, \xi_i\) による定式化は、こうした損失関数設計の拡張の出発点になっています。
SVMの利点と制約
| 利点 | 制約 |
|---|---|
| 高次元データに強い | 大規模データでは学習が遅い（\(O(n^2)\) 〜\(O(n^3)\) ） |
| カーネルで非線形対応 | 確率出力には追加処理が必要 |
| 過学習しにくい | 特徴量のスケーリングが必須 |
| サポートベクターのみで決定境界 | マルチクラスは間接的（OvOまたはOvR） |
関連記事
- SVMのカーネル設計：Mercerの定理・グラム行列の正定値性とRandom Fourier Features - 本記事のカーネルトリックがなぜ妥当なのかをMercerの定理から掘り下げ、RBFカーネルの無限次元性をRandom Fourier Featuresで数値的に検証した発展編です。
- アンサンブル学習の手法と比較 - ランダムフォレスト・勾配ブースティングなどの別の分類手法を解説しています。
- Self-Attentionの仕組みとPython実装 - カーネルトリックとAttentionの類似性を理解できます。
- K-means法とGMM：クラスタリングの理論とPython実装 - 教師なし学習との対比で分類と構造発見の違いを理解できます。
- ベイズ最適化の基礎とPython実装 - SVMのハイパーパラメータ（C, gamma）の自動チューニングに活用できます。
- ベイズ線形回帰の基礎 - 回帰問題へのベイズアプローチとSVR（サポートベクター回帰）の比較が有益です。
- クロスエントロピー法：モンテカルロ最適化の実践的手法 - 最適化の別のアプローチとして比較できます。
- ガウス過程回帰の理論とPython実装 - SVMと同じRBFカーネルを使いつつ、確率的予測と不確実性定量化を提供する別系統の手法です。
- 機械学習による時系列予測・分類・異常検知ハブ - SVMを含む分類手法をタスク・データ特性から選ぶための俯瞰ハブです。
- 時系列データの異常検知：統計的手法からカルマンフィルタまで - 決定境界による分類の発展形として、One-Class SVMなど教師なし異常検知への応用がつながります。
参考文献
- Vapnik, V. N. (1995). The Nature of Statistical Learning Theory. Springer.
- Cortes, C., & Vapnik, V. (1995). “Support-vector networks”. Machine Learning, 20(3), 273-297.
- Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press. Chapter 5 (Duality).
- Zhang, J., & Yang, H. (2023). “Bounded quantile loss for robust support vector machines-based classification and regression”. Expert Systems with Applications, 242, 122759.
- scikit-learn SVM documentation