8
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

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

Last updated at Posted at 2020-01-15

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]}$を導出できた。

NeurIPS-SGD-cleansing_method.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]}$を計算せず、以下の式で効率的に計算できる。
    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)
    

実験

NeurIPS-SGD-cleansing_results.png

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

(https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/viewPaper/16155)NeurIPS-SGD-cleansing_graph.png

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

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

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

次に読むべき論文

8
4
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
8
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?