主动学习中通常要评估样本的重要性/信息量，以选择最有价值样本使得模型提升最大。
这一点在样本可解释性中也有体现，即“什么样的样本对于训练来说更加重要？”
本文是几篇论文【1，2】的阅读笔记，从梯度的角度阐释样本对于最终测试集表现的影响。
训练样本如何影响测试表现【2】
自然的，去掉一个样本带来的参数变化可以写作 θ ^ − z − θ ^ \hat{\theta}_{-z}-\hat{\theta} θ ^ − z − θ ^
θ ^ − z = def arg min θ ∈ Θ ∑ z i ≠ z L ( z i , θ ) \hat{\theta}_{-z} \stackrel{\text { def }}{=} \arg \min _{\theta \in \Theta} \sum_{z_i \neq z} L\left(z_i, \theta\right)
θ ^ − z = def arg θ ∈ Θ min z i = z ∑ L ( z i , θ )
但是对于每一个样本而言，我们不可能总是去掉它并重新训练一个模型。
于是我们可以从 influence function 的角度来理解这个问题。
即计算样本权重变化一个很小的 ϵ \epsilon ϵ 1 n \frac{1}{n} n 1
θ ^ ϵ , z = def arg min θ ∈ Θ 1 n ∑ i = 1 n L ( z i , θ ) + ϵ L ( z , θ ) \hat{\theta}_{\epsilon, z} \stackrel{\text { def }}{=} \arg \min _{\theta \in \Theta} \frac{1}{n} \sum_{i=1}^n L\left(z_i, \theta\right)+\epsilon L(z, \theta)
θ ^ ϵ , z = def arg θ ∈ Θ min n 1 i = 1 ∑ n L ( z i , θ ) + ϵ L ( z , θ )
此时将样本 z z z θ \theta θ ϵ \epsilon ϵ
I up,params ( z ) = def d θ ^ ϵ , z d ϵ ∣ ϵ = 0 = − H θ ^ − 1 ∇ θ L ( z , θ ^ ) \left.\mathcal{I}_{\text {up,params }}(z) \stackrel{\text { def }}{=} \frac{d \hat{\theta}_{\epsilon, z}}{d \epsilon}\right|_{\epsilon=0}=-H_{\hat{\theta}}^{-1} \nabla_\theta L(z, \hat{\theta})
I up,params ( z ) = def d ϵ d θ ^ ϵ , z ϵ = 0 = − H θ ^ − 1 ∇ θ L ( z , θ ^ )
其中 H θ ^ = def 1 n ∑ i = 1 n ∇ θ 2 L ( z i , θ ^ ) H_{\hat{\theta}} \stackrel{\text { def }}{=} \frac{1}{n} \sum_{i=1}^n \nabla_\theta^2 L\left(z_i, \hat{\theta}\right) H θ ^ = def n 1 ∑ i = 1 n ∇ θ 2 L ( z i , θ ^ ) z z z ϵ \epsilon ϵ − 1 n -\frac{1}{n} − n 1 θ ^ − z − θ ^ \hat{\theta}_{-z}-\hat{\theta} θ ^ − z − θ ^ z z z
I up , loss ( z , z test ) = def d L ( z test , θ ^ ϵ , z ) d ϵ ∣ ϵ = 0 = ∇ θ L ( z test , θ ^ ) ⊤ d θ ^ ϵ , z d ϵ ∣ ϵ = 0 = − ∇ θ L ( z test , θ ^ ) ⊤ H θ ^ − 1 ∇ θ L ( z , θ ^ ) . \begin{aligned} \mathcal{I}_{\text {up }, \text { loss }}\left(z, z_{\text {test }}\right) &\left.\stackrel{\text { def }}{=} \frac{d L\left(z_{\text {test }}, \hat{\theta}_{\epsilon, z}\right)}{d \epsilon}\right|_{\epsilon=0} \\ &=\left.\nabla_\theta L\left(z_{\text {test }}, \hat{\theta}\right)^{\top} \frac{d \hat{\theta}_{\epsilon, z}}{d \epsilon}\right|_{\epsilon=0} \\ &=-\nabla_\theta L\left(z_{\text {test }}, \hat{\theta}\right)^{\top} H_{\hat{\theta}}^{-1} \nabla_\theta L(z, \hat{\theta}) . \end{aligned}
I up , loss ( z , z test ) = def d ϵ d L ( z test , θ ^ ϵ , z ) ϵ = 0 = ∇ θ L ( z test , θ ^ ) ⊤ d ϵ d θ ^ ϵ , z ϵ = 0 = − ∇ θ L ( z test , θ ^ ) ⊤ H θ ^ − 1 ∇ θ L ( z , θ ^ ) .
主动学习中对这一结论的运用【1】
依赖上一节中的影响力估计，训练集中样本 x x x x j x_j x j
I loss ( x , x j ) = 1 n ∇ θ L ( f θ ( x j ) ) ⊤ H θ − 1 ∇ θ L ( f θ ( x ) ) I_{\text{loss}}\left(x, x_j\right)=\frac{1}{n} \nabla_\theta L\left(f_\theta\left(x_j\right)\right)^{\top} H_\theta^{-1} \nabla_\theta L\left(f_\theta(x)\right)
I loss ( x , x j ) = n 1 ∇ θ L ( f θ ( x j ) ) ⊤ H θ − 1 ∇ θ L ( f θ ( x ) )
那么在整个测试集的总影响可以写作
∑ j I loss ( x , x j ) = 1 n ∑ j ∇ θ L ( T c + 1 ( x j ) ) ⊤ H θ − 1 ∇ θ L ( T c + 1 ( x ) ) \sum_j I_{\text{loss}}\left(x, x_j\right)=\frac{1}{n} \sum_j \nabla_\theta L\left(T^{c+1}\left(x_j\right)\right)^{\top} H_\theta^{-1} \nabla_\theta L\left(T^{c+1}(x)\right)
j ∑ I loss ( x , x j ) = n 1 j ∑ ∇ θ L ( T c + 1 ( x j ) ) ⊤ H θ − 1 ∇ θ L ( T c + 1 ( x ) )
其中 T c + 1 T^{c+1} T c + 1 c + 1 c+1 c + 1 c + 1 c+1 c + 1
L test ′ c + 1 = L test c + 1 + ∑ j I loss ( x , x j ) = L test c + 1 + 1 n ∑ j ∇ θ L ( T c + 1 ( x j ) ) ⊤ H θ − 1 ∇ θ L ( T c + 1 ( x ) ) \begin{aligned} L_{\text {test}}^{\prime c+1} &=L_{\text {test }}^{c+1}+\sum_j I_{\text {loss }}\left(x, x_j\right) \\ &=L_{\text {test }}^{c+1}+\frac{1}{n} \sum_j \nabla_\theta L\left(T^{c+1}\left(x_j\right)\right)^{\top} H_\theta^{-1} \nabla_\theta L\left(T^{c+1}(x)\right) \end{aligned}
L test ′ c + 1 = L test c + 1 + j ∑ I loss ( x , x j ) = L test c + 1 + n 1 j ∑ ∇ θ L ( T c + 1 ( x j ) ) ⊤ H θ − 1 ∇ θ L ( T c + 1 ( x ) )
由于测试集样本未知，即无法直接得到 ∑ j ∇ θ L ( T c + 1 ( x j ) ) ⊤ H θ − 1 ∇ θ L ( T c + 1 ( x ) ) \sum_j \nabla_\theta L\left(T^{c+1}\left(x_j\right)\right)^{\top} H_\theta^{-1} \nabla_\theta L\left(T^{c+1}(x)\right) ∑ j ∇ θ L ( T c + 1 ( x j ) ) ⊤ H θ − 1 ∇ θ L ( T c + 1 ( x ) )
L test ′ c + 1 = ∥ L test c + 1 + 1 n ∑ j ∇ θ L ( T c + 1 ( x j ) ) ⊤ H θ − 1 ∇ θ L ( T c + 1 ( x ) ) ∥ ≤ L test c + 1 + 1 n ∥ ∑ j ∇ θ L ( T c + 1 ( x j ) ) ⊤ H θ − 1 ∇ θ L ( T c + 1 ( x ) ) ∥ = L test c + 1 + 1 n ∥ ∇ θ L ( T c + 1 ( x ) ) ⊤ ∑ j H θ − 1 ∇ θ L ( T c + 1 ( x j ) ) ∥ ≤ L test c + 1 + 1 n ∥ ∇ θ L ( T c + 1 ( x ) ) ∥ ⋅ ∥ ∑ j H θ − 1 ∇ θ L ( T c + 1 ( x j ) ) ∥ \begin{aligned} L_{\text {test}}^{\prime c+1} &=\left\|L_{\text {test }}^{c+1}+\frac{1}{n} \sum_j \nabla_\theta L\left(T^{c+1}\left(x_j\right)\right)^{\top} H_\theta^{-1} \nabla_\theta L\left(T^{c+1}(x)\right)\right\| \\ & \leq L_{\text {test }}^{c+1}+\frac{1}{n}\left\|\sum_j \nabla_\theta L\left(T^{c+1}\left(x_j\right)\right)^{\top} H_\theta^{-1} \nabla_\theta L\left(T^{c+1}(x)\right)\right\| \\ &=L_{\text {test }}^{c+1}+\frac{1}{n}\left\|\nabla_\theta L\left(T^{c+1}(x)\right)^{\top} \sum_j H_\theta^{-1} \nabla_\theta L\left(T^{c+1}\left(x_j\right)\right)\right\| \\ & \leq L_{\text {test }}^{c+1}+\frac{1}{n}\left\|\nabla_\theta L\left(T^{c+1}(x)\right)\right\| \cdot\left\|\sum_j H_\theta^{-1} \nabla_\theta L\left(T^{c+1}\left(x_j\right)\right)\right\| \end{aligned}
L test ′ c + 1 = L test c + 1 + n 1 j ∑ ∇ θ L ( T c + 1 ( x j ) ) ⊤ H θ − 1 ∇ θ L ( T c + 1 ( x ) ) ≤ L test c + 1 + n 1 j ∑ ∇ θ L ( T c + 1 ( x j ) ) ⊤ H θ − 1 ∇ θ L ( T c + 1 ( x ) ) = L test c + 1 + n 1 ∇ θ L ( T c + 1 ( x ) ) ⊤ j ∑ H θ − 1 ∇ θ L ( T c + 1 ( x j ) ) ≤ L test c + 1 + n 1 ∇ θ L ( T c + 1 ( x ) ) ⋅ j ∑ H θ − 1 ∇ θ L ( T c + 1 ( x j ) )
而对于一个固定的测试集来说，∥ ∑ j H θ − 1 ∇ θ L ( T c + 1 ( x j ) ) ∥ \left\|\sum_j H_\theta^{-1} \nabla_\theta L\left(T^{c+1}\left(x_j\right)\right)\right\| ∑ j H θ − 1 ∇ θ L ( T c + 1 ( x j ) ) L test ′ c + 1 L_{\text {test}}^{\prime c+1} L test ′ c + 1 ∥ ∇ θ L ( T c + 1 ( x ) ) ∥ \left\|\nabla_\theta L\left(T^{c+1}(x)\right)\right\| ∇ θ L ( T c + 1 ( x ) ) c c c T c + 1 T^{c+1} T c + 1 T c T^{c} T c
L test ′ c + 1 ≤ L test c + 1 + 1 n ∥ ∇ θ L ( T c + 1 ( x ) ) ∥ ⋅ ∥ ∑ j H θ − 1 ∇ θ L ( T c + 1 ( x j ) ) ∥ ≲ L test c + 1 + 1 n ∥ ∇ θ L ( T c ( x ) ) ∥ ⋅ ∥ ∑ j H θ − 1 ∇ θ L ( T c + 1 ( x j ) ) ∥ \begin{aligned} L_{\text {test}}^{\prime c+1} & \leq L_{\text {test }}^{c+1}+\frac{1}{n}\left\|\nabla_\theta L\left(T^{c+1}(x)\right)\right\| \cdot\left\|\sum_j H_\theta^{-1} \nabla_\theta L\left(T^{c+1}\left(x_j\right)\right)\right\| \\ & \lesssim L_{\text {test }}^{c+1}+\frac{1}{n}\left\|\nabla_\theta L\left(T^c(x)\right)\right\| \cdot\left\|\sum_j H_\theta^{-1} \nabla_\theta L\left(T^{c+1}\left(x_j\right)\right)\right\| \end{aligned}
L test ′ c + 1 ≤ L test c + 1 + n 1 ∇ θ L ( T c + 1 ( x ) ) ⋅ j ∑ H θ − 1 ∇ θ L ( T c + 1 ( x j ) ) ≲ L test c + 1 + n 1 ∥ ∇ θ L ( T c ( x ) ) ∥ ⋅ j ∑ H θ − 1 ∇ θ L ( T c + 1 ( x j ) )
那么在主动学习的范畴下，更高的 ∥ ∇ θ L ( T c ( x ) ) ∥ \left\|\nabla_\theta L\left(T^{c}(x)\right)\right\| ∥ ∇ θ L ( T c ( x ) ) ∥ L test c + 1 L_{\text {test }}^{c+1} L test c + 1
具体梯度的计算需要通过 loss function 使用反向传播。
然而具体的真实标记并未获得，所以需要特地设计损失函数来计算梯度。
文章中提到了两种梯度的计算，第一种是 Expected-Gradnorm Scheme
L e x p ( T c ( x ) ) = ∑ i = 1 N P ( y i ∣ x ) L i ( T c ( x ) , y i ) \begin{equation}
L_{exp}\left(T^c(x)\right)=\sum_{i=1}^N P\left(y_i \mid x\right) L_i\left(T^c(x), y_i\right)
\end{equation}
L e x p ( T c ( x ) ) = i = 1 ∑ N P ( y i ∣ x ) L i ( T c ( x ) , y i )
另一种是 Entropy-Gradnorm Scheme
L e n t ( T c ( x ) ) = − ∑ i = 1 N P ( y i ∣ x ) log P ( y i ∣ x ) \begin{equation}
L_{e n t}\left(T^c(x)\right)=-\sum_{i=1}^N P\left(y_i \mid x\right) \log P\left(y_i \mid x\right)
\end{equation}
L e n t ( T c ( x ) ) = − i = 1 ∑ N P ( y i ∣ x ) log P ( y i ∣ x )
主动学习相关
当然也有很多其他的主动学习工作使用到了梯度，但是他们考虑问题的入手角度不同。
本文介绍的这种通过梯度的评估本质上是考虑其对测试误差的提升。
而其他的基于梯度方法通常是来评估样本对模型可能带来多大的改变，比如 EGL 和 BADGE。
尤其是 EGL，在形式上和本文介绍的方法很相似，不同的是其仅计算最后一层的梯度。
一些数学基础：Hessian 矩阵
黑塞/海森矩阵是在求多元函数的所有二阶偏导数。
具体来说，假设有一个实值函数 f ( x 1 , x 2 , … , x n ) f\left(x_1, x_2, \ldots, x_n\right) f ( x 1 , x 2 , … , x n )
H = [ ∂ 2 f ∂ x 1 2 ∂ 2 f ∂ x 1 ∂ x 2 ⋯ ∂ 2 f ∂ x 1 ∂ x n ∂ 2 f ∂ x 2 ∂ x 1 ∂ 2 f ∂ x 2 2 ⋯ ∂ 2 f ∂ x 2 ∂ x n ⋮ ⋮ ⋱ ⋮ ∂ 2 f ∂ x n ∂ x 1 ∂ 2 f ∂ x n ∂ x 2 ⋯ ∂ 2 f ∂ x n 2 ] \begin{equation}
\mathbf{H}=\left[\begin{array}{cccc}
\frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_1 \partial x_n} \\
\frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2} & \cdots & \frac{\partial^2 f}{\partial x_2 \partial x_n} \\
\vdots & \vdots & \ddots & \vdots \\
\frac{\partial^2 f}{\partial x_n \partial x_1} & \frac{\partial^2 f}{\partial x_n \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_n^2}
\end{array}\right]
\end{equation}
H = ∂ x 1 2 ∂ 2 f ∂ x 2 ∂ x 1 ∂ 2 f ⋮ ∂ x n ∂ x 1 ∂ 2 f ∂ x 1 ∂ x 2 ∂ 2 f ∂ x 2 2 ∂ 2 f ⋮ ∂ x n ∂ x 2 ∂ 2 f ⋯ ⋯ ⋱ ⋯ ∂ x 1 ∂ x n ∂ 2 f ∂ x 2 ∂ x n ∂ 2 f ⋮ ∂ x n 2 ∂ 2 f
用下标记号表示为 H i j = ∂ 2 f ∂ x i ∂ x j \mathbf{H}_{i j}=\frac{\partial^2 f}{\partial x_i \partial x_j} H ij = ∂ x i ∂ x j ∂ 2 f
可以在泰勒展开中理解这个矩阵。
在一元函数中，泰勒展开式为
f ( x ) = f ( x 0 ) + f ′ ( x 0 ) Δ x + f ′ ′ ( x 0 ) 2 ! Δ x 2 + ⋯ f(x)=f\left(x_0\right)+f^{\prime}\left(x_0\right) \Delta x+\frac{f^{\prime \prime}\left(x_0\right)}{2 !} \Delta x^2+\cdots
f ( x ) = f ( x 0 ) + f ′ ( x 0 ) Δ x + 2 ! f ′′ ( x 0 ) Δ x 2 + ⋯
相应的，在多元函数中
f ( x ) = f ( x 0 ) + ∇ f ( x 0 ) T Δ x + 1 2 Δ x T H ( x 0 ) Δ x + ⋯ f(x)=f\left(x_0\right)+\nabla f\left(x_0\right)^{\mathrm{T}} \Delta x+\frac{1}{2} \Delta x^{\mathrm{T}} \mathbf{H}\left(x_0\right) \Delta x+\cdots
f ( x ) = f ( x 0 ) + ∇ f ( x 0 ) T Δ x + 2 1 Δ x T H ( x 0 ) Δ x + ⋯
Reference
Wang, Tianyang, et al. “Boosting active learning via improving test performance.” Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 36. No. 8. 2022.
Koh, Pang Wei, and Percy Liang. “Understanding black-box predictions via influence functions.” International conference on machine learning. PMLR, 2017.
https://en.wikipedia.org/wiki/Hessian_matrix