Embedding-based Retrieval in Facebook Search

facebook的社交网络检索与传统的搜索检索的差异是，除了考虑文本，还要考虑搜索者的背景。通用搜索主要考虑的是文本匹配，并没有涉及到个性化。像淘宝，youtube这些其实都是涉及到了用户自身行为的，除了搜索还有推荐，搜推一体。为了个性化搜索，facebook构建了一套统一框架以及基于倒排索引

1. 介绍

搜索引擎帮助用户在海量的信息中进行检索，google和bing开发了各种技术来提高搜索质量。由于语义和意图非常难以表征，因此当前的搜索大多依赖于term匹配方法，也就是关键字匹配。

语义匹配：解决关键词不能完全匹配但是可以满足用户搜索意图所需要的结果

深度学习在语音，机器视觉和自然语言理解中取得了重大的进展。embedding即表征被证明是一种有效的方法。本质上来说embedding是一种将ids的稀疏向量表征为密集向量的方法，也被称为语义嵌入。一旦embedding建立好，就可以作为query和doc的表示，从而可以应用到搜索引擎的各个阶段。

一般来说，搜索引擎分为召回和排序。embedding在这两部分都可以使用，但是通常应用在召回层，因为位于系统的底部，而且也是瓶颈所在。基于embedding的检索通常称为EMR，基于embedding来表征query和doc，然后将检索问题转换为嵌入空间最邻的搜索问题。

召回：以低延时和低计算成本来检索一组相关的文档，称为recall
排序：以更复杂的算法和模型在顶部对最想要的文档进行排名，称为rank

EBR在搜索引擎中的最大挑战就是数据量巨大的问题，召回层需要处理数十亿或者万亿的文档。而且搜索引擎通常需要将基于embedding和term匹配的检索结合在一起，在检索层对文档进行评分。

为了解决这个问题，facebook提出了统一嵌入，这是一个双塔模型，其中一边是搜索请求，包括query，encoder和context，另一边则是doc。训练数据是从搜索日志中挖掘的，并从encode，query和context提取特征。

将embedding和term匹配的方法合并在一起非常简单，但是发现是次优的，

2. 模型

给定一个query，它的目标结果是T={t1,t2,...tN}T=\{t_1,t_2,...t_N\}T={t1​,t2​,...tN​}，模型返回的TopK个结果是D={d1,d2,...dK}D=\{d_1,d_2,...d_K\}D={d1​,d2​,...dK​}，模型想要最大化
$$recall@K=\frac{{\sum }_{i=1}^K{d}_i\in T}{N}$$

目标结果$T$是基于某些条件与query相关的doc，例如用户点击的结果，或者是基于人类评级的文档。将召回优化的问题定义为基于query和doc之间计算距离的排名问题。query和doc都通过编码器转换为向量，使用余弦值作为距离度量，损失函数使用triple loss。
对于facebook来说，检索不仅需要考虑文本的内容，而且还需要考虑搜索者的信息以及搜索的上下文，以此来满足用户的个性化。以搜人为例，虽然Facebook有数千个名为小王的用户，但是用户的搜索目标通常是他们的熟人。

2.1 评价指标

线上AB测试，离线是平均recall@K

query	目标文档个数	召回结果中有几个在目标文档中
$q_1$	$n_1$	$m_1$
$q_2$	$n_2$	$m_2$
…
$q_k$	$n_k$	$m_k$

$$recall@K=\frac{m_1+m_2+...+m_k}{n_1+n_2+...+n_k}$$

2.2 损失函数

给定一个三元组$(q^i,d_{+}^i,d_{-}^i)$，其中$q^i$是query，$d_{+}^i$和$d_{-}^i$分别是正样本和负样本。loss定义为
$$L=\sum _{i=1}^N\text{max}(0,D(q^i,d_{+}^i)-D(q^i,d_{-}^i)+m)$$

其中$D(u,v)$两个向量的距离度量，距离越近说明向量越接近也就是越匹配。我们的期望是$q^i$与正样本$d_{+}^i$距离越小越好，与负样本$d_{-}^i$的距离越大越好，也就是说两个距离之间的差值越大越好。用下面这个表来说明，假设m是5

query	正样本	负样本	距离	loss
$q$	$d_{+}^1=100$	$d_{-}^1=90$	10	$max(0,10+5)=15$
$q$	$d_{+}^1=8$	$d_{-}^1=1$	2	$max(0,2+5)=7$
$q$	$d_{+}^1=9.9$	$d_{-}^1=9.9$	0	$max(0,0+5)=5$
$q$	$d_{+}^1=80$	$d_{-}^1=77$	-3	$max(0,-3+5)=2$
$q$	$d_{+}^1=10$	$d_{-}^1=13.5$	-3.5	$max(0,-3.5+5)=1.5$
$q$	$d_{+}^1=0.8$	$d_{-}^1=2$	-1.2	$max(0,-1.2+5)=3.8$
$q$	$d_{+}^1=8$	$d_{-}^1=11$	-3	$max(0,-3+5)=2$
$q$	$d_{+}^1=4.9$	$d_{-}^1=10$	-5.1	$max(0,-5.1+5)=0$
$q$	$d_{+}^1=0$	$d_{-}^1=5$	-5	$max(0,-5+5)=0$
$q$	$d_{+}^1=9$	$d_{-}^1=19$	-10	$max(0,-10+5)=0$
$q$	$d_{+}^1=1$	$d_{-}^1=101$	-100	$max(0,-100+5)=0$

从上面这个表格可以看出，如果loss为正，说明query与正样本的距离比负样本的距离大，这肯定不好，当距离为负数，说明负样本的距离更大。还做了一个margin，

当负样本的距离远大于正样本的距离的时候，其实其实已经不用过度惩罚了，可以认为loss为0了。
当负样本的距离小于正样本的距离，这个时候我们需要对模型进行惩罚，即loss大于0

我仔细想了一下，其实很简单，如果正样本的距离大于负样本的距离，那么越大惩罚的力度就越大，反之，如果小于负样本的距离是不是就不惩罚了呢？不是的，不仅要小于负样本的距离，而且要足够小，因此设置了一个margin，但是小太多的话其实就不管了，因此已经超过预期了。

目标：不仅要小，而且要足够小，如果足够小，那么就不用再小

调整margin的值是非常重要的，不同的margin值会导致召回率有5%-10%的方差变化。通过对负样本进行随机采样，triplet loss可以近似为recall@K。对于每一个正样本，如果随机采$n$个负样本，模型优化的目标就是从$n$个样本中找出那$1$个正样本，假设实际上的候选集为$N$，近似优化召回$recall@K$。

2.3 统一嵌入模型

模型由三部分组成

• query编码器 $E_Q=f(Q)$，将查询query转变成向量embedding
• doc编码器$E_D=g(D)$，将文档doc转变成doc的向量embedding
• 距离度量函数$S(E_Q,D_D)$，查询query和文档doc之间的分数

编码器是一个神经网络，将稀疏输入$ids$输入转换成密集向量embedding，$f(\cdot )$和$g(\cdot )$是两个编码器，形式上是两个分立的编码器，实际上参数相同。距离度量函数使用cosin
$$S(Q,D)=cos(E_Q,E_D)=\frac{<E_Q,E_D>}{||E_Q||\cdot ||E_D||}$$

Q和Q的cos值越大说明两个向量越接近，也就是距离越小，反之值越小距离越大，因此距离的定义为$\text{dist}=1-cos(E_Q,E_D)$

传统的搜索输入只要文本信息，而这里的输入包含其他的信息，例如用户的位置，社交网络等，文档侧也是

双塔模型的一端是离线计算好的，文档侧所有的输入信息都应是静态的，不会随着query输入的变化而变化。
用户也会有静态特征，通常是一些统计数据，例如用户在某个类目（话题）下的点击率，这样的特征不仅会随着用户变化，而且也会随着文档变化。这样的特征有两种用法，

1. 在召回侧，用户在各个类目下的点击率统一作为向量输入到编码器中，表针的是这个用户的基础信息，通过神经网络对这些特征做非线性映射

我们可以统计历史1个月内用户在不同类目下的点击率（ctr，tfidf，freq均可）

user	类目1	类目2	类目3	类目4	类目5
u1	$p_{11}$	$p_{12}$	$p_{13}$	$p_{14}$	$p_{15}$
u2	$p_{21}$	$p_{22}$	$p_{23}$	$p_{24}$	$p_{25}$
u3	$p_{31}$	$p_{32}$	$p_{33}$	$p_{34}$	$p_{35}$

在召回层，我们的输入可以变更为$[e_1,e_2,...e_n,p_{i1},p_{i2},p_{i3},p_{i4},p_{i5}]$，将所有的信息拼接在一起作为输入即可。

2. 在排序侧，文档已经召回了，根据文档类型和用户信息，从属性库中可以获取用户在这个文档类型下的点击率，作为一个特征输入

而到了排序侧，doc都已召回了，针对<user,doc>进行打分，因此特征变为（只是举个例子）

pair	doc的类型	用户embedding特征	文档embedding特征	用户在这个doc类型下的点击率	特征
$<u_1,d_1>$	类目1	${\mathbf{e}}_{u1}$	${\mathbf{e}}_{d1}$	$p_{11}$	$[{\mathbf{e}}_{u1},{\mathbf{e}}_{d1},p_{11}]$
$<u_1,d_2>$	类目2	${\mathbf{e}}_{u1}$	${\mathbf{e}}_{d2}$	$p_{12}$	$[{\mathbf{e}}_{u1},{\mathbf{e}}_{d2},p_{12}]$
$<u_2,d_3>$	类目3	${\mathbf{e}}_{u2}$	${\mathbf{e}}_{d3}$	$p_{23}$	$[{\mathbf{e}}_{u2},{\mathbf{e}}_{d3},p_{23}]$

2.4 数据挖掘

正样本使用点击的doc
负样本有两种方式

1. 随机采样：对每个query，都从doc池中随机抽取一些doc作为负样本
2. 曝光未点击：在同一个session中，随机抽取一些曝光未点击作为负样本

使用曝光未点击作为负样本效果明显更差，这是因为曝光的负样本通常由于一个或多个因素匹配查询的结果（也就是跟query强相关），但是索引中的大多数文档于query并不怎么相关，如果负样本都选择这种曝光未点击的难样本，相当于改变真实数据的分布，这会导致embedding学偏

3 特征引擎

统一嵌入模型的优点是可以融合文本以外的各种特征

• 文本特征 字符n-gram是一种常见的方法来表征文本的向量，与单词n-gram相比他的优势有两个。1）词汇数量是有限的，而且embedding lookup会更小，训起来会更快。2）subword对oov会有更强的鲁棒性，query侧的拼写错误也可以识别。相当于term匹配，embedding召回有两个优点
  • 模糊匹配。召回类似的词，例如kind可以召回kinds等
  • 词汇扩增。搜索mini，可能会召回mini cooper等
• 位置特征 位置匹配在本地搜索等业务中是非常有效额。为了让模型在生成向量的时候考虑位置信息，将位置信息添加到了query和doc两端。对于query侧，提取了城市，地区，国家和语言等，对于doc端，添加了公开可用的信息。
• 社交网络特征 facebook有丰富的社交网络，因此单独训练了一个graph模型，将graph embedding作为特征输入到模型中

这种感觉非常的奇怪，把个性化的单塔模型做成双塔模型，我很难想想特征是如何确立的，这样不是会导致双塔的两个模型参数不一致吗

4 服务

4.1 ANN

量化有两个部分组成，一个是粗力度的量化，通过K-means将embedding量化到粗簇中（IVF），另一个是乘积量化（PQ），进行细粒度的量化。

• 粗量化：IMI和IVF是有效的，调整num_cluster的数量是重要的，对召回结果有影响
• PQ量化：PQ，OPQ（向量通过PCA转换再进行PQ）pq_bytes是需要调整的重要参数
• nprobe：nprobe决定扫描多少个簇，直接影响召回的性能和精度

这几个参数调整的策略

• 由于簇是不平衡的，例如分成了10个簇，可能80%的文档都集中再一个簇中，当簇不平衡的时候IMI算法大约一半的簇都只有几个样本。因此对于相同的num_cluster和nprobe来说，得到的文档都是不同的。
• 应用量化之前对数据进行转换通常很有用，他们尝试了PCA和OPQ来转换数据，观察到OPQ效果更好。
• 选择pq_bytes为$d/4$。PQ量化将向量最终压缩成x个字节，对于x的选择通常与维度d有关。较大的x会有更高的精度，但代价是增加内存和延迟。从经验看，$x>d/4$之后精度提升是有限的

4.3 query和index选择

怎么来判断一个query是否需要启动emb查询呢？

5. 后期优化

facebook的搜索排名系统非常的复杂，每一层都是基于前一层进行的优化，之前的召回层是基于布尔规则的，所以排序模型也是基于布尔规则的召回doc来设计的，，如果直接将ebr召回的doc让当前的排序模型打分，会导致emb召回的结果被排在后面，有两种解决思路

本质就是老汤模型

• embedding作为排序特征。将相似性分作为排序模型的一个特征，不仅有助于精排识别基于ebr的doc，而且还未所有结果提供了语义相似性的度量，探索了余弦相似性，Hadmard乘积和原始embedding向量，实验角度来看余弦相似性比其他的要好。

  • 本质就是做了特征补齐，原来布尔规则召回的doc也会反查向量，然后与query计算相似分，而ebr召回的doc也会去反查布关键字匹配构建的特征，例如tfidf，bm25等。
  • embedding作为特征的意思是可以直接把embedding作为特征，也可以基于embedding构建一些其他特征作为精排的输入，脑子活络一点，看清问题的本质

• 训练数据反馈。基于embedding的方式可以提高检索召回，但是与关键词召回相比精度较低，为了解决精度问题，建立了一个基于人类评级的pipeline。将基于embedding召回的记过发给人工去打分，以此来标记是否相关。然后使用人工打分的数据重新训练模型。

  • 老实讲，看着很像是ANCE的方式在做训练

6. 高级话题？？？

6.1 难样本挖掘

6.1.1 Hard negative mining(HNM). 分析人物搜索的EBR模型的时候发现，给定query，返回的前K个结果通常具有相同的名称，但是模型不会把正确结果排到其他结果之前，即使存在社交特征，模型也不会把这样的doc排到其他的doc之前。这说明模型并没有学会如何正确的利用社交特征，很有可能是因为负样本训练的太容易了，因为负样本很多都是随机采样的，通常与目标doc的名称不同。为了让模型更好的区分相似的结果，可以在embeding空间使用更接近正例的样本作为训练中的难负样本。

负样本是随机采样的，因此模型可以很容易区分出当前的正负，但是无法进行更细粒度的区分。例如模型不仅要可以区分出用户喜欢手机还衣服，还要区分出喜欢的是哪一款手机。

为什么即使拥有更多的特征，正确的结果依然不会被排在最前面，这些特征为什么没有被利用起来。这个分析的思路很好，但是怎么想到是因为负样本的原因的？

Online hard negative mining. 模型训练是基于mini-batch数据的，每个mini-batch的输入是n个正样本对{qi,d+i}i=1n\{q^i,d^i_+\}_{i=1}^n{qi,d+i​}i=1n​，将mini-batch中其他的pair对中的doc作为负样本随机采样，优先选择相似度最高的负样本作为难负样本，而且最好不要超过两个。因为负样本就是从全量的doc中随机抽取的。

positive pair	query	d+	d-	d-	d-	d-
<q1,d1>	q1	d1	d2	d3	d4	d5
<q2,d2>	q2	d2	d1	d3	d4	d5
<q3,d3>	q3	d3	d1	d2	d4	d5
<q4,d4>	q4	d4	d1	d2	d3	d5
<q5,d5>	q5	d5	d1	d2	d3	d4

或者是

positive pair	query	d1	d2	d3	d4	d5
<q1,d1>	q1	+	-	-	-	-
<q2,d2>	q2	-	+	-	-	-
<q3,d3>	q3	-	-	+	-	-
<q4,d4>	q4	-	-	-	+	-
<q5,d5>	q5	-	-	-	-	+

此时每个query有一个正样本，有$n-1$个负样本。我们在使用torch的dataloader的时候，可以在collect_fn将mini-batch的转换成我们想要的格式

使用mini-batch中的与正样本分数最接近的doc作为hard negative。使用triplet loss后，难负样本和非难负样本的差异是什么呢？从损失函数里面好像没有表现出来呀。

其实有个疑惑，mini-batch中的数据都是曝光且点击过的doc，因为都是正样本。但是哪些曝光始终未点击的doc怎么办呢？我有两点考虑，1）这些曝光但始终没有点击的doc或许就是垃圾，也可以认为是噪音，去掉反而会更好，毕竟优质库是哪些曝光且历史有过点击的doc，2）要看数据分布，如果doc池中大部分都是曝光未点击的，那么mini-batch肯定是不好的，因为与实际的分布不一致，但这个时候其实要考虑的就是为什么这么多doc曝光未点击，是不是因为资源池有问题。所以我觉得mini-batch其实是合理的。

Offline hard negative mining 在线的mini-batch负样本毕竟有限，不一定能很好的选出难负样本，而离线则可以从全量的库中进行采样。做法就是通过knn的方式筛选出top-k个负样本，而且只需要从一个簇中抽取即可，因为训练的过程中使用的其实就是semi-hard negative。

比较离线HNM和在线HNM，一个看起来违反直觉的发现是单纯使用难负样本会导致模型变差，分析之后发现单纯使用难负样本会导致模型在文本匹配上效果更差，通过调整抽样策略，最终得出了一个可以优于在线HNM模型的模型。

• 使用最难区分的负样本训练并不是最优的，通过比较了来自不同排名位置的样本发现，排名101-500之间的样本实现了最佳的模型召回

  负样本是按照什么来排序的？如果按照跟query的相似分或者正样本的相似分来计算，这个打分模型又是哪里来的？人工打分还是BM25这种无监督模型。而且一个query到底抽取了多少个负样本

  0-100的样本只是用户未点击，但是可能只是这一次没有点击而已，并不一定就是负样本，有可能还是正样本，而位置靠后的更有可能是负样本。

• 训练数据中包含简单的负样本是必须的，因为真实的数据就是会包含大量的easy样本

  召回模型是从全量的数据中找到与query最接近的doc，相关的doc必然是稀疏的，大部分都是比较好区分的doc，训练数据集的分布肯定是要跟实际分布一致的。在排序阶段，所有的数据都是跟query极度相关的了，数据分布于召回的数据分布肯定不一致了。

下面是两种抽样策略

1. 使用难易样本混合训练，难易样本的比例为1:100
2. 从“难”模型到“易”模型的迁移学习：从易到难模型的迁移不会使模型更好，但从难到易的迁移学习可以进一步增加模型的记忆能力

6.1.2 Hard positive mining 直接使用点击的样本作为正样本，这样会导致训练数据很少，所以从日志中挖掘出一些潜在转化的样本也作为正样本。例如可以有些浏览时长较长但未点击的样本