Data Cleansing for Models Trained with SGD

Dec 11, 2021 3 min read XAI

Go to Project Site

Dec 11, 2021 3 min read XAI

Go to Project Site

1. どんなもの？

SGDにおける学習問題は
$\displaystyle \hat{\theta} = \argmin_{\theta \in \mathcal{R}^p} \frac{1}{N} \sum^N_{n=1}{l(z_n; \theta)}$
lossの勾配を定義
$\displaystyle g(z; \theta) \coloneqq \nabla_\theta l(z; \theta)$

$j$番目のデータないときのSGDの更新は
$\displaystyle \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を以下で定義
$\displaystyle \theta_{-j}^{[t]} - \theta^{[t]}$
$u \in \mathcal{R}^p$に対して，Linear Influence Estimator（LIE）を定義（内積計算）
- $u$として識別結果の勾配$\nabla_\theta f(x; \theta^{[T]})$やロス関数の勾配$\nabla_\theta l(x; \theta^{[T]})$を用いる
- 以下ではロス関数の勾配$\nabla_\theta l(x; \theta^{[T]})$を採用

\displaystyle 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)

$Z_t \coloneqq I - \eta_t H^{[t]}$，データ$z_j$が含まれるSGDのステップを$\pi(j)$とすると
$\displaystyle \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)$
SGD-influenceは
$\displaystyle \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}$

$l(z;\theta)$が2段階微分可能であると仮定　→ テイラー展開
- $H^{[t]}$はLossのHessian $\displaystyle H^{[t]} \coloneqq \frac{1}{\left|S_t\right|} \sum _ {i \in S_t}\nabla^2_\theta l (z_i; \theta^{[t]})$
SGD-influenceは以下で近似できる
$\displaystyle \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}$

Multi-epochに拡張すると，（$K$はEpoch数）
$\displaystyle \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)$
$u^{[t]} \coloneqq Z_{t+1}Z_{t+2} \cdots Z_{T-1}u$ とすると
$\displaystyle \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$
SGDをトレースして，$u^{[t]}$を更新する
$\displaystyle u^{[t]} \leftarrow Z_{t+1} u^{[t+1]}=u^{[t+1]}-\eta_{t+1} H_{\theta^{[t+1]}} u^{[t+1]}$
SGDのTrainとTestのアルゴリズムは

True Linear Influence(データを除いて再学習して精度がどう変わるか)と比較
- 既存手法に比べて綺麗に相関があることを確認
MNISTとCifar10でデータクレンジングした結果
- Approxは恐らく，最終Epochのみに対してLinear Influence Estimationするモデル
- MNISTとCifar10ともにクレンジングにより精度向上を確認
実際にクレンジングによって削除されたサンプル