コンテンツにスキップ

SGD最適化モデルに対するデータクレンジング手法

Data Cleansing for Models Trained with SGD

https://arxiv.org/abs/1906.08473

github実装 https://github.com/sato9hara/sgd-influence

概要

学習がうまくいかなかったときに元データを分析することがあるが、データのError Analysisをする際に、どのインスタンス(データセット)が学習に強く影響しているのかを考察するためにはドメイン知識が必要。 この論文では、学習に悪影響を及ぼしているインスタンスをドメイン知識なしでCleanseする方法を提示している。

Keyword:

  • influence estimation
  • counterfactual SGD
  • Linear Influence Estimation (LIE)
  • Kendall's tau
  • Jaccard index

2. Preliminaries

SGDのおさらい

3. SGD-Influence

training step \(t\)において、インスタンス\(z_{j}\)を除いた時のgradientを\(\\theta_{-j}^{[t]}\)としたとき、SGD-influenceを以下のように定義する。 \(\(\\theta\_{-j}^{[t]} - \\theta^{[t]}\)\) つまり、j番目のインスタンスをdropした時の\(\\theta\)と何もしていない時の\(\\theta\)の差が大きい場合、そのインスタンスの学習への影響が大きいと言える。 このように、結果からデータを振り返る通常とは逆の視点で使っているのでこれをCounterfactual SGD（反実仮想: もしなかったらどうなるか）と呼んでいる。

Linear Influence Estimation (LIE)

\[ L_{-j}^{[T]}(u) = \\langle u, \\theta_{-j}^{[t]} - \\theta^{[t]}\\rangle \]

\(u\)に prediction functionの1階微分\(\\nabla_{\\theta}f(x,\\theta)\)や、loss関数の1階微分\(\\nabla_{\\theta}l(x,\\theta)\)を入れて用いる。後者では、インスタンス\(z_i\)が学習(loss)に及ぼす影響を測れる

実際は、テイラー展開で近似して

$$ L_{-j}^{[T]}(\nabla_{\theta}l(x,\theta)) \approx \nabla_{\theta}l(x,\theta_{-j}^{[t]}) - \nabla_{\theta}l(x,\theta^{[t]}) $$ として計算できる。

ただし、正直に計算してしまうとインスタンスの個数N回のSGD計算をやることになり計算コストが高いので効率的に行う方法を本論文で提案した。

4. Estimating SGD-Influence

今のところよくわからない。 変形すると\(\\Delta\\theta\_{-j}\)(2階微分)になる。

Eq(2) は漸化式繰り返し使って変形している\ Eq(3), (4)は、この辺の微積分の連続性の概念を元に不等式が成立しているっぽい。 https://ja.wikipedia.org/wiki/%E3%83%AA%E3%83%97%E3%82%B7%E3%83%83%E3%83%84%E9%80%A3%E7%B6%9A

5. Proposed Method for LIE

計算コスト本来なら\(O(p^2)\) かかるところを \(O(TM\\delta)\)にできている

  • p: データの次元?
  • T: total SGD steps
  • M: the largest batch size in SGD
  • \(\\delta\): complexity for computing the parameter gradient (どのOptimizerを使うかで決まる?)

過去の同様のアプローチとの違い

  1. 最適化されたモデルを想定しなくてもいい（学習の各ステップの状態でのモデルを用いることができる）
  2. lossがconvexでなく、non-convexでも良い

比較されてる論文 Understanding Black-box Predictions via Influence Functions とか

典型的なデータクレンジングである外れ値検出（テーブルデータならIsolation forest, 画像ならVAEやGANとかでの再構成）で外れ値と判断されたものは、必ずしもそれが学習に悪影響を及ぼすというわけでもない（が、本手法で外れ値と判断したものが実際に学習への影響度とリンクしている）

7. Experiments

7.1 Evaluation of LIE

Kendall's tau Jaccard index で評価している。これが何か調べる。

Fig1, Table1 x, yの見方がわからないが、y=xの線上に乗るほど、正確にインスタンスの影響を評価できているということ。過去の手法（赤のK&L）よりも青の提案手法の方が良い。 convexな例であるlinear logistic regressionと、non-convexな例であるDNNどちらにおいても、インスタンスの影響を正しく評価できているというのも重要。

7.2 Evaluation of Data Cleansing

Autoencoderの場合はvivid colorな背景を異常と見做しがちだが、それを除いても学習への影響は少ない（改善しない）。一方、画像内のインスタンスと背景の境界がぼやけているものはAutoencoderでは異常とみなされないが、学習への影響は大きかった（改善した）。提案手法は後者のパターンを異常を見抜けていた