MCTSは 2048 評価でランダム再起動より 2.88% 性能が悪かった
この記事のポイント
- MCTSの優位性を否定する比較がなかった
- 2048件でMCTSと再起動スケジューラを比較
- MCTSは2.88%劣る。ただし合成データのみ
数字で見る
この記事に出てくる数字
| 評価スケジュール数 | 2048 |
|---|---|
| MCTS劣勢率 | 2.88% |
| 探索プール改善率 | 1.85% |
どこで使えるか
コードの公開は記載なし
スポンサーリンク
解説
かみくだいて説明します
Yuyu Zhang さんが arXiv に論文を出しました。DAG という、作業の前後関係が絵図のように繋がっている状態を処理するスケジュール手法で、モンテカルロ木探索と、ランダムに最初からやり直すリストスケジューリングを、同じ計算量で比較した研究です。
同じ計算量で比べたんですか。どちらが速いんですか?
2048 個の候補スケジュールを評価する予算で比べたところ、モンテカルロ木探索はランダムにやり直す方より、2.88% 悪かったです。95% の信頼区間はマイナス 3.62% からマイナス 2.15% で、誤差の範囲ではありません。木探索の選び方が、最初に見つけた道にだけ進もうとして、他の道を探さない状態に似ています。
作り直す手間がかかるなら困りますね。計算量を増やせば追いつきますか。
計算量を増やしても追付きません。別の実験用データで調べたところ、やり直す方は 1.85% 改善しましたが、木探索は 0.24% しか伸びませんでした。木探索の最初の結果 720 件中 700 件は、最初から与えられた状態をそのまま使っているだけでした。
最初の状態に縛られているんですね。別の選び方に変えたらどうなりますか。
教科書通りの UCT という選び方に変えると、差はほぼなくなります。悪さは 0.26% まで縮まります。95% の信頼区間はマイナス 0.71% からプラス 0.23% です。木が細い作業ではやり直す方が有利で、段々になった規則的な作業では差が出ず、作業が密すぎるとどちらも改善の余地がないことが分かっています。
現場で組み込む技術者から見ると、選び方を変えるだけで済む話ですか。
選び方を変えるだけで済みますが、実際の環境にそのまま当てはまるかは分かりません。今回の実験は 8 から 32 個の作業、2 から 8 個のプロセッサ、予算は最大 2048 までの合成データに限っています。もっと大きな予算や現実のシステムでは、そこはまだ分かっていません。
多くの研究が比べる検証をやってこなかったんですか。
多くの研究がモンテカルロ木探索を提案しながら、同じ計算量で単純な手法と比べる検証をやってこなかった点です。今回の研究は計画を事前に固定し、独立した確認者が768件のスケジュールを正しく検証しました。手法の選定基準が最終結果に因果関係を持つことは証明されていませんが、木構造がどの時点で効果を示すかの構造的な位置を特定できた点が新しいです。
最後に、実用化に向けた次のステップは何ですか。
実際のシステムで使う場合、処理する作業の数やプロセッサの数に合わせて、同じ予算で比較する検証を改めて行う必要があります。予算を大きくした際の振る舞いや、現実のノイズがある環境での性能については、そこはまだ分かっていません。
出典
この記事のもとになった情報
※ 本文と音声は生成 AI が作成しています。内容は出典をご確認ください。
本作品のキャラクターには株式会社Live2Dの著作物であるサンプルデータが株式会社Live2Dの定める規約に従って用いられています。本作品は制作者の完全な自己の裁量で制作されています。このキャラクターモデルは株式会社Live2Dより許諾を得て商用利用しています。