Implement linear SVM

Introduction

Today, I implement liner SVM (support vector machine).
SVM is one of the most strong algorithm of machine learning before becoming popular Deep learning.
I will write detail of Logic of liner SVM in other posts.

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

My computer is windows. OS is windows. Program is written by Python3.
This program is used Interrior point method in Oputimization.

Dataset

I used two dataset.
First, I used data separated by hyper plane.
Second, I used data mixed

$C_1$ and

$C_2$ .
First data is distributed such as the following.
enter image description here

I can write separate line of distribution.
Second data is distributed such as the following.
enter image description here

I can not write separate line of distribution.
I will try liner SVM about these data.

Implementation

data1

This line is hyper plane.
It is written like copperplate.

data2
I tried to estimate hyper plane by variable C.

C value cause this line.
The smoller C value is the easier permitting miss classification.
It is difficult for our to confime effect of C.
It is easy to confime effect of C when I use non liner SVM.
I will write non liner SVM another post.

CODE

My code of liner SVM is opend to the github.
My SVM code is here
File used this time is git_SVM_check.py and git_SVM_def.py .
git_SVM_check.py is main file had following code.

if __name__ == '__main__':

git_SVM_def have class of SVM and code of interror point method.
I will write post of nonliner SVM.
If you see next post also ,I am very glad.

このブログの人気の投稿

カーネルK-means 理論編

Introduction English ver 今日は、カーネルK-meansの理論について書きます。カーネルK-meansは通常のK-meansの欠点を補うことができます。通常のK-meansの欠点とカーネルK-meansの強みも説明します。もし、まだ御覧になられていなければ、通常の K-means 理論編の記事を見ていただけるとよいのではないかと思います。カーネルK-meansの実装編も併せてご覧ください。概要 K-meansの弱点カーネルトリックカーネルK-means アルゴリズム K-meansの弱点例えば、次のようなデータを用意します。このデータはK-meansによってうまく分類することはできません。なぜなら通常のK-meansでは、データとプロトタイプのユークリッド距離に依存しているからです。そのため、このような円状に分布しているデータはうまく分類することができません。プロトタイプとはそれぞれのクラスにあり、そのクラスを代表するようなもののことです。K-meansでは各クラスの平均ベクトルとなります。それゆえ、以下のような分類になってしまいます。このようなデータではK-meansはうまくいきません。 K-meansで分類できるデータセットは次のように各クラスで固まっている必要があります。カーネルK-meansはK-meansの弱点を補います。カーネルトリック初めに、カーネルトリックを説明します。線形分離できないようなデータ

$X$ を例えば次のように線形分離できるように

$\phi(x)$ に送る写像

$\phi$ を考えます。カーネルは次のように定義されます。

$K(x,y) = \phi(x)^T \phi(y)$

$\phi$ を具体的に計算することは難しいですが、

$K(x,y)$ を計算することなら簡単です。この手法をカーネルトリックと呼ばれます。カーネルK means K-meansの目的関数を復習しておきます。

$J = \sum_{n=1}^{N} \sum_{k=1}^{K} r_{nk} ||x_n-\mu_k||^2$ ここで、プロトタイプは

$\mu_i ~\forall k \in K$ としま...

ダイクストラ法

Introduction English ver 今日は、ダイクストラ法について書きます。ダイクストラ法とは最短距離を求めるアルゴリズムです。地図はグラフで表されます。もし、まだ this page を見ていない方は先にこちらをご覧ください。今回はこの記事を前提としています。このページでは、グラフの定義と、ヒープ構造について書いています。ダイクストラ法ではヒープ構造を使って、かなりの計算量を落とします。このスライドはダイクストラ法を説明したスライドです。 Overview アルゴリズム実装アルゴリズムこのアルゴリズムはスタート始点のノードを決める。そして、それをAと名付ける。各ノードに

$d=\infty$ を割り当てる。ただし、スタート地点はd=0 Aの隣接ノードのリストをadj_listと名付ける。 For adj in adj_list: If d of adj > d of A + weight to adj -> d = A + weight to adj. グラフnetworkからAを取り除くグラフnetworkの中で最初のdを持っているノードをAとし、4に戻る。となっています。このアルゴリズムを図を用いて説明します。このグラフを使って説明します。初めに、スタート地点を決めます。そして、各ノードに

$d=\infty$ を割り当てます。 Aから始まります。Aの隣接ノードであるBのdを更新します。もし、現在のBよりもAのdとA->Bへの重みを足したもののほうが小さいならdをその値に更新します。同じようにCnのdを更新します。次にAを取り除きます。次はBから始まります。Aと同じことをやります。このダイクストラ法では今のような操作をグラフの全てのノードに×がつくまで続きます。実装このアルゴリズムでは

$O(log(|V|^2))$ という計算量を持っています。最小のdを持つノードを探すのに時間がかかります。しかし、ヒープ構造を使えばO((E+V)log(V))に減らせます。ヒープ構造で現時点での...

ロジスティック回帰理論編

Introduction English ver 今日はロジスティック回帰について書こうと思います。ロジスティック回帰は機械学習の中でも基本とされています。ロジスティック回帰は二値を分類するためのアルゴリズム、モデルです。概要この記事はPRMLを参考に書かせていただいています。最適化には反復再重みづけ最小二乗法を用いています。シグモイド関数分類のための確率を定義交差エントロピー誤差関数反復再重みづけ最小二乗法シグモイド関数初めにシグモイド関数を定義します。以下のような関数です。

$\sigma(a) = \frac{1}{1+\exp(a)}$ 後に扱うので、シグモイド関数の微分を計算しておきます。きれいな形をしています。

$\begin{eqnarray*} \frac{d}{d a} \frac{1}{1+\exp(a)} &=& \frac{\exp(-a)}{(1+\exp(-a))^2} \\ &=& \frac{1}{1+\exp(-a)} \frac{\exp(-a)}{1+\exp(-a)}\\ &=& \frac{1}{1+\exp(-a)} \{ \frac{1+\exp(-a)}{1+\exp(-a)} - \frac{1}{1+\exp(-a)} \} \\ &=& \sigma(a)(1-\sigma(a)) \end{eqnarray*}$ シグモイド関数は機械学習において大事な役割を果たしています。シグモイド関数は以下のような形をしています。これを見てわかる通り、シグモイド関数は次のような性質を持っています。シグモイド関数は定義域は

$(-\infty,\infty)$ で定義され、値域は

$(0,1)$ で定義されていますシグモイド関数は単調増加関数ですシグモイド関数は(0,0.5)で点対称ですシグモイド関数の値を確率として考えることができるようになります。分類のための確率の定義初めにデータが正しく分類されたかの確率を考えてみる。この直線は超平面だと思ってください。超平面は以下のように表されます。

$w^T x= 0$ wは超平面に対する法線ベク...

journey of Froakie (ケロマツの旅路)

このブログを検索

Implement linear SVM

Introduction

Dataset

Implementation

CODE

ラベル

コメント

コメントを投稿

このブログの人気の投稿

カーネルK-means 理論編

ダイクストラ法

ロジスティック回帰理論編

journey of Froakie (ケロマツの旅路)

Implement linear SVM

Introduction

Dataset

Implementation

CODE

ラベル

コメント

コメントを投稿

このブログの人気の投稿

カーネルK-means 理論編

ダイクストラ法

ロジスティック回帰 理論編

ロジスティック回帰理論編