Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
KDD2022 paper (Non-stationary AB Tests)
Search
Toshihiro NAKAE
November 24, 2022
0
73
KDD2022 paper (Non-stationary AB Tests)
Toshihiro NAKAE
November 24, 2022
Tweet
Share
More Decks by Toshihiro NAKAE
See All by Toshihiro NAKAE
SIGIR2022 Paper (Optimizing generalized Gini indices for fairness in rankings)
tnakae
1
43
WSDM2021 paper (Online Experimentation with Surrogate Metrics)
tnakae
0
240
SIGIR2020 Paper (Recommendation for New Users and New Items)
tnakae
0
210
Featured
See All Featured
Bash Introduction
62gerente
608
210k
CoffeeScript is Beautiful & I Never Want to Write Plain JavaScript Again
sstephenson
159
15k
Reflections from 52 weeks, 52 projects
jeffersonlam
346
20k
Mobile First: as difficult as doing things right
swwweet
222
8.9k
5 minutes of I Can Smell Your CMS
philhawksworth
202
19k
JavaScript: Past, Present, and Future - NDC Porto 2020
reverentgeek
47
5k
Writing Fast Ruby
sferik
627
61k
I Don’t Have Time: Getting Over the Fear to Launch Your Podcast
jcasabona
28
2k
Java REST API Framework Comparison - PWX 2021
mraible
PRO
28
8.2k
The Pragmatic Product Professional
lauravandoore
31
6.3k
Bootstrapping a Software Product
garrettdimon
PRO
305
110k
Site-Speed That Sticks
csswizardry
0
36
Transcript
Non-stationary A/B Tests KDD22 関連有志読み会 株式会社ビズリーチ 中江 俊博 2022-11-24
自己紹介 中江 俊博 (なかえ としひろ) 株式会社ビズリーチ リクルーティングプロダクト本部 プラットフォーム開発部 AI1グループ Mgr
経歴 NTTデータ数理システム(-2018) データ分析コンサルタント TripleW(2018-2019) 排尿予測モデル実装 ビズリーチ (2019-現職) 推薦モデルなどの機械学習関連の 実装の統括担当 KDD22 関連有志読み会 / Non-stationary A/B Tests 2
今回対象となる論文 Non-stationary A/B Tests (KDD 2022) Yuhang Wu, Zeyu Zheng+
University of California, Berkeley と Amazon の混成チーム 要旨 A/Bテストの対象となるmetricsが、定常性を満たさない場合に、 A/Bテストの推定値の分散が大きくなるケースがある。 非定常であるmetricsに対して、A/Bテストの推定値の分散を 低減させる方法を提案 KDD22 関連有志読み会 / Non-stationary A/B Tests 3
問題意識 A/Bテスト対象のメトリクスの時系列変動が非定常である場合 A/Bごとにメトリクスの平均の差を出すと分散が著しく大きくなる。 図(論文Figure1)のように日内変動、曜日変動をするようなケース 変動要素が曜日などに依存することが既知であれば層別化/回帰すればよい では、単純な周期性に還元できない非定常の場合どうしたらよい? 時系列を等間隔に分割して層別化すればよい!(今回の提案) KDD22 関連有志読み会 /
Non-stationary A/B Tests 4
前提(1) 対象となるサンプルは 平均 の Poisson で到着 Treatment/Control の割り当ては、確率 の Bernoulli
で決める。 このようにして集められたサンプルが手元にあると考える。 KDD22 関連有志読み会 / Non-stationary A/B Tests 5
前提(2) Treatment/Control の時刻 でのメトリクス は、 時刻 に依存して平均/分散が変動しているとする。 A/Bテストにおける推定値 KDD22 関連有志読み会
/ Non-stationary A/B Tests 6
サンプル事後層別化 Treatmentへの割り当て確率 が、時刻に依存せず固定である前提で、 サンプルを 個集めた後で、均等に 個の区間に分割 そのあとで、層別平均の差の重み付き和をとる (Sample-based Post Stratification
; SPS) KDD22 関連有志読み会 / Non-stationary A/B Tests 7
サンプル事後層別化の分散 Theorem 3.1 もし でかつ なら ここで、分散 については ちなみに、naiveなA/B比較(サンプル平均の差)の分散と比較する SPSは
の差の分散、naiveは分散の重み付き和になっている KDD22 関連有志読み会 / Non-stationary A/B Tests 8
何を言っているのか? naiveの分散は、それぞれの時系列の分散の和 + の分散 SPSの分散は、その時点における平均の差の分散 + の分散 KDD22 関連有志読み会 /
Non-stationary A/B Tests 9
具体例 線形に変化するような場合 ( も同様に線形を仮定) 推定値の分散 に起因する分散 に起因する分散 が大きく、かつ値が非常に近い場合は、 sps は
naive に対する改善が非常に大きい KDD22 関連有志読み会 / Non-stationary A/B Tests 10
もっと一般的な状況 Treatment への割り当て確率 が時刻によって異なる場合 もし、各時点における到着密度 が正確にわかるのであれば は、サンプル数増加で真の推定値 に(確率)収束する。 dps =
De-biased Post Stratification dpsでは、各時点でA/Bテストに含める確率もバラバラでもよいらしい。 ただし、 が正確にわかるという前提を一般の状況で 仮定するのは難しいと思われる このdpsについては、論文での記載はややあいまい。 もう少しちゃんと書いてほしい (掘り下げる余地ありとみるべきか) KDD22 関連有志読み会 / Non-stationary A/B Tests 11
別の発想 : 到着順に割り当てる工夫 で割り当てるのであれば、到着順にA/B/A/B/.. と 割り当てるのもよさそう! ほぼ同一時刻で対になるサンプルを生成しているのと 同じとみることができるから。 この発想で、Treatmentへの割り当て確率が有理数 で、
出現する 個ごとに Treatment を 個割り当てた場合の A/Bテストの平均の差 についても sps と同程度の分散になる! tr : Time-grouped Randomization KDD22 関連有志読み会 / Non-stationary A/B Tests 12
実験結果 7日間で時刻/曜日変動があるようなダミーデータを Eコマースの実績データをもとに生成 A/B比率 とする。 手法 naive : A/B群の平均の差 psf
: 曜日ごと平均の差の平均 sps, tr : 提案法 結果 KDD22 関連有志読み会 / Non-stationary A/B Tests 13
まとめ 一般的な非定常の時系列となるA/Bテストで分散が小さくなる サンプル事後層別化 sps = Sample-based Post Stratification を考案 単なる層別化と比較しても分散が小さくなる
A/B群への割り当てを到着順に割り当てるような方法 (tr = Time-grouped randomization)でも sps と同等の分散となる KDD22 関連有志読み会 / Non-stationary A/B Tests 14