Personalized DPP介绍

Reading time ~1 minute

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转化是数百万美金,因此这样的不大提升每年能带来额外的美金收入。

参考

Meta推荐系统-scaling laws介绍

meta在《Understanding Scaling Laws for Recommendation Models》讨论了推荐系统中的scaling law问题。# 摘要**规模(scale)**一直是提高机器学习性能的主要驱动力,理解**规模法则(scaling law...… Continue reading

kuaishou CQE时长预估介绍

Published on August 01, 2024

finalMLP介绍

Published on July 27, 2024