巷で話題のバンディットアルゴリズムを、
ネット上の素晴らしい資料を参考にしたり引用したりしながら、
おおまかなイメージがつかめるようにまとめていきます。
導入：タカシ君のお年玉
20XX年、元旦。
タカシ君は、この冬休みずっと、コインに念を送って表を出す練習に励んできました。
というのも、
- コインが5種類(A,B,C,D,E)あるが、どうやらそれぞれ形が違うようで、表が出る確率が違う（が変化はしない）
- 「1回ごとにコインを1つ選んで、50回コイン投げていいよ」と両親に言われている
- 表が出た回数×1000円をお年玉としてもらえる
ので、なんとかして表が出る回数を最大にしたいのです。
冗談はさておき、タカシ君は、どういう方針でコインを選ぶのがいいのでしょうか。
- 同じコインを投げ続ける？「コインB、君に決めた！」
- 全てのコインを均等に投げる？「平等にコインAを10回、Bを10回、...」
- これまで表が出たコインを多めに引く？「コインCは表が出やすそう」
根底にある考え
複数の選択肢から、最終的に一つを選ぶとき、
- 選択肢ごとに『良さ』の度合いを何らかの方法で数値化できる（事前には分からないけど）
- 試行回数が限られている
場合に
- 「ダメな選択肢をできる限り選ばずに、ベストな選択肢を選びたい」
問題の例：日常生活
- ランチのお店（和食？洋食？イタリアン？中華？）
- 旅行の行き先（北欧？南米？アフリカ？）
- 彼女へのプレゼント（時計？ネックレス？バッグ？）
問題の例：ビジネス
-
どの広告を出すと、一番多くクリックされるか(CTR)
-
1クリック20円なら→予算10万円なら5,000クリック
-
どのメールの文面を使うと、一番多く開封してもらえるか(メール開封率)
-
Webページ最適化
バラク・オバマ陣営が、大統領選挙戦でWebページ最適化を活用して多額の献金を集めることに成功したのは有名ですね。
Webページ最適化では、
「仮説パターン」＝デザインや機能がオリジナルと一部異なるウェブページ
を用意して、この仮説パターンの中から「広告クリック率」や「ページ滞在時間」といった評価指標を最大化するパターンを探しだします。
探索(exploration)と活用(exploitation)
-
探索：現在知っている情報以外の情報を獲得するために選択肢を選ぶこと
-
行ったことのない定食屋に行ってみる
-
出したことのない広告を出してみる（A/Bテスト実行中）
-
活用：現在知っている情報から、利益を最大化する選択肢を選ぶこと
-
「一番おいしいここにしよう」
-
「一番よかった広告を出そう」（A/Bテスト後の本番）
探索と活用はトレードオフ
- 探索ばかりだと・・・いい選択肢が分かっているのに選ばない←A/Bテスト中
- 活用ばかりだと・・・他にもっといい選択肢があっても気付けない
バンディットアルゴリズム
-
探索と活用を効率的に行い、一定期間での利益を最大化するアルゴリズム
-
（強化学習の文脈では）エージェントが効率的な学習を行うために用いられるアルゴリズム
-
単純のため、以下では値は2値
-
当たりかハズレか、クリックされたか否か、購入されたか否か
言葉の定義
| 言葉 | 意味 |
|---|---|
| アーム | 選択肢のこと |
| 多腕 | 腕(アーム)が多数あること。 |
| 引く | アームを選択し、その結果を受け取ること。 |
| 探索 | アームに関する情報を増やすためにアームを引くこと |
| 活用 | いま持っている情報から、最適と判断できるアームを引くこと |
アルゴリズムの種類
- epsilon-greedy
- 確率eで活用（期待値の最も高いアームを引く）、1-eで探索
- A/Bテストは、epsilon-firstと分類できる（一定期間ずっと探索→その後はずっと活用）
- Softmax
- UCB
A/Bテストとバンディットアルゴリズムは目的が違う！
http://www.slideshare.net/greenmidori83/ss-28443892
の42ページあたりからご覧ください。
シミュレーションしたい。
体裁は整え中・・・。
-
シミュレーション1、e=0.4
-
シミュレーション3、e=0.4
おわりに
- 手元の情報を生かしながら意思決定できる方法として、
「探索」と「活用」の考え方に基づくバンディットアルゴリズムを理解する - シミュレーションを通して、バンディットアルゴリズムのイメージをつかむ
発展
- Contextualなbanditなるものがあるらしい。
- http://www.slideshare.net/tsubosaka/introduction-contexual-bandit
- 男性/女性、年齢など、ユーザの情報を取り入れたwebマーケティングなどに応用可能
- LinUCBは代表的なアルゴリズム