MIT OCW, Machine Learning 09日目 カーネル化SVM

Rohit Singh, Tommi Jaakkola, and Ali Mohammad. 6.867 Machine Learning. Fall 2006. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

Lecture 8

Support Vector Machine Revisited

SVMをdual form(exampleが内積でのみ現れる形)に変換する. すべてのexampleを$\phi$で$d$次元のfeature spaceに写し,$\{\phi(\mathbf{x_t}, y_t)\}_{t=1}^n$が線形分離可能であるようにし,feature spaceにおいてmarginを最大化するパラメータを考える.この問題は
$$\text{minimize } \|\theta\|^2/2 \text{ subject to } y_t(\theta^T \phi(\mathbf{x}_t) + \theta_0) \geq 1, t=1,...,n \ \ \ (1)$$
という最適化問題に一致する. もちろんslack variableも導入できるが,これは後に回す. このような最適化問題(凸,線形制約)は,Lagrange multipliersによってdual formに変形できる. $\alpha_t \geq 0$を導入し,$\alpha = \{\alpha_1,...,\alpha_n\}$によって
$$J(\theta, \theta_0;\alpha)=\|\theta\|^2/2 - \sum_{t=1}^n \alpha_t \left[y_t(\theta^T\phi(\mathbf{x}_t)+\theta_0)-1 \right]$$
を$\alpha$によって最大化することを考えるのである.$J(\theta, \theta_0)=\max_{\alpha\geq 0} J(\theta, \theta_0, \alpha)$の最小化が$(1)$に一致することを示す.
$\theta, \theta_0$を少なくとも1つの束縛条件が満たされていないように設定する.$y_i(\theta^T \phi(\mathbf{x}_i)+\theta_0)<1$であるとすると任意の$\alpha_i>0$に$-\alpha_i[y_i(\theta^T \phi(\mathbf{x}_i)+\theta_0)-1]>0$.$\alpha_i =\infty$とすれば$J(\theta,\theta_0)=\infty$.だから,Lagrange multiplier $\alpha$は制約条件を満たさせる働きがあるとわかる.
Slater conditionsという条件を満たしているとき,ある変数で最大化し,他の変数で最小化するというLagrange multipliersの最適化問題の最大化最小化の順序を交換できる.つまり
$$\min_{\theta, \theta_0} \max_{\alpha\geq 0} J(\theta, \theta_0;\alpha) = \max_{\alpha\geq 0} \min_{\theta, \theta_0} J(\theta, \theta_0, \alpha)$$
である. 左辺をprimal formといい,右辺をdual formという. dual formについて,まず$\min_{\theta, \theta_0}J$を解く.微分して
$$\begin{aligned} \frac{d}{d\theta_0}J &= - \sum_{t=1}^n \alpha_t y_t =0\\ \frac{d}{d\theta} J &= \theta - \sum_{t=1}^n \alpha_t y_t \phi(\mathbf{x}_t)=0 \end{aligned}$$
またしても,最適な$\theta$は$\{\phi(\mathbf{x}_t)\}_t$の張る空間の元となった.これらをもとの式に代入して,
$$\begin{aligned} J(\alpha) &= \min_{\theta,\theta_0}J(\theta, \theta_0,\alpha) \\ &= \begin{cases} \sum_t \alpha_t - (1/2) \sum_i \sum_j \alpha_i \alpha_j y_iy_j [\phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j)], &\text{ if } \sum_t \alpha_t y_t = 0 \\ -\infty &\text{otherwise} \end{cases} \end{aligned}$$
よって,dual formの解は
$$\begin{aligned} \text{maximize } &\sum_t \alpha_t - (1/2) \sum_i \sum_j \alpha_i \alpha_j y_iy_j [\phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j)] \\ \text{subject to } & \alpha_t \geq 0, \sum_t \alpha_t y_t = 0\end{aligned}$$
の解である. これがSVMのdual formとかkernel formといい,quadratic optimization problemであり,Gram matrix $\mathbf{K} = (k_{i,j}) = (\phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j))$によって,特徴づけられる.
maximum margin hyperplaneはsupport vectorと呼ばれる少数のexampleによって決まることをすでに見たが,これは$\phi$によって写像されたexampleたちにも同様で,ほとんどの$\hat{\alpha}_t$は$0$になり,$\hat{\alpha_t}>0$なるとき,$\mathbf{x_t}$や$\phi(\mathbf{x_t})$をまたsupport vectorという.
$\hat{\alpha}_t$が決まると,$SV$をsupport vectorの集合として,
$$\begin{aligned} \hat{y}(\mathbf{x}) &= \hat{\theta}^T\phi(\mathbf{x})+\hat{\theta_0} \\ &= \sum_{t} \hat{\alpha_t}y_t [\phi(\mathbf{x}_t)^T\phi(\mathbf{x})] + \hat{\theta_0} \\ &= \sum_{t \in SV} \hat{\alpha_t}y_t [\phi(\mathbf{x}_t)^T\phi(\mathbf{x})] + \hat{\theta_0} \end{aligned}$$
によって新しいexample $\mathbf{x}$の推測$\hat{y}({\mathbf{x}})$が計算できる.
$\hat{\theta_0}$は$\hat{\alpha}$を求めた後で,
$$\forall i \in SV. \ y_i(\hat{\theta}^T \phi(\mathbf{x}_i)+\hat{\theta_0}) = y_i \sum_{t \in SV}\hat{\alpha_t}[\phi(\mathbf{x}_t)^T\phi(\mathbf{x}_i)]+y_i\hat{\theta_0}=1$$
を解くことで得られる.
この解のgeometric marginは$1/\|\hat{\theta}_0\|$で得られる.つまり
$$\hat{\gamma_{geom}} = \left( \sum_{i=1}^n \sum_{j=1}^n \hat{\alpha_i}\hat{\alpha_j}y_iy_j K(i,j) \right)^{-\frac{1}{2}}$$

geometric marginを最大にするようなkernelが最適なkernelと言えるが,定数倍によってgeometric marginもその分定数倍になるので,kernelの比較には正規化が必要である.

Kernel Optimization

kernelのあるパラメータを変えて,問題により適したkernelをつくることができる. パラメータの最適化には,cross-validationやgeneralization errorに関連した基準(marginなど)が用いられる.