LinkedinでInvalidなA/B テスト検知するための方法論を紹介している論文を読みました

A/Bテストにおけるメトリック解析の話から、丁寧にメトリックを分解し、検知ロジックを提案しています。LinkedinのA/B テストプラットフォームで実際に動いてるみたいです

Introduction

まずはじめに、invalidなA/BテストにはInternally または Externally なテストがあることを紹介しています

Internally invalid とは？

Treatment と Control間の差がTreatmentによる効果と結論づけれるのが本来のA/B テストの魅力の1つですが、その差がTreatmentによる効果ではない ことを言います

特にこの論文では、incomparable samples（つまり、比較不可なサンプル群）における Internally invalidを紹介しています。LinkedinでのA/Bテストのうち10%ほどが発生していたと報告されています

比較不可なサンプル群って何？と初見では思うかもですが、今年のKDD2019でも話があったSample Size Ratio Mismatchの話はこれの1つに該当します

gingi99.hatenablog.com

Externally invalid な A/B Test とは？

実験自体は正しく行えていても、実験の設定を超えて結果を一般化したときに妥当性が維持できない ことを言います

これも初見では何？となりましたが、具体的な例を述べますと、実験の結果が例えば時間依存 または サンプルの集団依存 していただけであって、100%リリースしたら思ったより有効な効果がでないような話がこれに該当します

これら2つのInvalidなA/Bテストを自動で検知するアルゴリズムを考えたのがこの論文の貢献です

このブログでは、Externally invalid が興味深かったので、それについて紹介します*1

Triggered Analysis

Triggered Analysisとは聞き慣れない言葉ですが、これを理解することがExternally invalidの実例を理解する上でとても重要になります

これは要するに、評価したいモノを実際に体験したユーザのみ を含んだ分析のことを言います。つまり、Treatment郡の集団に属した人でも、A/Bテストで評価したいモノ（例えば画面）を見てない人を含めて良いんだっけ？ということが動機です。例えば、Daily Active User(DAU) が2億人のウェブサイトがあったときに、A/Bテストで評価したあるページのDAUが200万人であるなら、本来Treatmentすべてのユーザを含めると、せっかくインパクトがある変更でもNoise（体験していないユーザが99%にいるため）になってしまいます

このTriggered analysisには session-triggering と user-triggering の2種類があります*2

f:id:gingi99:20190317215938p:plain

みたとおり、session-triggeringとは、評価したいモノを体験したセッションのみ を解析する。user-triggeringとは、ユーザが一度体験してからのユーザのすべてのデータ を解析することを言います

この論文では、user-triggeringに絞ります*3

Cross-day vs Single-day Impact

どのユーザを使ってImpact（効果）を評価するかの考え方として、cross-day impact と single-day impact の2つを述べています

実験期間 $k$ 日あるとします

cross-day impact とは、1日目からt日目（ $1 \le t \le k$ ）までの どこかの日にトリガーしたすべてのユーザ を使って効果を求めるやり方です

single-day impact とは、t日にトリガーしたユーザ を使って効果を求めるやり方です

cross-day impactを評価するために、 $n^{[1,t]}$ を1日目からt日目までのサンプルサイズ、 $X^{[1,t]}$ をユーザ $i$ のメトリック、 $\Delta^{[1,t]}\%$ をパーセンテージインパクト（リフト）とみなすと、 single-day impactはそのまま、 $n^{[t,t]}$ 、 $X_{i}^{[t,t]}$ 、 $\Delta^{[t,t]}\%$ として評価すればOKです

cross-day impactはあくまで、一度でもtriggerすればそのユーザは評価対象に含まれます。つまり、ある日はtriggerしてなくてもそのときのそのユーザのメトリクス値もImpactを評価する際に使われるということです

Fully-covered vs Partially-covered Metrics

実験を評価するメトリックとして、Fully-covered と Partially-covered メトリクスの2つを述べています

fully-covered metrics とは ユーザがトリガーしないとメトリクスの計算ができない指標 のことです。サイトに訪れることがトリガーであるA/Bテストの場合、ページビューの合計はFully-covered metricsに該当します。つまり、ページビューの合計は、トリガーの影響を100%受けているからです。

partially-covered metrics とは ユーザがトリガーしなくても計算できる指標 のことです。あるページを見ることがトリガーであるA/Bテストの場合、ページビューの合計はpartially-covered metricsになります。つまり、ページビューの合計は、トリガーがなくても計算することができるからです。

In-trigger vs Off-trigger Impact

in-trigger impact は、ユーザがトリガーした日におけるtreatment impact のことです

off-trigger impact は逆で ユーザがトリガーしていない日におけるtreatment impact のことです

もちろん、fully-covered metricsのoff-trigger impactは常に0になります*4

External Invalidity

普通我々はA/Bテストの結果から、最も良いTreatmentを見つけて、100%のユーザに向けてテストした機能をリリースしていくかと思います。例えば、「この機能で○％良くなる結果を得たので、すべてのユーザに適用して、四半期経てば、△％の収益アップが狙えます」という感じですね

これは暗黙的に 別のサンプル集団 と時間というものに対しても一般化して考えてる自然な思考だと思いますが、実はこれが External Invalidity を引き起こし得ることを論文では述べています

1つ目を Generalizing beyond the experiment population と言っており、A/Bテストの実験集団のみでの結果はあくまである機能に対する Local Impact であると言っています。これをユーザ全体の Global Impact にするには、別の集団でもA/Bテストを複数行い、Site wide Impact を求め、Global Impactに転換していくことを述べています。Site wide impactとは、いわゆるサイト全体への影響を評価することを言います。詳しい内容は、以下の論文で紹介されているようです

dl.acm.org

2つ目の Generalizing over time が本論文で扱うExternal Invalidityになります。文字通り、メトリクスとは時間に依存してしまうがゆえにTreatment Effectを見過うことです

ここでさらに、この時間依存型のtreatment effectを novelty effect と trigger-day effect に分類しています

Novelty Effect

これは、ユーザの振る舞いの変化 に起因するEffectのことを言います。具体的には、最初にトリガーを体験したときと、何度もトリガーを体験したときでは、ユーザの反応は異なってきます。例えば、最初は通知に対してとても反応していたのが、だんたんと無視するようになるような行動の変化のことを言います

結果、ユーザがトリガーすればするほど、treatment effectは増加/減少します。これは以下の左図のとおり、single-day と cross-day impactの両方で強い一定の傾向をします

f:id:gingi99:20190824125424p:plain

まず左図を理解するために、まず右図を理解します。x軸が表しているのは、A/Bテストが開始してからの経過日数で、y軸は ユーザのトリガーした平均的な日数 です。これが増加するのは、A/Bテスト後に新たにトリガーするユーザが増えるためです。x = 1のときに、y = 1になるのは、トリガーした人のみを対象に数えるためですね。x = 2のときに、y = 1.7くらいでしょうか。2日経過して、2日ともにトリガーしたユーザと1日しかトリガーしていない人（1日目 or 2日目）がいるためですね。x = 3のときに、y = 2くらいなので、このA/Bテストでは、3日間のうちに1度以上トリガーした人は平均的に2日くらいはトリガーすると解釈すれば良いと思います

ここで左図を振り返ると、single-day impactのほうがA/Bテストが経過するほど、減少スピードが速いです。single-day impactは 各日でトリガーした人（初めてトリガーしたユーザ、もしくは何度かトリガーしているユーザも含まれる）のみ でインパクトを測ります。経過日数が立つほど、何度もトリガーしてる人が増えてくるため、後半の日ほどsingle-day impactは小さくなります。一方、cross-day impactはA/Bテスト開始日から、現時点までの どこかの日でトリガーしたユーザ でインパクトを測ります。Novelty Effectがある場合は、最初の体験時がImpactを大きくするため、そのImpact分が後半の日でも影響してくるため、このようにcross-day impactのほうがsingle-day impactより大きくなります

こういったNovelty Effectの特徴を使って、検知するアルゴリズム（以下のSTEP1とSTEP2）を提案しています

STEP 1

single-day impactを評価する回帰モデル $\Delta \%^{[t,t]} = \beta_0 + \beta_1 \frac{1}{t^{\alpha}} + \beta_2 \frac{1}{t^{\gamma}}$ を学習します。 $\frac{1}{t^{\alpha}}$ がslow-decay 項、 $\frac{1}{t^{\gamma}}$ が fast-decay項を表します。パラメータ $\alpha$ と $\gamma$ はLinkedinのこれまでの何千ものA/B test結果チューニングした値（例として、 $\alpha=0.35$ と $\beta=2$ ）を使っています。 slow-decayとfast-decayは以下のgradualとelbowタイプになると述べています

f:id:gingi99:20190824132245p:plain

STEP 2

Novelty effectが検知されたとフラグをつけるために、(a) STEP1で学習したモデルの決定係数が0.8より大きい（つまり十分single-day effectを捉えている）(b) 回帰直線が経過日数に対して単調増加/減少する (c) single-day impactが最も大きい日と最も小さい日で比較し、統計的に有意な差があるか。これらの3つの条件で判定します

最後に注意点として、あくまでSTEP1とSTEP2の評価により、single-day impactに強い傾向が見られることがわかるが、Novelty effectのせいでその傾向が起こってるかは保証できないことを述べていいます。当然ですが、曜日効果や季節効果 *5 により、このような強い傾向を観測することはあります。また、Novelty effectがどれくらいの程度であったかを評価するのも困難であることを述べています

ちなみに、LinkedinでよくNovelty effectが検知されるテストには、新しい機能に最初に触ったユーザは強い傾向を示すこと / 通知系のテスト / 推薦アルゴリズムなどでよく見られると述べています

Trigger-day effect

Trigger-day effectとNovelty effectの違いとして、cross-day impactに強い傾向があるのに対し、single-day impactがフラットになるといった特徴があります

f:id:gingi99:20190824134402p:plain

trigger-day effectがいつ起こるかというと、off-trigger impactとin-trigger impactに大きな違いがあるとき に発生します

例えば、トリガーが"通知を送る"、メトリックがTotal Page ViewであるA/Bテストを想像してみましょう。トリガーを受けた日には2つのページを1度ずつ訪問し、それ以外の日はいつものページを1度訪問するだけである場合を考えると、ある週でのリフトは 8/7 - 1 ≒ 14.3%です。つまり、 in-trigger impactは100%、off-trigger impactは0%、すべての日で見たcross-day impactは14.3% になります。結果、single-day impactはin-trigger impactとほぼ同じとみなすことができるため一定のimpactが観測され、cross day impactはin-trigger と off-triggerの混合した結果になるので、テストが経過するにつれて増加/減少していきます

ここからtrigger-day effectを検知するアルゴリズムを提案しています

まずメトリックを分解していきます。 $X_i$ がユーザ $i$ のテスト期間中のあるメトリックの値の合計とします。それを、トリガーした日のメトリックの値の合計 $I_i$ とトリガーしていない日のメトリックの値の合計 $O_i$ に分解します（つまり、 $X_i = I_i + O_i$ ）

k日間のそのメトリックのリフトを以下のように定式化します（はてなのtex記法の挙動がよくわからなくなったので貼り付けます）

f:id:gingi99:20190824140515p:plain

f:id:gingi99:20190824142004p:plain

$w_k$ はin-trigger impactの重み係数として表現します

ここで、kを無限大に発散させたとき（つまり、経過日数をどんどん増やしていく）のことを考えると、ユーザがトリガーする確率が $p$ ならk日後までにトリガーしたユーザ数は組み合わせの計算式で求めることができます

f:id:gingi99:20190824142744p:plain

f:id:gingi99:20190824142901p:plain

これで $k \to \inf$ に発散させると、以下のように $w_k$ を得ることができます

f:id:gingi99:20190824142830p:plain

実際のwを求めてシミュレーションしてみると一致することが確認できます

f:id:gingi99:20190824142948p:plain

この定式化を使って、以下の2つの条件を満たすかどうかでtrigger-day effectがあるかを判定します

wが小さい（つまりテストがある程度経過している）、もしくはcross-day impactが圧倒的にsingle-day impactよりかつ一定の値を示している
2つのリフト $\Delta \%I$ と $\Delta \%O$ に有意な差がある

とくに、2つ目はDelta method*6を使って、 $var(\Delta \%I)$ と $var(\Delta \%O)$ で求めれば検定のための情報が出揃うので、判定可能になります*7

さいごに

ヒューリスティック感はありますが、実際解釈しやすく意味のあるImpact指標になっており使い勝手がよさそうでした。しかし、完コピするというより、こういうオリジナル指標をデータやサービスの特性に合わせて自分たちも作る必要があるなーと感じました

参考

LinkedIn の A/Bテスト基盤と文化（KDD2015のFrom Infrastructure to Culture: A/B Testing Challenges in Large Scale Social Networks）の内容を紹介してくれています。Linkedinのように企業独自の1000を超えるメトリクスの管理は参考になりますね www.flywheel.jp

*1:というのも、Internally invalid の章も読んだのですが、Sample Size Ratio MismatchについてはKDD2019の論文が詳しく、他の事象については腑に落ちなかったので

*2:図はWSDM2015 Diluted Treatment Effect Estimation for Trigger Analysis in Online Controlled Experimentsより引用

*3:一度トリガーを経験すると、あとの行動にも影響はなんらかの影響が出る可能性はあるなーと想像は付くのですが、そのようにデータを引っこ抜くETLのほうが大変な印象です

*4:トリガーしないとfully-covered metricsは0になるので、Off-tiggerな日は0ですよね

*5:Linkedin では実用上見たことがないらしい

*6:A Note on the Delta Method - https://u.demog.berkeley.edu/~jrw/Biblio/Eprints/%20M-O/oehlert.1992_American.Statistician_delta.method.pdf

*7:いつかブログで使い方を書くかも

OKIYUKI99 Blog

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

WSDM 2019 : How A/B Tests Could Go Wrong : Automatic Diagnosis of Invalid Online Experiments を読んだ