2016-06-24

rubyで単純パーセプトロン

ruby

目的

機械学習を勉強するにあたって単純パーセプトロンから入るのは通説らしいので、僕も単純パーセプトロンから機械学習を入門します。
理論を勉強しつつ、実際に実装してみることで理解を深めることが目的です。

注意

学習中であるため、この記事に書かれている内容の正しさは保証しません。
間違っている箇所を見つけたら指摘していただけると幸いです。

単純パーセプトロンとは

単純パーセプトロンは複数の入力を受け取り、値が何らかの値に達すると発火する識別器です

識別関数

識別関数とは何らかのデータを特定のクラスタに識別する関数です。

例えば、次のようなデータを考えます。
f:id:ogidow:20160621091021p:plain

青色のデータと赤色のデータの間に直線を引くことでデータを識別できそうです。
実際に直線を引いてみます。
f:id:ogidow:20160621091459p:plain

直線より上側にあるデータが青色のデータ、下側にあるデータが赤色のデータと識別することができました。

これを式で表してみます。

直線を式で表すと
${ \displaystyle w_0 + x_1 \cdot w_1 + x_2 \cdot w_2 = 0 }$
になります。

直線より上側は青色のデータ、下側は赤色のデータなので
青色のデータは
${ \displaystyle w_0 + x_1 \cdot w_1 + x_2 \cdot w_2 > 0 }$
となり、赤色のデータは
${ \displaystyle w_0 + x_1 \cdot w_1 + x_2 \cdot w_2 < 0 }$
となります。

直線の傾きや切片を決定する
${ \displaystyle w_0, w_1, w_2 }$
が決まれば直線が一意に決まります。
今回はこの直線が識別関数となります。

単純パーセプトロンではこの
${ \displaystyle w_0, w_1, w_2 }$
を学習によって求めます。

単純パーセプトロンによる学習

単純パーセプトロンについてのおさらいです。
単純パーセプトロンは複数の入力を受け取り、値が何らかの値に達すると発火する識別器です。

雑に図で表すとこんな感じです。
f:id:ogidow:20160621094328p:plain

この図に先ほどの識別関数を当てはめてみます。

f:id:ogidow:20160624184143p:plain

この図を式で表します。
${ \displaystyle u = \textbf{x} \cdot \textbf{w} }$

${\displaystyle \textbf{w} = \left( \begin{array}{c} w_0 \\ w_1 \\ w_2 \end{array} \right) }$ を重みと呼びます。

次に実際に学習方法を考えます。

学習の方法は

重み( ${w_0, w_1, w_2}$ )にランダムな値を設定する
学習データをパーセプトロンに投げ、出力が正しいか比較する
出力が間違っていれば、重みを更新する
重みの更新が収束するまで2〜3を繰り返す

重みの更新

学習データを読み込み出力結果が間違っていれば重みの更新を行います。
重みの更新は、正しい結果を出しそうな方向に少しづつずらしていきます。
この「重みを正しそうな方向に少しづつずらす」ために誤差関数 ${E}$ というものを定義します。

誤差関数とは、「予測した結果が実際の結果とどのくらいずれているか」を出力する関数です。
誤差関数はずれが大きいほど大きな値を返すのであればどのような関数でも大丈夫ですが、
単純パーセプトロンの場合、誤差関数は
${E=max(0, -t\textbf{w}\textbf{x})}$
と定義する場合が多いようです。

※ ${t}$ はデータの正解ラベルで正解の場合 ${1}$ を不正解の場合 ${-1}$ となります。

この誤差関数をグラフで表してみます。誤差関数は「正解とのズレが大きいほど大きな値を返す」という特性から、
2次関数のようなグラフを描きます。
f:id:ogidow:20160622092224p:plain

重みの更新は最終的にこのグラフでいう極小値を目指します。

では、どうすれば極小値に近づくように重みを更新でききるのでしょうか。
傾きを見て、傾きが負の場合正の方向へ、傾きが正の場合負の方向へ重みをずらしていけば、
重みを極小値へ近づけていけそうです。

これを式で表してみます。
${w_i = w_i - \frac{\partial E}{\partial w_i}}$

このままだと、 ${\frac{\partial E}{\partial w_i}}$ の値が大きくなりすぎるので、調整するために
学習率 ${p}$ をかけてあげます。
${w_i = w_i -p\frac{\partial E}{\partial w_i}}$

この式を展開していきます。
ここで、 ${E=0}$ の場合は更新自体を行わないので、 ${E=-t\textbf{w}\textbf{x}}$ についてのみ考えます。

${ w_i - \frac{\partial E}{\partial w_i} \\ = w_i - \frac{\partial (-tw_ix_i)}{\partial w_i} \\ = w_i + tx_i }$

よって更新式は
${ w_i = w_i + tx_i}$
となります。

rubyで実装

理解を深めるためにrubyで実装しました。
グラフの描画はgnuplotを使っています。

以下コードと実行結果となります。
GitHub - ogidow/Simple-perceptron-ruby

require "gnuplot"
# w1 + w2x + w3y = 0

class Perceptron
  def initialize(learning_rate, num_data)
    @w_vec = {}
    @learning_rate = learning_rate
    @num_data = num_data
  end

  def init_w_vec
    @num_data.times do
      @w_vec = {w1: rand(-10..10), w2: rand(-10..10), w3: rand(-10..10)}
    end
  end

  def predict (data)
    #p w_vec
    @w_vec[:w1] * 1 + @w_vec[:w2] * data[:x1] + @w_vec[:w3] * data[:x2]
  end

  def update (data)
    @w_vec = {w1: @w_vec[:w1] + @learning_rate * 1 * data[:label], w2: @w_vec[:w2] + @learning_rate * data[:x2] * data[:label], w3: @w_vec[:w3] + @learning_rate * data[:x1] * data[:label]}
  end

  def train (datas)
    update_count = 0
    datas.each do |data|
      result = predict(data)
      if result * data[:label] < 0
        update(data)
        update_count += 1
      end
    end
    update_count
  end

  def draw_graph(x1, y1, x2, y2, title)
    Gnuplot.open do |gp|
      Gnuplot::Plot.new(gp) do |plot|
        plot.xlabel "x"
        plot.ylabel "y"
        plot.title title

        plot.data << Gnuplot::DataSet.new([x1, y1]) do |ds|
          ds.with = "points"
          ds.notitle
        end

        plot.data << Gnuplot::DataSet.new([x2, y2]) do |ds|
          ds.with = "lines"
          ds.notitle
        end
      end
    end
  end

  def run
    #学習用データ作成
    init_w_vec
    datas = []
    @num_data.times do
      if rand > 0.5
        datas.push({x1: rand(1..100) * -1, x2: rand(1..100) * 1, label: 1})
      else
        datas.push({x1: rand(1..100) * 1, x2: rand(1..100) * -1, label: -1})
      end
    end

    ##学習開始
    ##収束条件：重みの更新がなくなったら
    update_count = 0
    5000.times do
      update_count = train datas
      break if update_count == 0
    end

    # w1 + x * w2 + y * w3  = 0
    # 分離直線の傾きと切片を求める
    slope = -1 * @w_vec[:w2] / @w_vec[:w3]
    interecept = -1 * @w_vec[:w1] / @w_vec[:w3]
    #学習した分離直線を出力
    puts "y = #{slope}x + #{-1 * interecept}"

    # 学習した分離直線を描画
    x =[]
    y =[]

    (-100..100).each do |i|
      x.push i
      y.push i * slope + interecept
    end

    draw_graph(datas.map{|v| v[:x1] }, datas.map{|v| v[:x2]}, x,  y, "perceptron")
  end
end

perceptron = Perceptron.new(0.2, 100)
perceptron.run

f:id:ogidow:20160620174831p:plain
見事に分離直線を引くことができました！！

感想

機械学習を勉強する入り口には立つことができたかなと思います。
これを機に機械学習と仲良くなっていきたいです。

2016-06-14

アンテナサイト作った話

プログラミング ruby

同期のブログのアンテナサイト作りました

http://six-antena.herokuapp.com/

f:id:ogidow:20160613143515j:plain

作った経緯
飲んだ勢いで、同期の一人に「同期ブログのアンテナサイト作るぜ！！！！！１」
と宣言したのがはじまりです。

環境
言語：ruby
フレームワーク：ruby on rails
インフラ：heroku

機能
データベースに登録されている同期のブログの更新情報がトップページに表示されます。
表示される内容は、各記事のタイトル、og:imageに指定されている画像とdescriptionと呼ばれる記事の概要が表示されます。
また、descriptionのない写真ブログからも記事を取得しているので、その場合はタイトルと画像のみが表示されます。

困っていること
アンテナサイトなので定期的にデータベースを更新しなければなりません。
herokuでタスクの定期実行を行う場合、「heroku Scheduler」というサービスを利用することで
実現できます。「heroku Scheduler」はプロセスの利用時間が750時間/1ヶ月まで無料で利用することができますが、
750時間を超えると課金対象になるので、「heroku Scheduler」を利用するにはクレジットカードの登録が必須となります。
しかし、僕はクレジットカードを持っていないので「heroku Scheduler」を利用することができません。
そのため、手動でデータベースの更新をやってます。
何か良い方法があれば教えてください。

これから
機能の追加・修正と見た目を良い感じにしたいです。

2016-04-28

GMOペパボに入社しました

ペパボ新卒6期生として入社したのおぎどーです。そろそろ入社して1ヶ月がたち落ち着いてきたので入社エントリというものを書いてみます

だれ

沖縄高専の専攻科で情報工学を学んだ22歳の若者ですドローン飛ばしたりしてました

ペパボとは

ペパボは「もっと面白くできる」を企業理念としている本当に面白い会社です。以下の動画見るとペパボの面白さを何となく理解していただけるかと思います
新卒採用2017 GMOペパボ会社説明会

なにやってるの

入社式を終え、すぐにグループ全体研修に入りました。そこでは、各グループの社長さんのお話やマナー研修、宿泊研修などを受けました。その後、ペパボの研修に入り各部署のオリエンテーションを受け、現在はポートフォリオ研修で自分のこれまでをふりかえっている最中です

これから

5月は福岡研修でそれが終わると技術研修が始まります。研修はまだまだこれからなので、一人前のエンジニアになれるよう頑張って行きたいなという感じです。また、研修を受けて技術の知識だけじゃなくデレクションやデザインも学びたくなったので、先輩や同期に助けもらってどんどん学んでいくぞ!!!!11という気持ちですので、各位よろしくお願いします

終わりに

ペパボは研修も充実してて、エンジニアのスーパープレイヤーも多く在籍してます！！ 17年卒の採用も始まってるみたいなんで興味ある方は是非！！！
新卒採用2017-GMOペパボ株式会社

2016-03-16

visual studioで動くbebop drone用の制御ライブラリを作った

c++ OpenCV bebop drone プログラミング

必要になったので、bebop drone用の制御ライブラリ「CV Bebop」を作成しました。

github.com

環境

visual studio 2012
言語：visual c++ 2012
画像処理ライブラリ：OpenCV3.1

使い方

必要なライブラリはすべて入っているので、visual studioのソリューションファイルを開き、ターゲットをwin64にし、Releaseモードでビルドするだけです。

ライセンス周りがよく分かっていないので、マズイところがあれば連絡していただければ幸いです。

2015-11-24

Q学習で迷路を学習

ruby 強化学習プログラミング

昔、授業でQ学習を習ったの思い出したのでQ学習使って迷路学習させるスクリプトをrubyで書いた

github.com

Q学習とは

Q学習は機械学習手法の方策オフ型TD学習の一つである。概念自体は古くから存在するが、Q学習（Q-learning）という名前で今日の手法がまとめられたのは、1989年のクリス・ワトキンズ（Chris Watkins）の論文に端を発する。
Q学習は有限マルコフ決定過程において全ての状態が十分にサンプリングできるようなエピソードを無限回試行した場合、最適な評価値に収束することが理論的に証明されている。実際の問題に対してこの条件を満たすことは困難ではあるが、この証明はQ学習の有効性を示す要素の一つとして挙げられる。
Q学習 - Wikipedia

なんか難しい感じだけど、マルコフ条件の元で状態遷移する場合(ある状態は直前の状態からのみ影響を受ける場合)、無限回試行すると、最適な行動を学習出来るってことらしい。たぶん

Q値の更新

Q学習のきもはQ値の更新で
f:id:ogidow:20151124001819p:plain
でQ値をどんどん更新していく
Q学習で迷路を学習するときのイメージは複数回試行することで報酬(ゴール)がどんどん伝搬していって各状態におけるQ値が決まっていく感じ

実験

こんな感じの迷路を学習させてみた

#####################
#S   0   0    0    0#
#0 -10   0    0    0#
#0   0 -10    0  -10#
#0 -10   0    0    0#
#0   0   0  -10   50#
#####################

Sが初期位置で右下の50がゴールになっている

この迷路を5000ステップ学習して、学習したQ値を使って迷路を解いた
学習時の行動選択は、ある小さな確率εでランダムに選択し、それ以外では Q値の最大の行動を選択するε-グリーディ法を利用した。

学習したQ値を利用して迷路を解いたところ、以下のような結果になった

x: 0 y: 0
   @   0   0   0   0
   0 -10   0   0   0
   0   0 -10   0 -10
   0 -10   0   0   0
   0   0   0 -10  50

x: 1 y: 0
   0   @   0   0   0
   0 -10   0   0   0
   0   0 -10   0 -10
   0 -10   0   0   0
   0   0   0 -10  50

x: 2 y: 0
   0   0   @   0   0
   0 -10   0   0   0
   0   0 -10   0 -10
   0 -10   0   0   0
   0   0   0 -10  50

x: 2 y: 1
   0   0   0   0   0
   0 -10   @   0   0
   0   0 -10   0 -10
   0 -10   0   0   0
   0   0   0 -10  50

x: 3 y: 1
   0   0   0   0   0
   0 -10   0   @   0
   0   0 -10   0 -10
   0 -10   0   0   0
   0   0   0 -10  50

x: 3 y: 2
   0   0   0   0   0
   0 -10   0   0   0
   0   0 -10   @ -10
   0 -10   0   0   0
   0   0   0 -10  50

x: 3 y: 3
   0   0   0   0   0
   0 -10   0   0   0
   0   0 -10   0 -10
   0 -10   0   @   0
   0   0   0 -10  50

x: 4 y: 3
   0   0   0   0   0
   0 -10   0   0   0
   0   0 -10   0 -10
   0 -10   0   0   @
   0   0   0 -10  50

ちゃんと解けてるっぽい

結構楽しかったので、これを気に機械学習とかちゃんと勉強してみたい

参考

Q学習 - Wikipedia
Q学習-最良経路を学習するスクリプト書いた (powered by Python) - Stargazing && Temporary Escapism ~インプット馬鹿への道~
Q-Learning

2015-10-30

rubyでRANSAC

ruby プログラミング

研究で必要になったから調べてみた

観測したデータから最小二乗法などでモデルを推定する際に、観測したデータに外れ値が混じっていた場合、推定したモデルは外れ値に引っ張られてしまいます。そこで、RANSACアルゴリズムを利用することで、外れ値を無視したモデルの推定を行うことが出来ます

RANSACアルゴリズム

1.観測データ群からランダムに幾つかのデータを取り出す
2.取り出したデータを用いてモデルを推定
3.推定したモデルに対して、観測データ群を適用し、モデルを評価する
4.1～3を複数回行い、一番評価が高いモデルを採用

意外とシンプルなアルゴリズムです。

実験

今回は、直線のモデルを最小二乗法で推定します。
直線のモデルなんで、
${Y = aX + b}$
のaとbの部分を推定します。

今回は正解のモデルを
${Y = X}$
っぽい直線としました。
正解データは

(1- rand() / 10) * x

また外れ値は

rand(0.0..5.0) * x

として生成しました。

ちなみにxは1から100までの整数です。
グラフの描画はgnuplotなるライブラリを使いました。

まずは外れ値なしの最小二乗法から

f:id:ogidow:20151030230915j:plain

なかなかよい感じ

続いて、外れ値ありの最小二乗法

f:id:ogidow:20151030231407j:plain

めっちゃ外れ値に引っ張られてます。

最後にRANSAC使った場合です。

f:id:ogidow:20151030231604j:plain

きれいに外れ値を無視してくれました。

RANSACは簡単に実装できて、強力なんですが、
複数回、モデルの推定を行って、それを更に観測データ群に適応させるので、
計算量がめっちゃ大きい感じがします。

実際にRANSACを使う場合には工夫が必要かもしれません

ちなみに今回書いたコードはこんな感じです。

2015-10-15

c++でイベント駆動っぽくTCPを書いた

プログラミング c++

github.com

思いつきでc++でイベント駆動っぽいTCPのクラス書いてみた

これでTCPのサーバーとクライアント両方ともイベント駆動っぽくかける

試しにエコーサーバ

サーバ

#include <iostream>
#include "TCPEventServer.h"

int main(void)
{

	eventTCP server(5432);

	server.on("connect", [](Socket *sock){
		std::cout << "connect" << std::endl;
		sock->on("echo", [sock](std::string data){
			std::cout << data << std::endl;
			sock->emit("echo", data);
		});

		sock->on("disconnect", [sock](std::string data){
			std::cout << "disconnect" << std::endl;
			sock->close();
		});
	});

	server.listen(5);
	
	return 0;
}

クライアント

#include <iostream>
#include "TCPEventClient.h"

int main(void)
{
	TCPEventClient client;

	client.connect("127.0.0.1", 5432);

	client.on("connect", [](Socket *sock){
		std::cout << "connect" << std::endl;
		sock->on("echo", [sock](std::string data){
			std::cout << data << std::endl;
		});

		sock->on("disconnect", [sock](std::string data){
			sock->close();
		});

		sock->emit("echo", "echo server");
	});

	return 0;
}

c++毛嫌いしてたけど、c++11からは結構よさげ