数学的視点から見たサポートベクターマシン（SVM）：最適化問題の解法

サポートベクターマシン（SVM）は機械学習における古典的なアルゴリズムです。この記事では、SVMの公式導出に焦点を当て、マージン距離の詳細な推論や、元の問題と双対問題の公式化を説明します。制約付き最適化問題をラグランジュ関数を用いて解決し、KKT条件を利用して最適解を求める過程を深く探ります。また、多項式カーネル関数とガウスカーネル関数の公式特性についても触れます。

マージン距離の推論

サポートベクターマシン（SVM）において、正の超平面と負の超平面の式はそれぞれ以下の通りです： $$ \vec{w} \cdot \vec{x} + b = 1 \quad \text{(正の超平面)} $$ $$ \vec{w} \cdot \vec{x} + b = -1 \quad \text{(負の超平面)} $$ ここで$\vec{w}=(w_1, w_2)$は重みベクトル、$b$はバイアス項、$\vec{x}=(x_1, x_2)$はデータポイントです。

仮に$\vec{x_m}$が正の超平面上の点、$\vec{x_n}$が負の超平面上の点であるとすると、次のようになります： $$ w_1 x_{1m} + w_2 x_{2m} + b = 1 \quad \text{(1)} $$ $$ w_1 x_{1n} + w_2 x_{2n} + b = -1 \quad \text{(2)} $$

式(1)から式(2)を引くと、次のようになります： $$ w_1 (x_{1m} - x_{1n}) + w_2 (x_{2m} - x_{2n}) = 2 $$ ベクトル形式で書くと： $$ \vec{w} \cdot (\vec{x_m} - \vec{x_n}) = 2 \quad \text{(3)} $$ 決定超平面上の2点$\vec{x_0}$と$\vec{x_p}$を考え、それらは決定超平面の式$\vec{w} \cdot \vec{x} + b = 0$を満たします。すなわち： $$ w_1 x_{10} + w_2 x_{20} + b = 0 $$ $$ w_1 x_{1p} + w_2 x_{2p} + b = 0 $$ 2式を引くと： $$ w_1 (x_{10} - x_{1p}) + w_2 (x_{20} - x_{2p}) = 0 $$ ベクトル形式で書くと： $$ \vec{w} \cdot (\vec{x_0} - \vec{x_p}) = 0 \quad \text{(4)} $$ 式(4)は、$\vec{w}$が決定超平面上の任意の2点のベクトル差に垂直であることを示しています。

式(3)と(4)から、$\vec{w}$と$(\vec{x_m} - \vec{x_n})$の内積が2であることがわかります。ベクトルの内積の定義$\vec{a} \cdot \vec{b}=|\vec{a}| \cdot |\vec{b}| \cdot \cos \theta$に基づき、ここで$\theta$は$\vec{w}$と$(\vec{x_m} - \vec{x_n})$の間の角度です。次のようになります： $$ |\vec{x_m} - \vec{x_n}| \cdot \cos \theta \cdot |\vec{w}| = 2 $$ $L = |\vec{x_m} - \vec{x_n}| \cdot \cos \theta$とすると： $$ L \cdot |\vec{w}| = 2 $$ 解くと： $$ L=\frac{2}{|\vec{w}|} $$

ここで$L$はSVMのマージン（margin）距離です。

マージン距離を導出する際に、ベクトルの内積の幾何学的意味を利用しました。すなわち、$\vec{a} \cdot \vec{b}=|\vec{a}| \cdot |\vec{b}| \cdot \cos \theta$であり、ここで$\theta$は2つのベクトルの間の角度です。この関係を通じて、内積をベクトルの長さと角度の関係に変換し、マージン距離の表現を導き出しました。

双対性の証明

線形サポートベクターマシン(SVM)において、元の問題は目的関数を最小化する重みベクトル$w$とバイアス$b$を見つけることです：

$$ \min_w f(w) = \frac{1}{2} |w|^2 $$

ここでの$|w|^2$はベクトル$w$のユークリッドノルムの平方、すなわち$L_2$ノルムを表します。目的は決定境界の幅を最小化し、より良い一般化能力を得ることです。この問題は以下の制約を受けます：

$$ y_j (w^T x_j + b) - 1 \geq 0 $$

ここで$x_j$は第$j$番目の訓練サンプル、$y_j$は対応するラベルで、+1または-1の値を取ります。これにより、すべてのデータポイントが正しく分類され、決定境界から少なくとも1単位の距離を持つことが保証されます。

この制約付き最適化問題を処理するために、ラグランジュ関数を構築します：

$$ L(w, b, \alpha) = f(w) - \sum_{j = 1}^n \alpha_j g_j(w, b) $$

ここで$\alpha_j \geq 0$はラグランジュ乗数で、元の問題の制約条件$g_j(w, b) = y_j (w^T x_j + b) - 1 \geq 0$を導入するために用いられます。

次に、双対関数$q(\alpha)$を定義します：

$$ q(\alpha) = \min_{w, b} L(w, b, \alpha) = \min_{w, b} \left( f(w) - \sum_{j = 1}^n \alpha_j g_j(w, b) \right) $$

$\alpha_j \geq 0$ および$g_j(w^{*}, b^{*}) \geq 0$であるため、次のように導出できます：

$$ q(\alpha) = \min_{w, b} \left( f(w) - \sum_{j = 1}^n \alpha_j g_j(w, b) \right) \leq f(w^*) - \sum_{j = 1}^n \alpha_j g_j(w^*, b^*) \leq f(w^*) \leq f(w) $$

これは、双対関数が元の問題の下限を与えることを意味します。次に、$\alpha^*$を見つける必要があります。これにより：

$$ q(\alpha) \leq q(\alpha^*) \leq f(w^*) \leq f(w) $$

SVMの元の問題と双対問題は次のように表現できます：

$$ \max_{\alpha} q(\alpha) = \max_{\alpha} \min_{w, b} L(w, b, \alpha) $$

その制約条件は：$ \alpha_i \geq 0 $

弱双対性が満たされるとき、$q(\alpha^*) \leq f(w^*)$が成り立ちます。強双対性が満たされる場合、すなわちSlater条件が成立する場合、$q(\alpha^*) = f(w^*)$が成り立ちます。Slater条件は、すべての不等式制約が厳密に成立する可行解が存在することを要求します。線形サポートベクターマシンは線形可分であり、Slater条件を自動的に満たします。

これにより、次のようになります：

$$ f(w) \geq q(\alpha^*) = f(w^*) \geq q(\alpha_i) $$

上記の式に基づいて、次のことがわかります：

$$ q(\alpha^*) \geq q(\alpha_i) $$ $$ f(w^*) \leq f(w) $$

$f(w)$は最小値を見つけ（元の問題）、$q(\alpha)$は最大値を見つけ（双対問題）、元の問題と双対問題の最適解は等しいです。すなわち：

$ w^*, b^* $は元の問題の解であり、$\alpha^*$は双対問題の解であり、$f(w^*) = q(\alpha^*)$です。

線形SVMにおいて、特定の条件（Slater条件）が満たされるとき、元の問題と双対問題の解が一致することがわかります。これは、複雑な最適化問題を解決するための有効な方法であり、特に元の問題を直接解くことが難しい場合に、双対問題を解くことで間接的に問題を解決することができます。

簡単な例

上記の元の問題と双対問題の解が同じであることをより直感的に理解するために、簡単な最適化問題を考えます。元の問題は次のように定義されます：

元の問題は： $$ \min_x f(x) = x^2 $$ 制約条件は： $$ x - 1 \geq 0 $$

この問題の目標は、関数$f(x) = x^2$を最小化し、同時に$x$が$x \geq 1$を満たす必要があります。直感的には、$x = 1$のとき、$f(x) = 1$であり、これは与えられた制約下での最小値です。

双対性を検証するために、ラグランジュ関数を構築します：

$$ q(\alpha) = \min_x L(x, \alpha) = \min_x (x^2 - \alpha(x - 1)) $$

ここで$\alpha \geq 0$はラグランジュ乗数で、元の問題の制約条件$x - 1 \geq 0$を導入するために用いられます。ラグランジュ関数を構築することで、制約付きの最適化問題を無制約の問題に変換しました。

次に、$L(x, \alpha)$について$x$の偏導数を求め、それを0に設定します：

$$ \frac{\partial L}{\partial x} = 0 2x - \alpha = 0 $$

解くと：

$$ x = \frac{\alpha}{2} $$

$x = \frac{\alpha}{2}$を$q(\alpha)$に代入します：

$$ q(\alpha) = - \frac{\alpha^2}{4} + \alpha $$

これで、双対関数$q(\alpha)$の形式を得ました。次に、双対問題の最大値$\max_{\alpha} q(\alpha) $を求める必要があります。

そのために、$q(\alpha)$について$\alpha$の導関数を求め、それを0に設定します：

$$ \frac{dq}{d\alpha} = - \frac{\alpha}{2} + 1 = 0 $$

解くと$$ \alpha = 2 $$

$\alpha = 2$を$x = \frac{\alpha}{2}$に代入すると、$$ x = 1 $$

このとき、$\alpha = 2$を$q(\alpha)$に代入して計算すると：

$$ q(\alpha) = - \frac{2^2}{4} + 2 = 1 $$

この簡単な例を通じて、元の問題の解$x = 1$、$f(x) = 1$と、双対問題の解$\alpha = 2$、$q(\alpha) = 1$が等価であることがわかります。これは、一定の条件が満たされる場合に、双対問題の解が元の問題の解と一致することを検証しています。

双対理論の応用を通じて、元の問題の解を見つけただけでなく、双対問題を解くことで同じ結果を得ることができ、双対問題の解の等価性を検証しました。

KKT条件による解法

SVMがKKT条件を満たす

SVMの元の最適化問題は凸最適化問題です。SVMの目的関数 $\frac{1}{2}|w|^2$ は$w$に関する二次関数であり、凸関数です。同時に、制約条件 $y_i(w \cdot x_i + b) \geq 1$ は線形（アフィン制約）であり、したがって凸です。凸最適化問題では、局所最適解が全体最適解であり、KKT条件は必要かつ十分な条件です。これは、ある点がKKT条件を満たす場合、それが全体最適解であることを意味します。

目的関数 $\frac{1}{2}|w|^2$ は連続で微分可能であり、制約条件 $y_i(w \cdot x_i + b) \geq 1$ も連続で微分可能です。この滑らかさは、勾配の存在と一意性を保証し、KKT条件における勾配条件（すなわち$w$と$b$に関する偏導数を求めて0に設定する）が有効に適用できるようにします。

凸最適化問題では、KKT条件は必要条件であるだけでなく、十分条件でもあります。つまり、ある点がKKT条件を満たす場合、それは全体最適解であることを意味します。SVMにおいて、KKT条件を解くことで最適な$w^*$と$b^*$を見つけ、最適な分離超平面を決定することができます。

KKT条件を利用した線形サポートベクターマシンの解法

元のSVM最適化問題は、$\frac{1}{2}|w|^{2}$を最小化し、同時に制約条件$y_{i}(w\cdot x_{i}+b)\geqslant1$を満たすことです。ここで$i = 1,2,\cdots,N$です。

まず、ラグランジュ関数を構築します。$L(w,b,\alpha)=\frac{1}{2}|w|^{2}-\sum_{i = 1}^{N}\alpha_{i}(y_{i}(w\cdot x_{i}+b)-1)$、ここで$\alpha_{i}\geqslant0$はラグランジュ乗数です。KKT条件に基づき、次のようになります：

$$ \nabla_{w}L(w^*,b^*,\alpha^*) = w^*-\sum_{i = 1}^{N}\alpha_{i}^*y_{i}x_{i}=0 $$

$$ \nabla_{b}L(w^*,b^*,\alpha^*)=-\sum_{i = 1}^{N}\alpha_{i}^*y_{i}=0 $$

$$ \alpha_{i}^*(y_{i}(w^*\cdot x_{i}+b^*)-1)=0 $$

$$ y_{i}(w^*\cdot x_{i}+b^*)-1\geqslant0 $$

$$ \alpha_{i}^*\geqslant0 $$

これらの条件はすべての$i = 1,2,\cdots,N$に適用されます。

$\nabla_{w}L(w^*,b^*,\alpha^*) = w^*-\sum_{i = 1}^{N}\alpha_{i}^*y_{i}x_{i}=0$から次のことが得られます：

$$ w^*=\sum_{i = 1}^{N}\alpha_{i}^*y_{i}x_{i} \quad \text{(5)} $$ 少なくとも1つの$\alpha_{j}^*>0$が存在します（もし$\alpha_{i}^*=0$と仮定すると、式$\nabla_{w}L(w^*,b^*,\alpha^*) = w^*-\sum_{i = 1}^{N}\alpha_{i}^*y_{i}x_{i}=0$から導かれる解に矛盾が生じます）。

$b^*$の解法については、$w^*=\sum_{i = 1}^{N}\alpha_{i}^*y_{i}x_{i}$を$y_{j}(w^*\cdot x_{j}+b^*)-1 = 0$に代入することで求めることができます（$\alpha_{j}^*>0$が存在する場合を考慮）。また、$y_{j}^{2}=1$に注意して次のように得られます：

$$ b^*=y_{j}-\sum_{i = 1}^{N}\alpha_{i}^*y_{i}(x_{i}\cdot x_{j}) \quad \text{(6)} $$

上記の理論に基づき、分離超平面は次のように表現できます：

$$ \sum_{i = 1}^{N}\alpha_{i}^*y_{i}(x\cdot x_{i})+b^*=0 $$

したがって、分類の決定関数は次のように書くことができます：

$$ f(x)=\text{sign}(\sum_{i = 1}^{N}\alpha_{i}^*y_{i}(x\cdot x_{i})+b^*) $$

SVMにおいて、相補的緩和条件$\alpha_i (y_i(w \cdot x_i + b) - 1) = 0$は、あるサンプル点$x_i$がサポートベクターでない場合（すなわち$y_i(w \cdot x_i + b) > 1$）、対応するラグランジュ乗数$\alpha_i$がゼロでなければならないことを示しています。逆に、あるサンプル点がサポートベクターである場合（すなわち$y_i(w \cdot x_i + b) = 1$）、対応する$\alpha_i$はゼロでない可能性があります。この条件は、サポートベクターのみが最適化問題の解に寄与することを保証し、問題の解法を簡素化します。

多項式カーネル関数とガウスカーネル関数

既存の問題が線形に分離できない場合、既存のデータを高次元空間にマッピングし、高次元空間で線形に分離可能な問題にすることができます。しかし、高次元特徴空間で直接計算することは非常に複雑です。式（5）と式（6）からわかるように、実際にデータを高次元空間にマッピングする必要はなく、データ点間の内積を知るだけで十分です。カーネル関数の役割は、高次元特徴マッピングを明示的に行わずに、元の特徴空間でカーネル関数の値を計算することで、高次元特徴空間での内積計算を間接的に実現することです。

ガウスカーネル関数は一般的なカーネル関数で、その形式は次の通りです： $$ K(x, y) = \exp\left(-\gamma |x - y|^2\right) $$

ここで$\gamma$は正のパラメータで、カーネル関数の幅を制御します。

指数関数をテイラー展開することができます：

$$ \exp(z) = \sum_{k=0}^{\infty} \frac{z^k}{k!} $$

$ z = -\gamma |x - y|^2 $を上記の式に代入すると、次のようになります：

$$ K(x, y) = \exp\left(-\gamma |x - y|^2\right) = \sum_{k=0}^{\infty} \frac{(-\gamma |x - y|^2)^k}{k!} $$

多項式カーネル関数の形式は次の通りです：

$$ K_{\text{poly}}(x, y) = (x \cdot y + c)^d $$

ここで$c$は定数項、$d$は多項式の次数です。

$|x - y|^2$は次のように展開できます：

$$ |x - y|^2 = (x - y) \cdot (x - y) = x \cdot x + y \cdot y - 2 x \cdot y $$

この表現をガウスカーネル関数のテイラー展開式に代入します：

$$ K(x, y) = \sum_{k=0}^{\infty} \frac{(-\gamma (x \cdot x + y \cdot y - 2 x \cdot y))^k}{k!} $$

各項$\frac{(-\gamma (x \cdot x + y \cdot y - 2 x \cdot y))^k}{k!}$は実際には多項式項であり、すなわち各項は$x$と$y$の異なるべき乗の組み合わせとして表現できます。

各項を注意深く観察すると、ガウスカーネル関数は実際には異なる次数の多項式カーネル関数を加重して得られたものであることがわかります。各項$\frac{(-\gamma (x \cdot x + y \cdot y - 2 x \cdot y))^k}{k!}$は、$k$次の多項式カーネル関数の加重形式と見なすことができます。

例えば、$k = 1$の場合：

$$ \frac{(-\gamma (x \cdot x + y \cdot y - 2 x \cdot y))^1}{1!} = -\gamma (x \cdot x + y \cdot y - 2 x \cdot y) $$

$k = 2$の場合：

$$ \frac{(-\gamma (x \cdot x + y \cdot y - 2 x \cdot y))^2}{2!} = \frac{\gamma^2 (x \cdot x + y \cdot y - 2 x \cdot y)^2}{2} $$

これらの項はすべて$x$と$y$の多項式形式であり、階乗$k!$によって加重されています。

ガウスカーネル関数は、無限次元で異なる次数の多項式カーネル関数を調和させて得られたものと見なすことができます。この調和により、ガウスカーネル関数は高次元特徴空間でより複雑な非線形関係を捉えることができます。したがって、多くの非線形タスクのシナリオで、ガウスカーネル関数は非常に優れた選択肢となります。