Swarmingって何？


HTM（hierarchical temporal memory）は大脳の新皮質の構造をヒントにしたニューラルネットワークの構成技法だ。

HTMでパターンを学習し、パターン以外のもの（anomaly）を検出することができる。

numentaはHTMの機能を実装したライブラリをnupicとしてgithub.com上に公開している。商用には特許がらみで許諾をとる必要はあるが、個人が学習のためにいじっても問題はない。

しかし、実際にデータを持っていたとして、それを解析し、学習し、推定を行うにはどのようにパラメータを決めたらいいか、私のような初心者は途方に暮れてしまうのではないだろうか？

パラメータを決めるためのツールがあり、それを実行することはswarmingと呼ばれているらしい。
以下、自分の勉強の記録を書き留めていく予定。

関連メモ：http://qiita.com/kgbu/items/f5e9352cab4388a62e29 (HTMのサンプルを眺めてみた)

## TL;DR 

以下のスライドの１３，１４ページあたりが直観的

PDF:　http://numenta.org/resources/blog/Swarming_in_NuPIC.pdf

機械学習のシステムの設計のパラメータ選択において遺伝アルゴリズムとちょっと似た手法。
遺伝子を空間内の点の座標と考えて、適応度を並列に計算して、その後、より適合度の高い「次世代」を作る方法として、遺伝子のシャッフルではなく、

* 個体群の重心
* 適合度の山登り(パラメータのランダムな変化のベクトルと適合度の変化による勾配の推定）

などが勘案されているようだ。

詳しくはこちらを参照してみてもいいかも。http://www.swarmintelligence.org/tutorials.php


# Swarmingのアルゴリズム

https://github.com/numenta/nupic/wiki/Swarming-Algorithm by Ryan J. McCall 
現状、このパートは上記のnumentaのnupicのWikiの記事の適当な要約。

## Overview


データについてどのようなモデルが良いのかを決めるswarmingのアルゴリズムについて述べている
（IMHO：そこを無手勝流にやっていくのがHTMじゃないのかよ、とも思うが、大脳新皮質はシンプルでも感覚受容器は自然淘汰でチューニング済みではあるよね、、、）

具体的にどのようにして調整するのかは「Running Swarms ( https://github.com/numenta/nupic/wiki/Running-Swarms )」の項を参照のこと

swarmingではあるデータの集まりについていくつかの異なるモデルを作って比較する。結果として得られるのはもっとも誤差が少なくなる設定パラメータである。

有用度を試すHTMベースのモデルを作成するときに考慮される要因

* データがレコードの集合だとして、どのフィールドを使うか
* HTMのモデルのうち、どの要素を使うか、そしてデータのうち、どれを適用するか
    * encoder
    * 空間プーリング
    * 時間プーリング
    * 分類器


最適なモデルを探索する空間は、その要素が多いだけに巨大になってしまいがちである。
例えばデータが５つの利用可能なフィールドを持ち、HTMの要素として３つ使えるものがあるとして、最適化するパラメータは１０個以上になる。
全ての可能な組み合わせを試すのはコストが高すぎるので、ダイナミックプログラミングの手法を用い、知的なノウハウに基づいて組み合わせの枝刈りをしていく。

swarmingは並列処理可能である。
N個のプロセスがあったとして、それぞれ異なるモデルの検証を走らせることができる。
分散処理において集中管理用のプロセスはない。

その代わり、各workerプロセスはデータベースを共有して設定を取得してその結果をpublishする。他のworkerの結果も取得して比較し、以後の処理内容を決める。

このデザインによって耐故障性が上がっている。どのworkerプロセスが死んだり新たに生成されたとしても、swarmのプロセスはそのまま実行されていく。workerが異なるマシンに分散していても可用性は高いし、データベースが常時ミラーリングなどでバックアップされていれば大丈夫。

## モデルに必要なデータフィールドの探索の方法

フィールドの検索はswarmプロセスの一番外側のループに当たる。

Swarmingでは利用するフィールドを選択するのに一種のgreedy(強欲)アルゴリズムを利用する。
検索全体は「sprint」と呼ばれる試行の積み重ねである。それぞれのsprintはモデルの持つフィールド数から１を引いた数だけ生成される。

最初のsprint #0は、モデルのデータのすべてのフィールド（A, B, C, D...)を個別にチェックする。その中でもっとも成績が良いフィールド（たとえばフィールドBとする）と、他のフィールドを組み合わせたケースについてチェックをしていく。(BA, BC, BD, BE,,,)
これを続けていくのだが、そのうちフィールドを増やしても結果が良くならなくなる。その時点探索を打ち切る。

以後のsprint #1から先のsprintでは、sprint #0で得られた成績上位のフィールドの内、あらかじめ決められた上限（デフォルトでは５つで設定変更は可能）の個数のフィールドだけで処理を行う。こうすることで、膨大なフィールドを持つデータがあったとしてもswarmの処理が実行可能になる。

それぞれのsprintの処理の中では一つ、もしくは複数の **mini-swarm(MS)** という処理が含まれている。


sprintで検証されるそれぞれのフィールドの組み合わせについて１つのmini-swarm(以後MS)が実行される。それぞれのMSでは複数のモデルを評価し、特定のフィールドの組み合わせにおいて最適なモデルを選ぶ。
MSの実行中にはモデルを特徴づける各種のパラメータを動かし、そのパラメータ空間において最適な点を決定することで最適なモデルを決める。
なお、モデルのパラメータには連続的なスカラー値と、離散的で定数の集合として数え上げ(enumerable)可能な値のものがあり、それぞれパラメータの最適値の決定方法は異なる。それについては以後の「スカラー値パラメータの選択」および「数え上げ値パラメータの選択」の項で説明する。


データの推移の予測やanomaly（異常）検知のモデルでは、予測の対象となるフィールドは常にsprintの処理の対象になる。ただし、最終的に選ばれたモデルに含まれるとは限らない。

sprintの過程では、評価の対象となる各フィールドのデータはHTMのネットワークの最下層からの入力として与えられる。それが最終的に構造が決定したときのネットワークの出力であっても、各フィールドのデータは分類器(classifier)へと個別に直接入力される。そのデータの分類器の学習の教師データ（期待される出力）として使われる。
このデータの流れの設定はフィールドの選択のループに先立って設定される。


空間的な分類のモデルを作る場合、フィールド探索において予想されるべきデータのフィールドは評価の対象とはならないのが他との違いである。

それは、他のフィールドの時刻ｔでの値から、ある時刻tでのフィールドの値を推定するとき、推定の対象となるフィールドの値はまだ知られていないので、ネットワークの入力にできないからである。

推定の対象となるフィールドの値は分類器への入力としては経路が確保されているので、この場合でも学習はできる。

## モデルのスカラー値パラメータの選択

この節ではMS(mini swarming)の工程においてスカラー値のモデルパラメータの最適な推定値を収束させるためやっていることを説明する。スカラー値というのは整数や浮動小数点の値のことである。

MSの工程では**Particle Swarm Optimization(PSO)**アルゴリズムでパラメータの最適な値を決めている。
（参照：http://numenta.org/resources/blog/Swarming_in_NuPIC.pdf　の１２－１６ページあたり）

このアルゴリズムでは試行対象となるモデルはparticle（粒子）と呼ばれる。モデルに含まれるいくつかのパラメータの値を多次元空間に存在する粒子の座標だと考えるのである。

最初にいくつかのparticleが生成される。
それらはパラメータ空間にばらばらに配置される（初期のモデルはばらばらなパラメータで構成される）。そして、ランダムな速度で移動（パラメータを変化させていく変分）するように設定されている。
それぞれのparticleは現在の位置（パラメータ）でモデルを評価して、合致度(fitness score: 推定値と比較した誤差)を得る。この合致度と他のparticleの合致度を使ってparticleの新しい位置を決める。
この過程を繰り返していく。
パラメータ空間を粒子の群れがランダムに動いて行って最適な場所へと漂って収束していくイメージである。

particleの新しいを位置を計算するには、MSに含まれるparticleの群れ(swarm)の中で過去もっともスコアの良かった位置と、それぞれのparticleの過去最高スコアの位置を参考にする。
あるparticleが群れ全体での過去最高の位置から遠ざかるにつれて、移動の速度（位置の変分）は大きくなる。また、局所解にとらわれないようにするために、ランダムなノイズも加えられる。


式は次のようになる。

```
vi = vi + ϕ1*rnd()*(pi-xi)+ ϕ2*rnd()*(gbest-xi)
xi = xi + vi
```

viとxiはそれぞれparticle[i]の移動速度と位置を表す。　piはparticle[i]の自己ベストの値がでた位置で、 gbestというのは群れとしてのベストの値が出た位置である。
φ1, φ2は適当な係数。

なお、pi - xiや gbest - xi　は、一般的には差分ベクトルの長さになる。


PSOのアルゴリズムではそれぞれのparticleには固有のIDが割り当てられている。particleがパラメータ空間を移動しても、そのIDで追跡できる。
あるparticleの最初の位置は第0世代に属するとされる。その後、新しい位置に移動した時には世代の番号が一つづつ増えていく。
MSの処理は群れとしてのベストの値が改善されなくなった時点で打ち切られる。

ユーザーがswarmの処理を開始する際に、処理の規模を'small'、'medium'、'large'と指定する。現在のところ、'small'というのはMSについて１つしかparticleを生成しない。'medium'だと５つ。'large'ならば15個のparticleを使って最適値を探索する。
particleが多ければ、探索の範囲は広がり、結果が最適に近く可能性は高まる。

## Choosing Enumerated Parameter Values モデルの数え上げ可能なケース分けのenumパラメータの選択


この節ではMS(mini swarming)の工程において数え上げ型(以後enum型)の値のモデルパラメータの最適な推定値を収束させるためやっていることを説明する。

enum型の値のパラメータの例としては、ブール値(true, false)や、取りうる値がリストとして明確に定義されている場合がある。例えば動物の種類として[鳥、魚、哺乳類]といったリストがある場合である。


このタイプのパラメータは時にはモデルの構成要素のパラメータであることもある、例えば空間プーリングの'randomSP'というのはブール値のenum型パラメータである。


enum型はモデルの概要を決める要素を表現することもある。例えば、'includedSP'というパラメータはブール値をとるが、このパラメータによってモデルが空間プーリングの要素を含むか否かが決まる。分類器のタイプ（例：'knn'(k nearest neighbour ニューラルネットワーク), 'svm'(サポートベクターマシン）を指定するようなenum型のパラメータもある


swarmingでは、それぞれのenum型パラメータについてスコアの平均値を記録していく。
例えば、あるパラメータが取りうる値が['A', 'B', 'C']だとして、'A'の時はモデルの誤差のスコアの平均が0.2であるとか、’B’の時は0.5であるとか、である。
新しいテスト用のモデルを生成する場合には、これまでもっとも良いスコア（誤差が少ない）のパラメータが選ばれる確率が高くなるようにして、有望なパラメータについてより詳細なデータが取れるようにする。


## 投機的実行

ワーカープロセスを最大限に利用するため、swarmではプロセスの投機的実行を行う。これがデフォルトの設定だが、これをオフにすることもできる。

たとえば、'medium'の設定でついて３つのフィールドに関するswarmを試行しているとする。この場合、１つのMS(mini swarm)について５つのparticleが作られる。
この例では sprint #0で３つのMSが実行され、それぞれ５つのparticleが処理される。もし、計算に使えるCPUが15個以上ならば、他のCPUはどうしたらいいだろう？投機的実行がオフであれば、余った計算資源は使いようがない。
まだそれぞれのフィールドの組み合わせでどのparticleの位置がベストかわかっていないので、次のsprint #0の試行を開始することもできないし、
まだどのフィールドの組み合わせがベストかわかっていないから 次のsprint #1を開始することもできない


しかし、投機的実行のオプションが指定されていて、余ったワーカープロセスがあるならば、それらのワーカープロセスはベストと思われるパラメータを推定して、それを元に試行を開始する。


余ったワーカーが試行するための新しいモデルを構築するとき、現在のsprintで実行ずみのparticleの次の世代を生成して使おうとする。
今、少なくとも１個のparticleが第N世代の処理を完了したとすると、そのparticleの位置を更新して第N+1世代のparticleの位置を計算し、それに対応するモデルで試行を開始する。この場合、第N世代の群全体のベストのスコアはわかっていないが、それ以前の情報を使う。


もし、まだ一つも第N世代のparticleの処理が終わっていなければ、workerは次の組み合わせレベルのsprintの処理を最初から開始しようとする。現在の第N世代の群全体のスコアやそれぞれのparticleのスコアもわかっていないので、新しいsprintが利用するのは現在の値である。


例えば、１つのフィールドだけでモデルを構成してsprint #0を開始した時、投機的実行がなければ'AB', 'AC', 'BC'といった２つのフィールドでモデルを構成した場合の処理は開始できないが、投機的実行でworkerが余っていれば即座に開始できる。