概要

多腕バンディット テスト

Steven L. Scott、博士、経済アナリスト

Google アナリティクス ウェブテストの基盤を成す統計手法について説明します。Google アナリティクスでは、ウェブテストの手法として多腕バンディット方式を採用しています。多腕バンディット テストには、次のような特徴があります。

  • 最も利益の大きい選択肢の特定を目標とする
  • ランダム分布がテストの進行とともに更新される

「多腕バンディット(multi-armed bandit)」という名前は、それぞれに異なる見込み配当率が設定された、「One-armed bandit(片腕の盗賊)」というスロット マシンが複数並んでいる状況を模した仮説テストという意味を持っています。スロット マシンのプレイヤーは、最も見込み配当率が高いスロット マシンを見つけ出す必要がある一方で、利益を最大化する必要もあります。この状況では、これまでの配当率が最も優れているマシンのみをプレイするか、それともさらに配当率が高いマシンがある場合を想定し、別のマシン(配当率が劣る可能性もあるマシン)も試してみるべきか、というジレンマが生じます。Google アナリティクス ウェブテストでは、この多腕バンディット問題に対処するために構築された高度な数学モデルを使用します。

ここではまず、アナリティクスが多腕バンディット方式を使用する背景について説明します。その後、多腕バンディット アルゴリズムによって実施されるシミュレーション テストのサンプルを 2 つ挙げます。それからよくある質問をいくつか取り上げ、最後に計算や理論に関する専門的な内容を扱う付録資料を紹介します。

予備知識

バンディット方式の仕組み

アナリティクスでは 1 日 2 回、テストの状況に目を通して各パターンの掲載結果を確認し、各パターンに振り分けるトラフィックの割合を調整します。成果の高いパターンにより多くのトラフィックを集め、成果の低いパターンはトラフィックを減らします。こうした調整は、サンプル数と掲載結果を考慮に入れた統計上の公式(詳細は付録を参照)に基づいて行うので、偶然ではなく実質的な掲載結果の相違を確認できます。テストが進行するに従い、成果の違いが浮き彫りになってくるので、最適なパターンを選択できる確率も徐々に高くなっていきます。

メリット

一般的に多腕バンディット方式に基づくテストは、統計的仮説検定に基づく「従来型」の A/B テストよりも効率性に優れています。統計的有意性にも優れ、多くの場合、こちらの方が結果が早期にわかります。効率性が高い理由は、テストが終わるまで「最終結果」をただ待つのではなく、成果の高いパターンに徐々にトラフィックを集中できるからです。また、明らかに成果の低いパターンから有望なパターンへサンプルを振り向けられるので、結果も早期に判明します。このように成果の高いパターンでより多くのデータを収集できるため、「優良」と「最高」の区別も早めに判断できるようになります。

基本的に、バンディット方式のテストは効率性が高いため、テストをより多く実施できます。トラフィックは成果の高いページに自動的に集まるため、テストに割り当てるトラフィックの割合も増やすことが可能。

従来型の A/B テスト

コンバージョン率が 4% のサイトで、新しいパターンのページをテストするとします。実はこの新しいパターンは 5% のコンバージョン率を生み出せるのですが、テスト前の段階ではそれは判明していないため、テストを実施することになりました。そしてこのテストの目的は、有意な統計結果として 95% の確率でコンバージョン率 5% を達成できるパターンを割り出すことです。標準的な検出力計算1 では、有意な統計結果として、4% から 5% へのコンバージョン率上昇を達成できる確率が 95% のパターンを割り出すためには、22,330 回の訪問数(オリジナルとパターンに 11,165 回ずつ)が必要となります。この場合、1 日の訪問数が 100 回だとすると、テスト終了までに 223 日間を要することとなります。visits per day to the experiment, so the experiment will take 223 days to complete. つまり標準的なテスト手法では、223 日間かけて仮説検定を行ってから、結果がわかることとなります。

では、1 日あたりの訪問数が 100 回で、多腕バンディット方式を使用した場合を見ていきます。1 日目はオリジナルとパターンに約 50 回ずつ訪問が振り分けられ、結果が分析されます。ベイズの定理によって、パターンの方がオリジナルより優れている確率が計算されます2。1 からこの数字を引いた値が、オリジナルの方が優れている確率となります。1 日目はオリジナルが運に恵まれ、パターンより優れている確率が 70% となりました。この結果を基に、2 日目はトラフィックの 70% がオリジナルに、30% がパターンに振り分けられます。2 日目の終わりになると、それまでの全トラフィック(2 日分)が集計され、オリジナルとパターンのそれぞれが他方より優れている確率が再計算されます。これにより、3 日目にそれぞれに振り分けられるトラフィックの割合が決まります。一連の停止規則が満たされるまで、このプロセスを繰り返します(停止規則の詳細は後ほど説明します)。

図 1 は、この設定でテストを行った場合のシミュレーションです。オリジナル(黒い線)とパターン(赤い点線)に振り分けられるトラフィックの割合が対を成しながら交差を繰り返し、やがてパターンの他方より優れている確率が 95% のラインに到達しています(この 2 つの割合を足すと必ず 100% になるため、一方の割合が高くなると他方が低くなります)。このテストは 66 日間で終了し、テスト期間が 157 日間短縮されることとなりました。

図 1: シンプルな 2 本腕バンディット テストでの確率のシミュレーション図。この確率によって、日ごとにオリジナルとパターンに振り分けられるトラフィックの割合が決まります。

もちろんこれは一例にすぎません。アナリティクスではシミュレーションを 500 回再試行し、サンプリングの繰り返しの中でこのバンディット テストの精度を高めていきます。図 2 は、そうして得られた結果の分布を表す図です。このテストでは、検出力計算に基づく従来型のテストと比べ、平均して 175 日間テスト期間を短縮できます。結果が出るまでに必要なコンバージョン数も、平均して 97.5 回減らすことができます。

図 2 検出力計算に基づく従来型のテストと比較した場合に、短縮できる日数と削減できるコンバージョン数の分布。distributions of the amount of time saved and the number of conversions saved vs. a classical experiment planned by a power calculation. コンバージョン率はオリジナルが 4%、パターンが 5% の場合を想定しています。

では、統計的な有意性はどうでしょうか。データ量が少ないと、エラーが生じる確率が高まるのでしょうか。そうではありません。バンディット テストでは、上記の 500 回のテストのうち 482 回で、パターンの方がオリジナルより優れているという正しい結果が導き出されます。つまり 96.4% の確率ですが、従来型のテストとエラー発生率はほぼ同程度です。検出力計算方式よりも長い時間がかかったテストも数回ありましたが、全体の約 5% にすぎません(5/500)。

また、オリジナルのコンバージョン率が 5%、パターンが 4% として、逆の設定でもテストを実施しましたが、その場合でも対称的な結果が得られました。500 回のうち 482 回で、オリジナルの方がパターンよりも優れているという正しい結果が再度導き出され、従来型のテストと比較した場合に、短縮できる日数は平均 171.8 日、削減できる必要コンバージョン数は平均 98.7 回となりました。

テストの停止

デフォルトでは、バンディット テストは最低 2 週間は実施されるよう設定されています。それ以降は 2 つの指標を分析します。

1 つ目は、各パターンがオリジナルを上回る確率です。95% 以上の確率でパターンがオリジナルを上回ることがわかった場合は、成果の高いパターンが割り出されたことが明示されます。最短期間の 2 週間と、信頼レベル 95% という数字はどちらも変更できます。

分析される 2 つ目の指標は、「テストにおける残存潜在価値」です。これは複数のパターンがある場合に特に有効です。テスト中のあらゆる時点で、最も成果見込みが高い「チャンピオン」のパターンが割り出され、テスト終了時には、その時点でのチャンピオンが選ばれるパターンとなります。テストにおける「残存価値」とは、チャンピオン以外のパターンを選択した場合に増加するとみられるコンバージョン率のことを指します。テストを実施することの本質は、この価値を把握することにあります。チャンピオンが最も優れたパターンである確率が 100% の場合は、テストの残存価値はゼロとなり、それ以上テストを実施する意味はなくなります。しかしそのパターンが最も優れている確率が 70% の場合は、別のパターンの方が優れている確率が 30% となり、ベイズの定理によって、別のパターンがどの程度優れているのかを示す分布データが導き出されます(計算に関する詳細は付録を参照)。

Google アナリティクスでは、テストにおける残存価値が 95% 以上の確率でチャンピオンのコンバージョン率の 1% 未満であることが場合に、テストが終了します。1% 未満ではなく、チャンピオンのコンバージョン率の 1% 未満という意味のため、チャンピオンのパターンのコンバージョン率が 4% の場合は、テストの残存価値がコンバージョン率 0.04% 未満になるとテストが終了します。

残存潜在価値に基づくテストの終了は、同率のパターンがあるケースに対処できるため有効です。たとえば多数のパターンを含むテストでは、2 つ以上のパターンの成果が同程度になる場合もあるため、いずれかのパターンを選ぶということが重要ではなくなります。こうしたケースでは、最適なパターンが 2 つ以上あるため、最も成果が高いパターンが割り出されるまでテストを続けるのではなく、パターンを切り替えても有意な差異が生じないことが判明した時点でテストを終了することが重要です。

より複雑なテスト

従来型のテスト方式と比較した場合の多腕バンディット方式の利点は、テストの複雑性が増していくにつれ高まっていきます。ウェブページの改善方法について複数の案が考えられる場合もあるため、複数のパターンをテストしたいケースもあるかと思われます。たとえば、オリジナルの他に 5 つのパターン ページをテストするとします。この場合はオリジナルと最も成果が高いパターンを比較する計算を行うことになるため、多重比較を考慮し、ある種の調整を行う必要があります。保守的な手法ですが、ボンフェローニ補正を用いると効率的に調整を行うことができます。ボンフェローニ補正では、仮説検定の有意水準をテスト対象のページ数で割ることでこの調整を行います。標準的な検出力計算を有意水準 0.05/(6 - 1)で実行すると、テスト対象の各ページに 15,307 回の訪問数が必要という結果が導き出されます。オリジナルを含めた 6 つのページに必要な訪問数は計 91,842 回となり、1 日あたりの訪問数が 100 回だとすると、このテストに必要な期間は 919 日間(約 2 年半)ということになります。通常はこれほど長い期間をかけてテストを実施するというのは現実的ではありませんが、アナリティクスでは、シミュレーションとしてこのテストを実施できます。

バンディット方式のシミュレーション ツールで、計 6 ページのこのテストを実施した場合を見ていきます。前述の例と同様、オリジナルのコンバージョン率は 4%、最も成果が高いパターンのコンバージョン率は 5% だとします。その他の 4 つのパターンには、オリジナルを上回る 4.5% のコンバージョン率を持つ次点のパターンが 1 つ含まれており、成果の低いそれ以外の 3 つのパターンのコンバージョン率はそれぞれ 3%、2%、3.5% です。図 3 がテスト結果の分布です。平均テスト期間は 88 日間(従来型のテストでは 919 日間)、削減できる必要コンバージョン数は平均 1,173 回です。テスト期間の分布は広い範囲にわたっていますが(早く終わるとは限りません)、バンディット方式のテストでは、従来型のテストと比較して、削減できる必要コンバージョン数は最少でも 800 回に上ります。

図 3: ボンフェローニ補正に基づく検出力計算による従来型のテストと比較した場合に、計 6 ページのバンディット テストで削減できるコスト。左側は、テストの終了までにかかる日数を示した図です(縦軸は従来型の検出力計算で必要となる日数です。右側の図は、バンディット テストで削減できる必要コンバージョン数を示しています。

コスト削減の一因は、テスト期間を短縮できる点にあります。図 4 は、500 回のシミュレーションの初回で、オリジナルを含めた各ページに振り分けられたトラフィックの割合の履歴データです。最初のうちは成果が高いページと低いページを特定することに苦労していますが、それでも非常に早い段階で、成果の低いページに振り分けられるトラフィックは激減しています。このケースでは、オリジナルはテスト開始当初に運に恵まれたため、他のパターンよりも長い期間にわたってある程度のトラフィックが振り分けられています。約 50 日が経過した後は、有望なページが絞られ、オリジナルと最も成果が高いパターンの一騎打ち状態になっています。それ以外のパターンが効果的に排除された後は、この両者で 1 日あたり 100 回の訪問数を分け合っています。バンディット テストでは、経済的な面からも(最も高い収益性が見込まれるパターンに優先的に訪問数が振り分けられるため)、統計的な観点からも(最も情報が必要なパターンに訪問数が振り分けられるため)、効率的に訪問数を振り分けることができます。

図 4: 計 6 パターンのバンディット テストの初回シミュレーションで、各ページに振り分けられたトラフィックの割合。

図 5 は、「事前に」結果がわかっていると仮定し、最も成果が高いパターン 2 のみにトラフィックを振り分けた場合との比較で、多腕バンディット テストの実施にかかる 1 日のコストを示したものです(実際には最も成果の高いパターンがテスト前にわかっているということはあり得ないため公正な比較ではありませんが、バンディット テストの有効性を示すためにこの比較を用います)。オリジナルはパターン 2 よりもコンバージョン率が 1% 低いため、平均すると、オリジナルに訪問が 1 回振り分けられることで無駄になるコンバージョン数は 0.01 回分となります。同様に、たとえばパターン 5 の場合は、訪問が 1 回振り分けられることで無駄になるコンバージョン数は 0.03 回分となります(パターン 2 よりもコンバージョン率が 3% 低いため)。各ページに振り分けられる訪問数に各ページのコストをかけ、全体の総和を算出すると、それがテストの 1 日のコストとなります。従来型のテストでは、1 日ごとに各ページに訪問数が 100/6 回ずつ振り分けられます(平均値であり、部分観測の振り分け方法によって異なります)。これはつまり、従来型のテストでは 1 日あたり 1.333 回分のコンバージョンが無駄になるということになります。一方、図 5 の赤い線は、バンディット テストを実施した場合の 1 日のコストを表しています。時間の経過とともに見込みの低いページに振り分けられるトラフィックが減っていくため、テストのコストが下がっていることがわかります。

図 5: バンディット テストを実施した場合の 1 日のコスト。従来型のテストを実施した場合は点線で示されているとおり、一定のコストが発生し続けます。

1 この記事の検出力計算は、すべて R 関数 power.prop.test で実行されています。

2 計算の詳細については、付録をご覧ください。付録の参照は必須ではありません。