danglingfarpointer's memoization

仕事周りでの気付き、メモ、愚痴などを書いていきます。

マッチ箱の脳(AI) -- パーセプトロン

人工知能 JavaScript

はじめに

前回の「マッチ箱の脳(AI)」のネタで、今回は「パーセプトロン」を組んでみることにしました。

パーセプトロンとは

機械学習のアルゴリズムの1つで、ラベル付けされた多次元データを、ラベルごとに分類する境界を求めるアルゴリズムです。

以降は簡単のため、2次元データに対して2値のラベル(-1または+1)が付けられるケースに限定します。

例えば:

label x y
+1 -2 1
+1 -1 4
+1 1 3
+1 3 3
-1 -3 -1
-1 0 -1
-1 2 1
-1 3 2

というデータに対しては、y = 0.5x + 1 が+1のデータと-1のデータを分類する境界となります。このような識別境界を求める手法の1つが、パーセプトロンです。

f:id:danglingfarpointer:20140907010057p:plain

パーセプトロンのアルゴリズム

  1. \(ax + by + c = 0\) という直線を考える。\(a, b, c\)はランダムに初期化
  2. \(a, b, c\)が更新されなくなるまで、以下を行う:
    1. 各訓練データ\((x_i, y_i)\)について、
      1. \(k = ax_i + by_i + c \)を求める
      2. \(k\)が\(+\)だが訓練データのラベルが\(-\)である場合、\(a = a-x_i, b = b-y_i, c -= c-1\)と更新
      3. \(k\)が\(-\)だが訓練データのラベルが\(+\)である場合、\(a = a+x_i, b = b+y_i, c = c+1\)と更新

上記が停止した時、\(ax + by + c = 0\)が識別境界となります。非常にシンプルです。なぜこの更新方法で良いのかについては、ちゃんとした理論があるようですが、正確に理解しているか怪しいので飛ばします- -;)

2次元データが「線形識別可能」、つまり直線により識別できるならば、上記のアルゴリズムは必ず停止し、答えが求まります。

例

上述した例に対してパーセプトロンを適用した結果です。5回の更新で識別境界を求めることが出来ました。ちなみにその境界は、 y = 0.581*x + 0.878.最終的な解に至る過程(cycle 0 -- cycle 4)も記しています（色で区別してるだけなので見難いかも）

f:id:danglingfarpointer:20140907010111p:plain

補足

サンプルのJavaScriptソースコード(Node.js). https://gist.github.com/danglingfarpointer/2fa56b9359ec2e260f6b

マッチ箱の脳(AI) -- 遺伝的アルゴリズム

人工知能 JavaScript

はじめに

「マッチ箱の脳(AI)―使える人工知能のお話」という人工知能系のアルゴリズムを分かりやすく解説したKindle本を買いました。その本に触発され、最近仕事で触っているNode.jsのお勉強も兼ねて、「遺伝的アルゴリズム」を題材にプログラムを組んでみることにしました。

マッチ箱の脳(AI)―使える人工知能のお話

マッチ箱の脳(AI)―使える人工知能のお話

遺伝的アルゴリズム

ざっくり説明すると、以下の手続きです。

  • 解こうとしている問題の解の候補を「遺伝子」として表現した上で、
  • 優秀な遺伝子（適応度の高い遺伝子; 優れた解候補）が生き残るようにしつつ、
  • 遺伝子間の交叉や突然変異を通して、世代（遺伝子の集まり）を反復的に進化させていき、
  • 一定の世代数だけ反復した後、もっとも優れた遺伝子を解とする

まさに遺伝子の自然淘汰や突然変異、遺伝子間の交叉をモチーフにしたアプローチです。

適用先

「マッチ箱の脳(AI)」と同様に、遺伝的アルゴリズムをナップサック問題に適用します。ナップサック問題とは、以下のような問題です。

前提:

  • 値段と重さが決まっているn個の品物がある
  • 所定の重さまでしか品物を入れられないナップサックがある

問:

  • ナップサックに入る範囲で、最も値段が高くなる品物の組み合わせは？

例えば、以下の表のような6個の品物をできるだけ値段が高くなるようにナップサックに入れたい。ただし、ナップサックには100KGしかはいらない。どのような品物の組み合わせがベストか?

id 値段 重さ
1 4500円 40KG
2 6000円 56KG
3 4000円 34KG
4 3000円 28KG
5 3000円 36KG
6 6900円 72KG

この答えは、1と2の組み合わせです。10,500円で96KG < 100KGとなります。

ナップサック問題はNP困難であることが知られています。つまり、品物数nが大きい場合、厳密な解を求めようとすると、現実的な時間では終わりません。

しかし、（厳密な解ではなく）最適に近い解であれば、実際は効率的に求められるようです。そうなってくると、あえて遺伝的アルゴリズムの題材にするのはどうかと思いますが、ここはあくまで本の設定に従います。

遺伝子よる解候補の表現

まずはナップサック問題の解候補をどのように「遺伝子」として表現するか。もちろん遺伝子といっても要は単なるオブジェクト表現です。

n個の品物がある場合、解候補は、それぞれの品物の取捨を表すn個の真偽値で表現できます。例えば上述した例であれば、6個の品物から3番目と5番目を選択した解候補は、以下のような遺伝子で表現できます。

[false, false, true, false, true, false]

適応度の定義

「適応度」とは、遺伝子が解候補としてどの程度優れているかを表す値です。大きい値ほど優れているとします。

ナップサック問題の設定を考えると、選択した品物の値段の合計を適応度と定義するのが適当です。ただし、重さの和がナップサックの容量を超えた場合、解とはなりえないので、適応度は0とします。

例えば上述した例で、3番目と5番目を選択した解候補の適応度は、ナップサックの容量を超えていないので(34KG + 36KG < 100KG), 7000(4000円 + 3000円)となります。また、2番目と3番目と4番目を選択した解候補については、ナップサックの容量を超えてしまったので(56KG + 34KG + 28KG < 118KG), 適応度は0となります。

遺伝子の交叉

新しい遺伝子を生成する1つの方法が、遺伝子間の「交叉」です。交叉により、2つの遺伝子の性質を組み合わせて、新たな遺伝子を2つ生成します。

交叉の方法はいくつかパターンがあるようですが、今回は「2点交叉」というものを用います。これは、2つの遺伝子を同じ2箇所で切断し、中央の部分を入れ替える、というものです。

例: 1番目と2番目の間と4番目と5番目の間を切断し、中央部分を入れ替える。

A: t | f t f | t f -----> t | f f f | t f
     |       |
B: f | f f f | t t -----> f | f t f | t t

遺伝子の突然変異

新しい遺伝子を生成するもう1つの方法が、遺伝子の「突然変異」です。ある遺伝子の性質にランダムに変異を与えることで、「ちょっとだけ違う」遺伝子を生成します。

今回は、以下の処理をしています。

  • まずは遺伝子から真偽値を1つだけランダムに選択して逆転
  • 次に遺伝子の全ての真偽値について、それぞれ3%の確率で逆転

優秀な遺伝子の保持

新しい世代を作る際に、古い世代の優秀な遺伝子をいくつかそのまま残すようにします。

優秀な遺伝子の選択の仕方には、これもまたいくつかのパターンがあるようです。今回は、1つの世代を10遺伝子と固定しています。そこで、そのうち最も優れた2つの遺伝子を残すようにします。

プログラム

以上のような感じで作ったプログラムを、以下を置いています: https://gist.github.com/danglingfarpointer/4333496926a5e6dc8c7b

実行するには

Node.jsの実行環境とパッケージ・マネージャー(npm)が必要です。

それらを準備したら、適当なディレクトリを作り、プログラムをindex.jsというファイルで保存し、npm install underscore(依存ライブラリのインストール)を実行して下さい。

MAC OS Xでの例:

mkdir knapsack
cd knapsack
pbpaste > index.js
npm install underscore

次にナップサック問題の品物を定義するCSVファイルを準備します。1列ごとに、品物の値段と重さを書いていきます。上述の例だと、以下のようになります。

4500, 40
6000, 56
4000, 34
3000, 28
3000, 36
6900, 72

そして実行。CSVファイルのパスとナップサックの容量を与えます。

node index.js /path/to/csv/file 100

実行例

http://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/knapsack_01.html で配布されているベンチマークの中で、10個の品物から成るデータセット(P01)を試してみました。ナップサックの容量が165, 最適解(値段の合計)は309です。

パラメタが良くないせいか実行ごとに結構ばらつくのですが、ある試行(100世代反復)の結果をグラフ化しました。

f:id:danglingfarpointer:20140810210831p:plain

縦軸は品物の値段の合計を表します。赤が最適解(309), 青が世代で一番優れた解候補の適応度、緑が世代の適応度の平均値です。80世代過ぎで最適解(309)に到達。適応度の平均値は50から170あたりを不規則にいったりきたりしています。

最後に

遺伝的アルゴリズムによってナップサック問題を解くプログラムをNode.jsで作りました。パラメタ設定や適応度・交叉・突然変異などの方式がナイーブなので、ばらつきの抑止も含め、よくしたいのであればいろいろ考える必要があります。

「マッチ箱の脳(AI)」の中の他の素材も、Node.jsで書いてみたいと思います。

軽井沢 ホテルブレストンコート

軽井沢に遊びに行ってきました。ホテルブレストンコートで、式を挙げている方を遠くにパシャリ。

f:id:danglingfarpointer:20140802230247j:plain

この時期当ホテルでは「サマーキャンドルナイト」が開催されており、写真のように敷地に多くのランタンが置かれる。暗くなってそれらの灯がきれいに輝く頃には、多くの観光客が集まってくるらしい。

残念ながら時間に余裕がなく、サマーキャンドルナイトを実際に見ることは出来なかった。次行くときは是非見てみたいものだ。

鶴見線でブラっと。。

巷で話題の横浜の鶴見線。いままで一度も乗ったことがなかったので、乗ってみた。

鶴見駅の鶴見線乗り場。駅内の広告によると、アーチ型の屋根は今ではかなり珍しいのだとか。

f:id:danglingfarpointer:20140731134155j:plain

1つの支線の終点である、海芝浦駅。ホームからの写真。

f:id:danglingfarpointer:20140731134221j:plain

海芝浦駅に隣接する小さい公園から。

f:id:danglingfarpointer:20140731134258j:plain

この駅は、東芝の工場の敷地内にある。そのため社員または関係者でないと、公園以外に出ることはできない（公園も東芝の敷地ではあるが、一般開放されている）

電車の中からもパシャリ。

f:id:danglingfarpointer:20140731134321j:plain

支線の分岐にある、浅野駅の駅舎。分岐上にちょうどホームがあるため、2つのホームが斜めに並んでいる。

f:id:danglingfarpointer:20140731134407j:plain

なんとなく昭和のノスタルジーを感じた鶴見線でした。

gitコミットログのユーザーやタイムスタンプを修正 

git commit --amend \
--date="Sat Jun 10 13:00:32 2014 +0900" \
--author="author <author@example.com>"

で、コミットしたユーザー(author)とその日時(author date)を修正できる。デフォルトのgit logで表示されるものが、これらである。

一方で、authorとauthor dateとは別に、committerとcommit dateがある。これらは、コミットをrebaseしたユーザーとその日時をトラックするために使われる。committerとcommit dateも修正するためには、以下のようにする:

GIT_COMMITTER_NAME="committer" \
GIT_COMMITTER_EMAIL="committer@example.com" \
GIT_COMMITTER_DATE="Sat Jun 10 13:05:32 2014 +0900" \
git commit --amend \
--date="Sat Jun 10 13:00:32 2014 +0900" \
--author="author <author@example.com>"

committerとcommit dateを確認するには、git logにオプションを与える:

git log --pretty=fuller