トリガー分析による検出力の改善

## 概要
トリガー分析とは、A/Bテストにおいて、実験の影響を受けなかったユーザーを分析から除外することです。トリガー分析によって検出力の向上が見込めます。トリガー分析はユーザーの部分集合に対する分析なので、トリガー分析からユーザー全体に対する効果を知るには追加の計算が必要になります。実験群によってトリガーされたユーザーの比率が異なる場合やトリガーされなかった集合の介入効果が大きい場合は、分析の妥当性が損なわれているおそれがあります。Counterfactual loggingと呼ばれるテクニックを用いると、分析時のトリガー条件の判定が容易かつ確実になりますが、パフォーマンス上の悪影響などを考慮したうえで実装するべきです。

## トリガー分析
トリガー分析とは、A/Bテストにおいて、実験の影響を受けなかったユーザーを除外して分析を行うことです（ランダム化単位がユーザーでないこともありますが、便宜上、ランダム化単位としてユーザーを想定します）。

ここで、「影響を受けない」とは、どの実験群に割り当てられてもユーザーの体験が変わらないことを意味します。例えば、Webサイトのアカウント削除ページに表示される文言を変更する実験では、アカウント削除ページを訪れなかったユーザーは、どちらの実験群に割り当てられたとしても、この実験の影響を受けていません。2つのレコメンドアルゴリズムを比較する実験では、2つのアルゴリズムが同じ項目を推薦したユーザーは、その実験の影響を受けていません。

## トリガー分析の効果をシミュレーションで確認
トリガー分析を行うことによって、ユーザー全体に対して分析を行うときに比べて、検出力が高くなります。このことを簡単なシミュレーションで確認しましょう。

二値のメトリクス（購入した・しない、クリックした・しないなど）を2つの実験群間で比較する設定を考えて、シミュレーションデータを生成します。このとき、ユーザーは4つの集合に分割されます。対照群でトリガーした（実験の影響を受けた）集合 $C_\theta$ 、対照群でトリガーしなかった集合 $C_\omega$ 、介入群でトリガーした集合 $T_\theta$ 、介入群でトリガーしなかった集合 $T_\omega$ の4つです。このうち、トリガーしなかった集合 $C_\omega$ と $T_\omega$ の真の母比率は共通して $0.3$ であるとし、トリガーした対照群 $C_\theta$ の真の母比率は $0.35$ 、トリガーした介入群 $T_\theta$ の真の母比率は $0.35 + \Delta p$ とします。つまり $\Delta p$ は介入効果です。また、各実験群のサンプルサイズはどちらも $2000$ とし、各実験群でトリガーしたユーザーの割合は共通して $0.2$ であるとします。以上の設定を以下の表にまとめます。

| 集合 | サンプル数 | 真の母比率 |
|:-:|:-:|:-:|
| $C_\theta$ |  $400$ | $0.35$ |
| $C_\omega$ | $1600$ | $0.3$ |
| $T_\theta$ |  $400$ | $0.35 + \Delta p$ |
| $T_\omega$ | $1600$ | $0.3$ |

$\Delta p$ を0, 0.05, 0.1, 0.2と変化させたときに、トリガー分析と通常の分析とで検出力がどう変わるか見てみます。

<details><summary>Rによるシミュレーションコード</summary>

```R
library(tidyverse)

ab_power = function(n = 2000, tau = 0.2, p_omega = 0.3, p_c_theta = 0.35, delta_p, B = 3200) {
  results = lapply(
    1:B,
    function(i) {
      n_theta = as.integer(n * tau)
      n_omega = n - n_theta
      c_theta = rbinom(1, n_theta, p_c_theta)
      c_omega = rbinom(1, n_omega, p_omega)
      t_theta = rbinom(1, n_theta, p_c_theta + delta_p)
      t_omega = rbinom(1, n_omega, p_omega)
      all_up = prop.test(
        x = c(c_theta + c_omega, t_theta + t_omega),
        n = c(n, n),
        correct = F
      )$p.value < 0.05
      trigger = prop.test(
        x = c(c_theta, t_theta),
        n = c(n_theta, n_theta),
        correct = F
      )$p.value < 0.05
      list(all_up = all_up, trigger = trigger)
    }
  )
  all_up_power = sapply(results, \(x) x$all_up) %>% mean
  trigger_power = sapply(results, \(x) x$trigger) %>% mean
  list(all_up = all_up_power, trigger = trigger_power)
}

set.seed(2024)
tib = tibble(delta_p = numeric(), analysis = character(), power = numeric())
for (delta_p in c(0, 0.05, 0.1, 0.2)) {
  powers = ab_power(delta_p = delta_p)
  tib = tib %>%
    add_row(delta_p = delta_p, analysis = "all-up", power = powers$all_up) %>%
    add_row(delta_p = delta_p, analysis = "trigger", power = powers$trigger)
}

ggplot(tib) +
  geom_line(aes(x = delta_p, y = power, color = analysis)) +
  scale_x_continuous(name = "Δp", breaks = c(0, 0.05, 0.1, 0.2)) +
  scale_color_discrete(name = "手法", labels = c("通常", "トリガー")) +
  labs(y = "検出力")

ggsave("./power.png", width = 1920, height = 1080, units = "px")
```

</details>

![power.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3840264/5df107f7-c625-dba6-2c92-9abe1d202659.png)


プロットから分かるように、 $\Delta p = 0$ のとき、すなわち介入効果がないときは、トリガー分析と通常の分析で偽陽性率は変わりません。一方、 $\Delta p \ne 0$ のときは、 $\Delta p$ の値に関わらず、トリガー分析の方が高い検出力で検定できています。

トリガー分析と通常の分析とでサンプルサイズを比較すると、当たり前ですがトリガー分析の方が小さくなります。一方で、真の平均値の差を比較すると、介入効果が0の集合 $C_\omega$ と $T_\omega$ が混じっている分だけ通常の分析の方が小さくなります。サンプル数が小さくなる影響より、平均値の差が大きくなる影響の方が上回っているので、トリガー分析の方が高い検出力で検定できるのですね。

## 効果の希釈
トリガー分析で算出した介入効果はトリガーした集合に対する効果なので、その効果を全体に対する効果に希釈する (dilute) 必要があります。

希釈の方法についての議論は Deng and Hu (2015) が詳しいので、ぜひ参照してください。私も目を通しましたが、勉強不足がたたってか、私にはややしっくりこない記述がありました（結論はおおむね納得できたのですが）。ここでは、私なりの理解に基づいて、希釈の方法とそれが要求している仮定を解説します。間違い探しのつもりで読んでみてください。

ユーザーの観測値の確率変数を $Y$、介入の確率変数を$T$、トリガーしたかどうかの確率変数を $S$ とします。トリガー分析の介入効果と全体の介入効果はそれぞれ

```math
\begin{align}
\Delta_{\text{trigger}} &= \text{E} \left[ Y \mid T=1, S=1\right] - \text{E} \left[ Y \mid T=0, S=1\right] \\
\Delta_{\text{overall}} &= \text{E} \left[ Y \mid T=1\right] - \text{E} \left[ Y \mid T=0\right]
\end{align}
```

となります。

ここで、以下の2つの仮定を導入します。

1. $T$ と $S$ は独立である。
1. トリガーしないときの介入効果は0である。
   すなわち $\text{E} \left[ Y \mid T=1, S=0\right] = \text{E} \left[ Y \mid T=0, S=0\right]$

仮定1より、

```math
\begin{align}
\text{E} \left[ Y \mid T=1\right] = \text{E}[Y \mid S=1, T=1]\text{P}(S=1) - \text{E}[Y \mid S=0, T=1]\text{P}(S=0)\\
\text{E} \left[ Y \mid T=0\right] = \text{E}[Y \mid S=1, T=0]\text{P}(S=1) - \text{E}[Y \mid S=0, T=0]\text{P}(S=0)
\end{align}
```

となります。これと仮定2より、

```math
\begin{align}
\Delta_{\text{overall}} &= \text{P}(S=1)\{\text{E}[Y \mid S=1, T=1] - \text{E}[Y \mid S=1, T=0]\} \\
&\quad\:- \text{P}(S=0)\{\text{E}[Y \mid S=0, T=1] - \text{E}[Y \mid S=0, T=0]\} \\
&= \text{P}(S=1)\{\text{E}[Y \mid S=1, T=1] - \text{E}[Y \mid S=1, T=0]\} \\
&= \text{P}(S=1) \Delta_{\text{trigger}}
\end{align}
```

となります。つまり全体の効果は、トリガー分析の効果にトリガー率をかければ求まるという、直観的な結果となりました。これは Deng and Hu (2015) の3.2節の結果と一致します。

この方法を使うためには、上記の仮定が満たされていなければなりません。トリガー条件を適切に設定できている場合、どちらの仮定も満たしていると考えてよいでしょうが、実験の実装には誤りがつきものです。トリガー率が実験群によって変わらないか、トリガーしなかった集合間の平均の差は有意に大きくないかなどを、ガードレールメトリクスとして設定することで、実験の信頼性を高めることができるでしょう。

## Counterfactual Logging
あるユーザーがトリガーしたかどうかを事後的に確認することは、実験によっては難しいことがあります。例えば、レコメンドアルゴリズムが継続的に学習を行っているため、過去の推薦結果の再現が難しく、どのリクエストに対して2つのレコメンドアルゴリズムが異なる結果を返したのか特定できない場合が考えられます。

このような場合は、counterfactual loggingの実装を検討すべきです (“Patterns of Trustworthy Experimentation,” 2020)。 Counterfactual loggingとは、ユーザーがどの実験群に属しているかに関わらず、トリガー条件を満たしたときにユーザーの識別子をログ出力することを指します。ログに出力された識別子を持つユーザーに限定した分析を行うことで、勝手にトリガー分析になるわけです。

Counterfactual loggingの実装によって、ユーザー体験が悪化することがあります。前述のレコメンドアルゴリズムの比較はその好例です。トリガー条件の判定のために2つのレコメンドアルゴリズムを実行するので、counterfactual loggingを実装しない場合と比べて、レコメンドアルゴリズム1回分だけ余計に時間がかかります。このパフォーマンスの悪化は、高速なアルゴリズムを利用しているときでも大きな悪影響をおよぼしている可能性があります。2017年のBingの試算では、Webサイトのパフォーマンスが0.1秒遅くなると、年間1,800万ドルの損失につながることがわかったそうです (Kohavi et al., 2021, p. 85)。

Counterfactual loggingの実装による悪影響が大きいと判断した場合、それ以外の手段でトリガー分析を行わなければなりません。たいていの場合、counterfactual loggingほどの精度は期待できないでしょう。そのときは、保守的なトリガーを使うべきです。保守的なトリガーとは、実験の影響を受けなかったユーザーも一部含んでしまうが、実験の影響を受けたユーザーは全て含むようなトリガーのことです。トリガーが保守的になることによって検出力は低下しますが、実験の妥当性は担保されたままです (Kohavi et al., 2021, p. 223)。

## 参考文献
- [Deng, A., Hu, V., 2015. Diluted Treatment Effect Estimation for Trigger Analysis in Online Controlled Experiments, in: Proceedings of the Eighth ACM International Conference on Web Search and Data Mining, WSDM ’15. Association for Computing Machinery, New York, NY, USA, pp. 349–358.](https://doi.org/10.1145/2684822.2685307)
- [Kohavi, R., Tang, D., Xu, Y., 2021. A/Bテスト実践ガイド : 真のデータドリブンへ至る信用できる実験とは. ドワンゴ.](https://www.kadokawa.co.jp/product/302101000901/)
- [Patterns of Trustworthy Experimentation: Pre-Experiment Stage, 2020. Microsoft Research. (accessed 2024-08-13)](https://www.microsoft.com/en-us/research/group/experimentation-platform-exp/articles/patterns-of-trustworthy-experimentation-pre-experiment-stage/)