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

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
Labels:

コメント

コメントを投稿

このブログの人気の投稿

Theorem of K-means

Introduction 日本語 ver Today, I will write about the theorem of K-means algorithm. K-means algorithm is a method to do clustering about K of class. The post of implement K-means is Implement kernel K-means This post is written about kernel K-means. The kernel K-means is the method which covers the weak point of K-means. I will explain kernel K-means another post. Overview 1 of K coding scheme prototype vector Distortion measure Computing 1 of K coding scheme K-means algorithm is clustering K of class. Now, K-means algorithm expresses that $x_n$ be belong to k like as follows. Let vector $r_n:1 \times K$ is $$r_n := (0,0,..,1,..,0)$$ this vector have 1 in element of k'th and have 0 in else. This expression is called 1 of K coding scheme. Prototype vector K-means algorithm chooses vector which called a prototype. this vector has represented by the cluster. K-means algorithm is regard mean vector as representative of the cluster. I...
コメントを投稿
続きを読む

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...
コメントを投稿
続きを読む

SVMの理論 part 2

Introduction English ver 今日はSVMの定理について書いていきます。 この記事はpart 2になります。Part 1 では目的関数の導出までを書きました。Part 2では双対問題とゆわれるものを導出します。Part 1で導いた目的関数は主問題と呼ばれます。一般的に、SVMでは主問題ではなく、双対問題を解くことで最適解を得ます。 もし、まだPart 1を見ておられない場合は、 Theorem of SVM part 1 を見てくださるとよいのではないかと思います。 SVMの実装編は Implement linear SVM Implement kernel SVM を御覧ください。 概要 主問題 双対問題  ラグランジュ関数 主変数について、最小化、双対変数について最大化 双対変数について最大化、主変数について最小化 主問題 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$$ これはソフトマージンの時の目的関数ですが、以後ソフトマージンの場合のみを扱っていきます。 さて、双対問題と呼ばれるものですが、これは主問題から自然に導かれます。 双対問題 SVMの最適化問題は凸二次最適化問題と呼ばれる種類の問題です。凸二次最低化問題は、必ず大域最適解に近づくことが知れれており、数値上の安全性が高いとされています。 双対問題を導出します。まず、主問題を以下のように書き換えます。 $$\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) -1 + \epsilon_i \}\leq 0,~~~, \forall i \in N~ -\epsilon \...
コメントを投稿
続きを読む