d0evi1 Reading time ~8 minutes

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问题可以正式写成：

\[\underset{p \in P}{max} \ F(x, p)\]

它遵循在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模型：

\[y = f(x, p), \forall x \in X, p \in P\]

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

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

\[s = g(y), \forall y \in Y\]

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

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

\[s = F(x,p)= (g \circ f) (x, p) = g(f(x, p))\]

3.3 Optimization stage

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

\[\underset{p \in P}{max} g(f(x,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的加权和的某种形式：

\[g(y) = c^{\top} y\]

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

\[g(y) = \sum\limits_{i=1}^k y_i\]

其中：

  • 如果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\)为：

\[\phi^{\top} = (x^{\top}, p^{\top}, vec(xp^{\top}))\]

假设：

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

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

\[y_i = f_i(\phi) = w_i^{\top} \phi = u_i^{\top} x + v_i^{\top} p + x^{\top} Q_i p\]

…(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)写成：

\[U=(u_1,\cdots, u_k)^{\top}, \\ V=(v_1, \cdots, v_k)^{\top}, \\ Q=diag(Q_1, \cdots, Q_k)\]

其中，将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\)，那么：

\[U \in R^{k \times n}, \\ V \in R^{k \times m}, \\ X \in R^{k \times nk}, \\ Q \in R^{nk \times mk}\]

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

\[y = f(x, p) = Ux + Vp + XQ_t\]

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

\[F(x,p) = g(f(x, p)) \\ = c^{\top} Ux + c^{\top} Vp + c^T XQ_t \\ = c^{\top} Ux + a^{\top} p\]

…(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为：

\[\phi^{\top} = (x^{\top}, p^{\top})\]

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

\[y_i = h_i^{GBDT}(x, p)\]

用户满意度指标是：\(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 = \sigma(w_i^T x_i)\]

其中，\(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：

\[y_i = h_i^{GBDT}(x_i)\]

我们会评估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)}, p^{(n)}, Pr(p^{(n)}), y^{(n)})\]

其中：

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

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

\[\bar{s} = \frac{1}{N} \sum\limits_{n=1}^N \frac{g(y^{n}) 1_{\lbrace p^{*(n)} == p^{(n)}\rbrace}}{Pr(p^{(n)})}\]

其中：

  • \(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 检索中的文档排序

综合搜索（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。

参考

d0evi1 Reading time ~5 minutes

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：

\[recall@K = \frac{\sum_{i=1}^K d_i \in T}{N}\]

…(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的定义如下：

\[L = \sum\limits_{i=1}^N max(0, D(q^{(i)}, d_{+}^{(i)}) - D(q^{(i)}, d_{-}^{(i)}) + m)\]

…(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中常用的一种相似度：

\[S(Q, D) = cos(E_Q, E_D) = \frac{<E_Q, E_D>}{|| E_Q || \cdot || E_D ||}\]

…(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)\)：

\[S_w(Q, D) = \sum\limits_{i=1}^n \alpha_i cos(V_{Q,i}, U_{D,i})\]

其中：

  • \(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：

\[E_Q = (\alpha_1 \frac{V_{Q,1}}{|| V_{Q,1}} ||, \cdots, \alpha_n \frac{V_{Q,n}}{|| V_{Q,n} ||}\]

…(4)

以及：

\[E_D = (\frac{U_{D,1}}{|| U_{D,1} ||}, \cdots, \frac{U_{Q,n}}{|| U_{Q,n}||}\]

…(5)

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

\[cos(E_Q, E_D) = \frac{S_w(Q,D)}{ \sqrt{\sum\limits_{i=1}^n a_i^2} \cdot \sqrt{n}}\]

…(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模型。

参考

d0evi1 Reading time ~2 minutes

baidu在《MOBIUS: Towards the Next Generation of Query-Ad Matching in Baidu’s Sponsored Search》介绍了它们的query-ad matching策略。

摘要

为了构建一个高效的竞价搜索引擎（sponsored search engine），baidu使用一个3-layer的漏斗（funnel-shaped）结构，来从数十亿候选广告中筛选(screen)出数百万的广告并进行排序(sort)，同时需要考虑低响应时延以及计算资源限制。给定一个user query，top matching layer负责提供语义相关的ad candidates给next layer，而底层的ranking layer则会关注这些ad的商业指标（比如：CPM、ROI等等）。在matching和ranking目标(objectives)间的明显分别会产生一个更低的商业回报。Mobius项目旨在解决该问题。我们尝试训练matching layer时，除了考虑query-ad相关性外，会考虑上CPM作为一个额外的optimization目标，通过从数十亿个query-ad pairs上直接预测CTR来完成。特别的，该paper会详述：当离线训练neural click networks，如何使用active learning来克服在matching layer上click history的低效（insufficiency），以及如何使用SOTA ANN search技术来更高效地检索ads（这里的ANN表示approximate NNS）。

1.介绍

baidu每天会处理数十亿的在线用户，来处理它们的多种queries。我们都知道，广告对于所在主流商业搜索引擎来说都是主要收入来源。本paper中，主要解释在baidu search ads系统上的最新尝试和开发。如图2所示，在搜索广告中它扮演着重要角色，会与user query相关的该广告会吸引点击，当它们的广告被点击时，广告主会支付广告费。baidu竞价搜索系统的目标是，在在线用户、广告主、付费搜索平台间形成一个闭环。

图片名称

图2

通常，付费搜索引擎会通过一个two-step process来展示广告。第一个step会检索给定一个query的相关广告，下一step会基于预测user engagement来对这些ads进行rank。由于在baidu中竞价搜索引擎的商用性，我们采用一个3-layer漏斗形结构的系统。如图3所示，top matching layer负责提供与一个user query以及user的profile相关的ad候选池到next layer。为了覆盖更多的语义相关广告，此处会大量使用expansion【1,3,4】以及NLP技术【2】。底层的ranking layer会更关注商业指标，比如：cost per mile（CPM=CTR x Bid），回报（ROI），等。

图片名称

图3

然而，在matching和ranking objectives间的不同，出于多种原因会导致一个更低的商业回报。给定一个user query，我们必须采用复杂模型，并花费大量计算资源在对数百或数千个ad候选进行ranking。可能令人失望的是，ranking模型上报分析得到：许多相关ads并没有提供高CPM，从而不会被展示。为了解决该问题，Baidu Search Ads建立“Mobius”项目，它的目标是建立关于付费搜索引擎的next generation query-ad matching system。之项目旨在统一不同的 learning objectives，包括：query-ad相关度以及许多其它商业指标，并符合：低延迟、计算资源的限制，以及对用户体验的较小不良影响。

本paper中，我们介绍了Mobius-V1: 它会让matching layer除query-ad相关度外，采用CPM作为一个额外的optimization objective。Mobius-V1能为数十亿user query&ad pair精准和快速预测CTR。为了达到该目标，我们必须解决以下主要问题：

  • 1.低效的点击历史（insufficient click history）：由ranking layer所采用的原始的neural click模型会通过高频ads和user queries进行训练。它趋向于估计一个具有更高CTR的query-ad pair来展示，尽管它们具有低相关性。
  • 2.高计算/存储开销：Mobius期望预测关于数十亿user query&ad pairs的多个指标（包括：相关度、CTR、ROI等）。它天然会面对对计算资源更大开销的挑战。

为了解决上述问题，我们受active learning【34,41】的思想启发，首先设计了一个“teacher-student” framework来加大训练数据，为我们的大规模neural click model来为数十亿user query&ad pair预测CTR。特别的，一个离线数据生成器会负责要建人造query-ad pairs来给出数十亿的user queries和ad candidates。这些query-ad pairs会被一个teacher agent进行judge，它派生自原始的matching layer，并擅长于衡量关于一个query-ad pair的语义相关度。它可以在人造query-ad pairs上帮助检测bad cases（比如：高CTR但低相关度）。我们的neural click model，作为一个student，通过额外bad cases被教会（teach）来提升在长尾queries和ads上的泛化能力。为了节省计算资源，并满足低响应时延的要求，我们进一步采用大量最近的SOTA ANN search，以及MIPS（Maximum Inner Product Search）技术来高效索引和检索大量ads。

2.Baidu付费搜索的愿景（vision）

长期以来，漏斗结构是付费搜索引擎的一个经典架构。主要组件包含了：query-ad matching和ad ranking。query-ad matching通常是一个轻量级模块，它会measure一个user query与数十亿ads间的语义相关度。作为对比，ad ranking模块则关注商业指标（比如：CPM、ROI等），并使用复杂的neural模型来对数百个ad候选进行排序后展示。这种解耦结构是个明智选择，可以节约大量计算开销。另外，它可以帮助科学研究和软件工作上作为两个模块，分配给不同的团队可以最大化目标的提升。

百度的付费搜索使用一个3-layer的漏斗结构，如图3所示。top matching layer的最优化目标是最大化在所有query-ad pairs间的平均相关度：

\[O_{matching} = max \frac{1}{N} \sum\limits_{i=1}^n Relevance(query_i, ad_i)\]

…(1)

然而，根据我们在baidu付费搜索引擎表现上的长期分析，我们发现，在matching和ranking objectives间的区别/差异会导致更低的CPM（关键指标）。当在ranking layer的模型上报出：许多由matching layer提供的相关ads在搜索结果中并没有被展示，因为它们在估计时没有更高的CPM，这很令人不满意。

随着计算资源的快速增长，baidu搜索ads团队（凤巢）最近确立了Mobius项目，它的目标是baidu付费搜索的下一代query-ad matching系统。该项目的蓝图如图4所示：是统一多个学习目标，包括：query-ad相关度，以及许多其它商业指标，将它们统一到单个模块中，遵循：更低的响应延迟、有限的计算开销、以及对用户体验上较小的影响。

图片名称

图4

该paper主要是Mobius的第一版，它会首先尝试teach matching layer考虑在query-ad relevance之外，将CPM作为一个额外的最优化目标。这里我们将目标公式化：

\[O_{Mobius-V1} = max \sum\limits_{i=1}^n CTR(user_i, query_i, ad_i) \times Bid_i \\ s.t. \frac{1}{n} Relevance(query_i, ad_i) \geq threshold\]

…(2)

这里，如何为数十亿的(user-queries, ad候选) pairs精准预测CTR是个挑战。

3. 系统

3.1 Active-learned CTR模型

baidu付费搜索引擎使用DNN来进行CTR模型预测（G size）具有超过6年的历史。最近Mobius-V1采用一个新的架构。构建Mobius-V1的一种简单方法是，复用在ranking layer中的original CTR模型。它是一个大规模和稀疏的DNN，擅长emmorization。然而，在CTR预测上对于长尾部的user queries和ads它也会有一个严重的 bias。如图5所示，在搜索日志中，同一用户有两个queries：”Tesla Model 3”和”White Rose”。对于过去使用的漏斗架构，在query “tesla Model 3”和ad “Mercedes-Benz”间的相关性会在matching layer中有保证。接着，在ranking layer中的neural click模型会趋向于在query-ad pair预测一个更高的CTR。

图片名称

图5

根据我们在query log上的分析，ads和user queries具有长尾效应以及冷启动问题。因此，我们不能直接利用原始的neural click model来为数十亿长尾的user queries和ads精准预测CTR。解决这个问题的关键是：如何teach我们的模型学会：将”低相关但高CTR(low relevance but high CTR)”的query-ad pairs认为是bad cases。

图片名称

算法1

为了解决这个问题，我们提出了使用在matching layer中的原始relevance judger作为teacher，来让我们的neural click model知道“low relevance” query-ad pairs。我们的neural click model，作为student，会以一个active learning的方式从有争议的bad cases上获得关于relevance的额外知识。图6通过一个流图展示了这种方式，算法1展示了使用active learning来teaching我们的neural click model的伪码。总之，active learning的迭代过程具有两个阶段：data augmentation和CTR model learning。特别的，我们会详细描述这两个phase。

图片名称

图6

数据扩量（data augmentation）的阶段会将一个来自query logs的click history的batch加载到一个data augmenter开始。data augmenter每次会接收query-ad pairs，它会将它们split成两个sets：一个query set和一个ad set。接着，我们会对两个sets使用一个cross join操作（\otimes）以便构建更多的user query & ad pairs。假设在click history的batch中存在m个queries和n个ads，那么data augmenter可以帮助生成\(m \times n\)个synthetic query-ad pairs。在列出所有可能的query-ad pairs后，relevance judger会参与其中，并负责对这些pairs的relevance进行评分。由于我们希望发现低相关度的query-ad pairs，会设置一个threold来保留这些pairs作为candidate teaching materials。这些low relevance query-ad pairs，会作为teaching materials首次被feed到我们的neural click model，接着每个pair会通过前一迭代的updated model进行预测CTR来进行分配。为了teach我们的3-classes(例如：click、unclick和bad)的neural click model学会认识“low relevance but high CTR”的query-ad pairs，我们可能直觉上会设置另一个threshold，以便过滤出大多数low CTR query-ad pairs。然而，我们考虑另一个选项来对augmented data的exploration和exploitation进行balance。我们会采用一个data sampler，它会选择并标记augmented data，被称为这些synthetic query-ad pairs的predicted CTRs。一旦一个query-ad pair被抽样成一个bad case作为我们的neural click network，这些pair会被标记为一个额外的category，例如：bad。

在学习我们的CTR模型的阶段，click/unclick history以及labeled bad cases两者都被添加到augmented buffer中作为训练数据。我们的neural click network是一个large-scale和multi-layer sparse DNN，它由两个subnets组成，例如：user query DNN和ad DNN。如图6所示，在左侧的user query DNN，会使用丰富的user profiles和queries作为inputs，而右侧的ad DNN会将ad embeddings作为features。两个subsets会生成一个具有96维的distributed representation，每个都会被划分成三个vectors(32 x 3)。我们对user query DNN和ad DNN间的vectors 的这三个pairs使用3次inner product操作，并采用一个softmax layer进行CTR预估。

总之，我们贡献了一种learning范式来离线训练我们的neural click model。为了提升在CTR预测上对于长尾上数十亿query-ad pairs的泛化能力，neural click model(student)可以actively query到relevence model (teacher)来进行labels。这种迭代式监督学习被称为active learning。

3.2 Fast Ads Retrieval

在baidu付费广告搜索中，我们使用如图6的DNN（例如：user query DNN和ad DNN）来各自获取queries和ads的embeddings。给定一个query embedding，Mobius必须从数十亿ad candidates中检索最相关并且最高CPM值的ads，如等式(2)。当然，为每个query穷举式地计算它不实际，尽管brute-force search理论上可以发现我们要找的所有ads（例如：100% ad recall）。online services通常具有严格的latency限制，ad retrieval必须在一个短时间内完成。因此，我们采用ANN search技术来加速retrieval过程，如图7所示。

图片名称

图7

如图6所示，mapping function会结合user vectors和ad vectors来计算cosine相似度，接着该cosine值传给softmax layer来生成最终的CTR。这种方式下，cosine值和CTR是线性相关的。在模型被学到之后，它很明显是正相关或负相关的。如果它是负相关，我们可以很轻易地将它转换成正相关，需要对ad vector加个负号就行。这样，我们可以将CTR预测问题reduce成一个cosine ranking问题，它是一个典型的ANN search setting。

ANN search的目标是：对于一个给定的query object，从一个大语料中检索到“最相似”的对象集合，只需要扫描corpus中的一小部分对象就行。这是个基础问题，已经在CS界广泛研究。通常，ANN的最流行算法是基于space-partitioning的思想，包括：tree-based方法、random hashing方法、quantiztion-based方法、random partition tree方法等。对于这类问题，我们发现，random partition tree方法相当高效。random partition tree方法的一个已知实现是：”ANNOY”。

在上面的解决方案中，business-related weight信息在user vector和ad vector matching之后被考虑。实际上，这个weight在ads ranking很重要。为了解释在ranking之前的这个weight信息，我们通过一个weighted cosine问题公式化成fast ranking过程，如下：

\[cos(x, y) \times w = \frac{x^T y \times x}{||x|| ||y||} = (\frac{x}{||x||})^T (\frac{y \times w}{||y||})\]

…(3)

其中：

  • w是business related weight
  • x是user-query embedding
  • y是ad vector

注意，weighted cosine会造成一个inner product seraching问题，通常被称为MIPS。

3.2.3 向量压缩（Vector Compression）

为数十亿ads存储一个高维浮点feature vector会花费大量的disk space，如果这些features需要在内存中进行fast ranking时会造成很多问题。一个常见的解法是，将浮点feature vectors压缩成random binary（或integer） hash codes，或者quantized codes。压缩过程可以减小检索召回到一个范围内，但它会带来具大的存储优势。对于当前实现，我们会采用一外quantization-based方法（像K-Means）来将index vectors进行聚类，而非对index中的所有ad vectors进行ranking。当一个query到来时，我们首先会寻找query vector所分配的cluster，接着获取来自index属于相同cluster的ads。PQ的思路是，将vectors分割成许多subvectors，每个split独立进行cluster。在我们的CTR模型中，我们会将query embeddings和ad embeddings同时split成三个subvectors。接着每个vector被分配到一个关于cluster centroids的triplet上。例如，对于一个billion-scale ads的multi-index，可以使用\(10^9\)可能的cluster centroids。在Mobious-V1中，我们使用OPQ（Optimized Product Quantization）变种。

4.实验

略

参考

d0evi1 Reading time ~1 minute

1.摘要

我们描述了一个实时竞价算法，来进行基于效果的展示广告分配。在效果展示广告中的核心问题是：匹配campaigns到广告曝光，它可以公式化成一个受限最优化问题（constrained optimization problem）：在有限的预算和库存下，可以最大化收益目标。当前实践是，在一个曝光粒度的可追踪级别上，离线求解最优化问题（例如：placement level），并且在预计算的静态分发模式下，基于online的方式服务广告。尽管离线方法会以全局视角来达到最优目标，但它不能扩展到以单个曝光级别上进行广告分发决策。因此，我们提出一个实时竞价算法，它可以细粒度地进行曝光评估（例如，使用实时转化数据来定向用户），并且根据实时约束（例如：预算消耗级别）来调整value-based的竞价。因此，我们展示了在一个LP（线性规划：linear programming ）的primal-dual公式，这种简单实时竞价算法确实是个在线解法，通过将dual problem的该最优解作为input，可以解决原始的主问题。换句话说，在给定与一个离线最优化的相同级别的经验下，在线算法会保障离线达到的最优化。经验上，我们会开发和实验两个实时竞价算法，来自适应市场的非稳态：一个方法会根据实时约束满意级别，使用控制理论方法来调整竞价；另一个方法则会基于历史竞价静态建模来调整竞价。最后，我们展示了实验结果。

1.介绍

略

2.背景

略

3.效果展示最优化：一个LP公式

为了为在线竞价生成基本算法形式，并且确立它的最优化（optimality），我们通过对基本效果展示广告最优化看成是一个LP问题。在基础设定中，曝光会被评估，并且单独分配，在demand-side侧约束下（例如：预算限制），会以曝光分发目标的形式给出。该公式会捕获所有的理论本质，并且实际的细微差异会在第6节被讨论。假设：我们首先定义以下概念：

    1. i会索引n个曝光，j会索引m个campaigns
  • 2.\(p_{ij}\)表示曝光i分配到campaign j上的CTR，\(q_j\)表示campaign j的CPC；\(v_{ij}=p_{ij}q_{j}\)是这种assignment的eCPI
  • 3.\(g_j\)是campaign j的曝光分发目标
  • 4.\(x_{ij}\)是决策变量，它表示曝光i是否分配到campaign j（\(x_{ij}=1\)）或不是（\(x_{ij}=0\)）

我们将如下LP公式化成primal：

\[max \sum_{ij} v_{ij} x_{ij} \\ s.t. \forall j, \sum_i x_{ij} \leq g_j, \\ \forall i, \sum_j x_{ij} \leq 1, \\ x_{ij} \leq 0\]

…(6)

dual problem接着：

\[min_{\alpha, \beta} \sum_j g_j \alpha_j + \sum_i \beta_i \\ s.t. \forall i, j, \alpha_j + \beta_i \gt v_{ij} \\ \alpha_j, \beta_i \gt 0\]

…(7)

重点注意的是：由于一个曝光，

5.1 基于控制论的竞价调整（bid adjustment）

基于经典控制理论的一个简单控制设计是，使用PI controller（proportialnal-intergral controller），这是proportional-integral-derivative (PID) controller的一种常用形式。据我们所知，在缺少低层过程的先验知识时，PID controller是最好的controller【3】。正式的，假设t表示time，\(r_j(t)\)和\(r'_j(t)\)分别是winning bids在time t上的期望概率（desired probabilities）和真实概率（observed probabilities）; \(e_j(t) = r_j(t) - r'_j(t)\)是在time t时的measure error。PI controller会采用如下形式：

\[\alpha_j(t+1) \leftarrow \alpha_j(t) - k_1 e_j(t) - k_2 \int_0^t e_j(\tau) d\tau\]

…(9)

这里:

  • \(k_1\)是P项（比例增益：proportional gain）
  • \(k_2\)是I项（积分增益：integeral gain）

两者都是待调参数。实际中，出于在线计算效率和曝光到达的离散性，time t不需要实时跟踪。假设：\(t \in [1, \cdots, T]\)会索引足够小的时间间隔（time intervals），其中T是在online bidding的整个duration内的intervals数目；在每个interval之后只会更新\(\alpha_j\)。

另一个更简单的控制方法：受水位标（Waterlevel）【4】的启发，在资源分配问题（resource allocation problems，比如：在保留位置上分发展示广告）上，有一个在线/快速近拟算法。waterlevel-based方法的更新公式：

\[\alpha_j(t+1) \leftarrow a_j(t) e^(\gamma (\frac{x_j(t)}{g_j} - \frac{1}{T})), /forall j\]

…(10) 其中：

  • \(x_j(t)\)表示获胜的campaign j在time interval t期间的曝光数；
  • 指数因子\(\gamma\)：是一个可调参数，它控制着算法根据erroe meaured \(\frac{x_j(t)}{g_j} - \frac{1}{T}\)来控制有多快。如果初始的\(\alpha_j\)（例如：由offline dual求解得到）对于未来的运行来说确实是最优的，我们希望将\(\gamma\)变为0

注意，在error项\(\frac{x_j(t)}{g_j} - \frac{1}{T}\)中，我们假设知道在time intervals上具有一个均匀的曝光流（impression stream）。该假设并不重要，因为它可以通过添加一个时间依赖先验（time-dependent prior）来被很容易地移除。另外，Water-based方法的更新具有一个很nice的链条特性：

\[\alhpa_j(t+1) = \alpha_j(t) exp(\gamma(x_j(t) / g_j - 1/T)) \\ = \alpha_j(t-1) exp(\gamma ( \sum\limits_{\tau=t-1}^t x_j(\tau) / g_j - 2/T)) \\ = ... \\ = a_j(1) exp(\gamma(\sum\limits_{\tau=1}^t x_j(\tau) / g_j - t/T))\]

…(11)

5.2 Model-based的竞价调整（Bid Adjustment）

我们的model-based方法从现代控制理论【9】中抽理出来，其中系统（在我们的case中是竞价市场）状态的一个数学模型是，用于生成一个控制信号（在我们的case为：竞价调整\(\alpha_j\)）。更正式的，我们会假设：在胜选竞价（winning bids）上有一个参数分布P：

\[w \sim P(\theta)\]

…(12)

其中，\(\theta\)是模型参数。我们使用泛化形式，因为一个合适参数选择应通过数据来进行经验调节，并且可能是domain-dependent的。一些合理的选择是：在winning bids【13】的square-root（均方根）上有一个log-normal分布【7】以及一个Gaussian分布，但两者都不可以天然处理negative bids。在我们竞价调整的加法形式如等式（3），一个negative bid \(b_{ij} = v_{ij} - \alpha_j < 0\)意味着：竞价者（bidder）不能满足由acquiring impression i的最小间隔，因而展示了整个value book的一个hidden part。我们：

  • 将概率分布函数PDF表示成\(f(w;\theta)\)
  • 将累积分布函数CDF表示成\(F(w;\theta)\)
  • inverse CDF(逆函数)表示为\(F^{-1}(p; \theta)\)。
  • 分布参数\(\theta\)的MLE由历史胜选竞价{w}的充分统计得到，它可以在线更新可读（例如：第一，第二时刻）。有了bidding landscape的静态模型后，我们可以通过使用bidding \(b_{ij} = v_{ij} - \alpha_j\)生成获胜概率：
\[p(w \leq b_{ij}) = \int_{-\inf}^{b_{ij}} f(w;\theta) dw = F(b_{ij}; \theta)\]

假设：对于所有impression i来说，winning bids会遵循一个单一分布是不现实的（通常是一个mixture model）。因此对于来自一个位置（placement）的一组同质曝光（homogeneous impressions）来说，会满足分布\(P(\theta)\)。实际上，我们会使用impression granularity level来安排\(P(\theta)\)，它同时具有supply-side和demand-side的拘束。现在假设我们只关注异构曝光（homogeneous impressions）。

我们希望将学到的胜选概率（winning probability）与未来的竞价行为相联系，来达到分发目标。假设：\(r_j\)是赢得剩余曝光的期望概率，表示campaign j满足目标\(g_j\)。在未来曝光i上，会尝试使用\(b_{ij} = F^{-1}(r_j;\theta)\)来竞价。然而，这种纯基于目标的方法，在使用feedback来显式控制future bids时会失败，因为会丢掉closed-loop controller（PID controller）上具有的稳定性、健壮性等优点来建模不确定性。换句话说，纯目标驱动的方法不会学到过往竞价（past bidding）做出的errors。我们提出一个model-based controller来解决该限制，并且利用由bidding landscape学到的知识。竞价调整的公式如下：

\[\alpha_j(t+1) \leftarrow \alpha_j(t) - \gamma(F^{-1}(r_j(t)) - F^{-1}(r_j^' (t))), \forall j\]

…(14)

其中，\(r_j(t)\)和\(r_j^'(t)\)分别是在time t上的期望胜选概率和真实胜选概率。乘法因子\(\gamma\)是一个可调参数，它控制着在对应于errors的一次更新上做出的rate。对于经典方法，model-based方法不会直接操作measured errors；作为替代，它会通过一个compact model \((P(\theta))\)来将一个error signal（获胜概率error）转换成一个control signal（updated \(\alpha_j\)）。

当缺少一个好的参数时这种方式不好，一个非参数模型在也可以使用。我们需要维护一个empirical CDF作为一个two-way lookup table \((F(w;D)和F^{-1}(p;D))\)来进行online inference。

6.效果展示广告优化：一个实际公式

我们已经开发了在算法1中的基本算法形式，并确定了在给定稳定曝光到达假设下的最优解。在基本的LP公式下，constraints会被编码成impression分发目标，曝光会被单独进行分配和评估。我们将LP问题直接使用商业约束进行公式化，主要是：demand-side预算限制以及supply-side的库存量；接着讨论在真实系统中要考虑的几个方面。假设我们首先更新以下概念：

  • 1.i表示索引n个impression groups（比如：placements），在一个group中的impressions会被看成是不可区分的，因而对于给定一个campaign来说会生成一个相同的CTR估计。
  • 2.\(g_j\)是对于campaign j的预算最高限额（budget cap）
  • 3.\(h_i\)表示对于group i来说的曝光量限制或预测
  • 4.\(x_{ij}\)表示：来自group i分配给campaign j的曝光数
  • 5.\(w_i\)：表示来自group i的每次曝光的（traffic acquisition）开销（cost），例如：在Vickrey acution中的第二价格

注意：我们会在同一个解法中做出CTR预测和supply constraint。避免刮脂效应(cream-skimming)问题很重要。如果CTR预估比起即时的supply constraint来说更细粒度，一个optimization方法是，在每个impression group总是分配impressions更高的CTR机会，这很明显是不现实的。我们会引入cost term \(w_i\)来泛化生成optimization给其它players，例如：参与到一个second-prece auction的一个ad network或者demand-side平台。primal LP变为：

\[max_x \sum_{i,j} (v_{ij} - w_{i}) x_{ij} \\ s.t. \forall j, \sum_j v_{ij} x_{ij} \leq g_j, \\ \forall i, \sum_j x_{ij} \leq h_i, \\ x_{ij} \gt 0\]

接着该dual problem是：

\[min_{\alpha, \beta} \sum_j g_j \alpha_j + \sum_i h_i \beta_i \\\]

6.实验评估

参考

d0evi1 Reading time ~3 minutes

2015年yahoo在《Smart Pacing for Effective Online Ad Campaign Optimization》提出了一种smart pacing的策略。

0.摘要

在定向广告中，广告主会在预算范围内在分发约束的情况下最大化竞价效果。大多数广告主通常喜欢引入分发约束（delivery constraint）来随时间平滑地花费预算，以便触达更广范围的受众，并具有持续性的影响。对于在线广告，由于许多曝光会通过公开竞拍(public auctions)来进行交易，流动性（liquidity）使得价格更具弹性，在需求方和供给方间的投标景观（bid landscape）会动态变化。因此，对于同时执行平滑步调控制（smooth pacing control）并且最大化竞价效果很具挑战。本文中提出了一种smart pacing方法，它会同时从离线和在线数据中学习每个campaign的分发步调（delivery pace），来达到平滑分发和最优化效果目标。我们也在真实DSP系统中实现了该方法。实验表明，在线广告活动（online ad campaign）和离线模拟都表明我们的方法可以有效提升campaign效果，并能达到分布目标。

1.介绍

在线广告是一个数十亿美金的产业，并且在最近几年持续两位数增长。市场见证了搜索广告（search advertising）、上下文广告（ contextual advertising）、保证展示广告(guaranteed display advertising)、以及最近的基于竞价的广告的出现。我们主要关注基于竞价的广告（auction-based），它具有最高的流动性，例如：每次ad曝光可以通过一个公开竞价使用一个不同的价格来交易。在市场中，DSPs（Demand-Side Platforms ）是个关键角色，它扮演着大量广告主的代理，并通过许多direct ad-network 或者RTB（实时竞价）广告交换来获得不同的广告曝光，来管理ad campaigns的整个welfare。一个广告主在一个DSP上的目标可以归为：

  • 达到分发和效果目标：对于品牌活动（branding campaigns），目标通常是花费预算来达到一个广泛受众、同时使得活动效果尽可能好；对于效果活动（performance campaigns），目标通常是达到一个performance目标（比如：eCPC <= 2美元），并同时尽可能花费越多预算。其它campaigns的目标通常在这两个极端之内。

  • 执行预算花费计划(budget spending plan)：广告主通常期望它们的广告会在购买周期内平滑展示，以便达到一个更广的受众，可以有持续性影响，并在其它媒介上（TV和杂志）增加活动。因此，广告主可以定制自己的预算花费计划（budget spending plans）。图1给出了budget spending plan的两个示例：平均步调（even pacing）和基于流量的步调（traffic based pacing）。

图片名称

图1 不同的预算花费计划

  • 减少创意服务开销（creative serving cost）：除了通过由DSPs负责的开销外，也存在由第3方创意服务提供商负责的creative serving cost。现在，越来越多的广告活动会以视频或富媒体的形式出现。这种类型的曝光的creative serving cost可以与优质存货开销（premium inventory cost）一样多，因此，广告主总是愿意减少这样的开销，并且来高效和有效地分发曝光给合适的用户。

3.问题公式化

我们关注两个campaign类型： 1) 品牌广告（branding campaigns） 2) 效果广告（performance campaigns）。其它campaign类型位于两个之间。这些类型的campaign可以具有它自己唯一的budget spending plan。我们首先将该问题公式化来解决，接着给出我们的解法。

3.1 前提

假设Ad是一个ad campaign，B是Ad的预算，G是Ad的效果目标。spending plan是一个随着由K个time slots构成的预算序列，表示在每个time slot上待花费的期望预算数目。我们将AD的spending plan表示为：

\[B = (B^{(1)}, \cdots, B^{(K)})\]

其中，\(B^{(t)} >= 0\)并且 \(\sum_{t=1,\cdots,K} B^{(k)} = B\)。假设\(Req_i\)是由一个DSP接受到的第i个ad request。如第2节所述，我们使用概率节流（probabilistic throttling）来进行budget pacing control。我们表示为：

  • \(s_i \sim Bern(r_i)\)：该变量表示：在\(Req_i\)上Ad是否参与竞价。其中：\(r_i\)是在\(Req_i\)上的point pacing rate。\(r_i \in [0, 1]\)表示Ad参与\(Req_i\)上竞价的概率。

  • \(w_i\)：该变量表示在\(Req_i\)上参与该次竞价时是否赢得该Ad。它会依赖于通过竞价最优化模块（bid optimization module）给出的竞价\(bid_i\)

  • \(c_i\)：当Ad服务于\(Req_i\)时的广告主开销。注意：开销包括inventory cost和creative serving cost。

  • \(q_i \sim Bern(p_i)\)：该变量表示当Ad服务于\(Req_i\)时，用户是否会执行一些期望的响应（例如：click）。其中\(p_i = Pr(respond \mid Req_i, Ad)\)是这些响应的概率。

  • \(C = \sum_i s_i \times w_i \times c_i\)是ad campaign Ad的总开销。

  • \(P=C/\sum_i s_i \times w_i \times q_i\)：ad campaign Ad的效果（performance）（例如：当期望响应是点击时的eCPC）

  • \(C = (C^{(1)}, \cdots, C^{(k)})\)：在K个time slots上的spending pattern，其中\(C^{(t)}\)是第t个time slot的开销，\(C^{(t)} >= 0\)并且\(\sum_{t=1,\cdots,K} C^{(k)} = C\)

给定一个广告活动Ad，我们定义：\(\Omega\)是penalty(error) function，它会捕获spending pattern C是如何偏离spending plan B。值越小表示对齐（alignment）越好。作为示例，我们会将penalty定义如下：

\[\Omega (C, B) = \sqrt \frac{1}{K} \sum\limits_{t=1}^K (C^{(t)} - B^{(t)})^2\]

…(1)

3.2 在线广告campaign最优化的Smart Pacing问题

广告主会花费预算，执行spending plan，并同时最优化campaign效果。然而，这样的一个抽象的多目标最优化问题，会有多个帕累托最优解（Pareto optimal solutions）。在真实场景中，广告主通常会为不同campaigns对这些目标定制优化级。对于品牌广告（branding campaigns），广告主通常会将花费预算放在最高优化级，接着是spending plan，而对效果并不很关注。在serving time时（例如：ad request time），由于我们使用概率节流（probabilistic throttling），我们完全可以控制的唯一东西是\(r_i\)。因而，对于没有指定效果目标的ad campaigns的smart pacing问题(smart pacing for ad campaigns without specific performance goals)定义为：决定\(r_i\)的值，以便以下的测算是最优的：

\[\underset{r_i}{min} P \\ s.t. C = B, \Omega (C,B) \leq \epsilon\]

…(2)

其中，\(\epsilon\)定义了违背spending plan的容忍度。相反的，对于效果广告（performance campaigns）具有指定的效果目标，达成效果目标是top优先级。此时坚持spending plan通常是低优先的。我们将smart pacing for ad campaigns with specific performance goals的问题定义为：决定\(r_i\)的值，以便以下测算是最优的：

\[\underset{r_i}{min} \Omega(C, B) \\ s.t. P <= G, B - C \leq \epsilon\]

…(3)

其中，\(\epsilon\)定义了没有花光所有预算的容忍度。由于市场的动态性，对于两个单目标最优化问题很难解决。在工业界已存在被广泛使用的方法，只会捕获效果目标，或者只会捕获预算花完目标。达到效果目标的一个示例是：对retargeting beacon触发ad requests，总是竞价。不幸的是，避免过度消费（overspending）或者欠消费（underspending）是无保障的。对于平滑步调控制（smooth pacing control）的另一个示例是，引入一个全局pacing rate，以便ad requests具有相同的概率被一个campaign竞价。然而，这些已经存在的方法没有一个可以解决我们公式化的smart pacing问题。为了解决该问题，我们研究了流行的campaign setups，并做出一些关键观察（可以启发我们的解法）：

  • CPM campaigns：广告主对于每个曝光会会付定固定数目的钱。对于品牌广告主（branding advertisers），campaign最优化的定义如公式2所示。只要预算可以被花费，并且spending pattern会随plan安排，高响应广告请求会比低响应的具有一个更高的point pacing rate，以便效果可以被最优化。对于效果广告主（performance advertisers，例如：eCPC、eCPA为目标），campaign最优化的定义如公式3所示。很明显，高响应的ad requerest应具有更高的point pacing rate来达到performance目标。

  • CPC/CPA campaigns：广告主会基于clicks/actions的绝对数目进行付费。显式效果目标是，保证当代表广告主进行竞价时，DSP不会损失钱。因此，这种optimzation的定义为等式(3)。授于高responding ad request以高point pacing rates，从广告主和DSP的视角来说会更有效：广告主会在creative serving cost上花费更少，而DSP可以节省更多ad机会来服务其它campaigns。

  • 动态CPM campaigns：DSP会为每个曝光花费一个动态数目的钱，而非固定。这些campaigns通常具有指定效目的目标，以便最优化问题会落在等式(3) 中。与CPC/CPA campaigns相似，高responding ad requests会更受偏爱，以便减少creative serving cost以及节约ad机会。

3.4 解法汇总

受这些观察的启发，我们开发了新的heuristics来求解smart pacing问题。该heuristics尝试找到一个可行解，它会满足如等式2或3定义的所有constraints，接着进一步通过feedback control来最优化目标。

  • 首先从离线服务日志中构建一个response prediction模型来估计\(p_i = Pr(respond \mid Req_i, Ad)\)，它会帮助我们区分高响应广告请求 和 低响应广告请求。
  • 第二，我们会通过将相似的响应请求group在一起来减小solution space，并且在相同group中的请求会共享相同的group pacing rate。使用高responding rates的groups会具有高的pacing rates（比如图2(a)中的蓝色箭头）。
  • 第三，我们会开发一个新的control-based的方法来从在线feedback data中学习，并能动态调整group pacing rates来逼近最优解。

不失一般性，我们假设campaign setup是具有/没有一个eCPC目标的CPM计费。我们的方法可以应用到其它计费（billing）方法上 ，效果广告或者其它grouping策略，比如：基于\(p_i/c_i\)的grouping。（期望的response per cost）

图片名称

图2 概率节流（Probabilistic Throttling） vs. 竞价修改（Bid Modification）的因子依赖图。灰色的因子涉及到budget pacing control。在pacing rate和response rate间添加依赖是其中一个关键点.

4.response预测

我们的解法依赖于一个准确的response prediction模型来预估\(p_i\)。如第2节，有许多文献解决该问题。这里我们简单描述了如何执行该预估。我们会使用在(2,11)中的方法，并基于它做出一些改进。在这种方法中，我们首先利用在数据中的层次结构来收集具有不同间隔的response feedback features。例如，在ad侧，从root开始，接着一层接一层是：advertiser category，advertiser，campaign，最后是ad。在层次结构的不同levels上的历史响应率（historical response rates）可以当作features来使用机器学习模型（LR、gbdt等）来给出一个\(p_i\)的原始预估（raw estimation），称为\(\hat{p}_i\)。接着我们使用属性（比如：用户的age、gender）来构建一个shallow tree。树的每个叶子节点标识一个关于ad requests的不相交集合，它可以进一步划分成具有不同平均响应率的子集。最后，我们会在叶子节点\(Req_i\)内对\(\hat{p}_i\)进行微调，使用一个piecewise linear regression来估计最终的\(p_i\)。该scheme会生成一个公平的accurate response prediction。

5.control-based的解法

在一个在线环境中，很难达到完全最优解来解决等式（2）和等式（3）的问题。我们采用启发法来减小原始问题的解空间。更特别的，使用第4节中描述的response prediction模型，相似的，responding ad requests会分组到一起，他们会共享相同的group pacing rate。不同分组会具有不同的group pacing rates来影响在高responding ad request groups上的偏好。原始问题（求解每个\(r_i\)的point pacing rate）会简化成求解一个group pacing rates的集合。我们会采用control-based的方法来调节group pacing rates以便online feedback data可以立即用于campaign最优化。换句话说，group pacing rates会通过campaign的生命周期动态调节。出于简洁性，在本文其它地方，pacing rate和group pacing rate会相通，我们会在第l个group的group pacing rate表示为\(r_l\)。

5.1 层级表示（Layered Presentation）

对于每个ad campaign，我们会维护一个层级数据结构，其中每层对应于一个ad request group。我们会以层级数据结构来保存每个ad request group的以下信息：

  • 平均响应率（通常是：CTR、AR等，它来自response prediction模型）
  • ad request group的优先级
  • pacing rate（例如：在ad request group中对一个ad request的竞价概率）
  • campaign在该ad request group中在最新time slot上的花费

这里的原则是：

  • 1) 对应于高响应ad request groups的layers应具有高优先级
  • 2) 高优先级layer的pacing rate应会比一个低优先级layer要更小

对于每个campaign，当DSP接收到一个合格的ad request时，它会首先决定：该ad request 会落在哪个ad request group上，指的是相应的layer来获得该pacing rate。DSP接着会代表campaign来竞价，它的概率会等于由一个preceding bid 最优化模块给出的retrieved pacing rate。

5.2 Online Pacing Rate调节

我们基于实时反馈，来采用一个control-based方法来调节每层的pacing rate。假设我们具有L个layers。对于每个layer，由response prediction model给出的response rate预估是：

\[p=(p_1, \cdots, p_L)\]

这里，如果期望的response是click，那么预估的每层的eCPC是:

\[e(e_1, \cdots, e_L)\]

其中：\(e_i = \frac{CPM}{ 1000 \times p_i}\)。假设每层的pacing rate在第t-1个time slot上是：

\[r^{(t-1)} = (r_1^{(t-1)}, \cdots, r_L^{(t-1)})\]

那么，每个layer的spending为：

\[c^{(t-1)} = (c_1^{(t-1)}, \cdots, c_L^{(t-1)})\]

对于将要到来的第t个 time slot会基于campaign目标，control-based的方法会预估：

\[r^{(t)} = (r_1^{(t)}, , \cdots, r_L^{(t)})\]

图片名称

图3 加速budget spending的一个示例

5.2.1 没有performance目标的Campaigns

我们首先描述对于没有指定效果目标的ad campaigns的微调算法。对于这种campaign类型，首要目标是花费预算，并根据budget spending plan进行安排。因而，在每个time slot的end，算法需要决定在下一个time slot中的预算量，并调整layered pacing rates来花费该量。

在下一time slot中的待花费预算，由当前预算花费状态来决定。给定一个ad campaign，假设它的总预算是B，budget spending plan是\(B = (B^{(1)}, \cdots, B^{(K)})\)，在运行m个time slots后，剩余预算变为\(B_m\)。我们需要决定在每个剩余time slots中的花费，表示为\(\hat{C}^{m+1}, \cdots, \hat{C}^{(K)}\)，以便总预算可以花完，penalty最小。

\[\underset{\hat{C}^{(m+1)}, \cdots, \hat{C}^{(K)}}{arg min \Omega} \\ s.t. \sum\limits_{t=m+1}^k \hat{C}^{(t)} = B_m\]

…(4)

其中，如果我们采用等式（1）的\(\Omega\)定义，我们具有以下的最优化公式：

\[\hat{C}^{(t)} = B^{(t)} + \frac{B_m - \sum_{t=m+1}^K B^{(t)}}{K - m}\]

…(5)

其中，\(t=m+1, \cdots, K\)。我们会触发该细节：由于页面限制，如何估计\(\hat{C}^{(t)}\)。在在线环境中，假设在最新的time slot中的实际花费是\(C^{(t-1)}\)，我们定义\(R=\hat{C}^{(t)} - C^{(t-1)}\)是residual，它可以帮助我们来做出调整决策。

图片名称

算法1

算法1给出了adujstment是如何完成的。假设：index L表示最高优先级，index 1表示最低优先级，假设\(l'\)是具有非零pacing rate的最后一层。

  • 如果R=0, 则不需要做adjustment。
  • 如果R>0，这意味着需要加速分发，pacing rates会以一种自上而下的方式进行调整。

从第L层开始，每一层的pacing rate会随层数一层层增加，直到第\(l'\)层。第5行会计算当前层的期望pacing rate，为了offset R。当第\(l' \neq 1\)时并且它的updated pacing rate \(r_{l'}^{(t)} > trial \ rate\)时，我们给第\(l' - 1\)层一个trial rate来准备进一步加速，如果R< 0，这意味着分发会变慢，每一层的pacing rate会以自底向上的方式减小，直接R是offset。第11行会生成当前layer到offset R的期望的pacing rate。假设l是最后要调的layer，\(l \neq 1\)和它的新的pacing rate \(r_l^{(t)} > trial \ rate\)，我们会给出第\(l-1\)层的trail rate来准备进一步加速。图4是一个分发如何变慢 的示例。

图片名称

图4 一个减少budget spending的示例

我们注意到，在在线环境中，该greedy策略会尝试达到等式（2）的最优解。在每个time slot内，它会努力投资inventories，并在总预算和speding plan约束下具有最好的效果。

5.2.2 具有效果目标的Campaigns

对于指定效果目标的campaigns（例如：eCPC <=2美元），pacing rate adjustment是有点复杂。很难预见在所有未来time slots内的ad request traffic，并且response rate分布可以随时间变化。因此，给定预算花费目标，利用在当前time slot中的所有ad requests，它们满足效果目标，不是等式（3）的最优解。算法2描述了对于这种类型的campaigns如何来完成adjustment。我们采用heuristic来进一步基于效果目标进行adjustment，它会添加到算法1中。

图片名称

算法2

如果在算法1后的期望效果不满足效果目标，pacing rates会从低优先级layers one-by-one的减少，直到期望效果满足目标。第7行会生成current layer的期望pacing rate，并使整体期望eCPC满足目标。在第2行，第4行的函数\(ExpPerf(c^{(t-1), r^{(t-1)}, r^{(t)}, e, i}\)会估计layers \(i, cdots, L\)的期望联合eCPC，如果pacing rates会从\(r^{(t-1)}\)调整到\(r^{(t)}\)，其中，\(e_j\)是layer j的eCPC。

\[ExpPerf(c^{(t-1)}, r^{(t-1)}, r^{(t)}, e, i) = \frac{\sum\limits_{j=i}^L \frac{c_j^{(t-1) \times r_j^{(t)}}{r_j^{(t-1)}}}}{\sum\limits_{j=i}^L} \frac{c_j^{(t-1)} \times r_j^{(t)}}{ r_j^{(t-1)} \times e_j }}\]

…(6)

5.3 Layers的数目，初始化和Trial Rates

设置layers的数目，intial和trial pacing rates很重要。对于一个新的ad campaign，它没有任何分发数据，我们在DSP中标识出最相似的最已存在ad campaigns，并估计一个合适的全局pacing rate \(r_G\)，我们期望新的campaign可以花完它的预算。接着layers的数目设置为\(L = [\frac{1}{r_G}]\)。我们表示：一个合适数目的layers要比过多数目的layer更重要：

  • 1) 如果有许多层，每个layer的分发统计并不重要
  • 2) 从系统角度看，过多数目的layers会使用更多宽带和内存

一旦layers的数目决定后，我们会在第一个time slot上运行全局pacing rate \(r_G\)。我们将该step称为一个intialization phase，这里分发数据可以被收集。我们将相同数目的曝光，基于它们的预测response rate来来标识layer分界，将它们分组（group）到期望数目的layers上。在下一time slot上，每一layer的pacing rate会基于在下一time slot的计划预算来重新分配，高响应layers会具有1.0的rates，而低响应layers将会具有0.0的rates。

在adjustment算法中，具有非零pacing rate相互挨着的直接连续的layer，会分配一个trial pacing rate。目标是在该layer收集分发数据，并准备将来加速。该trial rate假设相当低。我们通过保留预算的一个特定比例\(\lambda, e.g. \lambda=1%\)，生成这样一个rate，来在下一time slot中花费。假设trial layer是第l层，下一time slot上的预算是\(\hat{C}^{(t)}\)，我们会在至少一个time slot（初始阶段）上具有该layer的历史花费和pacing rate，trial pacing rate会生成：\(trial \ rate = r_l^{(*)} \times \frac{\lambda \times \hat{C}^{(t)}}{c_l^{(*)}}\)，其中：\(c_l^{(*)}\)和\(r_l^{(*)}\)是第l层的历史花费，以及pacing rate。

快速总结下，我们采用一个基于predicted response rate生成的关于所有ad requests的分层表示，并在每个layer level上执行budget pacing control来达到分发和效果目标。在当前time slot上的预算，以及剩余预算会被考虑来计算在下一time slot上的layered pacing rates。我们也尝试另一种方法来控制一个threshold，以便超过该threshold的predicted response rate的ad requests可以竞价。这种方法的缺点是不能令人满意。主要 原因是，ad requests通常不随response rate平滑分布，因此，在单个threshold上很难实现平滑控制。

6.实验评估

参考