文章名称
【SIGIR-2020】Influence Function for Unbiased Recommendation
核心要点
继续上节对IF的讨论，并进一步分析如何利用IF进行样本权重调节来实现数据纠偏，讨论IF可以纠偏的基理。简述如何对IF进行求解。
方法细节
问题引入
上一节讨论了IF是什么，以及相对于IPS方法IF方法的优势。那么，1）为什么IF可以进行纠偏，2）又是如何加权样本的（权重怎么求解），3）怎么求解IF的值？
具体做法
如上一节所述，单个样本的损失函数可以表示为如下图所示的式子。
因此，训练样本对所有验证集的影响可以表示为如下图所示的式子。如果
是训练样本
上的小扰动，
是这个扰动后的最优模型参数。那么，利用如下式子近似代替（估计）验证损失的变化。
对所有个训练样本，验证损失的变化如下图所示。
把这个损失变化融合到模型训练的ERM中，其结果如下图所示。可以看到，它与IPS具有相同的权重调节的结构，每个样本的权重为，其中
是为了平衡bias和variance进行的权重截断。
进一步，一个比较好的权重应该满足最小化无偏验证损失的条件，可以被形式化的表示为如下图所示的式子。
从上式可以看出，较小的样本
具有较大的样本权重
。公式3表示
由两部分组成，1）
表示在无偏的验证数据集上利用随机梯度下降法得到的参数梯度方向（相对于最优梯度
来说）；2）
有偏训练样本
对
的梯度方向的更新（因为是二阶导，所以是梯度方向的改变量）。因此，如果这两部分方向更相近，则
更小。增大这两部分方向更相近的样本的权重，能够促使模型的学习朝向无偏验证集合的方向前进。这两点是IF可以用来纠偏的主要原因和动机，因为不需要求解Propensity Score，所以可以避免overlap（样本重叠，在不同Propensity的情况下都存在类似的或相同的样本）和unconfounderness（无未观测混淆变量）等IPS必备的假设。
理论上，是有最优解的，即
。之前的方法[1]令
。但是由于这两种方法将不能保证莱伯尼茨连续，进而导致样本对验证集合过拟合，因此作者提出了如下图所示的权重计算方式，其中
，是超参数（有点类似softmax里的
）。
作者表示，这种类似sigmoid的函数是对公式5的一个平滑，而公式5是一个阶梯函数（不方便优化）。此外，经验估计时，服从正态分布，因此依据[2]中的做法，加入所以
和为1的约束，即
。
最后也是最重要的问题是如何计算IF。作者采用共轭提的方法（CG[3]）计算如下式子中的。随后，利用
计算每一个样本
的IF值。不同的损失函数或者模型需要由于，问题突性的原因，需要采用不同的损失函数。作者分析了LR方法，由于是凸优化，可以采用Mixed Preconditioned CG[4]来减少CG的迭代步数。而FM方法，由于非凸导致这种模型下的海森矩阵可能不是正定的，需要利用Gauss-Newton[5]方法来计算。具体的过程可以参见文章的附录部分[6]。
代码实现
IF4Rec的伪代码如下图所示。
心得体会
权重截断
在IPS的方法中，经常会使用到权重截断的方式进行偏差和方差的平衡，该方法也可以被应用到IF的方法中。
文章引用
[1] Ren, M., Zeng, W., Yang, B., and Urtasun, R. Learning to reweight examples for robust deep learning. arXiv preprint arXiv:1803.09050 (2018).
[2] Huang, J., Gretton, A., Borgwardt, K., Schölkopf, B., and Smola, A. J. Cor- recting sample selection bias by unlabeled data. In Advances in neural information processing systems (2007), pp. 601–608.
[4] Hestenes, M. R., and Stiefel, E. Methods of conjugate gradients for solving linear systems. JRNBS 49 (1952), 409–436.
[4] Hsia, C.-Y., Chiang, W.-L., and Lin, C.-J. Preconditioned conjugate gradient methods in truncated newton frameworks for large-scale linear classification. In Asian Conference on Machine Learning (2018), pp. 312–326.
[5] Schraudolph, N. N. Fast curvature matrix-vecctor products for second-order gradient descent. Neural Computation 14 (2002), 1723–1738.
