dl.acm.org
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
みたとおり、session-triggeringとは、評価したいモノを体験したセッションのみ を解析する。user-triggeringとは、ユーザが一度体験してからのユーザのすべてのデータ を解析することを言います
この論文では、user-triggeringに絞ります*3
Cross-day vs Single-day Impact
どのユーザを使ってImpact（効果）を評価するかの考え方として、cross-day impact と single-day impact の2つを述べています
実験期間
日あるとします
cross-day impact とは、1日目からt日目（
）までの どこかの日にトリガーしたすべてのユーザ を使って効果を求めるやり方です
single-day impact とは、t日にトリガーしたユーザ を使って効果を求めるやり方です
cross-day impactを評価するために、![n^{[1,t]}](https://chart.apis.google.com/chart?cht=tx&chl=%20n%5E%7B%5B1%2Ct%5D%7D)
を1日目からt日目までのサンプルサイズ、 ![X^{[1,t]}](https://chart.apis.google.com/chart?cht=tx&chl=%20X%5E%7B%5B1%2Ct%5D%7D)
をユーザ
のメトリック、![\Delta^{[1,t]}\%](https://chart.apis.google.com/chart?cht=tx&chl=%20%5CDelta%5E%7B%5B1%2Ct%5D%7D%5C%25)
をパーセンテージインパクト（リフト）とみなすと、
single-day impactはそのまま、![n^{[t,t]}](https://chart.apis.google.com/chart?cht=tx&chl=%20n%5E%7B%5Bt%2Ct%5D%7D)
、![X_{i}^{[t,t]}](https://chart.apis.google.com/chart?cht=tx&chl=%20X_%7Bi%7D%5E%7B%5Bt%2Ct%5D%7D)
、![\Delta^{[t,t]}\%](https://chart.apis.google.com/chart?cht=tx&chl=%20%5CDelta%5E%7B%5Bt%2Ct%5D%7D%5C%25)
として評価すれば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の両方で強い一定の傾向をします
まず左図を理解するために、まず右図を理解します。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}}](https://chart.apis.google.com/chart?cht=tx&chl=%20%5CDelta%20%5C%25%5E%7B%5Bt%2Ct%5D%7D%20%3D%20%5Cbeta_0%20%2B%20%5Cbeta_1%20%5Cfrac%7B1%7D%7Bt%5E%7B%5Calpha%7D%7D%20%2B%20%5Cbeta_2%20%5Cfrac%7B1%7D%7Bt%5E%7B%5Cgamma%7D%7D%20)
を学習します。
がslow-decay 項、
が fast-decay項を表します。パラメータ
と
はLinkedinのこれまでの何千ものA/B test結果チューニングした値（例として、
と
）を使っています。
slow-decayとfast-decayは以下のgradualとelbowタイプになると述べています
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がフラットになるといった特徴があります
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を検知するアルゴリズムを提案しています
まずメトリックを分解していきます。
がユーザ
のテスト期間中のあるメトリックの値の合計とします。それを、トリガーした日のメトリックの値の合計
とトリガーしていない日のメトリックの値の合計
に分解します（つまり、
）
k日間のそのメトリックのリフトを以下のように定式化します（はてなのtex記法の挙動がよくわからなくなったので貼り付けます）
はin-trigger impactの重み係数として表現します
ここで、kを無限大に発散させたとき（つまり、経過日数をどんどん増やしていく）のことを考えると、ユーザがトリガーする確率が
ならk日後までにトリガーしたユーザ数は組み合わせの計算式で求めることができます
これで
に発散させると、以下のようにを得ることができます
実際のwを求めてシミュレーションしてみると一致することが確認できます
この定式化を使って、以下の2つの条件を満たすかどうかでtrigger-day effectがあるかを判定します
- wが小さい（つまりテストがある程度経過している）、もしくはcross-day impactが圧倒的にsingle-day impactよりかつ一定の値を示している
- 2つのリフト
と 
に有意な差がある
とくに、2つ目はDelta method*6を使って、
と
で求めれば検定のための情報が出揃うので、判定可能になります*7
さいごに
ヒューリスティック感はありますが、実際解釈しやすく意味のあるImpact指標になっており使い勝手がよさそうでした。しかし、完コピするというより、こういうオリジナル指標をデータやサービスの特性に合わせて自分たちも作る必要があるなーと感じました
参考
LinkedIn の A/Bテスト基盤と文化（KDD2015のFrom Infrastructure to Culture: A/B Testing Challenges in Large Scale Social Networks）の内容を紹介してくれています。Linkedinのように企業独自の1000を超えるメトリクスの管理は参考になりますね
www.flywheel.jp
