Non-Sampling Learning for Personalized Recommendation

[参考]
*
*
*

• 基于用户偏好的个性化推荐机制中的未采样学习 - 陈冲
• B站视频：陈冲的《个性化推荐系统中的非采样学习》

现有的深度学习在大推荐系统任务中的研究主要聚焦于探索和引入不同类型的神经网络架构，在模型学习算法方面仍存在显著空白。
为了优化模型性能, 现有研究普遍采用负采样策略（Negative Sampling）进行训练。尽管该方法具有操作简便且易于实现的特点, 但近期研究表明其鲁棒性不足, 可能会导致重要训练样本被忽视而影响模型收敛至最优状态。
清华大学信息检索课题组（THUIR）首次提出并应用了非采样策略（Non-negative Sampling）到基于神经网络的大推荐系统中。
通过严谨的数学推导, 该研究设计了一系列高效的非采样学习算法, 将基于整体数据的学习时间复杂度较理论值下降了数十倍。
基于所构建的高效非采样算法框架, 分别开发了适用于不同应用场景的大推荐神经网络模型, 并在多个真实数据集上与现有state-of-the-art方法相比实现了显著提升效果, 包括训练时间和模型性能等多个方面。

填补了非采样神经网络推荐模型 研究的空白

Outline

1. background

2. Negative-Sampling VS Non-Sampling Learning

3. Efficient Non-Sampling Learning Method

4. Recommendation Models with Efficient Non-Sampling Learning

5. Discussion

1 Background

Value of Recommender System (RecSys)

• RecSys has evolved into the primary revenue generation mechanism for client-focused online services—essentially serving as a key profit channel.*

• For instance, e-commerce platforms facilitate direct sales through digital marketplaces, while new portals provide fresh content and user engagement.*

• Some statistics:

• YouTube Homepage garners an impressive share of online attention, with over 60% of clicks attributed to this platform.

• Among streaming giants, Netflix dominates with a staggering figure of over 80% movie rentals annually, delivering an estimated $1 billion in value.

• A significant portion of online traffic gravitates toward Amazon, with page views accounting for over a third.

推荐系统是当前解决信息过载，最有效的方法之一。

Users’ Sparse Feedback Information-用户的稀疏反馈信息

• Individuals commonly engage with items using implicit feedback（通常个体会通过隐式反馈与物品互动）

• For instance, individuals can utilize their viewing records and purchase history, as well as other metrics, to understand user preferences（例如，个体可以通过他们的查看记录和购买历史等指标来了解用户偏好）

• 利用隐式反馈数据存在困难……因为其本质上仅包含正向互动记录。

• 隐式反馈中包含的负面信息

• 比如说：当一个用户对某物品产生互动时（例如点击或购买），这通常意味着该物品可能具有吸引力。

• 然而如果一个用户未进行任何互动，则所获得的信息会不完整。

• 因此这些未被互动过的物品不能简单地被视为负样本。

• 其中未被点击或未被购买的商品数量较多……相对于那些经常被互动的商品来说，
  这种数据集的空间分布非常稀疏。

Individual users typically interact with a limited number of items when compared to a vast repository of hundreds of millions of items within the system.

2 Negative-Sampling VS Non-Sampling Learning

Applying Implicit Feedback Data: 负采样对比于非采样的学习方法

Two strategies have been widely used in previous studies:

Strategy for negative sampling which draws samples of negative instances from unlabeled data

Non-sampling (whole-dataset based) approach treats all unlabeled data as negatives

当采用隐式反馈数据时，在推荐系统中存在两类主要的学习策略用于应对这两种负样本的情况

1. 

负采样策略

是从所有用户中没有标记过的样例中抽取 一部分作为负例：

如我们推测，在用户的非购买商品集中可能存在一部分用户并不喜欢的商品；由于我们是从所有非购买商品中随机抽取一部分用于构建训练集D_{\text{train}}；该方法的优势在于其训练速度较快；然而其存在明显的缺陷：由于采样的随机性较大可能导致其无法捕捉到许多潜在的真实负样本；因此该方法的效果通常不够理想且稳定性较差；在实际应用中很难达到最佳效果

2. 

非采样策略

• 即认为用户未曾购买的商品均具备一定的负样本特征，并被归类为negative类别具有一定的权重系数
• 非采样技术充分利用了所有的数据信息从而实现了良好的覆盖效果
• 然而由于采用了全部的数据信息在实际应用中可能会面临较高的计算复杂度挑战

在传统的推荐算法中包括BPR（采用了负采样策略）、矩阵分解以及WMF（运用了加权矩阵分解而不依赖采样），

传统的方法通常不会过于复杂，
然而现在研究者们倾向于使用基于深度学习的方法，
而这些研究者们则更关注模型的结构，
通常会选择负样本抽样的策略。

The advancements in neural recommendation systems have been remarkable, but challenges remain. These models have achieved significant progress in accurately predicting user preferences based on vast datasets. However, they still face limitations such as cold start problems and scalability issues when dealing with sparse data.

然而目前在推荐系统任务中应用深度学习的主要方向包括侧重于探索...并采用多样化的神经网络架构。

• 方法在优化模型时常常被采用。
• 尽管如此，在实证研究中发现负样本的鲁棒性相对较低。

Complex Neural Network

Investigating novel deep learning architectures in recommendation systems. Among these include attention mechanisms, MLPs, and CNNs. The model demonstrates a remarkable capacity in handling intricate network configurations.

• With a large amount of parameters
  • Need extensive computations despite employing a sampling-based learning approach, particularly in the context of negative sampling.

Negative Sampling

• Lack strength or durability
  • Optimal performance in real-world scenarios is challenging to attain.

Are we able to identify some effective solutions for learning a neural recommendation model without the need for extensive sampling?

3 Efficient Non-Sampling Learning Method

非抽样学习方法的复杂性问题

为什么在现在的神经网络中没有使用非采样的方法：

1. 因为采用非采样的方法往往有很高的复杂度

• In implicit data, the user-item interactions R is defined as:

稀疏矩阵中，
R_{uv}=1 表示用户 u 购买了商品 v，
而 R_{uv}=0 则表示用户 u 没有购买商品 v。
因此，在这个矩阵中，
标记为1的数量相对较少，
因为大部分用户的购买记录为空。

• Hu et al. proposed the weighted regression loss for learning model parameters, assigning a confidence level to each predicted outcome.
• The conventional nonsampling learning typically employs weighted regression loss functions, commonly used in the 2008 formulation of weighted regression.

C_uv 代表权重参数；
R_{u,v} 表示真实评分（取值为0或1）；
\hat{R}_{u,v} 则是模型预测的结果（同样取值为0或1）；
右侧部分反映了该模型计算过程中的复杂性；
其中 B 表示批量大小；
V 包括 u 和 v（这些变量通常具有成千上万的数量）；
d 则代表嵌入空间的维度大小；
由此可知整体计算量预计达到百万到千万级别。

Efficient Non-sampling Learning Theorem

Loss Inference

在推导过程中，并未引入任何近似项。在计算梯度的过程中，上面提到的Loss与下面所说的高效Loss所得的结果完全一致。即没有进行过任何近似化处理 ==>> 实际上它不仅简化了计算过程，并且并非通过近似来简化。

应用

将高效的非采样的算法应用到推荐场景上：

Plain recommendation scenario (only the ID information is utilized):

We propose ENMF, 5%+ better and 30+ times faster than SOTA method (TOIS accept)

基础场景中：只使用用户和商品id，（ENMF：高效的非采样矩阵分解框架）

比SOTA方法在推荐效果上好5%，在推荐速度上快30倍以上

Social-aware recommendation scenario:

• Presenting EATNN, we demonstrate that the model improves performance by up to 4% and increases efficiency up to 7 times compared to the state-of-the-art method accepted at SIGIR 2019.
• Social-aware systems incorporate user social information, which enables the recommendation system to leverage relationships between users for personalized suggestions.

Multi-Behavior recommendation scenario:

这个系统建议实现一种改进型的方法，在效率上较现有最优算法提升了40%以上（AAAI 2020已接受）
多种用户交互行为即包括用户的点击操作、购买决策以及加入购物车等各类具体的行为表现
高效无采样协同过滤模型

Context-aware recommendation scenario:

• We present ENSFM, which is improved by up to 9% and faster by a factor of 5 compared to the SOTA method (WWW 2020 conference paper acceptance).
• In context-aware scenarios, we introduce a highly efficient non-sampling decomposition model.

4 Recommendation Models with Efficient Non-Sampling Learning

4.1 Plain recommendation scenario

只使用用户的id信息

• Highly efficient neural matrix factorization (ENMF) without any sampling
  • Input data:
    • User-based: a user account and all the items he/she has interacted with
    • Item-based: an item entity and all the users that have interacted with it

主要区别：

• 每一次输入均为一个user-item对，即为每个用户与相应商品的一次互动实例。
  • 本方法的输入分为两部分：一是每个用户与其相关商品集合；二是每个商品与其相关联的所有用户的集合。

[注]
Chong Chen and colleagues including Min Zhang and Yongfeng Zhang have authored the work alongside Yiqun Liu and Shaoping Ma. The study titled "Efficient Neural Matrix Factorization Without Sampling for Recommendation" was published in the ACM Transactions on Information Systems journal under the TOIS Vol. 38, No. 2 issue as Article 14.

User-based：

• 基于用户群体进行批量处理
• 为了进一步提升系统的扩展性，在后续工作中可引入更多关于用户的信息

Item-based：

• item作为batch索引
• 为了后面加入item相关的信息（如item的feature、knowledge）

（1）Experimental settings - 实验设计

Datasets:

在实验中使用了3个数据集，Ciao、Epinion、Movielens

Baselines:（比较的baseline）

BPR (UAI’09)

WMF (ICDM’08)

ExpoMF (WWW’16)

GMF (WWW’17)

NCF (WWW’17)

ConvNCF (IJCAI’18)

MP属于基础模型类

传统的非神经网络模型主要包括BPR、WMF和ExpoMF三种方法

广义矩阵分解法（GMF）是对矩阵分解进行了一定程度的扩展和优化

神经协同过滤器（NCF）起源于何老师于2017年的研究工作，在2018年后进一步发展为基于卷积神经网络的ConvNCF形式

Evaluation methods: HR@K, NDCG@K, K= 50, 100, 200

两种评价方式：HR, NDCG

（2）Model Comparisons

• Performance evaluation between two datasets across all methods
  • ENMF steadily surpasses the state-of-the-art baseline
  • achieves an improvement of over 4%

相较于现有方法而言更为出色，并且同样地，在传统的推荐算法中（其中基于采样的算法如WMF和ExpoMF），其学习性能优于BPR方法。

在神经网络领域中也能够观察到，在显著性水平上，ENMF超越了包括GMF、NCF和ConvNCF在内的其他模型，并表明非采样学习在神经网络中的有效性

（3）Efficiency Analysis

Comparison of runtime - 训练效率对比

• s: second; m: minute; h: hour; d: day
• S: training time for a single iteration;
• I: Overall iterations;
• T: Total time

10 times faster

GPU: GTX titan + 8核CPU

图1：每个epoch需要多少秒

表：这些模型在整体的数据集上训练完毕需要多少时间

s：代表单个epoch所需的时间（seconds per epoch）。
I：指总共需要进行的训练周期（total training epochs）。
采用无采样策略时，能够提高学习效率的同时所需总训练轮次会减少一些。

4.2 Social-aware Recommendation Scenario

即 用户的社交信息可以用来帮助进行用户偏好建模，提高推荐的准确性

• 利用用户的社交网络旨在减少数据稀疏性
• The effectiveness of recommender systems can be enhanced.
  == >> Social-aware recommendation

Shared preferences between the item domain and the social domain show variation across different users in real life.

开发了一种新型自适应迁移网络...用于社交关系分析领域，并在此基础上构建了一个创新性的新框架。该框架旨在改进现有迁移学习中的静态传输策略问题，在模型设计中融入了动态自适应学习机制。具体而言，在模型构建过程中引入了一种基于注意力机制的设计思路...从而实现了对每个用户量身定制的个性化迁移方案。此外，在算法层面进一步完善了高效的无采样算法体系...使其能够同时支持复杂的多任务学习需求。

• Efficient Adaptive Transfer Neural Network (EATNN)

左侧部分涉及用户与商品领域的互动机制，在推荐系统中采用矩阵分解方法进行模型构建；右侧则侧重于从用户的社交网络数据中提取行为特征与关系网络信息

Chong Chen, Min Zhang, Chenyang Wang, Weizhi Ma, Minming Li, Yiqun Liu and Shaoping Ma. 一种高效的自适应迁移神经网络用于社交感知推荐系统的研究与应用. 第42届国际 SIGIR 信息检索研究与开发研讨会. (SIGIR 2019)

（1）Attention-based Adaptive Transfer

模型上的 自适应迁移学习

• 用户在不同的领域中可能会有相似的兴趣。
• 其中一些用户的兴趣主要集中在商品上与社交活动相似；而另一些用户的兴趣则主要集中在社交活动上与商品选择上。
• 【

（2）Joint Learning

获得p_u与p_s后, 随后立即采用高效的无采样算法, 对两任务分别实施高效的无采样学习策略, 最终引入联合学习方法（通过特定参数将两损失函数融合）来进行训练。

（3）Experimental settings

Datasets:

这三个数据集组中包含了三种类型的互动关系：一种是用户与商品之间的互动关系；另一种是用户与用户的互动关系（其中一种是社交网络）。

Baselines:

BPR(UAI’09)

ExpoMF(WWW’16)

NCF (WWW’17)

SBPR (CIKM’14)

TranSIV (CIKM’17)

SAMN (WSDM’19)

复制代码

  * BPR、ExpoMF 和 NCF 不基于 social 信息
  * SBPR：基于 BPR 框架构建的社会化推荐模型
  * TranSIV：是一种非神经网络模型，并且其 Transform Learning 基于全局数据特征构建
  * SAMN：采用神经网络模型实现推荐任务，并不依赖于采样策略

Evaluation methods: Recall@K, NDCG@K, K=10, 50, 100

（4）Model Comparisons

• Performance assessment across three distinct datasets for all considered methods

  • Best Baselines:

    • TranSIV: non-neural architecture with complete dataset
    • SAMN: neural-based model trained on selected sample set

  • EATNN * Consistently significantly outperforms the best baseline

（5）Efficiency Analysis

• 收敛速度快（因为在每一轮中就考虑了所有的instance）

运行时间对比分析

4.3 Multi-Behavior Recommendation Scenario

消费者对商品的多维度互动记录（包括点击、浏览、收藏等行为特征）

例如，在用户的购买记录中很可能包含之前已放入购物车的商品；通常是他曾浏览过的产品；不同的情境下可能会产生不同的转换信息

• Diverse multi-behaviors (e.g., views, clicks, purchases) are ubiquitously present in various online platforms
  • There are strong interdependencies among distinctive behavioral patterns

[注]

Chong Chen, Min Zhang, Weizhi Ma, Yongfeng Zhang, Yiqun Liu and Shaoping Ma. Efficient Heterogeneous Collaborative Filtering without Negative Sampling for Recommendation. The 44th AAAI Conference on Artificial Intelligence. (AAAI 2020)

（1）Behavior Transferring

（2）Multi-task Learning

（3）Experimental settings

Datasets:

Baselines:

• 贝叶斯Personalized Ranking算法（2009年UAI会议）
• 显式矩阵分解方法（2016年WWW会议）
• 神经 Collaborative Filtering方法（2017年WWW会议）
• 基于内容的矩阵分解方法（2015年WWW会议）
• 多标签贝叶斯Personalized Ranking算法（2016年RecSys会议）
• NMTR是结合了来自两个不同会议（ICDE 2019和TKDE 2020）的研究成果的神经网络模型。

Evaluation methods: HR@K, NDCG@K, K=10, 50, 100

（4）Model Comparisons

对两个数据集进行性能对比分析，并评估多种方法的性能表现；其中非采样方法在多行为场景中表现出色，在多个关键指标上显著优于其他方法；该研究通过构建完整的实验框架，在不同场景下对各方法进行了全面评估，并通过统计分析验证了所提出方法的有效性

NMIR在每个样本中都进行了采样操作，并且仅包含阳性样本而没有阴性样本；每一次这样的采样操作都会带来较大的随机性，在一定程度上阻碍了模型的收敛
非采样的方法：在每次输入一个batch时（即一批数据），它的损失值（loss）会呈现出稳定的下降趋势

（5）Efficiency Analysis

运行时间比较
s为秒；m为分钟；h为小时；d为天。
S表示单次迭代的训练时间；
I代表整体迭代次数；
T为总耗时。

10 times faster

4.4 Context-aware Recommendation Scenario

Leveraging contextual information

用户的背景信息、商品特性以及当前交易的时间和地点等

Factorization Machines (FM) widely uses the negative sampling technique as a widely used solution.

用户将获得更多的偏好信息、个人特征以及商品属性等信息

怎么把这些额外的信息也引入进来呢？

——分解机模型是比较好的模型

Efficient Non-sampling Factorization Machines (ENSFM)

Chong Chen, Min Zhang, Weizhi Ma, Yiqun Liu and Shaoping Ma. Highly efficient non-sampling-based Factorization Machines for Context-Aware Recommendation framework. (Proceedings of the World Wide Web Conference) 2020 (WWW 2020).

（1）Proof

首先给出证明

两两之间的交互可以分为

• AB部分涉及了用户自身的功能交互；需要注意的是，这一部分内容与系统属性无关联。
• CD部分反映了项目内部的功能互动；值得注意的是，这一内容与用户体验无直接关联。
• AC、AD、BC及BD组合则代表了用户与项目的互动模式。

把前面的公式分解开来

证明：泛化的分解机模型可以转化为泛化的矩阵分解形式

（2）Efficient Mini-batch Learning Algorithm

Efficient Non-Sampling Learning Method就是在这种矩阵分解上做的

（3）Experimental settings

Datasets:

Frappe和Last.fm的数据集属于与CFM文章中的一样类型的数据集；该作者将他的数据集公开到了GitHub上。

Baselines:

* FM (ICDM 10)
* DeepFM (IJCAI 17)
* NFM (SIGIR 17)
* ONCF (IJCAI 18)
* CFM (IJCAI 19)
* ENMF (SIGIR 19)

Evaluation methods: HR@K, NDCG@K, K=5, 10, 20

（4）Model Comparisons

CFM：将模型设计得非常复杂，在model training上仍然采用负采样技术，则与其非采样方法相比效果差距明显

本研究对三种数据集上所有方法进行了性能对比分析。
其中最优基准为：
ENMF采用了全部数据；
CFM基于采样数据。

• ENSFM
  • Consistently significantly outperforms the best baseline

（5）Efficiency Analysis

Comparative analysis of runtime performance

Define the following time units as follows：s represents seconds, m denotes minutes, h indicates hours, and d stands for days.

S denotes the training duration required for each individual iteration.

I signifies the cumulative number of training iterations conducted.

T represents the aggregate training time expended over the entire process.

5 Discussion

• Recently, there has been a significant spike in interest recently regarding the application of novel neural networks for recommendation tasks.
• These models cannot guarantee improved performance due to their complexity, which makes optimization and tuning particularly challenging.
• We empirically demonstrate that selecting an appropriate learning method is significantly more crucial than employing advanced neural network architectures.
• Anticipating future research, we advocate prioritizing the design of models with enhanced learning algorithms tailored for specific tasks over the reliance on complicated structures and costly computational resources for incremental improvements.

[大佬Email]

• z-m@tsinghua.edu.cn
• cc17@mails.tsinghua.edu.cn

Github：

• https://github.com/chenchongthu/ENMF
• https://github.com/THUIR/ENMF