アナリティクス中野データ分析部の中村、中野です。今回から2回に分けてバンディットアルゴリズムをご紹介いたします。今回は基本編ということで「バンディットアルゴリズム」の基本的な思想と代表的な方策について簡単にご説明します。バンディットアルゴリズムはWEB広告配信やレコメンドシステム、はたまたトップ棋士に勝ち越したことで有名なアルファ碁にもその技術が応用されたことで注目を集めています。そもそも、バンディットアルゴリズムとはどういったものでしょうか。ややこしいその問題設定を丁寧に見ていきます。「限られた試行回数でできる限りいい選択肢を選んでいき、トータルの報酬を最大化したい」といったような問題設定です。WEB画面上に表示する広告や配信するコンテンツをどう選択するか、顧客にダイレクトメールを送る際の件名はどの候補がよいか、といったようにこのような問題はビジネスの現場でもよく見られます。重要なのはどの選択肢がよいか事前に情報がない、という点です。各選択肢について情報があるのであれば、それを学習データとして教師あり学習による予測モデルを作ることで事足ります。バンディットでは学習データがない状況からどの選択肢がよいかを学習しながら、その過程で得られる報酬を最大化することを目的としています。同じような設定でA/Bテストがよく用いられますが、バンディットと何が異なるのかを整理しましょう。A/BテストはAかBの2つの選択肢のどちらがより優れているかを統計学的仮説検定を元に判断する枠組みです。全体を2つのグループに分割し、あるグループにはAという選択肢、もう一方のグループにはBを適用し、その結果からAとBのどちらが優れているかを決定します。一度決定した後は優れた選択肢を選びつづけるというのが一般的です。A/Bテストは最適な選択肢を見つけるためのテストです。このように最適な選択肢を見つけ出す枠組みを最適腕識別と言い、A/Bテストはこの最適腕識別に分類されます。一方でバンディットアルゴリズムで目指すのは累積報酬の最大化です。有限回の試行の中で報酬を最大化するには、優れたアームを多く引き、劣ったアームは引く回数を抑えることが必要となります(バンディットの文脈では選択肢のことをアームと呼びます)。事前に各アームの良し悪しはわからないので、どのアームが良いかを探りつつ(探索)、良さそうなアームほど積極的に引いていく(活用)をバランスさせるのがバンディットアルゴリズムの本質です。どのアームが良いアームかについては、それまでに得られた報酬の標本平均などをアームごとにスコア化し、それらを比較することで判断します。そのため、ある時点で選択したアームの報酬が高ければ選択したアームのスコアが高くなり、報酬が低ければ選択したアームのスコアが低くなるといったように随時情報を更新しながらアームの良し悪しを判断していきます。バンディットアルゴリズムは、アームを選択した結果得られる報酬を動的に反映し、次のアームの選択に活かすことからA/Bテストに比べて機会損失の低減が見込めます。コンテンツの入れ替わりが多いようなケースではA/Bテストを都度設計するのは手間ですが、バンディットならシステム化できるというメリットもあります。Sampling方策の3つをご紹介していきます。単純な方策としてε-greedy方策が知られています。この方策では各ステップごとに確率εで探索、1−εで活用を行います。高かったアームを選択という方法でアームを選択していくことで累積報酬の最大化を目指します1。この方策はシンプルで判りやすいですが、最適な探索回数を見つけるのが困難という課題があり、探索と活用のバランスをうまく調整できないと次のような問題が生じます。累積報酬を最大化するためには最適なアームを多く引いていくことが重要ですが、選択回数が少ないアームについては報酬が正確に推定できていない可能性を考慮する必要があります。Bound)方策を紹介します。この方策では、アームを選択する際に毎回以下の式で表されるスコアを算出し、最もスコアの高いアームを引きます。少ないアームほど補正項の値は大きくなります。そのため標本平均は小さいが、選択回数が少ないアームも選ばれることがあります。単純に標本平均の大きなアームが選択される時は活用が行われ、標本平均は小さいが、選択回数が少ないアームが選択される時は探索が行なわれていると解釈できます。このようにUCB方策では探索と活用のバランスをうまくとりながらアームの選択を行い、報酬の最大化を目指します。「そのアームが最適なアームである確率」に注目した確率一致法という方法論があります。Samplingとはベイズ統計の枠組みをこの確率一致法に適用した方策です。」と解釈でき、数式を用いると以下のように表現できます。この式を各アームについて計算し事後確率を比較すれば良いのですが、一般にこの式を計算することは困難なことが知られています。実際に事後確率を直接比較する必要はなく、以下の手続きを行うことで「期待値最大の事後確率」に基づいたアームの選択を実現することができます。Sampling方策はUCB方策に比べて余分な探索が少なくなることが知られていて、有限の試行回数でより良い性能を達成することができます。Sampling方策)とランダムにアームを選んだ場合との比較実験を行います。実験では10本のアームを合計で10,000回選ぶ中で累積報酬を最大化することを目指します。得られる報酬は0/1のベルヌーイ分布に従い、パラメータpはそれぞれ以下のように設定します。10,000回)になります。結果にランダム性があるのでモンテカルロシミュレーションを行い、方策ごとの累積報酬の平均値で評価を行うこととします。実験の結果は以下の図のようになりました。(実験のコードはページ下部に記載)右の図がアルゴリズムごとの累積報酬を可視化した図で、方策ごとの平均累積報酬を表しています。方策に従ってアームを選択した場合では、ランダムに選択する場合と比べ累積報酬が高くなっていることがわかります。Sampling方策で約1,700回報酬を受け取っています。ランダムに選択した場合の累積報酬が約1,100回なので、50%以上の改善となりました。左の図はアルゴリズムことに最適アームの選択割合を可視化した図で、横軸が試行回数、縦軸が最適なアームを選択した割合を示しています。下の青い線がランダムにアームを選んだ場合で、およそ1/(アームの本数)の確率で最適なアームが選択されている様子が見られます(今回は1/10で10%)。紹介した3つの方策では、試行回数が多くなるにつれて最適なアームを選択する割合が多くなっている様子がわかります。Sampling方策が最も高く、最終的に約90%の割合で最適なアームを選択しています。ε-greedy方策とUCB方策について2つの図を見比べると、最適腕の選択割合(左図)ではε-greedy方策が割合が高いにも関わらず、累積報酬(右図)ではUCB方策の方が多く報酬を獲得しています。これは探索時にアームをランダムに選択するε-greedy方策と比べ、UCB方策はアームごとのUCBスコアに基づいてアームを選択することで悪いアームの選択回数を抑え、全体として比較的期待値の高いアームを多く引いたためと考えられます。実問題では報酬を最大化することだけではなく、計算効率についても考慮する必要があり、紹介した方策以外にもいくつかの方策が提案されています。今回は基礎編ということでバンディット問題の基本思想と代表的な方策についてご紹介しましたが、様々な応用問題も考えられています。アームから受け取る報酬の確率分布が時間変化する場合や、選択できるアームが時間変化する場合、アームごとに選択できる回数に上限がある場合などがあります。次回はそんな応用例の1つである文脈付きバンディット問題について紹介する予定です。Rewards")plt.show()最後になりますが、ALBERTでは、データサイエンティストを積極募集しています。採用ページをご覧ください。Optimization」のものを記述しています。↩Tweet中野データソリューション部の中野です。Rとpythonを中心に分析を行なっています。