Masaponto's Blog

お勉強メモ

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

機械学習

こんにちは。
Aizu Advent Calendar 2014 6日目の記事です。 (意味不明だったので修正しました)

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

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

機械学習アルゴリズムである単純パーセプトロンを実装したので、それについて書きます。
もし間違いがあれば教えてください。

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

単純パーセプトロンは、2クラス分類のパターン認識に使うアルゴリズムです。

パターン認識についてはこちら。
パターン認識 - Wikipedia
Pattern Recognition

単純パーセプトロンを例で簡単に説明します。

キノコを毒キノコと、そうでないキノコの2クラスに分けたいとします。
たくさんあるキノコのうち、ある12個に関しては毒の有無がわかっているとします。
そこで、その12個のキノコの長さと太さを測ってグラフにプロットします。 次のようになりました。

f:id:masaponto:20141206004522p:plain

毒々しい青色の点が毒が入ってるキノコ、赤い点がそうでないキノコです。
ここで、毒と無毒の2クラスに分けるんだから、こんな感じに直線を引きたくなりますよね。

f:id:masaponto:20141206004721p:plain

この直線を使えば、残りのキノコも分類できそうです。

単純パーセプトロンは、この直線を機械的に求める方法です。

機械学習の分野では、キノコの長さと太さをベクトルで表したものを特徴ベクトル、特に毒の有無が既知なキノコのベクトルを学習データ、 緑の直線を識別境界と言います。

アルゴリズム

以下のようなアルゴリズムで識別境界を決めます

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

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

はじめてのパターン認識

はじめてのパターン認識

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

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

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