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が含まれていていいのか怪しい気がしてきたので、もう一度よく考える。
• 先着順でないということはクライアントを待たせるということ。これの意味と影響を考える。

カブロボグリッドをとりあえず動かしてみた。

昨日まとめたBOINCの仕様の実感を何となくつかめた気がする。

今はこの研究室マシンでカブロボクライアントが走っているが、なにやら気に食わんらしい。Project Communication Failed?? うむぅ。なぜ？もしかして仕事がないんだろうか。ワークユニット生成はした覚えがない。どこでどういう風に行うものなのかはまだ理解していない。

BOINCのドキュメント首っ引きで進めているが、この順番で読めば間違いない、という風には書かれていないので必要な情報だけスキャンしようとするとやや難しい。片っ端から読まなければいけないかもしれない。

これからすること：

• ワークユニットとリザルト生成にまつわるBOINCの仕様を理解する
• カブロボグリッドにおけるワークユニットの構成方法を理解する
• クライアントによる出力がどこにどう記録されているのかを理解する
• ライアンが残したユーティリティスクリプトを読んで理解する

研究室にあるグリッド関連の書籍がかなり貧弱なので図書館に行ってみたが、やはりあまりエキサイティングな文献は見つからなかった。ついでに言えば 工学 部の文献室にも初めて行ってみたのだが、こちらもDoors検索すると状態が「研究室」の物ばかりで、結局余りよい書籍や文献は手に入らずじまいである。 まぁ今はまだ自分のやるべきことがハッキリしていないから論文を読んでも仕方がない（というよりも論文の探しようがない）のだが。

適 当に検索してみるとスケジューリングやらなにやらで色々と分散・並列コンピューティングに関する資料はヒットするのだが、そのうちどこまでの面倒を BOINCが見てくれているのかは知っておく必要がある。さすがに二週間でBOINC自体に手をつけるのは難しい。自分が触るべきところをハッキリさせる のが今週の目標か。

ネットワーク情報システム研究室のスタートアップとして、去年同じ研究室にいたRyanがやっていたカブロボグリッドにとりあえず着手することになりました。

これはRyanによる卒論のまとめおよびメモです。

アブスト

システムトレードとは、投資を行う際に裁量を排し、売買ルールに従って取引をする方法。株取引アルゴリズムとパラメータの組み合わせ（「パラメータAとBの除がCになれば売る」など）。この探索空間は膨大。これまでは人間の感覚によるヒューリスティックな選択がされてきた。
本研究では売買ルールの全探索のためにカブロボグリッドを構築し、実装と評価をした。

１．背景と目的

システムトレードの気運が高まっている。例えばトレードサイエンス株式会社では2006年から仮想市場でのカブロボコンテストを実施しているし、野村総研では大口の注文をシステムトレードを介して証券取引所に取り次ぐシステムを開発、運用している。取引アルゴリズムはルールとパラメータの組み合わせによるが、ルール同士を組み合わせることも可能であるため、探索空間は膨大であり、これまでブルートフォースなアプローチは取られてこなかった。

そこで、グリッドを利用してアルゴリズムの探索を行うシステムを提案、実装、評価する。そのためには
１）探索アプリケーションのグリッド化
２）全体を管理するグリッドの構築
が必要であり、本研究では２を行う。

２．要素技術

Ａ）BOINC
汎用グリッドフレームワーク。TANPAKU、SETI@HOME、BBC Climate Change Experimentなどで採用。クライアント数百万台での大規模運用も可能。

・サーバ
クライアントの状態把握、データの受け渡し、ワークユニットとリザルトの管理。
うち前者二つは提供され、後者二つは自前で用意する。

・ワークユニット
実行すべき計算を表現したルール。リザルトを抽象化したもの。
常に十分な数のワークユニットがサーバ上に存在するように、ワークユニットジェネレータにより定期的に生成される。

・リザルト
ひとつの計算を表現したもの。必ずしも計算後の結果ではない。
ひとつのワークユニットからは必ず同じリザルトが生まれるが、冗長化のためにデフォルトで五つのリザルトが生成される。

・クライアント
コアクライアント（BOINCが提供）とクライアントアプリケーション（プロジェクトが提供）。
コアクライアントは各々のマシンで直接実行できるネイティブコード形式でなければいけない。

Ｂ）カブロボ
トレードサイエンス株式会社が配布している取引シミュレーションソフトの一部。KaburoboSDK(Java)またはKaburoboBuilderLiteでカブロボを開発。2004～2006の株価データでのシミュレーションが可能。

３．カブロボグリッドの構築

サーバからクライアントへ取引ルールを渡し、配布されているシミュレーション機能で評価させる。クライアントはカブロボSDKとそのラッパー。

・株価データは本来単一でいいのだが、カブロボのインスタンスによってロックされるため、一台のクライアントマシン内で並行して走らせるために各リザルトに株価データを添付することにした。
・カブロボはシミュレーション結果を標準出力にしか出してくれないため、ファイルへリダイレクトする機構を実装。
・閉じた環境であるためリザルトの冗長度を5から2に変更。
・ワークユニットジェネレータを作成。

４．評価と考察

ネットワークとBOINCによる二つのオーバーヘッドが考えられるが、今回検証したのはBOINCのほうのみ。評価はサーバ1台、クライアント1台。結果、１リザルトあたりの処理時間はカブロボ単独148s、BOINC利用時179sとなった。（全体の18%）

５．今後の課題

ワークユニットジェネレータを改良し、より多くのワークユニットを生成できるようにする。
シミュレーションで使える銘柄を多くし、リアリティを増す。
以上。

感想など

・関連研究を明らかにしたい。
・BOINCのその他の利用例と基本的なグリッドのセオリーを調べたい。
・ヒューリスティックなアルゴリズムを利用することも検討。
・ルール同士の組み合わせが可能だというが、それなら探索空間は無限？
・もし有限ならばその大きさの概算がほしい。
・株価データを何回も送るのは通信がしんどい？そうでもない？
・今回生成できたワークユニットの数が少なかった理由は何？
・Low latencyの方向へ進めるならいじるのはワークユニットジェネレータあたりか。
・もっとクライアント数を増やして試したい。ってLow latencyするなら必然的に増やさねば。
・ということはスケジューリングや分配方法に頭をひねるべき
・そこへきてBOINCはどれほど世話を焼いてくれるのか？
・グリッドを使ったほうが人間ヒューリスティックよりもよいアルゴリズムが見つかるというのが論点ならば、計算速度だけではなく出てきた結果の有効性によって評価するべき。
・たとえばSETI@HOMEなら全世界の人間が参加しても困ることはないが、全世界の人間がこれをやりだしたらどないしまんねんという根本的な疑問。そもそもにおいて一部の人だけが使うから良いという技術？ただの個人的な倫理問題だが重要かも…。
・それにしても研究室にグリッド関連の書籍が少ない。