Koh P W, Liang P. Understanding black-box predictions via influence functions[C]. international conference on machine learning, 2017: 1885-1894.
@article{koh2017understanding,
title={Understanding black-box predictions via influence functions},
author={Koh, Pang Wei and Liang, Percy},
pages={1885--1894},
year={2017}}
概
本文介绍了如果计算(估计)损失关于样本的一些影响因子, 并介绍了一些应用范围.
主要内容
假设样本(z_1,ldots, z_n), (z_i = (x_i,y_i) in mathcal{X} imes mathcal{Y}), 通过最小化经验损失
[hat{ heta} := arg min_{ heta in Theta} frac{1}{n} sum_{i=1}^n L(z_i, heta),
]
找到最优解.
且假设(L)关于样本和参数都是二阶可导且强凸的.
样本重要性分析
显然, 此时给定一个测试样本(z_{test}), 其对应的损失为(L(z_{test},hat{ heta})), 那么衡量一个样本重要性的一个重要指标便是, 倘若在移除样本(z)的情况下重新训练模型, 对应的参数和损失的变化.
假设在移除样本(z)的情况下训练得到的最优参数为(hat{ heta}_{-z}), 并引入
[hat{ heta}_{epsilon, z} := arg min_{ heta in Theta} frac{1}{n}sum_{i=1}^n L(z_i, heta)+epsilon L(z, heta),
]
易得(hat{ heta}_{-z} = hat{ heta}_{-frac{1}{n},z}).
则
[ ag{1}
mathcal{I}_{up, params} (z) := frac{d hat{ heta}_{epsilon, z}}{d epsilon}|_{epsilon=0} = -H_{hat{ heta}}^{-1}
abla_{ heta} L(z, hat{ heta}),
]
其中(H_{ heta}:= frac{1}{n} sum_{i=1}^n
abla_{ heta}^2 L(z_i, hat{ heta})).
我们可以得到, 参数的变化量的一阶近似
[hat{ heta}_{-z} - hat{ heta} approx -frac{1}{n} mathcal{I}_{up,params} (z).
]
进一步, 我们定义损失的变化量
[ ag{2}
egin{array}{ll}
mathcal{I}_{up, loss} (z, z_{test})
& := frac{dL(z_{test}, hat{ heta}_{epsilon, z})}{d epsilon} |_{epsilon = 0} \
& =
abla_{ heta} L(z_{test}, hat{ heta})^T frac{d hat{ heta}_{epsilon, z}}{d epsilon} |_{epsilon = 0} \
& = -
abla_{ heta} L(z_{test}, hat{ heta})^T H_{hat{ heta}}^{-1}
abla_{ heta} L(z, hat{ heta}).
end{array}
]
样本摄动对损失的影响
倘若我们对其中一个样本(z)添加一个扰动(delta), 并在新的数据(z_{delta}:=(x+delta,y))上训练, 得到模型, 其参数和损失会如何变化?
我们定义
[hat{ heta}_{epsilon, z_{delta}, -z}:= arg min_{ heta in Theta} frac{1}{n} sum_{i=1}^n L(z_i, heta) + epsilon L(z_{delta}, heta)-epsilon L(z, heta),
]
并令(hat{ heta}_{z_{delta},-z}:= hat{ heta}_{frac{1}{n}, z_{delta}, -z})
同样可以证明
[ ag{3}
frac{d hat{ heta}_{epsilon, z_{delta}, -z}}{d epsilon} |_{epsilon=0} = -H_{hat{ heta}}^{-1} (
abla_{ heta} L(z_{delta}, hat{ heta}) -
abla_{ heta} L(z, hat{ heta})).
]
则
[hat{ heta}_{z_{delta}, -z}-hat{ heta} approx -frac{1}{n}H_{hat{ heta}}^{-1} (
abla_{ heta} L(z_{delta}, hat{ heta}) -
abla_{ heta} L(z, hat{ heta})) approx -frac{1}{n} H_{hat{ heta}}^{-1}
abla_x
abla_{ heta} L(z_{delta}, hat{ heta}) delta.
]
故
[ ag{5}
mathcal{I}_{pert, loss}(z, z_{test})^T:=
abla_{delta} L(z_{test}, hat{ heta}_{z_{delta},-z})^T approx -frac{1}{n}
abla_{ heta} L(z_{test}, hat{ heta})^T H_{hat{ heta}}^{-1}
abla_x
abla_{ heta} L(z, hat{ heta}).
]
注:文章这里没有(frac{1}{n})且是等号(我卡在这个地方了, 推不出来).
高效计算(H^{-1})
共轭梯度
此时我们不是计算(H_{hat{ heta}}^{-1}), 而是计算(s:=H_{hat{ heta}}^{-1}v), 比如在计算(mathcal{I}_{up, loss})的时候, (v=
abla_{ heta} L(z_{test}, hat{ heta})), 则对于固定的(z_{test})想要知道不同的(z_i)的影响可以直接用(s^T
abla_{ heta} L(z_i, hat{ heta})), 避免了重复运算.
即求解
[arg min_t quad frac{1}{2} t^TH_{hat{ heta}}t - v^Tt,
]
假设第(k)步为
[t=t_k,
]
则利用精确直线搜索
[arg min_{p} frac{1}{2} t_{k+1}^T H_{hat{ heta}}t_{k+1}-v^Tt_{k+1}, : mathrm{s.t.} : t_{k+1}=t_k + p(H_{ heta}t_k -v),
]
得
[p= -frac{Delta^T H_{hat{ heta}}t_k-v^TDelta}{Delta^T H_{hat{ heta}} Delta}, Delta=H_{hat{ heta}}t_k-v.
]
随机估计
这里是估计(H_{hat{ heta}}^{-1}), 为了符号简便省略下表, 因为(H^{-1}=sum_{i=0}^{+infty}(I-H)^i), 用(H_j^{-1}= sum_{i=0}^j (I - H)^i)表示前(j+1)项的和, 易知
[H_j^{-1} = I + （I -H)H_{j-1}^{-1}, H_j^{-1}
ightarrow H^{-1}.
]
我们从样本中均匀挑选, 计算(
abla_{ heta}^2 L(z_i, hat{ heta})) 作为(H)的替代, 则
[ ilde{H}_j^{-1}=I+(I-
abla_{ heta}^2 L(z_{s_j}, hat{ heta})) ilde{H}_{j-1}^{-1}.
]
当然, 处于稳定性的考虑, 我们可以一次性采样多个来作为(H)的替代.
一些应用
- 探索模型关于样本的内在解释, 即什么样的样本模型会更加偏好之类的;
- 生成对抗样本;
- 检测目标数据分布和训练分布是否一致;
- 检测训练数据的标签是否正确.
附录
(1)的证明
定义(Delta_{epsilon}:= hat{ heta}_{epsilon, z}-hat{ heta}), 则
[mathcal{I}_{up, params} (z) = frac{d Delta_{epsilon}}{d epsilon} |_{epsilon =0}.
]
由一阶最优条件可知
[0= frac{1}{n} sum_{i=1}^n
abla_{ heta} L(z_i, hat{ heta}) := R(hat{ heta}), \
0= R(hat{ heta}_{epsilon, z}) + epsilon
abla_{ heta} L(z, hat{ heta}_{epsilon, z}),
]
把(hat{ heta}_{epsilon, heta})看成自变量(固定(epsilon)), 第二个等式右边是关于这个变量的一个函数, 则其在(hat{ heta}_{epsilon, heta}=hat{ heta})处的泰勒展式为
[R(hat{ heta}) + epsilon
abla_{ heta} L(z, hat{ heta})+ [
abla_{ heta} R(hat{ heta}) + epsilon
abla_{ heta}^2 L(z, hat{ heta})] Delta_{epsilon} + o(Delta_{epsilon})=0
]
故
[Delta_{epsilon} = -[
abla_{ heta} R(hat{ heta}) + epsilon
abla_{ heta}^2 L(z, hat{ heta})] ^{-1} [0 + epsilon
abla_{ heta} L(z, hat{ heta})+o(Delta_{epsilon})],
]
因为(epsilon
ightarrow 0), (Delta_{epsilon}
ightarrow0) 易知,
[frac{d Delta_{epsilon}}{d epsilon |_{epsilon =0}} = -H_{hat{ heta}}^{-1}
abla_{ heta} L(z, hat{ heta}).
]