问题背景

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

  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有明显的提升。经过实践，此方法确实在此场景上有显著效果，但是该方法是否具有普适性，今后需要在更多场景下进行验证。

参考资料