1. 識別境界をきめる関数(識別関数)をランダムに決める。  
この関数は特徴ベクトルを入力すると、それが所属するクラスを出力します。
2. この関数に学習データを1つ入力して出力を見る。  
3. 実際のクラスと異なるクラスが出力された場合、関数を修正する。  
正しかった場合はそのまま。  
3. すべての学習データにおいて (2)(3) をやる。

まずは識別関数について説明します。

識別関数

単純パーセプトロンでは先ほどの例の識別境界を次の識別関数で求めます。

${ \displaystyle \ f( g(\boldsymbol{x}) ) = f( \sum_{i=0}^{N} w_i x_i + v ) = f( \boldsymbol{w}^t\boldsymbol{x} + v )\ }$

この関数は入力に特徴ベクトルを取り、その特徴ベクトルを持つキノコがどのクラスに属するかを返します。

xは入力の学習データです。

wは重みベクトルです。
ランダムに決められる要素をもつベクトルで、次元数は特徴ベクトルと同じです。
識別関数はこのベクトルに依存します。

vはバイアス項です。ランダムなスカラー値です。

fは活性関数とよばれるものです。ここでは単位ステップ関数です。*1
単位ステップ関数は入力が負だったら0を、負で無かったら1を返します。
これにより、出力は0か1になり、2クラスに分けられる訳です。
今回の場合、g(x) < 0 なら0、g(x) ≧ 0なら1が出力になります。

この式を少し変形してみましょう。
以下の例のように、特徴ベクトルに要素1を追加します。

(長さ, 太さ) -> (1, 長さ, 太さ)

そして、ベクトルwもスカラーvも乱数なので、vをベクトルwの第一要素として追加します。

(w0, w1) -> (v, w0, w1)

すると以下のように、変形できます。

${ \displaystyle \ f( g(\boldsymbol{x}) ) = f( \sum_{i=0}^{N} w_i x_i ) = f( \boldsymbol{w}^t\boldsymbol{x})\ }$

内積のみの形で表せたので、実装が楽になりした。

関数の修正

識別関数は重みベクトルに依存しているので、実際は重みベクトルを修正していくことになります。
重みベクトルの修正には以下の式を使います。

${ \displaystyle \ \boldsymbol{w'} = \boldsymbol{w} + \rho ( d - f( g(\boldsymbol{x}) ) ) \boldsymbol{x} }$

wは修正前の重みベクトル、w'は修正後の重みベクトルです。

xは入力の学習データです。

f(g(x))は先ほどの識別関数です。

ρは学習率と呼ばれるスカラー値で、主に0.5に設定されます。

dは学習データxの属すべきクラスです。

この式でdとf(g(x))の値が同じだったら、つまり識別関数が正しく識別できていたら、二項目の値が0になり、重みの更新が行われないことがわかります。上のように重みを更新していくことを"学習する"と言います。

識別関数とその修正方法を踏まえるとアルゴリズムは次のようになります。

(1). 識別関数の重みベクトルをランダムに定義する。
(2). 学習データから一つ選び、識別関数に適用する。
(3). 識別関数の返り値を重み修正法で更新する。
(4). すべての教師データにおいて、正しい値を返すまで(2),(3)を繰り返す。

実装

今回はHaskellとPython3で実装してみました。
環境はArch Linux(x64)、ghc7.10.1、python3.4 です。

コードはこちら。

Haskell
SimplePerceptron/SP.hs at master · masaponto/SimplePerceptron · GitHub

Python3

simple_perceptron.py · GitHub

実装の確認してみます。主に論理演算のAND、ORがよく使われるみたいです。

AND演算の真偽値表はこれです。

f:id:masaponto:20141206023932p:plain

ORはこれです。

f:id:masaponto:20141206024257p:plain

つまり、x1,x2を特徴ベクトルとして、演算結果を属してほしいクラスに対応させるわけです。

python3での結果以下の通り、
学習率はいずれも0.5です。

AND
f:id:masaponto:20150813152218p:plain

OR
f:id:masaponto:20150813152227p:plain

やったー。識別できてます。
いずれのグラフも、黒点がクラス0, 赤点がクラス1です。
最終的な識別関数は2変数関数(z = ax + by + c)なので、z = 0を入れてyについて解いた式を使うと二次元にプロットできます。
※Haskellの場合も同じような結果になるぞ！

おわり

本当は多層パーセプトロンの話もしたかったんですが、書いたコードが怪しいことと、解説するほど勉強できてないので、今回はしません。

つぎは
@Mopp_jp
もぷろぐ: 自作OSでのプロセス実装について (2) ~初めてのユーザプロセス~

参考資料

第3回単純パーセプトロン · levelfour/machine-learning-2014 Wiki · GitHub

テキストマイニングのための機械学習超入門二夜目パーセプトロン - あんちべ！

はじめてのパターン認識

作者: 平井有三
出版社/メーカー: 森北出版
発売日: 2012/07/31
メディア: ?行本-平装
購入: 1人クリック: 7回
この商品を含むブログ (3件) を見る

フリーソフトでつくる音声認識システム?パターン認識・機械学習の初歩から対話システムまで?

作者: 荒木雅弘
出版社/メーカー: 森北出版
発売日: 2007/10/01
メディア: 単行本（ソフトカバー）
購入: 45人クリック: 519回
この商品を含むブログ (39件) を見る

*1:他にも区分線形関数、シグモイド関数が用いられます。

2014-08-04

Haskell, Fay で数式パーサを作った

Haskell

題名通り数式パーサを作って見ました。
これです。

ExpressionParser
masaponto/ExpressionParser · GitHub

Fayとは

fayはHaskellのサブセットです。
Haskellっぽいコードをjavascriptに変換してくれます。

公式
Home · faylang/fay Wiki · GitHub

また、以下のページで紹介されています。

さらば愛しき JavaScript —— 愛と欲望の果てに Haskell は fay と出逢う。 - これは圏です

Introduction to Fay - 純粋関数空間

パーサ

「プログラミングHaskell」という本で数式パーサについて書かれていたので、それを参考に実装しました。

再帰下降構文解析です。
しかし数式のような左結合を含む文法の場合、再帰下降構文解析では一つ問題があります。
単純に左結合させようと

expr ::= expr '+' term | expr '-' term | term

という実装にすると、無限再起になってしまうのです。左再起というそうです。

参考
chainl と左再帰 - あどけない話
 左再帰 - Wikipedia
pasberth.com - このページは表示できません。

これを解決するために、

expr ::= term '+' term | term '-' term | term

にして " '+' term " の部分を可能な限り繰り返してパースし、リストにtermの結果の値を保存し、その後でリストの要素の和を求める形にしました。　

例えば、1-2+3*2-4 の場合、まず、1, '-' 2, '+' 6, '-' 4 とパースされます。そして [1,-2,6,-4] というリストを作ります。
で、このリストの要素を左から足し算していく、って感じです。

結局、パーサのBNF(?)はこれ。

expr ::= term '+' term | term '+' term '+' term | .... |  term '-' term | term '-' term '-' term | .... | term
term ::= pow '*' pow | pow '*' pow '*' pow | ... | pow '/' pow | pow '/' pow '/' pow | .... | pow
pow ::= factorialP '^' pow | factorialP
factorialP ::=  factor '!' | factor
factor ::= '(' expr ')' | number
number ::= '-' decimal | decimal
decimal ::= space nat space
nat ::= digit '.' digit | digit
digit ::= 0 | 1 | 2 | 3 | ...

space は空白をパースします。
四則演算、カッコ、冪乗、階乗をパースできます。
いろいろ怪しい。

作った感想(?)

github-pages 便利
ブラウザで動くの楽しい
fayはサブセットのため制限があって少し大変
fayすごい
Haskellすごい

参考書籍

プログラミングHaskell

作者: Graham Hutton,山本和彦
出版社/メーカー: オーム社
発売日: 2009/11/11
メディア: 単行本（ソフトカバー）
購入: 14人クリック: 503回
この商品を含むブログ (117件) を見る

すごいHaskellたのしく学ぼう!

作者: Miran Lipovača,田中英行,村主崇行
出版社/メーカー: オーム社
発売日: 2012/05/23
メディア: 単行本（ソフトカバー）
購入: 25人クリック: 580回
この商品を含むブログ (67件) を見る

追記

ガンマ関数の実装はこちらを参考にしました。
【GO FOR IT】実数の階乗 (i)(ii)(iii) - MIND_THE_GAP

2014-05-28

Androidのゲームアプリを作った

Android

Androidアプリを作りました。簡単なシューティングゲームです。
ある程度遊べるようになったのでgithubにあげました。

PON-SHOOTING

野良アプリとしてソースコードと共に公開しています。

インストール方法はこちらを参照してください。
apkファイルも上記のリポジトリにあります。

任意の場所をタッチしてスライドさせることで自機が動きます。
上から降ってくる敵に弾を当てて倒して下さい。1体倒すごとにスコアが1あがります。
敵や敵の弾に当たるとゲームオーバーです。

実機 LG optimus bright、Genymotion での nexsus7 などでしか動作確認を行っていないので、問題があるかもしれません。
何かあればコメントよろしくお願いします。

Masaponto's Blog

お勉強メモ

単純パーセプトロンを実装してみた

単純パーセプトロン 2クラス分類について

アルゴリズム