huawei在《Personalized Re-ranking for Improving Diversity in Live Recommender Systems》提出了personalized DPP方法。
摘要
2.reranking模型
2.1 DPP-based re-ranking
如【13】，DPP-based model要比MMR-based model要更有效且高效。因此，我们选择研究如何在我们的推荐系统中使用DPP-based reranking model。在本节，我们会讲述DPP-based reranking model，并讨论它的局限性，这激发我们在一下节中使用personalized DPP-based reranking模型。
我们将[13, 14, 20]的一些关键结果进行归纳，让读者更好地理解该模型。在一个关于items的集合（\(M=1,2,\cdots, \mid M \mid\)）上的一个点过程（point process）P，是一个在M的幂集（powerset）的概率分布。也就是说，\(\forall Y \subseteq M\)，P会分配一个概率分布\(P(Y)\)，使得\(\sum_{Y \subseteq M} P(Y)=1\)。如【20】中所述，我们的目标是：从整个item set M中选择一个合适的relevant和diverse的k个subset，使得集合满足\(max_{Y:\mid Y \mid = k, Y \subseteq M} P(Y)\)。再者，P可以通过一个\(M \times M\)的半正定kernal matrix L进行紧密参数化（compactly parameterzied），比如：\(P(Y) \propto det(L_Y)\)，其中\(det(L)\)是矩阵L的行列式（determinants），\(L_Y\)是一个L投影到只有Y的行和列上的子矩阵。因此，发现满足\(max_{Y:\mid Y \mid = k, Y \subseteq M} P(Y)\)的集合等价于发现这样的集合：\(max_{Y:\mid Y \mid = k, Y \subseteq M} det(L_Y)\)。
该半正定kernal matrix L定义如下：
\[L_{ii} = q_i^2 \\ L_{ij} = \alpha q_i q_j S_{ij}\]…(1) (2)
其中：
- \(q_i ( i \in [1, \mid M \mid ])\)表示从ranking function生成的item i的relevance score
- S表示一个关于items间的user-defined 相似矩阵，
- \(\alpha\)是一个关于对relevance 和 diversity间进行tradeoff的超参数
如之前所述，我们需要从整个item set M中选择一个items集合Y，使得：
\[\underset{Y:\mid Y \mid = k, Y \subseteq M}{max} det(L_Y)\]这是一个NP-hard问题【20】，具有复杂度\(O(C_{\mid M \mid}^{\mid Y \mid})\)时间来发现最优集合。为了使得DPP-based reranking model可以应用到工业界推荐系统中，我们选择使用一个高效&有效的近似算法，Fast Greedy Map Inference【21】，来在一个可接受的时延中执行reranking。这样的一个近似算法可以解决组合优化问题，时间复杂度只有\(O(\mid Y \mid^2 \mid M \mid)\)。尽管在【21】中没有提供理论上更低边界，在线A/B test测试验证了它的优越性。
算法1
为了更正式地表示它，我们将DPP-based reranking model以算法1方式进行归纳。每个round，FastGreedyMap会贪婪地选择一个item（如算法1中的第3行），也就是说，选中的item会最大程度提升updated submatrix的行列式。正式地，它会选择这样的item：
\[y = argmax_{i \in M} (log det(L_{Y \cup \lbrace i \rbrace}) - log det(L_Y))\]2.2 Personalized DPP
在DPP中，\(\alpha\)是一个可调的超参数，用来对relevance和diversity进行trade-off平衡。DPP假设：每个人都有相同的diversity degree的倾向分（propensity），由于当构建kernel matrix L时会应用相同的\(\alpha\)值，当执行reranking时对所有用户是共享的。然而，如第1节所讨论，不同的个人具有对多样性不同的倾向（propensity），因此DPP需要进行个性化。
在DPP中实现个性化的一种简单方法是，为每个user u设置一个唯一的超参数\(\alpha_u\)。不幸的是，该方法不可行，因为超参数的个性\(\alpha_u\)太大，不可能针对个人去调参。在本paper中，提出了一咱有效的方法来达到personalized DPP（简称：pDPP）。我们会将user-wise超参数\(\alpha_u\)进行factorize成两个因子：
\[\alpha_u = f_u \times \alpha_0\]…(4)
其中:
- \(\alpha_0\)：是一个可调共享的超参数，用来控制在所有用户上的relevance和diversity（在DPP中，与\(\alpha\)具有相同的功能)
- \(f_u\)：是一个user-wise factor，用来表示user u的多样性倾向（diversity propensity）
接着，我们详细说明定义\(f_u\)的意图。如第1节所解释，用户的多样性倾向（diversity propensity）可能受他们的历史行为的影响。作为一种可能的选择，我们可以使用该用户交互过的不同genres分布上的香农熵（shannon entropy），如下：
\[H(u) = - \sum\limits_{g \in G} P(g | u) log(P(g | u))\]…(5)
其中：
- \(P(g \mid u)\)表示user u对某类别g感兴趣的概率
- user u交互过的items之一是genre g
如【18】所示，一个user u具有更高的H(u)，表明该用户具有更高的diversity propensity，反之亦然。由于该直觉，我们将\(f_u\)定义为 normalized H(u)。正式的，我们提出使用一个parameterized min-max normalization，如下：
\[f_u = \frac{H(u) - H_{min} + l}{H_{max} - H_{min} + l} \ (l \geq 0)\]…(6)
其中：
- \(H_{max} = max_u H(u)\)表示在所有users上的最大熵值，
- \(H_{min}\)表示最小值
超参数l控制着\(f_u\)的个性化程度。如图3所示，一个更大的l值表示在所有用户间具有更小的个性化\(f_u\)值，例如：\(l \rightarrow \infty\)，它可以看成是\(f_u = 1\)，此时pDPP就降级为DPP。实际上，我们选择使用两个特例：当\(l=0\)时，\(f_u\)是标准的min-max normalized H(u); 其中当\(l = H_{min}\)时，\(f_u\)是max normalized H(u)。
图3
为了归一化，pDPP是DPP的一个个性化版本，无需引入额外的超参数进行调参。尽管公式很简单，第4节的实验结果表明它的有效性。
3.系统实现
3.1 框架修改
使用pDPP re-ranking 模型的推荐系统总览如图4所示。我们首先展示不考虑reranking model的模块（绿色框），接着展示了如何在pDPP中采用这些modules。
图4
一个推荐系统的架构包含了三个模块：
- (1) 离线训练模块（offline training module）：会处理user-item交互数据，抽取features（包括：user features、item features、context features），训练模型，以及上传模型。
- (2) 在线预测模块（online prediction module）会接收用户请求并返回一个关于items的列表。通常存在两步，称为：retrieval和ranking。由于存在数百万的items，有一个正常时延内对所有item进行排序很困难。retrieval step会返回一个符合用衣在该context下的较短的list。在减小候选size后，raking step会使用offline trained model为每个items计算relevance scores。
- (3) 近期更新模块（Nearline updating module）：它会更新user features、item features以及使用真实交互数据的离线训练模型。
我们提出的pDPP reranking model可以很轻易地集成到以上的架构中。接着，我们会描述如何采用三个模块来部分该reranking model。
- 在离线训练模块中，有个initializer会为每个user u计算\(\alpha_u\)值，并上传这样的值到online Indexer中
- 在在线预估模块中，会通过由任意ranking function计算得到的候选items的相关得分（relevance scores）以及从在线Indexer中的个性化\(\alpha_u\)，pDPP reranking model会综合考虑relevance和diversity来生成最终的推荐列表。
- 在近线更新模块中，个性化\(\alpha_u\)值是基于实时user-item交互数据进行更新的，更新后的\(\alpha_u\)值会被发送到online Indexer上。
图4
开发accurate ranking function是一个必要的研究主题。可以看到，我们的pDPP reranking model与任意高级的ranking function是兼容的，无需修改ranking function。
3.2 实践要点
为了帮助更好理解和实现我们的模型，我们归纳了一些实践要点：
-
在【21】中，kernel matrix L会被预计算并存储在内存中，如算法1所示。然而，这样的方法不能在真实推荐系统中执行，因为以下的原因：第一，relevance score \(q_i\)会被一个ranking function计算得到，会实时更新并且是个性化的。这种工业界方式的ranking function会对不同用户对相同item做出不同的relevance，另外，一个user-item pair的relevance score会在几秒后更新，因为user feature会发生变化。第二：我们的pDPP模型当构建L时具有一个个性化因子\(f_u\)，因此不同的users会具有不同的L。如果我们需要预计算并存储它们，我们需要花费大量时间和存储资源来处理这样的L。由于这两点，当该user触发请求推荐时，我们会为一个user即时（on-the-fly）计算个性化kernel matrix L。
-
在我们的实验中，我们尝试了两种不同方法来构建相似的矩阵S：一个会使用item features，另一个会使用user-item交互信息。使用user-item交互的该方法要比其它方法稍微更差些。原因是，user-item交叉通常非常稀疏，这使得：基于这些信息表示的item不是非常可靠。不管使用哪种方法，我们发现，当\(S_{ij}\)在[0, 1]间效果最好。
-
冷启问题：在我们的系统中，如果u是一个新用户，我们设置\(\alpha_u=\alpha_0\)。另外，只有少量交互的用户也会被我们的系统认为是新用户。我们会做出这样的决策：由于\(\alpha_0\)是一个对于exploration来说相对安全的值，可以较好地对relevance和diversity进行trade-off。
4.实验评估
4.1
4.2 在线评估
在离线评估中，展示pDPP的良好accuracy与diversity的tradeoff，我们部署pDPP到真实线上系统中来验定它的有效性。
4.2.1 实验设定
对于在线评估，我们会进行A/B test。我们会对比三种不同的模型族：base、DPP、pDPP。我们将所有用户随机分成成百上千个bins，每个bin包含了超过10w用户。一个bin的用户会通过三者之一进行服务。在我们的真实推荐系统中，DPP的超参数\(\alpha\)以及\(pDPP\)的\(\alpha_0\)设置为0.6，因为当\(\alpha=6\)时avg(P@5, ILD@5)的效果是最好的。
4.2.2 评估指标
为了比较这些方法的优点，我们在两个metrics上（accuracy和diversity）上进行评估。第一个accuracy指标通过下载率（download ratio）来评估，定义如下：
\[DR = \frac{total \ number \ of \ downloads}{total \ number \ of \ impressions}\]除此之外，我们会评估users的engagement。更特别的，我们会研究每个用户的平均下载数目(AD)，如下：
\[AD = \frac{total \ number \ of \ downloads}{total \ number \ of \ users}\]除了这两个accuracy指标，我们采用ILD来评估diversity，它在离线评估中也相同使用。
表3
4.2.3 在线效果
A/B在线测试如表3所示。考虑商业机密，我们只会在DR、AR和IDL上表示DPP、pDPP和Base模型的相对提升。
我们可以观察到，DPP和pDPP会比Base要在这三个评估指标上好很多。它建议我们提升diversity来增强推荐效果。在DPP和pDPP之间，我们观察到，pDPP要优于DPP，这表明：对diversity的个性化倾向比相同的倾向setting要更合适。我们观察到：pDPP要比DPP的线上提升，不会有离线评估那么大。通过详细分析，我们发现：大约35%的用户在它们的行为中只有一个下载记录，因此它很难定义它们的多样性倾向，这是未获得大提升的主要原因。然而，每天我们的APP store转化是数百万美金，因此这样的不大提升每年能带来额外的美金收入。