uctとは？ わかりやすく解説

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/10 02:35 UTC 版)

「モンテカルロ木探索」の記事における「UCT (Upper Confidence Tree)」の解説

探索と知識利用のバランスを取る1つの方法は、Levente Kocsis と Csaba Szepesvári が2006年に発表した UCT（木に適用したUpper Confidence Bound 1）である。UCT は Auer, Cesa-Bianchi, Fischer が2002年に発表した UCB1 (Upper Confidence Bound 1) に基づく方法である。Kocsis と Szepesvári は w n + c ln ⁡ N n {\displaystyle {\frac {w}{n}}+c{\sqrt {\frac {\ln N}{n}}}} が最大となる子ノードを選択することを提案している。各変数は以下の通り。 w は勝った回数 n はこのノードのシミュレーションの回数 N は全シミュレーション回数 c は定数。理論上は 2 {\displaystyle {\sqrt {2}}} であるが、実際は探索が上手く行くように調整する。 第1項の勝率は知識利用である。第2項は探索を表現していて、シミュレーション回数が少ないのを選択するようにする。

※この「UCT (Upper Confidence Tree)」の解説は、「モンテカルロ木探索」の解説の一部です。
「UCT (Upper Confidence Tree)」を含む「モンテカルロ木探索」の記事については、「モンテカルロ木探索」の概要を参照ください。