読者です 読者をやめる 読者になる 読者になる

About connecting the dots.

statistics/machine learning adversaria.

Optimizelyのstats engineによる逐次A/Bテスト

ABテストといえば,だいぶ前に有意とか検定とかそのあたりで,データ系の界隈がいろいろと盛り上がっていたのが記憶に残っているトピックなわけですが,今年の1月にABテストの大手Optimizelyのエンジンがリニューアルされてました.これがなかなか興味深いんで,今回はざっくりとその内容をご紹介します*1

とりあえず元ネタは以下の記事とテクニカルペーパーになります.

blog.optimizely.com

http://pages.optimizely.com/rs/optimizely/images/stats_engine_technical_paper.pdf

以下の内容は,基本的にはそこに書かれている内容の要約になります.

従来のABテストの問題点

これまでの,いわゆる古典的な統計学に従ったABテストの場合,以下のような問題があります.

  • 想定される差分やサンプルサイズについて,事前に見積もっておかないといけない
  • あらかじめ決めたサンプルサイズに達する前に何度も結果を覗くことで,間違った結果を得てしまうことがある
  • たくさんのバリエーションを一度にテストすることで,誤検出率が上がってしまう

サンプルサイズの事前見積もり

ABテストというのは,ようするに比率の差の検定なわけですけれども,実験的にこれを実施するためのお作法として,事前に想定効果を見積もって,それを検出可能なサンプルサイズを決定します.その上で得られたデータに対して,実際に差が出たかどうかを検定します.これは有名なスチューデントのt検定が,ビールの麦芽汁に酵母液をどれくらい入れればよいのかを決定するための手段として生み出されたように,生産現場において条件を変えて実験する,みたいなものにはとてもよく当てはまります.

しかしながら,Webの世界のABテストのように,サンプルは時間とともにどんどん入ってくるような環境だと,逆に足かせになります.穀物生産の現場ならいざ知らず,WebのUIテストのようなもので,事前に想定効果を事前に見積もるのは至難の技です.もちろんベースラインのパターンのコンバージョン率については,あらかじめログ集計でもしておけばいいわけですけれども,新しいパターンのデザインで3%あがるか,5%あがるかなんてよくわかりませんよね.

結果を何度もみることの影響

そしてABテストツールがあって,時間とともにサンプルが増えてコンバージョン率の折れ線グラフが更新されるというのに,事前に決めたサンプルサイズが溜まるまでそれを見ない,というのも現実的ではないわけです.コンバージョン率には揺らぎがあるため,実験期間中の短い間に5%有意ラインを超えることもよくあります.このときたまたま結果を眺めてたとしたら,差が出たと思って実験を早期に打ち切っちゃう(=偽陽性の結果となるわけです)なんてパターンがかなりあります.

以下の図は,Optimizelyの記事上にある画像を持ってきたものですが,ベースラインに対して新しい実験パターンのコンバージョンの方がずっと優勢なんですが,95%ラインを越えたり越えなかったり,という推移が見て取れます.ごく初期に95%を越えた段階で効果あり,と思って実験をストップしちゃうなんていうのは割とありがちな事態ではないでしょうか.

http://2nwl40151nra3yah86118nxtto0.wpengine.netdna-cdn.com/wp-content/uploads/2015/01/AA-test.png

誤検出率の向上

またABテストの優位性検定でみている有意性というのは,本当は差がないのに差があると判断しちゃう確率を一定以下(例えば5%)に抑える,という枠組みなわけです.しかしながら,同時に10パターンテストして,そのうち1つが(本当に有意な効果を持っていて)有意だという結果が得られたとします.しかし90%有意のテストだったとすると,10個のうち1個は,本当は効果がないのに有意であるという結果になってしまいます.本来はテスト全体で本当は効果がないのに有意である結果が得られる確率を10%にしたいのに,複数テストを同時に走らせることで,それよりもはるかに高い確率になってしまうわけです.

ソリューション

上記の問題を解決するために,彼らは以下の2つの枠組みを用いた新しいテストエンジンを作ったそうです.

逐次検定ベースのテスト

これまで,古典的統計学の枠組みにそった検定を行っていたことによる問題を,逐次検定を用いることで回避しました.逐次検定は,サンプルが追加されるごとに尤度比を計算して,その尤度比が想定していた閾値を超えた時点で有意とみなす,という手法になります.

実験群と統制群の比率の差分は,the law of the iterated logarithmに従って減衰するということらしく,それをモデルに取り入れた形でスコアを定義しました.数式書くの面倒なので,テクニカルペーパーのp7にある(2)式を参照してください.これにより,時間経過に伴う差分の変動を考慮した形で,第1種の過誤を一定に保ったまま繰り返し検定を行えるようにしました.

偽陽性率ではなく偽発見率

上で説明したように,複数パターンでの同時テストは,偽陽性率の上昇という大きな問題を抱えています.これを解決するために,彼らは検定全体で偽陽性が発見される確率=偽発見率を定義し,ベイズの枠組みを用いて信頼区間を定める形をとりました.信頼区間の上限は,以下のような式で定義されます.\thetaを実験群と統制群の差分,\hat{p}P(\hat{\theta}_n|\theta=0)\pi_0を帰無仮説が真である事前確率,iはABテストが行われた回数,Nはサンプル数です.

P(\theta=0|\hat{\theta}_{n,i})=P(\theta=0|\hat{p}_i)=\frac{\pi_0\hat{p}_i}{i/N}

すごくざっくりいうと,上の式で定義されるような,従来の偽陽性率よりも厳しい偽発見率という基準を用いることによって,第1種の過誤を減らす形の方策をとりました.これらの方略によって,従来数十%程度あった第1種の過誤が,一桁%にまで減少したそうです.

そんなわけで,すごいざっくりとしたOptimizelyのstats engineの紹介でした.このあたりの資料をいろいろみた挙句,そこまで頑張るならバンディッドでいいんじゃない? っていう感想が出てきたことはここだけの話です.

*1:細かい数式まわり,私自身もきちっと理解し切れているわけではないので,そこら辺解説してくれる人がいたら嬉しかったりします.