読者です 読者をやめる 読者になる 読者になる

徒然なる日々を送るソフトウェアデベロッパーの記録(2)

技術上思ったことや感じたことを気ままに記録していくブログです。さくらから移設しました。

今更 Support Vector Machine を実装してみる(1)

Java 機械学習

例の本、

フリーソフトではじめる機械学習入門

フリーソフトではじめる機械学習入門

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

補足1:式(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 の微分が0になっているはずですが、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 付属のデータを食わせてみます。