検索エンジンのABテストで発生するユーザー内相関を突破する

この記事はエムスリー Advent Calendar 2021 1日目の記事です。明日からも面白い記事が続々投稿されるので、ぜひ購読・拡散お願いします！

qiita.com

エムスリーエンジニアリンググループ AI・機械学習チームでソフトウェアエンジニアをしている中村(@po3rin) です。好きな言語はGo。情報検索系の話が好物です。

最近検索エンジンの改善やアルゴリズムの変更などの効果を分析する機会が多くなってきたのですが、ABテストの効果検証でやらかしてしまい、改めてABテストについて復習しています。そこで「A/Bテスト実践ガイド」という本を読みました。

A/Bテスト実践ガイド　真のデータドリブンへ至る信用できる実験とは (アスキードワンゴ)

作者:Ron Kohavi,Diane Tang,Ya Xu,大杉直也
ドワンゴ

Amazon

この本で、私が陥った大量にクリックするユーザーやボットによって検定の結果が歪んでしまうユーザー内相関について学びました。今回は検索エンジンの評価を題材にABテストでのはまりポイントを私の失敗事例と共にまとめてみます。

今回の実験設定
t検定の簡単な復習
ランダム化単位と分析単位が違う時の問題
- CTRの落とし穴
- 分散の落とし穴
  - デルタ法
  - デルタ法を使った分散推定を使ったABテスト
問題に気づくためのAAテスト
インターリービング
まとめ
- We're hiring !!!
- Reference

今回の実験設定

よくある実験設定を考えます。検索エンジンの出力する結果をユーザーに見せることでCTRをABテストします。同じクエリAに対してコントロール群のユーザーにはアルゴリズムAが出す結果を、介入群のユーザーにはアルゴリズムBが出す結果を表出します。

f:id:abctail30:20211130233258p:plain — 今回のABテストアーキテクチャ

今回はCTRを指標としてABテストすることを考えます。ユーザーは全ユーザーを対象とし、ユーザーはランダムにコントロール群、介入群に割り振られます。

今回は検索エンジン以外でも使える指標としてCTRを採用していますが、検索エンジンの評価においては他にもP@k、nDCG、などの指標が考えられます。指標については「情報アクセス評価方法論」が非常に詳しいです。

情報アクセス評価方法論

作者:酒井哲也
コロナ社

Amazon

また、このエムスリーテックブログでも過去にsDCGというクエリ修正アクションも考慮した評価指標について解説したのでもしよろしければこちらもご覧ください

www.m3tech.blog

t検定の簡単な復習

t検定はt分布を利用する検定法です。

コントロール群と介入群で観測されたメトリクスを $Y_c$ , $Y_t$ とすると帰無仮説 $H_0$ と対立仮説 $H_1$ をそれぞれ

$H_0 : \bar{Y_t} = \bar{Y_c}$

$H_1 : \bar{Y_t} ≠ \bar{Y_c}$

2標本t検定ではt統計量を計算します。コントロール群、介入群の指標の値をそれぞれ $Y_c$ 、 $Y_t$ とおくとt統計量 $T$ は下記の式で計算できます。

$Δ = Y_t - Y_c$

$T = \frac{Δ}{\sqrt{var(Δ)}}$

ここで $var(X)$ は $X$ の分散の計算式です。このt統計量 $T$ はt分布に従うので、t分布表からp値を計算できます。慣習的に $p \lt 0.05$ である時に統計的に有意として帰無仮説を棄却します。

この辺の話を更に詳しく知りたい場合は東京大学出版会の「統計学入門」がおすすめです。

統計学入門 (基礎統計学Ⅰ)

東京大学出版会

Amazon

ランダム化単位と分析単位が違う時の問題

実は先ほどの問題設定を仮定した際の仮説検定には落とし穴があります。それはランダム化単位と分析単位が異なるという問題です。

ランダム化単位とは今回の例で言うとユーザーであり、ユーザーをランダムにコントロール群、介入群に振り分けています。分析単位とは今回の例で言うと CTRの計算のために検索結果を表示するページビューになります。このランダム化単位と分析単位が異なっているといるとユーザー内相関が発生し、正しい仮説検定が行えないなどの問題が起きます。

どのような問題が起きるのかを2つ紹介します。

CTRの落とし穴

CTRを計算する際によく行われるのは全てのクリック数を総ページビュー数で割ったものではないでしょうか？これをページビューベースのメトリクスと呼びます。

ランダム化単位と分析単位が違う今回の場合では、大量にクリックするユーザーなどの外れ値に対して非常に弱く、仮説検定の際に問題になります。

例えば下記のような場合を考えましょう。

ユーザー	PV	クリック
A	3	1
B	3	1
C	10	10

この場合、CTRは

(1 + 1 + 10) / (3 + 3 + 10) = 75%

となります。C以外のCTRは1/3ですが、Cというユーザー(もしくはボット)が全てクリックしているためCTRが跳ね上がっています。そこで別のCTRの計算方法では、各ユーザーのCTRを個別に計算して、それらの平均をとります。これをユーザーレベルメトリクスの平均と言います。先ほどの例を使うと

(1/3 + 1/3 + 10/10) / 3 = 55.5%

となります。先ほどの定義よりもユーザーCの影響を抑えることができています。

まとめると、2つ目のCTRの定義であれば大量にクリックするユーザーの影響をある程度緩和できるので、ランダム化単位と分析単位が異なる状況においては2つ目の定義のCTRも見ておくと良いでしょう。

２つ目の定義の欠点としては逆に、クリックが少ないユーザーの重みが強くなってしまうのが問題です。特にクリック数の多いヘビーユーザーの数を重視したい場合などは1つ目の定義の方がいいかもしれません。

他にも後で紹介するデルタ法でヘビーユーザーの影響などを排除する方法があります。

分散の落とし穴

ページビューベースのメトリクスを再度考えましょう。ランダム化単位と分析単位が異なっていると分散の推定を正しく行えません。下記は分散推定の計算式ですが、この式はそもそも標本が独立同分布(i.i.d)であるという仮定を持っています。

$var(Y)= \frac{n}{n-1} \sum_a^{n=1} ( Y_i - \bar{Y} )^2$

ここで $\bar{Y}$ はメトリクス $Y$ の平均を表します。今回の実験設定では、Yiは表示ごとにクリックされたかどうかであり、同じユーザーからのクリックが含まれるため独立でなく、仮定に違反しています。例えば一人のユーザーやボットが異常にクリックする確率が高い場合には相関が発生してしまいます。よって上記の分散の推定式を使用してCTRの分散を推定することは厳密に正しくありません。

まとめるとランダム化単位と分析単位が違う場合は相関によってt統計量の計算にも影響を与え、仮説検定の結果を歪める恐れがあります。

正しく分散を推定するためにデルタ法を利用します。

デルタ法

デルタ法は、確率変数の関数をテイラー展開することで、変換された確率変数の平均や分散を変換前の平均や分散の値で推定する方法です。デルタ法を利用すると分散は下記のように推定できます。

$CTR = p/v$

$var(CTR) = \frac{1}{N}\ (\frac{1}{\bar{v}^2} var(\bar{c}) + \frac{\bar{v}^2}{\bar{c}^4} var(\bar{v}) -2 \frac{\bar{c}}{\bar{v}^3} cov(\bar{c}, \bar{v}))$

ここでCTRは今回の例で言うと $v$ はviewであり。 $c$ はclickです。 $cov(X, Y)$ は $X$ 、 $Y$ の共分散です。 $N$ は標本数です。この式の導入を細かく説明すると非常に長くなるので、僕が参考にした記事を引用するのでそちらを参照してください。

www.szdrblog.info

デルタ法を使った分散推定を使ったABテスト

Pythonで実際にCTRをシミュレーションして、デルタ法の実装をみてみます。

Pythonのバージョンは3.9で、実装で使用するモジュールは下記になります。

import math
from random import randint

import pandas as pd
import numpy as np
from scipy import stats

今回はPV、CTR共に正規分布に従うとしてデータを生成します。コントロール群のCTRは30%、介入群のCTRは31%であるという状況を大雑把に作ります。CTRの平均の計算は先ほど紹介したユーザーレベルメトリクスの平均を使ったCTR計算を使うので、このタイミングではユーザーごとのCTRも計算しておきます。

click_control = [randint(0, 30) for i in range(10000)]
view_control = [randint(1, 100) for i in range(10000)]

click_treatment = [randint(0, 31) for i in range(10000)]
view_treatment = [randint(1, 100) for i in range(10000)]

control = pd.DataFrame({'click': click_control, 'view': view_control})
treatment = pd.DataFrame({'click': click_treatment, 'view': view_treatment})

例えばcontrolは下記のようになります。

      clicks  views       ctr
0         33     96  0.343750
1         22    105  0.209524
2         34     95  0.357895
3         40     92  0.434783
4         38    102  0.372549
...      ...    ...       ...
9995      32    115  0.278261
9996      33    113  0.292035
9997      53     93  0.569892
9998      22    105  0.209524
9999      39    109  0.357798

次に、デルタ法でメトリクスの比の分散を推定する式を実装します。

def var_delta(x, y):
  mean_x = np.mean(x)
  mean_y = np.mean(y)
  var_x = np.var(x, ddof=1)
  var_y = np.var(y, ddof=1)
  cov_xy = np.cov(x, y, ddof=1)[0][1]
  result = (var_x / mean_x**2 + var_y / mean_y**2 - 2 * cov_xy /
            (mean_x * mean_y)) * (mean_x * mean_x) / (mean_y * mean_y * len(x))
  return result

この関数を使ってABテストを行い、p値を出してみます。

def ttest(mean_x, mean_y, var_x, var_y):
  diff = mean_y - mean_x
  var = var_x + var_y
  stde = 1.96 * np.sqrt(var)
  z = diff / np.sqrt(var)
  p_val = stats.norm.sf(abs(z)) * 2

  result = {'difference': diff, 'p-value': p_val}
  return pd.DataFrame(result, index=[0])

これらの関数を使って最終的な出力を見ることができます。

# 分散
var_c = var_delta(control['click'], control['view'])
var_t = var_delta(treatment['click'], treatment['view'])

# 平均
mean_c = control['click'].sum() / control['view'].sum()
mean_t = treatment['click'].sum() / treatment['view'].sum()

result = ttest(mean_c, mean_t, var_c, var_t)
print(result)

結果は下記のようになります。

  warnings.warn(msg)
   difference   p-value
0    0.008971  0.011113

ちなみに介入群のCTRの設定をコントロール群と同じ30%にすると当然ながらp値が0.8や0.5などの大きな値になることが確認できます。

   difference   p-value
0    0.000039  0.992062

問題に気づくためのAAテスト

上記で扱ったユーザ内相関のような問題に気づけるようにするためにはAAテストをするのが良いでしょう。 AAテストはABテストの開始前にさまざまな問題に気づく為の非常に有用な手法です。ABテストのようにユーザーを2つに分けて、同じ内容のものをテストします。

これにより、正しくユーザーが50%ずつ振り分けられているかや、バイアスが入っていないかなどをABテストを行う前にチェックできます。

アーキテクチャとしては下記の図のようになります。

f:id:abctail30:20211130233335p:plain — AAテストのアーキテクチャ

実際に弊社の検索エンジンをABテストする際にもAAテストで気づけた問題がありました。弊社でユーザーをランダム化単位としてCTRを計測したところコントロール群と介入群で $N$ %の有意な差がつき、喜んでいたのですが、ABテストをやる前のログからAAテストを行ったところ、そもそも最初からコントロール群と介入群でCTRに $N$ %の差がついてしまっていたことが判明しました。AAテストをせずにこの結果を持って意思決定していたらと思うと恐ろしいです。

ABテスト前にはAAテストを行うことをお勧めします。

インターリービング

今回は検索エンジンのオンライン評価をそれぞれの群に出し分けるアーキテクチャでしたが、ユーザー内のバイアスを防ぐための別の方法として、インタリービングという方法で２つの検索結果を混ぜてユーザーに見せる方法があります。今回は詳細な説明は省きますが、下記の記事が詳しいので是非読んでみてください。

data.gunosy.io

インターリービングは非常に強力な手法ですが、実装コストが発生し、かつインターリービングする分パフォーマンスにも影響を与えます。そのため、今回のアーキテクチャにするかインターリービングにするかはメリデメを考えて採用しましょう。

まとめ

今回は私が検索エンジンのABテストで陥っていたユーザー内相関を突破する方法を紹介しました。私自身、検索エンジンのABテストを行う中で、正しくABテストをすることの難しさを改めて認識しました。ABテストに関してはこのブログで大いに参考にした「A/Bテスト実践ガイド」が最高すぎて今年買ってよかった本No.1だったのでおすすめです。本日紹介したTipsを開発に活かしていただけたら幸いです。

エムスリー Advent Calendar 2021には続々と面白い記事が公開されていく予定なので、是非購読ボタンをお願いします！

qiita.com