"Data Cleansing for Models Trained with SGD"(NeurIPS2019)を読んだ。

## Data Cleansing for Models Trained with SGD

以下の論文を読んだのでまとめます。画像は全て論文からです。

論文: https://papers.nips.cc/paper/8674-data-cleansing-for-models-trained-with-sgd.pdf 

Hara, Satoshi, Atsushi Nitanda, and Takanori Maehara. "Data Cleansing for Models Trained with SGD." *arXiv preprint arXiv:1906.08473* (2019), NIPS2019

### 概要

ドメイン知識なしにデータのクレンジング(精度に悪影響しているインスタンス(influential instances)を取り除くことで学習データをコンパクトにする)を行う手法を提案。既存手法(influential function)ではloss関数が凸であることを仮定していたが、SGDの挙動をトレースすることでinfluential instancesを見つける手法を提案。Influential Instancesを除いた後の学習パラメータを**再学習なしに獲得できる。**MNIST, CIFAR10で評価し、効果を確認。

### 提案手法

貢献は以下

- SGDから測る学習インスタンスの影響をSGD-influenceとして新たに定式化
- SGD-influenceを推定する手法を提案し、学習インスタンスの影響を測るアルゴリズムを提案
    - アルゴリズムをconvex loss, non-convex lossで評価
- 効果を実験的に評価、特にMNIST, CIFAR10で評価



#### SGD-inference 

ある学習インスタンス($z_j$)がない時のSGDの挙動は以下のように計算できる。ただし$
g(z ; \theta):=\nabla_{\theta} \ell(z ; \theta)
$
$$
\theta_{-j}^{[t+1]} \leftarrow \theta_{-j}^{[t]}-\frac{\eta_{t}}{\left|S_{t}\right|} \sum_{i \in S_{t} \backslash\{j\}} g\left(z_{i} ; \theta_{-j}^{[t]}\right)
$$
SGD-influenceを以下のように定義する。(**$z_j$がある時のパラメータとない時のパラメータの差**)
$$
\theta_{-j}^{[t]} - \theta^{[t]}
$$

$u \in \mathbb{R}^{p}$ に対し、Linear Influence Estimator(LIE)を以下のように定義する。(**$u$がパラメータの差のベクトルと同じ方向を向いて入れば大きくなる**)
$$
L_{-j}^{[T]}(u):=\left\langle u, \theta_{-j}^{[T]}-\theta^{[T]}\right\rangle
$$
uにlossの勾配を入れてやれば($$
u=\nabla_{\theta} \ell\left(x ; \theta^{[T]}\right)
$$)、LIEはlossの差分に相当する(要確認)。
$$
L_{-j}^{[T]}\left(\nabla_{\theta} \ell\left(x ; \theta^{[T]}\right)\right) \approx \ell\left(x ; \theta_{-j}^{[T]}\right)-\ell\left(x ; \theta^{[T]}\right)
$$
つまり、LIEが負の値を取るならば、jのサンプルを取り除くことでlossが下がるということ。



#### Proposed Estimator

loss関数を2階微分可能と仮定し、$\nabla_{\theta} \ell()$のテイラー展開を使って以下を得る。
$$
\frac{1}{\left|S_{t}\right|} \sum_{i \in S_{t}}\left(\nabla_{\theta} \ell\left(z_{i} ; \theta_{-j}^{[t]}\right)-\nabla_{\theta} \ell\left(z_{i} ; \theta^{[t]}\right)\right) \approx H^{[t]}\left(\theta_{-j}^{[t]}-\theta[t]\right)
$$

ただし、$H^{[t]}$はlossのへシアンであり、以下。
$$
\frac{1}{\left|S_{t}\right|} \sum_{i \in S_{t}} \nabla_{\theta}^{2} \ell\left(z_{i} ; \theta^{[t]}\right).
$$

上記の近似を用い、SGD-influenceは以下のように計算できる。漸化式のようになる。

$$
\begin{aligned} \theta_{-j}^{[t]}-\theta^{[t]} &=\left(\theta_{-j}^{[t-1]}-\theta^{[t-1]}\right)-\frac{\eta_{t-1}}{\left|S_{t-1}\right|} \sum_{i \in S_{t-1}}\left(\nabla_{\theta} \ell\left(z_{i} ; \theta_{-j}^{[t-1]}\right)-\nabla_{\theta} \ell\left(z_{i} ; \theta^{[t-1]}\right)\right) \\ & \approx\left(I-\eta_{t-1} H^{[t-1]}\right)\left(\theta_{-j}^{[t-1]}-\theta^{[t-1]}\right) \end{aligned}
$$

最終的なSGD-influenceの式を得る。

- 以下のように定義。

$$
Z_{t}:=I-\eta_{t} H^{[t]}
$$

- $\pi_j$はSGDの中で$z_j$が使われたステップとする

- 更新式を$\theta_{-j}^{[\pi(j)+1]}$、$\theta^{[\pi(j)+1]}$で比較して、

- $$
    \theta_{-j}^{[\pi(j)+1]}-\theta^{[\pi(j)+1]}=\frac{\eta_{\pi(j)}}{\left|S_{\pi(j)}\right|} g\left(z_{j} ; \theta^{[\pi(j)]}\right)
    $$

以上より、
$$
\theta_{-j}^{[T]}-\theta^{[T]} \approx \frac{\eta_{\pi(j)}}{\left|S_{\pi(j)}\right|} Z_{T-1} Z_{T-2} \cdots Z_{\pi(j)+1} g\left(z_{j} ; \theta^{[\pi(j)]}\right)=: \Delta \theta_{-j}
$$

#### Proposed Method for LIE

Multi-epochに拡張した$\Delta \theta_{-j}$は以下の式で表される。
$$
\Delta \theta_{-j}=\sum_{k=1}^{K}\left(\prod_{s=1}^{T-\pi_{k}(j)-1} Z_{T-s}\right) \frac{\eta_{\pi_{k}(j)}}{\left|S_{\pi_{k}(j)}\right|} g\left(z_{j} ; \theta^{\left[\pi_{k}(j)\right]}\right)
$$


前記の結果を用い、LIEを求める。
$$
L_{-j}^{[T]}(u):=\left\langle u, \theta_{-j}^{[T]}-\theta^{[T]}\right\rangle
$$

$u^{[t]}:=Z_{t+1} Z_{t+2} \ldots Z_{T-1} u$とし、

$$
\left\langle u, \Delta \theta_{-j}\right\rangle=\sum_{k=1}^{K}\left\langle u^{\left[\pi_{k}(j)\right]}, \frac{\eta_{\pi_{k}(j)}}{\left|S_{\pi_{k}(j)}\right|} g\left(z_{j} ; \theta^{\left[\pi_{k}(j)\right]}\right)\right\rangle
$$

とする(内積の一項と二項で$Z_t$が打ち消しあう感じ)。この時$u^{[t]} \leftarrow Z_{t+1} u^{[t+1]}=u^{[t+1]}-\eta_{t+1} H_{\theta[t+1]} u^{[t+1]}$ を用いて$u^{[t]}$の値をIterativeに求めることができる。ここまでの議論の結果から、SGDにおけるパラメータ更新のLossの勾配を元に、パラメータの差分に対するLinear Influenceを求める$u^{\left[\pi_{k}(j)\right]}$を導出できた。


<img width="356" alt="NeurIPS-SGD-cleansing_method.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/13171/a6dfd9e8-2aeb-78ed-a718-0776c305e38c.png">

- 学習フェーズでは、SGDから中間情報($S_t, \eta_t, \theta^{[t]})$を保存しておく。$S_t$: バッチに用いたサンプルのindices, $\eta_t$: Learning rate, $\theta^{[t]}$: モデルパラメータ。
- 推論フェーズでLIEを推定する。このステップは$t=T-1$から始めてIterativeに計算していくことができる。
    - $H^{[t]}u$では直接$H^{[t]}$を計算せず、以下の式で効率的に計算できる。

    ```python
    grads = [tf.gradients(loss[i], theta) for i in St]
    Hu = tf.reduce_mean([tf.gradients(tf.tensordot(u, g, axes), theta) for g in grads], axis)
    ```

### 実験


<img width="758" alt="NeurIPS-SGD-cleansing_results.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/13171/a385663b-43de-f1f5-ac19-f86b2c86791a.png">

真のLinear Influence(実際にサンプル抜いて計算した場合)と比較した結果。Logistic Regressionを用いたMNISTの場合(右上)でも、既存手法に比べて綺麗に相関する。DNNの場合(下段)違いがより顕著


(https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/viewPaper/16155)<img width="763" alt="NeurIPS-SGD-cleansing_graph.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/13171/e653112a-070a-f5f8-73a8-afee41c2b71b.png">

サンプルを除去して行った時の精度の遷移。Approx.は1epochのみ用いてLIEする近似手法。

- 既存手法, 近似手法共にうまくいって、精度向上達成できる(10^1〜10^3サンプル除去)
- 近似なしの提案手法だと10^4くらいサンプル除いても悪くならない。


<img width="725" alt="NeurIPS-SGD-cleansing_qualitative-results.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/13171/ce6f9fbd-a75c-d1ee-125d-6d52ce485629.png">

取り除かれたサンプルの例。AEだとnoisyだったりbackgroundがvividなものが取り除かれるのに対し、提案手法では曖昧なサンプルが取り除かれている。

### 次に読むべき論文

- Google 検索の関連論文から。
    - [Interpreting Black Box Predictions using Fisher Kernels](https://arxiv.org/abs/1810.10118)
    - [Training Set Debugging Using Trusted Items](https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/viewPaper/16155)