OKIYUKI99 Blog

データ分析や日常に関するブログ

KDD 2019 : Diagnosing Sample Ratio Mismatch in Online Controlled Experiments: A Taxonomy and Rules of Thumb for Practitioners を読んだ

KDD2019な時期がきましたので、A/Bテスト系の論文あるかなと探してたときに気になった論文を読みました。

Booking.comのDirector of Experimentation のLukas Vermeer氏のツイートより

dl.acm.org

自分的要約としては、 複数の企業（Microsoft、Booking.com、Outreach.io）のこれまでの知見を集結させて、A/BテストにおけるSample Ratio Mismatch（SRM）がなぜ発生してしまうのかの根本原因を分類し、原因調査の勘所とそれらの防止策をまとめた論文 です。

はじめに

MicrosoftのA/Bテストの例として、以下のようなカルーセル UI でカードの数を12から16個に増やした画面を用意し、どちらの画面が良いかを比較するA/Bテストが紹介されています。

f:id:gingi99:20190807223832p:plain

最初の期待では、16個に増やしたほうがユーザがカルーセルに魅力を感じ、クリックする回数が増えると予想し実験を進めました。しかし、全く反対の結果（つまり、多くのカードを見たユーザほど、カルーセルのクリック回数が有意に減少した）が検出されてしまいました。

なぜこれが起こったかを調べたところ、実験開始後に、A/Bテストに割り当てられたTreatmentユーザ数がControlユーザ数と比べて有意に少なかったことが原因でした。それが起こってしまった原因を特定し（後に理由はでてきます）、正しく検証した結果、期待どおりのPositiveな差を検出することができました。

まさにこの現象のこと、Sample Ratio Mismatch（SRM） と言います。つまり、A/Bテストのために割当したControl / Treatmentの2つの集団で、サンプルサイズが 期待どおりの比率で集まらなかった ことで、誤った結果を導いてしまう現象です。

期待どおりというと、例えば多くのA/Bテストでは、テスト対象ユーザを事前に見積もったサンプルサイズのとおり集め、2つの集団が 50 / 50 の比率でスプリットして、テスト対象ユーザをControl / Treatmentのどちらかに割り当てるかと思います。

しかし、実際にA/Bテストを開始しデータを集めると、予定通り50/50になるかと思いきや、集計時にA/Bテストの対象ユーザの比率が 50.2/49.8 (たとえば、821,588人 vs 815,482人) になることがあります。

なぜTreatmentのほうが少なくなってしまったのでしょうか？ただの偶然？そして、これが問題になるのか？とも思いますが、MicrosoftのTechnical FellowのRon Kohavi氏のTweetでもSRMによって本来Flatな結果だった実験も誤って有意差が検出されてしまう例を紹介しています。

また、この論文でも、この現象によりA/Bテストの結果の信憑性が損なわれるため、SRMが発生しているかどうかは検知する必要があると述べています。

この期待どおりになっていないを検出する方法として、統計的仮説検定の枠組みで考えると、カイ二乗検定を行えば検出できそうであることは想像がつくかと思います。

この論文の貢献は、カイ二乗検定などの検出方法についての議論をするのではく、 なぜこのSRMが起こるかを複数の企業のA/Bテストの経験値と調査した実績から分類し、体系立てた ところにあります。

つまり、 SRMが起こってしまう根本原因はこれかこれかこれか....のどれかだと分類し、分析者がSRMの調査のための指針書として役立ててもらう ことが狙いのようです。

MicrosoftとBooking.comとOutreach.ioの連名であることからも、複数の企業の協力によりこの論文が完成しています。

本題の内容に入る前に、スムーズに論文を理解するために、一般的なA/Bテストの4ステップをおさらいしておきます。このステップそれぞれにSRMが起こってしまうポイントがありそうだなーという気持ちで理解しておけばOKです。

(1) 実験の割当。ユーザを、2つの実験グループ（Control or Treatment）に割り当てます。

(2) 実験の実行。ユーザに実験のためのコンテンツが実際に配信され、ユーザが実験に参加できる状態になり、実験が行われます。

(3) ログの処理。ユーザの行動ログなどのデータが収集・処理され、分析できる形式に集約します。

(4) 分析。集約したデータを分析します（当たり前ですが）

SRMの理解

SRMを分類するためにどうしたかというと、この論文の著者の過去のケースを再度分析したり（10,000個にもおよぶ）、実際A/Bテストを行っている分析者のインタビューも含めた定量＆定性調査により分類しています。

インタビューに使ったスクリプトも公開されていました：SRM Interview Guide 2019

MicrosoftではそもそもSRMはどれくらい発生してるのかを調べたところ、調べたテストのうち約6%でSRMが検出されました。年間10,000以上のA/Bテストが走ってるプロダクトでは、1日に1度は発生していた試算だそうです。

f:id:gingi99:20190808213120p:plain

実際の分析者のインタビューの内容を紹介されています。そこでは、SRMの発生はA/Bテストにおいて深刻な問題である。またそれがなぜ起こったを特定するのに、何ヶ月もかかることがあったなどが紹介されています。 しかし、SRMを防ぐことも可能であることと、逆にSRMの発生がTreatmentユーザにPostiveな結果であると解釈することもできることが紹介されていました（たとえば、コンテンツのLoad のSpeedがTreatmentで改善した場合、そのLoad Eventに関するログが増加する可能性があるなど）。

5種のSRM

ここからSRMを実際に分類していきます。

1つ目が、実験に割当を行うステップで起こってしまったSRMを紹介しています。

この例では、あるA/Bテストの前に、A/Aテストの時点でSRMが発生したケースがあったそうです。

原因は、実験の割当システムで特殊なUser IDを持ったユーザでのテストの配信トラブル（あまり詳しいことは書いていませんでした）で、50/50でテスト対象者を割当るはずが、49.9/50になっていたことがわかりました。

また、複数の実験を継続的に行っていると、ある実験に参加した人が次の実験にも参加することによるキャリーオーバー効果（ユーザの実験慣れのようなもの）が発生する場合に、SRMが起こってしまったことを紹介しています。

テストを大量に同時に行っているMicrosoftだからこそのSRMな気もしました。

2つ目がA/Bテスト"実行中"（ここでは、1セッションが解析対象になっているため、実行中と言ったときには何かしらのスパンがあるイメージ）に起こるSRMです。

これは、Skypeの改善に関するA/Bテストで、TreatmentにはMLモデルを使ってバッファリングパラメータをオンライン更新し、通話品質を高めることができるかのテストでした。Controlは、予め固定されたパラメータを使っています。

この実験では、当然のようにTreatmentの品質が改善するとMicrosoftは予想していました。しかし、いざ評価すると、全く反対の結果（音声の歪みや遅延が増加）が示され、さらにTreatmentのセッション数（コール数）がControlと比べて30%も少ない結果が得られてしまったそうです。

この原因は、セッションの途中で実験のための非同期に設定がリフレッシュされてしまい、Treatmentユーザの割当が変更されてしまったことが原因であったとわかりました（つらすぎる...）

これにより、Treatmentユーザの30%が、結果としてTreatmentのログとして扱われていないことがわかり、リフレッシュにより品質劣化まで引き起こしてしまったようです。なんとかログを調べ尽くし、リフレッシュが起こっていないセッションのみを使って評価することになりました。

これは、SRMの問題というより、開発側のQAミスなのでは？と思いましたが、この問題からSRMの一般化を行っています。それは、(1) このセッションが実験対象になるときの振る舞い (2) 実験中（つまりセッション中）の振る舞い (3) そのセッションで生成されるログの振る舞いの3つで構成されることを述べています。(3)はログが発生する前にユーザがExitしてセッションが壊れるケースがあるので想像はつきますが、(1)と(2)はかなり丁寧にログを見ないと見つけることも一筋縄ではいかないだろうなと想像できます。また、品質のA/Bテストだからこそ起こる問題かとも思います。

これを検知する仕組みとしてBooking.comでは、データ収集時のログを丁寧に取得し、Treatmentで警告ログ（割当の変更など）が増えてないかなどをモニタリングする仕組みをいれているようです。クライアント側のデータといえば、一般的にはかなりノイズの多いデータになることが想像できます。そこから検知できる仕組みがすでに動いていることに感心しました。

3つ目がA/Bテストのログ処理中におこるSRMを紹介しています。

これは、最初に紹介した12枚のカードを16枚のカードに変更したA/Bテストで起こったSRMです。この実験では、Treatmentユーザ（16枚のカードを見る対象）の数が少なくなっていました。

この原因は、エンゲージメントが高いユーザがなんとログの処理中にBotに分類されて(!)、Treatmentユーザから除外されてしまっていたことがわかりました。 エンゲージメントが異常に高い（大量にカードを見ていた）ことにより、Bot検知アルゴリズムの閾値を超えてしまったそうです。

（Bot検知を開発してる側も、12枚のカードがきっとこれまでデフォルトでパラメータチューニングされてデプロイされている中、16枚のカードになるなんて思ってもいなかったのだろうと勝手に解釈してしまいました）

この問題をログ処理中のSRMであると一般化しています。実験時の生ログを分析ができるフォーマットにETLするときに不適当な処理が入ってしまう問題であると述べてます。このSRMは防ぐのが難しいとも述べており、個人的には納得できます。

4つ目が分析時に発生するSRMです。

これは一番想像しやすいSRMかと思います。分析時にさまざまFilterを入れることで、不適当にTreatmentユーザが少なくなってしまう、逆に多くなってしまうことはあるかと思います。とくにA/Bテストなので、Treatmentにしか無い機能がある場合だと、Controlと収集ログの特徴が変化してしまうことは想像できます。

5つ目が実験とは関係のない別の要因が干渉してくることにより発生するSRMです。

Microsoft Store のHomepageのリデザイン（画面イメージは下記）のA/Bテストをしたときに、Controlユーザのほうが多かったことがあったことを報告しています。

f:id:gingi99:20190808230245p:plain

この原因は、検索エンジンのキャンペーンにより、ユーザが割当とは異なる誤ったURLに強制的にリダイレクトされてしまったことが原因だったそうです。

これはインターネット上でのA/Bテストだからこそ、別の仕組みと干渉してしまうことはあると思うので、防ぐのが難しい気もします。ユーザ側で見えてる画面までをモニタリングするしかないのでは？とも思います。 実際、Microsoftでは、割当ユーザが正しい画面（URLのパラメータなども見て）を見ているかをチェックしているそうです。

ここまでの5つのSRMを最後の図でまとめています。赤い＊マークが複数の実験でインパクトを起こしうる原因です。読者はこの図を用いてSRMの根本原因がどこにあるかを探っていけばよいでしょう。

f:id:gingi99:20190808231150p:plain

10のSRM調査の指針

最後の章に、SRM発生時に調べるべき10の指針を示してくれています。最後の図と合わせて見ながら、これらを調べていけばよいでしょう。

  1. Examine scorecards : 分析時のフィルタがミスってないか調べよう

  2. Examine user segments: あるユーザセグメントだけに起こってないか調べよう

  3. Examine time segments: ある時間セグメントだけに起こってないか調べよう

  4. Analyze performance metrics: A/Bテスト時のログのパフォーマンスメトリクス（ページのロード時間などに差がないか）を調べよう

  5. Analyze engagement metrics: EngagementがTreatmentで高いなら、Engagementが低いユーザが原因で起こっていると考えられる。そのユーザを調べよう

  6. Count frequency of SRMs: SRMが複数のA/Bテストで発生してるなら、原因はA/Bテストシステムである可能性が高い

  7. Examine A/A experiment: A/Aテストで発生してるなら、原因はA/Bテストシステムである可能性が高い

  8. Examine severity: TreatmentとControlのサンプル比率が大きく偏っていたなら、ログ収集およびログ処理時にユーザが除外されている可能性が高い

  9. Examine downstream: データの収集から集約までのパイプラインを確認してみよう

  10. Examine across pipelines: パイプラインが複数ある場合、互いに比べてみよう

おわりに

SRMは結果の信頼性を損なうだけでなく、分析者の調査時間もかなり必要であることを最後まで強調しています。

理想的には、今回の論文でのベストプラクティス集を使うことなく（つまり、SRMに出くわすことなく）A/Bテストを回していきたいと思いますが、SRMに出くわしたときはこの論文にそって調査していければと思います。