スキップしてメイン コンテンツに移動

カーネルSVMの実装

Introduction


今日はカーネルSVMを実装しました。
最適化には内点法を実装しました。
この記事では実装のみ書いていますが、理論編もそのうちに書きたいと思います。書き次第、リンクを貼っておきます。

# 第一弾書きました。
SVMの理論 part 1

僕のcomputerはwindowsでOSもwindowsです。
実装はPython3で行います。

概要

  • カーネルとは
  • データセットについて
  • 実装の結果

カーネルとは

カーネルとは非線形問題を解くための手法です。
直線で分類できないようなデータをある写像をもとで、直線で分類できるような分布に変形することです。次の画像を見たほうがわかりやすいかもしれません。
enter image description here
⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓
enter image description here
このように変形することをカーネルトリックといいます。
変形されたデータは写像\(\phi\)によって\(\phi(x)\)と表現されます。
\[\phi:x -> \phi(x)\]
しかし、SVMではカーネル関数は次のように表されることが多いです。
\[K(x,y)=\phi(x)^T \phi(y)\]
なぜなら、SVMでは \(\phi(x)^T \phi\)のみを計算するからです。
最もよく使われているカーネルはRBFとpolynomialです。
  • RBF
    \[K(x,y) = \exp(-\gamma ||x-y||^2)\]
  • polynomial
    \[K(x,y) = (x^Ty+c)^p\]
\(K(x,y) = x^Ty\)とすればこれは線形SVMになります。

データセット

今日使うデータセットはnp.random.randnによって生成された正規分布に従う乱数です。
enter image description here
と
enter image description here
このデータを作ったコードはここに置いてあります。

Implementation

今回はRBFカーネルを使いました。
\(\gamma = 0.5\)
正規化係数50とすると次のようになりました。
enter image description here
次に二つ目のデータセットに対して、RBF kernelを使いました。
\(\gamma = 0.5\)
正規化係数を100とすると、次のようになりました。
enter image description here
なんか面白い。
今回のSVMのコードはこちらに置いてあります。

Reference

https://qiita.com/ta-ka/items/e6fd0b6fc46dbab4a651
http://aidiary.hatenablog.com/entry/20100501/1272712699
https://www.amazon.co.jp/%E3%82%B5%E3%83%9D%E3%83%BC%E3%83%88%E3%83%99%E3%82%AF%E3%83%88%E3%83%AB%E3%83%9E%E3%82%B7%E3%83%B3-%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92%E3%83%97%E3%83%AD%E3%83%95%E3%82%A7%E3%83%83%E3%82%B7%E3%83%A7%E3%83%8A%E3%83%AB%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA-%E7%AB%B9%E5%86%85-%E4%B8%80%E9%83%8E/dp/4061529064
Labels:

コメント

コメントを投稿

このブログの人気の投稿

K-means 理論編

Introduction English ver 今日はK-meansアルゴリズムの理論について書きます。 K-meansアルゴリズムはクラスタリングのためのアルゴリズムです。 K-meansの実装の記事は カーネルK-meansの実装 を御覧ください。 この記事はカーネルK-menasの実装についての記事ですが、通常のK-meansの実装も行っています。カーネルK-meansについてはまた、今度別の記事で紹介したいと思います。 概要 1 of K 符号化法 プロトタイプ 歪み尺度 最適化 1 of K 符号化法 K-meansはK個のクラスについて分類することを考えます。 K-meansでは $x_n$がkのクラスに属していることを次のように表します。 ベクトル$r_n:1 \times K$ を $$r_n := (0,0,..,1,..,0)$$ このベクトルはk番目にのみ1を持ち、それ以外は0を要素に持つようなベクトルです。 こののような表現の仕方を1 of K符号化法と呼びます。 プロトタイプ K-meansではプロトタイプと呼ばれるベクトルを選びます。このベクトルは各クラスに一つあり、そのクラスの代表のようなベクトルです。 K-means ではそのようなベクトルは各クラスの平均ベクトルとなります。これは目的関数から自然と導かれます。 歪み尺度 プロトタイプベクトルを $\mu_i ~\forall k \in K$とします。 この時、k-meansの目的関数は次のようになります。 $$J = \sum_{n=1}^{N} \sum_{k=1}^{K} r_{nk} ||x_n-\mu_k||^2$$ ここで、 $r_{nk}$ は$r_n$のk番目の要素です。 この目的関数について少し説明をします。$r_{n}$は$x_n$が属しているクラスのラベルの場所だけ1で他は０であるので、 $$J = \sum_{n=1}^{N} ||x_n - \mu_{x_n}||$$ ここで、$\mu_{k_n}$は$x_n$が属しているクラスのプロトタイプです。 よって、 $$J = ||x_1 - \mu_{x_1}|| + ||x_2 -\mu_{x_2}|| + ...
コメントを投稿
続きを読む

カーネルk-meansの実装

Introduction   English ver 今日はカーネルk-meansの実装をしました。k-menasアルゴリズムはクラスタリングのためのアルゴリズムです。僕がカーネルk-meansを実装しようと思ったのには一つ理由があります。それは僕の友人がk-meansのプレゼンを、僕がカーネルのプレゼンをしていた時に、k-meansにカーネルを適応できないかと思ったからです。そこで、カーネルk-meansについての論文を探しました。 ここのpdf を主に参考にさせていただきました。うまくカーネルk-meansを実装できたと思います。ここでは、普通のk-meansとカーネルを用いた,kernel k-meansについての実装の結果を紹介します。 また、この記事では実装結果のみ書きますが、理論のほうも別の記事で書くつもりです。書き終えたらリンクをこの記事にも貼っておきます。 #  理論編書きました。K-means 理論編 概要 dataset   ちょっとだけ理論の説明  k-means    kernel k-means   Dataset   English ver 今回使うのは二つのデータセットです。一つ目は、普通のk-means用のデータです。二つ目はkernel k-means用のデータセットです。 一つ目のデータは、三つのグループで構成されており、次元は2で、サンプル数は300です。以下のような分布になっています。 二つ目のデータは二つのグループで構成されており、次元は2でサンプル数は300です。   this page にデータセットを作ったコードを載せています。 ちょっとだけ理論の説明 k-meansとは、k-平均法とも呼ばれています。初めに、適当なクラスに分け、各クラスの中で平均となるベクトルを求めます。そして、各データに対して、すべての平均ベクトルとの距離を求めます。そして、最小となる距離になるクラスに改めて、そのデータをクラスタリングします。そして、新たに得られたクラスの中でそれぞれ平均ベクトルを求め、これを繰り返し、平均ベクトルが動かな...
コメントを投稿
続きを読む

Bayes' theorem

Introduction sorry, this page is Japanese only.   今回はベイズの定理について書こうと思います。 ベイズの定理とは、イギリスのトーマス・ベイズによって発見された、条件付き確率に関する定理です。現在のベイズ推定で用いられる重要な定理です。どのような定理かを解説していこうと思います。 ベイズの定理 ベイズの定理とは 確率P(B|A):事象Aが起こった後での事象Bの確率（事後確率） 確率P(B):事象Aが起こる前の事象Bの確率（事前確率） とするとき以下が成り立つことを示しています。 $$P(B|A) = \frac{P(A|B) P(B)}{P(A)}$$ 例 例えば、次のように事象A、事象Bwo定義します。 事象A:あるYoutuberが動画を投稿したとき、再生回数が100万回を超える 事象B:あるYoutuberがお金を50万円以上使う動画を投稿する この時確率P(A|B)、つまり50万円以上を使った動画が再生回数100万回を超える確率は、youtube内の50万円以上使っている動画を根こそぎ集め、その再生回数を得ることによって推定できそうです。では確率P(A|B)がわかった時、確率P(B|A)もわかる。これがベイズの定理の強みです。（当然確率P(A)とP(B)がわかっている必要はあります。） 確率P(B|A)とはあるYoutuberの動画が再生回数100万回を超えたとき、その同がで50万円以上使っている確率となります。これがわかれば、100万回動画が再生される原因は本当に50万円以上お金を使うことなのかがわかります。 確率P(A|B)が低い時を考えてみましょう。 つまり、50万円以上使った動画は再生回数100万回を超える確率は高い。しかし、100万回再生回数を突破したとき、その動画が50万円以上使っている可能性は低い。この状況はベイズの定理の式を考えいると理解しやすいです。 ベイズの定理の式を見てみると、P(B|A)は低く、P(A|B)が高いということは、確率P(A)が著しく高い。もしくは、P(B)が著しく低い。この二つがあげられます。 つまり、あるYouruberが100万回再生を突破する確率がかなり、高い。もしくは、あるYoutuber...
コメントを投稿
続きを読む