確率論的なミニマックス法（前編）
本記事は、前回のエントリで書いた、ゲーム木探索アルゴリズムにおいて「評価値を確率変数とした場合のミニマックス法」についての検討の続きである。
勘違いしていたこと（重要でないので早く結論を得たい方は読み飛ばしてください）
最初の動機は「ベイズ統計」を使って、効率的に「読む手を絞る」ようなゲーム木探索アルゴリズムを設計することだった。先読みを行う度にそれぞれの手の価値の分布をベイズ更新していくようなアルゴリズムならば、「次にどの手を先読みすればよいか」を合理的に決められるんじゃないかと思ったからだ。例えば決定木の学習における属性選択のような、情報利得の期待値が最大になるようなものを優先するような方法を漠然と想像していた。しかしこの場合、ベイズの定理における「尤度」が計算できない。尤度を計算するためにはモデルの構造が分かっている必要があるが、構造も何も、先読みしてみないことには何も分からないではないか、と。
しかし「ミニマックス法を確率論的に定式化する」という新たなテーマを見つけたので、方向性を変えて検討を進めることにした。ミニマックス法における評価関数の値が確率変数だったらどうなるか、というテーマである。ベータ分布に絞って検討を始めたが、掘り下げていくうちに分布の形状は任意でよいことも分かってきた。
さて、能書きはこれくらいにして、始めよう。
確率変数の最大値の分布
ミニマックス法では、評価値の最大値・最小値を計算する必要がある。評価値が確率変数の場合、どう計算すればよいだろうか。とりあえず、評価値の範囲は０から１の連続値としておくが、各確率変数の分布の形状については特に条件を加えない一般的な状況で議論を進める。
では、N個の独立な確率変数の最大値の分布はどのようになるだろうか。密度関数
で考えると、N個の値の組み合わせパターンは複雑で、とても手に終えない気がしてくる。しかも分布の形は任意なのである。しかし驚くべきことに、密度関数ではなく分布関数
の世界で考えると、あっという間に答えが出る*1。なんと、
(最大値の分布関数) =
(ここがミソ)
= (N個の分布関数の積)
なのである。これを知ったときは驚きで卒倒しそうになった。最大値と掛け算が結びつくなんて。。確率論のすごさを垣間見た感じである。
これを直感的に確かめるには、確率変数の取りうる値が一点の場合に密度関数はデルタ関数になり、その累積分布関数はヘビサイドの階段関数
になることを考えてみると良い。
のうち一つでも0ならば
,全て1ならば
、つまり階段関数同士を掛け算すると一番右に段差がある階段関数だけが残る。したがって密度関数の世界で考えると、一番右に位置するデルタ関数
だけが残ることになる。すなわち、最大値の密度関数
は、
となり決定論的な大小比較と合致する。つまり確率変数の最大値は、決定論的な最大値の一般化になっているのだ！
ということなので、以降では密度関数ではなく分布関数を使ってアルゴリズム設計を進めよう。
最小値の分布
最小値の分布も、最大値と同様の議論で計算できる。
(最小値の分布関数) =
(ド・モルガンの法則)
である。
続きは後半で
さて、長くなったので続きは後半で書くことにしよう。アルファベータ枝刈りに相当する枝刈りもうまく定式化できることを示すのでお楽しみに！
