オバマ大統領の再選に大きく寄与したことで大きな注目を集めているA/Bテスト。A/Bテストを導入した、することを検討している、という開発現場も多いのではないだろうか。
そんな中、Web上で次のような議論を見つけた。
- 20 lines of code that will beat A/B testing every time
- Why multi-armed bandit algorithm is not “better” than A/B testing
一言でまとめると「A/Bテストよりバンディットアルゴリズムの方がすごいよ」「いやいやA/Bテストの方がすごいし」ということだ。
で、バンディットアルゴリズムとは一体何者なのか？
そこでBandit Algorithms for Website Optimization (O'REILLY)を読んでみた。その結果分かったことを踏まえてざっくりと解説する。（O'REILLYのサイトに行けば日本語版も売っている）
要約
バンディットアルゴリズムとは…
- 実データに基いてWebサイトなどの改善を行う手法の総称
- 活用（exploit）と探索（explore）の2つから成る
- さまざまなアルゴリズムが考案されている
この記事を読むと分かること
- A/Bテストの概要
- バンディットアルゴリズムの概要
- Epsilon-Greedy Algorithm
- 狭義のA/BテストはEpsilon-Greedy Algorithmにおいて
ε = 1の場合に等しい
この記事を読んでも分からないこと
- Epsilon-Greedy Algorithmより洗練された手法の詳細
- Softmax Algorithm
- UCB Algorithm
- バンディットアルゴリズムを実世界で利用する方法
そもそもA/Bテストとは何か
オバマ大統領の選挙キャンペーンで用いられ、再選に大きく寄与したことで一躍有名になったA/Bテストは、これまで人間の主観に依存していた様々な事柄の改善に対する意思決定方法を置きかえる、データに基づいた工学的なアプローチだ。
と、説明するとなんだか仰々しい感じがするが、その中身は気が抜けるほど単純である。
N種類のデザインを作ってユーザをランダムに振り分け、一番良い結果を導き出した法を採用する、という手法のことだ。A/Bテストという言葉はAとBという2種類のデザインを用いたために付けられた名前だが、別にNは2である必要は無い。ここでいう良い結果、というのは例えばコンバージョン率であったり、サイト滞在時間のような数値として計測できるものを用いる。オバマ大統領の選挙戦では選挙資金の寄付額などを用いたことが知られている。
大事なことは人の主観ではなくデータに基いて最適なデザインを模索するという点だ。データではなく主観に頼った場合、得てして発言力のある人の意見（CEOとかプロデューサーとか）が反映されることから、このような意思決定方法をHIPPO（Highest Paid Person's Opinion - 高給取りの意見）と呼ぶ。
しかしながら、A/Bテストという言葉は「人の意見ではなくデータに基いて判断する方法の総称」として扱われていることも多い。特に非学術的ニュースメディアではその傾向が強いように思う。下記に挙げる記事はその一例だ。
どちらが正しくて、どちらが間違っている、という話はここではしない。ここで言いたいのは、「A/Bテスト」という単語を見たときそれが広義の意味で使われているのか、狭義の意味で使われているのか、読者が文脈に応じて読み分ける必要がある、ということだ。
本稿は狭義の意味で用いている。
バンディットアルゴリズムとは
そんなA/Bテストと同じ文脈で語られる言葉に バンディットアルゴリズム （Bandit Algorithms）がある。これもA/Bテスト同様にデータに基づいた意思決定手法である。
これもA/Bテスト同様に複数のデザインを用意し、ユーザを振り分けて実際にテストして、その結果から最適なデザインを探すのだが、この個々のデザインを歴史的な経緯から 腕 （arm）と呼ぶ。
バンディットアルゴリズムは、もともとギャンブルに対する最適な戦略を考えることから始まった。
目の前に5つのスロットマシーンがある。それぞれのマシーンの当たる確率とその時の報酬は異なる。さて、手元に1000枚のコインがあるとき、そのコインをどのように配分すれば得られる報酬を最大化できるだろうか？
一般的なスロットマシーンには腕と呼ばれる棒がついており、コインを投入してその棒を引くとドラムが回転し始める。つまりここでやっていることは最も効率的な腕の引き方を考えていることと同じだ。
そういった訳で、バンディットアルゴリズムでは一つ一つのデザインを腕と呼ぶ。実際、Wikipediaでは Multi-armed bandit という名前の項目でバンディットアルゴリズムは説明されている。
そして、今の喩え話をWebアプリケーション開発の文脈に置きかえると、5つのデザインと1000人のユーザがいるとき、どのようにユーザを分配すれば最も効果的かを考える、ということになる。
バンディットアルゴリズムとA/Bテストは何が違うのか
それは既知の知識を活用するかどうかだ、と説明されることが多いようだ。
重要な要素として、バンディットアルゴリズムは 活用 （exploitation）と 探求 （exploration）の２つから構成される。活用は現時点で最もよいとされている腕を使うことであり、探求は候補の腕の中でどれが最も優れているかをテストすることだ。A/Bテストは全てのユーザを探求に割り振り、活用は行わない。
この立場からすれば「ユーザのX％でA/Bテストを実施する」というのは間違った表現だ、ということになるだろう。
何故バンディットアルゴリズムは"活用"を行うのか
何故バンディットアルゴリズムで活用を行うのか。
その理由を一言で言うなら リスクマネジメントの為 である。
バンディットアルゴリズムの目的は最良の腕を見つけることであることは間違い無いのだが、別に我々は研究目的でWebサイトを運営しているのではない。本質的には 収益を最大化すること が目的なのだ。その意味でこれまでに一定の結果を残してきた腕と、どんな結果をもたらすか分からない腕を同列に扱うことは、短期的な収益減のリスクを伴う。そこで、ある程度のユーザには現時点でもっともよいと思われるものを提示し、残りのユーザに対してテストを行うのだ。
A/Bテスト支持派の主張
多くの場合この"活用を行なう"という点においてバンディットアルゴリズムの方が優れていると説明されることが多いのだが、面白いことに、全く同じ理由でA/Bテストの方が優れていると主張する意見もある。つまり"活用が無い"からA/Bテストは優れている、というのだ。
何故A/Bテスト支持者が活用は不要だと考えるかというと、それは、スピードが損なわれるためだ。
ユーザを活用に回すとその分探求が遅れる。A/Bテスト支持派の意見は、多少の犠牲を払ってでも素早く最適な腕を見つけることが大切だ、というところに集約されるように思う。また、探求が早いということは直ぐに腕の良し悪しの区別がつくので、悪い腕を引き続けて損失が膨らむような愚は犯さない、ということでもある。
だが果たして本当にそうなのだろうか？例えば自動的に探求と活用の割合を調整するようなバンディットアルゴリズムであれば、ここでA/Bテスト支持派が行なっている指摘は意味を成さなくなるだろう。
バンディットアルゴリズムを評価する上でどのような評価軸があるのだろうか。
バンディットアルゴリズムを評価するための6つの指標
Bandit Algorithms for Website Optimizationではバンディットアルゴリズムを評価する6つの指標として下記のものが列挙されている。
| 指標 | 意味 |
|---|---|
| Curiosity | 探求から得られた知見を利用するか。一つ一つのテストは独立しているか否か。 |
| Increased Exploitation over Time | 自動的に探求の割合が減っていくか。 |
| Strategic Exploration | 何を最大化するか。利益か、得られる知見か、それともその両方か。 |
| Number of Tunable Parameters | 何個のパラメータを調整しなければならないか。（少ないほど良い） |
| Initialization Strategy | 各腕に対する初期値の割り当て方 |
| Context-Aware | ユーザと腕の相性などを考慮するか。例えば男性、女性を区別できるか、など。 |
Epsilon-Greedyアルゴリズム
バンディットアルゴリズムは活用と探求を行う、と言われてもピンとこないかも知れない。そこで最も単純なバンディットアルゴリズムである Epsilon-Greedyアルゴリズム を紹介する。
Epsilon-Greedyアルゴリズムの考え方は極めてシンプルで、0 ≦ ε ≦ 1を満たすεに対して、全てのユーザの内1 - εは活用、εは探求を行う。そして探求に割り当てられたユーザをテストしたい腕に改めて割り振る。このεの値を調整することで、活用と探求の割合を増減させることができるわけだ。
-
ε = 0の場合探求は一切行われないのでこれはバンディットアルゴリズムを使っていないのと同じ状況だ。 -
εを少しずつ増やしていくと、次第に探求の割合が増えていく。 -
ε = 1の時、活用は一切行われず全てのユーザが探求に回される。
そんなEpsilon-Greedyアルゴリズムだが、先ほど紹介した6つの評価指標に照らしてみると、いくつもの欠点があることが分かる。
| 指標 | Epsilon-Greedyアルゴリズムの評価 |
|---|---|
| Curiosity | 常に全ての腕が選ばれる確率が等しい。 |
| Increased Exploitation over Time |
εの値は一定なので、探求の割合は減少しない。 |
| Strategic Exploration | 何を最大化するか。利益か、得られる知見か、それともその両方か。 |
| Number of Tunable Parameters | 調整するパラメータはεの1つ |
| Initialization Strategy | 全ての腕が同じ評価 |
| Context-Aware | コンテキストは一切考慮しない |
Epsilon-Greedyアルゴリズムを改良する
Epsilon-Greedyアルゴリズムより優れたアルゴリズムは勿論存在する。Bandit Algorithms for Website Optimizationで紹介されているのは下記のものだ。（残念ながら各アルゴリズムの詳細を説明するだけの気力がないので、詳しく知りたい人は本書を実際に読んで欲しい。）
Softmaxアルゴリズム
Epsilon-Greedyアルゴリズムの大きな問題点の1つがCuriosity性が無いことだ。つまり、既にダメだと分かっている腕も等確率で選択されてしまい、損失が膨らむのだ。
Softmaxアルゴリズムは特にこの点においてEpsilon-Greedyアルゴリズムを改良したものになっている。探求が進む内に得られた期待値に応じて腕を重み付けし、それに基いて腕を選択する。またεの値を探求が進むに連れて自動的に増加させる、より発展的なアルゴリズムも紹介されている。これによってSoftmaxアルゴリズムは放置しておくだけで勝手に一番いい腕だけを使うようになるわけだ。
UCBアルゴリズム
Softmaxアルゴリズムは、各腕を引くことでどれだけ報酬が得られるか、という情報は使っているが、 各腕についてどれだけ知っているか は考慮されていない。つまり、本当は悪いのに良いと勘違いされた腕は、そのうち勘違いが是正されるが、本当は良いのに悪いと勘違いされた腕は無視されるのでいつまでも勘違いされたままになる可能性があるのだ。
UCBアルゴリズム（Upper Confidence Bound Algorithm）は名前からも分かるように、得られた評価値の信頼性を自動的に高めようとする。つまり、あまり良くわかっていない腕は積極的に試していくのだ。そのため本の中でも、Softmaxアルゴリズムに評価実験で劣るという結果が出た。だが、重要な点としてUCBはSoftmaxアルゴリズムと違って「Initialization Strategy」が自動化されるという強みがある。
また「Context-Aware」性を持ったUCBとしてLinUCBとGLMUCBという2つの改良版が紹介されている。LinUCBは線形回帰、GLMUCBは一般化線形回帰を用いて腕の価値を再評価する。（これらについては本書の中でも名前が紹介されている程度なので、詳しくは引用されている論文を当たらなければならない。）
現実的にバンディットアルゴリズムは使えるのか
最後に、このような理論を考えるときに重要なことは、その理論を現実の問題に応用出来るのか、ということだ。
が、この点についても7章で詳しく論じられているので詳しくはそちらを参照して欲しい。
結局バンディットアルゴリズムはA/Bテストより優れているのか
まず前提として、ここでいうA/Bテストとは「全てのユーザをランダムに振り分けてテストする」ものである、ということをご確認いただきたい。
この場合のA/Bテストはε = 1なEpsilon-Greedyアルゴリズムと等しい。故に「A/Bテストとバンディットアルゴリズムを比較すること」は「ゴールデンリトリバーと犬を比較すること」のようなもので、特に意味が無い。
A/BテストとEpsilon-Greedyアルゴリズムの比較という意味では、一長一短な面があると言えるだろう。Epsilon-Greedyアルゴリズムは非常にナイーブな実装であり、いくつもの問題を抱えているためだ。
その一方でEpsilon-Greedyアルゴリズムの問題点を改善した手法がいくつも提案されている。本稿とりあげたSoftmaxアルゴリズムやUCBアルゴリズムなどがその一例だ。これらとA/Bテストを比較するなら、バンディットアルゴリズムに軍配が上がると言えるのではないだろうか。
だが現実問題としてどれだけ実際のシステムの改善に応用出来るか、という話になると、実装コストなどさまざまな点も考慮しなければならなくなり、それらを勘案すると一概に「A/Bテストよりバンディットアルゴリズムの方が優れている」と言い切れないのではないだろうか。
合わせて読みたい
バンディットアルゴリズムの方が優れているよ、という趣旨のブログ記事。
上の記事に対する反論という形でA/Bテストの優位性を主張しているブログ記事。実際にA/Bテストとバンディットアルゴリズムの比較を行なっているが、ここで用いているのはEpsilon-Greedyアルゴリズムであることに注意。
バンディットアルゴリズムについての入門書籍。おそらくここまでしっかりまとまった本は他に無いのではないだろうか。洋書だが英文は簡単で比較的読みやすかった印象。古くからある知見に加えて、最近発表された学術論文の内容も取り扱われており、今後より深く勉強したくなった人のための文献紹介という面でも有用だと感じた。
翻訳和書。第2章の29ページ分がバンディット問題に関する、様々なアルゴリズムの効果と解説。