マイノート

いろいろ勉強したことをまとめていきます

MENU

rubyでk-meansを手軽に使えるライブラリ

k-meansをrubyから使えるライブラリ作りました。

k-meansについては前に軽くまとめたので、そちらを

www.tcom242242.net

本ライブラリの使い方

gem install t_learn

サンプル

今回は以下のようなデータをk-meansでクラスタリングしようと思います。 rubyからpythonのライブラリを使用できるpyCallを使い描画します。

f:id:ttt242242:20170629044640p:plain

以下のプログラムで使用しているサンプルデータ(sample_2dim.json)はgithubにおいてあります。

gist5e8111b0cc66613eaacca1e03277032a

クラスタリング結果

f:id:ttt242242:20170629044847p:plain

大きな点はクラスターの重心を表しています。うまくクラスタリングできてるようです。

EMアルゴリズムで混合ガウス分布のパラメータ推定できるライブラリ(ruby)

作ったもの

EMアルゴリズムで混合ガウス分布のパラメータ推定ができるライブラリをrubyで作りました。

github.com

使い方

まず、本ライブラリのインストー

gem install t_learn

1次元データに対して

githubにおいてある “sample_1dim.json” を使います。

このデータは正規化(各データ数を表す縦軸に対して)すると以下の画像のようなデータになります。

f:id:ttt242242:20170624211109p:plain

この混合ガウス分布のパラメータを推定します。

require 't_learn'

em = TLearn::EM_Gaussian.new()
data_list = JSON.load(open("./sample_1dim.json"))
history = em.fit(data_list, k_num=2) # k_num はガウス分布の個数

以下、実行結果

likelihood: -3088.0358230172806
likelihood: -3087.7133321058004
省略
likelihood: -2943.95823100874
likelihood: -2943.9582300846514
====================================
pi : [0.29168644105123087, 0.70831355894877]
mu : [[0.029483770596389985], [10.033090965120484]]
conv : [[[4.166929409854276]], [[8.88533611395374]]]

出力されたパラメータを用いると、以下のような(緑のグラフ)混合正規分布を表していることがわかります

f:id:ttt242242:20170624211123p:plain

うまく、パラメータを推定できているようです。

2次元データに対して

PRMLのサンプルデータを今回作成したライブラリ用に加工して、使用させていただきます。 ちなみにサンプルデータfaithful.jsongithubにおいてあります。 下のソースコードと同じディレクトリにサンプルデータを配置して、以下のソースコードを実行します。

require 't_learn'

em = TLearn::EM_Gaussian.new()
data_list = JSON.load(open("./faithful.json"))
history = em.fit(data_list, k_num=2) # k_num はガウス分布の個数

以下、実行結果

likelihood: -1264.5079209519638
likelihood: -1240.5772871778106
省略
likelihood: -1130.2639602913885
likelihood: -1130.263960190925
====================================
pi : [0.6441275620663266, 0.3558724379336733]
mu : [[4.28966107037274, 79.96810425509231], [2.0363874344782444, 54.47850611640881]]
conv : [[[0.1699695817230504, 0.9406238960300867], [0.9406238960300867, 36.04637543657748]], [[0.06916686263691188, 0.4351591734475339], [0.4351591734475339, 33.69722446174996]]]

ここでは、グラフをプロットしていませんが、 参考サイトと同じような値が得られています。(今回データを標準化していないため、対数尤度の値は異なります。)

まぁうまくいっているようです。

参考

今回、このライブラリを作成するのに以下のサイトを特に参考にしました。 ありがとうございました。

aidiary.hatenablog.com

CNNの伝搬と逆伝搬

※これから少しづつ改良していきます。

はじめに

少しCNNを触る機会があったので、

CNNにおいての伝搬、逆伝搬のところを勉強して自分用としてまとめた。

正直、数式はほとんど以下のサイトと同じである。

こちらの都合により $a$ を $y$ と変更しているなど、いくつか変更してある。

まず以下のサイトで理解してみることをおすすめする。

数式で書き下す Convolutional Neural Networks (CNN) - Yusuke Sugomori's Blog

上記のサイトの前半部分と同様に、

カーネル数が1の場合を今回は紹介する。

下記の2つの層の伝搬と逆伝搬についてのみ扱う。

  • Convolution Layer
  • MaxPooling Layer

Convolution Layer

まず、Convolution Layerの伝搬と逆伝搬について説明する。

伝搬

畳込みは以下の式で表現される。

\begin{equation} y_{ij} = \sum^{m–1}_{s=0}\sum^{n–1}_{t=0} w^{k}_{st} x_{(i+s)(j+t)} + b^k \end{equation}

やっていることは、以下の図がわかりやすい。

f:id:ttt242242:20170423213119p:plain:w200

f:id:ttt242242:20170423212953p:plain:w300

参考:http://hokuts.com/2016/12/13/cnn1/

逆伝搬

f:id:ttt242242:20170423212023j:plain:w300

カーネルの重み $w$ とバイアスである $b$ を更新する。

\begin{equation} w^{k}_{st} = w^{k}_{st} – \epsilon \frac{\partial E}{\partial w^{k}_{st}} \\ b^k = b^k – \epsilon \frac{\partial E}{\partial b^{k}} \end{equation}

カーネルの $w_{ij}$ は 畳み込んだ結果の二次元データ $y$ すべてに影響を与えているので、以下のように $y$ から勾配 $\frac{\partial E}{\partial w^{k}_{st}}$,$\frac{\partial E}{\partial b^{k}}$ を求める。

\begin{equation} \frac{\partial E}{\partial w^{k}_{st}} = \sum^{M–2(m/2)}_{i=0}\sum^{N–2(n/2)}_{j=0} \frac{\partial E}{\partial y^{k}_{ij}}\frac{\partial y^{k}_{ij}}{\partial w^{k}_{ij}} \\ = \sum^{M–2(m/2)}_{i=0}\sum^{N–2(n/2)}_{j=0} \frac{\partial E}{\partial y^{k}_{ij}} x_{(i+s)(j+t)} \\ \frac{\partial E}{\partial b^k} = \sum^{M–2(m/2)}_{i=0}\sum^{N–2(m/2)}_{j=0} \frac{\partial E}{\partial y^{k}_{ij}}\frac{\partial y^{k}_{ij}}{\partial b^{k}} \end{equation}

$\frac{\partial y^{k}_{ij}}{\partial b^{k}}$ は1より、

\begin{equation} = \sum^{M–2(m/2)}_{i=0}\sum^{N–2(n/2)}_{j=0} \frac{\partial E}{\partial y^{k}_{ij}} \end{equation}

さらにその後ろに伝搬させる必要がある場合

f:id:ttt242242:20170423212029j:plain:w300

$\frac{\partial E}{\partial x_{ij}}$は

\begin{equation} \frac{\partial E}{\partial x_{ij}} = \sum^{m–1}_{s=0}\sum^{n–1}_{t=0} \frac{\partial E}{\partial y^{k}_{(i–s)(j–t)}}\frac{\partial y^{k}_{(i–s)(j–t)}}{\partial x_{ij}} \\ = \sum^{m–1}_{s=0}\sum^{n–1}_{t=0} \frac{\partial E}{\partial y^{k}_{(i–s)(j–t)}}w^{(k)}_{st} \end{equation}

$i-s < 0$ もしくは $j-t < 0$ の場合は

\begin{equation} \frac{\partial E}{\partial y^{k}_{(i–s)(j–t)}} = 0 \end{equation}

と計算する。

MaxPooling Layer

f:id:ttt242242:20170423212037j:plain:w300

伝搬は単純に、二次元データのフィルタ適応部分で最も高い値を次の層に伝搬させる。

伝搬

\begin{equation} y_{ij} = max(x_{(li+s)(lj+t)})\ \ \ \ \ where \ \ (s \in l)\,(t \in l) \end{equation}

逆伝搬

逆伝搬は単純に、最も高い値だったユニットに逆伝搬させるだけ。

\begin{equation} \frac{\partial E}{\partial x_{(li+s)(lj+t)}} = \begin{cases} \frac{\partial E}{\partial y^{k}_{ij}} \ \ \ \ (y_{ij} = x_{(li+s)(lj+t)}) \\ 0 \ \ \ \ \ (otherwise) \end{cases} \end{equation}

Activation Layer

ここは参考サイトを見ればわかると思うので省略。

伝搬

\begin{equation} y_{ij} = ReLU(x_{ij}) = max(0,x_{ij}) \end{equation}

逆伝搬

\begin{equation} \frac{\partial E}{\partial x^{k}_{ij}} = \begin{cases} \frac{\partial E}{\partial x^{k}_{ij}} \ \ \ (y_{ij} \geq 0) \\ 0 \ \ \ \ \ (otherwise) \end{cases} \end{equation}

大脳皮質についてのメモ

大脳の外側2〜4ミリメートルの層があり、「大脳皮質」と呼ばれている。 この大脳皮質は約140億個のニューロンから構成されている。

f:id:ttt242242:20170408160120j:plain

参考: 無料イラスト 脳(png・CSeps)

各部位についてのまとめ

頭頂葉

  • 感覚情報の統合を行っている
  • 一部は視覚の処理に関わっている
  • 物体の位置や方向などを捉えるために重要な部位

前頭葉

  • 体の動きを司る「運動野」が存在し、歩行などの運動をコントロールしている
  • 理性的思考や感情のコントロールも行っている

側頭葉

  • 主に聴覚の処理に関わる
  • 音声や文字の意味を理解する働きを持つ

後頭葉

  • 目からの情報を制御する「視覚野」の大部分が位置している

大脳皮質ではないが重要な部位のメモ

海馬

イラストにはないが重要な部位なのでメモ。 - 記憶に重要な役割を果たす

嗅内皮質

イラストにはないが、嗅内皮質は海馬の前方に位置する - 互換から入力される信号のほとんどは、嗅内皮質を通して伝わる

参考文献

Newton(ニュートン) 2017年 03 月号 [雑誌]

Newton(ニュートン) 2017年 03 月号 [雑誌]

precisionとrecall

すぐ忘れるので、まとめておく

f:id:ttt242242:20170402170155j:plain:w400

{
  precision = \frac{TP}{TP+FP}
}

正と予測したデータのうち,実際に正であるものの割合

{
  precision = \frac{TP}{TP+FN}
}

実際に正であるもののうち,正であると予測されたものの割合

具体例

参考サイトの例を使わせていただきます。ありがとうございます。

検索システムを例に。

今、犬の画像を検索したいとする。

そして、システムAとシステムBの2つの検索システムがあり、それらを評価したい。

システムA

検索システムAは50件ヒットした。

犬の写真で間違えは一つもなかった。

取りこぼした犬の画像は70件あった。

\begin{equation} precision = \frac{50}{50 + 0} = 1.0 \end{equation}

\begin{equation} recall = \frac{50}{50 + 70} = 0.4166666666666667 \end{equation}

システムB

検索システムBは200件ヒット。

すべての犬の写真は抽出できた。

犬の写真で間違えは80件。

\begin{equation} precision = \frac{120}{120 + 80} = 0.6 \end{equation}

\begin{equation} recall = \frac{120}{120 + 0} = 1.0 \end{equation}

参考

F値 - 機械学習の「朱鷺の杜Wiki」

d.hatena.ne.jp

k-means

k-means概要

k-meansとは教師なし非階層クラスタリング手法の一つである。

下記の最適化問題を解くアルゴリズム

\begin{equation} * argmin_{C_1 ,\centerdot \centerdot \centerdot, C_k} \sum_{i=1}^{n} argmin_{j} ||v_i - C_j||^2 \end{equation}

$C_i$はクラスタ、 $v_j$はデータ

* は初期値に依存するからかな?

図で表したほうがわかりやすい。

まず、分類したいデータがある。

f:id:ttt242242:20170417084017j:plain:w200

この各点の座標情報からK_meansを使って分類すると、以下の図のようになる。ここではK=3とする。

f:id:ttt242242:20170417084020j:plain:w200

アルゴリズム

1. 適当にクラスタを割り振る

2. クラスタの中心 $C_i$ を計算する

  基本的には算術平均で求める。

\begin{equation} C_i = (\frac{v_{x1} + v_{x2} \centerdot \centerdot \centerdot v_{xn}}{n}, \frac{v_{y1} + v_{y2} \centerdot \centerdot \centerdot v_{yn}}{n}) \end{equation}

3. 各 $v_j$ と 各$C_i$ との距離を再計算し、 $v_j$ を一番近いクラスタに割り当てる

4. 1、2、3を $c_j$が属するクラスタの変化がなくなる、もしくは各 $c_j$ と $V_i$ との距離の変化がなくなるまで繰り返す。

プログラム

githubにあげた。 GitHub - Tcom242242/K_Means

今回は2次元のデータを200個作成し、分類した。

#!/usr/bin/ruby
# -*- encoding: utf-8 -*-

$LOAD_PATH.push(File::dirname($0)) ;
require "pry"
require "yaml"

#
# == k_means 
#
class K_Means

  attr_accessor :datas, :k, :c_list
  def initialize(datas: [[2, 3],[2, 8],[2, 3],[3, 5],[6, 3],[5, 3]], k: 2, dim: 2)
    @datas = datas
    sliced_datas = @datas.each_slice(k).to_a
    @k = k 
    @cluster_list = @k.times.map {|n| Cluster.new(n, nil,sliced_datas[n] , dim)}
    @dim = dim 
  end
  
  
  def fit()
    loop {
      @cluster_list.each{|c| c.reset_v_list()}
      @datas.each {|d|
        min_dist = 100000
        min_cluster_id = -1
        @cluster_list.each {|c|
          dist = calc_dist(d, c)
          if dist < min_dist 
            min_cluster_id = c.id 
            min_dist = dist
          end
        }
        @cluster_list[min_cluster_id].add_v(d)
      }

      @cluster_list.each{|c| c.calc_center()}
      break if !change_clusters_center?
    }

    formated_cluster_list = format_for_log()

    open("result.yaml", 'w') do |io|
      YAML.dump(formated_cluster_list, io)
    end
  end

  def format_for_log()
    result = @cluster_list.map {|c| c.format_hash()}
  end

  def calc_dist(v, cluster)
    dist_sum = 0.0
    v.each_with_index { |v_x, i|
      dist_sum += (cluster.vec[i] - v_x).abs
    } 
    return dist_sum/v.size
  end
 
  def change_clusters_center?()
    @cluster_list.each {|c|
      return true if(c.change_center?) 
    } 
    return false
  end 

  #
  # cluster 
  # cluster has id, vec, and v_list
  #
  class Cluster
    attr_accessor :id, :vec, :v_list, :last_vec

    def initialize(id, vec=nil, v_list=nil, dim=1)
      @id = id
      @v_list= v_list
      @vec = dim.times.map{0.0} if vec == nil
      @dim = dim
      calc_center()
    end

    def calc_center() 
      @last_vec = Marshal.load(Marshal.dump(@vec))
      vec_sum = Array.new
      @v_list.each { |v|
        v.each_with_index { |v_x, i| 
          vec_sum[i] ||= 0.0
          vec_sum[i] += v_x 
        } 
      }
      vec_sum.each_with_index { |new_vec, i| @vec[i] = new_vec/@v_list.size.to_f } 
    end 

    def add_v(v)
      @v_list.push(v)
    end

    def reset_v_list()
      @v_list = []
    end

    def change_center?
      @dim.times { |i|
        return true if @vec[i] != @last_vec[i]
      }
      return false
    end

    def format_hash()
      cluster_hash = {}
      cluster_hash[:id] = @id
      cluster_hash[:vec] = @vec
      cluster_hash[:v_list] = @v_list
      return cluster_hash
    end
  end
end

#
# for experiment
#
if($0 == __FILE__) then
  dim, data_num = 2, 200
  datas = data_num.times.map { |t|
    data = dim.times.map { rand()*10 }
  }
  # datas=[[10, 4],[2, 8],[7, 3],[3, 5],[6, 3],[5, 3],[2, 4],[2, 3], [1, 4], [1, 3], [6, 6], [10, 1],[1, 1], [8, 1], [1, 6], [10, 6]]
  # datas=[[2, 3],[2, 8],[2, 3],[3, 5],[6, 3],[5, 3]]
  k_means = K_Means.new(datas: datas, k: 3, dim: dim) 
  puts "calculating..."
  k_means.fit() 
  puts "finish"
end

結果をプロットしてみると、

f:id:ttt242242:20170417085521p:plain:w300

参考

k平均法 - Wikipedia

ITエンジニアのための機械学習理論入門

ITエンジニアのための機械学習理論入門