yahoo在2019年《Soft Frequency Capping for Improved Ad Click Prediction in Yahoo Gemini Native》提出了Soft Frequency Capping的技术。我们来看下：

1.介绍

yahoo的本地广告市场(native ad marketplace)（称为“Gemini native”）会提供给用户相应的广告：通过周围的本地内容进行重组后进行渲染（如图1所示）。对比搜索广告市场，用户意图通常是未知的。5年前启动，现在操控着每天数十亿美金的运行率，Gemini native是Yahoo的主要业务之一。每天超过20亿次曝光，数十万的active ads的库存，该市场会执行实时GSP（generalized second price）竞拍，会考虑：广告定向（ad targeting），预算考虑，频控规则（frequency）和近因原则(recency rule)，以及服务等级协议SLA（或latency）小于80ms的超过99%。

为了对在CPC价格类型特定context下的一个用户对本地广告进行排序，会为每个广告计算一个score（或expected revenue）：通过将广告主竞价 乘以 pCTR来得到。尽管Gemini native会处理其它价格类型，比如：oCPC，本文主要关注CPC价格类型。

pCTR会通过使用周期更新的模型“OFFSET”来计算：它是一个A feature enhanced collaborative-filtering (CF) based event-prediction algorithm。OFFSET是一个one-pass算法，它会为每个新的mini-batch的logged data使用SGD-based的学习方法来更新它的latent factor model。OFFSET的实现使用map-reduce架构，其中每个新的mini-batch的logged data会被预处理，通过许多mappers进行并行解析，模型实例的持续训练会通过多个reducers并行完成。

OFFSET通过他们的特征（age、gender、geo等）来表示它的用户，其中每个feature value（对于性别有：female、male或者unknown）通过一个latent factor vector（LFV）进行表示。一个用户的LFV通通应用一个non-linear function，它允许pairwise feature的依赖。由于OFFSET是一个user-less模型，一个特定用户观看一个特定广告（或frequency feature）的次数不能仅仅通过记录下来的曝光进行捕获。另外，frequency即不是一个user feature，也不是一个ad feature。因此，为了阻止用户重复观看同一个广告，基于硬频率捕获（HFC：hard frequency capping）的规则会在ad ranking过程被用于serving系统中。总之，用户在预定义的周期内观看一个ads超过预定义次数，会从ranked list中移除，不允许参与竞价。

从观测看，展示CTR会随着重复ad观看次数下降（15、17），在本工作中，我们会考虑一种新方法：通过模型将它看成是一种user-ad feature来处理频次。根据该方法，称为（SFC：soft frequency capping），对于每种曝光，frequency feature会通过user-ad pair进行计算，并用于训练一个frequency weight vector作为OFFSET SGD的一部分。在serving时，会根据incoming impression的frequency feature挑选合适的weight，并叠加到OFFSET score上。正如我们所见，frequency weight vector，产生的pCTR会随着frequency递减，表示用户对于重复观察相同的ads会厌倦。提出的方法在离线和在线评估上，对比SFC和HFC，表现出一个令人吃惊的效果提升。特别的，我们在在线实验服务真实用户时，获得一个7.3%的收益提升。SFC会增强OFFSET model，传到真实生产中，它会服务所有的Gemini native流量。我们也提供了关于frequency feature的统计，展示了不同人群在点击趋势。总之，在许多setting中会观察到“user fatigue（用户厌倦）”，因为CTR会随着频率特征的增加而递减。在许多特定的observation reveal中，男性和妇性用户体验相似的ad fatigue patterns，在观察5次广告后，在age group 50-60的群体上比group 20-30的群体的fatigue的两倍。

。。。 略

2.背景

2.1 Gemini Native

Gemini native是Yahoo主业务之一，。。。。

2.2 OFFSET Click-Prediction算法

Gemini native模型的算法是OFFSET：a feature enhanced collaborative-filtering (CF)-based ad click-prediction algorithm[2]。对于一个给定用户u的pCTR和一个ad a，会有：

…(1)

其中：\(\sigma(x) = (1+e^{(-x)})^{-1}\)是sigmoid function，

4.FREQUENCY FEATURE

Yahoo users的日志活动会包括native ad impressions，从中我们可以抽取和计算frequency，例如：一个指定用户在一个预定义周期内看到一个特定ad的次数。我们可以计算每个ad featrure的frequency（例如：创意广告、campaign、或advertiser）。因此，在设置后，ad feature \(A_f\)、时间周期\(T_f\)，我们可以提供每个user u以及每个ad a相应的frequency featrue \(f_{u,a}(A_f, T_f)\)（或者简单些：\(f_{u,a}\)）。注意，通过定义，frequency feature是一个非负整数\(f_{u,a} \in N^{+}\)。

示例：假设user u看了三个广告\(a_1, a_2, a_3\)，每个ad \(a_i\)具有ad features：advertiser \(Ad_i\)、campaign \(C_{a_i}\)，creative \(Cr_i\)，另外，假设这是在星期六晚上，刚好在午夜后，user u的Gemini native在最近一周的天活动日期如表1所示（从左到右）。下面给出了不同settings下的frequency feature的一些值：

5.统计与观察

在该节，我们提出一些关于frequencey的统计和观察。最重要的，我们展示了，frequency feature是很重要的，它对CTR具有重要影响。我们聚合了30天内的统计。它包括数十亿impression和clicks。我们注意到，当SFC方法包含在OFFSET中时，这里所使用的data会被收集，用于服务所有流量。

Global view（全局视角）

在图3中，平均归一化CTR，曝光数 CDF（cumulative density function），一个特定用户关于一个特定广告的观看数v（或frequency）会绘制成关于曲线。注意：v=0意味着，在这些曝光中，用户从未观看过在这之前的广告。 对于v次views的测算，normalized CTR可以通过除以average CTR来计算；对于v=0 （之前无views），可以通过平均CTR进行测算：

注意，在两个曲线上，最后一点包括了对于v>=50以上所有聚合的measurements。

从图上检查，可以做出许多observations。我们抛开异常点v=25，CTR会随着观看次数（频次）进行单调递减。特别的，在只有单一past view之后，平均CTR会以20%下跌，在7次views之后几乎有50%。这是个很清晰的证据表明：用户被展示相同广告多次后的快速厌倦。然而，CTR下降率会随着views次数递减，并且曝光数会随着frequency递减（忽略最后一个点，它包含了v>=50以上的所有曝光）。特别的，47%的曝光是之前从未看过的广告（v=0），对于见过一次的广告（v=1）只有10%，见过两次的广告（v=2）只有6%。

性别视角（Gender view）

在图4中，normalized CTR和曝光CDF会为男性、女生、未知性别的frequency函数进行给制。Gemini native流量对于表2中的每种性别都是共享的。令人吃惊的是，男性用户要比妇性用户多。性别不确定是因为注册用户未标注性别。曝光CDF曲线会提供后续支持，70%的未知用户曝光是之前从未见过的广告（v=0），而男性、女性只有40%这样的曝光。

如图所示，我们注意到frequency在男性、女性用户上具有相同的效应，具有几乎相同的厌倦模式。然而，未知用户行为却很不同，对于广告重复次数具有更高的容忍度。对于这些用户的这样行为的一个合理解释是，这些用户很可能是未注册用户，到达Yahoo时，来自外部搜索或社交媒体网站，比起注册用户来说具有一个相当不同的体验。

图4

年龄组视角（Age group view）

类似。

Yahoo vertical view

6.我们的目标

采用一种soft frequency capping方法，通过将frequency fearure包含到OFFSET模型中。提出的解决方案，对比起HFD可以被优化来提供最佳的offline和online效果。

7.SOFT FREQUENCY CAPPING

总览， frequency feature可以是一个特定用户在某个预定义时间周期\(T_f\)（例如：last day、last week、last month）内对某个特定ad feature \(A_f\)（创意creative、广告campaign、广告主advertiser）的。

总之，我们将frequency feature看成是一个user-ad feature，其中我们会学习一个frequency weight vector(s)，对应于一个预定义的weights category参数\(W_c\)，它决定了我们是否具有单个全局的vector 或对于每个campaign or 每个advertiser具有一个独立的vector。

特别的，对于每个incoming train事件 {(u, a, y, t)}，feature value \(f_{a,u}(A_f, T_f)\)会进行分箱操作（binned），乘以合适的frequency weight vector的对应entry，并加上OFFSET score。frequency weight vectors会通过SGD使用user和ad features进行学习，label 为y（click或skip）。在serving time中，frequency weight vectors被用作OFFSET model的一部分来计算pCTR，并用于竞价。

公式描述

SFC方法如算法1描述。

为什么要binning？作为binning based方法的另一种选择，我们会使用一个线性回归来进行additive frequency weight：

其中，\(c_a\)是一个weight，它可以被全局学到，每个campaign、或每个advertiser均有，\(g(\cdot)\)是一个arbitrary function。使用一个weight vector（每个bin具有一个weight entry）的优点是，我们不必假设：一个特定依赖（例如：\(g(\cdot)\)）会提供最好的效果，我们让模型来决定最好的拟合（fit）。在我们的case中，不存在缺点，因为frequency fearture可以具有非负整数值，可以避免量化错误（ quantizatio errors）。

期望的影响（Expected impac）

直觉上，这种方法的影响可以限制分数：对于相同用户对同一个ad出现重复观看。然而，理论上的考虑表明，这样的影响实际会强加给一个广告的首次views。

当我们使用HFC时，predictive model的得分会忽略：frequency会趋向于首次曝光和重复曝光的一个平均CTR。由于重复曝光会具有更低的CTR，这些得分会比首次view具有更低的CTR。添加SFC可以使得pCTR在首次view时具有更高的CTR，之后的views会随着SFC weights进行递减。因此，会接收许多次views的广告（ads）得分不再随这些views减小，从而它们的首次views的点击预测会更准确，之后的views也更准确。

8.效果评估

本节我们会进行在线、离线评估。

注意，由于记录的数据会被用于评估模型，很明显地，通过其它方式来产生结果是不可能的。该 警告在papers中很常见。

8.1 离线评估

为了评估离线效果，我们训练了两个offset models，一个使用SFC，如第7节所描述，其它没有frequency capping，作为baseline。我们会从头运行这些模型，其中，所有模型参数会被随机初始化，它会在一个月的Gemini native 数据上进行训练，包括了数十亿次曝光。

由于技术限制，我们使和以下的binning vector，它具有26个bins:

另外，我们会测试SFC算法参数的多个组合，并找到最好的setup来使用campaign作为ad feature（\(A_f = campaign\)），并在last week（\(T_f=week\)上聚合views），并使用一个global weight vector（\(W_c=global\)），它会消除一些稀疏性。我们使用sAUC和LogLoss metrics来评估离线效果，在应用效果metrics之前，每次曝光会被用来训练系统。OFFSET hyper parameters，比如SGD step size和正则系数，会通过adaptive online tuning机制进行自动决定。

效果指标

Area-under ROC curve(AUC)：AUC指定了概率，给出两个随机事件（一正一负，点击或跳过），以及预测的pairwise ranking是正确的。

Stratified AUC (sAUC)：每个Yahoo section的AUC的平均加权（通过postive event，例如：点击数），该metric的使用是因为：不同Yahoo sections会具有不同的prior click bias，因此，单独使用section feature对于达到更高AUC values来说被证明是充分的。

LogLoss

其中，\(T\)是一个training set，\(y \in \lbrace 0, 1\rbrace\)是postive event indicator（例如：click或skip）。我们注意到，LogLoss metric会用于优化OFFSET model参数以及它的算法超参数。

结果：LogLoss和sAUC的提升会随时间进行绘制，在图7上，对于一个使用binning vector \(B_{26}\)训练的OFFSET model，最好的SFC算法参数是：\(A_f=campaign, T_f=week, W_c=global\)，其中每个点表示了数据3小时价值。从图中看出，SFC model的优点是，所有提升都是正向。特别的，在last week训练上我们在LogLoss上有平均1.02%的提升，在sAUC上有0.83的提升。我们注意到，对于一个成熟算法来说，要达到这样的高accuracy提升，需要持续优化数年，这相当令人印象深刻。

为了达到这部分，我们将产生的全局campaign frequency weight vector如图8所示。weights 会随着frequency单调递减，其中，最后一点会包含所有大于v=25的frequency，它在曲线最下会掉落。后者会造成pCTR在该区域不准确，例如：\(f_{u,a}=25\)的under-prediction以及对\(f_{u,a} >> 25\)的over-prediction。由于我们具有较少的events，并具有更高的frequencies（如图3所示），这表明整体平均效果是under-prediction的。

统计异常解释

异常包含了在nCTR的小“jump”，它会“破坏”nCTR随frequency的单调递减性，这会发生在v=24和v=25间。如上所述，当SFC集成到offset中时，会使用binning vector \(B_{26}\)中的\([25, \infity)\)作为最后一个bin，进行收集统计信息。在之前的paragraph中，这会造成一个整体under-prediction effect在该区域的下降。由于statistics会被收集来进行auction wining events，我们会获得in-spite。

际

参考

• 1.https://dl.acm.org/doi/pdf/10.1145/3357384.3357801

摘要

MAB framework（Multi-Armed Bandit）已经被成功应用到许多web应用中。然而，许多会涉及到内容推荐的复杂real-world应用不能满足传统的MAB setting。为了解决该问题，我们考虑一个ordered combinatorial semi-bandit问题，其中，learner会从一个包含K actions的base set中推荐S个actions，并在S（超过M）个不同的位置展示这些结果。目标是：在事后根据最可能子集和位置来最大化累积回报（cumulative reward）。通过采用minimum-cost maximum-flow network（最小费用最大流网络），基于thompson sampling的算法常用于(contextual)组合问题中，以解决这个组合难题。它可以潜在与whole-page推荐以及任意概率模型一起工作，来说明我们方法的高效性，我们主要关注Gaussian process optimization以及一个contextual setting，其中ctr使用lr进行预测。我们演示了该算法在synthetic Gaussian process问题上的效果，以及在Yahoo!首页的Today Module的大规模新闻推荐数据集进行了验证。

1.介绍

我们使用新闻推荐作为示例。图1是一个portal website的snapshot。在该view中，存在6个slots来展示新闻推荐。这些slots在positions、container sizes以及visual appearance上都不同。一些研究表明：用户不会顺序扫描webpages[Liu 2015, Lagun 2014]。如何作出whole-page推荐，也就是说，从一个更大池子中选择6篇文章，并将它们放置在webpage上，这是一个在ranking之外的组合问题（combinatorial problem）。我们的目标是，寻找一个最优的布局配置（layout configuration）来最大化期望的总CTR。这个主题也有相关工作（Wang 2016），然而搜索引擎以real-time方式工作，它们的模型在batch data上训练（而非online learning的方式），因而忽略了exploration/exploitation tradeoff。

一些已经存在的工作使用multi-plays来解决bandits，例如：

• subset regret problem（Kale 2010..）
• batch mode bandit optimization with delayed feedbackes(Desautels 2014)
• ranked bandits(Radlinski 2008)

这类learning问题也被看成是一个combinatorial bandit/semi-bandit （Gai 2013）。然而，我们示例中的复杂combinatorial setting难度超出了这些方法。

为了建模这种场景，我们考虑如下的rodered combinatorial bandit问题。给定最优的context信息，而非选择一个arm，learner会选择一个关于S个actions的subset，并从M个可能位置上在S个不同位置对它们进行展示。我们的新颖性有：

• 1.我们的方法不会求助于其它方法来提供近似解。相反，我们会将该问题通过mcmf network进行公式化，并有效提供精确解（exact solutions）
• 2.据我们所知，我们的模型会处理通用的layout信息，其中positions的数目可以大于选中arms的subset数，例如：S < M.
• 3.我们会使用Thompson sampling作为bandit实例。Thompson sampling的一个优点是，不管随机reward function有多复杂，它在计算上很容易从先验分布进行抽样，并在所抽样参数下选择具有最高reward的action。因此，它可以潜在与任意probabilisitic user click模型一起工作，例如：Cascade Model和Examination Hypothesis。

图1

2.问题设定

由于position和layout bias，很合理假设：对于每篇文章和每个position，存在与(content, position) pair相关联的一个ctr，它指定了用户对于在一个特定position上展示的内容的点击概率。在一个序列rounds（\(t=1,2,\cdots, T\)）上，learner需要从关于K个actions的一个base set A中选中S actions来在S（小于M）个不同positions上展示，并接受到一个reward：它是在选中subset中关于(action,position) pair的rewards的总和。对于每个展示的(content, position) pair，所有回报（payoff）会被展示。该feedback model被称为“semi-bandits”（Audiber, 2013）。我们可以根据该方法来展示建模关于selected arms中subset的positions，我们称该setting为“ordered combinatorial semi-bandits”。

Ordered(Contextual) Combinatorial Bandits

在每个round t，learner会使用一个（optional）context vector \(x_t\)展示。为了考虑layout信息，会为每个(action, position) pair (k, m)构建一个feature vector \(a_{k,m}\)。该learner会从A中选择S个actions来在S(小于M)个不同positions进行展示。因此，一个合法的combinatorial subset是一个从S个不同actions到S个不同positions的映射；或者更简单地，它是一个one-to-one映射 \(\pi_t : \lbrace 1,2,\cdots, S\rbrace \rightarrow (A, \lbrace 1,2,\cdots, M \rbrace)\)。我们接着将每个\(\pi_t\)看成是一个super arm。该learner接着为每个选中的(action, position) pair接收 reward \(r_{\pi_t(s)} (t)\)。round t的总reward是每个position \(\sum\limits_{s=1}^{S} r_{\pi_t(s)}(t)\)的rewards总和。目标是：随时间最大化expected cumulative rewards \(E[\sum_{t=1}^T \sum_{s=1}^S r_{\pi_t(s)}(t)]\)。

contextual conbinatorial bandits的一个重要特例是，context-free setting：它对于所有t来说，context \(x_t\)是个常量。通过将S, K设置成特殊值，许多已经存在的方法可以被看成是我们的combinatorial bandits setting的特例。例如：S=1等价成传统的contextual K-armed bandits。如果我们将K=1设置成dummy variable，并将N个positions看成是actions，我们的combinatorial bandit问题会退化成为unordered subset regrets问题（Kale 2010）。bandit ordered slate问题以及ranked bandits可以看成是S=M的特例。我们的setting不局限于l2r，足够通用可以对whole-page presentation进行optimize。

3.Thompson Sampling

在(contextual) K-armed bandit问题中，在每个round会提供一个最优的context信息x。learner接着会选择一个action \(a \ in A\)并观察一个reward r。对于contextual bandit问题，Thompson Sampling在Bayesian setting中是最容易的。每个过往observation包含了一个三元组\((x_i, a_i, r_i)\)，以及reward的likelihood function，通过参数形式\(Pr(r \mid a, x, \theta)\)在参数集\(\Theta\)上进行建模。给定一些已知的在\(\Theta\)上的先验分布，这些参数的后验分布基于过往observations通过Bayes rule给出。在每个time step t上，learner会从后验中抽取\(\hat{\theta}^t\)，并基于抽取的\(\hat{\theta}^t\)选择具有最大expected reward的action，如算法1所示。

4.Orderd Combinatorial Semi-Bandits算法

由于Thompson sampling对于复杂reward functions的灵活性，我们的主要算法思想使用它来进行ordered semi-bandits。

在每个round t，ordered combinatorial semi-bandit问题涉及到：从一个K actions的集合A中选中S个actions，并在S个不同positions上进行展示，并收到一个reward（所选subset的reward和）。

一个naive方法是，将每个复杂的组合看成是一个super arm，并使用一个传统的bandit算法，它会在所有super arms上枚举values。由于super arms的数目会快速膨胀，该方法具有实际和计算限制。

假设每个context x以及(action, position) pair \(a_{k,m}\)的reward的likelihood function以\(Pr(r \mid x,a,\theta)\)的参数形式建模。下面三部分会开发thompson sampling的特殊变种，它们可以有效找到最优mapping \(\pi_t^*: \lbrace 1,2, \cdots, S \rbrace \rightarrow (A, \lbrace 1,2,\cdots, M \rbrace)\)，使得：

…(1)

将action selection看成是一个约束优化（constrained optimization）

为了找到最佳的super arm \(\pi_t^*\)，等式(1)中没有enumeration，我们首先定义：每个(action, position) pair的的expected reward为 \(E[r \mid a_{k,m}, x_t, \hat{\theta}^t]\) 。其中：对于在position \(p_m\)上展示action \(a_k\)，给定context \(x_t\)以及采样参数\(\hat{\theta}^t\)。。。。我们也定义了指示变量\(f_{k,m}\)来表示action \(a_k\)是否会在position \(p_m\)上被展示，\(f_{k,m} \in \lbrace 0, 1 \rbrace\)。我们接着将一个合法的super arm转成数学约束。首先，由于每个action会至多被展示一次，它对应于constraint \(\sum_m f_{k,m} \leq 1, \forall k\)。第二，在同一个position上不能放置两个action，因而我们有\(\sum_k f_{k,m} \leq 1, \forall m=1, \cdots, M\)。最终，会选中S个actions，它等价于\(\sum_k \sum_m f_{k,m} = S\)。在等式(1)中对super arms进行最大化，可以被表示成如下的integer programming：

服从：

…(2)

总之，integer programming问题不能被高效求解。然而，在下一节所示，给定的公式可以被解释成一个network flow，它遵循多项式时间解。

Network flow

integer optimization问题(2)可以被看成是一个minimum-cost maximum-flow公式，它的edge costs为\(-e_{k,m}\)，如图2所述。决策变量\(f_{k,m}\)表示flow的量，沿着一个bipartite graph的edges进行转移，具有expected rewards \(e_{k,m}\)。另外，S表示network flow的total size。另外，与biparite graph相连的edges的flow capacity为1，它表示这些edges可以适应一个flow，至多1个unit。另外，我们可以将constraints的最后集合使用连续等价\(f_{k,m} \in [0,1]\)进行relaxing，将(2)的integer programming公式变更成一个linear programming。

定理1：一个有向网络（directed network）的node-arc incidence matrix是完全unimodular。

这里，我知道问题(2)在linear programming relaxation中constraints的集合可以被表示成标准形式：\(Ax = b, x \geq 0\)，它具有一个完全unimodular的constraint matrix A。由于一个graph的incidence matrix具有线性独立行（linearly independent rows），S是一个integer，我们知道linear programming relaation(2)的 super arm selection问题会导致一个integer optimal solution \(f^* \in \lbrace 0,1 \rbrace^{K \times M}\)。另外，linear programming问题可以使用interior-point方法在多项式时间求解，因此我们可以有效求解super arm selection问题。请注意，对于min-cost network flow问题的专有算法可以比linear programming方法具有更好的运行时间。然而，这样的专有方法通常不会允许引入额外的constrainints。对于这些原因，我们在实验中使用一个linear programming solver。

Thompson sampling进行combinatorial semi-bandits

参考

• Efficient Ordered Combinatorial Semi-Bandits for Whole-page Recommendation

ali在2018年前提的一个《An End-to-end Model of Predicting Diverse Ranking On Heterogeneous Feeds》，我们来看下它的实现。

介绍

图1 Item Search Engine和Content Search Engine间的关系

2.基本概念

2.1 商业背景

alibaba自己拥有CSE(Content Search Engine)和ISE（Item Search engine），它会相互交互来为用户创建在线购物环境。在ISE中的所有items与CSE中的一群feed相关。用户可以自由地travel和search在两个搜索引擎。

阿里巴巴ISE和CSE的混合使用，对用户在线购物有收益。总之，用户会在阿里巴巴上日志化，他们与搜索引擎的交互总是有意图的。然而，当面对大量items时，如果他们只搜索在ISE中的items，他们可能会迷茫。例如，阿里的官网，像服装这样的热门品类可能包含上万的items。每个items会使用数十个keywords进行打标记（比如：风格、slim cut、韩版等）。如果没有任意指导，用户们从一个item候选的大集合中区分合适的items是面临挑战的。

因此，为了帮助用户避免疑惑，并提供它们可靠的购物建议，CSE会成为用户的购物指导。给定来自用户的queries，CSE会组织一个合适的feed ranking list作为一个返回结果，替代item ranking list。feeds可以被表示成post(article)、list(item list)以及video的形式。他们由电商领域（clothing、travelling、化妆品）专家的”淘宝达人（Daren）”生产。在它们的feeds流量，“达人”会介绍特定items的优点和缺点，并对特定subjects基于它们的领域知识提出个人建议。

• 一个post feed是一篇文章，它会介绍特定items的属性；
• 一个list feed是一个推荐items的集合；
• 一个video feed是一个用来演示建议items的short video。

通过达人的建议，用户可以做出更好的购物选择。

每天在生产环境中的数据会经验性地展示在两个搜索引擎间的user travel rate是否频繁。在用户跳到CSE中前，他们通常已经在ISE中搜索过记录。这表明用户实际上希望购买来自“达人”的建议。提供更好的CSE搜索结果可以帮助用户更方便的定向到合适的items，从而做出之后的购买，这是电商的主要目标。然而，仍然有挑战。首先，feed types是异构的，不同类型的feeds的匹配度（fitness）与一个给定的query是不可比的。例如，一个list feed是否比一个post feed更好依赖于用户体验。第二，大量用户进入阿里CSE会携带着来自ISE的用户行为。如何处理跨域信息并构建user profiles来形成一个在CSE上的个性化feed ranking需要进一步探索。

2.2 数据准备

在我们的方法中，我们的目标是：给定一个user u发起的一个query q，返回一个异构feed ranking list \(R_1(feed) \mid u, q\)。

在Top K个ranked feed中的每个item都会被安置（locate），并在CSE中从上到下分别在一个”slot”中展示。为了学习independent Multi-armed Bandit（iMAB）模型以及personalized Markov DNN(pMDNN)模型，需要获取slot相关的统计数据（全局信息）以及用户点击流数据（个性化信息）这两者。

2.2.1 slot相关的统计数据

用户偏好的一个假设是：在每个slot中的feed type相互独立。

对于每个slot，三个候选feed types的概率（post、list、video）会遵循它们自己的Beta分布。因此，给定在一个slot s上的候选类型T，为了估计一个feed type \(\theta\)的先验分布\(p(\theta \mid \alpha, \beta, T, s)\)，必须知道每个slot的所有slot相关统计信息，以便估计\(\alpha\)和\(\beta\)。slot相关的统计数据包含了两部分：在线实时数据和离线历史数据。在线实时数据指的是流数据：每天由用户生成的对于一个特定slot type的点击数(click)、曝光数(display)。离线历史数据指的是：过去n天page view（pv）、以及item page view（ipv）的总数。在线天数据是streaming data，只能在实时中观察到。而离线历史数据可以被追踪、并能从仓库中获取。我们会在表1中计算和展示top 5 slots的统计数据。

表1 在CSE的top 5 slots上的feed历史数据

从表1中看到，在每个相关slots的pv和ipv的总数会有不同，video feeds在CSE中的top 5 slots很难出现。这表示：从全局上看，用户在不同feed types会偏向不同的feed types。

2.2.2 用户点击流数据

来自ISE和CSE的用户行为序列数据对于训练一个个性化feed ranking结果来说是有用的。为了构建user profile，我们会设置一个window size w，它只考虑用户在ISE上的最新w个行为。该行为可以表示为两种类型的triplet：<user, issue, query>和<user, click, item>。

• 用户在items上的点击次数表明users和items间的关系，
• 而用户(users)发起（issue）相同query的次数表明：users和queries间的关系强度。

基于此，可以在相同的latent space上从每个user/query中学习得到一个给定维度的embedding。另外，在每个slot中的feed type通过one-hot encoder进行编码。最后，所有users、queries、feed types可以被表示成vectors。示例如表2所示。前两列指的是每个user \(f_u\)学到的表示，以及一个issued query \(f_q\)。第三列指的是在每个slot中feed type \(f_t\)的one-hot表示。

表2 对于每个slot的用户个性化数据的示例

3.方法

对于用户体验，我们希望观察到更好的异构feeds ranking。整个过程包含了Heterogeneous Type Sorting step以及Homogeneous Feed Ranking step。

• 对于第一个step，对于slot independent场景，会设计一个independent Multi-Armed Bandit(iMAB)模型；
• 对于slot denpendent场景，会设计一个改进版的personlized Markov DNN(pMDNN)模型。

第3.1节和3.2节会分别引入两个模型。对于第二个step，会使用一个DSSM模型来在每个slot上分配合适类型的feeds。第3.3节会详细介绍，pMDNN可以与DSSM一起训练来构成一个end-to-end模型。

3.1 independent Multi-Armed Bandit

在iMAB模型中，异构feed ranking的评估指标是：在ipv和pv间的ratio \(\theta\)。更高的\(\theta\)意味着：当一个用户浏览在CSE中的一个feed时，用户更可能会点击该feed。因此，\(\theta\)可以根据用户的实际需要来用于评估heterogeneous feed ranking的匹配度（fitness）。因此，对于每个independent slot，我们会为每个feed type估计一个先验ratio \(\theta\)分布，并倾向于选择能够生成最高\(\theta\)值的feed type。

理论上，由于Beta分布可以天然地表示成：由两个参数\(\alpha\)和\(\beta\)控制的任意类型的分布，它会假设每个type的ratio \(\theta\)具有一个先验分布遵循：\(\theta_i \sim B(\alpha_i^0, \beta_i^0)\)，

其中：

• \(i \in \mu = \lbrace post, list, video \rbrace\)。
• \(\alpha_i^0\)是type i的历史ipv数，
• \(\beta_i^0\)是type i历史pv数和ipv数间的差。

由于\(B(\alpha_i^0, \beta_i^0)\)的期望是：\(\frac{\alpha_i^0}{\alpha_i^0 + \beta_i^0}\)，它是ipv和pv间的历史ratio。因此，后验ratio分布可以通过在线实时流数据进行每天更新，表示成：

其中：

• \(D_i\)指的是每天到来的feed type i
• \(\lambda\)是时间影响因子，因为新数据会对更新ratio分布有影响。

最终，我们会使用一个two step sampling策略来选择每个slot的type。首先，对于每个feed type i，会被随机生成一个value \(\theta_i\)，因为在pv和ipv间的ratio的估计遵循以下的概率分布：

…(1)

其中，给定\(\alpha_i\)和\(\beta_i,\)，

• \(B(\alpha_i, \beta_i,)\)是一个常数
• \[\alpha_i,=\alpha_0+\lambda D_i^{ipv}\]
• \[\beta_i,=\beta_0 + \lambda(D_i^{pv} - D_i^{ipv})\]

第二，对于每个feed type，会应用一个softmax函数到所有feed types上来生成一个归一化的selection概率：

…(2)

其中：

• i指的是三种feed types的其中之一
• \(\theta_i\)是公式1展示了根据后验概率分布\(D(\theta)\)生成的随机值

这种方式中，在所有slots中的feed types会独立选中。整个过程的伪代码如算法1所示。

算法1

3.2 peronalized Markov DNN

Dependent heterogneous feed type selection会由三个因素决定：user、query、以及在相同page页上之前的slot feed types。

• 第一，不同users会在相同queries下对于items具有不同的偏好。例如，当一个用户搜索”dress”时，她可能会愿意看到关于dress描述的文章post。而对于其它user，他们可能更喜欢lists，因为他们想看到更多item选项而非单个item介绍。
• 第二，在当前slot上的feed types的用户偏好可能会受之前feed types的潜在影响，它可以被看成是一个Markov process。例如，没有用户愿意看到在所有slots上看到相同类型，他们或多或少希望看到不同types的feeds。
• 第三，不同queries在所有slots上应产生不同的feed type allocation。为了将用户偏好、query、以及推荐的previous feed types一起集成，对于第i个slot，我们提出了一个pMDNN模型来生成推荐的feed type \(t_i \mid (user, query, t_1, \cdots, t_{i-1})\)。整个模型可以解耦成两个子任务（sub tasks）：包括一个user&query表示学习任务、以及一个personlized slot type的预测任务，如图2所示。

图2 使用pMDNN的end-to-end模型，从cross-domain knowledge和user preference中进行学习

3.2.1 User和Query的表示

基于统计数据，在CSE中有80%的用户来自于ISE。因此，通过使用它们的用户行为序列数据，我们可以构建一个graph来描述users、queries、items间的关系。之后，node2vec会在最后使用一个skip gram模型来学习users和queries的embeddings。详细的pipeline如图2所示，目标函数如下：

…(3)

其中：

• \(\overset{\rightarrow}{f_v}\)是当前node v的embedding。
• t是node v的一个positive neighbour node；
• u是v的一个negative sampled node。

这意味着：给定一个node v，我们需要学习一个node embedding表示，它可以最大化概率来生成它的positive neighbor node u，并最小化概率来生成它的negative node node sets\(P_{noise}\)。

图2的中间部分表明，如何训练node embedding表示。input layer是node的one-hot encoding。weight matrix W是所有nodes的embedding，它可以帮助将input one-hot encoding node投影到一个\(\mid D \mid\)维的latent space上。接着，最大化概率来生成node u的neighour nodes。

在最后，所有users和queries可以使用一个给定长度维度的embedding representations。并且匀们使用user & query embeddings作为输入来进行slot feed type预测。

3.2.2 Type prediction

对于给定users、queries、以及previous slot feed types信息，我们希望预测每个slot的feed types。因此，目标函数为：

…(4)

其中：

• \(X_i\)是对于第i个slot的input feature vectors，它与user \(u_i\)、queries \(q_i\)以及previous slot feed types \(f_i\)相关。
• \(\Phi\)是input feature vectors到output feed type的转换函数。
• c是当前slot的true feed type。

我们的目标是最大化成功预测slot feed types的joint probability。

为了简化我们的pMDNN模型，并加速运行速度，只有slot feed type的一阶Markov过程会被应用到该模型上。它意味着预测第i个slot feed type，只有第(i-1)个slot feed type会对它有latent影响。而这对于一个user u的第一个slot feed type来说会带来一个问题。因为它没有previous slot feed type信息。对于一个user u，为了给第一个slot生成一个伪信息，user u喜欢的item i会在ISE中根据观看次数和停留时长被检测到。接着，我们会在ISE中将item i映射到在CSE中与它相关的feed f中，并使用f的type作为一个替代。

我们使用给定的user、query的embedding以及previous slot types来构建pMDNN模型来推荐feed type。input layer是user embedding(U)、query embedding(Q)和之前slot types(T)的concatenation。User和query embedding会通过在constructed graph上进行node2vec学到。整个input layer的构建可以看成是：

…(5)

最后，会在input layer上附加三个fully connected hidden layers。每个layer会使用线性分类器和cross entropy作为loss function。在每个hidden layer中的Activation function被设置为ReLu，output layer会使用Softmax作为activation function。通过gradient descent和BP，我们会训练模型直至收敛。outpu layer是一个vector，它包含了：，在通过一个softmax activation function之后，在每个指定slot上关于三种feed types的一个概率分布。

…(6)

L表示当前slot feed type的true label。pMDNN模型会在离线阶段被训练，我们可以管理trained model来预测实时用户请求。\(L_1, L_2, L_3\)分别表示三个hidden layers。图2的第一部分展示了这个工作流。

3.3 异构feed ranking

下一step是对homogeneous feeds进行排序，并填充相关的slots。例如，如果\(slot_i, slot_j, slot_k\)被选中具有”post” feed type，我们需要rank所有post feeds并选择在当前query下具有最高relevance score的top 3 feeds。由于所有types的feeds与文本信息相关（比如：title），会使用一个已经存在的DSSM来对所有post feeds进行rank来在三个slots上进行填充。

在DSSM中，我们不会为每个word会使用一个one-hot表示进行编码，而是使用word hashing方法来利用n-gram模型来分解每个word。这会减小word表示的维度。

最后，一个DNN模型可以使用query和feeds作为input layer，给定跨训练信的queries，并通过最大化点击文档的likelihood进行模型参数训练。相等的，该模型需要最小化以下的loss function：

…(7)

其中，\(\wedge\)表示NN的参数集。\(D^+\)表示具有true label的feed，Q是user-issued query。该模型会使用gradient-based数值优化算法进行训练。

最后，给定一个query，所有candidate feeds可以通过由该模型计算的generative probability进行排序。它可以使用pMDNN进行训练来公式化成一个end-to-end模型，如图2所示。而它仍需要从iMAB模型进行训练得到。

4.实验

我们会在ISE和CSE上进行实验，数据集划分：80%训练集，20%测试集。用户行为序列会收集N=90天的数据，来构建一个behaviors graph，它可以将users和queries表示成dimensional embeddings。

4.1 模型setup

对于iMAB模型，在online部分，我们实现了一个real-time Flink job，它会解析用户行为日志，并抽取一系列status表示：用户在不同slots上是否点击或浏览展示的feeds。接着用户行为被同步到online reward到iMAB模型中。由于阿里的用户行为日志非常大，为了确保Flink job时延低，我们分配了256个workers做parsing和joining，接着使用64个workers做aggregating。正如我们所预期的，online rewards会在3s内被传给iMAB模型，这使得它可以基于最新的用户行为来选择arm来表示一个概率分布。而在离线部分，超过1亿的ipv和pv记录会被聚合来估计Beta分布。基于经验表明，我们会在iMAB模型中设置\(\lambda=10\)来作为一个time impact factor。

另外，pMDNN模型需要一个训练过程，相应的设置如下：

• User和Query表示：128维的graph embedding
• Feed type表示：one-hot vector
• Activation function：ReLu和softmax
• Loss function：cross entropy
• optimizer：GD opitmizer
• learning rate: 0.0001
• epochs: 100000

我们会训练pMDNN模型，并导出saved_model格式来在CSE中进行serving，它会接收实时在线请求，包含：user、query、以及preceding feed type，接着使用转化后的embedding vectors按顺序预测下一个slot type。在原始DSSM中的缺省设置会应用到我们的模型中。

4.2 A/B test

我们在三个分桶上部署提出的模型。每个分桶会通过一个hash partition function来等价处理用户请求。我们会选择5个major indices来对比在iMAB和pMDNN间的效果。pv表示展示items的数目，而pv click表示有多少displayed items被点击；相似的，uv是不同用户进入到CSE的总数，uv点击表示用户点击feeds的数目；至于uv CTR，它是用户点或不点的ratio。

表3展示了实验结果。对比原始的离线ranking方法，pMDNN总体上要胜过iMAB。特别是uv click和uv ctr，他们对于我们的场景是必要的，因为uv click的增加表明：更多用户超向于CSE，以便它能改进它的购物体验，同时，uv ctr的增强表明：用户进入CSE实验上在模型的ranking结果中更感兴趣。至于pv click，它也表明我们的模型工作良好，因为更多用户在发起queries后愿意点击feeds。

基于pv click和uv CTR，我们可以下结论：pMDNN要优于iMAB，它通过应用cross-domain知识并优化在whole page上的ranking results。另外，结合上用户体验信息可以增加用户点击的概率（uv click指标）。

参考

• 1.https://sigir-ecom.github.io/ecom2018/ecom18Papers/paper13.pdf

yahoo在2016年《Beyond Ranking: Optimizing Whole-Page Presentation》的一篇paper里提出了针对whole-page优化的方法，我们来看下。

摘要

现代搜索引擎会从不同verticals中聚合结果：网页、新闻、图片、视频、购物（shopping）、知识页卡（knowledge cards）、本地地图（local maps）等。不同于“ten blue links”，这些搜索结果天然是异构的，并且不再以list的形式在页面上呈现。这样的变化直接挑战着在ad hoc搜索中传统的“ranked list”形式。因此，为这种异构结果group发现合适的呈现（presentation）对于现代搜索引擎来说很重要。

我们提出了一个新框架来学习最优的页面呈现（page presentation），从而在搜索结构页（SERP：search result page）上渲染异构结果。页面呈现被广泛定义成在SERP上呈现一个items集合的策略，它要比一个ranked list要更丰富些。它可以指定：item位置、image sizes、文本字体、其它样式以及其它在商业和设计范围内的变体。学到的presentation是content-aware的，例如：为特定的queries和returned results定制化的。模拟实验表明，框架可以为相关结果自动学习到更吸引眼球的呈现。在真实数据上的实现表明，该框架的简单实例可以胜过在综合搜索结果呈现上的先进算法。这意味着框架可以从数据中学到它自己的结果呈现策略，无需“probability ranking principle”。

1.介绍

十年前，搜索引擎返回”十个蓝色链接（ten blue links）”。结果呈现（Result presentation）很简单：通过估计的相关度对webpages进行排序。当用户往下扫描列表时会省力些，可以在top ranks点击到他希望的信息。这种“probability ranking principle”在1970年开始已经存在很久，并且在eye-tracking研究[20,19]以及搜索日志分析[24,15]中被证实。

今天的搜索引擎会返回比“ten blue links”更丰富的结果。除了webpages，结果可能还包括：news、images、video、shopping、结构化知识、本地商业地图等。每个特定corpus可以通过一个垂类搜索引擎（vertical search engine）索引；他们联合（federated）在一起为用户信息提供服务。不同于“ten blue links”，垂类搜索结果具有不同的视角外观、布局和大小（sizes）。他们会在页面上跨多列，不会严格限制在mainline list上（图1）。

图1 现代搜索引擎结果页

综合搜索结果会在搜索结果页（SERPs）上转移用户交互样式（user interaction patterns）。人的眼球会自发地被图片结果（graphical results）吸引，从而产生一个显著的attention bias：vertical bias[12, 26, 31]。更有趣的是，在某个垂类结果（vertical result）周围的blue links被点击的概率也会增加[12]。在垂类结果中，在整个SERP上的用户满意度不能从成对结果的偏好判断中可靠地推断出。

这些观察表明：用户不会按顺序扫描由综合搜索（federated search）返回的结果。尽管常规的”ranked list”公式仍会被用于综合搜索结果呈现上[5,4]，它本质上是一个一阶近似（first-order approximation）的问题。

本文中，我们提出了一个新的框架，它可以为在SERP上的异构搜索结果学习最优的呈现（presentation）。Page presentation被定义成：在SERP上呈现一个异构items集合的策略（strategy），它比一个ranked list更具表现力。它可以指定item positions、图片尺寸、文本字体、以及任意在商业限束下的元素变化风格。一个presentation的好坏可以通过用户满意度指标来判断：更好的呈现（presentation）会让用户更满意。该框架会学到一个scoring function，它会将搜索结果和其它在SERP上的presentation映射成用户满意度。接着，给定由一个new query的搜索结果，该框架能计算出一个能最大化用户满意度的presentation。

该框架相当通用。首先，我们可以灵活定义page presentation的范围。它可以将item positions（水平和垂直位置都行）、以及元素风格（图片大小、文本字体等）编码。ranked list只是它的一个特例。第二，不同应用场景可以采用不同的用户满意度指标。它不受click-based指标的限制，但也会将其它交互行为考虑其中，比如：停留时长（dwelling time）和首次点击时间（time-to-first-click）。最后，该框架也可以在其它交互搜索场景上实现，比如：移动端或tablelet devices的搜索结果呈现、在线社交网络的多媒体展示feeds、电商中的items布局（arranging） 。

我们在synthetic和real data上都做了实验，演示了该框架的强大。仿真实验展示了框架可以适配不同类型的attention bias，并可以学会呈现相关结果来捕获用户眼球。这意味着我们的方法可以直接针对由综合搜索带来的挑战，其中，用户不会按顺序扫描结果，并且结果不会以ranked list的形式展示。在real data实验中，framework的简单实现效果要好于在综合搜索结果排序上的先进算法。这是因为：ranked list在结果呈现上使用probability ranking principle的ranking算法，而我们的框架不认可它的存在。然而，它会纯粹从数据中学到它自己的结果呈现准则（result presentation principle），并可以达到SOTA的效果。

主要贡献：

• 1.我们对新问题（whole-page presentation optimization）进行公式化，它扩展了在ad hoc search上的异构文档排序
• 2.我们提出了一个通用框架，它会为综合搜索结果（federated search results）计算最优化的呈现（presentation）
• 3.在synthetic和real data上的实验表明：提出的框架可以解决新问题

2.问题公式化

Page Presentation Optimization的问题声明如下：“给定在一个页面上要展示的搜索结果，发现可以最大化用户满意度（user satisfaction）的最优呈现”。我们假设以下setting：搜索引擎返回针对某一query的一个结果集，并在SERP上根据一些呈现策略（presentation strategy）对items进行渲染。由于SERP会被展示给用户，用户可以与它交互来获得特定的用户满意度。现在假设我们在setting中定义了些重要概念：

定义1（Page Content）

Page Content是在页面上被展示的搜索结果集合。每个搜索结果是一个item。在接收到用户的query后，搜索引擎后台会返回一个关于k个items的集合。每个item被表示成为一个vector \(x_i\)。注意，不同的users和不同的queries会生成不同的items集合，因此\(x_i\)也可以从实际users和queries中编码信息。Page Content被呈现成k个item vectors的concatenation：\(x^{\top}= (x_1^{\top}, \cdots, x_i^{\top}, \cdots, x_k^{\top})\)。x的domain通过由后台返回的所有可能page content进行定义，被表示为X。

定义2（Page Presentation）

Page Presentation定义了要展示的page content x，比如：position、vertical type、size、color等。它可以被编码成一个vector p。p的domain通过在符合商业和设计约束下所有可能的page presentations进行定义，表示成P。

定义3（Search Result Page, SERP）

当Page Content x根据呈现策略p被排布在页面上时，会生成一个SERP。换句话说，content x和presentation p唯一地决定了一个SERP。它可以被呈现成一个tuple \((x, p) \in X \times P\)。

定义4（User Response）

User Response包含了它在SERP上的动作（actions），比如：点击数、点击位置、点击停留时长、第一次点击的时间。该信息被编码成一个vector y。y的domain由所有可能的user responses进行定义，表示为Y。

定义5（User Satisfaction）

用户体验会随着他与SERP交互来确定满意度。我们假设，用户的满意度可以被校准成一个real value \(s \in R\)：s越大意味着满意度越高。

User Response是满意度的一个很强指标。直觉上，如果用户打开了SERP，并在top result上进行了合适的点击，接着在这些结果上花了较长的停留时间，表明他很可能会享受这些结果。

有了以上定义，我们可以将问题公式化：

Page Presentation Optimization：对于一个给定page content \(x \in X\)，我们的目标是发现这样的presentation \(p \in P\)：当\(SERP (x, p)\)被呈现给用户时，他的满意度得分可以被最大化。

如果我们假设，存在一个scoring function \(F: X \times P \rightarrow R\)，它可以将SERP(x, p) 映射到用户满意度得分s上，接着，Page Presentation Optimization问题可以正式写成：

它遵循在Presentation p上的constraints。

Page Presentation Optimization问题是全新且充满挑战的。它之所以为新是因为page presentation可以被灵活定义，这使我们可以学习全新的方式来展示信息。检索和推荐系统通常会使用一个ranked list来展示异构内容（homogeneous content）。由于异构结果是网页形式编排，以极大化用户使用率的方式通过合理方式进行呈现很重要。该问题很具挑战性是因为：对于发现scoring function来将整个SERP（内容和呈现）映射成user satisfaction是非常不明确的。我们在下节提出我们的解决框架。

3.Presentation Optimization framework

我们提出了一种suprevised learning方法来解决page presentation optimization。该部分会建立一整个框架，包括：数据收集方法、scoring function \(F(\cdot, \cdot)\)的设计、learning和optimization阶段。在下一节，我们描述了实际的框架实例。

3.1 通过Exploration的数据收集

supervised learning需要labelled训练数据。在数据收集中的警告（caveat）是，正常的搜索流量（normal search traffic）不能被当成训练数据来学习scoring function \(F(x,p)\)。这是因为：在正常的搜索流量中，search engine具有一个deterministic policy来呈现page content x，它由在系统中已经存在的model/rules所控制。换句话说，Page Presentation p是由给定的Page Content x唯一确定的。然而，我们期望：随着我们通过不同的Page Presentations进行搜索，模型F可以告诉我们用户满意度。x和p间的混杂（confouding）会对学到的模型产生bias，这是一个非常严重的问题。

为了消除混杂（confouding），我们会分配“Presentation Exploration Bucket”来做随机实验。对于在该bucket中的请求，我们会使用随机的Page Presentation对Page Content进行组织。这里“随机（random）”意味着：会在商业和设计约束下均匀地抽取Presentation strategies，这样用户体验也不会损伤太大。更进一步，Presentation Exploration traffic由一个非常小量控制，因此不会影响整体的搜索服务质量。在这种方式下的数据收集保证了scoring function的无偏估计。

对用户随机曝光结果并不是我们想要的，也可以雇人工标注者来标记page，或者从使用不同的固定呈现策略（fixed presentation strategy）的多个buckets来收集数据，因为每个互联网公司都会测试他们的UI变化。由于我们已经在生产系统上开发了一种通过exploration framework的数据收集， 我们选择采用该方法来进行数据收集。

3.2 Learning Stage

Page Presentation Optimization的核心是，估计scoring function \(s = F(x, p)\)。我们可以考虑以下两个方法：

• (I) Direct方法：收集page-wise的用户满意度ratings，并直接对SERP和用户满意度间的依赖关系建模。该依赖路径（dependency path）是“\((x,p) \rightarrow s\)”。
• (II) Factorized方法：首先，在SERP上预测user response y，接着寻找一个函数来从这些responses上measure用户满意度。该依赖路径（dependency path）是“\((x,p) \rightarrow y \rightarrow s\)”。

方法(I)是简单的。然而，它非常难（当数据规模很大时，获得对于entire SERP的显式用户评分（explicit user rating）s很困难）。为了构建这样的数据集，我们需要大量的observations和人工标注来克服训练数据的稀疏性。

方法(II)分两步：

• 第一步：预测在一个给定页上的user responses；
• 第二步：基于它的page-wise response对用户满意度进行measure。

引入user response变量y可以在概念上进行分开：

• 一方面，在page上的user response是一个与页面交互的直接结果（direct consequence）
• 另一方面，用户满意度通常只通过从user responses中进行估计（比如：总点击数、或停留时长）

在方法（II）中，\(F(\cdot,\cdot)\)的复杂依赖被解耦成两个相对独立的因子。在实际上，方法（II）对于当前的web技术来说更现实，因为在SERP上的user response可以通过javascript很容易收集，而显式地询问用户来评估whole page是非常罕见的。因此，我们采用factorized方法。

在factorized方法中，第一步是学习一个user response模型：

这是一个supervised learning任务；f(x,p)的实际形式可以被灵活选择。我们可以简单地为在y中的每个component \(y_i\)构建一个模型（我注：类似于多目标?），或者我们可以直接使用结构化的输出预测（structured output prediction）联合预测y的所有component。在任意case中，用户在页面上的responses同时依赖于content（相关的、多样化的、吸引人的）和presentation（是否接近top、在图片块周围、或以big size展示）。

第二步是一个utility function，它定义了一个用户满意度指标：

基于page-wise user responses寻找合适的用户满意度指标不在本paper关注范围内，在[21,30,38]中有研究主题。确定，实践者通常会将指标定义成细粒度的user responses的聚合，比如：CTR、长停留点击（long-dwell-time clicks），首次点击时间（time-to-first-click）。

最终，对于整个SERP我们的scoring function为：

3.3 Optimization stage

对于给定的content x，通过求解以下的optimization问题，我们计算了最优的presentation \(p^*\)：

它遵循presentation p的约束（constraints）。

计算该optimization问题的计算开销，依赖于objective function \(F=g \circ f\)的实际形式，以及在presentation p上的constraints。在下一节中，我们展示了对于f和g的特定实例，\(p^*\)可以被相当有效地进行计算。

4.Presentation Optimization Framework

本节描述了该framework的实现，包括特征表示、用户满意度metric、两个user response模型以及它们的learning和optimization stages。我们会围绕l2r来展示该framework。

4.1 Features

在一个SERP上的content和presentation两者会同时在一个feature vector上进行表示，它会作为user response模型的input。

Content Features

content features包含了query和相应搜索结果的信息，这与l2r中所使用的相似。我们采用与[23]中所使用相近的content features来进行实验对比：

• 全局结果集特征（Global result set features）：由所有返回结果派生的features。他们指示了每个垂类（vertical）内容的是否有提供（availability）。
• Query特征（Query features）：词汇特征，比如：query unigrams、bigrams、共现统计等。我们也会使用query分类器的outputs、基于query features的历史session等
• 语料级特征（Corpus Level Features）：来自每个vertical及web文档的query-independent features，比如：历史ctr、用户偏好等
• 搜索结果特征（search result features）：从每个搜索结果中抽取得到。它是一个统计归纳特征列表（比如：每个单独结果的相关度得分、ranking features等）。对于一些verticals，我们也会抽取一些domain-specific meta features，比如：电影是否是在屏幕上，在movie vertical中是否提供电影海报，在news vertical中最新几小时的新闻文章的点击数。

Presentation Features

Presentation features会在SERP上被展示的搜索结果进行编码，它是在框架中的新features。具体示例包括：

• Binary indicators：是否在某一位置上展示某个item。该scheme可以编码在线框（wireframe）中的position，比如：一个list或多列panels。假设在frame中存在k个positions，会展示k个items。假设i是items的索引，j是positions的索引，\(1 \leq i, j \leq k\)。item i的presentation，\(p_i\)，是一个1-of-k的binary encoding vector。如果document i被放置在position j，那么\(p_i\)的第j个component是1，其余为0. 在本case中，我们将\(p_i\)的值表示为\(p_{ij}-1\)。page presentation \(p^{\top} = (p_1^{\top}, \cdots, p_k^{\top})\)包含了\(k \times k\)的二元指示变量（binary indicator variables）、本质上编码了k个对象(objects)的排列（permutation）。
• Categorical features：page items的离散（discrete）属性，比如：一个item的多媒体类型（text还是image），一个textual item的字体（typeface）
• Numerical features：pape items的连续（continuous）属性，比如：一个graphical item的亮度、以及对比度
• 其它特征：page content和presentation间的特定交叉可能会影响user response，比如：“在graphical item之上紧接一个textual item”

在实际实验中，我们会使用两种类型的presentation features。我们会使用binary indicators来编码items的位置。对于本地的搜索结果（local search results），我们会将presentation size编码成一个categorical feature（”single” vs. “multiple”条目）。

4.2 用户满意度metric

我们会假设：用户满意度指标 g(y)是对y中components的加权和的某种形式：

在该实验中，我们使用关于k items的click-skip metric[23]：

其中：

• 如果item i被点击，则有\(y_i=1\)；
• 如果item i被跳过并且它下面的某些item被点击，则有\(y_i=-1\)。

一个skip通常表示浪费性检查（wasted inspection），因此我们会将它设置成一个单位的negative utility。该metric会强烈地偏向于在top positions上的邻近点击（adjacent click）。

4.3 User Response Models

我们会使用两个模型来预测page-wise user response：

• 第一个模型会采用在content和presentation间的特征二阶交叉（features quadratic interaction）。它会允许一个有效的最优化阶段（optimization stage）
• 第二个模型使用gradient boosted decision tree来捕获在content和presentation间的更复杂、非线性交叉。我们期等它来生成更好的效果.

二阶特征模型（Quadratic Feature model）

首先，假设我们考虑一个关于user response模型的简单实现，它可以在optimization stage上进行高效求解。由于它使用x和p间的二阶交叉特征（quadratic features），我们称之为“Quadratic Feature Model”。

假设：对于k个items存在k个positions。

• Page content x：是关于k个item vectors的concatenation；
• Page Presentation p：使用二元指示\(p \in \lbrace 0,1 \rbrace^{k \times k}\)进行编码，如第4.1节定义。
• vec：该模型也包含了x和p间的完全交叉作为features。假设 vec(A)表示包含了在matrix A中所有elements的row vector，一列挨一列，从左到右。

Quadratic Feature Model的增广特征向量（augmented feature vector）\(\phi\)为：

假设：

• \(y \in R^k\)是User Response vector；
• 每个component \(y_i\)是在item i上的一个User Response

线性模型\(f_i\)被用于预测在y中的每个\(y_i\)：

…(1)

\(u_i, v_i, Q_i\)分别是content-only特征、presentation-only特征、content-presentation二阶交叉特征各自对应的参数。参数\(w_i = \lbrace u_i, v_i, Q_i \rbrace\)可以使用正则线性回归来估计。为了避免overfitting，我们会将\(u_i\)和\(v_i\)的\(L_2\) norm进行正则化，并进一步在\(Q_i\)上利用low-rank regularization来处理二阶特征的稀疏性。

总之， 我们具有了k个这样的模型，每个模型会预测y中的一个\(y_i\)。为了在概念上将k个模型分组，假设将系数(cofficients)写成：

其中，将x和p“拷贝（copy）” k次来获得以下：

• matrix：\(X=diag(x^{\top}, \cdots, x^{\top})\)
• vector：\(t^{\top}=(p^{\top}, \cdots, p^{\top})\)

为了声明维度，如果\(x \in R^n, p \in R^m\)，那么：

其中：\(t \in R^{mk}\)，user response model可以被写成：

将用户满意度metric表示为：\(g(y) = c^{\top} y\)。那么scoring function \(F=g \circ f\)为：

…(2)

其中，\(a=V^{\top} c + \sum\limits_{i=1}^k c_i Q_i^{\top} x\)是一个已知vector。

最后，optimization stage会找到将(2)最大化的p，并满足在p上的constraints。由于给定了page content x，在(2)中的第一项是一个常数，可以丢弃。第二项\(a^T p\)是一个关于p的线性项。由于\(p \in \lbrace 0, 1\rbrace^{k \times k}\)会编码成一个k排列（k-permutation），在\(a \in R^{k \times k}\)中的每个component表示成用户满意度的增益，如果item i被放置在position j上，\(1 \leq i,j \leq k\)。因此，optimzation问题会化简成：最大二部图匹配（maximum bipartite matching），这是线性分配问题的一个特例。它可以通过Hungarian算法高效求解，时间复杂度为：\(O(\mid p \mid^3)=O(k^6)\)。在一个具有2GHz CPU的单核计算机上，对于50个items，该问题可以在10ms内求解。

GBDT

为了捕获在content x和presentation p间更复杂的非线性交叉，我们将前面章节的quadratic feature model \(f_i\)替换成gbdt模型：\(h_i^{GBDT}\)。GBDT是学习非线性函数的一个非常有效的方法。

我们的feature vector为：

在y中的每个user response \(y_i\)通过一个GBDT模型来预测：

用户满意度指标是：\(g(y) = c^{\top} = \sum\limits_{i=1}^k c_i y_i\)

在optimization阶段，由于每个\(h_i\)是一个无参数模型，我们不能根据p来获得\(F(x,p) = \sum\limits_{i=1}^k c_i h_i^{GBDT}(x, p)\)的解析形式。也就是说，在p上的optimization是棘手的。在实际settings中，由于商业和设计约束，p的搜索空间通常会被减技到十位数的可能值。我们可以实现并行枚举(paralled enumeration)来快速发现最优的presentation来最大化用户满意度。

4.4 特例：L2R

当我们将page presentation限定在一个ranked list时，假设：当更相关的结果被放在top ranks上时，用户会更满意，那么presentation optimization会化简成传统的ranking问题。

，，，

5.仿真研究

通过仿真（simulation），我们展示了presentation optimization framework的潜能。我们使用synthetic dataset，以便我们可以知道“ground truth”机制来最大化用户满意度，因此，我们可以轻易地确认该算法是否可以真正学到最优的page presentation来最大化用户满意度。在该研究中，我们已经有两个目标：

• (1) 我们展示了该framework允许page presentation的通用定义
• (2) 我们使用position bias和item-specific bias两者来展示framework可以自动适配用户交叉习惯

5.1 总览

我们首先给定一个关于simulation workflow的总览。该仿真的“Presentation Exploration Bucket”会生成一个包含由random presentation的items set组合成的页面。每次生成一个新页面时，每个item被分配一些从一个底层分布中抽样的reward（例如：相关信息）。仿真的“user”会具有一个特定类型的attention bias：

• (1) position bias：比起其它地方，用户会花更多注意力在页面的特定区域（图2a所示）
• (2) vertical bias（或item-specific bias）：某一特定类型item及它的周围会更吸引人的注意力

图2 不同类型的user attention bias

(当”Presentation Exploration Bucket”生成一个page时，“user”带有attention bias去检查它时，就发生一次“interaction”。当用户检查一个item时，他会接受到相应的reward。对该page的用户满意度是rewards的总和。Page Content、Presentation、以及被检查的items和positions（user responses），会变成框架希望学习的数据。最终，我们会测试该框架是否成功学到用户的attention bias。给定items的一个新集合，我们会希望看到，该框架会将具有更高rewards的items放置到更容易获得注意力的positions上来达到最大化用户满意度。因此，为了对模型在user attention bias上的当前置信（current belief）进行可视化，我们可以在该page上绘制item rewards的分布。

5.2 数据生成过程

在“search engine”侧，一个page（不管是1D list还是2D grid）包含了k个positions。Page Content \(x=(x_1, \cdots, x_k)^T\) 以及 \(x_i \sim N(\mu_i, \sigma)\)表示了k个items的内在奖励（intrinsic reward）。对于1-D list我们设置k=10，对于2-D grid设置k=7 x 7。 \(\mu_i\)是从[0, 1]中抽取的随机数字，\(\sigma=0.1\)。page presentation p从k-permutations中随机均匀抽取。whole page被表示成：(x, p)。

在”user”侧，attention bias按如下方式仿真：

Position bias：检查position j是否是一个具有参数\(p_j\)的Bernoulli随机变量。一个真实示例是：top-down position bias，当user与一个ranked list交互时常观察到。

Item-specific bias：检查item i是否是一个具有参数\(p_i\)的Bernoulli随机变量。一个真实示例是：vertical bias，当用户与一个包含了垂直搜索结果（vertical search results：images、videos、maps等）交互时常观察到。

接着，”user”会与页面(x, p)进行交互：k个binary values会从k个Bernoulli分布中抽取得到，并且被记录成一个user response vector \(y \in \lbrace 0, 1 \rbrace^k\)。如果item i被examine到，\(y_i=1\)，该user收到一个reward \(x_i\)。用户满意度等于examined items的reward总和。我们会生成10w个pages来训练4.3节中的Quadratic Feature Model。

5.3 讨论

为了对学到的最优的presentation进行可视化，我们会选择一个随机的x，并计算相应的最优的presentation \(p^*\)，接着根据\(p^*\)来安置\(x_i\)。一个page可以被可视化成关于\(x_i\)的rewards的热力图（heat map）。理想情况下，具有更高reward的items（“better content”）应该放置在具有更高概率user attention的position上。

图3 1-D list中的top position bias和presentation

图4 2-D canvas上的top-left position bias

图5 2-D canvas上的two-end position bias和presentation

图3、4、5在多个position biases上对presentation结果进行了可视化。我们可以看到，该算法的确能学到将“更好内容（better content）”放置到具有更多user attention的position上。由于Page Presentation的定义是通用的，对于1-D list和2-D grid它都可以处理。另外，它可以捕获在2-D canvas上的position bias的复杂分布：在图4上的top-left position bias，以及在图5上的top-bottom position bias。

图6展示了在item-specific bias下的结果可视化。这是个很有意思的case，其中在page上的一个item是非常夺人眼球的，并且它也会吸引用户的attention到它周围的items上（例如：一个image会吸引用户的眼球，同时也会吸引注意力在在大标题(caption)和描述文本上）。另外假设：对于那些远离eye-catchy item的items，用户的attention会进一步下降。那么，最优的presentation strategy是放置item在page的中心，以便whole page会分派最大的reward。在图6中，我们可以看到：当该item（深红色区域）位于页面中心时，用户满意度值s是最高的。

图6 Item-Specific bias。s: page-wise user satisfaction。当一个specific item(例如：图片)吸引了用户的注意力时，它周围的结果也会受到关注，那么: 当垂类（vertical）被放置在页面中心时，page-wise reward最高

6.真实数据实验

通过在一个商业搜索引擎上获取的real-world dataset，我们展示了page presentation最优化框架的效果。

6.1 数据收集

我们使用一个非常小部分的搜索流量作为presentation exploration buckets。该数据会通过2013年收集。垂类搜索结果（vertical search results）的presentation会包括：news、shopping和local listings进行探索（exploration）。在exploration buckets中，web结果的顺序会保持不变，verticals会被随机地slot落到具有均匀概率的positions上。随机生成的SERPs不会受系统ranking算法的影响。如3.1节所示，当训练模型时，还需要消除page content confouding。该exploration SERP接着被呈现给正常方式交互的用户。用户在SERP上做出response，与page-wise content信息（比如：query、以及来自后端的document features）会被日志化。

6.2 方法

我们使用两个pointwise ranking模型作为baseline方法。他们使用4.1节描述的content features进行训练。第一个baseline方法在生产环境中使用（logit-rank）[23]。它会为每个垂类结果（vertical result, 包括web result）估计一个logistic regression模型：

其中，\(y_i\)是一个binary target变量，它表示结果是否被点击（\(y_i = +1\)）或被跳过（\(y_i=-1\)）（4.2节有描述），其中\(\sigma(\cdot)\)是归一化到[-1, 1]间的sigmoid link function。

第二个baseline方法使用GBDT来学习一个pointwise ranking function(GBDT-RANK)，它使用一个GBDT regressor：

我们会评估4.3节中presentation optimization框架的两种实现：Quadratic Feature Model (QUAD-PRES)和GBDT Model（GBDT-PRES）。他们使用pase-wise信息(x,p)来预测user response vector，例如：clicks和skips的vector。

在实现中，我们使用Vowpal Wabbit来学习logistic regression模型，XGBoost来学习GBDT模型。模型的超参会在一个holdout数据集上进行调参。

6.3 评估

我们使用一半的exploration SERAP作为训练集（1月到6月），其余做为测试集。它包含了上亿的pageview，从真实流量中获取。对比标准的supervised learning setup，它很难做一个无偏的离线效果评估，因为该任务存在天然交互性。这是因为offline data \(x^{(n)}, p^{(p)}, y^{(n)}\)使用一个指定的logging policy收集得到，因此我们只能观察到对于一个指定page presentation \(p^{(n)}\)的user response \(y^{(n)}\)。

在离线评估中，当给定Page Content \(x^{(n)}\)时，该算法会输出一个presentation \(p^{*(n)} \neq p^{(n)}\)，但在离线时我们观察不到user response，因此不能评估它的好坏。为了解决该问题，我们使用一个offline policy evaluation方法[28]来评估online推荐系统。它的实现很简单，可以提供一个无偏的效果估计（unbiased performance estimate），依赖于通过random exploration的数据收集。

给定通过random exploration收集到的一个关于events的stream：

其中：

• \(x^{(n)}\)：Page Content
• \(p(n)\)：对应的Page presentation
• \(Pr(p^{(n)})\)：指的是从均匀随机曝光中生成\(SERP(X^{(n)}, p^{(n)})\)的概率
• \(y^{(n)}\)：得到的User Response

对于N个offline events的平均用户满意度可以计算为：

其中：

• \(1_{\lbrace \cdot \rbrace}\)是indicator function
• \(g(y^{(n)})\)是对SERP n的用户满意度

这意味着该算法会在这些exploration SERPs上会评估：哪个presentation会与算法选的相匹配（match）；否则在离线评估中该SERP会被抛弃。

随着match沿页面往下走，match rate会下降（表1）。如果我们需要针对预测\(p^{*(n)}\)和实际\(p^{(n)}\)间的exact match，那么大部分test set会被抛弃，效果评估会趋向于具有大的variance，从而不可信。我们的评估只关注在第一、第二、第三个webpage result之上的垂类结果。注意，第一个webpage result不总是在top rank上；top rank经常被垂类结果（vertical results）占据。

表1 random exploration presentation p与predicted optimal presentation \(p^*\)间的match rate。“Until Web1”意味着p和\(p^*\)会在第1个webpage结果之上编码相同的presentation

6.4 结果

表2展示了平均page-wise用户满意度。可以看到whole-page优化方法要胜过ranking方法，由于ranking方法会使用probability ranking principle通过相关度来对结果进行排序，它会假设存在一个top-down position bias。QUAD-PRES和GBDT-PRES不会做出这样的假设，它们只会纯粹从数据中学到它们自己的result presentation principle。GBDT模型的效果好于logistic regression模型的原因是：logistic regression假设线性边界，而GBDT则是对非线性边界建模。

表2

注意：在我们的关于用户满意度metric（\(g(y)\)）的定义中，一个skip会产生negative utility \(y_i=-1\)。QUAD-PRES和GBDT-PRES通常会比baseline方法更好，这是因为会考虑retrieved items、page presentation、以及在entire SERP上的交互，不只是单个结果。presentation-blind模型会建模logit-rank和gbdt-rank，它们总是希望将最可能获得点击的结果放置在top位置上。然而，对于特定queries，人们可能倾向于跳过图片结果（graphical results）（例如：当用户真实搜索意图是information时，会跳过shopping ads）。在这样的case中，一个click会趋向于发生在top rank之下。作为对比，presentation optimization方法会同时考虑在页面上的结果和它们的position。这会生成更易觉察的结果安置（arrangement）。当我们越往下的SERP时，我们可以看到GBDT-PRES会吸引更多的点击，并具有越少的跳过。

表3、4、5展示了在Web1、Web2、Web3上的CTR。”S. Local”表示本地商业结果的单个(single)条目（比如：餐馆）；“M. Local”表示本地商业结果的多个（mutiple）条目。对于相同的vertical/genre结果，会呈现不同的size。在CTR项上，ranking方法会具有非常强的效果，因为他们会直接对高CTR进行最优化。然而，whole-page最优化方法仍具竞争力，通过考虑page-wise信息，有时会具有更好的CTR。

有意思的是，对于News vertical，对SERP上的其它结果、以及presentation并不会有过多帮助。作为对比，明知的（knowing）page-wise结果可以帮助提升top-ranked local listings上的CTR一大截。一个可能的解释是：新闻与常规网页类似，包含了丰富的文本信息以及他们的内容相关度可以通过标准ranking函数进行建模。另一方面，local listings…

7.相关工作

7.1 检索中的文档排序

7.2 综合搜索（Federated Search）

综合搜索（Federated Search或aggregated search）指的是通过一个特定垂类搜索引擎集合，在SERP上聚合结果。通常，来自不同垂类的内容是异构的，并且视觉上更丰富。综合搜索具有两个子任务：垂类选择（vertical selection）和结果呈现（result presentation）。给定一个query，vertical selection的任务会精准地决定哪个候选垂类提供可能的相关结果。在从候选垂类中获得结果后，result presentation则将垂类结果进行合并（merge）来生成相同页上的网页结果。

该paper主要关注result presentation。之前的方法将它看成是一个ranking问题[5,34,23]。特别的，[5,23]采用pointwise ranking函数来排序结果（results）和块（blocks），而[5,34]也构建了pairwise的偏好判断来训练一个ranking函数。[14]考虑了图片和电商结果（shopping results）的2-D grid presentation。比起rankedlist和2-D grid，我们的框架则允许presentation的灵活定义，允许任意的frames、image sizes、文本字体。

综合搜索结果极大地改变了SERP的景观（landscape），它也反过来要求在评估方法上做出变更。[9]提出了一个whole-page relevance的概念。他们主张Cranfield-style evaluation对于在现代SERP上量化用户的整体体验是不充分的。它建议通过为多个SERP elements分配等级来评估整页相关度（whole-page relevance）。我们的框架通过定义一个合适的用户满意度指标来体现该思想。

我们的工作与商业搜索或在线广告竞价的whole-page最优化相关，主要关注于优化搜索服务提供者的回报。我们的框架更通用，并且可以通过更改optimization objective来应用到这些问题上。

7.3 搜索行为建模（Search Behavior Modeling）

为了分发好的搜索体验，在SERP上理解用户行为很重要。眼球跟踪实验和点击日志分析观察到：用户在浏览blue-link-only的SERPs上会遵从序列顺序。更低ranked results会使用更低概率被examined到。在另一方面，这些结果也证实了probability ranking principle，鼓励搜索引擎在top上放置更多相关结果。另一方面，当使用click-through data作为相关性来评估训练ranking functions时，必须处理position bias。

由于异构结果出现在SERP上，用户在浏览结果时不再遵循序列顺序。

RL公式

Y. Wang在中，补充了RL的方式。

8. RUNTIME-EFFICIENT PAGE PRESENTATION POLICY

在本节中，我们提供了在page presentation optimization问题上的一个关于RL的新视角。第三节的方法实验是求解一个RL问题的众多可能方式之一。基于新公式，我们提供了一个policy learning方法，它可以求解相同问题，运行也很高效。最终，我们通过仿真实验展示新方法的高效性。

8.1 RL Formulation

我们引入普用的RL setup，接着将page presentation optimization转化成为一个RL问题。

在一个通用的RL setup中，一个agent会扮演着一个随机环境（stochasitc environment）的角色，它会在一个timesteps序列上顺序选择actions，最大化累积收益。它可以被看成是以下的MDP（Markov decision process）：

• state space S
• action space A

• initial state分布\(p(s_0)\)，state转移动态分布$$p(s_{t+1}

  s_t, a_t)\(，满足Markov性质：\)p(s_{t+1}

  s_0, a_0, \cdots, s_t, a_t) = p(s_{t+1}

  s_t, a_t)$$

• 一个reward function \(r: S \times A \rightarrow R\)
• 在给定state上选择actions的一个policy: \(S \rightarrow P(A)\)，其中\(P(A)\)是在A上measure的概率集合，\(\theta \in R^m\)是一个关于m个参数的vector。\(\pi_{\theta}(a \mid s)\)是在state s上采取action a的概率。一个deterministic policy是一个特例，其中：一个action a在任意state上满足\(\pi_{\theta}(a \mid s) = 1\)
• 该agent会使用它的policy来与MDP交互来给出关于states、actions、rewards的一个trajectory（\(S \times A \times R\)）：\(h_{0:T}=s_0,a_0,r_0, \cdots, s_T, a_T, r_T\)。cumulative discounted reward(return)是：\(R_{\gamma} = \sum\limits_{t=0}^{\infty} \gamma^t r(s_t, a_t)\)，其中，discount factor \(\gamma \in [0, 1]\)决定了future rewards的present value
• action-value function \(Q^{\pi} (s, a) = E[R_{\gamma} \mid s_0=s, a_0=a;\pi]\)是在state s上采用action a的expected return，接着following policy \(\pi . Q^*(s,a) = max_{\pi} E[R_{\gamma} \mid s_0=s, a_0=a; \pi]\)是最优的action-value function
• agent的目标是获得一个policy \(\pi\)，它可以最大化expected return，表示为\(J(\pi)=E[R_{\gamma} \ \pi]\)

在page presentation optimization中，agent是这样的算法：对于每个到来的search query，它决定了在对应SERP上page content的presentation。相关概念对应如下：

• (1) 一个query的page content x是state，state space为X
• (2) page presentation p是一个action，action space为P
• (3) intial state distribution \(p(x)\)通过query分布来决定。由于我们不会建模在搜索引擎与用户之间的顺序交互，因此没有state transition dynamics
• (4) reward function是在一个给定SERP上的用户满意度v，我们会通过scoring function \(v=F(x,p)\)进行估计。在state-action space \(X \times P\)中的每个点是一个SERP
• (5) 一个policy会为给定的page content x选择一个presentation strategy p。这也是公式(1)的page presentation optimization问题。 -(6)由于没有state transition，收益 \(R_{\gamma}=v\)，discount factor \(\gamma=0\)，effective time horizon \(T=0\)
• (7) 由于该policy不会在initial timestep之后起效果，action-value function等于reward function，\(Q^{\pi}=F(x,p), \forall \pi\)，因而：\(F(x,p) = Q^*(s,a)\)
• (8)expected return \(J(\pi) = E[v \mid \pi] = E_{x \sim p(x)} [E_{p \sim \pi(p \mid x)}[F(x,p)]]\)是agent希望最大化的平均用户满意度

因此，page presentation optimization问题可以被看成是一个RL问题。第3节的方法实际上是一个Q-learning方法。它首先在exploration数据上通过supervised learning来学习最优的action-value function（在我们的case中，它与reward function/scoring function相一致）F(x,p)。接着，它通过选择能最大化optimal action-value function \(\pi(\ \mid x)=1\)的action来生成一个deterministic policy，如果：p能求解\(max_{p \in P}F(x,p)\)以及\(\pi(p \mid x)=0\)

该方法的一个主要缺点是，它必须在运行时为每个query求解一个组合最优问题（combinatorial optimization problem），这对于\(F(\cdot, \cdot)\)的复杂函数形式来说很难。幸运的是，在RL中将该问题进行重塑对于runtime-efficient solutions带来了新曙光。以下我们描述了policy learning的一种解决方案。

8.2 Page Presentation的Policy learning

我们会找寻一个新的page presentation算法：

• (1) 它在runtime时很高效
• (2) 表现力足够，例如：能捕获在一个页面上的综合交互
• (3) 通过exploration buckets上收集到的数据进行离线训练

这些需求对于Web-scale online应用来说很重要，因为：

• (1) runtime高效性直接影响着用户体验
• (2) 不同的items在一个SERP上进行展示时可能会有依赖
• (3) 搜索算法的离线更新可以减少未知exploration行为的风险

一个policy-based agent会满足上述所有要求。通过experience，agent会学到一个policy \(\pi_{\theta}(a \mid s)\)而非一个value function。在runtime时，对于给定的state s，它会从\(\pi_{\theta}(a \mid s)\)中抽取一个action a，在action space上不会执行optimization。在RL场景中，action space是高维或连续的，通常采用policy-based agent。

在我们的问题setting中，agent会从exploration data中学到一个policy \(\pi_{\theta}(p \mid x)\)。对于一个search presentation policy，它更希望是deterministic的，因为搜索引擎用户更希望搜索服务是可预期和可靠的。我们可以将一个deterministic policy写成：\(p.= \pi_{\theta}(x)\)。在runtime时，给定page content x，policy会输出一个page presentation p，它会渲染内容到页面上。为了捕获在page contents间的复杂交叉，\(\pi_{\theta}(\cdot)\)可以采用非线性函数形式。

现在，我们描述presentation policy的设计和训练：

8.2.1 Policy Funciton设计

policy \(\pi_{\theta}\)采用page content vector作为input，并输出一个presentation vector。output vector会编码一个关于k个items的排列（permutation）：\(x^T=(x_1^{top},\cdots, x_k^{\top})\)，同时带有其它categorical和numerical性质（例如：image sizes、font types）。它不会去询问\(\pi_{\theta}\)来直接输出一个关于k-permutation作为\(k \times k\)的binary indicators的一个vector，我们会考虑隐式输出一个k-permutation的函数。至少有两种方法可以考虑：

• (1) 通用排序方法（Generalized ranking approach）：\(\pi_{\theta}\)会为每个item输入一个sorting score，它定义了一个顺序：可以将k个items安排在k个位置上。
• (2) 通用的seq2seq方法（Generalized sequence-to-sequence approach）：\(\pi_{\theta}\)会为每个item-position pair输出一个matching score，这需要在k个items和k个positions间的一个二部图匹配（bipartite matching）

注意，在上面的两种方法中，k个positions可以采用任意任意layout，不限于1-D list。如果\(\pi_{\theta}\)会综合考虑所有items和它们的依赖，那么两种方法都是可行的。在本文中，我们会考虑方法（1）。我们在未来会探索方法(2)。

在方法(1)中，每个item i会具有一个sorting score \(f_{\theta}(\bar{x_i})\)。该sorting scores会通过相同的function \(f_{\theta}\)来生成。feature vector \(\bar{x_i}\)对于每个item i是不同的，并且会包含整个page content feature x。这可以通过将item i的维度放置到x的前面、并将item i的原始维度设置为0来达到。也就是说：对于\(i=1, \cdots, k\)， 有\(\bar{x_i}^{\top}= (x_i^{\top}, x_1^{\top}, \cdots, x_{i-1}^{\top}, 0^{\top}, x_{i+1}^{\top}, \cdots, x_k^{\top}\)。这允许函数\(f_{\theta}\)考虑整个page content，但会为每个item输出一个不同的score。为了捕获在items间的复杂交互，每个\(F_{\theta}\)是一个LambdaMart模型（例如：GBDT模型）。

7.2.2 Policy Training

有多种方法以离线方式来训练一个policy，包括：model-based方法、off-policy actor-critic方法。这里我们使用一个model-based方法，它需要首先学到reward function和state transition dynamics。在我们的setting中，reward function是scoring function \(F(x, p)\)，不存在state transition。因此我们采用两个steps来训练policy \(\pi_{\theta}\)：

• (1) 从exploration data中学习scoring function F(x, p)
• (2) 通过最大化expected return \(J(\pi_{\theta}) = E_{x \sim p(x)} [F(x, \pi_{\theta}(x))]\)来训练policy \(\pi_{\theta}\)

注意，step(1)和step(2)涉及到optimization step \(max_{p \in P} F(x, p)\)。它允许我们选择关于F和\(\pi\)的复杂函数形式来捕获每个页面间的复杂依赖。

在RL文献中，policy通常根据policy gradient方法进行训练。也就是说，\(\pi_{\theta}\)会通过沿\(\Delta_{\theta}J\)方法上移动\(\theta\)来逐渐改进。对于deterministic policies，计算\(\Delta_{\theta}J\)是non-trivial的，正如我们的case。我们在LambdaMart中使用\(\lambda-gradients\)的思想来最优化policy。

由于我们的policy \(\pi_{\theta}\)会通过soring来生成一个permutation，我们可以将\(F(x, \pi_{\theta}(x))\)看成是一种“list-wise objective”。确实：x包含了k个items，\(p=\pi_{\theta}(x)\)定义了一个关于它们的permutation，尽管该layout并不是一个”list”。在\(F(x, \pi_{\theta}(x))\)与常规listwise IR measures间（比如：NDCG和MAP）的差异是：NDCG和MAP基于人工分配的per-item relevance，而\(F(x, \pi_{\theta}(x))\)会自动从数据中学到。对\(J(\pi_{\theta})\)最优化会转化成对listwise objective \(F(x,\pi_{\theta}(x))\)进行最优化。listwise l2r方法LambdaMart很适合该场景，它可以对大多数IR measures进行优化。

LambdaMart使用了一系列的回归树（regression trees），每个会估计\(\lambda\)。对于一个query q，\(\lambda_i \in R\)是一个分配给文档\(d_i\)的数字，它表示当前sorting score \(u_i\)会被改变多少来提升由q检索到的ranked list的NDCG。因此，\(\lambda\)是NDCG对应于soring scores的gradients。他们可以在预测的ranking中，通过交换两个documents \(d_i\)和\(d_j\)进行计算，接着观察在NDCG上的变化：

其中，。。。

8.3 仿真实验

在与第5节中相同的仿真setup下，我们实现了上述的policy-based算法。我们的目标是展示：policy-based方法可以同时学到1D和2D layouts，它的表现与原始的page presentation算法（Q-learning算法）是可比的。

表6展示了在1D和2D场景上的page presentation算法的用户满意度。由于仿真用户满意度是stochastic的，我们会在每个setup上运行1000次求平均方差和标准差。

• Ideal算法如图3(b)和4(b)所示。它会将具有最高reward的item放置到具有最高检查可能性的位置上。它会给出效果的上界。
• Q-Learning算法是QUAD-PRES。它的作用如图3(c)和4(c)所类似
• 我们包含了Policy算法的两个变种。他们在scoring function F的实现上有差异。一个使用factorized方法，其中每个item的reward会使用一个GBDT模型来估计，并且pagewise用户满意度是估计的item rewards的求和。另一个使用direct方法，其中，单个GBDT模型会使用整个SERP信息(x,p)来直接预测pasewise的用户满意度。
• RANDOM算法则将items进行随机shuffle到各个位置上。它给出了算法的下界。

在两种场景下，Q-LEARNING的效果几乎与IDEAL一样好。使用factorized F的policy与在1D case中的Q-LEARNING差不多，比在2D case中的Q-LEARNING稍微差一些。这是因为我们使用了一个policy function \(\pi_{\theta}(x)\)来逼近在Q-LEARNING中的”\(argmax_{p \in P} F(x, p)\)” global optimization过程。它会在presentation质量和runtime效率间做一个tradeoff。

scoring function在policy-based方法上扮演着重要角色。在direct方法中，F会丢失pagewise用户满意度的内部结果，它对于泛化到未见过的presentations是必要的，可以在policy training期间提供accurate feedback。factorized方法会保留在\(F=g \circ f\)的结果，因此它会比direct方法训练一个更好的policy。

参考

• 1.Beyond Ranking: Optimizing Whole-Page Presentation
• 2.Optimizing Whole-Page Presentation for Web Search

facebook在《Embedding-based Retrieval in Facebook Search》介绍了它们的推荐策略。

摘要

社交网络中的搜索（比如：Facebook）会比其它经典web搜索构成更大挑战：除了query text外，更重要的是，考虑上搜索者（searcher）的context来提供相关结果。searcher的社交图谱（social graph）是这些context的一个主要部分，这是Facebook search的独特之处。而embedding-based retrieval(EBR)被应用到web搜索引擎中已经好多年了，Facebook search仍主要基于Boolean matching模型。在本paper中，我们会讨论使用unified embedding framework来构建semantic embeddings来进行个性化搜索，该系统会在一个经典搜索系统中基于一个inverted index来提供embedding-based retrieval服务。我们讨论了一些tricks和experiences在整个系统的end-to-end optimization上，包括ANN参数tuning和full-stack optimization。最终，我们将整个过程表述成两个selected advanced topics。我们会为Facebook Search的verticals上评估EBR，并在online A/B experimenets上获取大的metrics提升。我们相信，该paper会提供给你在search engines上开发embeddinb-based retrieval systems一些观点和经验。

1.介绍

search engine是一个很重要的工具，帮助用户访问大量在线信息。在过去十年中，已经有许多技术来提升搜索质量，特别是Bing和Google。由于很难从query text上准确计算搜索意图以及文档的意义表示，大多数搜索技术基于许多term matching方法，一些case上keyword matching可以很好的解决问题。然而，semantic matching仍然是个大挑战，需要解决：期望结果可能与query text不匹配，但能满足用户搜索意图的情况。

在最近几年，deep learning在语音识别，CV、NLP上得到了巨大进步。在它们之中，embedding已经被证明是成功的技术贡献。本质上，embedding可以将ids的sparse vector表示成一个dense feature vector，它也被称为：semantic embedding，可以提供语义的学习。一旦学到该embeddings，它可以被用于query和documents的表示，应用于搜索引擎的多个stages上。由于该技术在其它领域的巨大成功，它在IR领域以及工业界也是个活跃的研究主题，被看成是下一代搜索技术（next generation search technology）。

总之，搜索引擎由二个layer组成：

• recall layer：目标是检索一个相关文档集合（低时延和低开销），通常被称为“retrieval”；
• precision layer：目标是使用复杂算法和模型对最想要的文档进行top rank，通常被称为“ranking”

embeddings理论上可以被应用到这两个layers上，但通常在retrieval layer上使用embeddings会更多些，因为它在系统更底层（bottom），通常会是瓶颈。在retrieval中的embeddings的应用被称为“embedding-based retrieval”或”EBR”。出于简洁性，EBR是一种使用embeddings来表示query和documents的技术，接着retrieval问题被转换成一个在embedding space上的NN search问题。

EBR在搜索问题中是个挑战，因为数据的规模很大。retrieval layer需要在search engine的index上处理billions或trillions的文档，这不同于ranking layers：通常它在每个session只考虑数百个documents。在embeddings的training和serving上都具在大规模的挑战。第二，不同于CV任务中embedding-based retrieval，search engine通常在retrieval layer上需要同时包括：embedding-based retrieval和term matching-based retrieval来进行打分。

Facebook search，作为一个社交搜索引擎，与传统搜索引擎相比具有独特挑战。在facebook search中，搜索意图（search intent）不只依赖于query text，同时对于发起该query的用户以及searcher所处的context具有很强的依赖。因此，facebook的embedding-based retrieval不是一个text embedding问题，而是一个IR领域的活跃的研究主题。另外，它是个相当复杂的问题，需要一起考虑：text、user、context。

为了部署EBR，我们开发了一个方法来解决modeling、serving、full-stack optimization的挑战。在modeling上，我们提出了unified embedding，它是一个two-sided model。一个side是：query text、searcher、context组成的search request，另一个side是：document。为了有效地训练该模型，我们开发了方法来从search log中挖掘训练数据，并从searcher、query、context、documents中抽取featrues。为了快速进行模型迭代，我们采用了离线评估集来进行一个recall metric评估。

对于搜索引擎，构建retrieval models具有独特挑战，比如：如何构建representative training task建模和有效、高效学习。我们调查了两个不同的方法：

• hard mining：来有效解决representing和learning retrieval 任务的挑战
• ensemble embedding：将模型划分成多个stages，其中每个stage具有不同的recall/precision tradeoff

在模型被开发后，我们需要在retrieval stack上进行开发以支持高效的模型serving。使用已存在的retrieval和embedding KNN来构建这样的系统很简单，然而我们发现这是次优（suboptimal）方案，原因如下：

• 1) 从我们的初始实验看存在巨大性能开销
• 2) 由于dual index，存在维护开销
• 3) 两个candidate sets 可能会有大量重合，整体上低效

因此，我们开发了一个混合retrieval framework来将embedding KNN与Boolean matching进行整合，来给retrieval的文档进行打分。出于该目的，我们采用Faiss来进行embedding vector quantization，并结合inverted index-based retrieval来提供混合检索系统。除了解决上述挑战外，该系统也有两个主要优点：

• 1) 它可以允许embedding和term matching进行joint optimization来解决search retrieval问题
• 2) 它允许基于term matching限制的embedding KNN, 它不仅可以帮助解决系统性能开销，也可以提升embedding KNN results的precision

search是一个multi-stage ranking系统，其中retrieval是第一个stage，紧接着还有ranking、filtering等多个stages。为了整体优化系统来返回new good results，假设在结尾有new bad results，我们会执行later-stage optimization。特别的，我们合并embedding到ranking layers中，并构建一个training data feedback loop来actively learn来从embedding-based retrieval中标识这些good和bad results。图1是EBR系统的一个图示。我们在facebook search的verticals上评估了EBR，它在A/B实验上具有大的提升。

图1 EBR系统总览

2.模型

我们将搜索检索任务公式化成一个recall optimization问题。特别的，给定一个search query，它的target result set \(T=\lbrace t_1, t_2, \cdots, t_N \rbrace\)，模型返回top K个结果：\(\lbrace d_1, d_2, \cdots, d_K \rbrace\)，我们希望最大化top k个结果的recall：

…(1)

target results是基于特定准则与给定query相关的documents。例如，它可以是user clicks的结果，或者是基于human rating的相关文档。

我们基于query和documents之间的距离计算，将一个ranking problem公式化为recall optimization。query和documents使用一个neural network model被编码成dense vectors，我们基于它使用cosine similarity作为距离metric。我们提出使用triplet loss来近似recall objective来学习neural network encoder，它也被称为embedding model。

而semantic embedding通常被公式化成在IR上的text embedding problem，它在facebook search上是低效的，它是一个个性化搜索引擎，不仅会考虑text query，也会考虑searcher的信息、以及search task中的context来满足用户个性化信息的需要。以people search为例，有上千个名为“john Smith”的user profiles，当一个用户使用”John Simth”作为query搜索时，实际的target person很可能是他的朋友或者相互认识的人。为了建模该问题，我们提出了unified embedding，它不仅会考虑上text，也会在生成的embeddings上考虑user和context信息。

2.1 评估metrics

由于我们的最终目标是：通过online A/B test，以端到端的方式来达到质量提升。开发offline metrics很重要，在在线实验前可以快速评估模型质量，从复杂的online实验setup中隔离问题。我们提出在整个index上运行KNN search，接着使用等式(1)中的recall@K作为模型评估指标。特别的，我们会抽样10000个search sessions来收集query和target result set pairs作为evaluation set，接着报告在10000 sessions上的平均recall@K。

2.2 Loss function

对于一个给定的triplet \((q^{(i)}, d_{+}^{(i)}, d_{-}^{(i)})\)，其中：

• \(q^{(i)}\)是一个query
• \(d_{(+)}^{(i)}\)和\(d_{(-)}^{(i)}\)分别是相关的positive和negative documents

triplet loss的定义如下：

…(2)

其中：

• \(D(u, v)\)是一个在vector u和v间的distance metric
• m是在positive和negative pairs间的margin
• N是triplets的总数

该loss function的意图是：通过一个distance margin从negative pair中分离出positive pair。我们发现：调整margin value很重要——最优的margin value会随不同的训练任务变化很大，不同的margin values会产生5-10%的KNN recall variance。

相似的，我们使用random samples来为triplet loss生成negative pairs可以逼近recall optimization任务。原因如下：

当candidate pool size为n时，如果我们在训练数据中对每个positive抽样n个negatives，该模型将会在recall@top1的位置上进行最优化。假设实际的serving candidate pool size为N，我们可以近似最优化recall@topK \(K \approx N/n\)。在第2.4节，我们将验证该hypothesis并提供不同positive和negative label定义的对比。

2.3 Unified Embedding模型

为了学习最优化triplet loss的embeddings，我们的模型由三个主要部分组成：

• 一个query encoder \(E_Q = f(Q)\)：它会生成一个query embedding
• 一个document encoder \(E_D = g(D)\)：它会生成一个document embedding
• 一个相似度函数 \(S(E_Q, E_D)\)：它会生成一个在query Q和document D间的分数

一个encoder是一个neural network，它会将一个input转换成一个低维的dense vector，被称为embedding。在我们的模型中，这两个encoders \(f(\cdot)\)和\(g(\cdot)\)缺省是两个独立的networks，但可以选择共享部分参数。对于相似度函数，我们选择cosine相似度，因为它是embedding learning中常用的一种相似度：

…(3)

该distance被用于在等式(2)中的loss function，因此cosine distance被定义成：\(1 - cos(E_Q, E_D)\)

encoders的inputs可以从常规的text embedding模型区分unified embedding。unified embedding可以编码textual、social以及其它有意义的contextual features来分别表示query和document。例如，对于query side，我们可以包含searcher location以及其它social connections；而对于document side，以社群搜索（groups search）为例，我们可以包括aggregated location以及关于一个Facebook group的social clusters。

大多数features是具有较高基数（cardinality）的categorical features，它们可以是one-hot或multi-hot vectors。对于每个categorical feature，会插入一个embedding lookup layer进行学习，输出它的dense vector表示，接着feed给encoders。对于multi-hot vectors，最终的feature-level embedding会使用一个关于多个embeddings的加权组合(weighted combination)。图2表示我们的unified embedding模型架构。

图2 Unified Embedding Model架构

2.4 训练数据的挖掘

对于一个检索任务，定义positive和negative labels是non-trivial问题。这里我们会基于模型的recall metric来对比一些选择方式（options）。；我们会使用click作为正样本（positive）；而对于负样本（negative），我们会使用以下的两种negatives options进行实验：

• 随机抽样（random samples）：对于每个query，我们会随机从document pool中随机抽样documents作为负样本
• 非点击曝光（non-click impressions）：对于每个query，我们会在相同的session中随机抽样这样的曝光未点击数据来生成负样本

对比起使用随机负样本（random negative），使用非点击曝光（non-click impressions）作为负样本训练的模型会具有更差的model recall：对于people embedding model来说在recall上相差55%的退化（regression）。我们认为：这是因为对于hard cases（它们在一或多个因子上会与query相match）存在负样本偏差（negatives bias），在索引index中的大部分documents都是easy cases，它们不需要与query完全匹配。将所有负样本(negatives)都变成这样的hard negatives，会将训练数据的表示变更成为真实的retrieval任务，这样可以将non-trivial bias强加到学到的embeddings中。

我们也会使用不同方式的mining positives进行实验，并发现以下的有意思的现象：

• 点击（clicks）：它使用点击结果作为正样本，因为clicks表示用户对于结果的反馈，它很可能与用户的搜索意图相匹配
• 曝光（impressions）：我们将retrieval看成是一个ranker的近似，但它执行的很快。因此，我们希望设计retrieval模型来学习那些可以被ranker排得更高的相同集合的结果。从这个意义上说，对于retrieval model learning来说，展示（show）或曝光（impressed）给用户的所有结果都等价为正例（positive）。

我们的实验结果表明，两种定义效果相当；模型使用click vs. impressions进行训练，给定相同的data volume，会导致相似的recalls。另外，我们会对click-based训练数据与impression-based数据达成一致，然而我们没有观察到在click-based模型上有额外的收益。这表明增加impression data不会提供额外的值，模型也不会从增加的训练数据量上获得收益。

我们以上的研究表明，使用点击（click）作为正样本（positive）以及随机抽样（random）作为负样本（negative）可以提供一个合理的模型表现。在它之上，我们进一步探索hard mining策略来提升模型区分相似结果间不同之处的能力。我们将在6.1节讨论。

3.特征工程

unified embedding model的一个优点是，它可以吸收除text之外的不同features来提升模型表现。我们观察到在不同的verticals上的一致性，unified embedding对比text embedding会更高效。例如，对于event search，当从text切换到unfied embeddings上会有+18%的recall提升，对于group search则会有+16%的recall提升。unified embeddings的效果高度依赖于对informative features的识别和制作。表1表明通过增加每个新的feature category到gropup embedding model（text features作为baseline）中的增量提升。在该节中，我们会讨论一些重要的features，它们会对主要的模型提升有贡献。

Text features

对于text embedding，character n-gram[7]是一个常用的方式来表示text。对比word n-grams它的优点有两方面。首先，由于有限的vocab size，embedding lookup table具有一个更小的size，在训练期间可以更高效的学习。第二，对于query侧（比如：拼写差异或错误）或者document侧（facebook存在大量内容）来说，subword representation对于out-of-vocab问题来说是健壮的。我们对比了使用character n-grams vs. word n-grams的模型发现前者的效果更好。然而，在characger trigrams的top，包括：word n-gram represantations会额外提供较小但一致的模型提升（+1.5%的recall gain）。注意，由于word n-grams的cardinality通常会非常高（例如：对于query trigrams有352M），需要进行hashing来减小embedding lookup table的size。即使有hash冲突的缺点，添加word n-ngrams仍会提供额外收益。

对于一个facebook entity，抽取text features的主要字段（field）是people entities的name、或者non-people entities的title。对于Boolean term matching技术，我们发现使用纯粹text features训练的embeddings特别擅长于解决以下两种场景：

• Fuzzy text match。例如，该模型允许学习在query “kacis creations”与”Kasie’s creations” page间的匹配，而term-based match则不能
• Optionalization。例如，对于query “mini cooper nw”，该模型可以学习检索期望的群组（expected group）：Mini cooper owner/drivers club。通过丢弃“nw”来得到一个optional term match。

Location features

Location match在许多搜索场景具有优点，比如：对于本地business/groups/events的搜索。为了让embedding模型在生成output embeddings时考虑上locations，我们添加location features到query和document side features上。对于query side，我们会抽取searcher的city、region、country、language。对于document side，我们会添加公开提供的信息，比如：由admin打标记上的explicit group locaiton。有了这些text features，该模型可以成功学到query与results间相匹配的implicit location。表2展示了在group search中，由text embedding model vs. text+location embedding model分别返回的top相似文档上的一个side-by-side的对比。我们可以看到，带location features可以学到将localtion信号混合到embeddings中，ranking文档具有相同的location，因为来自Louisville, Kentucky的searcher会有更高的位置。

4.Serving

4.1 ANN

略

4.2 系统实现

为了将embedding-based retrieval集成到我们的serving stack中，我们实现了在Unicorm（facebook的搜索引擎）中NN search的一级支持。Unicorn会将每个document表示成一个bag-of-terms，它们可以是任意strings，可以表示关于document的二元属性，通常会使用它们的语义进行命名。例如，一个用户john居住在Seattle，会具有以下term：text:john以及location:seattle。terms可以有与它们绑定的payloads。

一个query可以是在该terms上的任意一个Boolean expression。例如，以下query可以返回所有具有在名字中有john和smithe、并且居住在Seattle或Menlo Park的people:

1
2
3
4
(and (or (term location:seattle)
		(term location:menlo_park))
	(and  (term text:john)
		(term text:smithe)))

为了支持NN，我们将文档表示进行扩展来包含embeddings，每个具有一个给定的string key，并添加一个 (nn : radius ) query operator，它会匹配那些 embedding在query embedding的特定radius范围内的所有documents。

在indexing时，每个document embedding会被quantized，并转化成一个term（对于它的coarse cluster）以及一个payload（对于quantized residual）。在query time时，(nn)在内部会被重写成一个(or)的terms：它与离query embedding (probes)最近的coarse clusters相关，来匹配上些term payload在一定radius限制内的documents. probes的数目可以通过一个额外的属性：nprobe来指定，无需重写一个独立的系统，我们可以从已经存在的系统中继承所有的features，比如：realtime updates、高效的query planning及execution，以及支持multi-hop queries。

最后支持top-K NN queries，我们只会选择与query最近的K个documents，接着对query的剩余部分进行评估。然而，从实验上看，我们发现radius mode可以给出在系统效果和结果质量上更好的trade-off。一个可能的原因是，radius mode允许一个constrained NN search，但topK mode提供一个更宽松的operation，它需要扫描所有index来获得topK的结果。因此，我们在生产环境中使用radius-based matching。

4.2.1 Hybrid Retrieval

由于具有(nn) operator作为我们Boolean query language的一部分，我们可以支持hybrid retrieval表达式，它可以是embeddings和terms的任意组合。这对于model-based fuzzy matching来说很有用，可以提升像拼写变种（spelling variations）、optionalization等的cases。而从其它retrieval expression的部分进行复用和获益。例如，一个误拼的query: john smithe，它会寻找一个人名为john smith in Seattle or Menlo Park的人；搜索表达式和上面的类似。

该表达式在检索在question中的user时会失败，因为term text:smithe会在匹配document时会失败。我们可以通过(nn) operator添加fuzzy matching到该表达式中：

1
2
3
4
5
（and (or (term location:seattle)
		 (term location:menlo_park))
	   (or (and (term text:john)
	   		   (term text:smithe))
	     (nn model-141709009 : radius 0.24 :nprobe 16)))

其中model-141795009是embedding的key。在该case中，当query(john smithe) embedding和document(john smith) embedding间的cosine distance小于0.24时，target user会被检索到 。

4.2.2 Model Serving

我们可以以如下方式对embedding model进行serving。在训练完two-sided embedding model后，我们将模型分解成一个query embedding model以及一个document embedding model，接着分别对两个models进行serving。对于query embedding，我们会部署一个online embedding inference来进行实时inference。对于documents，我们会使用Spark来以batch offline的方式进行model inference，接着将生成的embeddings与其它metadata发布到forward index上。我们做这样额外的embedding quantization包括：coarse quantization、PQ，并将它发布到inverted index中。

4.3 Query和Index Selection

为了提升EBR的效率和质量，我们会执行query和index selection。我们会应用query selection技术来克服像over-triggering、huge capacity cost以及junkines increase。我们不会trigger EBR来进行特定quereis，因为EBR在没有提供额外value时会很弱，比如：一些searchers发起的easy queries会寻找一个之前搜索和点击过的的特定query。在index侧，我们会做index selection来让搜索更快。例如，我们只会选择月活用户、最近events、popular pages以及groups。

5. later-stage optimization

facebook search ranking是一个复杂的multi-stage ranking系统，其中每个stage会渐进式地改进（refine）来自前一stage的结果。在该stack的最底部是retrieval layer，其中会使用embedding based retrieval。来自retrieval layer的结果接着通过一个ranking layers的stack进行排序（sort）和过滤（filter）。在每个stage的model对通过前一layer返回的结果分布进行最优化。然而，由于当前ranking stages是为已经存在的搜索场景所设计的，这会导致由EBR返回的新结果被已经存在的rankers进行次优排序（sub-optimally ranked）。为了解决该问题，我们提出两种方法：

• Embedding作为ranking feature。对embedding相似度进一步进行propagating不仅可以帮助ranker识别来自EBR的新结果，也可以提供一个针对所有结果的通用语义相似度measure。我们探索了许多options来抽取基于embeddings的features，包括：在query和result embedding间的cosine相似度、Hadamard product、raw embeddings。从实验研究上看，cosine similarity feature比其它选项效果更好
• 训练数据反馈闭环（feedback loop）。由于EBR可以提升retrieval recall，对比term matching，它可以具有一个更低的precision。为了解决precision问题，我们基于human rating pipeline构建了一个封闭的feedback loop。特别的，我们会在EBR后对结果进行日志，接着发送这些结果到human raters来标记是否相关。我们使用这些人工标注的数据来重新训练相关性模型，从而它可以被用于过滤来自EBR中不相关的结果，只保留相关的结果。这被证明是一个有用的技术，来达到在EBR中recall提升的一个高precision。

6.高级主题

EBR需要大量研究来继续提升效果。我们研究了两个重要的embedding modeling领域：hard mining和embedding ensemble，来持续增强SOTA的EBR。

6.1 Hard mining

在文本/语义/社交匹配问题上，对于一个retrieval任务的数据空间，具有多样性的数据分布，对于一个embedding模型来说，在这样的空间上进行高效学习需要设计一个特别的training dataset。为了解决该问题，hard mining是一个主要方向，对于embedding learning来说也是一个活跃的领域。然而，大多数CV的研究用于分类任务，而搜索检索没有“classes”的概念，因此唯一的问题是已经存在的技术不一定能work。在该方向上，我们划分为两部分：hard negative mining和hard positive mining。

6.1.1 Hard negative mining（HNM)

以people search为例，当分析我们的embedding模型时，我们发现：给定一个query，从embeddings返回的topK个结果通常具有相同的名字。尽管引入了social features，该模型不会总是将target results排得比其它要高。这使我们认为：模型不能合理利用social features，这很可能是因为：负样本（negative training data）太容易(easy)，因为是随机样本，通常具有不同的名字。为了使得模型能更好地区分相似结果，我们可以使用在embedding space中与正样本（positive）更接近的样本作为hard negatives。

Online hard negative mining

由于模型训练是基于mini-batch更新的，hard negatives会以一种动态且高效的方式在每个batch中被选中。每个batch由n个positive pairs组成：（\(\lbrace q^{(i)}, d_{+}^{(i)} \rbrace_{i=1}^{n}\)）。接着对于每个query \(q^{(i)}\)，我们会它使用所有其它positive documents \(\lbrace d_{+}^{(1)}, \cdots, d_{+}^{(j)}, \cdots, d_{+}^{(n)} \mid j \neq i \rbrace\)来构建一个小的document pool，并选择具有最高相似度得分的documents作为hardest negatives来创建training triplets。允许online hard negative mining是我们模型提升的一个主要contributor。它可以极大提升跨所有verticals的embedding模型质量：

• 对于people search的recall具有+8.38%的recall
• 对于groups search具有+7%的recall
• 对于events search具有+5.33%的recall

我们也观察到：最优的setting是每个positive最多有两个hard negatives。使用超过两个hard negatives会使model quality退化。

online HNM的一个限制是：来自随机抽样（random samples）中任意的hard negative的概率可能很低，因此不能产生足够hard的 negatives。接着，我们会基于整个result pool来生成harder negatives，也就是：offline Hard Negative Mining。

Offline hard negative mining

offline hard negative mining由以下的过程生成：

• 1) 为每个query生成top K的结果
• 2) 基于hard selection strategy选择hard negatives
• 3) 使用最新生成的triplets来重新训练embedding模型
• 4) 反复进行整个过程

我们执行大量实验来对比offline hard negative mining和online hard negative mining。一个发现是：使用hard negatives进行简单训练的模型，比不过random negatives训练的模型。更进一步分析表明：“hard”模型会在non-text features上放置更多的weights，但在text match上会比”easy”模型表现更差。因此，我们会调整sampling strategy，并最终生成能胜过online HNM模型的一个模型。

第一个insight是关于hard selection strategy。我们发现，使用hardest examples并不是最好的strategy。我们会对比来自不同的rank positions中的抽样，并发现在rank 101-500间的抽样能达到最好的model recall。

第二个insight是retrieval task optimization。我们的hypothesis是：训练数据中的easy negatives的出现仍然是必要的，因为检索模型是在一个input space上操作的，它混合了不同levels的hardness数据组成。因此，我们探索一些方式来与hard negatives一起集成random negatives，包括：从一个easy model中的transfer learning。从经验上看，以下两种技术具有最好的效果：

• Mix easy/hard training：在训练中混合random和hard negatives是有益的。增加easy/hard negatives的ratio可以持续提升model recall，当在easy:hard=100:1时达到饱和。
• 从“hard”模型到”easy”模型的transfer learning：从easy到hard模型的transfer learning不会生成一个更好的模型，从hard到easy的transfer learning可以达到一个更好的model recall的提升

最后，在training data中为每个data point计算穷举KNN是非常time-consuming的，由于计算资源限制，总的模型训练时间会变得不切实际。对于offline hard negative mining算法来说，具有一个高效地top K generation很重要。ANN search是实际的解法，它可以极大减小总的计算时间。更进一步，在一个random shard上运行ANN search是足够生成有效的hard negatives的，因为我们在训练期间只依赖semi-hard negatives。

6.1.2 hard positive mining

我们的baseline embedding模型使用点击或曝光（clicks或impressions）作为正样本，它由生产系统返回。为了最大化EBR的互补增益（complementary gain），一个方向是：标识出那些由生产系统中没有被成功检索但是positive的新结果。为了该目标，我们会从searchers的activity log中的失败搜索会话（failed search sessions）中挖掘潜在的target results。我们发现，通过该方法挖掘的positive samples可以有限地帮助模型训练。只使用hard positives训练的模型可以达到与只使用点击训练数据（click training data）相同level的model recall，而数据容量只有4%。通过将hard positives和impressions作为训练数据进行组合，可以进一步提升model recall。

6.2 embedding ensemble

我们从HNM的实验发现：easy和hard样本对于EBR模型训练都很重要——我们需要hard examples来提升model precision，但easy example对于表示retrieval space来说也很重要。使用random negatives训练的模型会模拟检索数据分布，当在一个非常大的K上进行recall时可以优化更好，但当K很小时，在topK上会有很差的precision。另一方面，该模型训练的目标是优化precision，例如：使用非点击曝光作为negatives或者offline hard negatives的模型，对于更小候选集合的排序(ranking)要更好，但对于检索任务会失败（failed）。因此，我们提出了通过一个multi-stage方法，使用不同levels的hardness训练的模型进行组合：第一个stage时模型会关注recall，第二个stage时模型会专注于区分由第一个stage返回的相似结果间的不同之处。我们会使用与在[18]中的 cascaded embedding training相类似的方式，以cascaded的方式对不同level的hardness的训练进行ensemble。我们会探索不同形式的ensemble embeddings，包括：weighted concatenation、cascade model。我们发现两者很有效。

Weighted Concatenation

对于(query, document) pair，由于不同模型会提供不同的cosine相似度，我们会使用cosine similarity的加权求和作为metric来定义该pair有多接近。为了更特别，给定一个模型集合\(\lbrace M_1, \cdots, M_n \brace\)以及它们相应的weights：\(\alpha_1, \cdots, \alpha_n > 0\)，对于任意的query Q和document D，我们定义Q与D间的weighted ensemble similarity score \(S_w(Q, D)\)：

其中：

• \(V_{Q,i}, 1 \leq i \leq n\)：表示由模型\(M_i\)关于Q的query vector
• \(U_{D,i}, 1 \leq i \leq n\)：表示由模型\(M_i\)关于D的document vector

在serving时，我们需要将多个embedding vecgtors进行ensemble到单个representation中，对于query和document侧，可以满足以上的metric属性。我们可以证明：使用weighting multiplication到normalized vector的一侧，可以满足该需求。特别的，我们会以如下方式构建query vector和document vector：

…(4)

以及：

…(5)

很容易看到，在\(E_Q\)和\(E_D\)间的cosine相似度与\(S_w(Q,D)\)成比例：

…(6)

我们使用ensemble embedding进行serving，与第4节描述的方式相似。weights的选择会根据在evaluation data set上的效果进行经验选择。

在第二个stage embedding models上，我们探索了许多模型选项。实验表明，使用non-click impressions的模型可以达到最好的kNN recall（对比baseline模型，具有4.39% recall提升）然而，当使用embedding quantization时，对比于single model，ensemble会在accuracy上损失更多，因为当在online进行serving时实际收益会减小。我们发现，在embedding quantization之后具有一个最好的recall，最好的strategy会对一个相对简单的模型以及一个使用offline hard negative mining的模型进行ensemble，其中，训练负样本的hardness lebel可以被修改和调节。该ensemble候选可以轻微降低offline的模型提升，但能在online上达到极大的recall提升。

Cascade Model

不同于weighted ensemble的并行组合，cascade model会顺序地在第一stage模型后运行第二个stage模型。我们对比了不同的2-stage模型选择。我们发现，使用non-click impressions训练的模型并不是一个好的候选；整体提升会小于weighted ensemble的方法。另外，通过增加第二stage的模型，增益会随rerank的结果数而减小。然而，在第二stage上使用offline hard negative model会达到3.4%的recall提升。这对于cascade来说是一个更合适的模型候选，因为基于第一stage模型的output对于offline HNM的训练数据构建会更精准。

另外，我们探索了另一个cascade模型组合。我们观察到，当unified embedding总体上会比text embedding具有更大的model recall。它会生成新的text match failures，因为它偏向于social和location matches。为了增强模型的text matching能力，我们会采用cascade策略：使用text embedding来预选择text-matching的候选，接着使用unified embedding模型来对结果进行re-rank返回最终的top候选。这对比起单独使用unified embedding模型会达到一个极大的在线提升。

7.结论

通过使用deep learning，引入语义embeddings到search retrieval中是有长期收益的，可以解决semantic matching问题。然而，由于建模难度、系统实现以及cross-stack optimization复杂度，特别是对于一个大规模个性化社交搜索引擎来说，这是个高度具有挑战性的问题。本paper中，提出了unfied embedding来为social search建模语义，并在经典的基于搜索系统的inverted index上提出了embedding-based retrieval的实现。

第一个step是实现unified embedding模型和EBR系统。对于端到端地方式优化系统的结果质量和系统效果来说，仍有很长的路到走。我们会在模型提升、serving算法调参、以及later-stage optimzation上引入我们的经验。我们相信，这对于那些基于EBR的用户可以具有更有价值的体验。EBR的成功部署可以利用最新的语义embedding学习技术来提升检索的质量。我们沿该方向在第一个step引入了我们的进展和学习，尤其是hard mining和embedding ensemble。

对于持续提升该系统存在着许多机会。未来，主要有两个方向。一个方向是：更deep。我们会使用更高级的模型如：BERT、以及构建task-specific模型来解决问题的特定部分。我们会在不同的stages进行深入研究，包括：serving算法tuning以及ranking模型的提升，通过对full-stack failure分析来确认在不同stacks上的提升机会。另一个方向是：universal。我们会利用pre-trained text embedding模型来开发一个universal text embedding sub-model，并应用到不同的任务上。另外，我们也会跨多个用例开发一个universal query embedding模型。

参考

• 1.https://arxiv.org/pdf/2006.11632.pdf