基于比特级重要性编码的协同过滤算法

嘿，记得给“机器学习与推荐算法”添加星标

题目： Projected Hamming Dissimilarity for Bit-Level Importance Coding in Collaborative Filtering

会议： WWW2021

论文地址： https://arxiv.org/pdf/2103.14455.pdf

1 Motivation

在涉及到大量物品的推理任务时，一种常见的办法就是将数据样本映射到海明空间里，从而可以利用位运算进行高效的操作，数据样本之间的相似性可以通过学习其二值表示然后计算海明距离来实现。尽管这种办法很高效，但是二值表示的每一维度都是同等权重的，这意味着数据潜在的差异性息丢失了。

基于此，作者为了利用二值编码的高效性，同时保存数据的差异信息，提出了一种新的计算海明相似性的方法，并对二值编码的每一维度进行二值加权。

2 Methodology

2.1 Preliminaries

给定两个数据样本

和

，其中

和

分别表示

和

的哈希码，

为其哈希码长度。

和

之间标准的海明距离计算如下：

2.2 Projected Hamming dissimilarity for bit-level importance coding

与标准海明距离有着相似的formulation，但是物品哈希码

在用户哈希码

上的映射使得

获得了一个二元权重，这对应着用户哈希码

中不重要的比特位。

为了加速运算，作者将上述改写为：

2.3 PROJECTED HAMMING DISSIMILARITY IN COLLABORATIVE FILTERING

作者利用重构损失作为优化目标：

其中，

其中

为一个固定的放射转换，将映射的海明距离区间转换到评分区间。

对于用户和物品哈希码的生成，首先得到用户和物品的实值编码，再利用采样策略将其映射成哈希码：

其中，

为学到的用户第

个实值特征，

通过均匀采样得到。由于采样过程的不可微，利用straight-through estimator[1]进行反向传播

3 Experiments

Datasets

Yelp、ML-1M、ML-10M、Amazon

Metrics

NDCG、MRR

Baselines

DCF[2]、CCCF[3]、MFmean、MFmedian、VH

Results

（1）利用映射的海明距离优化的哈希码优于所有的哈希baselins；

（2）所提方法在MRR指标上获得的增益比NDCG的大，说明bit-level的重要性编码更影响排序列表的顶部；

（3）CCCF、DCF和VH有差不多的性能表现，说明利用标准的海明距离优化得到的哈希码在性能上有潜在的性能上界；

（4）实值的MF优于所有的哈希方法，说明浮点数的表示能力优于哈希码。

作者将所有用户按照其NDCG@10排序得到如图1所示结果：

（1）论文所提方法优于所有哈希方法，说明映射的海明距离具有鲁棒性；

（2）在ML-10M上的20,000个用户，MF的性能最差，说明MF并不总是优于哈希方法；

（3）在Amazon数据集上，用户区间为[80000,120000]，哈希方法都差于MF，说明哈希码相对于实值表示表示能力有限。

作者按照用户活跃度将其进行排序，得到如图2所示结果：

（1）对于低活跃度的用户表现性能都较好，随着活跃度的上升，性能逐渐下降；

（2）在除了Yelp的其余数据集上，在低活跃度的时，哈希方法与MF性能所差无几，随着用户活跃度上升，开始出现较大性能gap。

作者研究了用户的平均物品流行度对性能的影响，得到了如图3所示结果：

（1）有着高物品流行度的用户表现性能较好，反之，性能较差，这是因为流行物品在训练过程能够经常被训练到，不论是哈希码还是实值表示，都可以得到较好的物品表示。

作者验证了训练和评测过程中哈希码的采样策略对性能的影响，实验结果如图4所示，发现在训练过程中使用随即采样，评测过程中使用确定采样，实验性能最好。

作者进行了效率实验，结果如图5和表2所示，发现所提方法均优于baselines。

References

[1] Yoshua Bengio, Nicholas Léonard, and Aaron Courville. 2013. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint arXiv:1308.3432 (2013).

[2] Hanwang Zhang, Fumin Shen,Wei Liu, Xiangnan He, Huanbo Luan, and Tat-Seng Chua. 2016. Discrete collaborative filtering. In Proceedings of the International ACM SIGIR Conference on Research and Development in Information Retrieval. 325–334.

[3] Chenghao Liu, Tao Lu, Xin Wang, Zhiyong Cheng, Jianling Sun, and Steven C.H. Hoi. 2019. Compositional Coding for Collaborative Filtering. In Proceedings of the International ACM SIGIR Conference on Research and Development in Information Retrieval. 145–154.