memo/2011-01-31
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
**To: ogura From: takataka [#w0cf4ec2]
お伝えしたいことをおぐら君の席の左の白板に書いときました．
**To: hiroaki From: takataka [#k4060d55]
今晩，風呂の中で次の論文をななめ読みしました．
UCBを提案している論文です．
Finite-time Analysis of the Multiarmed Bandit Problem
-PETER AUER, NICOLO CESA-BIANCHI, PAUL FISCHER
-Machine Learning, 47, 235--256, 2002
その結果，「勝率を用いる場合とスコアを用いる場合で評価値（以下では報酬と呼びます）の分散が違うのをどう扱うか」の解決策らしきものが見えたのでおしらせします．
この論文では，坂口君も用いているUCB1
#jsmath{{
\bar{x}_j + \sqrt{ \frac{ 2\ln n }{n_j} }
}}
は，報酬が [0,1] である場合の方策として提案されています（だから勝率を用いる場合はそのままでよい）．
一方，報酬の平均も分散も未知の場合は，正規分布と考える UCB1-NORMAL というのを提案しています．
本来は，スコアを用いる方はこの UCB1-NORMAL を用いる方がよさそうですが，両者の式を見比べて高橋が考えたところでは，次のようにすればお手軽に UCB1-NORMAL と近いアルゴリズムになりそうです．
+現在の実験のように，あらかじめスコアの標準偏差を求めておく．これを &jsmath( \sigma ); とする．
+スコアを &jsmath( 2\sqrt{2}\sigma ); で割った値を報酬として UCB1 の値を計算する
+スコアの平均はUCB1の値に影響しないので，いじる必要なし
でもできたら UCB1-NORMAL を実装する方がよさげ…．
後で相談しましょう．
それから，UCTのことを調べていたら，「playout回数が（あらかじめ定めた）一定値を超えたら展開（子ノードに下る）する」というような説明に出会いました．
坂口君の実装とはちょっと違うようです．
UCTのオリジナルの論文
Bandit Based Monte-Carlo Planning,
-L. Kocsis and C. Szepesvari,
-LNCS vol.4212 (ECML 2006), pp. 282-293, 2006.
を読んだらちゃんと説明されてそうな気がしますが，まだ読んでません．
**To: takataka From: hiroaki [#qdedb041]
UCB、UCTともに少しパラメータや条件式をいじるだけなので、時間は掛からないと思います。~
UCBでは、モンテカルロ法の部分で評価値の重みを変えるだけ~
UCTでは、クラスUCTのメンバ変数として探索時間とプレイアウト回数を持っているので初期化の際に実引数を変えるのと、~
プレイアウト１回制限から3回制限への変更は、関数PlayOneSequence の中の条件式while(nb > 1)を while(nb > 3) に書き換えるだけで済みます~
終了行:
**To: ogura From: takataka [#w0cf4ec2]
お伝えしたいことをおぐら君の席の左の白板に書いときました．
**To: hiroaki From: takataka [#k4060d55]
今晩，風呂の中で次の論文をななめ読みしました．
UCBを提案している論文です．
Finite-time Analysis of the Multiarmed Bandit Problem
-PETER AUER, NICOLO CESA-BIANCHI, PAUL FISCHER
-Machine Learning, 47, 235--256, 2002
その結果，「勝率を用いる場合とスコアを用いる場合で評価値（以下では報酬と呼びます）の分散が違うのをどう扱うか」の解決策らしきものが見えたのでおしらせします．
この論文では，坂口君も用いているUCB1
#jsmath{{
\bar{x}_j + \sqrt{ \frac{ 2\ln n }{n_j} }
}}
は，報酬が [0,1] である場合の方策として提案されています（だから勝率を用いる場合はそのままでよい）．
一方，報酬の平均も分散も未知の場合は，正規分布と考える UCB1-NORMAL というのを提案しています．
本来は，スコアを用いる方はこの UCB1-NORMAL を用いる方がよさそうですが，両者の式を見比べて高橋が考えたところでは，次のようにすればお手軽に UCB1-NORMAL と近いアルゴリズムになりそうです．
+現在の実験のように，あらかじめスコアの標準偏差を求めておく．これを &jsmath( \sigma ); とする．
+スコアを &jsmath( 2\sqrt{2}\sigma ); で割った値を報酬として UCB1 の値を計算する
+スコアの平均はUCB1の値に影響しないので，いじる必要なし
でもできたら UCB1-NORMAL を実装する方がよさげ…．
後で相談しましょう．
それから，UCTのことを調べていたら，「playout回数が（あらかじめ定めた）一定値を超えたら展開（子ノードに下る）する」というような説明に出会いました．
坂口君の実装とはちょっと違うようです．
UCTのオリジナルの論文
Bandit Based Monte-Carlo Planning,
-L. Kocsis and C. Szepesvari,
-LNCS vol.4212 (ECML 2006), pp. 282-293, 2006.
を読んだらちゃんと説明されてそうな気がしますが，まだ読んでません．
**To: takataka From: hiroaki [#qdedb041]
UCB、UCTともに少しパラメータや条件式をいじるだけなので、時間は掛からないと思います。~
UCBでは、モンテカルロ法の部分で評価値の重みを変えるだけ~
UCTでは、クラスUCTのメンバ変数として探索時間とプレイアウト回数を持っているので初期化の際に実引数を変えるのと、~
プレイアウト１回制限から3回制限への変更は、関数PlayOneSequence の中の条件式while(nb > 1)を while(nb > 3) に書き換えるだけで済みます~
ページ名:
![[PukiWiki]](image/blackuni3-80x80.png "[PukiWiki]")
