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

Implement kernel SVM

Introduction


Today, I implement the kernel SVM.
Oputimization is interror point method.
This post is written about Implementation.
I will write Theorem of kernel SVM in another post.
I will put when writing its post finished.

# I finished writing theorem of SVM.
Theorem of SVM part1

My computer is windows.
Also, OS is windows.
I implement by Python3.

Overview

  • introduce kernel
  • introduce dataset
  • result of implementation

kernel

The kernel is the method of solving the nonlinear problem.
kernel is map converting data so that linear can separate class of data.
enter image description here
⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓
enter image description here
Converting data is expressed \(\phi(x)\).
\[\phi:x -> \phi(x)\]
but, kernel function is used \[K(x,y)=\phi(x)^T \phi(y)\] in SVM,
Because, SVM can cumpute only \(\phi(x)^T \phi\).
The famous kernel is RBF and polynomial.
  • RBF
    \[K(x,y) = \exp(-\gamma ||x-y||^2)\]
  • polynomial
    \[K(x,y) = (x^Ty+c)^p\]
If \(K(x,y) = x^Ty\) , This is linear SVM.

Dataset

Today, I use following two data generated from normal distribution by np.random.randn.
enter image description here
and
enter image description here
The code making this dataset is upload in github.
code of making dataset

Implementation

I used RBF kernel.
gamma is 0.5
Regularization coefficient is 50.
enter image description here
next, I use RBF kernel.
gamma is 0.5.
Regularization coefficient is 100.
enter image description here
My code is published github.
kernel SVM code

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

コメント

このブログの人気の投稿

Thorem of SVM part 2

Introduction 日本語 ver This post is written about theorem of SVM. This post is part 2. Part 1 is written about deriving the objective function. I will write about dual problem. The objective function which deriving in Part 1 is called the main problem. Typically, We optimize not the main problem, but the dual problem. I will write about deriving the dual problem from the main problem. If you until look up part 1, please look up Theorem of SVM part 1 . I implement SVM. It post is Implement linear SVM Implement kernel SVM Overview Main problem Dual problem  Lagurange function maximize L about dual variable, minimize L about primal variable minimize L about primal variable, maximize L about dual variable. Main problem I will review the main problem in Part 1. $$\min_{w,b} \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i$$ $$~~s.t~~ \forall i \in N, y_i (w^T \phi(x_i) + b) \geq 1 - \epsilon_i ,~~~, \forall i \in N~\epsilon \geq 0$$ This problem is called s...

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で他は0であるので、 $$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}|| + ...

Definition of Topology space

Introduction 日本語 ver Today, I will write about General Topology. General topology is very impossible for studying mathematics. General topology defines phase to define continuity of function. Today, I will explain phase. Also, This post is my review of General Topology. Overview  Distance space Axiom of phase Topology space Open set Distance space Firstly, Distance space is defined. Let X is set, $d:X\times X ->\mathbb{R}$, (X,d) is distance space $\iff$ $\forall x,y \in X,~~~~~d(x,y) \geq 0$ $\forall x,y \in X,~~~~~x = y \implies d(x,y) = 0$ $\forall x,y \in X,~~~~~d(x,y) = d(y,x)$ $\forall x,y,z \in X, ~~~~d(x,y) + d(y,z) \geq d(x,z)$ this condition is called axiom of distance. d is called distance function. Topology  space Let (X,d) is distance space. $\mathbb{O} \in 2^X$ is phase in (X,d) $\iff$ $\phi,X \in \mathbb{O}$ $\forall O_1,O_2 \in \mathbb{O} \implies O_1 \cap O_2 \in \mathbb{O}$ $\forall \Lambda ,~~\forall \{O_\l...