文章名称

【KDD-2020】【Netflix/Spotify】Counterfactual Evaluation of Slate Recommendations with Sequential Reward Interactions

核心要点

文章旨在流式推荐系统中，准确对序列推荐模型的好坏进行离线评估的问题，以及如何改进现有序列推荐模型。现有方法要么具有较大的方差（主要是数据稀疏造成的）要么需要遵循过强的独立性假设。作者提出RIPS，基于图相关的因果关系假设，以近似估计目标策略下，页面期望收益总和的方式，来加权历史训练样本的收益进行模型训练。这种做法，使得序列推荐模型具有较低的方差，并且允许序列中的物品受到顺序交互的。同时，该方法是渐进无偏的。

上一节介绍了slate推荐场景下离线评估目标模型的背景和挑战，并介绍了作者在该场景下对IPS方法的定义。本节继续介绍如何解决IPS存在的问题。

方法细节

问题引入

如上一节所述，现有的IPS方法存在高方差的问题，尤其是在状态空间（在off-policy evaluation里是动作空间）较大的场景下，如推荐场景。主要有两方面原因，造成推荐场景下动作空间的庞大，

候选物品数量较多，例如内容推荐场景，候选物品可能上亿或十亿。
推荐列表一般是多个结果的有序组合，即top- $K$ 排序列表。不同物品之间在排序结果中存在交互影响，并且对最终目标起到至关重要的作用。同时，这种交互影响，也不允许我们把每一个排序的列表当做独立的动作看待，因为其打破了SUVTA的假设。因此，不能通过假设物品间影响独立等方法简化动作空间（也就是不能简单的进行因子分解）。

综上，我们必须寻找一种方法，把推荐列表当作action（或者说treatment），并解决方差大的问题。

具体做法

IIPS

首先，让作者仔细分析了独立性假设下的IPS方法，并对比了没有任何假设的IPS方法与独立假设下IPS方法的因果图。独立假设下的IPS方法利用item-position click模型，假设某个物品的点击概率只和物品本身的特征以及它在排序列表中的位置有关系，其具体的估计公式如下图所示。

IIPS estimatior

作者表示IIPS方法是不同IPS方法的一阶近似[1,2]，其因果图与通用的IPS因果图如下中，子图a和子图b所示。

causal graph of IPSs

作者表示IIPS的方式足以达到降低方差的目的，但是，如上所述，独立假设过强，忽略了交互影响，导致估计结果是有偏的。

Pseudoinverse Estimator

[4]提出了pseudoinverse estimator假设slate-level的收益是其中每一个子动作收益的线性组合，并且不假设子动作的收益可以被观测到（或者说假设不需要观测到）。换句话所，整个推荐列表的收益，是列表中灭一个物品的收益的线性组合。

上述线性假设结合连续性的假设，即 $h(A|X) > 0 \Rightarrow \pi(A|X) > 0, \forall A, X$ ，可以将off-policy evaluation的问题变为线性回归问题，其具体估计公式如下图所示。

PI estimator

其中， $\mathbf{1}_{A^{(n)}}$ 表示物品的位置示性向量。 $\dagger$ 表示pseudoinverse of a matrix，详情参见引文[4]。PI方法的线性思想，仍然假设子动作之间是相互独立的。并且，没有办法把整个slate的收益归集到某个特定的子动作上。

RIPS

为了解决IIPS中，物品（也就是单个action）和当个物品收益（reward）之间没有相互联系的问题，作者假设位置 $k$ 的收益与第 $k$ 个物品的特征以及前一个（ $k − 1$ ）个物品的特征和收益相关。其因果关系（因果关系，或者按作者所说，其马尔科夫结构）如图1的子图c所示。

由于存在复杂的依赖关系，因为不能直接利用简单的样本求和来代替期望值。所以，采用嵌套期望的方式估计目标模型的收益期望，具体的公式如下图所示。

nested expectation

利用IS进行权重调节后，得到的估计公式如下图所示，可以看出，在推荐列表末尾的物品依赖关系比较长，依然会受到较小概率的影响，导致方差过大（因为是概率的乘积，乘积越多概率越小，并且分子分母可能不在一个量级）。

nested expectation with IS

为了解决上述问题，作者采用了两项技术，

normalization

lookback capping

由于任何子列表 $A_{1:k}$ ，其权重的期望（只看权重，不看收益）始终为1，具体原因如下图所示。

expected reweighting factor

基于此，可以利用一种迭代normalization的方法来近似nested expectation，也就是所谓的RIPS方法，具体公式如下图所示，其中 $\gamma_k^{(n)}$ 表示积累的信息。

RIPS

但是，当 $k$ 较大的时候，比如推荐列表的结尾，物品仍然受到较大累积量（仍然是嵌套的关系）的影响。Normalization只是转化了问题，并没有完全解决。

作者采用lookback capping[3]，选择足够数量的lookback距离（也就是判断到底需要依赖多久以前的物品的影响）来简化嵌套深度，减少方差影响。该方法计算e�ective sample size (ESS) ，其具体公式如下图所示。

EES

通过超参数 $t$ ，控制 $ESS > Nt$ ，来平衡偏差和方差，因为如果lookback越少（也就是简化后的依赖深度越小），可能损失的交互影响越多，也就越有偏。

值得注意的是，作者表示不需要进行lookahead，因为依赖关系是从前到后。

心得体会

Direct Method（model-based method）

作者提到，尽管假设了物品之间的顺序依赖关系，但并没有直接假设其背后的模型，而如果直接使用模型就是所谓的Direct Method（这个说法更符合causal inference场景的认知，一般EIB的方法就是所谓的Direct Method，直接估计可能的收益，作为插值。而更偏policy evaluation的说法是Model-based method，直接建模收益的生成过程的模型。）

个人感觉，其实可以理解为是更简单的假设，没有建立复杂的模型关系，把作者提到的线性依赖推广，就得到了更复杂的模型，也算是一种复杂度和实用性，有效性的平衡。

ESS

如前所述，个人觉得文章的核心是超参数 $t$ ，本质上还是在平衡方差和偏差，只不过转化成了 $ESS > Nt$ 。

文章引用

[1] StephenBonnerandFlavianVasile.2018.Causalembeddingsforrecommendation. In Proceedings of the 12th ACM Conference on Recommender Systems. ACM, 104– 112.

[2] Prem Gopalan, Jake M Hofman, and David M Blei. 2015. Scalable Recommenda- tion with Hierarchical Poisson Factorization.. In UAI. 326–335.

[3] Lihong Li, Wei Chu, John Langford, and Robert E Schapire. 2010. A contextual- bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web. ACM, 661–670.

[4] Yixin Wang and David M Blei. 2018. The blessings of multiple causes. arXiv preprint arXiv:1805.06826 (2018).

因果推断推荐系统工具箱 - RIPS（二）

因果推断推荐系统工具箱 - RIPS（二）

文章名称

核心要点

方法细节

问题引入

具体做法

IIPS

Pseudoinverse Estimator

RIPS

心得体会

Direct Method（model-based method）

ESS

文章引用