はじめに
本記事では、サポートベクトルマシン（SVM）のハードマージンにおける分離超平面の導出プロセスを詳しく説明します。最適化問題の設定、主問題のKKT条件、強双対性と凸性条件、そして双対問題の導出について解説します。また、主問題の実行可能領域と双対問題の関係についても触れます。
点と超平面の距離
$n$ 次元空間において、点 $\mathbf{x}_i$ と超平面 $ w_0 + \mathbf{w}^\top \mathbf{x} = 0 $ の距離は次の式で与えられます。
\text{距離} = \frac{\left| w_0 + \mathbf{w}^\top \mathbf{x}_i \right|}{\| \mathbf{w} \|}
ハードマージンSVMの最適化問題
1. 最適化問題の設定
スケーリングの問題と制約の導入
サポートベクトルマシンの目的は、データセットを線形分離する超平面を見つけ、そのマージン$d$（超平面と最も近いデータ点との距離）を最大化することです。しかし、超平面 $ w_0 + \mathbf{w}^\top \mathbf{x} = 0 $ は、$w_0$ と $\mathbf{w}$ を任意の正の定数 $ k $ でスケーリングしても同じ超平面を表します。
\begin{align}
w_0 + \mathbf{w}^\top \mathbf{x} = 0 \quad &\Longleftrightarrow \quad k w_0 + (k \mathbf{w})^\top \mathbf{x} = 0 \\
\frac{\left| w_0 + \mathbf{w}^\top \mathbf{x}_i \right|}{\| \mathbf{w} \|} \geq d
&\Longleftrightarrow
\frac{\left| k w_0 + k\mathbf{w}^\top \mathbf{x}_i \right|}{\| k\mathbf{w} \|} \geq d \\
\frac{y_i (w_0 + \mathbf{w}^\top \mathbf{x}_i) }{\| \mathbf{w} \|} \geq d
&\Longleftrightarrow
\frac{y_i(k w_0 + k\mathbf{w}^\top \mathbf{x}_i)}{\| k\mathbf{w} \|} \geq d
\end{align}
ここで、$ y_i \in { -1, 1 } $ はデータ点のクラスラベルです。このスケーリングの自由度により、$w_0$ と $\mathbf{w}$ を固定しない限り、マージンの最大化問題が一意に定まらなくなります。そこで、スケーリングを固定するために以下の制約を導入します。
y_i \left( w_0 + \mathbf{w}^\top \mathbf{x}_i \right) \geq 1, \quad \forall i
マージンの定義
導入した制約により、マージン $ d $ は次のように定義できます。
d = \frac{1}{\| \mathbf{w} \|}
したがって、マージンを最大化することは $ || \mathbf{w} || $ を最小化することと同値になります。
最適化問題の定式化
以上を踏まえて、ハードマージンSVMの最適化問題は次のように定式化されます。
-
目的関数（最小化）：
\min_{w_0, \mathbf{w}} \quad \frac{1}{2} \| \mathbf{w} \|^2 -
制約条件：
y_i \left( w_0 + \mathbf{w}^\top \mathbf{x}_i \right) \geq 1, \quad \forall i
ここで、目的関数の $ \frac{1}{2} $ は計算を簡単にするために導入されています。
主問題のKKT条件
最適化問題の最適解は、以下のKarush-Kuhn-Tucker（KKT）条件を満たします。KKT条件は、制約付き最適化問題における最適性の必要条件であり、主問題の最適性条件として記述されます。
-
実行可能領域：
y_i \left( w_0 + \mathbf{w}^\top \mathbf{x}_i \right) - 1 \geq 0, \quad \forall i -
ラグランジュ乗数の非負性（Dual feasibility）：
\alpha_i \geq 0, \quad \forall i -
停留条件：
\frac{\partial L}{\partial w_0} = 0\frac{\partial L}{\partial \mathbf{w}} = 0 -
相補スラック条件：
\alpha_i \left( y_i \left( w_0 + \mathbf{w}^\top \mathbf{x}_i \right) - 1 \right) = 0, \quad \forall i
ここで、ラグランジュ関数 $ L(w_0, \mathbf{w}, \boldsymbol{\alpha}) $ は以下のように定義されます。
L(w_0, \mathbf{w}, \boldsymbol{\alpha}) = \frac{1}{2} \| \mathbf{w} \|^2 - \sum_{i=1}^N \alpha_i \{ y_i \left( w_0 + \mathbf{w}^\top \mathbf{x}_i \right) - 1 \}
ラグランジュ乗数 $ \alpha_i \geq 0 $ は、制約条件に対応する双対変数です。
ラグランジュ緩和と双対問題の導出
1. 強双対性と凸性条件
強双対性とは、主問題の最適値と双対問題の最適値が一致する性質を指します。強双対性が成り立つと、双対問題を解くことで主問題の解を得ることができます。
強双対性が成り立つための条件として、主問題が凸最適化問題であり、さらに制約がSlaterの条件（厳密可行性条件）を満たす必要があります。本問題では、以下の理由から強双対性が成立します。
- 目的関数の凸性：目的関数 $ \frac{1}{2} || \mathbf{w} ||^2 $ は $ \mathbf{w} $ に関して二次形式であり、凸関数です。
- 制約条件の線形性：制約 $ y_i \left( w_0 + \mathbf{w}^\top \mathbf{x}_i \right) - 1 \geq 0 $ は $ \mathbf{w}, w_0 $ に関して線形であり、凸集合を定義します。
- Slaterの条件の成立：厳密可行解（制約を厳密に満たす解）が存在するため、Slaterの条件が満たされます。
これらの条件により、強双対性が成立し、主問題と双対問題の最適値が一致します。
なぜラグランジュ緩和問題と双対問題を考えるのか
強双対性が成立するため、主問題を直接解く代わりに、双対問題を解くことで効率的に最適解を求めることができます。特に、双対問題は主問題よりも計算が容易であり、高次元データに対しても適用可能です。また、双対問題ではカーネル関数を用いた非線形拡張が容易になるという利点もあります。
2. ラグランジュ緩和問題の定義
ラグランジュ緩和問題とは、主問題の制約条件をラグランジュ乗数を用いて目的関数に組み込み、制約を「緩和」する手法です。これにより、制約付き最適化問題を無制約の最適化問題に変換できます。
ラグランジュ緩和問題の目的関数は以下のようになります。
\min_{w_0, \mathbf{w}} \max_{\boldsymbol{\alpha} \geq 0} L(w_0, \mathbf{w}, \boldsymbol{\alpha})
ここで、制約条件はラグランジュ関数の中に組み込まれており、KKT条件の一部（特に相補スラックネス条件）が緩められています。
3. 双対問題の設定
ラグランジュ関数を $ w_0, \mathbf{w} $ について最小化し、ラグランジュ乗数 $ \boldsymbol{\alpha} $ について最大化することで、双対問題を導出します。
-
双対関数：
g(\boldsymbol{\alpha}) = \inf_{w_0, \mathbf{w}} L(w_0, \mathbf{w}, \boldsymbol{\alpha}) -
双対問題：
\max_{\boldsymbol{\alpha} \geq 0} g(\boldsymbol{\alpha})
停留条件の適用
ラグランジュ関数を $ w_0, \mathbf{w} $ について最小化するために、停留条件を適用します。
- $ w_0 $ に関する微分：
\frac{\partial L}{\partial w_0} = 0 \implies \sum_{i=1}^N \alpha_i y_i = 0
-
$ \mathbf{w} $ に関する微分：
\frac{\partial L}{\partial \mathbf{w}} = 0 \implies \mathbf{w} = \sum_{i=1}^N \alpha_i y_i \mathbf{x}_i
双対関数の計算
停留条件から得られた $ w_0, \mathbf{w} $ をラグランジュ関数に代入し、双対関数 $ g(\boldsymbol{\alpha}) $ を計算します。
\begin{align*}
g(\boldsymbol{\alpha}) &= L(w_0, \mathbf{w}, \boldsymbol{\alpha}) \\
&= \frac{1}{2} \| \mathbf{w} \|^2 - \sum_{i=1}^N \alpha_i \left( y_i (w_0 + \mathbf{w}^\top \mathbf{x}_i) - 1 \right) \\
&= \frac{1}{2} \| \mathbf{w} \|^2 - w_0 \sum_{i=1}^N \alpha_i y_i - \mathbf{w}^\top \sum_{i=1}^N \alpha_i y_i \mathbf{x}_i + \sum_{i=1}^N \alpha_i \\
&= \frac{1}{2} \| \mathbf{w} \|^2 - 0 - \mathbf{w}^\top \mathbf{w} + \sum_{i=1}^N \alpha_i \quad (\text{ステーショナリティ条件より}) \\
&= -\frac{1}{2} \| \mathbf{w} \|^2 + \sum_{i=1}^N \alpha_i \\
&= -\frac{1}{2} \left( \sum_{i=1}^N \alpha_i y_i \mathbf{x}_i \right)^\top \left( \sum_{j=1}^N \alpha_j y_j \mathbf{x}_j \right) + \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^\top \mathbf{x}_j + \sum_{i=1}^N \alpha_i
\end{align*}
双対問題の定式化
-
目的関数（最大化）：
\max_{\boldsymbol{\alpha}} \quad W(\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^\top \mathbf{x}_j -
制約条件：
\sum_{i=1}^N \alpha_i y_i = 0, \quad \alpha_i \geq 0, \quad \forall i
KKT条件の双対問題における一部暗黙的満足について
主問題の実行可能領域と双対問題
主問題の実行可能領域は、制約条件 $ y_i (w_0 + \mathbf{w}^\top \mathbf{x}_i) - 1 \geq 0 $ によって定義されています。しかし、双対問題ではこれらの制約が明示的に現れません。これは、ラグランジュ緩和によって制約がラグランジュ関数に組み込まれているためです。
相補スラック条件の暗黙的満足
相補スラック条件も双対問題の制約には明示的に現れませんが、双対問題を解く過程で暗黙的に満たされます。理由は以下の通りです。
-
ラグランジュ乗数の役割：ラグランジュ乗数 $ \alpha_i $ は、主問題の制約違反に対するペナルティとして機能します。双対問題ではこれらのラグランジュ乗数を最大化することで、主問題の制約条件を間接的に考慮しています。
-
主問題の実行可能性の反映：双対問題の解を通じて、主問題の実行可能領域が暗黙的に考慮されます。ラグランジュ乗数が正の値をとるのは、対応する制約が等号成立（境界上）または非活性（ソフトマージンにおける内部）である場合です。
-
強双対性の成立：本問題では強双対性が成立するため、主問題と双対問題の最適値が一致します。この結果、双対問題の最適解は、主問題の相補スラックネス条件を満たすように自動的に調整されます。
-
相補スラック条件の重要性：相補スラックネス条件は、主問題の制約とラグランジュ乗数の間の関係を示すものであり、主問題の実行可能領域内で最適解が得られることを保証します。
以上のように、双対問題の最適化過程でラグランジュ乗数を適切に選ぶことにより、主問題の実行可能領域と相補スラックネス条件が暗黙的に満たされます。これにより、双対問題を解くだけで主問題の最適解を得ることができます。
分離超平面の導出
1. 最適解の計算
双対問題を解いて得られた最適なラグランジュ乗数 $\alpha_i^\ast$ を用いて、$w_0$ と $\mathbf{w}$ を計算します。
-
$ \mathbf{w} $ の計算：
\mathbf{w}^\ast = \sum_{i=1}^N \alpha_i^\ast y_i \mathbf{x}_i -
$ w_0 $ の計算：
相補スラック条件より、$ \alpha_i^\ast > 0 $ のデータ点（サポートベクトル）に対して、
y_i \left( w_0 + \mathbf{w}^\top \mathbf{x}_i \right) = 1これを用いて $ w_0 $ を求めます。
w_0^\ast = -\frac{1}{2}{\mathbf{w}^\ast}^\top (\mathbf{x}_+ + \mathbf{x}_-)
2. 分離超平面の式
最終的な分離超平面（決定境界）は次の式で表されます。
w_0^\ast + {\mathbf{w}^\ast}^\top \mathbf{x} = 0