サポートベクターマシン(SVM)の最適化

2024年2月8日 2024年2月12日

この記事ではサポートベクターマシン(SVM)の最適化問題について特化して詳しく解説していく。

この記事で分かること一覧

SVMは凸二次最適化問題である。
強双対性の理論と証明
SVMにおいてはKKT条件が必要十分条件であることの証明
SMOアルゴリズム

SVMのマージン最大化などの基本的な理論についてはこちらの記事を参考にしてほしい。むしろ順番としてはこちらの記事を読んでからこの記事を読んだほうが理解が深まると思う。

: サポートベクターマシン（SVM）徹底解説！マージン最大化とカーネル法、双対問題とは
この記事ではできうる限り厳密にサポートベクターマシンの理論について解説を行っていく。この記事を読めばSVMのおおよそすべてが分かる。注意としては実装の仕方やコードなどの解説は一切行わ ...
続きを見る

SVMの基本原理

SVMの基本的な目的は、データを分類する最適な超平面を見つけることである。この超平面は、異なるクラスに属するデータポイントを最も効果的に分離する。SVMでは、次の二つの主要な概念が用いられる。

マージン最大化: SVMは、クラス間のマージン（すなわち、超平面と最も近いデータポイント間の距離）を最大化する超平面を見つけることを目指す。マージンが大きいほど、未知のデータに対する分類性能が向上すると考えられる。
カーネル法: 非線形なデータを効果的に扱うために、カーネルトリックが導入された。カーネル法により、元の特徴空間を高次元空間に写像することで、非線形な関係を線形分離可能にする。これにより、複雑なデータパターンに対しても、SVMを用いることが可能になる。

このように、SVMはその単純さと効果性から、多くの分野で広く採用されている。

凸最適化の基本定義

凸最適化問題とは、凸関数を最小化（または凸関数の逆数を最大化）する問題である。ここで、「凸関数」とは、その定義域上の任意の二点を選んだ場合、それらを結ぶ線分が関数のグラフの上方または上に位置する関数のことを指す。数学的には、関数$f(x)$が凸であるための条件は次のように表される。

$$
f(\theta x+(1-\theta) y) \leq \theta f(x)+(1-\theta) f(y)
$$

ここで、$x,y$は関数の定義域内の任意の点であり、$\theta$は０と１の間の任意の数である。

凸最適化の特徴

凸最適化問題の主な特徴は以下の通りである：

大域的最適解の存在: 凸最適化問題では、局所的な最適解が必ず大域的な最適解となる。これは、非凸問題では一般に成り立たない重要な特性である。
計算の効率性: 凸問題は、効率的なアルゴリズムによって解くことができる。これにより、大規模な問題に対しても実用的な解が得られる。
解の安定性: 凸問題の解は、パラメータの小さな変化に対して安定であることが多い。この性質は、モデルのロバスト性を確保する上で重要である。

サポートベクトルマシンにおける最適化問題は、この凸最適化の枠組みの中で凸二次最適化問題として定式化される。

SVMの最適化問題の定式化

SVMの最適化主問題

パラメータ$\boldsymbol{w}$（重みベクトル）、$b$（バイアス項）、$\boldsymbol{\xi}$（スラック変数）が用いて、SVMの最適化問題は以下のように定義される。

$$
\begin{aligned}
\min _{\boldsymbol{w}, b, \boldsymbol{\xi}} & \frac{1}{2}\|\boldsymbol{w}\|^2+C \sum_{i \in[n]} \xi_i \\
\text { s.t. } & -\left(y_i\left(\boldsymbol{w}^{\top} \boldsymbol{\phi}\left(\boldsymbol{x}_i\right)+b\right)-1+\xi_i\right) \leq 0, \quad i \in[n] \\
& -\xi_i \leq 0, \quad i \in[n] \end{aligned}
$$

ここで、$\|\boldsymbol{w}\|^2$はマージンの逆数と解釈されるため、これを最小化することでマージンを最大化する。$C$は正則化パラメータであり、誤分類のペナルティの大きさを調節する。$\boldsymbol{\xi}$はスラック変数で、各データポイントがどの程度誤分類を表す。$y_i$は各データポイント$\boldsymbol{x}_i$のクラスラベルで、$\phi$は各データを高次元空間に写像する関数（カーネル関数）である。

この定式化により、SVMはマージンと誤分類のトレードオフを効果的にバランスさせることができる。

強双対性の理論と証明

強双対性の基本概念とその重要性

表式を簡単にするために、目的関数と制約条件の式を以下のように定義する

$$
\begin{aligned} \mathcal{P}(\boldsymbol{\theta}) & =\frac{1}{2}\|\boldsymbol{w}\|^2+C \sum_{i \in[n]} \xi_i \\ c_i(\boldsymbol{\theta}) & =\left\{\begin{array}{l} -\left(y_i\left(\boldsymbol{w}^{\top} \boldsymbol{x}_i+b\right)-1+\xi_i\right), i \in[n] \\ -\xi_{i-n}, i=n+1, \ldots, m \end{array}\right. \end{aligned}
$$
ただし、$m=2n$,$\boldsymbol{\theta}=(\boldsymbol{w}^\top,b,\boldsymbol{\xi}^\top)$とする。

このとき主問題は以下のように簡潔に定義できる。

SVMの主問題（簡易版）

$$
\begin{aligned} & \min _{\boldsymbol{\theta}} \mathcal{P}(\boldsymbol{\theta}) \\ & \text { s.t. } c_i(\boldsymbol{\theta}) \leq 0, i \in[m] \end{aligned}
$$

双対変数をまとめて$\boldsymbol{\lambda}=\left(\boldsymbol{\alpha}^{\top}, \boldsymbol{\mu}^{\top}\right)^{\top}$とすると、ラグランジュ関数は以下のように記述できる

$$
L(\boldsymbol{\theta}, \boldsymbol{\lambda})=\mathcal{P}(\boldsymbol{\theta})+\boldsymbol{\lambda}^{\top} c(\boldsymbol{\theta})
$$

ただし、$c(\boldsymbol{\theta})$ は $c_i(\boldsymbol{\theta})$を並べたベクトルとする。また、双対問題の目的関数値$\mathcal{D}(\boldsymbol{\lambda})$と表記する

ラグランジュの関数を含むラグランジュの未定乗数法の解説はこちらの記事で詳しく行っている。

: ラグランジュの未定乗数法（KKT条件）の証明と直感的理解、そしてその幾何的解釈
この記事ではラグランジュの未定乗数法について徹底的に解説していく。なぜラグランジュの未定乗数法はあれで導出することができるのか、厳密な証明、直感的な理解、幾何的な解釈をすべて取り扱う渾 ...
続きを見る

$$
\mathcal{D}(\boldsymbol{\lambda})=\min _{\boldsymbol{\theta}} L(\boldsymbol{\theta}, \boldsymbol{\lambda})
$$

そして強双対性は次のように書ける

強双対性

SV分類の最適な主変数を$\boldsymbol{\theta}^*$とし、双対変数を$\boldsymbol{\lambda}^*$とすると

$$ \mathcal{P}\left(\boldsymbol{\theta}^*\right)=\mathcal{D}\left(\boldsymbol{\lambda}^*\right) $$

強双対性の概念は、主問題と双対問題の関係を表す。一般に、最適化問題には、元の問題（主問題）とそれに関連する双対問題が存在する。強双対性が成立する場合、主問題の最適な解の目的関数値と双対問題の最適な解の目的関数値が等しくなる。これは、主問題の最適解が双対問題の最適解を通じて得られることが保証される。

証明

任意の$\boldsymbol{\theta}$に対して、以下の集合$\mathcal{U}$と$\mathcal{L } $を定義する。

$$
\begin{aligned}
\mathcal{U} & =\left\{\left(z_0, \boldsymbol{z}\right) \in \mathbb{R}^{1+m} \mid z_0 \geq \mathcal{P}(\boldsymbol{\theta}), \boldsymbol{z} \geq \boldsymbol{c}(\boldsymbol{\theta})\right\} \\
\mathcal{L} & =\left\{\left(z_0, \boldsymbol{z}\right) \in \mathbb{R}^{1+m} \mid z_0<\mathcal{P}\left(\boldsymbol{\theta}^*\right), \boldsymbol{z}=\mathbf{0}\right\}
\end{aligned}
$$

目的関数と制約条件の凸性により$\mathcal{U}$と$\mathcal{L } $はともに凸集合であり、かつ、共通部分を持たないため、分離定理より互いを分離する徴兵面が存在する。

これは、任意の2点$\left(z_0, \boldsymbol{z}\right) \in \mathcal{U},\left(z_0^{\prime}, \boldsymbol{z}^{\prime}\right) \in \mathcal{L}$に対し、以下を満たす$\left(\tilde{\lambda}_0, \tilde{\lambda}\right) \neq 0$が存在することを意味する

$$
\tilde{\lambda}_0 z_0+\tilde{\boldsymbol{\lambda}}^{\top} \boldsymbol{z} \geq \tilde{\lambda}_0 z_0^{\prime}+\tilde{\boldsymbol{\lambda}}^{\top} \boldsymbol{z}^{\prime}
$$

このとき、もし$\left(\tilde{\lambda}_0, \tilde{\boldsymbol{\lambda}}\right)$が0より小さい要素を含んでいると、$\mathcal{U}$内の点の選び方によって左辺がどこまでも小さくなれてしまうため$\left(\tilde{\lambda}_0, \tilde{\boldsymbol{\lambda}}\right) \geq 0$であることが分かる。さらに、$\lambda_0>0$を仮定すると、$\boldsymbol{z}^{\prime}=0$から以下の関係を得る

$$
z_0+\frac{1}{\tilde{\lambda}_0} \tilde{\boldsymbol{\lambda}}^{\top} \boldsymbol{z} \geq z_0^{\prime}
$$

任意の$\varepsilon > 0$を選んで、上の不等式に$z_0=\mathcal{P}(\boldsymbol{\theta}), \boldsymbol{z}=c(\boldsymbol{\theta}), z_0^{\prime}=\mathcal{P}\left(\boldsymbol{\theta}^*\right)-\varepsilon$を代入すると

$$
\mathcal{P}(\boldsymbol{\theta})+\frac{1}{\tilde{\lambda}_0} \tilde{\boldsymbol{\lambda}}^{\top} c(\boldsymbol{\theta}) \geq \mathcal{P}\left(\boldsymbol{\theta}^*\right)-\varepsilon
$$

となる。さらに、$\varepsilon>0$は任意であったため

$$
\mathcal{P}(\boldsymbol{\theta})+\frac{1}{\widetilde{\lambda}_0} \tilde{\boldsymbol{\lambda}}^{\top} \boldsymbol{c}(\boldsymbol{\theta}) \geq \mathcal{P}\left(\boldsymbol{\theta}^*\right)
$$

が成立する。また、非負ベクトル$\frac{1}{\tilde{\lambda}_0} \tilde{\boldsymbol{\lambda}}$を双対変数$\boldsymbol{\lambda}$だとみなすと、以下のように表現できる。

$$
L\left(\boldsymbol{\theta}, \frac{1}{\tilde{\lambda}_0} \tilde{\boldsymbol{\lambda}}\right) \geq \mathcal{P}\left(\boldsymbol{\theta}^*\right)
$$

この不等式は任意の$\boldsymbol{\theta}$に対するものであり、関数$L$を$\boldsymbol{\theta}$に関して最小化したものが$\mathcal{D}$であることを考慮すると以下を得る。

$$
\mathcal{D}\left(\frac{1}{\tilde{\lambda}_0} \tilde{\boldsymbol{\lambda}}\right)=\min _{\boldsymbol{\theta}} L\left(\boldsymbol{\theta}, \frac{1}{\tilde{\lambda}_0} \tilde{\boldsymbol{\lambda}}\right) \geq \mathcal{P}\left(\boldsymbol{\theta}^*\right)
$$

この不等式を弱双対定理$\mathcal{P}\left(\boldsymbol{\theta}^*\right) \geq \mathcal{D}\left(\boldsymbol{\lambda}^*\right)$を併せると、$\mathcal{D}\left(\boldsymbol{\lambda}^*\right)=\mathcal{P}\left(\boldsymbol{\theta}^*\right)$でなければならないことが分かる。また、$\lambda_0=0$の場合を考えると、以下の不等式が成立してなければならない。

$$
\boldsymbol{\lambda}^{\top} \boldsymbol{c}(\boldsymbol{\theta}) \geq 0
$$

任意の$\boldsymbol{\theta}$でこれが成立するには$\boldsymbol{\lambda} \geq \mathbf{0}$であり、かつ$c_i$が1次関数であることを考慮すると、$\boldsymbol{\lambda} = 0$でなければならない。しかし、このとき$\left(\lambda_0, \boldsymbol{\lambda}\right) \neq \mathbf{0}$と矛盾してしまうため、$\lambda_0>0$と言える。

□

KKT条件の導入とSVMでの応用

カルーシュ・クーン・タッカー（KKT）条件は、制約付き最適化問題、特にサポートベクトルマシン（SVM）における最適化問題の解析において重要な役割を果たす。SVMにおいて、KKT条件は最適な解が満たすべき必要十分条件を提供する。この性質が重要なのは解の最適性を判定するのに都合がいいからである。

KKT条件

以下の条件がSVMの主変数、双対変数の最適性の必要十分条件である。

$$
\begin{align*}
\frac{\partial L}{\partial w}=\boldsymbol{w}-\sum_{i \in[n]} \alpha_i y_i \phi\left(\boldsymbol{x}_i\right) & =\mathbf{0} \tag{1}\\
\frac{\partial L}{\partial b}=-\sum_{i \in[n]} \alpha_i y_i & =0 \tag{2}\\
\frac{\partial L}{\partial \xi_i}=C-\alpha_i-\mu_i & =0, i \in[n] \tag{3}\\
-\left(y_i\left(\boldsymbol{w}^{\top} \phi\left(\boldsymbol{x}_i\right)+b\right)-1+\xi_i\right) & \leq 0, i \in[n] \tag{4}\\
-\xi_i & \leq 0, i \in[n] \tag{5}\\
\alpha_i & \geq 0, i \in[n] \tag{6}\\
\mu_i & \geq 0, i \in[n] \tag{7}\\
\alpha_i\left(y_i\left(\boldsymbol{w}^{\top} \phi\left(x_i\right)+b\right)-1+\xi_i\right) & =0, i \in[n] \tag{8}\\
\mu_i \xi_i & =0, i \in[n] \tag{9}
\end{align*}
$$

(1)~(3)はラグランジュ関数の主変数に関する微分であり、次の(4),(5)は主問題の制約条件,(6),(7)は双対変数の非負条件であり、最後の二つ(8),(9)は双対変数と不等制約の乗算によって定義される相補性条件と呼ばれる条件である。

証明

まず必要条件について考える。式(2)~(7)は主問題と双対問題の制約条件によって最適化においては必ず満たされている。最適解は当然制約条件を満たしているので、$\boldsymbol{c}(\boldsymbol{\theta}) \leq 0$であり、以下の関係が成立する。

$$
\mathcal{P}\left(\boldsymbol{\theta}^*\right) \geq \mathcal{P}\left(\boldsymbol{\theta}^*\right)+\boldsymbol{\lambda}^{* \top} c\left(\boldsymbol{\theta}^*\right)=L\left(\boldsymbol{\theta}^*, \boldsymbol{\lambda}^*\right) \geq \min _{\boldsymbol{\theta}} L\left(\boldsymbol{\theta}, \boldsymbol{\lambda}^*\right)=\mathcal{D}\left(\boldsymbol{\lambda}^*\right)
$$

強双対性より、左辺と右辺は等しいので、結果として以下が導かれる。

$$
\lambda^{* \top} c\left(\theta^*\right)=0
$$

$\boldsymbol{\lambda}^* \geq 0, \boldsymbol{c}\left(\boldsymbol{\theta}^*\right) \leq 0$であるため、相補性条件(8),(9)を得る。また、$L\left(\boldsymbol{\theta}^*, \boldsymbol{\lambda}^*\right)=\mathcal{D}\left(\boldsymbol{\lambda}^*\right)=\min _{\boldsymbol{\theta}} L\left(\boldsymbol{\theta}, \boldsymbol{\lambda}^*\right)$となるため、$\boldsymbol{w}$に関する最小化を考えると、式(1)も成立していることがわあkる。

次に十分性について考える。

ある$\boldsymbol{\theta}$と$\boldsymbol{\lambda}$が条件を満たしていると仮定する。

このとき、(2)~(7)によって、$\boldsymbol{\theta}$と$\boldsymbol{\lambda}$は双対問題の制約条件を満たしていることは明らかである。さらに、以下の関係を導くことができる

$$
\begin{aligned}
& \mathcal{P}\left(\boldsymbol{\theta}^*\right) \leq \mathcal{P}(\boldsymbol{\theta})=\mathcal{P}(\boldsymbol{\theta})+\boldsymbol{\lambda}^{\top} c(\boldsymbol{\theta})=L(\boldsymbol{\theta}, \boldsymbol{\lambda})=\mathcal{D}(\boldsymbol{\lambda}) \leq \mathcal{D}\left(\boldsymbol{\lambda}^*\right) \\
&
\end{aligned}
$$

ここで、相補性条件(8),(9)より、$\boldsymbol{\lambda}^{\top} c(\boldsymbol{\theta})=0$であること、式(1)~(3)より$L(\boldsymbol{\theta}, \boldsymbol{\lambda})=\mathcal{D}(\boldsymbol{\lambda})$が成立することを利用している。弱双対性より$\mathcal{P}\left(\boldsymbol{\theta}^*\right) \geq \mathcal{D}\left(\boldsymbol{\lambda}^*\right)$であるため、関係式が成立するのは以下の場合のみ

$$
\mathcal{P}\left(\boldsymbol{\theta}^*\right)=\mathcal{P}(\boldsymbol{\theta})=\mathcal{D}(\boldsymbol{\lambda})=\mathcal{D}\left(\boldsymbol{\lambda}^*\right)
$$

よって十分性が証明できた。

これらの条件を使用して、SVMの最適化問題を解くことにより、効率的かつ正確な分類器を構築することができる。次のセクションでは、SMOアルゴリズムの詳細な解説に進む。

SMOアルゴリズム

SMO（Sequential Minimal Optimization）アルゴリズムは、サポートベクトルマシン（SVM）の訓練を効率的に行うために開発された方法である。このアルゴリズムは、SVMの最適化問題をより小さなサブプロブレムに分割して解くことにより、全体の計算効率を向上させる。

SMOアルゴリズムの概要

SMOアルゴリズムは、1998年にJohn Plattによって提案された。このアルゴリズムの主な特徴は以下の通りである：

サブプロブレムへの分割：SVMの最適化問題は、多くの変数に関する複雑な問題である。SMOはこの問題を、一度に2つの変数だけを最適化するような小さな問題に分割する。これにより、問題をより単純化し、高速に解くことが可能になる。
解析的な方法：SMOでは、サブプロブレムを解析的に解くことができる。これにより、勾配降下法のような数値的最適化手法に比べて、計算効率が大幅に向上する。
ヒューリスティックな選択：どの変数のペアを最適化するかは、特定のヒューリスティックに基づいて選択される。例えば、現在の解がKKT条件を最も満たさない変数のペアを選択するなどの方法がある。
収束の保証：SMOアルゴリズムは、適切な条件下での収束を保証する。つまり、一定の反復回数後には、最適な解に近い値が得られる。

SMOアルゴリズムの導入により、特に大規模なデータセットに対してSVMを効率的に訓練することが可能になった。このアルゴリズムは、SVMの実装において広く採用されている。次のセクションでは、SMOアルゴリズムの数学的基礎について詳しく見ていく。

2変数の最適化

双対変数の変数変換

問題を扱いやすくするため、双対変数$\left\{\alpha_i\right\}_{i \in[n]}$を変数変換を行う。

$$
\beta_i=y_i \alpha_i, i \in[n] $$

ラベルは$y_i \in\{ \pm 1\}$なので、$\alpha_i$と$\beta_i$は次の関係にある。

$$
y_i \beta_i=y_i^2 \alpha_i=\alpha_i, i \in[n] $$

この変数変換を用いるとSV分類の双対問題は次のように表される。

$$
\begin{aligned}
\min _{\left\{\beta_i\right\}_{i \in[n]}} & \frac{1}{2} \sum_{i, j \in[n]} \beta_i \beta_j K_{i j}-\sum_{i \in[n]} y_i \beta_i \\
\text { s.t. } & \sum_{i \in[n]} \beta_i=0 \\
& 0 \leq \beta_i \leq C, \forall i \in\left\{[n] \mid y_i=+1\right\} \\
- & C \leq \beta_i \leq 0, \forall i \in\left\{[n] \mid y_i=-1\right\}
\end{aligned}
$$

ここで、カーネル関数$K_{i j}=K\left(\boldsymbol{x}_i, \boldsymbol{x}_j\right)$を表す。

SMOアルゴリズムにおける二変数の最適化

SMOアルゴリズムでは、$n$個の未知変数$\left\{\alpha_i\right\}_{i \in[n]}$のうち、異なる二つの変数$\beta_s, \beta_t, s \neq t$を選び、その変数についての最適化を行う。

等式制約のため、変数を一つでなく二つ選ぶ必要があり、等式制約を満たすためには$\beta_s + \beta_t$の値が一定である必要がある。

二つの変数を以下のように更新する場合を考える。

$$
\beta_s \leftarrow \beta_s+\Delta \beta_s, \quad \beta_t \leftarrow \beta_t+\Delta \beta_t
$$

このとき等式制約を満たすためには

$$
\beta_s+\beta_t=\left(\beta_s+\Delta \beta_s\right)+\left(\beta_t+\Delta \beta_t\right)
$$

が必要であり

$$
\Delta \beta_t=-\Delta \beta_s
$$

を満たす必要がある。すなわち、二つの変数$\beta_s$ と $\beta_t$のみを変数として最適化問題を解く場合、実質的に自由に動ける変数は$\Delta \beta_s$の一変数となる。

$\Delta \beta_s$の範囲の決定

続いて、$\Delta \beta_s$の満たすべき範囲を考える。更新後の$\beta_s$ と $\beta_t$が$ 0 \leq \beta_i \leq C, \forall i \in\left\{[n] \mid y_i=+1\right\}$と$- C \leq \beta_i \leq 0, \forall i \in\left\{[n] \mid y_i=-1\right\}$を満たすには

$0 \leq \beta_s+\Delta \beta_s \leq C \quad y_s=+1$ の場合
$-C \leq \beta_s+\Delta \beta_s \leq 0 \quad y_s=-1$ の場合

となるように、$\Delta \beta_s$に制約を加えなければならない。これを$y_s$と$y_t$の符号のそれぞれの組み合わせに対して考慮すると、$\Delta \beta_s$は

$$
\begin{gathered}
\max \left(-\beta_s, \beta_t-C\right) \leq \Delta \beta_s \leq \min \left(C-\beta_s, \beta_t\right) \\
y_s=+1, y_t=+1 \text { の場合 } \\
\max \left(-\beta_s, \beta_t\right) \leq \Delta \beta_s \leq \min \left(C-\beta_s, C+\beta_t\right) \\
y_s=+1, y_t=-1 \text { の場合 } \\
\max \left(-C-\beta_s, \beta_t-C\right) \leq \Delta \beta_s \leq \min \left(-\beta_s, \beta_t\right) \\
y_s=-1, y_t=+1 \text { の場合 } \\
\max \left(-C-\beta_s, \beta_t\right) \leq \Delta \beta_s \leq \min \left(-\beta_s, C+\beta_t\right) \\
y_s=-1, y_t=-1 \text { の場合 }
\end{gathered}
$$

を満たす必要がある。

双対問題の最適化

双対問題を$\Delta \beta_s$に関する制約付き最適化問題として書き直すと

$$
\begin{aligned}
\min _{\Delta \beta_s} & \frac{1}{2}\left(K_{s, s}+2 K_{s, t}+K_{t, t}\right) \Delta \beta_s^2 \\
& -\left(y_s-\sum_{i \in[n]} \beta_i K_{i, s}-y_t+\sum_{i \in[n]} \beta_i K_{i, t}\right) \Delta \beta_s
\end{aligned}
$$
s.t. $L \leq \Delta \beta_s \leq U$

と表せる。ただし、$L,U$は$y_s,y_t$の符号に応じた先の四つの不等式の下限と上限である。

これは一変数$\Delta \beta_s$の制約付き二次関数の最小化問題となるので、最適解は

$$
\Delta \beta_s= \begin{cases}L & L>\frac{y_s-y_t-\sum_{i \in[n]} \beta_i\left(K_{i, s}-K_{i, t}\right)}{K_{s, s}+2 K_s t+K_{t, t}} \text { の場合 } \\ U & U<\frac{y_s-y_t-\sum_{i \in[n]} \beta_i\left(K_{i, s}-K_{i, t}\right)}{K_{s, s}+2 K_{s, t}+K_{t, t}} \text { の場合 } \\ \frac{y_s-y_t-\sum_{i \in[n]} \beta_i\left(K_{i, s}-K_{i, t}\right)}{K_{s, s}+2 K_{s, t}+K_{t, t}} & \text { その他の場合 }\end{cases}
$$

と得られる。

２変数の選択

この二つの変数$\beta_s$と$\beta_t$はどのように選ばれるのだろうか。

これ、実はランダムに選んだとしてもSMOアルゴリズムは最終的には最適解に収束する。

しかし、なるべくうまく$\beta_s,\beta_t$を選んでやることで収束の早さを改善することができるのである。

この選び方には様々な手法が提案されているが、KKT条件をより満たさないものから順に選ぶという方法が一般的である。

そしてすべての$\alpha_i$がKKT条件を満たすことができればアルゴリズムを停止し、SVMの最適化つまり学習は完了である。

これで欲しかった分類境界を示す関数$f(\boldsymbol{x})$を決定することができた。

まとめ

SVMは理解するとさほど難しいことをやっているわけではないということが分かったと思う（その背景にある最適化の理論などは複雑だが）

シンプルイズベストという言葉もあるように、データセットによってはSVMがほかのモデルと比べて最良の結果をもたらす場合もある。

つまり、SVMはまだまだ現在でも有力な分類マシーンであり、理解する意義は多いにある。

さらにその内部で使われている一つ一つのパーツや理論はほかの最先端のAIでも使われることが多い。

この記事がその理解の助けになれば幸いである。

参考先

posted with カエレバ

パタ-ン認識と機械学習ベイズ理論による統計的予測下/シュプリンガ-・ジャパン/クリストファ-・Ｍ．ビショップ

posted with カエレバ

楽天市場

Amazon

Yahooショッピング

しっかり学ぶ数理最適化モデルからアルゴリズムまで/講談社/梅谷俊治

posted with カエレバ

コメントコメントをキャンセル

サポートベクターマシン（SVM）徹底解説！マージン最大化とカーネル法、双対問題とは

この記事ではできうる限り厳密にサポートベクターマシンの理論について解説を行っていく。この記事を読めばSVMのおおよそすべてが分かる。注意としては実装の仕方やコードなどの解説は一切行わない。理論的な部分に関しての解説をとことん行う。サポートベクターマシン(SVM)とはサポートベクターマシン(SVM)とは、サポートベクトルマシンとも呼ばれ、分類問題でよく用いられる有名な機械学習の手法の一つである。分類問題とは、入力されたデータを複数の特定のカテゴリーに分ける問題である。た ...

Multi-Head AttentionとScaled Dot-Product Attentionの全て：Transformerの核心を徹底解説

この記事では、Transformerの中心的な役割を果たすMulti-Head Attentionについて解説する。 Transformerのほかの機構の詳細な解説はせず、完全にMulti-Head Attention特化の解説となるので、ほかの機構や全体観を掴みたい方はこちらの記事をご一読いただきたい。この記事はまずはScaled Dot-Product AttentionというMulti-Head Attentionの中で使われている核心部分についてこれでもかと詳しく解説したのちに、本 ...

Transformerとは？世界を変えた深層学習モデルの仕組みをわかりやすく徹底解説

近年のAI技術の急激な発展には「Transformer」という深層学習モデルの存在が大きく関わっている。この記事では、そのTrasformerについてその仕組みとそれがなぜ組み込まれているかを画像をふんだんに使用して徹底的に解説している。必要な知識はなんと高校数学と行列の足し算、掛け算のみ！今後のAI社会において理解しておいて絶対に損はないので、ぜひ読んでほしい。 Transformerってなに？？ Transformerは、もともと機械翻訳の深層学習モデルとして2017年にGoogl ...

ソフトマックス（Softmax）関数とは：定義、特性、実装方法まで徹底解説

本記事は、Softmax関数に関する理解を深めたい方々を対象にしています。必要な前提知識は以下の通りです。基本的な数学知識（特に確率論と指数関数）ニューラルネットワークの基本概念 Pythonプログラミングの基礎機械学習における一般的な用語の理解この記事では、Softmax関数の定義からその性質、応用例、そして実際のコーディング方法に至るまでを段階的に解説しています。機械学習の分野における多クラス分類問題への理解を深めるための基礎的なガイドとして、本記事を活用いただければと思います。 &nbsp ...

コサイン類似度とは？ベクトルの内積から見る類似度

データ分析や機械学習の分野で広く用いられるコサイン類似度は、ベクトル間の類似性を測定する強力なツールである。この記事では、コサイン類似度の基本原理から、高次元データでの振る舞い、そして次元の呪いに対処する方法までを詳細に解説する。データサイエンティストや機械学習エンジニアにとって重要なこの問題を、わかりやすく、段階的に理解し、実践的な解決策を身につけるための一助となることを目指す。【定義】コサイン類似度とは何かコサイン類似度は、特に二つのベクトル間の角度を利用して、それらがどれだけ似 ...

２０２３年の振り返り記事　月ごとに何をしたのかと、何の記事を書いたのかを振り返って反省