Oddwit

月例発表会向けレジュメとスライドの第一版ができた。最近研究関連の事を書いてなかったので、ラフにではあるがいまのところのアウトラインをまとめておく。

タイトル：「カブロボグリッド実現方法の検討」

カブロボグリッドとは

カブロボは、自動株取引きプログラム。選択した売買アルゴリズムによって儲かったり儲からなかったりするため、良いアルゴリズムを発見することが大きな課題になる。

カブロボのアルゴリズムは売買ルールとパラメータで表現されるが、ルール同士を組み合わせることも可能なため、その数は膨大。グリッドの力でこれを片っ端から探索しようというのがカブロボグリッドだ。

だが、本当に片っ端からやるだけでは効率が良くない。そこで、より良いアルゴリズムをより短時間で見つけるために、行う仕事の選択と、クライアントへの仕事の割り振り方に関していくつかの方策を提案する。

仕事の選択

片っ端から試すより、良いアルゴリズムの周辺を重点的に試行するほうがおそらく効率が良い。さらに、たとえばユーザが希望した部分を優先的に試行するような仕組みが欲しい。

そこで、仕事の生成をオーディションラインとトレーニングラインの二つに分ける。

オーディションラインは、基本的にはユーザが指定した部分の仕事を生成する。

トレーニングラインは、オーディション出身で比較的性能が良かったアルゴリズムの周辺へ手を伸ばしていく。

加えて、トレーニングラインから確率的にジャンプを起こし、少しだけ離れた部分のアルゴリズムをオーディションさせる。これは焼きなまし法に似ている。

仕事の割り振り方

ま ず前提として、カブロボグリッドではエラー耐性のために同じ仕事を複数のクライアントに割り当てる。同じ仕事を4つのクライアントに振る、というのは「冗 長性」として自由に設定可能だ。また、このうち最低3つの結果が一致していればそれを正しい結果とみなす、というような設定が可能で、この値を「クオラ ム」と呼ぶ。

さて、いまのカブロボグリッドでは冗長性を一律で設定できるが、仕事ごとに設定できない。だが冗長性をその時々のクライアントたちの能力によって動的に変更することで無駄が減らせるはずだ。

そ こで、何通りか考えられる冗長性rに対して、期待値Erを定義する。これはEr = 1/(jr * lr) で表される。jrは冗長性rのときに一回でコンセンサスが得られない確率。lrはそのときに失われる時間。これらは仕事を受け取るクライアントの能力に よって決まる。常にこのErが最大になるようなrをその仕事の冗長性として設定することで、常にもっとも効率が良いと見込める冗長性設定が可能になる。

次 に、最低限必要でない仕事をどのクライアントに割り振るべきかを考える。これは、たとえば冗長性4、クオラム3の場合の4つ目の仕事だ。前の3つが同じ結 果で返って来たときにこの4つ目の仕事は無駄になるわけで、それを例えばものすごく能力の高いクライアントに渡してしまうのはもったいない。そのクライア ントは無駄にならない別の仕事をすべきだ。

そこで、ある仕事wuを受け取れるそれぞれのクライアントiについて、もったいなさMiを定義す る。これはMi = w/(j * ei) で表される。wは仕事wuの計算量、jは自分と同じ仕事をしているほかのクライアントたちがエラーを起こす確率、eiは自分自身がエラーを起こす確率。こ れらの値は同じ仕事をしているクライアントたちと、手の空いているクライアントたちの能力によって決まる。常にこのMiが最小になるようなクライアントi に仕事を振ることで、もっとも無駄のない割り振りが可能になる。

これから考えるべきこと

• 「期待値」という言葉は厳密にはふさわしくないので、他の分かりやすい言葉を考える。
• もったいなさの式にjが含まれていていいのか怪しい気がしてきたので、もう一度よく考える。
• 先着順でないということはクライアントを待たせるということ。これの意味と影響を考える。