Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

影響関数（influence function）

データ点ztestz_{test}の予測において訓練データ点zzが与えた影響の大きさを評価する関数I(z,ztest)\mathcal{I}(z, z_{test})を推定する技術。

アイデア

  • 経験リスクR(θ)=1n∑i=1nL(zi,θ)R(\theta) = \frac{1}{n} \sum^n_{i=1} L(z_i, \theta)の最小化による学習アルゴリズムを前提とする。

  • 訓練データ全件で学習したモデルθ^\hat\thetaと、訓練データからデータ点zzを抜いて学習したモデルθ^−z\hat\theta_{-z}との差分θ^−z−θ^\hat{\theta}_{-z} - \hat{\theta}でインスタンスzzの影響度がわかる

  • インスタンスzzのデータ点ztestz_{test}に対する影響度は、誤差L(ztest,θ)L(z_{test}, \theta)の大きさからわかる

  • データ点ztestz_{test}の予測において訓練データ点zzが与えた影響の大きさ L(ztest,θ^−z)−L(ztest,θ^)L(z_{test}, \hat{\theta}_{-z}) - L(z_{test}, \hat{\theta})を推定する

文献

  • Koh & Liang (2017)が提案

  • Hara et al. (2019)はconvexでない損失関数にも使えるよう拡張したらしい

  • Guo et al. (2020)はFastIFを提案：k-最近傍のデータに探索範囲を絞るなどして最大80倍の高速化

  • Sharchilev et al. (2018)は勾配ブースティング決定木に向けたinfluence functionを提案

    • Influence Functionはモデルのパラメータθ\thetaの微分によって近似推定するため、決定木ベースのアルゴリズムなど微分不可能なアルゴリズムでは計算できないため

Notation

  • データ点z=(x,y)z=(x, y)

  • 誤差関数L(z,θ)L(z, \theta)

    • 経験リスク：R(θ)=1n∑i=1nL(zi,θ)R(\theta) = \frac{1}{n} \sum^n_{i=1} L(z_i, \theta)

  • NN訓練データ点が訓練集合Z\mathcal{Z}に含まれるとする

  • 標準的な経験リスク最小化：θ^=arg⁡min⁡θ1n∑i=1nL(zi,θ)\hat{\theta} = \arg \min_{\theta} \frac{1}{n} \sum^n_{i=1} L(z_i, \theta)

Leave-One-Out

1つのインスタンスzzを抜いて訓練した場合にどれだけモデルθ\thetaが変わるかを考える

θ^−z−θ^θ^−z:=arg⁡min⁡θ∈Θ∑zi≠zL(zi,θ)\hat{\theta}_{-z} - \hat{\theta}\\ \hat{\theta}_{-z} := \arg \min_{\theta \in \Theta} \sum_{z_i \neq z} L(z_i, \theta)
(1)

モデルの変化がわかればテストデータ点ztestz_{test}に対する誤差の変化も評価できる

L(ztest,θ^−z)−L(ztest,θ^)L(z_{test}, \hat{\theta}_{-z}) - L(z_{test}, \hat{\theta})
(2)

nn個の訓練データ全部を評価するにはnn回学習し直す必要があるので現実的なアプローチではない

Influence Function

アイデア

数学的なトリックを活用して再学習を避けつつLOOを近似していく。

訓練データ全部を使った経験リスクに、データ点zzについての誤差L(z,θ)L(z, \theta)を重み付きで足したリスク関数で訓練したパラメータθ^ϵ,z\hat{\theta}_{\epsilon,z}を考える

θ^ϵ,z:=arg⁡min⁡θ1n∑i=1nL(zi,θ)+ϵL(z,θ)\hat{\theta}_{\epsilon,z} := \arg \min_{\theta} \frac{1}{n} \sum^n_{i=1} L(z_i, \theta) + \epsilon L(z, \theta)
(3)

zzを入れることによる変化分がとれるので、これのϵ\epsilonでの微分のϵ=0\epsilon = 0のときの値をパラメータについての上側のinfluence functionとする

Iup,params(z):=dθ^ϵ,zdϵ∣ϵ=0=−Hθ^−1∇θL(z,θ^)\mathcal{I}_{up, params}(z) := \left . \frac{d \hat{\theta}_{\epsilon,z} }{ d \epsilon } \right | _{\epsilon = 0} = -H^{-1}_{\hat{\theta}} \nabla_{\theta} L(z, \hat{\theta})
(4)
導出

（Koh & Liang (2017)のAppendixより）

up-weightedされた経験リスクのもとでの推定量は

θ^ϵ,z=arg⁡min⁡θ∈Θ{R(θ)+ϵL(z,θ)}\hat{\theta}_{\epsilon, z} = \arg \min_{\theta \in \Theta} \big \{ R(\theta) + \epsilon L(z, \theta) \big \}
(6)

これともとの推定量の差をΔϵ\Delta_{\epsilon}とする

Δϵ=θ^ϵ,z−θ^\Delta_{\epsilon} = \hat{\theta}_{\epsilon, z} - \hat{\theta}
(7)

第二項はϵ\epsilonと関係無いので、ϵ\epsilonで微分すると消える

dΔϵdϵ=dθ^ϵ,zdϵ\frac{d \Delta_{\epsilon} }{d \epsilon} = \frac{d \hat{\theta}_{\epsilon, z} }{d \epsilon}
(8)

θ^ϵ,z\hat{\theta}_{\epsilon, z} は arg minの解なので最適性条件を満たす、つまりup-weightedされた経験リスクを微分してゼロとなるポイント

0=∇R(θ^ϵ,z)+ϵ∇L(z,θ^ϵ,z)0 = \nabla R(\hat{\theta}_{\epsilon, z}) + \epsilon \nabla L(z, \hat{\theta}_{\epsilon, z})
(9)

ϵ→0\epsilon \to 0とすると

θ^ϵ,z=arg⁡min⁡θ1n∑i=1nL(zi,θ)+ϵL(z,θ)→arg⁡min⁡θ1n∑i=1nL(zi,θ)+0=θ\hat{\theta}_{\epsilon, z} = \arg \min_{\theta} \frac{1}{n} \sum^n_{i=1} L(z_i, \theta) + \epsilon L(z, \theta) \to \arg \min_{\theta} \frac{1}{n} \sum^n_{i=1} L(z_i, \theta) + 0 = \theta
(10)

ゆえにθ^ϵ,z→θ^\hat{\theta}_{\epsilon, z} \to \hat{\theta}なので、テイラー展開f(x)=f(a)+f(a)(x−a)+⋯f(x) = f(a) + f(a) (x - a) + \cdotsを用いると

0=[∇R(θ^)+ϵ∇L(z,θ^)]+[∇2R(θ^)+ϵ∇2L(z,θ^)]Δϵ+o(∥Δϵ∥)≈[∇R(θ^)+ϵ∇L(z,θ^)]+[∇2R(θ^)+ϵ∇2L(z,θ^)]Δϵ\begin{align} 0 &= \big[ \nabla R(\hat{\theta}) + \epsilon \nabla L(z, \hat{\theta}) \big] + \big[ \nabla^2 R(\hat{\theta}) + \epsilon \nabla^2 L(z, \hat{\theta}) \big] \Delta_{\epsilon} + o(\| \Delta_{\epsilon} \|) \\ &\approx \big[ \nabla R(\hat{\theta}) + \epsilon \nabla L(z, \hat{\theta}) \big] + \big[ \nabla^2 R(\hat{\theta}) + \epsilon \nabla^2 L(z, \hat{\theta}) \big] \Delta_{\epsilon} \end{align}
(11)

となる。整理すると

Δϵ≈−[∇2R(θ^)+ϵ∇2L(z,θ^)]−1[∇R(θ^ϵ,z)+ϵ∇L(z,θ^)]\Delta_{\epsilon} \approx - \big[ \nabla^2 R(\hat{\theta}) + \epsilon \nabla^2 L(z, \hat{\theta}) \big]^{-1} \big[ \nabla R(\hat{\theta}_{\epsilon, z}) + \epsilon \nabla L(z, \hat{\theta}) \big]
(12)

であり、θ^\hat{\theta}はR(θ^)R(\hat{\theta})を最小化して∇R(θ^)=0\nabla R(\hat{\theta})=0になると考え、o(ϵ)o(\epsilon)の（ϵ\epsilonに比例する）項を消すと

Δϵ≈−[∇2R(θ^)+ϵ∇2L(z,θ^)]−1[∇R(θ^ϵ,z)⏟=0+ϵ∇L(z,θ^)]\Delta_{\epsilon} \approx - \big[ \nabla^2 R(\hat{\theta}) + \epsilon \nabla^2 L(z, \hat{\theta}) \big]^{-1} \big[ \underbrace{ \nabla R(\hat{\theta}_{\epsilon, z}) }_{=0} + \epsilon \nabla L(z, \hat{\theta}) \big]
(13)

より

Δϵ≈−∇2R(θ^)−1∇L(z,θ^)ϵ=−Hθ^−1∇L(z,θ^)ϵ\Delta_{\epsilon} \approx - \nabla^2 R(\hat{\theta})^{-1} \nabla L(z, \hat{\theta}) \epsilon \\ = - H_{\hat{\theta}}^{-1} \nabla L(z, \hat{\theta}) \epsilon
(14)

（ϵ∇L(z,θ^)\epsilon \nabla L(z, \hat{\theta})は残るのはなぜ？？？？）

よって

dθ^ϵ,zdϵ∣ϵ=0=−Hθ^−1∇θL(z,θ^)\left . \frac{d \hat{\theta}_{\epsilon,z} }{ d \epsilon } \right | _{\epsilon = 0} = -H^{-1}_{\hat{\theta}} \nabla_{\theta} L(z, \hat{\theta})
(15)

LOOの近似

もしϵ=−1n\epsilon = -\frac{1}{n}なら

θ^ϵ,z=arg⁡min⁡θ1n∑i=1nL(zi,θ)−1nL(z,θ)\hat{\theta}_{\epsilon,z} = \arg \min_{\theta} \frac{1}{n} \sum^n_{i=1} L(z_i, \theta) - \frac{1}{n} L(z, \theta)
(16)

もしzzが訓練データに含まれるなら、訓練データからzzを除去した場合と同様なので、LOOの考え方を近似できる

θ^−z−θ^≈−1nIup,params(z)\hat{\theta}_{-z} - \hat{\theta} \approx -\frac{1}{n} \mathcal{I}_{up, params}(z)
(17)

損失へのupweighting

データ点ztestz_{test}におけるinfluenceを計算するため、微分の連鎖律を使う

Iup,loss(z,ztest):=dL(ztest,θ^ϵ,z)dϵ∣ϵ=0=∇θL(ztest,θ^)⊤dθ^ϵ,zdϵ∣ϵ=0=−∇θL(ztest,θ^)⊤Hθ^−1∇θL(z,θ^)\begin{align} \mathcal{I}_{up, loss}(z, z_{test}) :&= \left . \frac{d L(z_{test}, \hat{\theta}_{\epsilon, z}) }{ d \epsilon } \right | _{\epsilon = 0} \\ &= \nabla_{\theta} L(z_{test}, \hat{\theta})^\top \left . \frac{d \hat{\theta}_{\epsilon, z} }{ d \epsilon } \right | _{\epsilon = 0} \\ &= - \nabla_{\theta} L(z_{test}, \hat{\theta})^\top H^{-1}_{\hat{\theta}} \nabla_{\theta} L(z, \hat{\theta}) \end{align}
(18)

ヘッセ行列の計算の高速化

nn個のデータとpp次元パラメータがあるとき、ヘッセ行列の逆行列はO(np3+p3)O(n p^3 + p^3)の計算量を要するので削減したい

  1. 共役勾配（conjugate gradients: CG）法

    • 連立一次方程式に帰着させて近似解を得る方法

  2. Hessian-vector products (HVPs)

    • ヘッセ行列とベクトルの積を近似推定する数学的トリックを使う方法

  3. Stochastic estimation (Agarwal et al., 2017)

    • SGDのようにランダムサンプリングしてCG法のiterationを回す

FastFI

Guo, H., Rajani, N. F., Hase, P., Bansal, M., & Xiong, C. (2020). Fastif: Scalable influence functions for efficient model interpretation and debugging. arXiv preprint arXiv:2012.15781.

Influence Functionは計算が重い

  1. データ点の評価はO(n)O(n)

  2. モデルパラメータのinverse Hessianの計算コストが高い

  3. 上記の計算は並列可能であるが、先行研究のアルゴリズムでは直列

FastIfのアイデア

  1. 全データを探索するのではなく、fast nearest neighbor search（Johnson et al., 2017）で探索範囲を狭め、桁違いに計算量を抑える

  2. Hessianの推定において、品質を保ちつつ時間を半分以下にするハイパーパラメータ集合を識別

  3. シンプルに並列計算へ拡張し、さらに2倍高速化

実験においてほとんどのケースで全体で2桁程度の高速化が確認された

LeafInfluence

Case-deletion importance sampling estimators

[0807.0725] Case-deletion importance sampling estimators: Central limit theorems and related results

Bayesian Modelのためのinfluence function的なアプローチ。データセットDDからサンプルiiを除いたデータD\iD^{\backslash i}の事後分布をP(θ∣D\i)P(\theta \mid D^{\backslash i})とすると、サンプルを抜いたことの影響を分布の密度比P(θ∣D\i)P(θ∣D)\frac{ P(\theta \mid D^{\backslash i}) }{P(\theta \mid D)} で評価できる。そしてこの密度比はデータを抜いて再学習しなくても計算可能、らしい。まだちゃんと読んでない。

機械学習
因果とSHAP
機械学習
Influence Function 線形回帰での例