2016年9月6日火曜日

バンディット問題の理論とアルゴリズム

『バンディット問題の理論とアルゴリズム』購入。
本多淳也/中村篤祥・著 講談社
ISBN:9784061529175
本体 2800円(税別)
http://www.kspub.co.jp/book/detail/1529175.html

なんだか凄そうである。
http://qiita.com/yuku_t/items/6844aac6008911401b19




バンディット問題とは、選択肢の集合から1つの要素を選択し、その選択肢に対する報酬を得るが、他の選択肢の報酬情報は得られない、というプロセスを繰り返す設定において、報酬和の最大化を目指す逐次決定問題である。
◯『人生は選択の繰り返しです。...本当にもっと良い現在があったかどうか確かではありません。....1つ言えることは、「探索」と「知識利用」のバランスが重要であることです。
...最適な選択をするために、もっと良い道を探す「探索」と今までの経験を生かす「知識利用」のバランスをとることが重要です。まさにこれがバンディッド問題の本質でもあるのです。』
◯バンディッド問題は大別して、確率的バンディット敵対的バンディットに分けられる。前者は各アームから何らかの確率分布に従って生成され、後者はプレイヤーの方策を知っている敵対者が報酬を決める場合を想定する。バンディッドとは盗賊という意味で、
1台のアームが付いた古典的なスロットマシーンで、プレイヤーに賭けをさせることにちなんで1腕バンディットといい、複数のスロットマシンを選んでアームを引くことを反復することで儲けの最大化を図ること多腕バンディット問題という。プレーヤーがスロットを引く戦略を方策という。
◯現実への問題では、治験、インターネット広告配信、推薦システム、ゲーム木探索、オンライン経路制御など多岐にわたる。
◯プレイヤー方策の評価方法として、有限時間区間における累積報酬無限時間区間における幾何割引された累積報酬がある。累積報酬の他に、リグレット(後悔)という評価値があり、これは「あの時ああしていればよかった」という後悔の大きさの値である。(面白い!)
◯機械学習でバンディット問題が取り上げられたのは、UCB方策(2002年)。コンピュータ囲碁で使われるモンテカルロ木を取り入れたUCTアルゴリズム (2006年)で囲碁の性能が向上。推薦システムにはLinUCB方策というものが提案され、これはコールドスタート問題(新しいユーザ又は新しい商品に関してパーソナライズされた適切な推薦が行われるまで時間がかかる)という問題の解決手段となる。
敵対的バンディッドでは、ブースティングにも関係あるHedgeアルゴリアウムを適用したExp3方策(1995年)がありリグレット解析を行った。その後 2009年の改良されたINF方策が提案された。
◯この書籍の構成は2章から5章で、基本的なバンディット問題の設定。2章は、大偏差原理など、3章では効率的な方策の構成、4章では厳密なリグレット解析、5章では敵対的バンディット。6章からは発展で、6章は最適腕識別。7章バンディッド問題の基本的な拡張として、報酬の構造の線形モデルへの一般化。8章では非線形、無限個のアームがる状況の連続腕バンディッド。9章では、非定常的な確率モデル、観測モデルの一般化。10章では現実の問題、インターネット広告配信やゲーム木探索の効果的な方策を取り扱っている。

プログラム
https://iridge.jp/blog/201412/5508/

0 件のコメント:

コメントを投稿

石田吉貞『隠者の文学』講談社学術文庫

 FIRE系の動画や書籍を読んでいる。また、年齢を上になるにつれ、自分と社会の距離感なども気になる。本書は、以前から読んで気にいったいた中野孝二『清貧の思想』と同様の思想の書籍である。 石田吉貞『隠者の文学』講談社学術文庫 隠者の文学―苦悶する美 (講談社学術文庫) 隠者と隠者...