多样性算法在58部落的实践与思考

指导阅读

在明确了“推荐系统的个体多样性优化”这一主题后，本文从整体架构上清晰地阐述了召回层、规则层和多样性层中的优化细节。在MMR和DPP算法中，既有原理也有实践。最后通过图表展示效果对比，根据自身业务特点进行有针对性的距离设计。

背景

在推荐系统中，除了相关性，多样性也是衡量系统好坏的重要指标之一。然而，多样性和相关性之间往往存在一些矛盾。从业务指标的角度，探讨了如何权衡多样性和相关性的思维方法，介绍了多样性算法的实用方案，最终通过多样性手段达到改善业务指标的目的。

1.多样性算法的意义和难点

在推荐系统中，准确率一直是衡量系统好坏的最重要指标，大部分工作都在研究如何提高准确率。然而，推荐结果的质量是由多个维度来衡量的。越来越多的研究表明，基于准确度的推荐并不能提高用户的体验和满意度，反而容易促进信息茧的出现。因此，如何平衡和优化准确性和多样性，从而提高业务的整体数据指标，成为了推荐系统的另一个优化方向。

在实践中，我们总结了多样性算法的几个难点:

1)模型的优化目标是模糊的。

众所周知，各种用户行为(点击、转化、停留、分享等。)可以作为优化精度的目标。我们可以清晰地收集用户行为作为模型的目标标签，从而设计和优化模型。因为多样性本身就是一个集合统计量，很难找到直接的用户行为作为模型优化的目标。

2)业务指标和多样性指标之间的冲突

业务关注指标(转换率、停留时间等。)和多样性指标不是简单的正或负。如果单纯为了提高多样性指数而做多样性，会导致最终结果与商业目标产生偏差，降低推荐质量。

综上所述，在58部落推荐系统的多样性实践中，我们排除了单纯用多样性指标作为评估算法的方法。结合部落的业务特点，我们设定的目标是:以多样性作为提升业务指标的手段，通过多个业务指标和多样性指标综合评估算法的效果，最终达到两个指标共同提升的目的，从而提升用户体验。

58部落多样性算法的实践

在分集算法的研究中，分集通常分为两种类型:

基于个人用户的多样性，旨在避免向单一用户推荐相似的商品，从而改善用户体验，增加用户满意度；

基于所有用户的多样性，旨在优化长尾商品的分发效果；

因为我们现阶段的主要目标是个人用户体验，所以选择基于个人用户的多样性作为实践方向。

1.推荐的系统架构图

推荐系统的在线层次结构图

为了确保推荐数据的多样性，我们在三个地方进行了优化:

1)召回层:从数据源提供多样化的候选集，通过提高粗糙候选池中主题、类别、作者的覆盖率，保证数据源的多样性；

2)规则层:在相关性损失很小的情况下，通过提高精细排序候选池中主题和类别的覆盖率，保证进入精细排序池的数据的多样性；

3)?多样性层:对数据进行统一和多样化处理，保证数据输出的多样化。

数据决定了效果的上限，算法只是逼近这个上限。在多样性层，尽可能只保证精细排序后的数据多样性。由于结果受精行候选池的数据多样性的影响，如果能在召回层的数据源中保持候选集的多样性会更好。

2.数据来源多样化

2.1召回层多样化的实现

回忆层架构图

在召回阶段，我们采用了多渠道召回。为了保证数据的多样性，通过增加一些不同的召回策略来丰富数据源，比如:

通过多样性算法，获取用户个性化、多样化的话题、类别和作者进行召回，保证召回兼顾多样性和相关性；

通过一些长尾、时间、惊喜回忆，增加数据的新颖性和多样性；

通过一些基于关系和属性的协同召回分支，提高了数据的多样性。

通过增加多样性和新颖性召回，粗候选池中数据的覆盖率提高了约120%，基于类别的覆盖率提高了约100%。

2.2实现规则层的多样化

规则层架构图

我们推荐的数据是各种异构的实体，所以在进入细行(规则层)之前，会对类型进行分桶处理。每种类型都要经历一个从粗排到细排的数据拦截阶段，主要拦截指标一般是粗排的相关分值。为了防止截断破坏召回层对数据源所做的多样性优化，我们先将这类粗排列的结果按类别分成桶，然后控制多样性。最后，调整各种类型的比例，补充数据，做一些必要的筛选。在相关性不大的情况下，提高细行数据的多样性。

由于规则层多样性算法是按类型分桶的，所以不受各种异构类型实体混合排列的影响，适用于各种多样性算法。

在规则层加入多样性算法的干预后，精细排序候选池中数据的覆盖率基于主题提高了80%左右，基于类别提高了70%左右。？

常规图层添加多样性后的online ctr和uvctr的变换效果如下图所示:

规则层算法的效果比较

从上图可以看出，在差异方面，各算法都不是很大，性能略胜一筹。总的来说，算法执行得稍微好一点。规则层主要是用多样性算法代替以前的启发式规则，从而自动化数据源的多样性。

3.基于重排序方法的多样化图层

对于算法参数调整，我们主要参考三个业务指标:

Pvctr表示pv点击率；Uvctr代表uv点击率；Avgpv代表人均观展次数。

对于应用多样性算法的场景，在规则层的单一类型中使用了常见的多样性算法，如binomal、EE、DPP、XQUAD、PM2、Bayes和MMR，但是常见的算法并不适合多样性层中的各种异构类型的实体，因为58个部落具有多样性和异构性，很难用单一的向量生成方法来度量稠密空间中的异构项，并且不同类型的实体的兴趣分布的重叠程度不是很高。

3.1分集架构图

多样性层架构图

限于篇幅、业务组合的重要性、时效性等原因，下面重点介绍MMR和DPP在工程实践中的应用。

3.2MMR？的原则

MMR原理的全称是MaximalMarginal Relevance，是一种减少冗余、保证相关性的贪婪排序算法。在推荐场景下，我们可以在保证推荐结果多样性的同时，向用户推荐相关产品。公式:

s是所选文档的有序集合，一般是相关排序的结果；

r代表下一个候选文档；

Di代表下一个候选文档；

Dj代表s中的文档；

Sim函数:是一个相似性度量函数，比如相似度；

表示候选文档和查询文档之间的相关性；

表示文档和现有文档之间的最大相似性；

？权重系数，调整推荐结果的相关性和多样性。

作为一种贪婪算法，它也是每次计算公式中的最大值，放入有序的结果集中，同时从候选集中删除选中的项，然后更新参数，然后在下一轮继续选择，直到结果集中的数据满足需要或者没有数据可供选择。

实现进程

Mmmr算法流程图

实验效果

MMR参数效果对比图

为了统一算法流程，我们对原论文中公式中的和进行了换位。为了保证在同一张图中比较几个指标，图中的和有一定程度的放大和缩小。从图中可以看出，多样性参数是逐渐调整的，逐渐降低，达到当时的最高点，因为越小，结果越趋于相关。并且人均观看次数稳步上升，说明随着多样性的增加，会吸引一部分人点击，他们会浏览更多的内容，在家时效果最好，在家时达到最高点。

？工程实现问题

在计算距离时，我们实现了当前文档与所选文档之间的平均距离，避免使用最大距离造成推荐结果中后续文档之间的高相似度。

文章间相似度函数的定义可以基于文中提到的相似度。但这要求候选列表之间必须有一个统一的项目向量，以确保该向量是任意对任意的。因为存在许多类型的推荐结果，并且它们是异构的，所以在这种情况下，相似性不是很好解释的。我们的做法是用一个自定义的距离结合业务，下面会详细介绍。

3.3 DPP的原则

行列式点过程的全称是定义在离散点集的幂集上的概率分布。是随机抽样的子集，对于任何一个，都有

公式中变量的含义:

y？行列式点过程随机抽样得到的随机子集；

是y的任意子集；

表示命中样本中所有元素的概率；

？k是实对称方阵，又称核矩阵，每个元素？可以认为是集合中第一个元素之间的相似度，与抽样概率成反比。可以看做是物品与用户的相关性，与抽样概率成正比。

Ka？是k的主主公式，阶是其中元素的个数。

下图可以形象地描述决定点过程:

决定点过程示意图

表示项目I和J同时被抽样的概率。从公式中可以看出，相似项越多，同时被抽样的概率越小。

该算法的思想是将重排序问题视为子集选择问题，目标是从原始数据集中选择高质量但多样化的子集，通过DPP保持高质量和多样性之间的平衡。DPP是一种高性能的概率模型，通过行列式简化了复杂的概率计算。DPP也可以理解为一个采样过程，两个元素被抽取为子集的概率与单个元素被抽取的概率以及两个元素之间的相似度有关。

DDP实施方案

？第一个是Google提出的基于窗口的重新排序方案。文中提到的核矩阵构造方案是:

Dij表示项目I和j之间的距离，它是自由变量。当a=1时，相当于标准的RBF核。当...的时候

矩阵的非对角线被缩小，这基本上对应于使所有项目多样化。当a & gt1，矩阵的对角线按比例放大，起到了让所有项目更相似的反效果。

随着集合的增长，小集合的概率增大，大集合的概率减小。由于一个& gt在1，L可能是非半正定的。为了保证核矩阵每次都是半正定的，本文对核矩阵进行映射，计算L的特征分解，用0代替任意负特征值。

同时提出了一种基于深度Gram核矩阵的深度学习模型优化方法，降低网格搜索参数的复杂度。

第二种是宾夕法尼亚大学提供的方案，是DDP最大后验推断的一般解决方案，但是每得到一项都要通过计算来重构核矩阵，延迟不容乐观。

三是部落虎视频提出的最大后验推断解决方案。针对传统地图时间复杂度高的问题，提出了一种改进的快速求解的贪婪算法:

靠施工？

映射的子模函数转化为子模函数最大化问题。并采用贪婪算法解决子模函数最大化带来的NP难问题。

每次选择一个乘积并添加到结果集Yg，Yg被初始化为一个空集，直到满足条件，该乘积需要满足以下等式:

由于计算行列式的复杂度很高，本文将其分解为Cholesky，初始化为空，通过一些列变换得到:

作者还提出了增量更新，并通过推导得到最终的增量更新公式(具体推导过程参考原论文):

我们实现了三种方案，第二种方案延迟较大，无法应用于在线。我们在第一种方案中实现的简单模式是直接计算行列式，延时比第三种方案大。方案3可以不用核矩阵修复，排序结果会小于预期的数据量。在实际应用中，结合数据量和效率的需求，我们最终选择了hulu提出的第三种实现方案。

DPP实施流程

DPP算法流程图

实验效果

DPP参数变化对应的效果图

为了保证几个指标在同一张图中相互比较，pvctr和avgpv都有一定程度的放大缩小。从上图可以看出，逐渐调整分集参数，pvctr越来越大，在0.7左右时达到最高。Uvtr和人均观看次数稳步上升，说明随着多样性的增加，不点击的人会被吸引去点击，人们会浏览更多的内容。而且Uvtr在0.7达到峰值，0.7效果最好。DDP每条曲线的最后一个参数值都很低，因为在0.999，构造核矩阵时A的值变得很大。指数变化后，很多核矩阵都有最大值，矩阵不满足秩。只返回少量数据，属于异常情况，各项指标都在下降，这也是算法调试过程中要避免的一点。

工程实现问题

在实现上，我们主要使用EJML，一个高效的开源Java矩阵运算库，是目前尝试中相对高效的库。

在工程实现中，主要参考文中提到的使用。

exp(αr_u)

代替Ru，通过调整分集和相关性，

α=θ/((2(1-θ)) )

文中提到的半正定性保证是可以修正的。

S_ij=(1+？f_i，f_j？)/2

在我们的应用中，影响并不大，主要是因为我们的相似度矩阵是用户自定义的。

DPP的主要优化点是效率。我们采用虎虎视频的优化方案，不遍历行列式，整个100项的重排序过程平均延迟只有4 ms。

核心矩阵的构建，因为我们需要一个用户自定义的距离，更具可解释性，能与业务紧密结合，所以相似度矩阵和核心矩阵也是用户自定义的。

按窗口分批排序整个列表。根据子模函数的性质，小数据集比大数据集更具排他性，窗口效果更好。

针对DPP参数调整，首先固定用户自定义的距离参数寻找合适的，然后循环固定和调整距离参数，通过网格搜索优化参数。

？由于核矩阵对秩不满意，返回的数据量可能小于预期的数据量，可以正常使用，对业务没有太大影响。如果对返回的数据量有严格的要求，我们需要考虑修改核矩阵。可以参考google提出的核矩阵修改方法，同时对延迟会有一点影响，延迟大概会翻倍。

3.4差异层算法效果对比图

原始算法、MMR和DPP的比较

多样性层主要考虑稳定性和时效性。我们的主要流量是在两个隐式分集算法中，MMR和DDP，而我们的原始算法是由启发式规则控制的。通过对最优参数下的算法进行比较，发现DDP的整体效果优于MMR，与原算法相比有了很大的提高。下表显示了两种算法与原始算法相比变化。

指示器\算法寄存器

数字数据处理器

pvctr+3.4%+5.8%

vvctr

+5.4%+7.9%

avgpv

+4.2%+6.0%

？各算法业务指标变化图

自定义距离

为了更好地解释和更紧密地整合业务，我们使用用户定义的距离。用户定义距离的好处如下:

？可解释性强，自定义距离偏向于人能理解的目的，使距离更具可解释性；

并且业务结合更加紧密，自定义距离利用业务相关信息紧密结合业务；

它是通用的，可以在不同的异构实体之间使用，这是在其他距离上无法做到的。

我们练习的自定义距离如下:

1.贾卡德距离/汉明距离

这个自定义距离是通过Hamming-Jakad距离平铺近似法实现的。

自定义距离-贾卡德/汉明距离

就是结合服务构造汉明向量，先计算汉明距离，再通过雅可比相似度归一化。

2.？自定义距离-树模型距离

用户自定义树模型的距离通过树状分层衰减和自顶向下的业务组合实现。

自定义距离树模型

树的叶节点是距离的分散值。

我们尝试了以上三种自定义距离的方法，从可解释性、业务组合和在线实验效果来看，树模型是目前最合适的一种。

总结与展望

评价推荐系统的多样性有很多方面。本文不仅使用多样性指数来衡量算法的好坏，而且基于业务指标综合考虑多样性结果，对多样性和业务关注指标进行权衡，最终通过多样性算法实现改善业务指标的目的。在工程实现方面，本文介绍了该算法试图从召回、规则和重排序等方面实现多样性，特别是在最重要的重排序阶段。基于MMR和DDP算法，优化计算效率，根据业务数据特点定制距离，满足从多维度度量项目相似度的业务需求。

目前，就文献中的效果而言，学习多样性算法比非学习算法更有效，且显性比隐性更有效。但是多品类异构实体之间的关系就没有那么直观了，以后我们会结合业务特点进行尝试。另外，基于强化学习的多样性算法也是多样性研究的一个方向，目前我们又进行了尝试。

参考资料:

1.C.-N .齐格勒、S.M .麦克尼、J.A .康斯坦和g罗森。通过主题多样化改进推荐列表。WWW2005

2.？j .卡波内尔和j .戈尔茨坦。使用基于多样性的重排序方法对文档进行重新排序并生成摘要。SIGIR 1998

3.？詹妮弗·吉伦沃特亚历克斯·库勒萨·本·塔斯卡。确定点过程的近似最佳映射推断。？奶头？2012

4.马克·威廉，阿吉特·库玛尔·拉曼纳森，亚历山大·博诺莫，萨加尔·贾恩，艾德·h·齐，詹妮弗·吉伦沃特。YouTube上关于决定性点过程的实用多样性推荐。CIKM'18 2018

5.？陈拉明，，周汉宁。提高推荐多样性的决定性点过程的快速贪婪映射推理。NeurIPS 2018

6.CSDN博主曹永盛。行列式顶点过程介绍。csdn，2019。

关于作者:

刘发帅，58赶集集团，高级算法工程师。

周建斌，58赶集集团，算法架构师，技术委员会委员。