RのContextualパッケージをいじってみた際のメモ書き

はじめに

このブログの私の中での位置づけは、今後仕事で使いそうなものを調べて書き溜めるというところにあります。仕事で使っているものはブログに載せないというスタンスでもあるのですが、出来るだけ先回りしておきたいところです。今回は、昨年のJapan.RやTokyo.Rで紹介されていたcontextualパッケージを触ってみたというゆるふわな内容となっています。

目次

・バンディット問題とは
・マーケティング関連でバンディット問題が役に立つ場面
・バンディット問題で出てくる数学的な知識と方策
・Contextual Bandit問題とは
・Contextualパッケージでできること
・サンプル実行
・おわりに
・参考情報

バンディット問題とは

「選択肢の集合から1つの要素を選択して、その選択肢に対する報酬を得るものの、他の選択肢の報酬情報は得られないというプロセスを繰り返す設定において、報酬の合計値を最大化することを目指す逐次決定問題」とされています。バンディットは昔ながらのスロットマシンが客からお金をむしり取ること(盗賊)にちなんでいるそうです。胴元は盗賊ということなんでしょうか?

大学時代の知人は毎日パチンコ屋に行ってから講義に行っていましたが、出そうな台・出そうな店を転々としていましたが、あれはバンディット問題を彼なりに解いていたのでしょう。当時はサクラの台というのがあったらしく、3000円ほど投資すれば大当たりになるのだとか。そしてその大当たりに釣られて他の客が頑張るという意味で、サクラの台だそうです。

マーケティング関連でバンディット問題が役に立つ場面

私はマーケティング×データ分析を生業としているので、マーケティング方面にしか関心がないのですが、バンディット問題は役立つ可能性が十分にあるというか既に一部の企業ではバリューを出しています。

・インターネット広告配信:オレシカナイトでSpeeeの方がトンプソン抽出で精度を増していた。
・推薦システムにおけるコールドスタート問題:ネットフリックスが情報推薦の際にContextual Banditを適用

バンディット問題とは異なるものの、最適腕識別問題においては、クックパッドのクリエイティブ出し分けやGoogleのウェブテスト(旧Webサイトオプティマイザー)などで使われています。ちなみに、バンディット問題と最適腕識別問題は似て非なるものであるということを『バンディット問題の理論とアルゴリズム』で知りました。

また、マーケティングとは違いますが、株価のトレーディングの際にバンディットアルゴリズムを使っているという事例(Bandits and Stocks)が当然ながらあるようです。

バンディット問題で出てくる数学的な知識と方策

バンディット問題の書籍を読もうとすると、数理統計学の知識が必要です。

あるスロットを何回引くべきかという意思決定の際に、「神のみぞ知る真の報酬」と「あるスロットの報酬」がどれくらい外れているか、そしてそのハズレ具合は許容できるのかということが重要になります。
「神のみぞ知る真の報酬と、あるスロットの報酬がΔだけ外れている確率」の推論の精度に関心があるということです。

バンディット問題において、「その時のベストのスロットを引いた際のリターン」と「その時実際に選んだスロットのリターン」の差の期間合計値をリグレットとして、そのリグレットを小さくするようにスロットを選びます。
そのリグレットに対して理論的な下限を求める際に、数理統計学の知識が必要になります。

具体的には、ヘフディングの不等式、その前提となるマルコフの不等式やチェビシェフの不等式やチェルノフ限界、積率母関数やイェンセンの不等式などです。
それらを駆使しながら、様々な施策の中で、理論的な下限がより小さくなるようなものを探そうという流れのようです。

『バンディット問題の理論とアルゴリズム』を読む上で前提となっていそうな知識として、スタンフォード大学の講義資料(CS229 Supplemental Lecture notes Hoeffding’s inequality)を運良く見つけることが出来たので、これをもとに学ぶと理解が捗ると思います。

リグレットの下限を低めることを目指して、様々なアプローチが議論されます。

ε-貪欲法

  • 概要:スロットを回す回数のうち、一定割合(ε)をスロットの探索に当て、残りの期間を良いとされるスロットを回し続ける。
  • メリット:実装が容易でシステムに組み込み易い
  • デメリット:期待値が悪いスロットも良いスロットも同じ回数引いてしまうので性能が悪くなる。スロットの種類が多い際はより一層悪くなりやすい。

UCB(Upper Confidence Bound)方策

  • 概要:標本平均に補正項を足した、UCBスコアを各時点ごとに計算し、最もスコアが高いスロットを回す。なお、補正項は選択回数の少ないスロットに対して大きくなります。
  • メリット:ε-貪欲法と異なり、リグレットの上限がεなどの水準に左右されない。ハイパーパラメータが少ない。
  • デメリット:真の期待値についての信頼区間を求めることは本質的ではない。

KL-UCB

  • 概要:KLダイバージェンスを用いてUCBスコアを計算し、最もスコアが高いスロットを回す。
  • メリット:KLダイバージェンスを様々なモデルに応じて置き換えることができるなど、柔軟性がある。
  • デメリット:KLダイバージェンスの逆関数を計算する必要があり、毎回ニュートン法などを適用する必要がある。

MED(Minimum Empirical Divergence)方策

  • 概要:期待値最大である際の尤度が一定以上のスロットを回すという方策。
  • メリット:KLダイバージェンスの逆関数を計算する必要がない。
  • デメリット:KL-UCBよりも性能が悪い。IMEDという方策であればその弱点を克服している。

トンプソン抽出

  • 概要:期待値最大でないスロットの選択数の期待値を近似的に最小化するという取り組みを、ベイズ統計の枠組みで行ったもの。
  • メリット:経験的に高い性能となりやすい。
  • デメリット:?

Contextual Bandit問題とは

ある時点のあるスロットの報酬が、ユーザーの特徴量と誤差項により線形で表すことができるものを、線形バンディットと呼びます。
ユーザーの各行動の特徴量が時刻により異なる値を取ることを許すという設定を、文脈付きバンディット(Contextual Bandit)と呼びます。
つまり、Contextual Banditは時刻により異なるユーザーの特徴量が与えられたもとでの、利得の期待値の最大化問題となります。

具体的には、パチンコ店における期待値最大化の行動を考えるとすると、パチンコ台の大当たり確率は、午前か午後か、大当たりが既に他の台で出たか、その台がどれくらい回されているかなどの時間による文脈に左右されるという状況となります。

このContextual Banditにおいても、先程あげたようなリグレットを最小にするような様々な方策があります。LinUCB方策や、線形モデルのトンプソン抽出、ロジスティック回帰モデルのバンディットなどです。

Contextualパッケージでできること

こちらの資料にある通り、バンディットアルゴリズムのシミュレーションとオフライン評価が行えるパッケージです。
多様なバンディットアルゴリズムを試すことができます。
要となるデータですが、シミュレーションにより生成することもできれば、過去にランダムに出し分けたログなどのデータがあればそのデータをもとにアルゴリズムの検証をすることができます。

サンプル実行

さて、今回は完全に手抜きです。GitHubにあったサンプルコードを3つほど回すだけです。ただ、特徴量の突っ込み方などをサンプルコードから学べるので、ぜひ開発者のGitHubをご覧ください。

サンプル1:ABテストによる最適腕選択

パッケージのGitHub
にコードがありました。Bandit Algorithms for Website Optimizationという書籍に登場してきている例をRで実行できるサンプルです。
・ε-貪欲法を様々なεでシミュレーションして最適なスロットを見つける
・ソフトマックスによる方策に関しても様々なτに応じたシミュレーションをして最適なスロットを見つける
・UCB方策によりシミュレーションを行い、最適なスロットを見つける。ε-貪欲法やソフトマックスとの比較を行う
という実験ができます。シミュレーションの設定として、スロットごとの当たりの出る確率をベクトルで指定しています。

実行するのに10分くらいはかかるかもしれません。

ε-貪欲法

・最適なスロットを選んだ確率

・平均報酬額

 ・累積報酬額

ソフトマックスによる方策

・最適なスロットを選んだ確率

・平均報酬額

・累積報酬額

UCB方策

・最適なスロットを選んだ確率

・平均報酬額

・累積報酬額

サンプル2:文脈付きバンディット問題で映画のレーティングの最適化

同じGitHubにあるこちらのコードは、映画のデータセットに対して、文脈付きバンディット問題でオフラインテストをするためのコードです。映画のレーティングが4以上なら1そうでないなら0のデータを作り、特徴量として映画館で見たか家で見たか、一人で見たか家族と見たか、週末に見たかどうかなどの変数を7個ほど作成しています。方策としては、ランダムなもの、ε-貪欲法、トンプソン抽出、LinUCBをシミュレーションしています。

実行してから処理が止まるまで1時間程度はかかりましたが、LinUCBが累積の報酬が大きいようです。

サンプル3:文脈付きバンディット問題でMovieLensのTop50の作品における評価の最適化

こちらのコードは、MovieLensのデータセットにおいて、特徴量として過去にユーザーが評価した映画のカテゴリーの割合を19カテゴリ分用意して、ユーザーの見た映画の評価を最も高めるという、文脈付きバンディット問題です。こちらは実行して、30分程度で処理が終わりました。先程のサンプルと同じで、LinUCBが累積の報酬が大きいようです。

おわりに

2~3年前に、Tokyo Web Miningの懇親会でContextual Banditの論文いいぞとテラモナギさんが紹介していて、へー、そんなのあるんだと、「へー」の域を出なかったんですが、一歩前進した気がします。先人が切り開いた道を2~3年後に舗装されてから通るというのも遅いなと感じられるので、残業もっと減らして勉強時間増やしたいと思います。

参考情報

バンディット問題の理論とアルゴリズム (機械学習プロフェッショナルシリーズ)
Bandit Algorithms for Website Optimization: Developing, Deploying, and Debugging
Contextual package ~ Japan.R Shota Yasui
Package ‘contextual’
バンディットアルゴリズムの復習3:UCB(Upper Confidence Bound)

多腕バンディットモデルに関する参考文献

多腕バンディットモデルについて調べた際の文献です。

バンディットアルゴリズム入門と実践
http://www.slideshare.net/greenmidori83/ss-28443892
目的
・限られた施行回数の中で、最も良い選択をすること。
背景
・大体のことはやってみないとわからない。
・何度繰り返しても100%正しく知ることはできない。
解説
・探索(Explore)→不確実だが行ったことのない店に行ってみる。
・活用(Exploit)→実績ある行きつけの店に行く。
・探索と活用のトレードオフ
・選択肢(アーム)
・引く
 アームを選択して結果を得ること
・探索
 アームに関する情報を増やすためいアームを引くこと
・活用
 今持っている情報から最も良いアームと判断できるアームを引くこと
・epsilon-greedy
 探索と活用を確率的に行う
・epsilon-first
 ある一定期間完全に探索を行い、その後の期間は活用のみを行う
・softmax
 当たる確率の高いアームを高い確率、当たる確率の低いアームを低い確率で引くことで、探索と活用を行う
・Upper Confidence Bounds(UCB)
 アームについてどれだけ知っているかの情報を考慮に入れてアームを選択、知らないアームについて積極的に探索
・Bayes
 ベイズ確率を計算して、良いアームの確率が最も高いアームを引く
・ユーザーのクラスタに応じて、バンディットアルゴリズムで施策を打てば、one to oneマーケティングに近づけるかも

バンディットアルゴリズムによる最適化手法
https://www.oreilly.co.jp/books/9784873116273/

johnmyleswhite/BanditsBook
https://github.com/johnmyleswhite/BanditsBook

バンディットアルゴリズムによる最適化手法 4章
http://hagino3000.blogspot.jp/2014/05/banditalgo4.html

A/Bテストよりすごい?バンディットアルゴリズムとは一体何者か
http://qiita.com/yuku_t/items/6844aac6008911401b19

Bayesian Bandits – optimizing click throughs with statistics
https://www.chrisstucchio.com/blog/2013/bayesian_bandit.html

Beta-distribution Bandit
https://gist.github.com/stucchio/5383015#file-beta_bandit_test-py

雑談
先日、強化学習に明るい方の話を伺ったのですが、A/Bテストはどちらが良いかノウハウが溜まる観点からすると、良い試みなので、多腕バンディットと単純比較するのはあまりしないとおっしゃられていました。それでもやはり、最終的に良い方に表示がされるようになるはずなので、無駄の多いA/Bテストよりも、強化学習を使ってサイトとしての収益を重視した方がいいのだろうという話で落ち着きました。
アイテム数が多い場合は強化学習も大変だと思いますが、2つのクリエイティブの出し分けとかならカジュアルに実装できそうですね。