1. Understanding Black-box Predictions via Influence Functions

[TOC]

ICML 2017 Best Paper, Link:
arxiv，原文
github，代码链接
Note 1，一个好的讲解博客
Note 2，论文作者的一个Talk，可以下载视频

1.1. 简介

这是ICML 2017的最佳论文，有时候虽然神经网络模型取得了非常高的预测精度，但是却无法解释模型是怎么得到这些结果的，这篇论文可以在一定程度上理解模型对于数据的敏感程度，分析每一个数据的变化将会对模型的参数和预测带来什么样的改变，并提出了一些有意思的用途。

主要解决的问题：计算改变一个训练数据之后对模型参数和模型预测的影响有多少。

1.1.1. 最有意思的一些结果

上图主要是训练了鱼和狗两个类别，绿点是与，红点是狗，左边的图纵坐标是删除一个训练数据后对于模型Loss的影响，横坐标是欧几里得距离。第二行是SVM线性模型，第三行是Inception网络模型，右边的图是模型对TestImage预测时最有帮助的图。这里也可以显示出来线性模型和网络模型在预测时的差异，线性模型会更倾向于通过欧几里得距离更近的点进行预测，而网络模型会在所有的数据上平等的学习模式，可能这也是网络模型优于线性模型的原因。

有没有办法欺骗精度很棒网络模型？这就是现在对抗样本正在做的事情，在测试样本中增加一个小的扰动就可以让精心训练的模型表现的像弱智一样。这篇文章不同于对抗样本，而是从训练数据出发，在训练数据中的一个样例中增加一个扰动，就让一整类的测试完全失效。这里分析了30个测试样例，然后在左上图的测试样本中增加一个小的扰动，就让其中16个测试样例的结果反转。

1.2. Approach

1.2.1. 一些符号的定义

符号	定义	解释
$\mathcal{X}$	输入空间	模型中的输入数据，比如一个图像
$\mathcal{Y}$	输出空间	模型中的输出数据，比如图像的Label
$z_{i}=(x_{i},y_{i}) \in \mathcal{X} \times \mathcal{Y}$	Training Point	一个输入和一个输出组成的训练点
$\theta \in \Theta$	Parameters	可以理解为一个模型的参数或者一个模型
$L(z_{i},\theta)$	Loss	损失函数
$\hat{\theta}=argmin_{\theta \in \Theta}\frac{1}{n}\sum_{i=1}^{N}L(z_{i},\theta)$	Empirical Risk Minimizer	最小化经验风险，可以简单理解为从一堆模型中挑选一个使得Loss最小的模型
$\hat{\theta}_{-z}=argmin_{\theta \in \Theta}\frac{1}{n}\sum_{z_{i}\neq z}L(z_{i},\theta)$	Removing a point z	去掉一个训练点之后模型参数的变化
$\hat{\theta}_{\epsilon,z}=argmin_{\theta \in \Theta}\frac{1}{n}\sum_{i=1}^{N}L(z_{i},\theta)+\epsilon L(z,\theta)$	Upweight z	对z增加一个权重
$z_{\delta}=(x+\delta,y)$	Perturbation	对输入数据增加一个扰动
$\hat{\theta}_{\epsilon,z_{\delta},-z}$	Perturbation	用 $z_{\epsilon}$ 代替z之后模型的变化，具体从右往左看参数，首先-z将原始数据删掉，然后添加一个增加扰动的新数据 $z_{\epsilon}$ ，并在这个新数据上附上权重 $\epsilon$

1.2.2. 更改一个训练点

为了了解一个训练数据是如何影响模型最后预测的，一个最简单的办法就是去掉这个训练点 $z$ ，然后重新训练，但是这样的代价难以承受。以前的一个工作描述了如何快速计算这种影响，在训练点z增加的权重对模型参数的影响如下：

$\begin{aligned} \mathcal{I}_{up,params}(z)=\frac{d\hat{\theta}_{\epsilon, z}}{d\epsilon}\vert_{\epsilon=0}=-H_{\hat{\theta}}^{-1}\nabla_{\theta}L(z,\hat{\theta}) \\ H_{\hat{\theta}}=\frac{1}{n}\sum_{i=1}^{N}\nabla_{\theta}^{2}L(z,\hat{\theta}) \end{aligned}$

其中H是Hessian矩阵并且假定是正定矩阵。这样，删除一个测试样例实质上是使得 $\epsilon=-\frac{1}{n}$ ，这样，就可以得到如下的封闭公式，这样就可以不用重新训练模型，而是求出其中最主要的Hession就可以了。

$\hat{\theta}_{-z}-\hat{\theta}\approx-\frac{1}{n}\mathcal{I}_{up,params}(z)$

同时，我们可以得到改变一个训练点是如何影响测试点的Loss的，由于这些都是封闭形式的公式，因而比原始问题要更容易计算得到。

$\begin{aligned} \mathcal{I}_{up,loss}(z,z_{test})&=\frac{dL(z_{test},\hat{\theta}_{\epsilon, z})}{d\epsilon}\vert_{\epsilon=0} \\ &=\nabla_{\theta}L(z_{test},\hat{\theta}_{\epsilon,z})^{\top}\frac{d\hat{\theta}_{\epsilon, z}}{d\epsilon}\vert_{\epsilon=0} \\ &=\nabla_{\theta}L(z_{test},\hat{\theta}_{\epsilon,z})^{\top}\mathcal{I}_{up,params}(z) \end{aligned}$

（closed-form expression）封闭形式或者解析解：意思是可以将一个迭代过程或者无限次运算写成一个简单的有限次计算函数。我最初在具体数学上接触到这个概念，比如一个无限求和函数， $\sum_{i=1}^{n}i$ ，可以写成一个封闭形式为： $\frac{n*(n+1)}{2}$ 。

1.2.3. 对训练数据进行扰动

沿用上述的定义，对于一个新的扰动 $z_{\delta}$ ，定义模型和影响如下：

$\begin{aligned} \hat{\theta}_{\epsilon,z_{\delta},-z}&=arg\min_{\theta \in \Theta}\frac{1}{n}\sum_{i=1}^{N}L(z_{i},\theta)+\epsilon L(z_{\delta},\theta)-\epsilon L(z,\theta) \\ \frac{d\hat{\theta}_{\epsilon,z_{\delta},-z}}{d\epsilon}\vert_{\epsilon=0}&=\mathcal{I}_{up,params}(z_{\delta})-\mathcal{I}_{up,params}(z) \\ &= -H_{\hat{\theta}}^{-1}(\nabla_{\theta}L(z_{\delta},\hat{\theta})-\nabla_{\theta}L(z,\hat{\theta}))\\ \hat{\theta}_{z_{\delta},-z}-\hat{\theta}& \approx -\frac{1}{n}(\mathcal{I}_{up,params}(z_{\delta})-\mathcal{I}_{up,params}(z)) \end{aligned}$

看起来这种扰动只能在微小的变化上起作用（即函数是连续的），但是可以通过插值将这种方法运用到离散的训练数据或者离散的标签中，但是如果输入是连续的并且扰动足够小，那么我们可以得到一个非常好的近似结果。

当损失函数L在x和 $\theta$ 上可微的时候，我们可以近似得到以下的公式，第三个公式是将扰动对于Loss函数的变化，通过这种变化可以找到一个足以欺骗模型的扰动。

$\begin{aligned} \|\delta\| \rightarrow 0, & \nabla_{\theta}L(z_{\delta},\hat{\theta})-\nabla_{\theta}L(z,\hat{\theta}) \approx [\nabla_{x}\nabla_{\theta}L(z,\hat{\theta})]\delta \\ \frac{d\hat{\theta}_{\epsilon,z_{\delta},-z}}{d\epsilon}\vert_{\epsilon=0} &\approx -H_{\hat{\theta}}^{-1}[\nabla_{x}\nabla_{\theta}L(z,\hat{\theta})]\delta \\ \mathcal{I}_{pert,loss}(z,z_{test})^{\top} &= \nabla_{\delta}L(z_{test},\hat{\theta}_{z_{\delta},-z})^{\top}\vert_{\delta=0} \\ &= -\nabla_{\theta}L(z_{test},\hat{\theta})^{\top} H_{\hat{\theta}}^{-1}[\nabla_{x}\nabla_{\theta}L(z,\hat{\theta})]\delta \end{aligned}$

1.2.4. 与欧式距离的关系

如果我们想知道在测试样本中有哪些会对模型预测产生较大的影响，比较简单的一个思路就是找到和这个测试样本最接近的训练数据，即寻找欧式距离最近的，然而这种方法并不是最优的。可以根据上文中的影响力公式来设置一个简单的验证方法，首先，为了简化计算，我们设置以下参数并得到计算公式：

$\begin{aligned} \sigma(t) &= \frac{1}{1+\exp(-t)} \\ L(z,\theta) &= \log(1+\exp(-y\theta^{\top}x)) \\ \nabla_{\theta}L(z,\theta) &= -\sigma(-y\theta^{\top}x)yx \\ H_{\theta} &= \frac{1}{n}\sum_{i=1}^{n}\sigma(\theta^{\top}x_{i})\sigma(-\theta^{\top}x_{i})x_{i}x_{i}^{\top} \\ \mathcal{I}_{up,loss}(z,z_{test}) &= -y_{test}y \cdot \sigma(-y_{test}\theta^{\top}x_{test}) \overbrace{\color{red}{\sigma(-y\theta^{\top}x)}}^{\text{Train Loss}} \cdot x_{test}^{\top} \overbrace{\color{red}{H_{\hat{\theta}}^{-1}}}^{\text{Hessian}} x \end{aligned}$

结果如上图所示，这里只有MNIST中1和7两个数据集，绿色是7类，红色是1类。（1）左图中的点是训练集中每一个样例对Test Image的影响程度，纵坐标表示原始的公式中的影响程度，横坐标分为三种，主要是公式中标红的两部分，第一部分是TrainLoss，第二部分是Hessian，将这两部分去掉之后的影响分数。（2）右图为TestImage和对预测最有害的数据，很显然这个模型认为这个右边这张图为7是比较不合理的。

由于原图的纵坐标没有标数据，我重新弄了一张图，这是对4和9进行对比，同时在实验的时候可以看到，这两个类别的影响就特别小，比上一个小了一个数量级，同时这种情况在2和8，1和8中同样存在。

1.3. 其他（存在的问题）

1.3.1. 加速计算

直接计算Hession矩阵是十分困难的，复杂度与模型的参数量直接相关，但是计算Hessian矩阵的方法已经十分成熟，可以使用近似的方法线性复杂度计算Hessian的近似值，比如Hessian-vector Products（HVPs），使用Conjugate gradients（共轭梯度）或者Stochastic estimation（随机估计）的方法进行近似。（这些方法我都不是很懂，有时间可能会新开一个文章专门介绍）

1.3.2. 非连续点

在模型计算中很容易产生一些不连续的值，由于方法本身需要损失函数（Loss）具有二阶可导的特性，这些不连续的值会破坏算法，因此这里使用SmoothHinge的方法剔除这些非连续点。

1.3.3. 全局最小值

在算法开始的时候， $\hat{\theta}$ 是找到一个最优的模型参数，但是很多时候模型可能根本到达不了这个最小值，因而Hessian有可能会出现负的本征值，在这里是使用凸二次近似方法对损失函数构建一个软极小值来近似。

论文笔记：Understanding Black-box Predictions via Influence Functions