今更 Support Vector Machine を実装してみる（１） - 徒然なる日々を送るソフトウェアデベロッパーの記録（２）

例の本、

作者: 荒木雅弘
出版社/メーカー: 森北出版
発売日: 2014/03/29
メディア: 単行本（ソフトカバー）
この商品を含むブログ (4件) を見る

を底本に機械学習を勉強しているこの頃ですが、Support Vector Machine の章は
色々端折って書いてあるので、まずはそれを補足して本題に入りたいと思います。

補足１：式(7.12)を極とするパラメータの計算式の導出

$1/2 \times \|w\|^2$ を線形条件 $y_i (\vec{w}\cdot\vec{x_i} + w_0) \ge 1$
の下で最小化する問題が解を持つための必要十分条件は KKT 条件
${ \displaystyle \vec{w}-\sum_i ( \lambda_i * y_i (\vec{x_i}) ) = 0 }$
${ \displaystyle y_i (\vec{w}\cdot\vec{x_i} + w_0) \ge 1 }$
${ \displaystyle \lambda_i \ge 0 }$
${ \displaystyle \lambda_i (y_i (\vec{w}\cdot\vec{x_i} + w_0 - 1) = 0 }$
で与えられます。 $\lambda_i$ はラグランジュの未定係数です。

新しい式 $z = 1/2 \times \|w\|^2 - \sum_i (\lambda_i * (\vec{w}\cdot\vec{x_i} + w_0 - 1))$
では最小を与える点は w, w0 の微分が０になっているはずですが、w については考慮済みなので、
w0に関して微分すると教科書通り、 $\sum_i(\lambda_i y_i) = 0$ が
導出されるので、最小化するべき式は
${\displaystyle z = -1/2 \sum_{i,j}(\lambda_i \lambda_j y_i y_j \vec{x_i}^\mathrm{T} \cdot \vec{x_j}) + \sum_i \lambda_i }$
${\displaystyle \sum_i (\lambda_i y_i) = 0 }$
となります。（教科書と符号が逆になっています。）
新しい制約条件を取り込むために再度ラグランジュの未定係数 $\mu$ を導入すると KKT 条件は
${\displaystyle -\sum_j(\lambda_j y_i y_j \vec{x_i}^\mathrm{T} \cdot \vec{x_j}) + 1 + \mu y_i = 0 }$
${\displaystyle \sum_i(\lambda_i y_i) = 0 }$
${\displaystyle \mu \ge 0 }$
wを $\lambda_i$ で書き直した式を w, w0 に関する境界条件に代入してみると
$\sum_j(\lambda_j y_i y_j \vec{x_i}^\mathrm{T} \cdot \vec{x_j}) + w_0 y_i \ge 1$
なので、 $\mu = -w_0$ であることが分かります。（制約条件がいわいる「有効制約」になっている
ことにも注意します。）
$\vec{x_i}^\mathrm{T} \cdot \vec{x_j}$ をカーネル $K(\vec{x_i},\vec{x_j})$ と書き、(カーネルは可換であることに注意)
更に $A_{ij} = y_i y_j K(\vec{x_i}, \vec{x_j})$ と置くと、上式は
$\displaystyle \left( \begin{array}{c} A \ \vec{y}^\mathrm{T} \\ \vec{y} \ 0 \end{array} \right) \left( \begin{array}{c} \vec{\lambda} \\ w_0 \end{array} \right) = \left( \begin{array}{c} 1 \\ 0 \end{array} \right)$
ただし、 $\vec{y} = \left( y_1, y_2, \cdots, y_m \right)$ とします。
また左辺に出てくる行列をここだけの用語として「Aの拡大行列A'」と呼ぶことにします。

この式は解けるのか？

前節最後に導出した式は行列 $A$ が半正定値、または半負定値であれば逆行列を持ちます。
Aの拡大行列A'の固有値を $\nu_1, \cdots, \nu_{m+1}$ とした時、
$A' = P^\mathrm{T} D P$ という対角行列 D と直交行列 P が存在しますが、
$A'_{ij} = \sum_{k=1}^{m+1}(P_{ik} \nu_k P_{kj})$ なので、もし $\nu_{m+1} = 0$ で
あったとすると、 $A_{ij} = \sum_{k=1}^{m}(P_{ik} \nu_k P_{kj})$
つまり、 $\nu_k$ は行列 A の固有値になっていますので、A'の他の固有値は
全て0以上、または全て0以下となるはずです。よって二次形式 $\vec{x}^\mathrm{T} A' \vec{x}$
は任意の $x \in \mathbb{R}^m$ で0以上または0以下となるはずですが、この二次形式を
成分に展開してみると
$\sum_{i,j}^{m+1}(x_i A'_{ij} x_j) = \sum_{i,j}^m(x_i A'_{ij} x_j) + 2 \sum_j(x_i y_i x_{m+1})$
となって例えばAが正定値の場合は $x_{m+1} < \frac{-\sum_{i,j}^m{y_i A'_{ij} y_j}}{2 m}$
という $x_{m+1}$ を取ると二次形式は負となってしまい、矛盾します。
従って $\nu_k$ は非ゼロであり、逆行列が存在します。

線形方程式を解く

得られた方程式はサンプルの数次数の線型方程式となり、陽解法で解くのが難しくなります。
ここでは収束が比較的早い共役勾配法（
共役勾配法 - Wikipedia
）で解いてみる予定です。手法の詳細は Wikipedia を参照してください。

サンプルを解いてみる

サンプルとして、xor を考えます。 $K(x, y) = (\langle x, y\rangle + 1)^2$ とします。
${\displaystyle 0: x_0 = [0, 0] y_0 = 1 }$
${\displaystyle 1: x_1 = [1, 0] y_1 = -1 }$
${\displaystyle 2: x_2 = [0, 1] y_2 = -1 }$
${\displaystyle 3: x_3 = [1, 1] y_3 = 1 }$
となるので、
${\displaystyle K(x_0, x_i) = 1, K(x_1, x_1) = 4, K(x_1, x_2) = 1, K(x_1, x_3) = 4 }$
${\displaystyle K(x_2, x_2) = 4, K(x_2, x_3) = 4, K(x_3, x_3) = 9 }$
となります。解くべき式は
${\displaystyle + \lambda_0 - \lambda_1 - \lambda_2 + \lambda_3 - w_0 = 1 }$
${\displaystyle - \lambda_0 + 4 \lambda_1 + \lambda2 - 4 \lambda_3 + w_0 = 1 }$
${\displaystyle - \lambda_0 + \lambda_1 + 4 \lambda2 - 4 \lambda_3 + w_0 = 1 }$
${\displaystyle + \lambda_0 - 4 \lambda_1 - 4 \lambda_2 + 9 \lambda_3 - w_0 = 1 }$
${\displaystyle \lambda_0 - \lambda_1 - \lambda_2 + \lambda_3 = 0 }$
この式を解くと
$\lambda_0 = 10/3, \lambda_1 = 8/3, \lambda_2 = 8/3, \lambda_3 = 2, w_0 = -1$
となります。

明日はこれらの式を Java で書き、Weka 付属のデータを食わせてみます。