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

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}|| + ...

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...

Introduction English ver 今日から位相空間論について書いていきます。自分の復習のためですが、、、 位相空間は数学を学ぶ上でとても重要になってきます。 位相空間を定義する利点の一つは写像の連続性を位相を用いて定義できるからです。 今日は位相の定義について書いていきたいと思います。 概要   距離空間 位相の公理 位相空間 開集合 距離空間 初めに距離空間を定義します。 Xを集合,関数dを $d:X\times X ->\mathbb{R}$とします。この時、 (X,d)が距離空間である$\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)$ この条件は距離の公理と呼ばれています。 dは距離関数と呼ばれています。 位相空間 (X,d)を距離空間とします。この時、 $\mathbb{O} \in 2^X$が(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_\lambda \}_{\lambda \in \Lambda} \in O \implies \bigcup_{\lambda \in \Lambda} O_\lambda \in \mathbb{O}$ ここで$2^X := \{A | A \subset X \}$です。 この条件は位相の公理と呼ばれています。 気を付けるべき点は $\Lambda$ は任意の添え字集合であることです。つまり、$\mathbb{N}$でなくても$\mathbb{R}$のような実数無限集合でもよいのです。 この時、$(X,d,\mathb...

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...

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 \...

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...

Introduction   English ver SVMの理論編を書いていこうと思います。実装編は 線形SVMの実装 カーネルSVMの実装 をご覧ください。 このpart 1の記事ではSVMの目的関数の導出までを書いていきます。 概要 一般線形モデル SVMの説明 ハードマージン ソフトマージン 一般化線形モデル  SVMには一般化線形モデルが使われています。一般化線形モデルとは次のようなモデルのことです。 $$f(x) = w^T\phi(x) + b$$ bはバイアスと呼ばれています。 $$0 = w^T\phi(x) + b$$ は超平面（n次元平面）を表します。この超平面は$\phi(x)$をきれいに２クラスに分類するように決めます。 ここで$\phi(x)$は平面で分類できないようなxを平面で分類できる特徴空間に送る写像です。 $\phi(x)$のイメージは以下の画像を見てください。 左は線形分離不可能なデータ。右は$\phi(x)$によって特徴空間に移された線形分離可能なデータです。 よって$w^T \phi(x) + b$は特徴空間では平面となります。 次に、SVMの目的を説明します。 SVMの説明 SVMではラベルは1 or -1として扱います。$y \in \{1,-1\}$、Xをデータセットとします。 私たちの目的は決定関数と呼ばれるものを作ることです。 SVMでは以下のようなものです。 $$f(x_i) > 0 \implies y_i = 1$$ $$f(x_i) < 0 \implies y_i = -1$$ f(x)は $w^T \phi(x) + b$とし、パラメータwとbを最適化します。 しかし、最適化するにはあるよい基準が必要になります。SVMではマージンと呼ばれる値を使い、最適な境界線を決定します。 ハードマージン SVMはマージンと呼ばれる値を用いて、クラスの境界は決定されます。 マージンとは何なのでしょうか？ 境界$w^T \phi(x) +b = 0$から一番近いデータ$x_i$を持ってきます。マージンとは、境界と$x_i$との距離のことを言います。 ...

Introduction   日本語 ver I will explain theorem of SVM. Please look at my implementation of SVM. Implement linear SV M Implement kernel SVM Today, I will explain about SVM until deriving the objective function. Overview   Generalized linear model   Explain SVM hard margin   soft margin   Generalized linear model   SVM is used generalized linear model. Generalized linear model is following function $$f(x) = w^T\phi(x) + b$$ b is called bias. $$0 = w^T\phi(x) + b$$ is hyper plane. This hyper plane separate two class of $\phi(x)$. hyper plance is n-dimensional plane. if n = 1, hyper plane is line. if n = 2, hyper plane is normal plane. $\phi(x)$ have effect of converting x to data which can be separated by a line. image of $\phi(x)$ is the left image has nonlinear data. right image has linear data. $\phi(x)$ convert from left image to right image. I will handle $w^T \phi(x) + b$ a...

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-平均法とも呼ばれています。初めに、適当なクラスに分け、各クラスの中で平均となるベクトルを求めます。そして、各データに対して、すべての平均ベクトルとの距離を求めます。そして、最小となる距離になるクラスに改めて、そのデータをクラスタリングします。そして、新たに得られたクラスの中でそれぞれ平均ベクトルを求め、これを繰り返し、平均ベクトルが動かな...

Introduction   日本語 ver Today, I implement kernel k-means. The k-means algorithm is clustering algorithm. A reason that I implement kernel k-means algorithm is that I and my friend conceived introducing kernel to k-means. I investigated paper of kernel k-means. I found [This page](http://www.cs.utexas.edu/users/inderjit/public_papers/kdd_spectral_kernelkmeans.pdf)  Thus I could implement kernel k-means algorithm. I introduce the implementation of normal k-means and kernel k-means. I handle the only implementation of kernel k-means. I will write the theory of kernel k-means. If I finished writing it, I publish on this post. #  I finished. Theorem of K-means Overview   dataset   a few explaining k-means  k-means    kernel k-means   Dataset   I used two datasets. first data is designated for normal k-means. second data is designated for kernel k-means. First data ha...

Introduction English ver 今日はカーネルSVMを実装しました。 最適化には内点法を実装しました。 この記事では実装のみ書いていますが、理論編もそのうちに書きたいと思います。書き次第、リンクを貼っておきます。 # 第一弾書きました。 SVMの理論 part 1 僕のcomputerはwindowsでOSもwindowsです。 実装はPython3で行います。 概要 カーネルとは データセットについて 実装の結果 カーネルとは カーネルとは非線形問題を解くための手法です。 直線で分類できないようなデータをある写像をもとで、直線で分類できるような分布に変形することです。次の画像を見たほうがわかりやすいかもしれません。 ⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓ このように変形することをカーネルトリックといいます。 変形されたデータは写像$\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によって生成された正規分布に従う乱数です。 と このデータを作ったコードは ここ に置いてあります。 Implementation 今回はRBFカーネルを使いました。 $\gamma = 0.5$ 正規化係数50とすると次のようになりました。 次に二つ目のデータセットに対して、RBF kernelを使いました。 $\gamma = 0.5$ 正規化係数を100とすると、次のよ...

Introduction 日本語 ver 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. ⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓⇓↓ 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$ , T...