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。

参考

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:

(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到该表达式中:

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

参考

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.实验

参考

华为在《PAL: a position-bias aware learning framework for CTR prediction in live recommender systems》提出了一种解决position-bias方法。

摘要

在推荐系统中精准预测CTR很重要。CTR模型通常基于来自traffic logs收集得到的feedback训练得到。然而,在user feedback中存在position bias,因为用户在一个item上的点击(clicks)不仅仅只因为用户喜欢这个item,还有可能是因为它具有一个较好的position。解决该问题的一种方式是:在训练数据中将position建模成一个feature。由于很简单,这种方法在工作界被广泛应用。然而,使用不同的default position值可能会导型完全不同的推荐结果。因些,该方法会导致次优(sub-optimal)的线上效果。为了解决该问题,在该paper中,我们提出了一种Position Aware Learning framework(PAL)来解决该问题。它可以建模在offline training中的position-bias,并在online inference时不使用position information。我们在一个三周的AB test上进行实验,结果表明,PAL的效果在CTR和CVR(转化率ConVersion Rate)指标上要比baseline好3%-35%。

1.介绍

实际生产环境中的推荐系统包含两个过程:offline training和online inference,如图2所示。在offline training中,会基于从traffic logs中收集到的user-item interaction信息训练一个CTR预估模型。在online inference中,训练好的模型会部署到真实线上来做出预测。

图片名称

图2 不同position上的CTR

有个问题是:user-item interaction是受展示该item的positions影响的。在[14]中,CTR会随着display position而快速下降。相似的,我们也在华为maintream APP store上观察到了这样的现象。如图1所示,不管是整体的App Store (图1(a)),或是单个特定App(图1(b)),我们可以观察到:normalized CTR会随着position显著下降

图片名称

图1 生成推荐的workflow

这样的观察表明,用户点击某个item可能不仅仅是因为喜欢这个item,还有可能是因为在一个好的position上。因此,从traffic logs中收集得到的training data包含了positional bias。我们将该现象称为“position-bias”。作为CTR信号的一个重要因子,在offline training中将position-bias建模到CTR预测模型中是很必要的。

尽管提出了许多click models来建模training data中的position-bias【1-3】,在现实问题中(在online inference中position信息是不提供的)这样的研究很有限。一个实用(practical)的方法是逆倾向加权(inverse propensity weighting)【15】。在该方法中,在position信息使用一个用户定义的转换,接着该转换后的值固定。然而,如【10】所述,对于position信息很难设计一个好的转换,这会产生比自动学到的转换更差的效果。因此,【10】的作者提出在训练数据中将position建模成一个feature,这种方法在工业界广泛使用。特别的,在online inference中使用一个default position value来预测CTR,因为actual position information在那时并没提供。不幸的是,使用不同的default position values可能会导致完全不同的推荐效果,这会导致生成一个次优的online performance。

在本paper中,我们提出了PAL来建模position-bias。PAL的思想基于以下假设:一个item被用户点击基于两个因素(假设item被user看到)

  • a) item被用户看到的概率
  • b) 用户在该item上点击的概率

上面的每个factor在PAL中会被建模块“as a module”,这两个modules的outputs是一个item被用户点击的概率。如果两个modules单独进行optimzied,它会导致整个系统达到一个次优的状态,因为两个modules的training objectves间不一致性(inconsistency),正如[18]中所述。为了避免这样的限制,并生成更好的CTR预测效果,PAL中的两个modules会同时进行jointly optimized。一旦这两个modules在offline training下训练完全成,第二个module可以部署到online inference上来预测CTR。

2.方法

2.1 概念

我们假设:offline的点击数据集为 :\(S = \lbrace (x_i, pos_i \rightarrow y_i) \rbrace_{i=1}^N\)

其中:

  • N:是总样本数
  • \(x_i\):是样本i的feature vector,它包含了:user profile, item features和context信息
  • \(pos_i\):是样本i的position信息
  • \(y_i\):是user feedback(如果user在该item进行点击,则\(y_i=1\);否则\(y_i=0\))

我们会使用x,pos,和y来分别表示feature vector、position信息和label。

2.2 Preliminary

两种方法对在offline training中的position-bias进行建模,称为“as a feature”和”as a module”

As a feature

该方法会将position信息建模成一个feature。在offline training中,CTR模型的input feature vector是x和pos的concatenation,例如:\(\hat{x} = [x, pos]\)。然后基于该concatenated feature vector训练一个CTR预测模型。

由于position信息被建模成offline training中的一个feature,在online inference中也应包含一个表示“position”的feature,如图3的右侧所示。然而当执行online inference时,position信息是不提供的。一种解决该问题(在inference时缺失该position)的方法是:为每个position,按top-most position到bottom-most position顺序,判断最适合的item。可以分析得到,brute-force方法具有\(O(l n T)\)的时间复杂度(其中:l是ranking list的长度,n是candidate items的数目,T是inference的latency),它对于一个低延迟的在线环境来说是不可接受的。

图片名称

图3 PAL framework vs. BASE

为了减短延时,可选择一种【10】中描述的具有O(nT)复杂度的方法,它会为所有items选择一个position来作为position feature的值。然而,不同的position value会产生完全不同的推荐结果。因此,我们需要寻找一个合适的position值来达到好的online performance。这里有两种方法来比较使用不同position values进行inference的效果: online experiment和offline evaluation。前者很好,但代价高。因此,我们必须采用offline evaluation来选择合适的position value。另外,不管是使用online experiment或offline evaluation来选择position value,它都不具备良好的泛化特性,因为对于某一个应用场景的online inferenece的position value并不适用于另一个场景。

As a module

为了解决将position信息作为一个feature的上述缺陷,我们提出了一个新的框架来将position信息作为一个module,因此,我们可以在offline training中建模position-bias,并在没有position信息的online inferenece中使用。

3.PAL Framework

我们的framework受以下假设的启发:一个item被一个用户点击,只因为被该用户看到了。更特别的,给定item被用户看到,那么我们认为用户点击一个item的概率依赖于两个因素:

  • a) item被用户看到的概率
  • b) 用户在该item上被点击的概率

如等式(1)所示:

\[p(y=1 | x, pos) = p(seen | x, pos) p(y = 1 | x, pos, seen)\]

…(1)

如果我们进一步假设(注意:此处为PAL的关键假设)

  • a) 一个item已经被看到(seen)的概率只与该相关position被观察到的概率相关
  • b) 一个item被点击(click)的概率与该position是否被看到(seen)相互独立

那么,等式(1)被简化成等式(2) :

\[p(y=1 | x, pos) = p(seen | pos) p(y=1 | x, seen)\]

…(2)

如图3左侧所示,我们的PAL框架基于等式(2)设计,并包含了两个modules:

  • ProbSeen:第一个module会对概率\(p(seen \mid pos)\)建模,它通过图3中的”ProbSeen”进行表示,将position信息pos作为input
  • pCTR:第二个module会对概率\(p(y=1 \mid x, seen)\)进行建模,它表示了图3中的”pCTR”,表示该模型predicted CTR。它的输入是training data中的feature vector x。

任意CTR预测模型(比如:linear models和deep learning models)都可以应用于这两个modules上。

接着,学到的CTR被表示成图3中的”bCTR”,它会将在offline training中的position bias认为是这两个modules的输出的乘积。如【18】所示,如果两个modules被单独进行优化,不同的training objectives间的不一致(inconsistency)会导致整体系统达到一个次优(sub-optimal)的状态。为了避免这样的次优(sub-optimal)效果,我们在该framework中会对这两个modules进行jointly和simultaneously训练。更特别的,PAL的loss function被定义成:

\[L(\theta_{ps}, \theta_{pCTR}) = \frac{1}{N} \sum\limits_{i=1}^N l(y_i, bCTR_i) = \frac{1}{N} \sum\limits_{i=1}^N l(y_i, ProbSeen_i \times pCTR_i)\]

…(3)

其中,\(\theta_{ps}\)和\(\theta_{pCTR}\)分别是ProbSeen module和pCTR module的参数,其中\(l(\cdot)\)是cross-entropy loss function。pCTR module,被用于online inference过程,并不会被直接最优化。实际上,当label和predicted bCTR间的logloss最小化时,ProbSeen和pCTR modules的参数可以如等式(4)和等式(5)通过SGD进行最优化,以便position-bias和user preference的影响会分别被隐式学到。

\[\theta_{ps} = \theta_{ps} - \eta \cdot \frac{1}{N} \sum\limits_{i=1}^N (bCTR_i - y_i) \cdot pCTR_i \cdot \frac{\partial ProbSeen_i}{\partial \theta_{ps}}\]

…(4)

\[\theta_{pCTR} = \theta_{pCTR} - \eta \cdot \frac{1}{N} \sum\limits_{i=1}^N (bCTR_i - y_i) \cdot ProbSeen_i \cdot \frac{\partial pCTR_i}{\partial \theta_{pCTR}}\]

…(5)

在offline training过程中,与[5,13,16]相似,early stop策略被用在训练过程中来获得well-trained model。一旦PAL被well-trained,module pCTR可以被部署到线上进行CTR inference。很容易观察到:position在PAL中的pCTR module并不需要,因此,我们不需要像“as a feature”那样在online inference时分配position values。

3.在线实验

在真实推荐系统中设计在线实验来验证PAL的效果。特别的,我们使用一个三周的AB test来验证PAL vs. “as a feature”的baseline方式。AB test在Company X的app Store的游戏中心的游戏推荐场景进行。

3.1 Datasets

在CompanyX的AppStore生产环境中,我们从traffic logs中抽样了10亿样本作为offline training dataset。为了更新我们的模型,training dataset以一个sliding time-window style的方式进行refresh。training的features包含了app features(例如:app id, category 等)、user features(比如:downloaded、click history等)、context features(例如:操作时间等)。

3.2 Baseline

baseline framework指的是“as a feature”策略。实际上,该baseline采用的是在[10]中的方法。正如所声明的,我们需要选择一个合适的position value作为online inference。然而,由于资源有限,对于使用所有可能positions来评估baseline framework是不可能的。因此,我们会选择合适的positions来进行offline experiment。

Settings。为了选择合适的position(s),我们收集了两个场景的数据集(dataset 1和dataset 2)。test dataset通过next day的traffic logs中收集得到。我们在test dataset中使用不同的position values,范围从position 1到position 10. 与[5,11,13,16]相似,采用AUC和LogLoss来作为metrics对离线效果进行评估。

结果和分析。offline实验的结果如图5所示,其中Base_pk是具有position value k的baseline framework,它会为test data中的所有items分配该值。PAL框架所使用的test data没有position values。从图5看到,分配不同position values,AUC和LogLoss值在test data上变化很大。另外,BASE_p9可以达到最高的AUC,BASE_p5可以达到最低的LogLoss,Base_p1可以在AUC和LogLoss上同时达到最差的效果。我们选择最好的(BASE_p5和BASE_p9)以及最差的(BASE_p1)这两个作为baselines来做与PAL做online ABtest。值得注意的是,PAL在offline experiment中对于AUC或LogLoss均不会达到最好的效果

图片名称

图5 offline实验结果

3.3 AB test

Settings。对于control group,2%的用户被随机选中,并使用baseline framework生成的推荐结果进行呈现。对于experimental group,2%的users使用PAL生成的推荐结果进行呈现。在baseline和PAL中使用的模型是DeepFM,并使用相同的网络结构和相同的特征集。由于资源限制,我们不会在同一时间部署三个baseline(BASE_p1, BASE_p5和BASE_p9)。相反的,他们只会一个接一个地部署,每个轮流一周时间,来对比PAL。更特别的,我们会在每周分别对比PAL vs. BASE_p1、 PAL vs. BASE_p5、PAL vs. BASE_p9.

Metrics

我们采用两种metrics来对比PAL和baselines的在线效果,称为:

  • 实际CTR(realistic CTR):\(rCTR = \frac{\#downloads}{\#impressions}\)
  • 实际转化率(realistic Conversion Rate):\(rCVR = \frac{\#downloads}{\#users}\)

其中:#downloads, #impressions 以及 #users分别表示天级别的下载数、曝光数、访问用户数。

这与predicted CTR不同(例如图3中的“pCTR”),”rCTR”是我们在线观察到的realistic CTR。

结果

图4表示了online experiements的结果。蓝色和红色的histograms展示了PAL对比baseline在rCTR和rCVR上的提升。首先,rCTR和rCVR的metrics在整个三周的AB test上均获得提升,验证了PAL要比baselines要好。第二,我们也观察到,首周中(baseline使用BASE_p1)rCTR和rCVR(图4虚线)的平均提升是最高的,第二周最低(baseline使用BASE_p5)。该现象告诉我们,baseline的效果对于分配不同的position values区别很大,因为推荐可能与所分配的不同的position values完全不同。

图片名称

图4 Online AB test的结果

3.4 在线分析

为了完全理解AB test,并验证我们提出的框架在online inference上消除,我们分析了PAL和baselines的推荐结果。

第一个实验是为了对比与ground truth ranking之间的ranking distance。我们将ground truth ranking定义成一个关于items的list,它通过\(f(rCTR, bid)\)的值降序排列。会采用Spearman’s Footrule来measure在两个rankings中的位移 (displacement),它被广泛用于measure两个rankings间的距离。我们定义了【ground truth ranking】与【由PAL或baselines生成的ranking \(\delta_M\)】在top-L上的距离,如下所示:

\[D(\delta_M, L) = \frac{1}{|U|} \sum\limits_{u \in U} (\sum\limits_{i=1}^L |i - \delta_{M,u}(i)| )\]

…(6)

其中:

  • u是在user group U中的一个具有popularity \(\mid U \mid\)的user
  • \(\delta_{M,u}\)是由model M为user u生成的推荐列表
  • \(\delta_{M,u}(i)\):在ground truth ranking中的第i个item在推荐\(\delta_{M,u}\)中的position 处

我们对比了\(M \in \lbrace PAL, BASE_{p1}, BASE_{p5}, BASE_{p9} \rbrace\)以及\(L \in [1, 20]\)的\(D(\delta_M, L)\),如图6(a)所示,其中,线色实线是PAL的结果,其它线是baselines的结果。我们可以看到,PAL会生成对比ground truth ranking最短的距离,这意味着由PAL生成的推荐与我们在线观察到的real ranking最相似。这通过PAL在offline training中使用position-bias建模、并在online inference中消除position-bias来完成,这可以解释,PAL的效果要好于baselines。

图片名称

图6 online分析

第二个实验对比了PAL和baselines间的个性化(personalization)。Personalization@L 可以mearure 在一个跨不同users的ranking中top-L的inter-user diversity(推荐结果的一个重要因子)。Personalization@L由等式(7)定义:

\[Personlization@L = \frac{1}{ |U| \times (|U|-1)} \sum\limits_{a \in U} \sum\limits_{b \in U} (1 - \frac{q_{ab}(L)}{L})\]

…(7)

其中,\(\mid U \mid\)是user group U的size,\(q_{ab}(L)\)是user a和user b在top-L中公共items的数目。Personlization@L 越高表明,跨不同users在top-L positions上更diverse的推荐items。

我们分别计算了关于PAL 以及baselines的personalization@L。图6(b)表明,在top-5(L=5)、top-10(L=10)以及top-20(L=20)上不同frameworks关于推荐的的personalization。我们可以看到在推荐中由PAL生成的的top items会比baselines生成的更多样一些。由于PAL能在消除position-bias影响后更好地捕获到不同users的特定兴趣、以及根据用户个性化兴趣生成的推荐items。

参考

microsoft在《Modeling and Simultaneously Removing Bias via Adversarial Neural Networks》paper中提出了一种使用adversarial network解决position bias的方法:

介绍

在online广告系统中,需要对给定一个query估计一个ad的ctr,或PClick。通过结合该PClick估计以及一个广告主的bid,我们可以运行一个auction来决定在一个页面上的哪个位置放置ads。这些ad的曝光(impressions)以及他们相应的features被用来训练新的PClick模型。这里,在线广告会存在feedback loop问题,其中:之前看到过的ads会占据着training set,在页面上越高位置的ads会由大部分正样本(clicks)组成。该bias使得在所有ads、queries以及positions(或D)上估计一个好的PClick很难,因为features的比例过高(overrepresentation)与高CTR占据feature space有关

我们假设:在一个page上的position(例如:mainline、sidebar或bottom)可以概括PClick bias的一大部分。实际上,我们的目标是学习这样的一个PClick表示:它对于一个ad展示的position是不变的(invariant),也就是说,所有potential ads对于给定页面上的一个位置,仍然会是单一的相对排序。尽管我们可以很容易地使用一个linear function来强制在position features,但其它features的intrinsic bias相对于position来说更难被移除。

为了学习这种位置不变特性(position invariant feature)的PClick模型,我们使用ANNs(adversarial neural networks)。ANNs会使用competing loss functions来进行建模,它在tandem([6])下进行最优化,最近的工作[1,9]有使用它们进隐藏或加密数据。我们的ANN representation包括了4个networks:Base、Prediction、Bias、以及Bypass Networks(图1)。最终在线使用的PClick prediction是来自Bypass和Prediction networks的outputs的一个线性组合的结果,它用来预测\(\hat{y}\)。然而,在训练这些predictors期间,会使用Bias network adversary(对手)进行竞争。该Bias network只使用由Base network生成的low rank vector \(Z_A\),尝试对position做出预测。相应的,Prediction、Bypass和Base networks会最优化一个augmented loss function,它会对Bias network进行惩罚。结果是,在传给Prediction network之前,vector \(Z_A\)与position无关。

克服position/display biases的另一个方法是:使用multi-armed bandit方法来帮助生成更少的无偏训练数据以及covariate shift。然而,两者都需要来自一个exploration set中的大量样本来生成更好的估计。实际上,很难获得足够量的exploration data,因为它通常会极大影响收益。我们的ANN方法无需exploration,可以应用于已存在的dataset。

为了测试模型的有效性,我们会在真实数据集和伪造实验上进行评估。我们会生成两个伪造数据集集合,并模拟online ads系统的feedback loop,并展示systematic和user position biases可以通过ANN进行处理,并生成更精准的估计。

我们也展示了:当在CTR上进行最优化时,在模型中移除bias间的一个tradeoff。我们展示了:在评估时通过使用该tradeoff,ANN架构可以在无偏数据集上恢复一个更精准的估计。

我们的贡献如下:

  • 一个新的ANN表示,用于移除在线广告的position bias
  • 指定一个不同的squard covariance loss,在bias组件上进行对抗最优化(adversarial optimization)
  • 引入一个bypass结构来独立和线性建模position
  • 详细的人工数据生成评估,演示了在在线广告系统中的feedback问题

2.在付费搜索中的position bias

ML应用中的feedback问题是常见的。为了演示它,我们主要关注付费广告搜索中的CTR或PClick问题。一个标准的Ad selection stack包括了:

  • 选择系统(selection system):selection system会决定ads的一个子集来传给model
  • 模型阶段(model phase):model会尝试估计在分布D上的完全概率密度函数,它是整个Ads、Queries、Positions space。特别的,我们会估计\(P(Click \mid Ad, Queries, Positions\ space)\) 。
  • 竞价阶段(auction phase)[7]:在auction阶段,广告主会对关键词竞价(bid)并对queries进行匹配。Ads和他们的positions会最终由PClicks和广告主bids所选择。我们主要关注model phase或PClick model。

出于许多原因,很难估计D。首先,一个在线Ads系统会从D中抽样一个小量的有偏部分。机器学习模型会使用许多features跨<Ad,Query>上进行估计PClick。许多丰富的features是counting features,它会会跨<Ad,QUERY>的过往进行统计信息(比如:该Ad/Query组合在过去的点击百分比)。Query Ad pairs经常出现在Ad stack中,它们具有丰富的informative feature信息:然而,从未见过或者很少见过的Query Ad pairs并没有这些丰富的信息。因而,对于一个模型来说,保证一个Query Ad pair在online之前没有展示过很难进行ranking,这会导致feedback loop

第二,一个feedback loop会在training data和PClick model间形成。新的training data或ads会由之前的model的ranking顺序展示,一个新的PClick model会从之前的training data中生成。因而,产生的Feedback Loop(FL)会偏向于过往的模型和训练数据

Position CTR,\(P(y \mid Position = p)\)是一个ad在一个页面上的给定位置p的点击概率。这可以通过对在给定位置中展示的ads的CTRs做平均计算得到。具有越高ranked positions的Ads一般也会生成更高的CTRs。之前的工作尝试建模或解释为什么存在position bias【5】。在我们的setting中,我们假设:过往ads的\(P(y \mid Position = p)\)会总结在一个在线广告系统中存在的这些issues,因为具有越高Position CTR的ads,也越可能具有与high PClicks更强相关的特性。

在理想情况下,一个PClick模型只会使用来自D中的一个大量的随机且均匀抽样数据(RUS数据:randomly and uniformly sampled data)。一个在线Ads stack的核心目标是:广告收入(ad revenue)。实际上,不可能获得一个大的随机抽样数据集,因为online展示许多随机的Ads和queries pair在代价太高。

3.背景

3.1 在线广告

biased FL的训练数据问题,可以通过multi-armed bandits来缓解。multi-armed bandits问题的核心是:寻找一个合理的Exploration & Exploitation的trade off

在付费搜索广告的context中,会拉取一个arm,它对应的会选择一个ad进行展示。

  • Exploration实际上意味着具有较低点击概率估计的ads,会导致在short-term revenue上的一个潜在损失(potential loss)。
  • Exploitation偏向于那些具有最高概率估计的ads,会产生一个立即的广告收入的增益。

Bandit算法已经成功出现在展示广告文献、以及其它新闻推荐等领域。由于简洁、表现好,Thompson sampling是一个流行的方法,它对应的会根据最优的概率抽取一个arm。

这些方法在该假设下工作良好,可以探索足够的广告。在在线机器学习系统中,medium-term和short-term revenue的损失是不可接受的。我们可以获取exploration data的一个小抽样,但通常获得足够多的exploration data开销很大,它们受训练数据极大影响。因此,大量biased FL data仍然会被用于训练一个模型,这个问题仍存在。

另一种解决该问题的方法是:回答一个反事实的问题(answering the conterfactual question)[2]。Bottou et al.展示了如何使用反事实方法。该方法不会直接尝试最优化从D上的抽样数据的效果,而是估计PCLick models在过往表现有何不同。作者开发了importance sampling技术来估计具有置信区间的关于兴趣的conterfactual expectations。

Covariate shi‰ft是另一个相关问题,假设:\(P(Y \mid X)\)对于训练和测试分布是相同的,其中:Y是labels,X是features。然而,p(X)会随着training到testing分布发生shifts或者changes。与counterfactual文献相似,它会对loss function进行rebalance,通过在每个实例上乘以\(w(x)=\frac{p_{test}(x)}{p_{train}(x)}\),以便影响在test set上的变化。然而,决定w(x)何时test set上不会具有足够样本变得非常困难。在我们的setting中RUS dataset不足够大来表示整个分布D。

3.2 Adversarial Networks

对抗网络(Adversarial networks)在最近变得流行,特别是在GANs中作为generative models的一部分。在GANs中,目标是构建一个generative model,它可以通过同时对在一个generator和discriminator network间的两个loss functions进行最优化,从一些domain中可以创建真实示例。

Adversarial networks也会用于其它目的。[1]提出使用Adversarial networks来生成某些级别的加密数据。目标是隐藏来自一个adversary的信息,。。。略

4.方法描述

给定一个biased Feedback Loop的training set我们描述了一种ANN结构来生成精准的PClick预测 \(\hat{y}\)。我们假设一个连续值特征b,它会对该bias进行归纳。我们将b定义成在Ads context中的position CTR或\(P(y \mid Position=p)\)。一个input features集合X通常与b弱相关

4.1 网络结构

图片名称

图1

ANN表示包括了如图1所示的4部分:Base network、Predction network、Bias network、以及一个Bypass Network,该networks的每一部分具有参数:\(\theta_A, \theta_Y, \theta_B, \theta_{BY}\)。

  • 第一个组件,Base和Prediction networks,会独立地对b进行最优化;
  • 第二个组件,Bypass network,只依赖于b。

通过以这种方式解耦模型,ANN可以从bias存在时的data进行学习。

Bypass结构会直接使用b,它通过包含它的最后的hidden state \(Z_{BY}\)作为在等式1的最后sigmoid prediction函数中的一个linear term。最终的hidden states的集合用于预测\(\hat{y}\)将包含一个来自Prediction和Bypass Network的线性组合。假设:

\[\hat{y} = sigmoid(W_Y Z_Y + W_{BY} Z_{BY} + c)\]

…(1)

其中:

  • \(Z_y\):表示在prediction network中最后的hidden activations
  • \(W_Y\):表示weights,用来乘以\(Z_Y\)
  • \(W_{BY}\):它的定义类似
  • c:标准线性offset bias项

在b上的linear bypass strategy,当直接包含b时,允许ANN独立建模b,并保留在b上相对排序(relative ranking)

给定X,Base Network会输出一个hidden activations的集合,\(Z_A\)会将输入feed给Prediction和Bias networks,如图1所示。\(Z_A\)用于预测y效果很好,而预测b很差

4.2 Loss functions

为了完成hidden activations的期望集合,我们会最小化两个competing loss函数:

  • bias loss: \(Loss_B\)
  • noisy loss:\(Loss_N\)

其定义分别如下:

bias loss:

\[Loss_B(b, \hat{b}; \theta_B) = \sum\limits_{i=0}^n (b_i - \hat{b}_i)^2\]

…(2)

noisy loss:

\[Loss_N(y, \hat{y}, b, \hat{b}; \theta_A, \theta_{BY}, \theta_Y) = (1-\lambda) Loss_Y(y, \hat{y}) + \lambda \cdot Cov_B(b, \hat{b})^2\]

…(3)

bias loss函数在等式2中定义。loss function会衡量在给定\(Z_A\)时Bias network是否可以较好预测b。在图1中,只有Bias network(orange)和\(\theta_B\)会分别根据该loss function进行最优化,从而保持所有其它参数为常数。

等式3描述了noisy loss function,它会在\(\theta_A, \theta_{BY}, \theta_Y\)上进行最优化,而保持\(\theta_B\)为常数。该loss包含了\(Loss_Y(y, \hat{y})\)来表示prediction loss,可以以多种方式定义。本工作中,我们使用binary cross entropy来定义\(Loss_Y\)。

\[Loss_Y(y, \hat{y}) = \frac{1}{n} \sum\limits_{i=0}^n y_i log(\hat{y}_i) + (1-y_i) log(\hat{y}_i)\]

…(4)

\(Cov_B(b, \hat{b})\)是一个sample covariance的函数,它通过在一个给定minibatch中计算跨b和\(\hat{b}\)均值来计算:

\[Cov_B(b, \hat{b})^2 = (\frac{1}{n-1} \sum\limits_{i=0}^n (b_i - \bar{b})(\hat{b}_i - \bar{\hat{b}})^2\]

…(5)

\(Cov_B(b, \hat{b})^2\)表示来自预测噪声的距离\(\hat{b}\)。squared covariance是0,当\(\hat{b}\)与b非正相关或负相关。当存在高相关性时,只要\(\lambda\)足够大,\(Loss_N\)会被高度惩罚。

产生的\(Loss_N\)的objective function会对两种差的预测对模型进行惩罚,X用于恢复b。\(\lambda\)控制着每个项与其它有多强相关。

4.3 学习

实际上,covariance function会跨每个mini-batch进行独立计算,其中会从每个minibatch进行计算。两个loss function \(Loss_N\)和\(Loss_B\)会通过在相同的minibatch上使用SGD进行交替最优化(alternatively optimized)。

4.4 在线inference

为了在一个online setting上预测,我们会忽略Bias network,并使用其它三个networks来生成predictions: \(\hat{y}\) . 在在线广告系统中,对于在过去在线没有看到过的数据,我们将b设置为Position 1 CTR,接着它们会feed到Bypass Network中

5.系统级bias的人工评估

我们会生成人造数据来展示自然的feedback loop或者在在线广告stack中出现的system level bias。我们首先根据一个bernoulli(概率为:\(P(Y=1)=0.1\))生成click labels,其中Y=1表示一个点击的ad。接着,feature vectors \(x_j\)会从两个不同但重合的正态分布上生成,根据:

\[x_j = \begin{cases} N(0, \sigma), & \text{if $Y=0$} \\ N(1, \sigma), & \text{if $Y=1$} \end{cases}\]

其中,我们设置\(\sigma=3\)。

这会构成一个完全分布D,会采用10w样本来构建一个大的Reservoir dataset。我们接着表示通过仿真一个迭代过程来表示feedback loop,其中之前的top ranked \(x_j\)(或ads)被用于训练数据来对下一个ads进行排序。图2和3展示了这个feedback loop过程,算法2演示了该仿真。

图片名称

图2

图片名称

图3

根据第i-1天的Reservoir数据集中的10000个实例的\(\frac{K}{2}\)候选集合使用无放回抽样随机抽取,其中K=500.模型\(M_{i-1}\)会在第i-1天上训练,并在每个候选集合上对top 2 ads进行排序,在第i天展示给用户。labels会在第i天展示,它随后会形成对可提供的\(topk_i\)训练数据供下一次迭代。

我们会重复该过程,直到迭代了T=100轮. 每次迭代中,我们会记录对于每个top 2 positions的平均position CTR \(P(y \mid Position=p)\)。p=1表示top ranked ads,p=2表示2nd top ranked ads。我们会将position CTRs看成是连续bias term b。为了启动该过程,我们会从Reservoir中抽取K个实例来构成\(topk_0\)。在一个在线Ads系统中,多天的训练数据通常被用来减小systermatic bias。后续评估中,我们会利用最近两天的训练数据(例如:\(M_i\)只在\(topk_i\)和\(topk_{i-1}\)上训练)。每个模型\(M_i\)是一个logistic regression classifier,它具有l2正则。我们在算法2的13行上设置参数r=0,来展示一个系统级的feedback loop bias。我们构成了testing data,从该feedback loop过程中独立,或从D中抽取10w样本来进行HeldOut RUS评估。

图片名称

表1

在过去两天的每个position的CTR如表1所示,整个CTRs的计算在所有天上计算。所有的4 CTR values可能相等,因为他们每个都与250个训练样本相关。因此,一种naive方法是预测平均CTR values。这会构建对一个adversarial Bais Network如何来预测b的一个上界。我们会在表2中记录过去最近两天数据(4 values)的average CTR,并使用该值来计算MSE。

图片名称

表2

5.1 setup

当在FL data上训练模型时,可以生成D或RUS HeldOut data。对于该FL data,我们它使用不同的\(\lambda\)来训练一个ANNs的集合,并将b设置为它的Position CTR。除了last layers外,所有hidden activations会使用hyperbolic tangent function。Prediction network的output activation function是一个sigmoid,并且Bias Network的output activation是线性的。Bypass network包含了具有1个node的1个hidden layer,而Base、Prediction、Bias networks每个都包含了带有10个nodes的1个ideen layer。我们会执行SGD,它具有minibatch size=100以及一个learning rate=0.01. 我们会在FL data上训练100个epochs。在这个主训练过程之后,我们允许Bias network在\(Loss_B\)上训练100个epochs。理想的,在给定从Base network生成的\(Z_A\)上,这会允许Bias network来预测b。

根据对比,我们会为一个带有\(\lambda=0\)的ANN执行相同的评估。该模型可以看成是一个完全独立的vanilla neural network,它在y上进行最优化,而一个独立的Bias network可以观察和最优化\(Loss_B\),无需对Base Network进行变更。我们会对每个模型运行10个具有不同weight initialization的实验,并上报关于y的AUC以及在b上的MSEs。

5.2 主要结果

为了评估来自D的一个无偏样本,我们会使用position 1 CTR, 0.464, 它从最近一天\(topk_{T-1}\)得到。

表3展示了从D中抽取的HeldOut data的AUC和LogLoss,它会在该dataset上训练一个logistic regression模型。这是构成在AUC的一个上界的理想情况。

图片名称

表3

除了使用Bypass network的ANN架构外,我们也展示了不带Bypass network的ANN的一个变种。图4展示了在FL和RUS datasets上AUCs和MSEs。x-aixs是一个reverse log scale,\(\lambda\)从0到0.99999.随着 \(\lambda\)的增大,MSE大多数会增加FL AUC error的开销。使用Bypass network的ANN的FL MSE error会下降到0.00078(如表2所示),它与只有平均CTR的naive方法具有相同的表现。

图片名称

图4

我们注意到,随着\(\lambda\)达到1,在\(Loss_N\)中的\(Loss_Y\)项变得无足轻重,因此可以是\(\lambda\)的一个集合,可以在D的AUC项上进行最优化,它在图4c上可以看到。

ANN模型从\(\lambda=0.9999\)到\(\lambda=0\)在RUS set上的AUC上会有12.6%增益,而在RUS set上只训练一个模型10%的off。

5.3 Bypass vs. non Bypass的结果

图4中的结果展示了使用Bypass vs. non-Bypass ANN在AUC上的微小提升,以及在RUS dataset上具有更高MSEs。我们也分析了根据给定不同的position CTRs在bypass network预测中的不同。我们会在第\(day_{T-1}\)天feed Position 1 CTR作为input到Bypass network中,和features一起做预测,\(\hat{y}_1\),并在\(day_{T-1}\)feed Position 2 CTR来创建\(\hat{y}_2\)。

我们会计算average prediction。图4e展示了这些结果。随着MSE的增加,会在预测上有所不同。因此,我们会假设:Bypass network可以快速解释在ANN表示中的position CTR。

6.在user level bias上的人工评估

另一个造成position bias的factor可能是一个user level bias。用户可能会偏向于不会点在Position 1下的ads,除非是相关和用户感兴趣。我们会模拟一个额外的User level Bias信息,通过在之前的人工评估中截取position 2 ranked ad的labels来进行。算法2的12-14行的,通过使用概率r来切换observed click label从1到0.

。。。

参考