サポートベクターマシン カーネル編
こんにちは、小澤です。
当エントリは「Machine Learning Advent Calendar 2017」の16日目のエントリです。
今回は機械学習svmについてざっくりまとめ理論編でも触れられている、SVMにおいて、データを高次元に飛ばすことで非線形の決定境界を作ることが可能なカーネル法について書かせていただきます。
SVMにおけるweightの求め方
SVMのweightは以下の最適化問題を解くことによって求められました
[latex] min. \frac{1}{2}||{\bf w}||^2 + C \sum_i \xi_i \\ \\ st. y_i({\bf w}^T {\bf x} - b) \geq 1 - \xi_i \\ \xi_i \geq 0 [/latex]
ここで、wがwight, bが切片、xが実際のデータ, ξがスラック変数となっています。
これを解いて、wとbを求めるには、少々難しい計算になります。 凸関数であることを利用して、ラグランジュの未定乗数法を使って、双対問題をといて、ともはや日本語でおkって話ですね。 この辺りは、この後のカーネル関数を導入するに必要な式を出したいだけなので、詳細は割愛して、詳細は参考文献に任せることにします。
最終的に未定乗数αとβを使って、以下のような式を最大化すればいいことになります。
[latex] L({\bf w}, b, \alpha, \beta) = -\frac{1}{2} \sum_{i, j} \alpha_j \alpha_j y_i y_j {\bf x}_i {\bf x_j} + \sum_i \alpha_i [/latex]
なんか複雑な式ですが、要するに各データの組み合わせで掛け算している感じですね。 この式を使って、元の関数は
[latex] f({\bf x}) = \sum_i \alpha_i y_i {\bf x}_i {\bf x} + b [/latex]
と表すことができます。
カーネル関数の導入
さて、上記の計算では、サポートベクター(x_i)との内積で計算されるものになっています。 そのため、この内積部分の計算の仕方を工夫すれば、高次のベクトル空間での計算も可能になります。
この高次元の内積を求めるための関数として、カーネル関数kを導入すると、以下のような式になります。
[latex] f({\bf x}) = \sum_i \alpha_i y_i k({\bf x}_i, {\bf x}) + b [/latex]
カーネル関数の例
さて、では実際にどのようなカーネル関数が使われるのか例を2つ見ていきましょう。
多項式カーネル
まずは、多項式カーネルです。 これは、読んで字のごとくd次の多項式で表されるカーネルです。
[latex] k({\bf x}_i, {\bf x}_j) = ({\bf x}_i {\bf x}_j + r)^d [/latex]
rが新たにハイパーパラメータとして追加されています。
RBFカーネル
RBF(Radial Basis function Kernel)は以下のような関数で表されます。
[latex] k({\bf x}_i, {\bf x}_j) = \exp(-\gamma ||{\bf x}_i - {\bf x}_j||^2) [/latex]
こちらは非常によく使われるカーネル関数です。 そのため、SVMのハイパーパラメータとして、Cとγの組み合わせで目にする機会も多いかと思います。
おわりに
今回は、SVMのカーネル法について、書かせていだきました。
非常に駆け足な内容となってしまいましたが、「SVMはカーネル関数を使って非線形な分類ができる」というのがどういうことかなんとなくわかっていただければと思います。
明日は、ランダムフォレストについて書かせていただく予定です。 お楽しみに！
