WSDM'22「Facebook」SVP-CF：采样方法哪家强？

秋枫学习笔记

发布于 2022-09-19 11:11:16

4040

发布于 2022-09-19 11:11:16

文章被收录于专栏：秋枫学习笔记

关注我们，提升学习效率

title：On Sampling Collaborative Filtering Datasets
link：https://cseweb.ucsd.edu/~jmcauley/pdfs/wsdm22.pdf
from：WSDM 2022
code：https://github.com/noveens/sampling_cf

1. 导读

本文主要是针对采样提出的对应方法，在实际工作中，通常面临的数据量是非常大的，并且有些数据是长尾分布的，稀疏的，有时需要对大型数据进行相应的采样后再进行模型的训练，本文一方面介绍了许多已有的方法，对于这方面不太了解的小伙伴可以阅读了解；另一方面，提出了一种新的方式，SVP-CF，来对数据进行采样。

文中涉及一些额外内容，可在“参考内容”中查看。

2. 方法

2.1 数据类型

一般推荐系统方法涉及三类数据，

显式数据，例如评分

r_i^u

等，可以用MSE等方法来衡量预测准确与否

隐式数据，例如点击，购买等，可以用AUC，Recall，nDCG等来衡量
序列数据，用户u的交互序列商品可以表示为

S^u=(S_1^u,...,S_{S^u}^u)

，一次序列来预测下一个可能交互的商品。

针对不同类型的数据可以采用不同的模型方法，本文主要采用以下方法对所提方法进行测试对比，他们能够适用的场景以及所采用的评价指标具体如下，

2.2 采样策略

给定用户-商品数据D，目标是通过采样策略s构建一个p%的子集

D^{s,p}

。在本文中，为了全面起见，作者考虑了八种流行的抽样策略的样本，可分为以下三类：

2.2.1 交互采样

首先是三种交互采样方式。

随机交互采样，随机从数据D中采样p%得到

D^{s,p}

。

用户历史分层采样，为了匹配D和

D^{s,p}

之间的用户频率分布，从每个用户的消费历史中随机抽取p%的交互。

用户历史时序采样，和随机分层采样不同，该方法从每个用户最近的交互数据中采样p%。

2.2.2 用户采样

随机用户采样，随机保留用户，迭代地保留随机用户的所有交互，直到保留了 𝑝% 的原始交互。
头部用户采样，不断地将最少交互数的用户从集合中删除，只保留头部用户

2.2.3 图采样

构建用户-商品交互二分图，然后进行采样。

基于中心的采样，计算每个节点的pagerank中心化分数，然后保留分数最大的节点的所有边，直到保留的交互数达到p%
随机游走采样，在图上执行多次随机游走并重新启动，并保留至少访问过一次的那些节点对之间的边。不断扩展直到 𝑝% 的初始边被保留
Forest-fire Sampling，这是一种雪球采样方法，通过随机“燃烧”访问节点的出边进行。它最初从一个随机节点开始，然后传播到以前未访问过的邻居的随机子集。一旦我们创建了具有 𝑝% 初始边的图子集，传播就会终止。

2.3 SVP-CF

基于代理的选择（Selection-Via-Proxy，SVP）[1]是针对分类数据集提出的，如cifar-10等。其思想是希望设计一个简单且高效的模型作为代理来定义每个数据点的重要性。本文就是基于SVP提出的，但是要将其用于CF数据，需要考虑以下几点，

数据异质性：与输入空间 X 和标签空间 Y 上的分类数据不同，CF（ Collaborative Filtering）数据由许多四元组 {𝑢，𝑖，r ，𝑡 } 组成。这种多模态数据为样本数据添加了许多不同的维度，使得定义有意义的采样器变得越来越复杂。
定义数据点的重要性：与分类不同，可以通过对保留数据的经验风险来衡量分类器的性能，作为推荐，有多种不同的场景以及大量相关评估指标。因此，将重要性标记技术用于推荐任务变得具有挑战性。
缺失数据：CF数据具有以下特点：稀疏、长尾分布、用户-商品交互矩阵的非随机缺失 (MNAR) 属性。https://wenku.baidu.com/view/68fe313ef5335a8103d2202c.html

由于用户-商品交互数据的异质性，我们可以以各种不同的方式进行子采样，即对用户，交互，商品等其中一类进行采样，文中作者讨论将SVP-CF应用于用户和交互采样的情况，其他情况亦可扩展。

无论是对用户还是交互进行采样，SVP-CF 通过在原始数据 D 上训练一个廉价的代理模型 P 并修改遗忘事件方法 [2] 以保留具有最高重要性的数据点。对于显式反馈，如果是采样交互，则数据点的重要性被定义为特定交互的平均MSE，如果采样用户，则数据点的重要性被定义为用户u的平均MSE；对于隐式或序列反馈，采用P的平均逆AUC作为数据点的重要性。

为了处理** MNAR 和长尾问题**，提出了 SVP-CF-Prop，它利用用户和商品的倾向来纠正分布不匹配，同时估计每个数据点的重要性。令

p_{u,i}=P(r_i^u=1|r^{*u}_i=1)

表示真实是交互的情况下，预测也是交互的概率，r表示相关性分数。E表示P的总共训练轮次。

\mathcal{P}_e

表示训练到第e轮次后的代理模型P，

I^+_u:=\{j|r_j^u>0\}

表示用户u的正交互的集合，

I^-_u:=\{j|r_j^u=0\}

表示负交互的集合。SVP-CF-Prop的重要性函数

I_p

定义为下式，其中的p_ui由下面的倾向性模型来建模得到。

\begin{array}{l} I_{p}(u \mid \mathcal{P}):=\frac{1}{\left|I_{u}^{+}\right|} \cdot \sum_{i \in I_{u}^{+}} I_{p}(u, i \mid \mathcal{P}) ; I_{p}(u, i \mid \mathcal{P}):=\frac{\Delta(u, i \mid \mathcal{P})}{p_{u, i}} \\ \text { where, } \quad \Delta(u, i \mid \mathcal{P}):=\left\{\begin{array}{l} \sum_{e=1}^{E}\left(\mathcal{P}_{e}(u, i)-r_{i}^{u}\right)^{2} \\ \text { (for explicit feedback) } \\ \sum_{e=1}^{E} \sum_{j \sim I_{u}^{-}} \frac{1}{\mathbb{1}\left(\mathcal{P}_{e}(u, i)>\mathcal{P}_{e}(u, j)\right)} \\ \text { (for implicit/sequential feedback) } \end{array}\right. \end{array}

倾向性建模

有许多方法可以对用户-商品交互的倾向性得分建模，包括逻辑回归等。这里倾向性得分计算公式如下，其中N_u,N_i分别表示用户和商品的总数，A和B是两个固定的标量，

C_u=(log(|U|)-1)\cdot (B+1)^A

C_i=(log(|I|)-1)\cdot (B+1)^A

\begin{aligned} p_{u, i} &=P\left(r_{i}^{u}=\left.1\right|\stackrel{*}{r}^{u}_i=1\right) \\ &=P\left(r^{u}=1 \mid \stackrel{*}{r}^{u}=1\right) \cdot P\left(r_{i}=\left.1\right|\stackrel{*}{r}_{i}=1\right)=p_{u} \cdot p_{i} \end{aligned}

p_{u}:=\frac{1}{1+C_{u} \cdot e^{-A \cdot \log \left(N_{u}+B\right)}} \quad ; \quad p_{i}:=\frac{1}{1+C_{i} \cdot e^{-A \cdot \log \left(N_{i}+B\right)}}

2.4 采样策略性能评价

令不同CF场景为f，评价指标为m，在全数据上推荐系统方法得到的性能表示为

R_{f,m}

，采样后的性能表示为

R_{f,m}^{s,p}

，其性能衡量可以由下式计算，这里的λ是常数，

\tau()

函数是 Kendall’s Tau系数，具体计算方式可从网上查找。https://blog.csdn.net/mba16c35/article/details/42490537

\Psi(\mathcal{D}, s)=\lambda \cdot \sum_{f} \sum_{m} \sum_{p} \tau\left(\mathcal{R}_{f, m}, \mathcal{R}_{f, m}^{s, p}\right)

3. 结果

image.png

参考内容

[1] Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. 2020. Selection via Proxy: Efficient Data Selection for Deep Learning. In ICLR https://blog.csdn.net/qq_39867051/article/details/106458329

[2] M. Toneva, A. Sordoni, R. Combes, A. Trischler, Y. Bengio, and G. Gordon. 2019. An Empirical Study of Example Forgetting during Deep Neural Network Learning. In ICLR.https://www.cnblogs.com/dushuxiang/p/10593310.html

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2022-01-18，如有侵权请联系 cloudcommunity@tencent.com 删除

https

网络安全

本文分享自秋枫学习笔记微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

https

网络安全

登录后参与评论

0 条评论

热度