ソフトマージンSVMの双対問題
サポートベクターマシン（SVM）は、分類問題において最適な決定境界を見つける強力な機械学習手法です。ソフトマージンSVMは、完全に線形分離できないデータに対してもうまく動作するよう拡張されたバージョンです。
ソフトマージンSVMの理論
Step 1: 原問題の定式化
線形分離不可能な場合の目的関数：
$\min_{\mathbf{w}, b, \boldsymbol{\xi}} \frac{1}{2}\|\mathbf{w}\|^2 + C\sum_{i=1}^{n}\xi_i$
制約条件：
$y_i(\mathbf{w}^T\mathbf{x}_i + b) \geq 1 - \xi_i, \quad \xi_i \geq 0, \quad i = 1, \ldots, n$
ここで：
- $\mathbf{w}$：重みベクトル
- $b$：バイアス項
- $\xi_i$：スラック変数（誤分類の許容度）
- $C$：正則化パラメータ（誤分類のペナルティ）
ソフトマージンの意義
ソフトマージンSVMでは、スラック変数$\xi_i$を導入することで、一部のデータ点がマージン内や間違った側に分類されることを許可します。これにより、ノイズを含むデータや線形分離不可能なデータに対してもロバストな分類器を構築できます。
Step 2: ラグランジュ関数の構築
原問題のラグランジュ関数：
$L(\mathbf{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\mu}) = \frac{1}{2}\|\mathbf{w}\|^2 + C\sum_{i=1}^{n}\xi_i - \sum_{i=1}^{n}\alpha_i[y_i(\mathbf{w}^T\mathbf{x}_i + b) - 1 + \xi_i] - \sum_{i=1}^{n}\mu_i\xi_i$
ここで、$\alpha_i \geq 0$と$\mu_i \geq 0$はラグランジュ乗数です。
Step 3: KKT条件と双対問題導出
原問題の最適性条件（KKT条件）：
$\frac{\partial L}{\partial \mathbf{w}} = \mathbf{w} - \sum_{i=1}^{n}\alpha_i y_i \mathbf{x}_i = 0$
$\frac{\partial L}{\partial b} = -\sum_{i=1}^{n}\alpha_i y_i = 0$
$\frac{\partial L}{\partial \xi_i} = C - \alpha_i - \mu_i = 0$
重要な関係式：
- $\mathbf{w} = \sum_{i=1}^{n}\alpha_i y_i \mathbf{x}_i$
- $\sum_{i=1}^{n}\alpha_i y_i = 0$
- $\alpha_i + \mu_i = C$
Step 4: 双対問題の導出
KKT条件を原問題に代入して双対問題を得ます：
$\max_{\boldsymbol{\alpha}} \sum_{i=1}^{n}\alpha_i - \frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_i \alpha_j y_i y_j \mathbf{x}_i^T \mathbf{x}_j$
制約条件：
$0 \leq \alpha_i \leq C, \quad i = 1, \ldots, n$
$\sum_{i=1}^{n}\alpha_i y_i = 0$
双対係数の制約$0 \leq \alpha_i \leq C$の導出
KKT条件から$\alpha_i + \mu_i = C$かつ$\mu_i \geq 0$なので：
- $\mu_i \geq 0$ ⟹ $\alpha_i \leq C$
- $\alpha_i \geq 0$（ラグランジュ乗数の非負性）
したがって、$0 \leq \alpha_i \leq C$が成り立ちます。
Step 5: カーネル関数への拡張
非線形カーネルを用いた双対問題：
$\max_{\boldsymbol{\alpha}} \sum_{i=1}^{n}\alpha_i - \frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_i \alpha_j y_i y_j K(\mathbf{x}_i, \mathbf{x}_j)$
内積$\mathbf{x}_i^T \mathbf{x}_j$がカーネル関数$K(\mathbf{x}_i, \mathbf{x}_j)$に置き換わります。
一般的なカーネル関数：
- 線形カーネル：$K(\mathbf{x}_i, \mathbf{x}_j) = \mathbf{x}_i^T \mathbf{x}_j$
- RBFカーネル：$K(\mathbf{x}_i, \mathbf{x}_j) = \exp(-\gamma\|\mathbf{x}_i - \mathbf{x}_j\|^2)$
- 多項式カーネル：$K(\mathbf{x}_i, \mathbf{x}_j) = (\mathbf{x}_i^T \mathbf{x}_j + r)^d$
Step 6: サポートベクターの判定
双対係数の値による分類：
| 双対係数$\alpha_i$ | 対応するデータ点 | 特徴 |
|---|
| $\alpha_i = 0$ | 非サポートベクター | 決定境界に影響しない |
| $0 < \alpha_i < C$ | 境界上のサポートベクター | マージン境界上（$\xi_i = 0$） |
| $\alpha_i = C$ | 内部または誤分類サポートベクター | マージン内部または誤分類（$\xi_i > 0$） |
Step 7: 決定関数
分類関数：
$f(\mathbf{x}) = \text{sign}\left(\sum_{i \in SV}\alpha_i y_i K(\mathbf{x}_i, \mathbf{x}) + b\right)$
ここで、$SV$はサポートベクターの集合（$\alpha_i > 0$となるインデックス）です。
バイアス項の計算：
境界上のサポートベクター（$0 < \alpha_i < C$）について：
$b = y_i - \sum_{j \in SV}\alpha_j y_j K(\mathbf{x}_j, \mathbf{x}_i)$
Step 8: 正則化パラメータ$C$の意味
$C$パラメータの影響
- $C$が大きい：誤分類を強くペナルティ ⟹ ハードマージンに近い ⟹ 過学習リスク
- $C$が小さい：誤分類を許容 ⟹ ソフトマージン ⟹ 汎化性能向上
- $C \to \infty$：ハードマージンSVMに収束
- $C \to 0$：すべてのデータを誤分類
Step 9: 最適化アルゴリズム
SMO（Sequential Minimal Optimization）アルゴリズム：
- 2つの双対係数を同時に更新
- 解析的に最適解を計算
- 制約条件を満たすよう調整
- 収束まで反復
収束条件：
KKT条件の満足：
- $\alpha_i = 0$ ⟹ $y_i f(\mathbf{x}_i) \geq 1$
- $0 < \alpha_i < C$ ⟹ $y_i f(\mathbf{x}_i) = 1$
- $\alpha_i = C$ ⟹ $y_i f(\mathbf{x}_i) \leq 1$
SVMの利点と応用
Step 10: 理論的優位性
- 最大マージン原理：汎化誤差の上界を最小化
- 凸最適化：大域最適解の保証
- カーネルトリック：高次元特徴空間での効率的計算
- スパース解：サポートベクターのみが重要
実用的な応用：
- テキスト分類：スパム検出、文書分類
- 画像認識：顔認識、物体検出
- バイオインフォマティクス：遺伝子分類、タンパク質分類
- 金融：信用リスク評価、不正検出
選択肢の検証
| 選択肢 | 正誤 | 理由 |
|---|
| $0 \leq \alpha_i \leq C$ | ✓ 正 | KKT条件から導出される制約 |
| $\alpha_i \geq 0$のみ | ✗ 誤 | ソフトマージンでは上界$C$が存在 |
| カーネル不含 | ✗ 誤 | 目的関数に$K(\mathbf{x}_i, \mathbf{x}_j)$が含まれる |
| $C$が現れない | ✗ 誤 | 制約条件で$\alpha_i \leq C$として現れる |
したがって、正答は「双対係数$\alpha_i$の制約は$0 \leq \alpha_i \leq C$である」です。