ADWIN(ADaptive WINdowing) について


レコメンドシステムや需要予測のモデルを使い続けている場合、モデルの予測精度の劣化が問題になります。この問題は、日々新しいデータが追加されていく中で、状況に変化がおきてしまい、過去のデータの学習が予測に悪影響を与えることがあるからです。

このような状況の変化を **concept drift** と呼びますが、concept driftに対応するために、モデルを学習するデータの期間を更新する必要があります。このデータ期間のことを **window** と、学習するデータ期間をどのように選択する手続きを **window strategy** と呼びます。

ADWINはその代表的なアルゴリズムであり、動的にwindowのサイズを調整することができます。

この記事ではこのADWINのアルゴリズムについて解説します。

---

## ADWINを提案した論文の情報

- タイトル：
    Learning from Time-Changing Data with Adaptive Windowing
- 著者：
    A Bifet, R Gavalda
- 掲載年：
    2007年
- 被引用数：
    1347 @2022/04/30 確認
- URL：
    https://epubs.siam.org/doi/abs/10.1137/1.9781611972771.42


--- 

#### Setting

ADWINへの入力は以下の2つです。

 - 信頼区間を決定する外れ値の確率 $\delta \in (0,1)$。例えば、$\delta = 0.05$なら信頼区間95%が設定される。
 - 時間$t$ごとに、次々と観測されるストリーミングデータ $[x_1, x_2, ..., x_t, ...]$

この時、$x_t$の値は前処理によって$[0,1]$の範囲に標準化されていることとする。標準化の計算方法は分析者の任意で設定する。

観測される$x_t$は、真の分布$D_t$から観測されたと見なし、その分布の期待値を$\mu_{t}$とする。すなわち、$x_t \subset D_t = D(\mu_{t})$ である。

windowを$W$とし、この中に $x_t$ が日々追加されていく。
$W$の長さは$n$。
$W$の内部にある観測値$x_t$の平均を$\hat{\mu}_{W}$とする。

#### アルゴリズム

ADMINのアルゴリズムを以下にしめす。

![figure1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/429933/be28bd92-7a75-d659-2a20-8350004420db.png)

上図のプログラムの行ごとに以下の処理が定義されている。

 - **(2-3行目)**
    時間$t$が更新されるたびにfor文が実行し、新しい観測値$x_t$を$W$に追加する。
 - **(3-6行目)**
    $W$の複数の分割パターン$W_0$と$W_1$について、後に定義される$\epsilon_{cut}$よりもその平均差が大きければ、古いインスタンスの集合 $W_0$ には、古いconceptの観測値が含まれていると考える。そのため、$W_0$に含まれる最も古い$x_i$を削除し、$W$を更新する。
 - **(7行目)**
    以上の繰り返しの結果、$W$ に残った$x_i$の平均である $\hat{\mu}_{W}$ を出力する。

この時、$W$を分割した$W_0$と$W_1$をsubwindowと呼ぶ。subwindowの要素数は、その平均値が信頼できるほど十分に大きい必要がある。
ADWINの結果、$W(= W_0 \cup W_1)$は単一の分布$D(\mu)$から抽出されたインスタンスのみで再構成されたとみなす。

#### 閾値の定義

この$W_0$と$W_1$の平均差の閾値となっている$\epsilon_{cut}$は以下で計算される。

$$
m =\frac{1}{1 / n_{0}+1 / n_{1}}\left(\text { harmonic mean of } n_{0} \text { and } n_{1}\right) 
$$
$$
\delta^{\prime} =\frac{\delta}{n}, \text { and } \quad \epsilon_{c u t}=\sqrt{\frac{1}{2 m} \cdot \ln \frac{4}{\delta^{\prime}}}
$$

$\delta^{\prime}$ の役割は、多重仮説検定問題を避けることである。
例えば、3つの集合A,B,Cについて、その平均差が有意であるかを検定するために、危険度5%のt検定を行った場合、一つのペアの集合間の誤検定率は5%となる。よって、A-B,A-C,B-Cのt検定のうちどれかが一つでも誤検定となる確率は$1-(1-0.05)^3=0.143$と増大する。
このように、「A,B,Cの平均値は同じである」という仮説を検定する場合、通常の二集合間の検定を繰り返してしまうと、検定精度が悪化する。これが多重仮説検定問題である。
ADWINでは、 $W_0$ と $W_1$ の平均差について $n$ 回の異なる可能性を検定する。これを $\delta^{\prime}$ でこの問題を補正している。

ADWINはすべてのインスタンス$x_t$を処理する際に、以下の特徴がある。

- **False positive rate bound(偽陽性率境界)**
    もし真の平均値$\mu_t$が一定であれば、(つまり、concept driftが発生していない場合、)ADWINがwindowをその処理ステップで縮小する確率は$\delta$となる。(仮に95%信頼区間として$\delta=0.05$に設定していたら、ADWINが誤って$x_t$を処理する確率は5%になる)
- **False negative rate bound(偽陰性率境界)**
    もし、ある分解$W_0, W_1$において$\mu_{W_0} - \mu_{W_1} > 2 \epsilon_{c u t}$であれば、ADWINは$1-\delta$の確率で$W$を$W_1$に、あるいはより短いサイズへと縮小する。

実際には、上記の$\epsilon_{c u t}$の定義では保守的(conservative)すぎ、実用的ではない。これは Hoeffding bound に基づいたすべての分布に有効な定義ではあるが、分散の小さい分布の大きな偏差を過大評価する欠点がある。
よって、十分に大きなwindowのサイズである場合、$\mu_{W_0} - \mu_{W_1}$ が正規分布に従うことが観察できることから、以下の $\epsilon_{c u t}$ を用いるべきだろう。

$$
\epsilon_{c u t}=\sqrt{\frac{2}{m} \cdot \sigma_{W}^{2} \cdot \ln \frac{2}{\delta^{\prime}}}+\frac{2}{3 m} \ln \frac{2}{\delta^{\prime}}
$$

上式の $\sigma_{W}^{2}$ は $W$ 内の観測値の分散。
上式の平方根の項は、標準偏差の倍数であり、その倍率はsettingで設定した $\delta$ で決まる。
$\delta^{\prime}$　についても、以下で十分に多重仮説検定問題に対処できる。

$$
\delta^{\prime}=\frac{\delta}{\ln n}
$$


---
以上で、ADWINの解説を終わります。
なにかのお役に立てたら幸いです。