著者: Brian Karrer, Liang Shi, Monica Bhole, Matt Goldman, Tyrone Palmer, Charlie Gelman, Mikael Konutgan, Feng Sun
所属: Facebook
選んだ理由
A/B テスト周りが気になっていた
統計学的な知識の涵養と,スケールさせるためにどういうシステムになっているのかの技術的関心
まとめ
Facebook, LinkedIn, Netflix など大規模なオンラインサービス
実験としてユビキタスに商品(サービス)変更のための効果測定 A/B テストをしている
ユーザ単位での「ランダム化試験」が一般的:user_id のようなものをハッシュ化して数値の範囲で割り振るみたいな
そのときの A/B 二群(control v.s. treatment)の差を見ることで効果を測る
平均因果効果(平均処置効果):2群の平均の差 $ \mu_A - \mu_Bなど
ランダム化試験の仮定として安定単位処理値仮定(SUTVA: Stable Unit Treatment Value Assumption)がある
「テスト被験者(ユーザ)の観測値(潜在アウトカム)は,他のユーザのテスト割り付けによる影響を受けないはず」
これが崩れると困る
しかし,テストには干渉 (ネットワーク効果)が存在する場合がある
もし干渉があるなら,SUTVA 違反のため,ユーザ単位でのランダム化試験による検定は適切ではない
たとえば Facebook のような SNS では,A/B テストの切り分けとは別にユーザ間の連絡が機能としてあるため,これが干渉かもしれない:この機能自体の A/B テストとかはどうするんだろう?
ユーザ単位のテストのみを行うと,テストの影響を見誤ってしまうかもしれない
そのため「クラスター無作為化試験」がある
ユーザをある単位のクラスターにまとめて,その中での干渉は許容しつつ,クラスター間での干渉を取り除くような工夫をすると,干渉の影響のない推定値(高精度な平均処置効果の推定値)が期待できる
Facebook では大規模なクラスター無作為化試験まで行えるような,実験実行フレームワークがある
この論文ではそのフレームワークの仕組みや理論周りの説明をしている
さらに,このフレームワークではネットワーク効果による干渉があるかどうか・どれくらいの大きさかを定量的に判断することもでき,それによって設計したクラスタリングが有用だったかを遡って判断できる
論文内では,ネットワーク効果は干渉よりも狭義なので,干渉については触れず「ネットワーク実験(Network Experiment)の実行」と呼ぶ
実データを用いて干渉に関わる実験をしているものは珍しいのが推しポイントと主張
実際に SUTVA 違反となる(既存のユーザ単位ランダム化試験では誤った判断をしていたであろう)実験の例を2つ挙げている
Instagram ストーリーの閲覧 UI を変えたとき,リアクションの変化を作成者(リアクションの受け手)側はどう感じるか
実行した洞察として,いままではサイズバランスのとれたクラスタでの実験や推定に焦点が当てられてきたが
提案手法(混合型・かつクラスタのバイアスが偏っている)は同等あるいはそれ以上の統計的検出力を持ち,干渉をよりよく抑えることができる
どのユニット(ユーザ)が処置を受けたかを記録する「トリガーロギング」という手法がさらに分散を低減する
このトリガーという概念は LinkedIn の実験基盤にもある(まだ読んでない...)
まずは細かい話は置いておいて,6章の具体的なケーススタディを紹介
実験例1
背景: Instagram ストーリーの実験
Facebook Stories Viewer Experience チームで Android と iOS ユーザを対象に,新しい返信デザインに関する2週間の混合ネットワーク実験(A/B テスト)を実行した.
ユーザーが Facebook ストーリーを閲覧すると,
コントロール群:すべての emoji が入った水平スクロールバー(図3左)が表示される
テスト群:テキストの返信ボックスの横にひとつだけアイコンがあり,クリックするとすべての絵文字がポップアップする
Android テスト群:青いサムアップ(図3右)
iOS テスト群:透明なハート(図3中)
https://gyazo.com/2940f06630ead6402f23cf44307412ce
左がコントロール群,中が iOS テスト群,右が Android テスト群.
ユーザランダム実験の結果
ストーリー視聴者:直接的に処置の影響を受け,emoji の使用率と(反応の)送信率が減少する
ストーリー作成者(視聴者の反応をもらう側):視聴者のうちテスト群・コントロール群両方からのフィードバックを受けるので,まとめて集計するとこちらへの効果が検出されなかった
これが SUTVA 違反ではないか?ということ
けど視聴者 UI が変化したことで起こった↑の現象に対して作成者の体験がどうなるのか,行動がどう変わるのかはちゃんと知りたいよね(もちろん変化はないのかもしれないと思いつつ)
ストーリー作成者への間接的な処置効果を測りたいので,作成者への視聴者の干渉を軽減し,ネットワーク効果の有無や大きさを推定する混合実験を行うことにした
仮説
関心のあるメトリクス一例
ストーリー視聴者の emoji 返信
ストーリー視聴者のテキスト返信
ストーリー作成者が受け取った emoji 返信
ストーリー作成者が受け取ったテキスト返信
毎日活動している(投稿している)ストーリー作成者数
フィードバック(視聴者からの返信)を1回以上受け取ったストーリー作成者数
フィードバックを1回以上受けとったストーリー作成者数割合
仮説は「新しい体験(処置)が,直接的にストーリー視聴者からのテキスト返信を増やし,軽量な返信(emoji のみの返信)を減らす」
< emoji を押しにくくするような UI にするのと同義なのでそうなるだろうなと思う
混合実験の関心:作成者のメトリクスに関する下流処理効果(間接的な影響?)についてと,クラスタランダム化された推定値とユーザランダム化された推定値の比較について
うまいクラスター無作為化では,視聴者の返信と作成者への影響のテスト-コントロール間の干渉が減少することでユーザ無作為化の推定値との差が大きく測定されるはず
https://gyazo.com/9f4c27e5367348972545612d3d465419
arXiv 版にはあった仮説的な因果関係のグラフを載せておく(ACM では消えているので微妙なやつかもしれないが)
結果
https://gyazo.com/428b364f2fa7ac1e5d434a7418a6a9ed
一番左 cluster test - cluster ctrl 列: クラスタランダム化をした状態での比率推定量の点推定・95%信頼区間
仮説と一致している
視聴者の emoji 返信 23.8% ↓, テキスト返信 11.1% ↑
作成者の emoji 受信 6.4% ↓, テキスト返信 2% ↑
作成者側の効果は直接影響のある視聴者と比較して小さいけど,視聴者のリアクションの変化と一致していて,予想されていたものである
1日のアクティブ作成者が 0.25% ↓, フィードバックを1回以上受け取ったアカウントが 1.2% ↓, フィードバックを1回以上受け取ったアカウントの割合 0.9% ↓
左2番目 user test - user ctrl 列: 一般的なユーザランダム化での比較結果
作成者メトリクスに注目:干渉によって,メトリクスが有意でなく,cluster test - cluster ctrl 列と比較して少なくなっている
これがクラスタランダム化の有効性を示す証拠
cluster test - user test 列:
すべての作成者メトリクスでクラスタテスト群の推定値がユーザテスト群と有意に異なる(0 が範囲に入っていない)
クラスタテスト群の作成者は同じクラスタ内の視聴者からの返信が多くなる
つまり視聴者からは emoji の返信が少なく,テキストの返信が多くなり,総数として返信は少ない,1日のアクティブな作成者数は減少している
上記より,ネットワーク実験(混合実験)はこれまでのユーザ無作為化デザインよりも干渉を捉え,より妥当な推定値につながると主張する
分析方法のバリエーション
いままでやってきたのは回帰調整(共分散分析)を用いたユーザ部分母集団に関する結果
条件付き SUTVA テスト
https://gyazo.com/a14e3b150438f44e92565553163c8704
下4つの (*) がついている指標は条件付き SUTVA テストに失敗している.つまり,ユーザ間の干渉が発生している指標であるとわかる
なんで?...赤と緑が重なっていればクラスタ無作為化とユニット無作為化の平均値には差がないといえるため,ネットワーク効果(干渉)が発生していないと考えられる
実験例2
背景: 通勤圏(Commuting Zones)実験
Facebook の性質的には,ユーザのクラスタリング方法は実験例1のように友情ネットワークだったり,コンテンツ(ストーリー)の生産者と消費者の間のオンライン関与が考えられる
他に,地理的な位置によってクラスタリングが定義される場合もある.
特に,Jobs on Facebook (JoF) のような製品では個人が自分の所在地に近い雇用者と交流する可能性が高い
なので地理的なクラスタを用いた JoF の実験例を紹介
求人企業と Facebook ユーザを結びつけるサービス
求人企業が求人情報を掲載し,ユーザが応募できるようにする
二面性:ユーザの行動に影響を与える変化は,雇用者の行動にも影響を与える可能性がある
ユーザ無作為化実験では,これら全体的な効果を分離することは困難
応募の少ない求人案件を上位表示させることによる全体効果を把握したい
ユーザは最も採用されやすい雇用主と繋がれて体験が向上する
応募から得られる限界効用が最も高い(過去の取引実績の少ない)雇用主の体験が向上する
↑これによりもっと多くの求人情報が掲載され,求職者に多くの機会を提供できるかも
ユーザテスト
過去に応募の少なかった求人案件をブーストし,次の指標を追跡調査
プラットフォーム上で送られた応募
応募時に過去に応募のなかった案件に送られた応募(最初の応募)
クリエイター(雇用主)への影響の代理指標:雇用主への影響を直接測定するのは難しいので
問題:control - treatment の干渉がある
応募のない求人案件をブーストすると treatment 群の求人案件は知名度が上がり,多くのユーザが応募
しかし,その中には control 群の中でも応募してしまう人がいる
この干渉は,応募のない仕事へのブースト治療効果を誇張してしまう
ユーザは住んでいる場所で仕事を探すだろう
Facebook の Data for Good プログラムで利用できるクラスタリングである「Facebook の通勤圏」を使った
これによりcontrol - treatment 群のユーザ間干渉を考慮
https://gyazo.com/71ff6276096fb185600a03ea483c7b17
ジョブボードとブラジルの通勤圏 (Commuting Zone) の例
結果
常に新しい仕事を探しているユーザはごく一部なので,トリガーロギングが有効であると考え,混合実験を行った
https://gyazo.com/43721abe642d80a9b9f461d62c8c41ed
2.5 週間のテスト結果のまとめ
一列目のユーザ無作為化におけるユーザの過去に応募のない仕事への応募:71.8% ↑
大きくて嬉しい.しかしユーザ側の treatment 効果に上方バイアスがかかっていることが示された
二列目のクラスター無作為化実験だと 49.7% ↑
標準誤差を 30% 以上削減できる回帰調整の恩恵
通勤圏(地理的)レベルで無作為化することでいくつか確認できた
ユーザランダム化では,「過去に応募が0件の仕事への応募」指標に大きな偏りが生じる
このユーザ体験変更(掲載ブースト)は雇用者は多くの求人を掲載する原因となった
別求人の掲載確率は 17.0% ↑ (四列目)
このように,市場の健全性を保つためには相互作用を理解することが重要で,そのためにネットワーク実験をしようという話
フレームワーク実装
2つのことをしている
treatment(処置)の展開:どのユーザをどうテストするのか・しないのか
クラスタの管理:クラスタそのものの情報の管理・更新パイプライン(後述)
treatment の展開
図は左から右にながれる処理
https://gyazo.com/560ceba84a5514ec74a269527e1f9f72
要するに,あるユーザはそれぞれの実験に対して A/B のどちらに属するのかを割り振る
ユーザ(実験ユニット,図の色のついた点)とクラスタリング(大きな円)が母集団(ユニバース)
どのユーザをどうクラスタリングしているのかの情報すべてが universe
ユニバース名に基づいて universe segments にハッシュ化され,実験に割り当てられる.
この universe segment で任意の時点で複数の相互排他的な実験をユニバースに含めることができる
実験割当後,セグメントはハッシュによって2つに分けられる:混合試験
ユニットランダムセグメント:一般的なユーザ単位の A/B(ユニットランダム化試験)
クラスターランダムセグメント:クラスターランダム化試験
クラスタの管理
クラスタリングは時間の経過とともに陳腐化し,品質が低下すると思われる
新しいユニット(ユーザ)が参加したりして,実験上の母集団とサービスの母集団が乖離
干渉のパターンも変化するかもしれない
フレームワークでは新しい universe の作成・既存 universe クラスタリングの更新ができる
定期的にクラスタリングを再生成するパイプラインがある
名前・作成日の両方でインデックス化
名前:比較対照できる,時間経過で生まれるシーケンスを示す
e.g. Facebook のフレンドシップグラフを週単位でクラスタリング
検索は Key-Value サービスを名前と日付の両方でインデックス
universe は作成時にクラスタリング名と日付が割り当てられる
universe をリフレッシュするには,その universe に対する実行中の実験をすべて停止する
そうしたら日付を入れ替えられる
使い続けたい,有効だと思っている universe のある実験者に継続性を与える
トリガーロギング・不可知論的回帰調整推定量について
不可知論的とは?...能動学習という分野で使われている,ノイズ分布等に仮定を置かない
トリガーロギング
フレームワークを呼び出した際に
ユニット(ユーザ)の割り当てが計算される
(universe名, 実験名) を Key-Value ストアに投げてユニット i のクラスタを問い合わせる
クラスタを持っていない/クラスタが実験に割り当てられていないなら実験母集団から除外
つまり,デフォルトのコントロール処理
この呼び出しと割り当ては個別に記録される(トリガーロギング)
LinkedIn のテスト基盤にも記述がある↓
2.2.1 Logging
モニタリングや分析をサポートするため、アプリケーション層で「getTreatment」を呼び出す際に、タイムスタンプ、testKey、実験名、ID(実験単位)、バリアントなどの情報を含むイベントが記録される。これらのイベントはKafkaトピックに保存され、定期的に HDFS クラスタに ETL され、データワークフローで使用されます。
これらの実験イベントは、LinkedIn.com へのリクエストごとではなく、「getTreatment」コードが呼ばれたときのみ発生することに注意することが重要です。これはログのフットプリントを減らすだけでなく、実際に実験の影響を受けたユーザーのみを A/B テスト分析に含めるトリガー分析も可能にします。例えば、LinkedIn.com のデイリーユーザーは 2000 万人ですが、そのうち実際に実験が行われている「求人」ページを訪れたのは 200 万人だけということもあり得ます。このようなトリガー情報がなければ、特にトリガー率の低い実験では、実験の本当の影響をノイズから切り分けることは困難である。
トリガーによるロギングでも、発生するイベントの量は課題となっています。現在、毎日平均100億のイベントが生成され、その数は、増加するユーザーベースでより多くの実験が実行されるにつれて急速に増加しています。私たちは過去に何度かイベントスキーマと生成条件を見直し、派生する属性を削除し、値をエンコードしています。今後も、この課題に対処するための新たな解決策を見出すために、継続的な改善努力が必要です。
まとめと感想
Facebook の A/B テスト基盤の紹介,実際のテストと分析を元に,クラスタベースのランダム化実験が必要な場合を紹介した
アーキテクチャが抽象的なので実装ってなるともうちょっと詰めなきゃいけないが,混合実験の気持ちはわかった
Gunosy ではクラスタベースのランダム化実験が実施されているのだろうか
実施されているとしたら,どのような部分で活用されているか
実施していないとしてら,どこに活用できそうか
因果推論とか統計の用語が絡んでくるあたりはまだ理解が怪しい...
4.4 Agnostic regression adjustment がまだうーんという感じ
クラスタランダム化だとサンプル数が少ないので分散が大きく信頼区間の幅が良くない,これを改善するモチベ
クラスタベースの回帰調整で分散低減!らしい
Uber とかもやっている因果推論の CUPED (controlled-experiment using pre-experiment data )法の親戚っぽい
処置前のデータから時間的発展を予測しておいて,実際の処置後データとの乖離から影響を図るっぽい
予測モデルの精度が大事そう
本文中にも CUPED 法が言及されていたので関係あるかなと