- 講師：津田宏治
- 資料：生物データマイニング論(2019)
In [1]:
import numpy as np
import matplotlib.pyplot as plt
二次計画問題を解くアルゴリズム概観¶
| アルゴリズム | 説明 |
|---|---|
| 伝統的な二次計画法のアルゴリズム | 計算コスト及びメモリ使用量の面で現実的には厳しい。 |
| チャンキング(chunking) | カーネル行列からラグランジュ乗数が $0$ となるデータに対応する行および列を取り除いても、ラグランジュ関数が不変であることを利用し、元々の二次計画問題は、より次元数の小さな問題を順番に解くことで、最終的には $0$ とならないラグランジュ乗数だけを残す、という問題に帰着する。 |
| 射影共役勾配法(projected conjugate gradient method) | チャンキングを実装する手法 |
| 分解法(decomposition method) | チャンキングと同様サイズの小さな二次計画問題を繰り返し解くという手法だが、ここの部分問題の大きさが一定であるため、任意の大きさのデータに対応できる。 |
| 逐次最小問題最適化法(SMO;sequential minimal optimization) | 分解法の計算コストを削減した手法。たった２つのラグランジュ乗数を含む部分問題を逐次解いていくことで最終的な解を得る。 |
逐次最小問題最適化法(SMO;sequential minimal optimization)¶
ラグランジュ双対問題を以下のように定義する。
$$ \begin{aligned} \tilde{L}(\mathbf{a}) &=\sum_n^Na_n - \frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^Na_na_mt_nt_mk(\mathbf{x}_n,\mathbf{x}_m)& (7.10)\\ a_n & \geq 0,\quad n=1,\ldots,N & (7.11)\\ \sum_{n=1}^Na_nt_n &= 0 & (7.12) \end{aligned} $$- 逐次最小問題最適化法(SMO;sequential minimal optimization)は反復法である。
- 適当な初期値 $\mathbf{a}^{(0)}$ から出発して、更新 $\mathbf{a}^{(k)} \rightarrow \mathbf{a}^{(k+1)}$ を繰り返す。
- この際、１度には2つの成分しか動かさない。
ここで、$a_p$ と $a_q$ だけ動かすことを考える。（他の $a_n$ は定数とみなす）
この時、制約条件より
$$ a_pt_p + a_qt_q = 0-\sum_{n\neq p,q} a_nt_n = \mathrm{const.}$$が成立する。したがって、
$$ \frac{\partial a_q}{\partial a_p} = -\frac{t_p}{t_q} =-t_pt_q \cdots (\ast)$$と解析的に偏微分を求めることが可能である。
目的関数 $\tilde{L}$ の変化量¶
以下、$K_{ij} = k\left(\mathrm{x}_i,\mathrm{x}_j\right)$ とおく。ここで、
$$a_p\mapsto a_p+\Delta_p, \quad a_q\mapsto a_q+\Delta_q$$と更新した時、目的関数 $\tilde{L}$ の変化量 $\Delta\tilde{L}$ は、
$$ \begin{aligned} \Delta\tilde{L} &= \Delta_p + \Delta_q - \Delta_pt_p\sum_{n=1}^Na_nt_nk(\mathbf{x}_p,\mathbf{x}_n) - \Delta_qt_q\sum_{n=1}^Na_nt_nk(\mathbf{x}_q,\mathbf{x}_n)\\ &-\frac{1}{2}\left[\Delta_p^2k(\mathbf{x}_p,\mathbf{x}_p) + 2\Delta_p\Delta_qt_pt_qk(\mathbf{x}_p,\mathbf{x}_q) + \Delta_q^2k(\mathbf{x}_q,\mathbf{x}_q)\right] \end{aligned} $$となる。
- $(\ast)$ より $\Delta_q = -t_pt_q\Delta_p$ である。
- $t_p=t_q(\Longleftrightarrow\Delta_q=-\Delta_p)$ の時と $t_p\neq t_q$ の時に場合分けをし、それぞれ $\Delta_p$ で変化量を偏微分して $0$ とおく。
- 結果は共に等しく、以下で表される。 $$ \begin{aligned} \Delta_p &= \frac{1-t_pt_q + t_p\left(\sum_{n=1}^Na_nt_nK_{qn} - \sum_{n=1}^Na_nt_nK_{pn}\right)}{K_{pp} - 2K_{pq} + K_{qq}}\\ &= \frac{1-t_pt_q + t_p\left(y(\mathbf{x_q}) - y(\mathbf{x}_q)\right)}{K_{pp} - 2K_{pq} + K_{qq}}\\ \end{aligned} $$
クリッピング¶
この時、
- $t_pa_p+t_qa_q=c$
- $a_p\geq0$
- $a_q\geq0$
が成立していなければならないので、以下を満たすように $\Delta_p$ のクリッピングを行う必要がある。
- $t_p=t_q$ のときは $ 0 \leq a_p + \Delta_p \leq c/t_p$
- $t_p=-t_q$ のときは $ \mathrm{max}\{0,c/t_p\}\leq a_p+\Delta_p$
変数の選択方法¶
最後に、動かす $\mu_p,\mu_q$ の選択基準であるが、SMO法の発見者である $John C. Platt$ の論文に従うならば以下の様になる。
- $KTT$条件を破る$a_p$を$1$つ目に選ぶ。
- 続いて、$\left|y\left(\mathbf{x_q}\right)-y\left(\mathbf{x_p}\right)\right|$ が最大となる$a_p$を次に選ぶ。
これは、$\left|y\left(\mathbf{x_q}\right)-y\left(\mathbf{x_p}\right)\right|$ が大きければそれだけステップ幅も大きくなるため収束が早くなるというヒューリスティックス（直感）である。
これを繰り返して、$\tilde{L}$ が収束するまで反復を繰り返せば学習完了である。
実装例¶
In [ ]: