論文読みメモ： Applying the Delta method in metric analytics: A practical guide with novel ideas（その1）

以下の論文を読みます。

Alex Deng, Ulf Knoblich, Jiannan Lu. Applying the Delta method in metric analytics: A practical guide with novel ideas. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD’18). ACM, 233–242, 2018.
[1803.06336] Applying the Delta method in metric analytics: A practical guide with novel ideas
KDD 2018 | Applying the Delta method in metric analytics: A practical guide with novel ideas

以下の記事でも同じ論文が紹介されています。

統計指標の信頼区間を評価する Delta method とその応用（論文紹介） - LINE ENGINEERING

論文で紹介されている4つのケースのうち1つ目などは以前から従来法とデルタ法の比較が紹介されているようです。例えば以下のサイト（ただこれは「正規二変量の比」とされています；論文はビッグデータの文脈で「『漸近』正規二変量の比」の計測手法として紹介していることになります）。

正規二変量の比の信頼区間 (デルタ法, Fieller's theorem) | 統計解析 | Kengo Nagashima - The Institute of Statistical Mathematics

https://nshi.jp/contents/doc/nrd_ci/121030_nrd_ci.pdf

※ キャラクターは架空のものです。解釈の誤りは筆者に帰属します。おかしい点がありましたらご指摘ください。

次回：まだ

f:id:cookie-box:20190101160814p:plain:w60

タイトルは「指標の分析への、デルタ法の応用―斬新なアイデアと実践ガイド」かな。

f:id:cookie-box:20190101155733p:plain:w60

斬新なアイデアて。

近年ではオンライン指標によってビジネスパフォーマンスが計測・監視されているけど、データが多いのでそういう指標ははだいたい正規分布にしたがうと考えてよい（本当かな）。ノイズがガウシアンなら低コストで逐次的に推測できる。ただ諸事情で推測しづらい指標もある。だからデルタ法を応用してみる―というアブストラクトだね。

それだけだと斬新さがわからないですね…。イントロの「背景」を読むと、ビッグデータ時代になったが、~~SVMをだしに~~データサイズにスケールしないアルゴリズムもあるといった後、メタアルゴリズムに注目が集まっているといっていますね。メタアルゴリズムというのは並列化が困難なアルゴリズムを分散アルゴリズムにするものなんですね？どういったものなんでしょうか…。まあそれで、次の節には「でも普通に分散できることもあるよね」ということで、例えばあるデータの平均と分散がほしいならデータの和と2乗和だけ蓄積すればよいと…確かにそうですね！その発想はなかったです。

それくらい発想して。

その次の節では、なんかもう所望の指標をモデリングしようという話になっていますね。中心極限定理は、独立に同一の分布にしたがう確率変数 $X_1, \cdots, X_n$ の標本平均を $\bar{X}$ 、真の平均と分散を $\mu, \, \sigma^2$ とすると、 $\sqrt{n}(\bar{X}-\mu)/\sigma$ は $n \to \infty$ で標準正規分布に分布収束するというものですね。昨日やりました。このことから母平均の信頼区間が見積れると。科学分野でエラーバーをみたらだいたいこれだろうと。ただこれだけだと利用できる場面が限定的すぎるということでデルタ法というのが続いて紹介されていますね。何か $n$ に依存する確率変数 $T_n$ と定数 $\theta$ が $n \to \infty$ 以下を満たすとき（ $\xrightarrow{d}$ は分布収束）、

$\sqrt{n}(T_n - \theta) \xrightarrow{d} N(0,1)$ $\phi'(\theta)$ が存在して $\phi'(\theta) \neq 0$ であるような連続関数 $\phi$ について以下が成り立つということです。 $\sqrt{n} \bigl( \phi(T_n) - \phi(\theta) \bigr) \xrightarrow{d} N \bigl( 0,\phi'(\theta)^2 \bigr)$ これは、 $\theta$ の周りでのテイラー展開より $\phi(T_n) = \phi(\theta) + \phi'(\theta)(T_n - \theta) + O\bigl( (T_n - \theta)^2 \bigr)$ なので、 $\sqrt{n} \bigl( \phi(T_n) - \phi(\theta) \bigr) = \phi'(\theta) \bigl( \sqrt{n} (T_n - \theta) \bigr) + O\Bigl( \bigl( \sqrt{n}(T_n - \theta) \bigr)^2 / \sqrt{n} \Bigr)$ であることからしたがうということです。2変量の場合も同様です。 $(T_n, U_n)^\top$ が $n \to \infty$ 以下を満たすとしましょう。 $\sqrt{n} \bigl( (T_n, U_n)^\top - (\theta_t,\theta_u)^\top \bigr) \xrightarrow{d} N(0,\Sigma)$ $(\theta_t, \theta_u)^\top$ の周りでのテイラー展開より、 $\phi(T_n, U_n) = \phi(\theta_t, \theta_u) + \phi_t'(\theta_t, \theta_u)(T_n - \theta_t) + \phi_u'(\theta_t, \theta_u)(U_n - \theta_u) + O\bigl( (\cdot_n - \theta_\cdot)^2 \bigr)$
$\sqrt{n} \bigl( \phi(T_n, U_n) - \phi(\theta_t,\theta_u) \bigr) = \begin{pmatrix} \phi_t'(\theta_t, \theta_u) \\ \phi_u'(\theta_t, \theta_u) \end{pmatrix}^\top \sqrt{n} \bigl( (T_n, U_n)^\top - (\theta_t,\theta_u)^\top \bigr) + O\bigl( \sqrt{n} (\cdot_n - \theta_\cdot)^2 \bigr)$
ですので結局、 $\displaystyle \sqrt{n} \bigl( \phi(T_n, U_n) - \phi(\theta_t,\theta_u) \bigr) \xrightarrow{d} N \left( 0, \begin{pmatrix} \phi_t'(\theta_t, \theta_u) \\ \phi_u'(\theta_t, \theta_u) \end{pmatrix}^\top \Sigma \begin{pmatrix} \phi_t'(\theta_t, \theta_u) \\ \phi_u'(\theta_t, \theta_u) \end{pmatrix} \right)$ が成り立ちます…これ、通常の確率変数の変換とはどう違うんでしょうか。

$\phi$ が1次関数だったら $\sqrt{n}(T_n - \theta)$ が $N(0, 1)$ にしたがうとき $\sqrt{n} \bigl( \phi(T_n) - \phi(\theta) \bigr)$ は $N \bigl( 0,\phi'(\theta)^2 \bigr)$ にしたがうね。 $n \to \infty$ なら $\phi$ が1次関数でなくても $\sqrt{n} \bigl( \phi(T_n) - \phi(\theta) \bigr)$ は近似的に $N \bigl( 0,\phi'(\theta)^2 \bigr)$ にしたがう（ $\sqrt{n}$ がかかっているからね）。さらに $n \to \infty$ で $\sqrt{n}(T_n - \theta) \xrightarrow{d} N(0, 1)$ の場合も $\sqrt{n} \bigl( \phi(T_n) - \phi(\theta) \bigr) \xrightarrow{d} N \bigl( 0,\phi'(\theta)^2 \bigr)$ がいえる、か。「正規分布にしたがうある確率変数について $n \to \infty$ で成り立つこと」であれば、「 $n \to \infty$ で正規分布に近づく確率変数」でも成り立つだろうという合わせ技の発想って感じがするね。

なるほど…この式の後にこの計算は parallelizable とありますが、この $T_n$ は標本平均 $\bar{X}$ であるという前提で進んでいくんでしょうか。標本平均でなかったらサーバクラスタごとに並列に情報を蓄積していけるかわからないと思うんですが…まあ標本平均以外にどのような標本依存の確率変数がデルタ法の条件を満たすかわからないですが。それで、問題は、指標を計測するのに適切な $\phi$ がわからない？え？？「指標を計測しよう → 並列化のためにデルタ法 $\phi(\bar{X})$ を使おう → $\phi$ って何だっけ ← 今ここ」という状況なんですか？？どうしてその見通しなくデルタ法を使おうと思ったんですか？？

まあそれだけ並列化する必要性が逼迫していたんじゃないかな…。それで、この論文では以下の4つの事例（多いな）への応用を紹介するらしいよ。

ratio metrics（同じ指標の対照群と処置群における値の比）
cluster randomized experiments（クラスターランダム化比較試験）
outer confidence intervals
within-subject studies（被験者内実験）

コードは Microsoft Azure Notebooks - Online Jupyter Notebooks で公開してるって。

では一つ目からみていきましょう。

1. 同じ指標の対照群と処置群における値の比

$X_1, \cdots, X_n$ を独立に同一の分布にしたがう対照群からの観測結果（真の平均と分散 $\mu_x, \, \sigma_x^2$ ）、 $Y_1, \cdots, Y_n$ を独立に同一の分布にしたがう処置群からの観測結果（真の平均と分散 $\mu_y, \, \sigma_y^2$ ）とします。また $\sigma_{xy}$ を共分散としますが、対照群とするユーザと処置群とするユーザをランダムに選出していれば $\sigma_{xy} = 0$ であると。まあその場合、以下の表で $X_i$ カラムと $Y_i$ カラムが相関をもってはおかしいですね。

id	$X_i$	$Y_i$
1	対照群での1人目の指標の値	処置群での1人目の指標の値
2	対照群での2人目の指標の値	処置群での2人目の指標の値
3	対照群での3人目の指標の値	処置群での3人目の指標の値

それでこのとき、単なる標本平均の差 $\hat{\Delta} = \bar{Y} - \bar{X}$ が平均処置効果（ATE） $\Delta = \mu_y - \mu_x$ の不偏推定量になるということですが、標本平均は母平均の不偏推定量なのでそうなりますね。そして、 $\bar{X}$ も $\bar{Y}$ も標本数が大きければ近似的に正規分布にしたがうので、 $\hat{\Delta}$ も近似的に正規分布にしたがうと。正規分布の再生成から明らかです。よって $\hat{\Delta}$ の信頼区間は求まります。それはそうです。

しかし―ここからが本論ですね―現実には $\Delta = \mu_y - \mu_x$ ではなく $\Delta = (\mu_y - \mu_x)/\mu_x$ を推定したいはずだといっています。推定量 $\hat{\Delta} = (\bar{Y} - \bar{X})/\bar{X}$ によって。まあ確かに、UI を変更したことで1人あたりクリックする商品の数が何個増えたというより、何割増えたといった方が UI 変更がどれだけすごかったのかわかりやすいのかもしれません。…でも、グーグル検索すると正規分布にしたがう2つの確率変数の商はコーシー分布にしたがうと出てきますよ？

それはどちらも平均が $0$ とかの場合だね…。

正規分布の比(商)の分布 Fieller-Hinkley - 高精度計算サイト

まあでも確かに、まずはまともに出そうとしてみるべきだろう。ただそうするとなんだか分布自体が複雑だ。これじゃ信頼区間がよくわからない。だから Fieller は工夫した。たぶんこんな考え方だと思う。 $\Delta$ は本来定数なんだと思ってノイズ $\varepsilon$ を分離すれば $(Y-X-\varepsilon)/X = \Delta \, \Leftrightarrow \, Y - (1+\Delta)X = \varepsilon$ となる。 $\varepsilon = Y - (1+\Delta)X$ の漸近分布は $\Delta$ を用いてかける（ $\Delta$ が定数なら正規確率変数の線形結合なんだから簡単だ）。ただ本当は $\varepsilon$ は $0$ になってくれなくちゃならない。 $n$ を大きくしても残る $\varepsilon$ のノイズは $\Delta$ が不確定だったせいなんじゃないか、と考えて $\Delta$ に差し戻す…というのは以下の PDF の「1.2 Fieller’s theorem による比の信頼区間」を読んだ適当な解釈だけど。

https://nshi.jp/contents/doc/nrd_ci/121030_nrd_ci.pdf

この Fieller の方法による信頼区間（タイプするのはしんどかったから論文をみて）は精度がよいらしい（サンプルがそこまで多くないときは；上の PDF にもデルタ法より Fieller の方法の方がよいとある）。そしてさらに、デルタ法を用いる方法がある（上の PDF にも 1.1 として載ってるね）。こっちの方が表式はシンプルになる。 $T_n = \bar{X}, \, U_n = \bar{Y},\, \phi(x, y) = y/x, \, \phi_x'(x, y) = -y/x^2, \, \phi_y'(x, y) = 1/x$ を上の2変量のデルタ法に代入するとこうだ。
$\displaystyle \sqrt{n} \left( \frac{\bar{Y}}{\bar{X}} - \frac{\mu_y}{\mu_x} \right) \xrightarrow{d} N \left( 0, \begin{pmatrix} -\mu_y/\mu_x^2 \\ 1/\mu_x \end{pmatrix}^\top \Sigma \begin{pmatrix} -\mu_y/\mu_x^2 \\ 1/\mu_x \end{pmatrix} \right)$ $\mu_x, \mu_y$ を標本平均、 $\Sigma$ を標本分散共分散行列で代用するなら、上の分散はこうなる。 $\begin{pmatrix} -\bar{Y}/\bar{X}^2 \\ 1/\bar{X} \end{pmatrix}^\top \begin{pmatrix} s_x^2 & s_{xy} \\ s_{xy} & s_y^2 \end{pmatrix} \begin{pmatrix} -\bar{Y}/\bar{X}^2 \\ 1/\bar{X} \end{pmatrix} = \frac{1}{\bar{X}}\sqrt{s_y^2 - 2\frac{\bar{Y}}{\bar{X}}s_{xy} +\frac{\bar{Y}^2}{\bar{X}^2}s_{x}^2}$ これから信頼区間が論文の (4) 式になるとわかるね。

Fieller さんの手法は検算しましたか？

めんどいからやってない。まあそれで、デルタ法はエッジワース展開によりさらによい近似に拡張できるとある。

エッジワース展開？

私たちは昨日中心極限定理の話をたどった。私たちはそこで $\varphi_1(t)$ の $3$ 次以上の項が消えるのをみた。確かに $n \to \infty$ で $\varphi_1(t)$ の $3$ 次以上の項は消える。ただ、現実には $n$ は $\infty$ にまでなっていないのだから、消えていない。

え？いや確かに、現実のシチュエーションでは、厳密にはそうでしょうけど。

だから $3$ 次以上のモーメントも拾ってあげよう。 $\log \varphi(t)$ を $\log \varphi_1(t)$ で表すのは容易だ。これを $\varphi(t)$ に戻す。このとき、ネイピア数の定義の形の極限を逆につかえば無限級数の形で表現できる。この無限級数の1項目の反転は正規分布だ。2項目以降も反転すれば、正規分布からのぶれを調整できる。…これがエッジワース展開だ。実際には標本の情報をもとにこの調整をすることになる。論文の3ページに、 skewnes の調整方法が紹介されているね。