JADIDINEJAD在《The Simpson’s Paradox in the Offline Evaluation of Recommendation Systems》中提出推荐系统中的Simpson’s Paradox:

1.介绍

推荐系统通常会以online(A/B testing或interleaving)或offline方式进行评估。然而,由于online evaluation[6,14]部署研究系统的难度,推荐系统的离线评估仍然是大范围使用的evaluation方式。实际上,很难以离线方式通过使用历史用户交互日志可靠地评估一个推荐模型的效果【7,16,43】。该问题是因为存在混淆因子(confounders),例如:那些可以影响items的曝光(exposure)以及结果(outcomes)(比如:ratings)的变量。在当一个平台尝试建模用户行为时,如果没有解释在曝光的推荐items的选择偏差(selection bias),这时会出现confounding问题,从而导致不可预料的结果。在这种情况下,很难区别用户交互是来自于用户的真实偏好、还是受部署推荐系统(deployed recommender system)的影响

通常,推荐系统的离线评估会具有两个阶段:

  • 1) 收集来自一个deployed system的用户反馈集合
  • 2) 使用这样的feedback来经验性评估和比较不同的推荐模型

第一阶段可以服从不同类型的confounders,即可以是由用户关于item的选择行为来初始化,或者通过受deployed推荐系统的动作影响来初始化。例如,除了其它交互机制(比如:搜索)之外,用户更可能会与被曝光的items进行交互。在这种方式下,在一个新推荐模型的离线评估中使用历史交互,而这样的交互从deployed推荐系统中获取得到,形成一个closed loop feedback,例如:deployed recommender system存在对收集到的feedback的具有一个直接影响,它可以被用来进行对其它推荐模型的离线评估。因而,新的推荐模型会根据它趋向于模拟由deployed model收集到的交互有多像来进行评估,而非有多满足用户的真实偏好。另一方面,在一个open loop(随机化)场景中,deployed model是一个随机推荐模型,例如:为users曝光随机的items。因此,在deployed model与新的推荐model间的feedback loop会打破,deployed model不会对收集到的feedback dataset具有影响,相应的,它对于在基于收集到的feedback dataset上对任意新模型的离线评估都没有影响。然而,为users曝光随机items是天然不实际的,用户体验会降级。因此,基于closed loop feedback对推荐系统进行训练和评估会是一个严重问题

Simpson’s paradox是统计学中的一个现象,当多个不同分组的观察数据中出现的一个显著趋势,会在这些分组组合在一起时消失或者逆转【29】。在推荐场景中,当曝光(例如:推荐items)和结果(例如:用户的隐式和显式反馈)相关联时,并且曝光和结果会受一个第三方变量强烈影响时,会发生Simpson’s paradox。在统计学上,如果观察到的feedback是Simpson’s paradox的一个产物,根据confounding variable对feedback进行分层,可以消除悖论。我们会讨论:在推荐系统的情况下,该confounding variable是交互数据被收集的deployed model(或系统),a.k.a:closed loop feedback【17】。在本paper中,我们的核心目标是,对于closed loop feedback在推荐系统离线评估上提供一个in-depth研究,并提供了一个健壮的解来解决该问题。特别的,我们会讨论:从一个deployed model收集到的feedback datasets会偏向于deployed model的特性,并导致证实Simpson’s paradox的结论。我们通过研究在推荐系统离线评估上的confounding variable(例如:deployed model’s的特性),可以观察到显著趋势;当从经典离线setting中上报observations时,该趋势接着会消失或逆转。另外,我们提出了一种新的评估方法,它可以解决Simpson’s paradox,以便产生一种更合理的推荐系统离线评估方法。

为了更好地理解该问题的微妙之处,考虑一个deployed推荐模型,它会提升一个指定分组的items(例如:流行的items)——对比起只有少量交互的长尾items,存在一些少量的头部items,它们会被广泛曝光给用户并获得大量交互。当我们基于从前面deployed model收集到的feedback来评估一个新的推荐模型时,如果没有解释不同的items曝光的有多频繁,评估过程会被deployed model的特性所混淆,例如:任意模型的效果会具有这样一个趋势,展示与已经存在的deployed model相似的属性,这很可能会引起过估计(over-estimated)。在这种情况下,我们可能会选择部署一个匹配已deployed model的特性的新模型,从实际用户角度看,它会比另一个模型更低效。在本paper中,我们通过研究该问题在标准离线评估中做出结论的结果,并提出一种新的方法来解决该问题。特别的,本paper的贡献有两块:

  • 我们提出了一种in-depth分析
  • 为了解决该问题,提出了一个新的propensity-based stratified evaluation方法

2.相关工作

我们的工作主要受三块相关工作的启发:

  • 在l2r中解决bias(2.1节)
  • 算法混淆(algorithmic confounding)或closed loop feedback(2.2节)
  • 在counterfactual learning和evaluation中的工作(2.3)

3.离线评估法

本节中,我们会将当前offline evaluation方法进行总结,称为标准holdout evaluation和counterfactual evaluation。

3.1 Holdout Evaluation

3.2 Counterfactual Evaluation

4.介绍

辛普森悖论(Simpson’s paradox)是统计学中的一种观察现象:在观察数据集的许多不同groups中都出现的一个显著趋势,当将这些groups组合在一起时会消失甚至反转。该topic在许多文献上被广泛讨论。在该现象中会出现一个明显的悖论,当聚合数据时会支持这么一个结论:它与在数据聚合前的相同的分层数据的结论相反。当两个变量间的关系被研究时,如果这些变量会被一个协变量(confounding variable)所强烈影响时,就会发生辛普森悖论。当该数据根据混杂变量(confounding variable)进行分层时,该悖论会展示出相悖的结论。在这种情况下,使用一个显著性检验(significance test)可以识别出在一个指定层做出的错误结论;然而,如第7节所示,显著性检验不可能识别出这样的统计趋势(trends)。在推荐系统的评估场景,会在所有用户上进行testing,这里讨论的悖论通常会涉及到user-item feedback生成过程。在另一方面,当因果关系(causal relations)在统计建模中被合理解决时,辛普森悖论可被解决。

在本节中,为了演示辛普森悖论,我们会从一个paper[8]中呈现一个真实示例,它会对比肾结石(kidney stone disease)的两种治疗方法(treatments)的成功率。这里的目标是:基于观察找出哪个treatment更高效。【8】会随机抽样350个病人,它们会接受每个治疗,并上报如表1所示的成功率。一个合理的结论是:treatment B要比treatment A更高效(83% vs. 78%的康复率)。另一方面,悖论是,当考虑上结石大小时,比如:treatment A对于小size(93% vs. 87%),大size(73% vs. 69%)两者都要有效,但最终的成功率会反转。[8]会讨论treatment (A vs. B) 以及结果(成功 vs. 失败)会与一个第三个混杂变量(confounding variable:这里的结石大小)有关。

图片名称

表1 a) 肾结石示例。每个条目表示:恢复数/总病人数,成功率见括号 b) 推荐系统中离线评估的辛普森悖论。每个条目表示了受检模型在相应分层上的效果。*表示对比其它模型的一个显著差异(paired t-test, p<0.05)

假设 1: 医生趋向于对不严重病例(例如:小结石)选择treatment B,对于更严重病例(例如:大结石)使用treatment A进行治疗

表1验证了以上的假设,例如:大多数接受treatment A的病人都是大结石病例(group 3中350个随机病人中有263个),而大多数接受treatment B的病人都是小结石病例(Group 2的350中的270)。因此,当从接受A或B治疗的病人中被随机挑选样本时,抽样过程并不纯随机,例如:样本会倾向于:严重病例进行treatment A进行measuring,而轻症病例进行treatment B进行measuring。这就是因果分析中著名的现象:辛普森悖论。

表1b展示了在推荐系统的离线评估中的辛普森悖论示例。我们对两个推荐模型的有效性进行评估,如表1b中的A、B模型。两个模型会在相同的dataset上使用相同的evaluation metric进行评估。根据一个paired t-test,在检查的数据集上的标准离线评估表明:模型A要明显好于模型B。然而,将待检测数据集划分成两个层(Q1和Q2)表明:模型B对于待测数据集的99%(Q1)要更好,而模型A在1%(Q2)上面要更好。当Q1和Q2进行聚合时,模型B在99%待测数据集上的的统计优势会消失。在以下部分,我们会呈现:辛普森悖论是如何影响推荐系统的离线评估的,并讨论这样的悖论的原因,以及提出一个新的评估方法来解决它。

5.基于倾向的分层评估(PROPENSITY-BASED STRATIFIED EVALUATION)

当为一个推荐系统的离线评估创建一个数据集时,用户反馈不仅会用户与来自deployed recommendation system推出的items交互上被收集到到,也会通过其它形式(比如:当浏览item的目录时发生的交互、或者点了sponsored items的链接)进行收集得到。对于区分用户的不同反馈源来说并不简单,因为没有公共数据集提供这样的数据来确定用户反馈的source。因此,在本paper中,我们的研究主要关注于用户反馈的主源,称为deployed system。为了演示在推荐系统中的辛普森悖论,我们需要一个因果假设,它与第4节中的假设1相似。

图片名称

图1 推荐系统中的Closed loop feedback

图1a展示了一个典型推荐系统的信息流,其中用户反馈会通过deployed system进行收集。

  • 部署好的推荐系统组件(通过RecSys表示)会为target user(例如:通过推荐items的一个ranked list)过滤出items进行曝光(exposure: e)
  • 另一方面,用户在items上记录的偏好(例如:ratings或clicks)(用r表示)会被作为交互数据来训练 或 评估推荐模型的下一次生成(next-generation)。

因而,由于用户点击是从RecSys曝光的items获得的,模型本身会影响数据的生成,而它们则会被用于训练和评估。图1a中的系统是一个动态系统,其中,系统进行简单联想推理(associative reasoning )的原因是很难的,因为每个组件会互相影响。图1b表明了在这样一个闭合循环反馈场景下的因果关系图。实线表示了在原因和效果间一个explicit/observed关系,而虚线表示了一个implicit/unobserved关系。如上所示,在推荐系统的case中,主要的混合变量是,来自交互数据的deployed model会被收集。我们的目标是,基于来自deployed model收集到的封闭循环反馈(r))评估一个推荐模型(Y)的效果会影响主干扰因子(main confounder),例如:deployed model的特性。在该情况下,很难区分: 来源于用户真实偏好影响的的用户交互,或者受deployed recommendation model影响的用户交互。因此,在该场景下,用户反馈通常会通过deployed system进行收集,我们会假定,基于闭循环反馈数据集的推荐模型离线评估,会受以下deployed recommendation model的强烈影响:

假设2: 闭环循环反馈(closed loop feedback)会从一个deployed recommendation model来收集到,并倾向于deployed model的特性(characteristics)(例如:曝光items)deployed model的该特性会在推荐模型的离线评估中作为一个混淆因子(confounding factor)。

deployed recommendation model的核心问题是:尝试建模潜在的用户偏好,在没有解释算法混淆的情况下,这使得它很难对用户行为(或者使用用户数据)做出断言。另一方面,如果图1a中的RecSys组件是一个random模型,那么在User和RecSys组件间的连接会被移除,RecSys组件会在收集到的feedback dataset上没有影响,这种情况 称为“开环循环反馈(open loop feedback)”,对比起在collection中的任意其它item,没有items会接收到或多或少的期望曝光。

如图1b所示,如果deployed model的特性(e)可以被标识和评估,离线评估(Y)会与confounder独立。因此,为了验证在推荐系统中(假设2)closed loop feedback的影响,我们必须量化deployed model的特性。结尾处,根据5,47,我们会如下定义propensity score:

定义5.1 propensity score (p_{u,i})是deployed model(如图1a中的RecSys描述)对于expose item (i in I)的曝光给user (u in U)的趋势

propensity (p_{u,i})是在一个闭环反馈场景下,deployed model将item i曝光给user u的概率。该值会对来自一个无偏开环曝光(unbiased open loop exposure)场景的系统偏差(deviation)进行量化,其中:随机items会被曝光给该用户,deployed model对收集到的feedback没有影响。propensity score (p_{u,i})允许我们基于观察到的闭环feedback来设计并分析推荐模型的离线评估,因此它会模拟一些开环场景的特殊特性。

分层(Stratification)是用来标识和估计因果效应的知名方法,会在每个层调查因果效应之前,首先标识出潜在层(underlying strata)。总意图是:在confounding variable上进行分层,并研究在每个层上的潜在结果。因此,衡量不考虑confounding variable的潜在结果是可能的。在这种情况下,在confounding variable上的边缘化(marginalisation)可以作为一个组合估计(combined estimate)被使用。如前所述,在推荐系统中的假设condounding variable是deployed model的特征(假设2)。定义5.1会将该变量量化成倾向(propensities)。在这种情况下,在propensity scores上的分层会允许我们分析deployed model特性在推荐模型的离线评估上的该效应。

出于简洁性,假设我们具有一个单一的categorical confounding variable X。如果我们基于X的可能值将观察到的结果进行分层,那么潜在结果(Y)的期望值如下所示:

[E(Y) = sumlimits_x E(Y | X=x) P(X=x)]

…(4)

其中:

  • (E(Y mid X = x))是在给定分层x下对于observed结果的条件期望,
  • (P(X=x))是x的边缘分布。

例如,在肾结石的示例中,condounding variable是结石大小,基于它进行分层((X = lbrace small, large rbrace)),潜在结果是treatment效果。我们可以基于等式(4)计算每个treatment的期望值。例如:treatment A的期望值可以按如下方式计算:

[E(A) = E(A | X = small) P(X=small) + E(A | X = large) P(X = large)]

…(5)

例如:基于表1a和等式(5)中的数字,treatment A的期望值(resp. B)分别计算为:0.832和0.782,

计算:

  • P(X=small)=(87+270)/(87+270+263+80)=0.51,
  • P(X=large)=(263+80)/(87+270+263+80)=0.49
  • E(A) = 0.93 x 0.51 + 0.49 x 0.73 = 0.832
  • E(B) = 0.87 x 0.51 + 0.69 x 0.49 = 0.782

E(A) > E(B),它可以更好地估计treatments的实验效果。

相似的,对于表1b的推荐示例,模型A和模型B的期望值分别被计算为:0.343和0.351(计算所需数据参考第7节),计算如下:

  • E(A) = 0.339 * 0.99 + 0.695 * 0.01 = 0.343
  • E(B) = 0.350 * 0.99 + 0.418 * 0.01 = 0.351

从而得到E(B) > E(A)。

如上所示,在推荐系统中,主要的假设混淆变量是deployed model(假设2)。该变量可以量化成propensity scores(定义5.1)。Propensity是一个连续变量。在本paper中,我们会通过将propensity scores进行排序和分片成将它转换成一个categorical variable,然后转成一个预定义好数目的分层,例如:表1b中的Q1和Q2分层。在表1a和表1b的两个case,都基于假设混淆变量并使用等式(4)对等验证分层进行边缘化,会解决Simpson’s paradox。例如:在表1b中,模型B会被认为更好的model,因为它对于99%的user-item feedback在效果上要好。这个重要的趋势会被提出的分层评估进行捕获,而在标准离线评估中,当将Q1和Q2分层聚合在一起时,结论会完全逆转。在下节中,我们会研究simpson paradox的效应,以及提出的propensity-based分层评估的好处。特别的,我们研究了以下问题:

研究问题1:在closed loop feedback场景下,推荐系统的离线评估有多大程度是受deployed model特性所影响的

然而,我们的目标是评估deployed model特性在推荐模型离线评估中的confounding effect,如图1b所示。就这一点而言,相似的原理图示例如第4节所示,我们对于将基于deployed model的特性的observed closed-loop feedback进行分层这一点比较感兴趣。这样的分层分析使得我们可以去评估:在推荐系统的标准离线评估中辛普森悖论的存在。从而,我们会研究许多不同推荐模型的相关关系的显著趋势,其中:在大多数层上观察到的一个趋势,在标准离线评估中会消失或者逆转。

研究问题2:当进行一个可比离线评估时,propensity-based stratified evaluation是否可以帮助我们更好地估计实际的模型效果

在上述研究问题中,我们的目标是:评估在推荐模型的离线评估中,提出的提出的propensity-based stratified evaluation是否有效。如等式(4)所示,我们可以利用在confounding variable分布上的边缘化(marginalisation)作为潜在结果的一个组合估计。在该研究问题上,我们会评估:该估计是如何与open loop(randomised) evaluation相关的,其中deployed model是一个随机推荐模型(例如:random items会被曝光给该user)。特别的,给定一个特别的评估方法(open loop、closed loop等),我们可以去measure基于标准的rank-based评估指标(nDCG)多种推荐模型的效果,并记录这些模型的所用metrics的相对排序。我们接着研究在examined models的相对排序间的相关性,并对比从一个open loop(随机化)设定下获得的rankings,以及使用propensity-based evaluation这两者的评估。我们会利用适当的显著性检测,如第6节所述,来决定:在对比标准的离线holdout evaluation时,由d propensity-based stratified evaluation评估的模型效果要比open loop(随机) evaluation更好。

6.实验设定

下面,我们会通过实验来解决两个前面的研究问题。图2表示了实验的总结构。每个评估方法(X, Y和Z)会会基于它们的相对表现对多个检查的推荐模型进行排序。我们会使用Kendall’s (tau) rank相关系数来对受检模型在每个评估方法上(Y or Z)的相对顺序间的联系,对比ground truth进行measure,例如:open loop(randomiszed) evaluation(X)。这样的相关值会在图2中被描述成(tau_{XY})和(tau_{XZ})。另外,我们会使用Steiger’s方法来测试在两个评估方法间的差异显著性,例如:baseline evaluation method(Y)以及提出的evaluation method(Z)。我们会对比propensity-based stratified evaluation、标准offline holdout和counterfactual evaluation方法作为baseline两者。以下,我们描述了我们实验设定的详情,包含:使用的数据集和评估指标、受检推荐模型、以及如何在实验中估计propensities。

图片名称

图2 基于Steiger’s方法的依赖相关度(dependent correlations)显著性测试。每种评估方法(Y and Z)的效果可以通过基于与open loop (randomised) evaluation (X)之间的Kendall’s (tau) rank collrelation进行measur。在baseline evaluation方法(Y)和提出的evaluation方法(Z)间的显著性差异可以基于Steiger’s方法进行measure。

6.1 Datasets和Evaluation Metrics

我们会使用4种数据集,它们被推荐系统的离线评测所广泛使用,称为:MovieLens、Netflix、Yahoo! music rating、Coat shopping dataset。

  • MovieLens包含了6k users对4k items的1M的ratings
  • Netflix包含了10k users对5k items的607k ratings
  • 而Yahoo! dataset包含了300K ratings,它由15.4k个users对1k items进行rate得到
  • Coat shopping dataset:模拟以在线方式购买coat。包含了mh 290 users对 300 items的7k ratings。

所有datasets都通过一个unknown deployed recommendation system以closed loop方式进行收集得到。另外,Yahoo! dataset还有一个独特的feature:一个关于users(5.4k)的子集会被要求对10个随机选中的items(open loop场景)进行评分(rate)。因此,对于该子集,我们会具有closed loop和open loop(random) feedback。相似的,对于Coat dataset,每个用户会被要求提供对于24个self-selected(closed loop) items、以及16个随机选中(open loop) items进行ratings。然而,在一个真实的evaluation setup中,模型会基于收集到的closed loop feedback进行训练;因为实际评估会基于open loop(random) feedback进行很难进行收集。

我们会使用normalised Discounted Cumulative Gain(nDCG@k) metric 对不同的cut-offs(k={5,10,20,30,100}),而非使用不带rank cutoff的nDCG。以便表示对于每个user的所有items的rank metric。对于所有datasets的用户rating值是一个整数 (r in [0, 5])。我们的目标是:对每个user的最相关items进行排序。因此,我们会将所有explicit rating values进行二值化,通过(r>=4)来保留最高的推荐items。在closed loop evaluation中,我们会使用80%的closed loop dataset(MovieLens, Yahoo!和Coat)来进行训练,另外20% random split作为testing另一方面,对于open loop evaluation(Yahoo! & Coat),我们会在所有提供的open loop(randomised) feedback上进行评估。

6.2 推荐模型

我们使用由Cornac framework提供的实验来评估以下的模型:

  • BO: 一个简单的baseline model:会在忽略用户偏好的情况下,推荐一个随机的items组合给每个用户
  • GA:一个baseline model,会在忽略用户偏好的情况下,推荐全局平均rating给每个user
  • POP:一个baseline model,会在忽略用户偏好的情况下,它会基于流行度(popularity:例如:一个指定item被评分的次数)来对items进行rank
  • MF:Matrix Factorisation,一个rating prediction模型,它会将users和items表示为latent vectors。该模型会被用来预测每个user-item pair的observed rating
  • PMF:Probabilistic Matrix Factorisation。MF的扩展版本。
  • SVD++:
  • WMF:Weighted MF。MF的扩展版本。
  • NMF:Non-negative Matrix Factorisation。
  • BPR:Bayesian Personalised Ranking。
  • MMMF:Maximum Margin Matrix Factorisation
  • NCF: Neural Collaborative Filtering
  • MLP: Multi-Layer Perceptron
  • GMF: Generalised Matrix Factorisation
  • NeuMF: Neural Matrix Factorisation

我们对在closed-loop和open loop场景下的模型效果的相对顺序比较关心。因此,根据以下研究,我们会采用不同的超参数来控制latent factors的size:{10, 20, …, 100},从而导致有104个模型需要评估。每个受检模型会指定相应的latent variable size。比如:size m=40 MF,则为(MF^{40})。我们的代码和数据集可以在: https://github.com/terrierteam/stratified_recsys_eval.提供。

6.3 估计Propensity Scores

propensity score (p_{u,i})会被定义成:deployed model将item i曝光给user u的趋势(定义5.1)。由于它对于deployed model来曝光每个item给user是不实际的,我们必须为多个user/item pairs 估计propensity scores (p_{u,i})。[47]提出了一种简单方法来估计propensity scores,它基于如下的简单假设:

假设1: propensity score是用户独立的(user independent),例如:(p_{u,i} = p_{*,i})。该假设是为了解决:在公开数据集中的辅助用户信息的缺失。

user independent propensity score (p_{*,i})可以使用一个2-step的生成过程(generative process)来估计:

[p_{*,i} = p_{*,i}^{select} * p_{*,i}^{interact mid select}]

…(6)

其中:(p_{*,i}^{select})是先验概率(prior probability),item i通过deployed model被推荐出来,(p_{*,i}^{interact mid select})是user 与推荐出来的item i进行交互下的条件概率。基于这样的温和假设,我们可以估计user independent propensity score (p_{*,i})如下:

[hat{p}_{*,i} propto (n_i^*)^{frac{gamma + 1}{2}}]

…(7)

其中,(n_i^*)是item i被交互的总次数,(gamma)是一个参数,它影响着在items上具有不同流行度的propensity分布。power-law参数(gamma)会影响着在items上的propensity分布,具体取决于dataset。根据之前的研究,对于每个dataset,我们会使用极大似然来估计(gamma)参数。

7.实验结果与分析

我们在第5节提出使用一个propensity-based的直接评估方法,它会在推荐系统的离线评估中,考虑上deployed model的混杂角色( confounding role)。在第6节中,我们提出使用Kendall’s (tau)相关系数来量化在propensity-based stratified evaluation方法以及open loop evaluation间多个目标推荐模型的相对顺序间的相似度。下面,我们会会分别根据在第5节的两个研究问题开展实验,并关注和验证在标准离线评估的中 Simpson’s paradox,以及使用提出的propensity-based ed stratified evaluation方法的效果(7.2)。

7.1 RQ1: 研究Simpson’s Paradox

RQ1会研究:在推荐系统的离线评估中,基于假设2中提到的一个closed loop feedback dataset来研究deployed model的confounding effect。在第6.3节中,我们表述了一个简单的统计方法来表示deployed model的角色作为propensity scores。在下面,我们会使用estimated propensity score (hat{p}_{*,i})来将数据集划分成两个相同大小的层( strata),称为Q1层和Q2层。

Q1和Q2 strata来分别表示用户与长尾items和头部items的交叉,我们会根据等式(7),基于每个item交互的总次数来估计propensity scores。

首先,我们会在closed loop dataset(MovieLens和Netflix)和open loop dataset(Yahoo!和Coat)上举例说明Simpson’s paradox。表2和表3会对比评估方法的效果(称为:holdout、IPS、提出的stratified评估法)。出于简洁,以下,我们会关注MovieLens dataset,分析两个模型(BPR、WMF)以及一个metric(nDCG)。我们观察到:在使用holdout和IPF评估法时,BPR要比WMF都好。然而,在同样的test dataset上进行分层分析(Q1和Q2层)表明:对于Q1分层,WMF要比BPR好很多;对于Q2分层,BPR则是支配模型。另外,我们观察到:Q1和Q2分层会分别覆盖99%和1%的user-item interactions。实际上,对于99%的test dataset(例如:Q1分层),WMF要比BPR好很多,但当我们结合Q2分层上1%的feedback时趋势会逆转,如holdout evaluation表示所示。因此,实际问题是:当使用holdout evaluation方法进行评估时认为的,BPR是否会比WMF执行的更好?分层分析表明:通过我们提出的分层评估法,WMF会被认为是更优的模型。我们注意到,BPR只会在1%的feedback dataset上是更优的模型,holdout和IPS evaluation方法两都都会受在test dataset上少量user-item interactions的影响。例如:在Q2分层中的1%的user-item interactions。该分层对应在MovieLens dataset的3499个items中只有4个items。在表3中,在MMMF和MF models间,在Netflix dataset中观察到相同的pattern。

在MovieLens和Netflix datasets中,我们不会访问open loop feedback,例如:feedback会通过一个随机曝光items进行收集。结果是,我们不能measure在一个open loop场景下的模型实验效果,对比起相应的closed loop场景。如第6.1节,我们对于在Coat dataset中的所有users,都有一些open loop feedback;而在Yahoo! dataset上只有一部分users有。表4和表5会表示在Yahoo! dataset中模型的两个pairs的效果对比。特别的,在表4中,我们会对比BPR和MF,它使用nDCG评估指标,并观察到:使用经典holdout evaluation方法,BPR要明显好于MF。另一方法,IPS评估法更偏向于MF,但,基于paired t-test(p < 0.05)上的差异没有显著。然而,基于估计倾向(Q1和Q2分层)的分层分析表明:对于Q1分层,MF要好于BPR;它可以覆盖在test dataset上92%的feedback;而BPR对于Q2分层则是更好的模型,它在closed loop test dataset上覆盖了8%的feedback。确实,对于test dataset中的大多数feedback和items(92%和99.5%),MF要胜过BPR。因此,我们会争论:通过任意的评估法(我们提出的分层评估法,或者open loop evaluation),MF应该被认为是一个更好的模型。当我们基于Q1和Q2分层(例如:holdout evaluation)的聚合数据进行评估模型时,在Yahoo! dataset上,1000个总items中只有少量5个items它对应于只有8%的总user-item interactions,会在受检模型的离线评估中,扮演着一个混杂因子的角色。当考虑上Coat dataset(表5)时,当评估GMF和SVD推荐模型的效果时,我们也会观察到相同的现象。表2、表3、表5中观察到的现象可以通过从一个closed loop场景收集到的datasets(MovieLens、Netflix、Yahoo!和Coat)被解释。因此,收集到的closed loop dataset会倾向于deployed model的特性(如表2、表4和表5中的Q2分层所捕获的)。

接着,为了完整回答RQ1,我们会评估以上观察的总结,通过验证在所有104个模型上的评估中 Simpson’s paradox的盛行。图3表明了,所有受检模型()在Yahoo!和Coat datasets上在open loop evaluation和closed loop evaluation间的相关性。我们观察到,模型会表现出在Q1和Q2分层上的一个imbalanced效果,例如:Q1分层的nDCG score与Q2分层不成比例((nDCG_{Q2} >> nDCG_{Q1}))。另一方法,在Q1分层和open loop evaluation上Kendall’s (tau)相关性,对比起Q2分层要更高。特别的,对于Coat dataset(图3b),基于Q2分层的closed loop evaluation对比open loop evaluation具有一个负向correlation。因此,在holdout evaluation中通过组合这两个异构分层,如图3a和3b所示,不能说明Q1分层覆盖feedback的大多数(在Yahoo!和Coat datasets上分别是92%和93%的total feedback),会导致不可预料的后果。特别的,在open loop evaluation和holdout evaluation间的Kendall’s (tau)相关性,会比Q1分层和open loop evaluation间的对应相关性要低很多,例如:对于Yahoo!和Coat datasets,分别为:0.62 < 0.72 和 0.20 < 0.51. 这回答了RQ1: 推荐系统的offline holdout evaluation会受deployed model特性的影响(在Q2分层捕获),会导致对Simpson’s paradox的一个证实。

总之,在本节中,我们强调了在推荐系统的标准离线评估中,基于于closed loop和open loop datasets,证实了Simpson’s paradox的存在。接着,我们会研究提出的propensity-based分层评估法来解决该问题。

7.2 RQ2: 评估Propensity-based Stratified Evaluation方法

在本节中,我们会研究提出的propensity-based分层评估法会导致:对比IPS和holdout evaluation方法,结论与从open loop(随机化)evaluation获取的结果对齐的范围。确实,我们的目标是:研究每种评估法对应于open loop evaluation的范围。相反的,我们会考虑open loop evaluation,它与在线评估(A/B testing或interleaving)更相似,其中:评估过程不会受任意混淆因子的影响。如第6.2节所示,我们会利用在evaluation方法与open loop evaluation间Kendall’s (tau)的rank相关系数。

表6展示了,在评估方法和ground truth(例如:open loop evaluation)间的Kendall’s (tau)的rank相关系数。在分析该表时,我们会观察到,对于Yahoo! dataset,在holdout evaluation和open loop evaluation间的(tau)相关系数是medium-to-strong((0.599 leq tau leq 0.729));而对于Coat dataset, weaker((-0.40 leq tau leq 0.327)),对于更大的截止点,两个数据集上的相关度都会轻微上升。确实,我们注意到,Coat dataset吃饭休息发货呢MovieLens/Netflix/Yahoo!会有一个不同的数据生成过程。另外,受检用户和items的数目会低于在Yahoo!dataset中数目。该发现与我们之前的研究一致:基于标准rank-based metrics的离线评估不必与在线评估的结果正相关,研究者们会质疑离线评估的合法性。

接着,我们会考虑在counterfactual evaluation(IPS)和open loop evaluation方法间的Kendall’s (tau)相关性。表6表明,IPS评估方法效果要比holdout评估要稍微好些,例如:对于两个数据集中nCDG cut-offs的绝大多数,IPS的相关值要大于holdout evalution方法。然而,根据Steiger’s test,这些相关度差异没有任何在统计上是显著的。因此,我们会下结论,在评估期间,对比起holdout evaluation方法,counterfactual(IPS) evaluation方法不会更好地表示无偏用户偏好。这是因为:在IPS评估方法中,每个feedback是基于它的propensity进行加权独立(weighted individually)的。feedback sampling process(例如:从closed loop feedback中收集到的过程),并不是一个随机过程(random process)。因此,抽样的feedback会倾斜,相应的estimated propensity scores是不均的。在这种情况下,基于disproportionate propensities对feedback进行reweighting会导致在使用IPS评估模型效果评估上的高variance。

我们现在考虑表6中分层评估的相关性。这表明:在两个数据集中,对于nDCG cut-offs的绝大多数,特别是更深的cut-offs,分层评估的效果要好于holdout和IPS评估方法。例如:考虑将nDCG作为evaluation metric,我们会观察到,提出的分层评估方法效果要显著好于holdout evaluation和IPS evaluation,例如:对于Yahoo! dataset,0.710 > 0.622,0.710 > 0.644;对于Coat dataset,有0.283 > 0.202和0.283 > 0.225. 总体上,我们发现,对于两个datasets中更深的nDCG cut-offs,我们的propensity-based evaluation方法,效果要显著好于holdout和counterfactual evaluation。这可以回答RQ2.

然而,holdout evaluation的效果,IPS evaluation和提出的propensity-based分层评估方法,对于shallow nDCG cut-offs并不显著(对于Yahoo! dataset和Coat dataset来说,分别是:(10 leq k leq 20 和 20 leq k leq 30))。对于deeper rank cut-offs的增加的sensitivity,支持了之前的研究:它对于推荐系统评估上deeper cut-offs的sparsity和discriminative pwoer来说更健壮。【43】发现,在feedback sampling process期间,由于只有少量items会曝光给该user,使用deeper cut-offs会允许研究者执行更健壮和discriminative evaluations。由【25】中,deeper rank cut-offs的使用对于训练listwise learning2rank技术来说可以做出相似的观察。

在feedback sub-populations (表6中的Q1和Q2分层)的进一步实验表明:受检模型的离线评估,它只基于long-tail feedback(Q1分层)更好地与open loop evaluation相关。特别的,对于Coat dataset,基于Q2分层的受检模型的离线评估,会与open loop evaluation具有一个负相关性。这支持了[9]的工作,它发现:非常少量的头部流行items会对推荐系统的rank-based evaluation进行倾斜。他们建议:当评估推荐模型的效果时,排除非常流行的items

而表6演示了提出的分层评估方法对于两个sub-populations(Q1和Q2分层)的效果,我们接着检查了所使用分层数目的影响。特别的,在图4中,演示了提出的分层评估对于Coat和Yahoo! datasets的分层数目的影响。水平轴(X={1,2, …, 10})会表示分层的数目,而竖直轴表示在提出的分层数目上与open loop(随机化)评估间对于104个受检模型的相关性。当我们只具有一个分层时(例如:在图4a和图4b中的X=1),提出的分层评估法对应于表6中的holdout evaluation。我们观察到,对于在两个数据集中的分层数目,对比起holdout评估(例如:X=1),提出的分层评估方法可以更好地与open loop(随机)评估相关。然而,在提出的分层评估和open loop(随机)评估间的相关度上,分层数目具有一个边缘效应(marginal effect),例如:在提出的分层评估(2<=X <=10)对于Coats和Yahoo! datasets间的平均相关度(mean correlations)是:(0.266 pm 0.021)以及(0.706 pm 0.026),对比在holdout evaluation(X=1)中分别是0.202和0.622相关度。另外,对于(2 leq X leq 10),大多数cases(coats和Yahoo!中分别是5/9和7/9)表示显著高于holdout evaluation的相关度。注意,每个dataset中的分层数目,可以使用分层原则(stratification principle)【24】来决定,它倾向于使用在每个层(stratum)内的层(strata),用户的反馈尽可能会相似。尽管不同数据集具有不同级别的closed loop effect,它取决于deployed model的特性,我们的实验表明:没有关于deployed model的进一步信息,基于estimated propensities将closed loop feedback分层为sub-populations,允许研究者们说明来自收集到的feedback dataset的closed loop effect。

8. 结论

参考

阿里在《One Model to Serve All: Star Topology Adaptive Recommender for Multi-Domain CTR Prediction》中提出了一种思路来解决不同模块使用同一模型的思路:

1.介绍

传统CTR模型关注于single-domain的prediction,其中ctr模型会服务于单个业务domain,它基于从该domain中收集到的样本进行训练。每个业务domain是一个特定位置(items被展示给移动端app或PC 网站)。在大的商业公司(比如:阿里和亚马逊),经常有许多业务domains需要进行CTR预估来增强用户满意度和提升商业回报。例如,在阿里,商业domains的范围有: 猜你喜欢、Banner、以及其它domains。图1展示了在阿里的一些业务domains。

图片名称

图一

  • Banner:在banner中,会在taobao主页的top banner上展示items。这些item可以是一个商品、商店、或一个品牌。
  • 猜你喜欢:在该模块中,items都是商品,在左或右列被展示给用户

由于不同业务domains会有重叠的用户组(user groups)和items,在这些domains间会存在共性,允许信息共享对于学习每个domain的CTR模型来说是有益的。然而,特定的user group可能会不同,用户行为也会在多个domains内变化。这些差异会导致domain-specific数据分布简单将所有data进行混合并训练单个共享的CTR模型不能很好地在所有domains上工作良好

除了混合数据并训练一个shared model外,另一种简单解法是,为每个商业domain构建一个独立的模型。这种方式也会有一些缺点:

  • (1) 一些业务domains会比另一些domains具有更少的数据。将数据进行分割会忽略domain共性,并造成更少的训练数据,使得模型很难学习
  • (2) 维护多个模型会造成资源大量消耗,并需要更多的人工开销。当商业domains的数目达到上百个时会相当麻烦

本paper的目标是学习一个有效和高效的CTR模型来同时处理多个domains。我们将multi-domain CTR prediction公式化成:recommender需要为M个商业domains (D_1, D_2, cdots, D_M)作为CTR预测。该模型可以将input作为(x, y, p),其中:

  • x是公共特征(像:历史用户行为、用户profile特征、item feature、context feature等),会被多个商业domain使用
  • (y in lbrace 0, 1rbrace)是点击label
  • p是domain indicator:它表示该样本是在哪个domain上被收集

注意:(x,y)从domain-specific分布(D_p)上抽取得到,分布会随着不同的domains有所不同。multi-domain CTR预测的目标是:构建一个有效且高效的模型,它会为每个domain给出精准的CTR预测,并在资源消耗上开销不大,该模型可以充分利用domain共性,并能捕捉domain间的差异。

一种用于提升学习的可能策略是,使用domain进行多任务学习。如图3所示,multi-domain CTR预测与多任务学习间的不同之处是:multi-domain CTR预测是在不同的domains上解决相同的任务(都是CTR 预测任务),不同domains的label spaces是相同的,数据分布有所不同。作为对比,大多数多任务学习方法则在相同的domain上解决不同的任务,其中label space会不同,例如:联合估计CTR和CVR。由于任务的异构性,已存在的多任务学习方法则关注于在bottom layers上的共享信息,但会在task-specific output layers上保持独立。直接在multi-domain CTR预测上采用multi-task方法可能不会充分利用上在label space上的domain关系,并且会忽略不同domains上不同数据分布。

图片名称

图3 multi-task learning与multi-domain learning的对比。大多数多任务学习方法关注在单个domain内处理不同任务。作为对比,multi-domain learning会为多个domains作出预测来解决相同的任务,例如:ctr预测,其中,label spaces是相同的。直接采用multi-task方法来进行multi-domain CTR预测不能充分利用在label space中的domain关系,并忽略不同domains上的不同数据分布

为了充分利用domain关系,我们提出星形拓朴自适应推荐(STAR Topology Adaptive Recommender: STAR)来进行multi-domain CTR预估。提出的STAR模型是星形拓朴,如图4所示。STAR包含了共享的中心参数,以及domain-specific参数的多个集合。每个domain的最终模型通过将共享中心参数(shared centerd params)和domain-specific参数进行组合来获得。中心参数(centered parameters)被用于学习在所有domains间的总行为,其中公共知识可以被学习到以及在所有domains间转移。domain-specific参数会捕获在不同domains间的特定行为来提升更加refined的CTR预估。star topology会利用跨多个domains间的有效信息转换,来学习domain公共性和差异。该paper会实现STAR模型,它使用在每个layer上对weights做element-wise product来作为组合策略。由于embedding layers会在工业界推荐器上贡献大多数参数量,添加的domain-specific参数对于总参数量来说可被忽略。因此,使用STAR模型来serve多个domains只需要添加少量计算和内存开销,就能达到更好的效果。

主要的贡献如下:

  • STAR:
  • 不同domains具有不同的数据分布,当使用batch normalization时,这会生成不准确的统计。我们提出Partitioned Normalization(PN),它会为不同domains上的样本进行独立normalization来解决该问题。PN会在domain内生成更准确的moments,它会提升model效果。
  • 在mulit-domainCTR预测中,描绘domain信息的features是很重要的。我们提出一个auxiliary network,它会直接将domain indicator作为input,并学习描绘该domain的有embeddings。该embedding会feed给auxiliary network,它比原始network更简单。这会使得domain indicator以一种直接方式影响最终预测。
  • 我们会在工业产品数据集上评估STAR,并将它部署在2020的阿里展示广告系统上。持续的收益验证了STAR的效果。直到现在,STAR的部署带来了6%的CTR和8%的RPM提升。它可以泛化到其它场景上。

2.相关工作

图片名称

图2 (a)对于所有domains的single shared model,方形nodes表示共享模型 (b) 每个domain一个模型,每个模型独立学习。圆形节点表示domain-specific model (c) 提出的STAR,其中每个domain具有特定的参数,也会共享一个公共centered model。边意味着center shared参数与domain-specific参数的组合

3.提出的方法

在本节中,我们首先提出一个关于multi-domain CTR预估的简洁背景介绍。接下是提出方法multi-domain的CTR预估的架构总览。接着我们详细介绍STAR,包括提出的STAR topology network,partitioned normalization以及auxiliary network。

3.1 Multi-domain CTR预估

在序列推荐系统中,推荐会采用用户历史行为、user profile特征、target item feature以及其它features(比如:context feature)作为input。一个用户u在一个item m上点击的预估CTR((hat{y}))可以计算如下:

[hat{y} = f( E(u_1), cdots, E(u_i); E(m_1), cdots, E(m_j); E(c_j), cdots, E(c_k))]

其中:

  • (lbrace u_1, cdots, u_i rbrace)是user features的集合,包括:用户历史行为,user pfofile feature。
  • (lbrace m_1, cdots, m_j rbrace)是target item feature的集合
  • (lbrace c_1, cdots, c_k rbrace)是其它features的集合
  • (E(cdot) in R^d)表示embedding layer,它会将sparse IDs映射到可学习的dense vectors上

在将raw feartues映射到低维embeddings上后,惯例是将这些embeddings聚合来获取固定长度的vectors。可以部署不同类型的聚合方法(42, 43)来聚合这些embeddings来抽取用户兴趣并获取固定长度的presentation。获得的representation接着feed到下面的DNN中(例如:一个multi layer fully-connected network)来获得最终的CTR预测。

传统的CTR模型(6,13,23,42,43)通常从一个单一商业domain上获取数据进行训练。然而,真实推荐通常会处理不同的商业domains。推荐系统需要为M个domains (D_1, D_2, cdots, D_M)同时作为CTR预测。该模型会将(x,y,p)作为input,其中:

  • x是在多个domains中用到的公共featrure(比如:用户历史行为、user profile、target item feature);
  • (y in lbrace 0, 1rbrace)是点击的label
  • (p in lbrace 1,2, cdots, Mrbrace)是domain indicator,它会表示样本来自哪个domain。

注意(x,y)是从domain-specific分布(D_p)上抽样得到,该分布对于不同domains会不同。multi-domain CTR预估的目标是:构建单个CTR模型,它可以给出准确的CTR预估,并以较低资源和开销进行serve。

3.2 架构总览

如上所示,忽略domain indicator p,学习单个共享CTR模型会忽略domain的差异性。这会导致次优的模型参数。另一方面,对于不同domain训练不同模型会更差,因为将domains进行分隔,每个模型会得到更少的数据。由于资源开销以及人力开销,在生产环境中为每个domain维护一个独立的模型是不可行的。

最后,我们提出STAR来进行multi-domain CTR预估,它可以更好使用不同domains间的相似性,并能捕获domain上的差异。如图4所示,STAR包含了三个主要部分:

  • (1) partitioned normalization(PN):它会为不同domains间的样本进行单独normalization
  • (2) star topology FC network (star topology FCN)
  • (3) auxiliary network:它会将domain indicator看成是input featrure,并能学到它的语义embeddings来捕获domain差异性

图片名称

图4 single-domain CTR预测以及STAR的对比。在STAR中,partitioned normalization(PN)会为不同domains的样本进行nomalization。被归一化的features接着作为input来feed给下面的star topology FCN中。star topology FCN包含了共享的centered FCN以及多个domain-specific FCNs。每个domain的最终组合模型通过

在训练期间,domain indicator p会首先被抽样,接着会使用一个B个mini-batch实例:

[(x_1, p), (x_2, p), cdots, (X_B, p)]

会从该domain中抽样。STAR会首先将这些input features通过一个embedding layer进行嵌入作为低维vectors。在工业推荐系统中,该模型通常会使用数十亿features(15)进行训练,embedding的参数通常要比其它部分的参数更多。这使得它在不同domains上使用有限数据来学习domain-specific embedding很难。例如:对于在日常任务中用到的模型,embeddings参数要比FC layers上超过10000倍。因此,在STAR模型中,我们将所有domains共享相同的embedding layer,例如:在不同domains上的相同ID features会共享相同的embedding。共享的embedding layer会跨不同的domains,可以极大减少计算和内存开销。

该embeddings接着被pooled和concatenated,来获得B个固定长度的reprensentations。在这之后,B个抽取的representations会通过PN(patitioned normalization) layer进行处理,接着为不同domains进行独立的normalization statistics。normalizated vectors接着作为input被feed到star topology FCN中来获取output。star topology FCN包含了共享的centered FCN以及多个domain-specific FCNs。每个domain的最终模型通过将shared centered FCN和domain-specific FCN进行组合获得

在multi-domain CTR预估中,描述domain信息的features很重要。在STAR模型中,auxiliary network会将domain indicator作为input,并使用描述该domain的其它features来feed到auxiliary network中。auxiliary network的output 会被添加到star topology FCN的output中,来获取最终的prediction。我们让auxiliary network比star topoology FCN更简单,便得让模型以一个直接和简单方式来捕获domain差异。接着我们描述这些组件。

3.3 Partitioned Normalization

如上,raw featrures会首先转换成低维embeddings,接着进行pool和aggregation来获得中间表示。尽管一个实例的中间表示为z,为了训练deep networks更快和更稳定,一个标准的惯例是应用normalization layer到中间表示z上。在所有的normalization方法之间,batch normalization(BN)是一个表示方法,它对于训练非常深的DNN很重要(14,31)。BN会为所有样本使用一个全局的normalziation,它会累积normalization moments,并学习跨多个样本的共享参数。具体的,BN的训练归一化给定如下:

[z' = gamma frac{z-u}{sqrt{sigma^2 + epsilon}} + beta]

其中:

  • z’是output
  • (gamma)和(beta)是可学习的scale和bias参数
  • (mu, sigma^2)是当前mini-batch的均值(mean)和方差(variances)

在testing期间,在所有样本上的均值E和方差Var的移动平均统计,使用如下:

[z' = gamma frac{z-E}{sqrt{Var + epsilon}} + beta]

…(2)

换句话说,BN会假设:所有样本是独立同分布(i.i.d)的,并在所有训练样本上使用共享的statistics。

然而,在multi-domain CTR预估中,样本假设是在一个特定domain上是局部i.i.d的。在testing期间在BN layers上共享全局的monents和参数,会牺牲domain差异性,并导致模型效果的降级。为了捕获每个domain上唯一的数据特性,我们提出partitioned normalization(PN), 它会为不同domains上单独对statistics和parameters做normalization。具体的,在training期间,假设当前的mini-batch是会第p个domain上抽样得到,我们会计算当前mini-batch的均值(mean)和方差(variances),并将feature进行归一化:

[z' = (gamma * gamma_p) frac{z - mu}{sqrt{sigma^2 + epsilon}} + (gamma + gamma_p)]

…(3)

其中:

  • (gamma, beta)是全局的scale和bias
  • (gamma_p, beta_p)是domain-specific scale和bias参数

对于每个mini-batch,它会接受最终scale,通过将共享的(gamma)与domain-specific (gamma_p)进行element-wise相乘作为final scale,例如:PN会根据domain indicator自适应地对representation进行缩放。相似的,PN的bias也可以根据domain自适应地计算,它可以通过global bias (beta)和domain-specific bias (beta_p)求和来实现。注意:通过对比BN,PN也会在training期间使用当前mini-batch的moments,但PN会引入domain-specific scale和bias (gamma_p, beta_p)来捕获domain差异。

除了在scale和bias上的修改外,PN也会让不同domains进累计domain-specific的均值(E_p)和方差(Var_p)的移动平均。在testing期间,PN会将第p个domain的实验z进行转换:

[z' = (gamma * gamma_p) frac{z - E_p}{Var_p + epsilon} + (gamma + gamma_p)]

…(4)

从等式(4)来说,我们可以看到,PN会使用domain-specific的平均(E_p)和方差(Var_p)来归一化中间表示z。因而,PN会根据domain indicator为条件自适应更改中间表示来捕获差异特性。

3.4 Star Topology FCN

在PN layer之后,表示(z')会被作为input来feed到下面的star topology multi-layer FCN上。如图5所示,提出的star topology FCN会为每个domain包含一个共享的centerd FCN和独立FCNs,因而,FCN的总数是M+1. 第p个domain的最终模型可以通过对shared centered FCN和domain-specific FCN组合来得到,其中,centered参数会学习在所有domains上的通用行为,domain-specific参数会捕获在不同domains上的指定行为,来帮助更多的fefined CTR预测。

图片名称

图5 STAR如何为不同domains生成FCN的参数。STAR包含了一个共享的centered FCN和独立的每个domain的FCNs。对于每个domain,一个neural network layer的最终weights会通过将shared FCN与domain-specific FCN进行element-wise乘法来获得。共享参数会通过所有示例的梯度进行更新,而domain-speciific参数只会通过在该domain下的样本进行更新。

特别的,对于shared FCN,假设W和b分别是NN layer上的weights和bias。对于第p个在omain的specific FCN,假设:(W_p)和(b_p)是相应layer上的weights和bias。我们将input维度表示为c,output维度表示为d,(例如:(W, W_p in R^{c times d}, b, b_p in R^d)),第p个domain的最终的weights (W_i^*)和bias (b_i^*)可以通过以下获得:

[W_p^* = W_p otimes W, b_p^* = b_p + b]

…(5)

其中,(otimes)表示element-wise乘法。假设:(in_p in R^{c times 1})表示来自第p个domain该neural network layer的输入,最终的output (out_p in R^d times 1)给定如下:

[out_p = phi((W_p^*)^T in_p + b_p^*)]

…(6)

其中,(phi)表示该layer的activation function。shared param和在domain-specific param的组合可以在所有layers上使用。通过这种方式,STAR可以对它的参数基于domain为条件进行调节。

注意,我们会对shared centerd FCN和domain-specific FCN进行组合策略,它的实现是:将每个layer上的weights进行element-wise乘,将bias进行加得到;也可以尝试研究其它策略。shared参数会通过对所有样本的梯度进行更新,而domain-specific参数则只会在使用该domain的样本时才会被更新。如上所示,工业推荐系统的大多数参数,会由embedding layer来贡献,STAR只会增加M个FCNs,量级很少。

3.5 Auxiliary Network

在CTR建模的传统方式下,所有features会被同等看待,并被feed给复杂的模型。在multi-domain CTR预测时,对于模型来说自动学习domain差异是很难的。我们会讨论一个好的multi-domain CTR模型应该具有以下几个特性:

  • (1) 具有考虑上domain特性的信息特征
  • (2) 这些featrures可以很容易并直接影响final CTR预估

背后的直觉是,描会domains的features很重要,因为它可以减少模型难度来捕获domains间的不同。

最后,我们提出一个auxiliary network来学习domain差异。为了讨论与domain特性相关的信息特征,我们将domain features直接看成是ID feature input。domain indicator会首先映射到embedding vector上,并与其它features进行concate。auxiliary network接着会根据concatenated features分别计算forward pass,来获得一维output。我们将star topology FCN的一维output表示成(s_m),auxiliary network的output表示成(s_a)。(s_m)和(s_a)会被相加来获得最终logit。接着使用sigmoid来获得CTR预测:

[Sigmoid(s_m + s_a)]

…(7)

在我们的实现中,auxiliary network会比主网络更简单,它是一个二层FCN。这种简单结构可以使得domain features可以直接影响final prediction。

(hat{y}_i^p)表示在第p个domain的第i个样本上的预测概率,(y_i^p in lbrace 0, 1rbrace)是ground truth。我们会在所有domains上对cross-entropy loss function进行最小化:

[min sumlimits_{p=1}^M sumlimits_{i=1}^{N_p} - y_i^p log(y_i^p) - (1 - y_i^p) log(1 - hat{y}_i^p)]

…(8)

4.实验

参考

tx在《Progressive Layered Extraction (PLE): A Novel Multi-Task Learning (MTL) Model for Personalized Recommendations》提出了PLE模型:

1.介绍

个性化推荐在在线应用中扮演着重要角色。RS需要包含多种用户反馈来建模用户兴趣,并最大化用户的engagement和satisfaction。然而,由于存在高维问题,用户满意度通常很难通过一个learning算法来直接解决。同时,用户satisfaction和engagement具有许多可以直接学习的主要因素,比如:点击、完成、分享、收藏、评论的概率(click likelihood)。因此,有许多尝试使用MTL多任务学习到RS中来同时建模用户的satisfaction或engagement。实际上,这在工业应用中是主流。

MTL会在单个模型中同时学习多个任务,通过在任务间共享信息来高效地提升学习。然而,在现实推荐系统中,任务经常松散相关或者有冲突,这会导致效果退化(performance deterioration),称为“negative transfer”。在一个真实的大规模视频推荐系统和真实数据集上,我们通过大量实验发现,当任务相关性很复杂时并且有样本依赖时(例如:对比起单任务模型,多个任务不能同时提升,这被称为“跷跷板效应(seesaw phenomenon )”),已存在的MTL模型通常可以提升一些任务,但会牺牲其它任务的效果。

之前的工作主要解决negative transfer,但忽略了seesaw phenomenon,例如:cross-stitch network[16]和sluice network [18]提出,学习静态线性组合 (static linear combinations)来对不同任务的表示进行融合(fuse),这不能捕获样本依赖性(sample dependent)。MMOE[13]应用gating networks来对基于input的bottom experts进行组合来处理任务差异,但忽略了在experts间的差异和交叉。因此,设计一个更强大和高效的模型来处理复杂相关性,并消除seesaw效应很关键。

为了达到该目标,我们提出了一个新的MTL模型,称为渐近层抽取 Progressive Layered Extraction (PLE),它可以很好地利用在shared network设计上的先验知识来捕获复杂的任务相关性(task correlations)。对比起在MMOE中的粗糙共享参数,PLE会显式地将shared experts和task-specific experts进行分离来缓和有害参数干扰(harmful)。再者,PLE会引入multi-level experts和gating networks,并应用progressive separation routing来从lower-layer expert抽取更深的knowledge,并在更高levels上逐渐将task-specific parameters给分离出来。

为了评估PLE的效果,我们在真实工业界推荐dataset以及主要的公开数据集上(包括census-income[5]、synthetic data[13]、以及Ali-CCP)开展了大量实验。实验结果表明:在所有数据集上,PLE的效果要好于state-of-the-art MTL模型,并展示了一致提升。另外,在tencent的大规模视频推荐系统中在线指标的极大提升,表明PLE的优点。

主要的贡献如下:

  • 在大规模视频推荐系统和公开数据集上,通过大量实验发现,一个有意思的seesaw效应已经被观察到:SOTA的MTL模型经常会提升某些任务,但同时牺牲另一些任务的效果,并不能胜过单任务模型(single-task model),因为存在复杂的内在相关性。
  • 使用新的shared learning架构的PLE模型会提升shared learning效率,并能从joint representation learning和information routing的角度,能解决seesaw现象以及negative transfer。除了推荐应用外,PLE可以灵活地应用于许多场景
  • 我们在工业和公开datasets上的大量离线实验评估了PLE的效果。在tencent的大内容推荐平台上的在线A/B test结果也显示了,PLE在SOTA的MTL模型上能有极大提升,在view-count上有2.23%的增长,在watch-time上有1.84%的提升,它可以生成极大的商业收益。PEL已经成功部署到推荐系统中,可以应用到许多其它推荐应用上。

2.相关工作

在推荐系统中,高效的多任务学习模型、以及MTL模型的应用是两个研究领域。在本节中,我们简单讨论在这两个领域的相关工作。

2.1 MTL模型

图片名称

图1 MTL模型的network routing。蓝色四边形和圆形分别表示shared layers和gating network,粉色和绿色四边形表示task-specific layers,粉色和绿色圆形表示不同任务的task-specific gating networks

图1 a)中展示的Hard parameter sharing【2】是最基础和常用的MTL结构,但经常存在negative transfer,因为参数会在多个任务间直接共享而存在任务冲突(task conflicts)。为了解决任务冲突,图 1f)的cross-stitch network[16]和图1g)的sluice network[18]同时提出学习对来自不同的tasks的representations进行选择性的线性组合加权。然而,在这些模型中,representations是通过对所有样本使用相同的static weights进行组合的,并没有被解决seesaw效应。在本工作中,提出了PLE(Progressive Layerd Extraction)模型,并使用带gate结构的progressive routing机制来对基于input的knowledge进行融合(fuse),它可以达到适配不同的inputs的组合。

使用gate结构和attention network来进行信息融合(information fusion)已经存在一些研究。MOE【8】首先提出在bottom上共享一些experts,并通过一个gating network来对experts进行组合。MMOE[13]则对MOE进行扩展,并为每个任务使用不同的gates来获取在MTL中的不同融合权重(fusing weights)。相似的,MRAN[24]会应用multi-head self-attention来学习在不同feature sets上的不同的representation子空间。expert和attention module则在所有tasks间共享,在MOE、MMOE和MRAN中不存在task-specific的概念。相反,我们提出的CGC(Customized Gate Control)和PLE模型会对task-common参数和task-specific参数进行显式分离(explicitly),并避免由复杂任务相关性导致的参数冲突。对于MMOE来说,尽管存在理论上的可能性收敛到我们的网络设计,在网络设计上的先验知识(prior knowledge)是很重要的,MMOE在实际上很难发现收敛(convergence)。Liu【10】应用task-specific attention networks来对选择性地对shared features进行融合(fuse),但不同的任务在attention network中的融合(fusion)之前仍会共享相同的representation。之前的network的研究都没有显式地解决representation learning和routing的joint optimization问题,特别是在一个 inseparable joint(非独立联合)方式,而该工作会首次在joint learning和routing的通用框架上提出一个新的progressive separation方式

存在一些工作,使用AutoML的方式来寻找一个好的network结构。SNR framework【12】通过二元随机变量来控制在sub-networks间的connections,并使用NAS来搜索最优的结构。相似的,Gumbel-matrix routing框架【15】则学习MTL模型的routing并将它公式化成一个使用Gumbel-Softmax trick的二元matrix。像MDP的Modeling routing process,会使用MARL[19]来训练routing network。在这些工作的network结构使用特定的简化猜想而设计的,不够通用。在[17]中的routing network会为每个任务在每个depth选择不超过一个function block,这会减小模型的表现力。Gumbel-matrix routing network[15]则提出在representation learning上进行constraint,因为每个任务的input需要对每个layer上的representation进行merge。另外,在这些frameworks中的fusing weights不适合对不同的inputs,对于这些方法来说寻找最优的结果带来的昂贵搜索开销是另一个挑战。

2.2 RS中的MTL

为了更好地利用多种用户行为,MTL learning已经被广泛应用到推荐系统中,并达到了大量提升。一些研究则会集成传统的推荐算法:比如:在MTL中集成CF和MF。Lu[11]和Wang[23]则引入regularization在隐表示上。

。。。

3.推荐中的seesaw效应

negative transfer是在MTL中的一个常见现象,特别是对于松散相关的任务【21】。对于复杂的任务相关性,特别是样本依赖相关模式,我们也观察到:当提升shared learning效率并达到比相应的single-task模型的极大提升时,会有seesaw现象。(对于当前MTL模型来说,在所有任务上获得提升是很难的)。在本节中,我们基于tencent的大规模视频推荐系统,介绍和调查了seesaw效应。

3.1 视频推荐的MTL ranking系统

图片名称

图2 视频推荐的一个MTL ranking系统

在本节中,我们简单引入服务tencent news的MTL ranking系统,它是世界最大的内容平台,基于用户的多样化反馈来推荐新闻和视频给用户。如图2所示,有多个目标来建模不同的用户行为:比如:在MTL ranking系统中的click、share、comment。在offline的训练过程, 我们会基于从user logs中抽取的用户行为来训练MTL ranking模型。接着,对于每个任务,基于ranking module的weighted-multiplication会将这些预测分(predicted scores)进行组合到一个最终分,通过等式1的组合函数,最终推荐top-ranked videos给用户。

[score={p_{VTR}}^{w_{VTR}} times {p_{VCR}}^{w_{VCR}} times {p_{SHR}}^{W_{SHR}} times cdots times {p_{CMR}}^{W_{CMR}} times f(video_len)]

…(1)

其中:

  • 每个w:决定了每个predicted score的相对重要性
  • (f(video_len)):是一个非线性变换函数,比如:在视频长度(video duration)上的sigmoid或log函数
  • (w_{VTR}, w_{VCR}, w_{SHR}, w_{CMR}):是通过在线实验搜索优化的超参数,用来最大化online metrics。

在所有任务之外,播放完成度VCR(View Completion Ratio)播放通过率VTR(View-Through Rate)是分别是两个重要目标建模关键在线指标:观看数(view-count)和观看时长(watch-time)。特别的,VCR预测是一个回归任务(regression task),它使用MSE loss来预测每次view的完成度。VTR预测是一个二分类任务,它使用cross-entropy loss来预测一个valid view的概率,它被定义成:超过一定观看时间阈值的一次播放行为。在VCR和VTR间的相关模式(correlation pattern)很复杂。首先, VTR的label是一个关于播放动作(play action)和VCR的组合因子,只有watch time超过阈值的一个play action会被看成是一个有效view。第二,play action的分布也复杂,因为在wifi下来自auto-play场景的样本会高于play的平均概率,而来自显式点击场景(没有auto-play)的其它样本会具有更低的play概率。由于复杂和强样本依赖的相关性,当联合建模VCR和VTR会观察到一个seesaw效应。

3.2 在MTL中的Seesaw效应

为了更好地理解seesaw效应,我们会使用single-task模型和SOTA MTL模型来执行实验分析,在复杂相关的VCR和VTR任务组上。除了hard parameter sharing、cross-stitch、sluice network、mmoe外,我们也评估了两个独创的结构:非对称共享(asymmetric sharing)和定制共享(customized sharing)。

  • 非对称共享(asymmetric sharing):是一种新的sharing机制,用来捕获在任务间的非对称关系。根据图1b,bottom layers会在任务间的非对称共享,具体某个任务的表示需要共享依赖于任务间的关系。公共融合操作(fusion)(比如:concatenation、sum-pooling、average-pooling)可以用来组合不同任务的bottom layers的outputs
  • 定制共享(Customized Sharing):图1c会显式地将shared parameters和task-specific parameters进行分离,以避免内在冲突和negative transfer。对比起single-task模型,customized sharing会添加一个shared bottom layer来抽取sharing信息,并将shared bottom layer与task-specific layer的concatenation后feed给相应task的tower layer。

图3展示了实验结果,其中右上角的泡泡表示具有更好的效果,具有更高的AUC和更低的MSE。AUC或MSE具有0.1%的提升,会对整个系统的在线指标具有极大提升【4,6,14】。可以看到硬参数共享(hard parameter sharing)和cross-stitch network会存在极大的negative transfer问题,在VTR上效果最差。通过独创的共享机制来捕获非对称关系,asymmetric sharing可以达到在VTR上的极大提升,但在VCR上出现极大降低,这与sluice network类似。由于shared layers和task-specific layers的显式分隔,customized sharing可以在single-task模型上提升VCR,而在VTR上只有轻微的损耗。MMOE则会在两个任务上同时对single-task进行提升,但VCR的提升只有:+0.0001. 尽管这些模型会在这两个任务上具有不同的学习效率(learning efficiency),我们可以很明确地观察到seesaw效应:一个任务的提升会导致其它任务的效果退化,因为没有一个baseline MTL模型依完全落在第二象限。在公开的benchmark datasets上的具有SOTA模型的实验,也会具有明显的seesaw效应。细节会在第5.2节中提供。

图片名称

图3

如前所示,VCR和VRT间的相关模式是很复杂并且样本依赖(sample depedent)的。特别的,VCR和CTR间存在一些偏序关系(partially ordered relations),不同样本表现出不同的相关度。因而,cross-stitch和sluice network会为所有样本使用相同的static weights来共享representations,不能捕获样本依赖,存在seesaw效应。MMOE通过使用gates获得来基于input的fusing weights,在一定程度上会处理任务差异(sample difference)和样本差异(sample difference),这会胜过其它baseline MTL模型。然而,在MMOE中experts会在所有tasks间共享,没有差异,这不能捕获复杂任务相关性,这会对某些tasks带来有害噪音。再者,MMOE会忽略在不同experts间的交叉,这会进一步限制joint optimization的效果。除了VCR和VTR外,在工业界推荐应用中有许多复杂相关任务,因为人类行为经常微妙且复杂,例如:在在线广告和电商平台中的CTR预测和CVR预测。因此,一个强大的网络需要考虑在experts间的差异(differentiation)和交叉(interactions),这对于消除由复杂任务相关性带来的seesaw效应来说很重要。

在本paper中,我们提出了一个PLE(Progressive Layered Extraction)模型来解决seesaw效应和negative transfer。PLE的关键思想是:

  • 首先,它会显示地将shared experts和task-specific experts进行分离,来避免有害的参数干扰。
  • 第二,multi-level experts和gating networks会被引入来对多个抽象表示(abstract representations)进行融合。
  • 最后,它会采用一个新的progressive separation routing来建模在experts间的交互,并达到在复杂相关任务间更高效的知识迁移。

如图3所示,PLE在多个任务上要比MMOE取得更好的提升。结构设计和实验的细节在第4节。

4.PLE(PROGRESSIVE LAYERED EXTRACTION)

为了解决seesaw效应和negative transfer,我们提出了一个Progressive Layered Extraction(PLE)模型,它使用一个新的sharing结构设计。

  • 首先,一个CGC(Customized Gate Control)模型会显式地对提出的shared experts和specific experts进行分离。
  • 第二,CGC被扩展到一个通用的PLE模型中,它使用multi-level gating networks和progressive separation routing来进行更高效的信息共享和joint learning。
  • 最终,对于MTL模型来说,loss function会被最优化以便更好地处理joint training的实际挑战。

4.1 CGC(customized Gate Control)

受customized sharing的启发,它在single-task上,通过显式分离shared layers和task-specific layers来达到与single-task模型相似的效果。如图4所示,在bottom有一些experts modules,在顶部有一些task-specific tower networks上。每个expert module由多个称为experts的子网络(sub-networks),在每个module中的experts的数目是一个用来tune的超参数。相似的,一个tower network也是一个multi-layer network,宽和高是超参数。特别的,在CGC中的shared experts负责学习共享模式(shared patterns),而对于specific tasks的模式会由task-specific experts来抽取。每个tower network会从shared experts和它自己的task-specific experts中吸收知识,这意味着shared experts的参数会被所有任务影响,而task-specific experts的参数具受相应specific task的影响。

图片名称

图4 CGC模型(Customized Gate Control)

在CGC中,对于选择性融合(selective fusion),shared experts和task-specifc experts通过一个gating network进行组合。如图4所示,gating network的结构是基于一个使用softmax作为activation function、input会作为selector的single-layer feedforward network,用来计算选中vectors的weighted sum,例如:experts的outputs。更精准的,task k的gating network的output可以公式化为:

[g^k(x)= w^k(x) s^k(x)]

…(2)

其中:

  • x是input representation
  • (w^k(x))是一个weighting function,通过线性变换和一个Softmax layer来计算task k的weight vector:
[w^k(x) = Softmax(W_g^k x)]

…(3)

其中:

  • (W_g^k in R^{(m_k + m_s) times d})是参数矩阵
  • (m_s)和(m_k)分别是shared experts以及第k个specific experts的数目,d是input representation的维度。
  • (S^k(x))是一个selected matrix,它由所有selected vectors组成,包括shared experts和第k个specific experts:
[S^k(x) = [E_{(k,1)}^T, E_{(k,2)}^T, cdots, E_{(k,m_k)}^T, E_{(s,1)}^T, E_{(s,2)}^T, cdots, E_{(s,m_s)}^T ]^T]

…(4)

最后,第k个任务的prediction是:

[y^k(x) = t^k (g^k(x))]

…(5)

其中:

  • 第(t^k)表示任务k的tower network。

对比起MMOE,CGC会移除在一个任务的tower network与其它任务的task-specific experts间connections,允许不同类型的experts来集中高效学习不同的知识,无需干扰。结合gating networks的好处,来基于input动态融合representations,CGC会达到在tasks间更灵活的balance,更好处理任务冲突和样本依赖相关性。

4.2 PLE(Progressive Layered Extraction)

CGC会显示对task-specific和shared components进行分离。然而,在deep MTL中,learning会随着越来越深的语义逐渐走形,通常对于立即表示(intermediate representations)是否应该被看成是shared或task-specific来说是不清晰的。为了解决该问题,我们使用PLE将CGC进行泛化。如图5所示,在PLE中有multi-level extraction networks来抽取higher-level的共享信息。除了对task-specific experts的gates外,extraction network也会为shared experts使用一个gating network来组合来自该layer的所有experts的知识。因而,在PLE中不同任务的参数在像CGC这样的early layer上不会完全分离,但会在upper layers上会逐渐分离。在higher-level extraction network中的gating networks会采用gates的融合结果作为selector,而非raw input,这是因为它可以提供更好的信息来选择从更高level experts中抽取到的知识。

图片名称

图5 Progressive Layered Extraction (PLE) Model

在PLE中weighting function、selected matrix、以及gating network的计算与CGC中的相同。特别的,任务k在第j个extraction network中的gating network的公式为:

[g^{k,j}(x) = w^{k,j}(g^{k,j-1}(x))S^{k,j}(x)]

…(6)

其中:

  • (w^{k,j}):是task k的weight function,它使用(g^{k,j-1})作为input,
  • (S^{k,j}):是选中task k在第j个extraction network的matrix。

值得注意的是,在PLE的shared module的selected matrix与task-specific modules非常不一样,因为它在该layer中包括了所有shared experts和task-specific experts。

在计算所有gating networks和experts后,我们可以最终获得在task k的prediction:

[y^k(x) = t^k(g^{k,N}(x))]

…(7)

有了multi-level experts和gating networks,PLE可以为每个task抽取和组合更深的语义表示来提升泛化性(generalization)。如图1所示,对于MMOE来说,routing策略是完全连接的,对于CGC来说则是早期分离的(early separation)。不同的是,PLE会采用一个progressive separation routing来从所有更低layer的experts抽取信息,抽到更高level的shared knowledge,并渐近地将task-specific参数分离出来。progressive separation的过程与此类似:从化学药品中为期望产品抽取化合物的抽取过程。在PLE的知识抽取和转换的过程期间,更低level的表示会jointly extracted/aggregated,并在更高level的shared experts上进行routed,获取共享知识和渐进地分发给特定的tower layers,以便达到更高效和灵活的joint representation learning和sharing。尽管MMOE的full connection routing看起来像是CGC和PLE的一个通用设计,在第5.3节中的实际研究表明,MMOE不能收敛到CGC或PLE的结构,尽管存在可能性。

4.3 MTL的joint loss optimization

当设计高效的网络结构时,我们接着关注于以end-to-end的方式联合训练task-specific和shared layers,一种常用的joint loss公式是:对每个单独的task的losses的加权求和:

[L(theta_1, cdots, theta_K, theta_s) = sumlimits_{k=1}^K w_k L_k(theta_k, theta_s)]

…(8)

其中:

  • (theta_s)表示共享参数,K表示任务数
  • (L_k, w_k, theta_k):分别是任务k的loss function、loss weight、task-specific parameters

然而,由于存在许多问题,在实际中对MTL models做出joint optimization很具挑战。在本paper中,我们会对joint loss function进行最优化来解决在真实推荐系统中遇到的两个问题。

第一个问题是:由于顺序的用户动作产生的不同类的样本空间(heterogeneous sample space)。例如,用户在点击一个item后只会分享或评论。这会导致如图6所示的不同样本空间。

图片名称

图6 不同任务的training space

为了联合训练这些任务,我们会考虑所有任务的样本空间的联合(union)作为整个训练集,而当计算每个任务的loss时,会忽略在它之外样本空间的样本:

[L_k(theta_k, theta_s) = frac{1}{sum_i sigma_k^i} sumlimits_i sigma_k^i loss_k(hat{y}_k^i (theta_k, theta_s), y_k^i))]

…(9)

其中:

  • (loss_k)是任务k基于prediction (hat{y}_k^i)、以及ground truth (y_k^i, sigma_k^i in lbrace 0, 1 rbrace)计算的样本i的的loss,它表示样本i位于task k的样本空间。

第二个问题是:一个MTL模型的效果对于在训练过程中loss weight的选择是否敏感【9】,因为它决定了在joint loss上每个任务的相对重要性。实际上,这会观察到:每个任务在不同的训练过程会具有不同的重要性。因此,我们会为每个task考虑loss weight作为一个动态权重(dynamic weight),而非一个static权重。首先,我们会为task k设置一个初始的loss weight (w_{k,0}),接着在每个step后基于updating ratio (gamma_k)更新它的loss weight:

[w_k^{(t)} = w_{k,0} times gamma_k^t]

…(10)

其中:

  • t表示training epoch
  • (w_{k,0})和(gamma_k)是模型的超参数

5.实验

在这部分,会在腾讯大规模推荐系统以及公开benchmark datasets上执行大量离线和在线实验来评估提出模型的有效性。我们也在所有gate-based MTL模型上分析了expert的使用,以便理解gating networks的工作机制,并验证CGC和PLE的结构。

5.1 在视频推荐上的评估

在本节中,我们会使用复杂和正常相关的任务组作为在视频推荐系统上的多个任务,来评估提出模型的效果。

5.1.1 Dataset

我们通过在腾讯新闻从视频推荐系统上抽样用户日志,收集了一个工业界dataset,它具有8天连续。它具有4.69亿用户,268w个视频,并在数据集上具有9.95亿样本。如前所述,VCR、CTR、VTR、SHR(share rate)、CMR(comment rate)是在该dataset中建模的任务。

5.1.2 Baseline模型

在该实验中,我们在单任务、asymmetric sharing、customized sharing上对比了CGC和PLE,其中SOTA MTL模型包括:cross-stitch network、sluice network,MMOE。由于multi-level experts会在PLE中共享,我们会将MMOE扩展到ML-MMOE(multi-layer MMOE),如图1所示,通过添加multi-level experts来进行公平对比。在ML-MMOE中,更高level的experts会对来自更低level的experts的representations进行组合,所有gating networks会共享相同的selector。

5.1.3 实验setup

在该实验中,VCR prediction是一个regression task,它使用MSE loss进行训练和评估;在其它动作上的任务建模都是二分类任务,它们使用cross-entropy loss进行训练,并使用AUC进行评估。在首个7天的样本会用来进行训练,其余样本是test set。对于在MTL模型和single-task模型中,对于每个task,我们采用一个3层的MLP network,它使用RELU activation和hidden layer size为[256,128,64]。对于MTL模型,我们实现了expert作为一个single-layer network,并对以下的model-specific超参数进行调参:shared layers的数目、在hard parameter sharing和cross-stitch network上的cross-stitch units,在所有gate-based模型中的experts数目。对于公平比较,我们实现了所有multi-level MTL模型作为two-level models来保持相同深度的模型。

图片名称

表1

基于公平的评估指标(比如:AUC和MSE),对于一个特定任务,我们定义了一个MTL gain的指标来量化评估多任务学习要比单任务模型的好处。如等式11所示,对于一个给定的task group以及一个MTL模型q,在任务A上q的MTL gain被定义成MTL模型q对比相同网络结构和训练样本的single-task model的效果提升。

[MTL gain = f(n) = begin{cases} M_{MTL} - M_{single}, & text{M is a positive metric} \ M_{single} - M_{MTL}, & text{M is a negative metric} end{cases}]

…(11)

5.1.4 复杂相关性的任务评估

为了更好捕获主要的在线engagement metrics,例如:view count和watch time,我们首先在VCR/VTR的任务组上开展实验。表1展示了实验结果,我们会以粗体表示最好得分,效果下降则以灰色。在VTR上,CGC和PLE可以极大胜过所有其它baseline模型。由于在VTR和VCR间复杂相关系,我们可以很明显地观察到seesaw效应,它使用zigzag灰色分布,一些模型提升VCR但会伤害VTR;而一些则提升VTR但伤害VCR。特别的,MMOE会同时提升在single-task上的任务,但这些提升是不大的,而ML-MMOE则会提升VTR但会伤害VCR。对比MMOE和ML-MMOE,CGC会提升VTR更多,提升VCR很少。最后,PLE会收全省到相同的一步,并在上述模型上达到极大的提升,它具有最好的VCR MSE,以及其中一个最好的VTR AUCs。

图片名称

表2

5.1.5 在正常相关性的任务上评估

由于CGC和PLE在处理真实复杂相关性的任务上表现很好,我们会进一步在具有正常相关性模式的CTR/VCR的一个通用任务组上进行验证。由于CTR和VCR的目标是建模不同的用户动作,在它们间的相关性更简单些。如表2所示,事实上,除了cross-stitch之外的所有模型,在两种任务上都表现出正向的MTL gain,这表明:在CTR和VCR间的相关性模式并不复杂,不会具有seesaw效应。在该场景中,CGC和PLE仍能在两种任务上极大地胜过所有SOTA模型,并具有显著的MTL gain,这验证了CGC和PLE的收益是通用的,可以有效达到更好的共享学习,并能在多个任务场景下一致提供增量的效果提升,不仅仅是那些具有复杂相关性的任务,同时也包括普通相关的任务。

图片名称

表3

5.1.6 online A/B testing

在VTR和VCR的任务组上我们进行仔细的online A/B test,达4周。我们在c++深度学习框架上实现了所有MTL模型,随机分配用户给不同的buckets,并在每个分桶上部署一个模型。最后的ranking score通过多个predicted scores的组合函数来获得(如第3节所示)。表3展示了MTL models在single-task模型上的提升(total view count per user/ total watch time per user)。它表明:对比baseline models,CGC和PLE能在online metrics上能达到极大的提升。另外,在所有在线指标上,PLE都要极大好于CGC,这表明:在MTL中,AUC或MSE上的小提升可以为在线metrics带来极大提升。PLE已经部署在tencent平台上。

5.1.7 多任务上的评估

最后,我们在多个挑战性场景上探索了CGC和PLE的可扩展性。除了VTR和VCR外,我们会引入SHR(share rate)和CMR(comment rate)来建模user feedback actions。可以很灵活地扩展CGC和PLE到多任务cases中,只要为每个task添加一个task-specific expert module、gating network、tower network即可。如表4所示,对比起single-task model,CGC和PLE几乎在所有task group上会达到极大提升。这表明CGC和PLE仍展示了促进任务协同的好处,对于超过2个任务的通用场景,仍可以阻止negative transfer和seesaw效应。PLE的效果在所有cases上都要极大好于CGC。因此,PLE展示了在跨不同sizes的task groups上提升shared learning efficiency的更强的收益。

图片名称

表4

图片名称

图7

5.2 public datasets上的评估

5.3 Expert使用分析

为了探索experts是如何通过不同gates间进行聚合的,我们在工业界dataset上的VTR/VCR task group上,研究了所有gate-based models的expert utilization。出于简洁性和公平对比,我们会考虑将每个expert看成是一个single-layer network,在CGC和PLE的每个expert module上保持一个expert,而在MMOE和ML-MMOE的每个layer则会保持三个experts。图8展示了在所有testing data上每个gate使用的experts的权重分布,其中:bars的高度以及垂直short lines分别表示weights的均值和标准差。它表明:VTR和VCR在CGC中会使用极不同的weights来组合experts,而在MMOE中则使用非常相似的weights,这表明:CGC的良好设计结构可以帮助达到在不同experts间更好的区分度。另外,在MMOE和ML-MMOE中所有experts都有非零权重,这进一步表明:对于MMOE和ML-MMOE来说,在没有先验知识的情况下,很难去收敛CGC和PLE的结构,尽管存在理论可能性。对比起CGC,在PLE中的shard experts对tower networks的input具有更大的影响,特别是在VTR任务上。实际上,PLE的效果要好于CGC,这表明在更高level上共享更深的representations的价值。换句话说,需要在任务间共享的更深语义表示,因此 一个progressive separation routing可以提供一个更好的joint routing和learning scheme。

图片名称

图8

6.

参考

youku在《Deep Time-Stream Framework for Click-Through Rate Prediction by Tracking Interest Evolution》提出了一个兴趣演进的框架。

摘要

CTR预测在像视频推荐等工业应用中是一个必要的任务。最近,deep learning模型被用来学习用户的整体兴趣表示(overall interests),然而会忽略兴趣可能会随时间动态变化的事实。我们认为:有必要在CTR模型中考虑上连续时间信息(continuous-time information)来从丰富的历史行为中跟踪用户兴趣。在本paper中,我们提出了一个新的Deep Time-Stream framework(DTS),它会通过一个常微分方程(ODE: ordinary differential equation)来引入time information。DTS会使用一个neural network来持续建模兴趣的演化,它可以来解决用户兴趣会随它们的历史行为动态表征带来的挑战。另外,我们的框架可以通过利用额外的Time-Stream Module,无缝地应用到任意deep CTR模型上,对原始CTR模型不会做任何变改。在公开数据集的实验、以及工业数据集的表现看,可以达到很好的效果。

介绍

CTR预测目标是估计一个用户在一个给定item上的概率,在学习界和工业界这是一个备受关注的问题。以在线视频为例,一个CTR算法会提供给用户数千个不同类目的视频,因此,精准捕获用户的兴趣很重要,可以提升用户的留存和收益。

为了达到该目标,基于用户历史点击进行建模用户兴趣会影响用户偏好。为了抽取用户兴趣的表示,提出了许多传统模型、以及deep模型。尽管这些模型在建模用户整体兴趣时达到了极大成功,它们会忽略用户兴趣的动态变化。为了进行一个更精准的结果,RNN-based方法提出捕获在user-item interaction序列中的依赖。然而,这些方法只考虑用户行为的顺序,忽略在行为间的时间间隔(time interval),它对于预测用户行为是很重要的信息。在图1中,作为示例,Mike通常会在白天观看关于Donald Trump的视频,在晚上享受Taylor Swift的音乐视频,根据他的行为的timestamps。因而,将Mike的playlog看成一个点击视频序列,会忽略他的潜在兴趣随时间的变化。不幸的是,现有的CTR模型不能建模在连续时间上的模式,因为大多数模型不知道时间间隔(time interval)。

图片名称

图1

另外,在inference阶段,只预测下一次点击(next click)而不考虑执行action时的时间会有问题。将用户行为的时间合并进去,比如:建模在行为间的逝去时间间隔(elapsed time interval)的效果,这对于精准建模用户兴趣非常重要。例如,在图1中,如果Mike在9 p.m.(下午)观看了Taylor的视频,很可能他会在几小时内观看另一个Taylor的视频(而非Donald),而在半天后观看Donald的视频概率会更大些。然而,传统方式总是在任意时刻上获得相同的精准预测。

基于前面的观察,我们认为在CTR模型上考虑上time-stream信息(比如:连续时间信息:constinous-time info)很重要。因此,我们提出了一种新的Deep Time-Stream framework(DTS),它会将time-stream信息引入到CTR模型中。因此,我们提出了一种新的Deep Time-Stream框架(DTS)。Time-stream信息可以通过常微分方程(ODE)进行公式化,它指的是一个描述在依赖变量的导数和独立变量间的关系的函数。特别的,DTS会使用ODE来建模用户潜在兴趣的演化,它会将用户在兴趣状态随时间进行求导参数化,比如:ODE的解会描述用户兴趣的动态演化。另外,DTS会具有以下能力:统一在time-stream(通过点击的timestamp进行)上的用户历史行为(已点击什么)和target items(将点击什么),因而根据给定的下一时间(next time)做出inference,并提供一个更加精准的CTR预测。为了达到最小的模型变更代价(model-altering cost),ODE会被打包成一个Time-Stream Module,它可以应用到任意的deep CTR模型上。该paper的贡献如下:

  • 提出了一个新的DTS框架,会将用户的latent interest evolution建模成一个ODE,它会极大提升模型的表达能力,可以更好地捕获用户兴趣的演进
  • DTS可以在任意时间生成用户的feature,因而对于适配评估很灵活
  • Time-Stream Module可以轻易地转成已存在的CTR模型,无需对原始框架做变化

1.背景

在机器学习中,有效管理一类hypotheis(线性或非线性),可以表示data patterns。ODEs可以被用于一个hypothesis。考虑在(R^d)中的微分方程:(frac{dz}{dt} = f(z, t), z(0)=z_0),z在time t上的解被定义成(z(t))。在监督学习中的ODE方法背后的基本思想是,调整f,使得z(t)可以生成拟合该数据所需的非线性函数。

实际上,Chen 2018的DNN被看成是discrete ODE,他们的迭代更新可以被看成是关于一个连续转换(continuous transformation)的Euler discretization。在另一方面,neural ODEs是一组DNNs模型的family,可以被解释成一个关于ResNets或RNN的continous等价。为了观察该现象,我们会将在ResNets或RNNs中的一个layer t到t+1的hidden state看transformation看成是:

[h_{t+1} = h_t + f_t(h_t)]

…(1)

在ResNets中,(h_t in R^d)是在layer t的hidden state;(f_t: R^d rightarrow R^d)是一个差值函数(differentiable function),它会保留(h_t)的维度。在RNNs中,(h_t in R^d)是第t个RNN cell上的hidden state,它更新时会抛出一个函数(f_t: R^d rightarrow R^d)。(h_{t+1} - h_t)的差可以看成是一个在timestep (Delta t = 1)上的导数(h'(t))的离散化(discretization)。假设:(Delta t rightarrow 0),我们可以看到:动态的hidden state可以通过一个ODE进行参数化:

[underset{Delta t rightarrow 0}{limit} frac{h_{t+Delta t} - h_t}}{Delta t} = f(h, t)]

z(t)的解或h(t)可以使用一个ODE solver进行求解,会使用许多复杂数值方法来选择:比如:linear multi-step方法、RUnge-kutta methods或adaptive time-stepping。以上方法在deep learning中很有用,因为他们可以自适应地选择network的layers。这里要注意的不是solver本身,而是数据的表示。因此我们将solver看成是一个黑盒的differential equation solver:

[z_{t_1}, ..., z_{t_N} = ODE_{solver}( z_{t_0}, f, theta_f, t_1, cdots, t_N)]

…(2)

其中,(theta_f)是关于f的参数。

在下一节中,我们会展示,ODEs是如何被用来建模用户兴趣演化的动态性的,以及如何让ODEs在训练时能够稳定。

2.Deep Time-Stream Framework

在本节中,我们会描述DTS。首先将CTR公式化成一个二分类问题。给定数据样本:

[x = (x^U, x^V, x^P) in X]

其中: ((x^U, x^V, x^P))分别表示来自User behavior、target Video以及user Profiles这些不同字段的one-hot vectors的concatenate。

再者,每个字段包含了一个关于点击行为的列表:

[x^U = [(v_1, c_1); (v_2, c_2); cdots; (v_N, c_N)]]

其中:

  • (x_i^U = (v_i, c_i))表示发生在time (t_i)的第i个行为上
  • video (v_i)以及相应的category (c_i),其中N是user的历史行为的数目;
  • (x^V)表示target video和它的category (x^V = (v_{N+1}, c_{N+1})),等式的成立是因为:target video会随着第(N+1)的用户点击而发生,potential click的预测时间被看成是next time (t_{N+1})。

因而,我们会统一在time stream上的用户历史行为和target video,通过timestamps来表示t:

[t = [t_1, t_2, cdots, t_N, t_{N+1}]]

User Profile (x^P)包含了有用的profile信息,比如:gender、age等。Label (y in Y)表示用户是否点击是指定的视频,(y=1)表示点击,(y=0)表示未点击。CTR的目标是学习一个从X到Y的mapping (h in H),其中,(H)表示hypothesis space,(h: X rightarrow Y)表示预测用户是否将点击该视频。预测函数h可以通过以下objective function进行最小化学到:

[underset{h}{min} sumlimits_{(x,y) in X times Y} L(h(x;t), y)]

…(3)

其中,L是epmirical loss,它会在以下子部分引入。

2.1 通用框架

我们提出的框架DTS可以看成是一个Base-Model加上Time-Stream Module,如图2所示。BaseModel被看成是一个已经存在的deep CTR模型,比如:DNN,PNN,DIN等。除了base model外,Time-Stream Module会收集所有events的timestamps,包括:一个用户在过去的历史点击时间、以及在预测时的用户潜在点击时间。注意,后半部分在已存在的CTR模型中会被忽略。另外,Time-Stream Module会通过一个ODE来跟踪潜在兴趣演进,来计算一个增强型输入(enhanced input),它会引入continuous-time信息,并保留base inputs的维度。因此,在DTS框架中,任意的deep CTR模型可以被用于BaseModel,无需做任何更改。对比BaseModel,它会输入在用户点击item事件上的一个点击概率,DTS可以通过在给定时间上用户点击item事件的点击概率,从而对output做出提升。

图片名称

图2

在面,我们会介绍BaseModel,并引入Time-Stream Module来捕获兴趣,并建模兴趣演进。

2.2 BaseModel

2.3 Time-Stream Module

用户兴趣会随时间动态变化。BaseModel会通过一个在点击item feature上的pooling操作获取一个表示向量,但会忽略时间信息。动态pattern的缺失会限制用户行为特征的能力,这对于建模用户兴趣很重要,因为用户点击items是一个用户在对应时间上对兴趣的表示。对于BaseModel,如果对continous pattern的能力缺失会导致在建模动态用户兴趣时的inaccuracy。

是否存在优雅的方式来表示一个用户的real-time兴趣,并建模动态兴趣演化的pattern?continous-time evolving激发我们设计了一个称为Time-Stream Framework的方法,它会利用ODE来建模动态兴趣。ODE在物理、生物、化学、工程和电子领域被广泛应用,如果ODE可解,会给出一个初始点(initial point),它可以决定所有它的future positions,这些points被称为“trajectory或orbit”。本文中我们使用ODEs作为hypothesis class,其中trajectory表示一个潜在的兴趣演化轨迹(lantent interst evolution trace)。在等式1中,ODE可以是通用的RNNs形式,RNNs可以被认为是continuous ODE的一个离散版本。continous ODE具有一些优点,比如:评估很灵活,相应的可以自适应地选择RNN的长度。另外,我们也可以使用高级数值方法来训练,比如:multi-grid方法、parallel shooting方法。图3展示了Time-Stream Module的架构。

图片名称

图3 Time-Stream Module的结构。DTS会保持BaseModel的基本框架,可以继承原先的效果。另外,DTS会扩展Time-Stream module,将latent time state (z_t)建模成一个ODE。Decoder (phi)会将(z_t)映射到embedded space,并混合上embedding来增强embedding的quality。Guide loss被设计用来帮助hidden state的收敛

为了通过ODE的一个latent trajectory来表示兴趣演进,会使用一个可微函数,(frac{d z(t)}{dt} = f(z(t), t; theta_f))来表示兴趣演化率,其中:(theta_f)是关于f的参数。因此,给定一个initial state (z_{t_0}),ODE的trajectory可以使用等式(2)提到的一个solver来进行求解:

[z_{t_1}, cdots, z_{t_N}, z_{t_{N+1}} = ODE_{solver}(z_{t_0}, f, theta_f, t_1, cdots, t_N, t_{N+1})]

…(5)

其中,(z_{t_1}, cdots, z_{t_N}, z_{t_{N+1}})是ODE的解,它可以描述dynamics f在每个观察时间(t_1, cdots, t_N, t_{N+1})的latent state。由于相似的人可能会有相近的兴趣兴趣演进pattern,我们会构建一个mapping g,它可以将user profile embedding (e^P)转化成latent time-stream space来获取initial value:(z_{t_0} = g(e^P; theta_g)),mapping g是一个具有参数(theta_g)的线性转换,它会当成是一个将profile embedding space转化latent time-stream space的encoder。

另一方面,(phi)是一个decoder,它可以将latent time-stream feature (z_{t_i})转成video embedding-spaned space。(phi(z_{t_i}; theta_{phi})是behavior feature的adujstment或supplementary,它可以携带额外的行为演化patterns。 对于user behavior feature的adujstment,我们有:(bar{e_i} = e_i + phi(z_{t_i}; theta_{phi})),其中:(i=1, 2, cdots, N)。fuse operation可以被设置成像concatenation的operation,但在本工作中,add操作会被用来保证adujstment以及original feature具有相同贡献。对于target video feature,我们有:(bar{e}^V = e_{N+1} + phi(z_{t_{N+1}; theta_phi))

增强行为特征(enriched behavior feature) (bar{e}^U = (bar{e}_1, bar{e}_2, cdots, bar{e}_N)),video vector (bar{e}^V)和profile feature (e^P)会接着被发送到Base CTR模型的其余部分。

使用ODE作为一个generative model,允许我们在任意时间做出预测,不管是过去或是将来,因为在timeline上是连续的。ODE的output可以通过一个黑盒的差分等式solver进行计算,它会来评估hidden unit dynamics是否需要来决定有期望的accuracy的solution。

function f的选择

latent function f需要被指定,使用不同类型的函数来满足不同需求。接着,我们会引入一些方法来利用不同类型的ODE function f来建模intrest evolution的过程。

Simple form

function f的最简单形式是,f是一个关于独立变量t的函数:

[f(z, t) = frac{dz}{dt} = A(t), z(t)=int_{t_0}^t A(lambda) d{lambda} +C]

…(6)

其中,A是control function,C是一个constant。该类型的问题可以通过直接计算z(t)具有一个解析解。如果这样,数值形求解ODE不存在额外开销。一个特例是具有常系数的linear differential equation (f(z, t) = A(t) = alpha),它意味着在rate (alpha)时有latent state discount。因此,对于所有的t会有(z_{t_i} = alpha (t_i -t_0) + z_{t_0})。这里的看法是,f的单调trajectory会模拟用户兴趣的特性:主要被最近兴趣所影响,因此会减小较早兴趣的影响,并增加用户最近行为的影响。特例相当简单,但在实验中达到很好的效果。

复杂形式

f的简单形式不能表达用户diverse的time-searies的pattern。为了解决该限制,另一个选择是:使用一个neural network参数化dynamics f的导数,它可以极大提升模型的表示能力。在本paper中,会使用一个带sogmoid activation unit的双层neural network:(f(z) = sigmoid(w_2 cdot sigmoid(w_1 cdot z + b_1) + b_2))

其中:(w_1, w_2, b_1, b_2)是线性参数,(sigmoid(cdot))是activate unit。在该形式下的f很难获得一个解析解 ,在(z_{t_1}, cdots, z_{t_N}, z_{t_{N+1}})下的解可以使用一个数值形ODE solver来计算。

Guide Loss

前面的函数在单次调用ODE toolbox上可以被求解,现代ODE solvers会在approx error的增长上会有保障。然而我们有以下需要注意的事项:

1) 当function形式变得复杂时,ODE的行为可能会遇到expolodes的情形,收敛到稳态或者展示混乱行为。这可以解释一些难点:比如:在DNN训练中遇到的梯度vanishing或explosion。

2) 另一方面,由于target item的行为会由用户兴趣演进所触发,该label只表示(z_{t_{N+1}})的最后点击行为,而历史state (z_t)不会获得合适的监督(supervision)。

为了缓解这些问题,我们提出了guide loss,它会使用behavior embedding (e_i)来监督latent function的学习。为了这样做,受word2vec的启发,我们构建了一个小网络,它会将decoded hidden state (phi(z_{t_i}))推至更接近下一行为(e_{i+1}),而非一个随机负采样实例(e^{rand})。Guide loss可以公式化为:

[L_{guide}(p,v,n)=- frac{1}{N} sum_i (v_i cdot p_i + v_i cdot n_i - log(frac{v_i cdot p_i}{v_i cdot n_i})) \ p_i = FC(e_{i+1}), v_i = FC(phi(z_{t_i})), n_i = FC(e^{rand})]

其中,FC(x)是一个将PRelu作为activation的fully connected layer。模型的整个loss如下:

[L = L_{target} + lambda L_{guide}]

…(7)

其中,L是overall loss function,(L_{target})由等式(4)引入,(lambda)是hyper-parameter,它会对兴趣表示和CTR预测进行balance。

整体上,guide loss的引入有一些优点:

  • 1) 从兴趣学习的角度,guide loss的引入会帮助ODE的每个hidden state更丰富地表示兴趣
  • 2) 对于ODE的最优化,当ODE会建模长历史行为序列时,guide loss会减小BP的难度
  • 3) 对于embedding layer的学习,Guide loss会给出更多语义信息,这会产生一个更好的embedding matrix

training和inference

在训练阶段,我们的模型会具备重新加载BaseModel参数的能力。接着,所有weights会进行finetuned来获得一个快速收敛。我们会通过初始化f的参数以及初始值为0来达到一个safe-start,比如:ODE的trajectory是一个0常数。这样,在训练的开始,整个模型会与original CTR base model保持相同。

在inference阶段,我们可以在任意的推荐时间(t_{N+1})来预测用户兴趣演进,因为我们会利用ODE solver来在下一时间(t_{N+1})来集成f的函数。在工业界,DTS会更有效:当预测在(t_{N+1}, t_{N+2}, t_{N+n})的多个CTR时,没有必要从头计算hidden trajectory。很容易集成从(t_N)到(t_{N+n})的function,它们的计算很cheap。

4.实验

参考

youku在《Multi-objective Optimization for Guaranteed Delivery in Video Service Platform》提出了一种方法:

1.介绍

2.相关工作

3.内容的曝光分配模型

在本节中,首先给出内容的保量分发策略的一些概念:

3.1 前提

我们只考虑需要GD策略的抽屉或者模块(drawers),它被表示为:

[S = lbrace s_j, j in Z_n rbrace]

其中:

  • (Z_n)表示从1到n的整数集合

在drawer (s_j)的位置集合被表示为:

[D_{s_j}=lbrace d_{jk}, j in Z_n, k in Z_{Theta(s_j)}rbrace]

其中:

  • (Theta_{s_j})表示在drawer (s_j)的位置数目

假设需要考虑在这些drawer的内容集合被表示为:

[Q=lbrace q_i, i in Z_m rbrace]

其中:m是内容数目

在每个位置(d_{jk})的整体天级PV限制被表示为(C(d_{jk}))。不失一般性,后面章节,我们将PV value表示为x,将CLICK value表示为y

考虑到每个drawer和position的资源容量(resource capacity),以及每个内容的CTR趋势,我们的目标是:为每个内容发现合适的天级PV,它可以最大化整个频道的VV,同时尽可能避免”过曝光(over-exposure)”和“欠曝光(under-exposure)”。因此,GD策略的主要问题是:给定一个内容的PV value x,我们估计它的click value值y。正式的,点击预估模型是一个”mapping”函数,它可以根据历史天级PV和CLICK数据来学到相应的patterns,并能预测一天的click value。

3.2 pv-click-ctr预估模型

每个内容的CTR趋势(trend)涉及到许多因素,很难对这些因素枚举并基于它的历史数据进行模型构建。因而,我们从其它视角对该问题进行研究。

总的来说,点击来自于曝光。在大多数case下,越多的曝光会带来越多点击数。然而,每个内容的目标消费者的总数目是有限的。当曝光量过大时,对同一消费者进行重复曝光在统计上不能带来更多的点击。这种“饱和”现象可以在我们的产品中通过历史数据观察到,这与经济学系统中的人口模型相似。受[13]的启发,我们引入一个参数化模型(parametric model)来捕获以上的观点。

特别的,假设:

  • y(x)表示点击值,它与在一天内某一内容的一个PV value x一一对应
  • (Delta x)是PV增量
  • (Delta y)是对应于(Delta x)的点击增量
  • r是相对增长率系数。不同内容的相对增长率是不同的,因为它主要依赖于内容质量

如果PV值x很小,我们可以将CLICK增长率看成是与PV成比例关系,因为越多的曝光通常会带来越多的点击:

[frac{y(x+Delta x) - y(x)}{Delta x} approx r * y(x)]

…(1)

然而,当PV value x很大时,点击会具有“饱和”效应,增长率会递减。正式的,它可以写成:

[frac{y(x+Delta x) - y(x)}{Delta x} < 0]

…(2)

与paper[13]相类比,我们使用一个关于y(x)的线性递减函数,来描述“饱和”效应,例如:

[frac{y(x+Delta x) - y(x)}{Delta x} = r(1 - frac{y(x)}{y_m}) y(x)]

…(3)

其中,(y_m)被称为中心点击值(pivot CLICK value)。当PV超过对应于(y_m)的PV量时,相对增长率会为负,例如:如果(y(x) > y_m, 1-frac{y(x)}{y_m} < 0)。其中,r和pivot CLICK (y_m)是核心content-based参数,表示内容的属性。

假设:(Delta x rightarrow 0),那么等式(3)将是一个在CLICK和PV值间的ODE常微分方程模型:

[frac{dy}{dx} = r ( 1 - frac{y}{y_m}) y]

…(4)

等式(4)的解为:

[y = frac{y_m y_0}{y_0 - (y_0 - y_m) e^{-r(x - x_0)}}]

…(5)

其中:

  • (x_0)和(y_0)表示初始PV和初始CLICK。

如果(y_0 < y_m),CLICK value会增长,随着(x rightarrow infty)时会渐近逼近(y_m);如果(y_0 > y_m),CLICK value会递减;随着(x rightarrow infty)会远离(y_m),事实上(y = y_m)是等式(4)的等价。因而,(y = y_m)的均衡点(equilibrium)。因而,等式(4)的正均衡点(y=y_m)是全局稳定的,也就是说,对等式(4)的y(x)求解(lim_{n rightarrow infty} y(x) = y(m)),其中任意初始值(x_0)。

为了描述每个视频内容的CTR趋势,在等式(5)中的参数r和(y_m)需要通过历史PV和CLICK数据进行填充。我们将所有内容相关的因子归属为这些参数,期望它们来表示内容自己的CTR趋势。我们使用least square fitting方法来估计这些参数。

3.3 曝光分配公式

基于3.2节提出的pv-click-ctr预估模型,该子部分目标是,开发一个最优化程序模型来解决PV分配问题。假设:

  • (x_{ijk})表示内容(q_i)从位置(d_{jk})获得的PV value
  • (f(x_{ijk}))是对应于(x_{ijk})对应的CLICK value,它可以使用等式(5)进行计算

我们的目标是:最大化总视频观看数(video views: VV),并通过最优化(x_{ijk})来最小化CTR variance。通过分析最优化目标和约束,分配问题可以被定义如下:

[max sumlimits_{i=1}^m sumlimits_{j=1}^n r_{ij} f(x_{ijk}), k in Z_{Theta(s_j)} \ min frac{sumlimits_{i=1}^m (p_i - P)^2}{m - 1} \ p_i = frac{sum_{j=1}^n f(x_{ijk})}{sum_{j=1}^n x_{ijk}}, forall i in lbrace 1, 2, cdots, m rbrace, forall k in Z_{Theta(s_j)} \ P = frac{sumlimits_{i=1}^m sumlimits_{j=1}^n f(x_{ijk})}{sumlimits_{i=1}^m sum_{j=1}^n x_{ijk}}, forall k in Z_{Theta(s_j)}]

….(6)(7)(8)(9)

约束条件为:

s.t.

[sumlimits_{i=1}^m x_{ijk} < C(s_j), forall j in lbrace 1, 2, cdots, n rbrace, forall k in Z_{Theta(s_j)}]

…(10)

[sumlimits_{i=1}^m sum_{j=1}^n x_{ijk} < R, forall k in Z_{Theta(s_j)}]

…(11)

[x_{ijk} < max lbrace C(d_{jl}), l in Z_{Theta(s_j)} rbrace, \ forall i in lbrace 1,2, cdots, mrbrace, forall j in lbrace 1,2, cdots, nrbrace, forall k in Z_{Theta(s_j)}]

…(12)

[|C_{jk}| leq k, C_{jk} = lbrace x_{ijk} | x_{ijk} geq C(d_{jk}), 1 leq i leq m rbrace, \ forall j in lbrace 1, 2, cdots, n rbrace, forall k in Z_{Theta(s_j)}]

…(13)

其中:

  • (r_{ij}):是对于内容(q_i)在drawer (s_j)中CLICK和VV间的正相关系数
  • (C(s_j)):是drawer (s_j)的总PV资源数
  • R:是drawer set S的总可供资源数

等式(6)的最优化目标是在所有drawers上最大化总VVs。其它最优化目标是,在最小化等式(7)-(9)描述的的不同内容间的CTR variance。

  • 等式(10)描述的约束意味着:内容集合Q在drawer (s_j)中的资源分配不能超过它的资源容量(capacity)
  • 等式(11)表示drawer set S的资源约束
  • 等式(12)是位置资源约束,它表示资源分配给在任意drawer中的一个内容,不能超过它的最大位置资源容量
  • 等式(13)可以确保它们必须是一个drawer的一且只有一个位置分配给一个内容,也就是说:我们不能在相同时间展示相同内容给用户。

4.GA-based内容分配算法

为了获得在第3节中建模的分配问题的最优或次优解,提出了一个遗传算法(Genetic Algorithm)GA分配算法,它是一个迭代算法,其中会嵌入pv-click-ctr预测模型。

注意,等式(6)-(13)中表示的PV分配问题,对应于一个多目标约束优化问题(MCOP: Multi-objective Constrained Optimization Problem),它的最优解是很难找出的。通常,一个MCOP可以通过加权法( weighting)被转化成一个单目标最优化问题,接着PV分配问题定义如下:

[max g(X | lambda) = sumlimits_{i=1}^m sumlimits_{j=1}^n r_{ij} f(x_{ij}) + lambda frac{1} {frac{sumlimits_{i=1}^m (p_i - P)^2}{m-1}} \ p_i = frac{sumlimits_{j=1}^n f(x_{ij})}{sumlimits_{j=1}^n x_{ij}}, forall i in lbrace 1,2, cdots, m rbrace \ P = frac{sumlimits_{i=1}^m sumlimits_{j=1}^n f(x_{ij})}{sumlimits_{i=1}^m sumlimits_{j=1}^n x_{ij}}]

…(14)(15)(16)

[s.t. X in Omega]

…(17)

其中:

  • (lambda)表示weight参数
  • (Omega)是等式(10)-(13)描述的决策(变量)空间
  • (g(X mid lambda))是目标函数

应该注意的是,通过等式(14)-(17)建模的分配问题是一个组合优化问题,并且它是非线性和非平滑的。组合优化问题是,它的可行解集合是离散的。该问题是NP-hard完全问题,它在多项式时间内全局最优的求解是相当难的。像branch和bound的搜索算法可以退化成完全枚举,并且CPU时间需要求解,可能会在最坏情况下指数级增长。为了实际求解这样的问题,必须合理的满足寻找好的近似最优解。作为搜索一个近似最优解的经典算法,GA提供了一个可选的方法。不同于通用的GA,我们提出的GA框架包含了以下主要两个部分:

  • coding scheme考虑上ODE约束
  • 本地搜索操作(带elitist策略的选择、交叉和突变)

4.1 Coding Scheme和ODE-based Fitness

根据GA的常用框架,对于分配问题的解是一个染色体(chromosome)或个体(individual)。特别的,在我们问题中的chromosome是一个矩阵,其中,elements是从drawers的相应位置分配的PV value。chromosome会以两步生成:

  • 1) 对于任意内容(q_i),会生成一个关于PV values的排列(x_i = [x_{i,1}, x_{i,2}, cdots, x_{i,n}]),其中(x_i)的长度为n
  • 2) 对于不同内容合并所有的排序,是为了形成关于chromosome的最终形式(X= [x_1, x_2, cdots, x_m])

在GA中,每个个体(individual)的fitness函数的值,例如(fitness),是与生存者(survival)的概率是高度相关的。高fitness的个体相对于整体人口来说具有一个被选中进行交配(mating)的高概率,而低fitness个体具有一个相应的被选中低概率。特别的,在该问题中的个体X的fitness函数等于在等式(14)中定义的目标函数。需要注意的是,等式(14)的主要部分是(f(x_{ij}))。如上所述,(f(x_{ij}))是一个对应于PV value (x_{ij})的CLICK value,它可以通过第3.2节提到的pv-click-ctr模型来获得。假设个体X的fitness函数是F(X),假设:(U=lbrace u_1, u_2, cdots, u_l rbrace),以及(V=lbrace v_1, v_2, cdots, v_lrbrace)分别表示历史天级PV数据和CLICK数据的集合。由于在等式(4)中定义的两个参数通过使用U和V的数据进行fit,假设(l geq 4)。对于一个PV value (x_{i,j} in X),寻找一个element (u_k in U)如下:

[u_k = argmin || u_{bar{k}} - x_{i,j} ||, u_{bar{k}} in U]

…(18)

根据等式(3),我们可以获得(x_{i,j})的一个相应CLICK value:

[f(x_{i,j}) = v_k + r(1 - frac{v_k}{v_{max}}) v_k(x_{i,j} - u_k)]

…(19)

其中,r和(v_{max})是通过将来自U和V的数据作为input来fit的参数。接着根据等式(14),fitness function F(X)可以获得:

[F(X) = g(X|lambda)]

…(20)

4.2 Elitist策略的局部搜索操作

局部搜索操作(local selection operation)涉及到一系列操作,比如:选择(selection)、突变(mutation)、交叉(crossover)。主要目标是,继承高质量基因到下一代中,并进一步提升计算效率以及全局收全敛的概率。

在选择阶段,我们会使用elitism策略来保留“好”基因到下一代中。具体的,假设(X_u^k)是在第k代的个体,下一代对应(X_u^k)如下:

[X_i^k =]

…(21)

这意味着,我们只要保留具有高fitness value的个体到下一代即可。

交叉操作会随机将高质量个体的基因片段进行随机交叉。交叉概率的范围推荐0.4-0.99. 我们使用Order Crossover(OX) strategy。

突变(mutation)操作在GA中具有探索效应,这被期望可以达到大概率的全局最优。通过突变操作,一个新的染色体会通过在交叉之后在染色体中变更某些基因的编码来生成。为了确认人口演进的稳定性,突变概率通常会设得更小的值。本paper使用一种自适应突变概率,如下所示:

[p_m =]

…(22)

其中(p_{max})和(p_{min})表示最大和最小突变概率,其中在本paper分别采用0.05和0.01. F是fitness function,(F_{max})和(F_{avg})是对于当前人口的fitness function的最大值和平均值。

5.实验

参考