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]}$を導出できた。
-
学習フェーズでは、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]}$を計算せず、以下の式で効率的に計算できる。
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)
実験
真のLinear Influence(実際にサンプル抜いて計算した場合)と比較した結果。Logistic Regressionを用いたMNISTの場合(右上)でも、既存手法に比べて綺麗に相関する。DNNの場合(下段)違いがより顕著
(https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/viewPaper/16155)
サンプルを除去して行った時の精度の遷移。Approx.は1epochのみ用いてLIEする近似手法。
- 既存手法, 近似手法共にうまくいって、精度向上達成できる(10^1〜10^3サンプル除去)
- 近似なしの提案手法だと10^4くらいサンプル除いても悪くならない。
取り除かれたサンプルの例。AEだとnoisyだったりbackgroundがvividなものが取り除かれるのに対し、提案手法では曖昧なサンプルが取り除かれている。