问题背景

本文主要介绍一种融合社交关系的隐式矩阵分解的方法,在物品推荐时,融合关系链可以进一步提升推荐效果。物以类聚,人以群分,此现象启发了笔者在此方向做尝试,举几个例子:

  1. 好友给你推荐了几本书,你会发现有一种相见恨晚的感觉
  2. 你可能和你的朋友喜欢相同的一款奈雪果茶
  3. 坐了你朋友的车后,你也买了同样的车型。

基于这些现象,笔者总结一个基本假设:朋友之间有相同的特质,这种特质使得我们成为好友的可能性变大,同时也控制着我们对物品的喜好。通过关系链,将朋友交互过的物品传递给用户,应该可以提升推荐效果。

恰好笔者的工作环境中有大量的关系链数据,并且之前笔者研究过隐式矩阵分解(IMF)推荐技术,并且在实践中大规模的应用该方法,该方法在大部分场景上取得了不错的效果。IMF的主要优势是仅需用户物品的隐式交互数据(如购买次数,使用次数,消耗时长等)即可快速上线,无需大量特征工程,并且可以使用廉价CPU进行大规模并行计算(SPARK),轻松处理上亿数据。所以,希望能够在保留这些特性的基础上充分利用关系链,达到一举两得的效果。

IMF算法本质上可以抽象为, \(\text{User} + \text{Item} \xrightarrow{\text{Embedding}} \text{Ranking}\)

若在此算法基础上融合关系链,新的算法可以抽象为,

\[\text{User} + \text{Item} + \text{Relation} \xrightarrow{\text{Embedding}} \text{Ranking}\]

下面介绍算法具体如何实现。

算法推导

经过对原始IMF的算法原理分析后,有两种可能的改进思路:

  1. 社交关系融入目标函数
  2. 社交关系融入Confidence,详细定义参考我的博客

方向1:社交关系融入目标函数

目标函数的修改如下

\[G(x_\star,y_\star) = \sum_{u,i} c_{ui} \left(p_{u,i} - \beta x_u^Ty_i- (1-\beta )\frac{\sum_{v \in n(u)} x_v^Ty_i s(x_u,x_v)}{\sum_{v \in n(u)} s(x_u,x_v)} \right) ^2 + \lambda\left(\sum_u \Vert x_u \Vert^2 + \sum_i \Vert y_i \Vert^2 \right) \qquad (1)\]

IMF算法的符号与这里保持一致。引入的新符号如下,

  • $n(u)$ 表示用户u的好友
  • $s(x_u, x_v)$ 表示用户u和v的关系权重
  • $\beta$ 表示用户偏好和好友偏好的权重,介于0-1之间

虽然公式(1)考虑的好友的关系,但是这个算法计算复杂度非常高,无法利用现有IMF的优化方法在线性时间内完成计算,所以无法支撑大规模工业级别计算,故放弃此方向。

方向2:社交关系融入Confidence

首先回忆IMF中Confidence的计算过程,

\[c_{ui} = 1 + \alpha r_{ui} \qquad (2)\] \[c_{ui} = 1 + \alpha \log(1 + \frac{r_{ui}}{\epsilon}) \qquad (3)\]

(2)或(3)均可,根据实际效果显示,(3)的离线效果往往较好。 $r_{ui}$ 是用于u和物品i的交互,如果将该值考虑关系,那么可以仍然利用现有IMF的实现,即可融合关系数据,如下

\[r^\prime_{ui} = r_{ui} + \delta \frac{\sum_{v \in n(u)} r_{vi} s(x_u,x_v)}{\sum_{v \in n(u)} s(x_u,x_v)} \qquad(4)\]

其中$\delta$是衰减系数,控制关系传递的confidence的显著程度。

$s(x_u, x_v)$最简单的方法是好友权重相同,即$s(x_u, x_v)=1$。但是,有些社交关系带权重,此时可以直接利用这些权重,即$s(x_u, x_v) = w_{uv}$。如果希望利用社交关系链本身的特征,并且关系链没有显示的权重,可以通过我们团队林博研发的Personalized PageRank算法计算出隐式的关系权重(该算法可以高效处理上百亿的关系链),即$s(x_u, x_v) = PPR(u,v)$。

此方法对原有IMF的计算框架无任何修改,保留了IMF的所有优点,仅需要在“特征”上将社交关系融如其中。笔者使用此方法分别进行了离线实验和线上验证,取得了不错的效果。

实验效果

离线和在线实验均是在一个实际推荐场景中进行,该场景是一个大型多人在线角色扮演游戏(MMORPG)中的商城推荐,推荐列表定期刷新。该场景关系链数据没有权重,所以使用等权重,对比算法是原始IMF,离线AUC平均相对提升$7.18\%$。离线数据显示改进后的算法明显优于原始算法,所以将离线算法推到线上验证,算法上线时添加了基于PPR的隐式关系链权重,以期望得到更好的效果,线上算法效果如下,

评估指标是平均曝光购买金额(曝光ARPU),笔者对绝对值做了脱敏处理,但是不影响算法效果对比。数据显示,无论是等权重社交关系,或是PPR计算的社交权重,融合了IMF后,均相比原始IMF有明显的提升。经过实践,此方法确实在此场景上有显著效果,但是该方法是否具有普适性,今后需要在更多场景下进行验证。

参考资料