https://blog.csdn.net/whgyxy/article/details/123948586
论文地址：https://arxiv.org/abs/2006.11632
Facebook搜索作为社交网络搜索与传统的Web搜索挑战不同，在提供结果时考虑用户的上下文非常重要。论文提出基于embedding的向量检索应用到社交网络搜索，主要贡献如下：
最近几十年来不同的技术被开发来提升搜索质量，尤其在Web搜索引擎领域，包括Bing和Google。因为很难从查询文本中准确计算搜索的意图并表示网页的语义，搜索技术大部分基于不同的词匹配技术上，对于关键词匹配的情况，它可以表现的很好。但是语义匹配仍然是一个挑战问题，即如何在查询文本不完全匹配的情况下满足用户的搜索意图。
最近深度学习在语音识别、计算机视觉、自然语言理解等领域取得长足进步。通过他们的embedding，在这些领域被证明是成功的。本质上，embedding是id的稀疏向量表示成稠密的特征向量的一种表示方法，也称为语义embedding，可以学习语义。一旦学习到了embedding，可以作为查询与网页的向量表示应用到搜索引擎的不同阶段。因为在其他领域的成功应用，embedding在信息检索及搜索引擎变得非常活跃。
一般来讲，搜索引擎包含一个召回层，目标是以低时延、低计算成本检索相关的文档集，还有一个排序层，目标是通过复杂的算法模型将用户更需要的文档排序在前面。embedding可以应用到召回和排序，但是有更多机会应用到召回层，因为处于系统的底层，这里经常是系统的瓶颈。基于embedding的召回检索( embedding-based retrieval )通常简称为EBR，使用embedding来表示查询文本及网页，将检索问题转化为在向量空间的近邻 nearest neighbor (NN)搜索问题。
EBR在搜索引擎中是个挑战问题，其一，不同于排序层处理数百个网页文档，检索召回层需要处理十亿以上的网页文档，这种巨大规模给embedding的离线训练和在线serving带来了挑战；其二，不同于计算机视觉，搜索引擎经常需要合并基于embedding检索的结果和基于词匹配检索的结果。
Facebook搜索相比传统的搜索引擎有自己独特的挑战，查询意图不仅仅依赖于查询文本，而且非常依赖于查询的用户及查询的上下文信息（像查询用户的位置信息）。因此Facebook搜索是一个更加复杂的问题，需要理解查询文本、用户、上下文。
为在Facebook搜索上面应用EBR，我们在建模、在线serving、全链路优化上面开发了很多方法来应对挑战。在建模上，我们提出联合embedding，这是个双塔模型，一边是查询文本、用户、上下文信息，另外一边是文档信息。为高效训练模型，我们从搜索日志中挖掘训练数据，从查询文本、用户、上下文、文档中抽取特征。为了更快的模型迭代，我们开发了评估指标来离线评估模型。
搜索引擎构建召回模型有独特的挑战，像怎样构建一个可表示的能有效学习的训练任务。我们调研了2个方向： h a r d m i n i n g hard \ mining hard mining来解决表示及有效学习检索任务的问题， e n s e m b l e e m b e d d i n g ensemble \ embedding ensemble embedding将模型划分为不同的阶段，每个阶段有召回和准确的平衡。
模型开发后，需要在召回任务中开发有效为模型提供服务的方法。一个直接的做法是构建一个系统，这个系统结合来自现存的检索候选结果和来自embedding KNN的候选结果，但是这样做不是最优的，原因如下：
因此我们开发了一种融合了embedding KNN和布尔匹配方式来对文档进行打分的检索。为实现这个目的，我们应用了Faiss库来做embedding向量量化，并和倒排索引检索融合。这个系统有2点优势：
搜索是多阶段的打分系统，召回检索是第一个阶段，后面是排序及过滤等不同的阶段。为整体优化提醒，返回好的结果，抑制差的结果。如下图Figure 1所示，我们将embedding融合到了排序层召回，构建训练数据，来学习和鉴别好的及差的结果。
将检索任务格式化为召回最优化问题，给定一个搜索的查询文本，目标结果集
T
=
t
1
,
t
2
,
.
.
.
,
t
N
T={t_1,t_2,...,t_N}
T=t1,t2,...,tN，模型返回的
t
o
p
K
topK
topK个结果{d_1,d_2,…,d_K}，希望最大化
t
o
p
K
topK
topK的召回结果
r
e
c
a
l
l
@
K
=
∑
i
=
1
K
d
i
∈
T
N
(
1
)
recall@K = \frac {\sum_{i=1}^Kd_i \in T} {N} \ \ \ \ \ \ \ \ \ (1)
recall@K=N∑i=1Kdi∈T (1)
目标结果集是给定查询的相关文档，例如，用户点击的文档。
将召回最优化问题形式化为计算查询和文档距离的排序问题，查询和文档由DNN编码成稠密向量，使用cos相似度作为距离度量。
语义embedding在信息检索中经常表述为文本embedding问题，但在Facebook个性化搜索引擎中是不够的，不仅仅需要考虑查询文本，还需要考虑搜索用户，以及搜索的上下文信息，来满足用户的个性化搜索需要。以人名搜索为例，可能在Facebook上面有成千上万的人叫”John Smith“，在Facebook上，一个实际的用户搜索这个名字时，可能是在搜索他的朋友或者熟人。为建模这样的问题，我们提出了 u n i f i e d e m b e d d i n g unified\ embedding unified embedding不仅考虑查询文本，而且考虑用户及上下文信息。
我们的最终目标是通过在线AB实验提供端到端的质量改进，因此开发离线指标在上线前快速评估模型质量非常重要，在索引中运行KNN检索然后使用公式1定义的 r e c a l l @ K recall@K recall@K来评估。具体来讲，采样10000个搜索会话，汇聚这些会话的查询和目标结果，然后计算这些会话上面的评估 r e c a l l @ K recall@K recall@K指标。
对于给定的三元组
(
q
(
i
)
,
d
+
(
i
)
,
d
−
(
i
)
)
(q^{(i)},d_+^{(i)},d_-^{(i)})
(q(i),d+(i),d−(i))，
q
(
i
)
q^{(i)}
q(i)是查询，
d
+
(
i
)
d_+^{(i)}
d+(i)和
d
−
(
i
)
d_-^{(i)}
d−(i)是相关的正样本和负样本文档
L
=
∑
i
=
1
N
m
a
x
(
1
,
D
(
q
(
i
)
,
d
+
(
i
)
)
−
D
(
q
(
i
)
,
d
−
(
i
)
)
+
m
)
(
2
)
L = \sum_{i=1}^N max(1, D(q^{(i)},d_+^{(i)}) - D(q^{(i)},d_-^{(i)}) + m)\ \ \ \ \ \ \ \ \ (2)
L=i=1∑Nmax(1,D(q(i),d+(i))−D(q(i),d−(i))+m) (2)
D
(
u
,
v
)
D(u,v)
D(u,v)表示向量
u
u
u和向量
v
v
v的距离，
m
m
m是正样本和负样本增强的间隔。这个loss函数就是通过距离间隔将正样本对和负样本对区分开，调整间隔值非常重要，不同的间隔值会导致5%-10%的召回结果偏差。
三元组loss中使用随机样本作为负样本对可以逼近召回最优化任务，原因如下，如果我们对每个正样本采样n个负样本，候选池大小为n，模型最优化的是top1位置。如果候选池大小为N，最优化的为 t o p K ≈ N / n topK \approx N / n topK≈N/n，后面会证明这个假设。
为学习优化三元组loss的embedding，模型包含三个组件：
S ( Q , D ) = c o s ( E Q , E D ) = < E Q , E D > ∥ E D ∥ ⋅ ∥ E D ∥ ( 3 ) S(Q,D) = cos(E_Q,E_D) = \frac {<E_Q,E_D>} {\parallel E_D \parallel \cdot \parallel E_D \parallel}\ \ \ \ \ \ \ \ \ (3) S(Q,D)=cos(EQ,ED)=∥ED∥⋅∥ED∥<EQ,ED> (3)
公式（2）中的cosine距离定义为
1
−
c
o
s
(
E
Q
,
E
D
)
1-cos(E_Q,E_D)
1−cos(EQ,ED)
统一的embedding模型与传统的文本embedding模型的区别在于输入到编码器的信息，统一的embedding模型编码文本的、社交的、上下文的特征信息来表示查询和文档的向量表示。例如，查询端可以包含搜索者的位置和社会关系，文档端可以包含聚合的位置及社交群。
大多数特征是高基数的科类别特征，能变成 o n e − h o t one-hot one−hot或者 m u l t i − h o t multi-hot multi−hot向量，对于每一个类别特征，在输入encoder之前，会插入一个embedding look-up的层，使得变成一个稠密向量。对于 m u l t i − h o t multi-hot multi−hot向量，多个embedding的加权组合作为特征的embedding输入，结构如下图Figure 2所示
在检索任务中定义正负样本是个非同小可的问题，我们初始研究中，选择点击作为正样本，实验了下面的两种负样本方式
使用曝光未点击负样本显著差与使用随机负样本，因为这些负例可能在一个或者多个因素和查询匹配相关，作为hard案例存在，而大多数文档其实是easy案例，和查询匹配相关性不大。如果把这些hard负例作为所有的负例，相对于真实的检索任务，将会改变训练数据的分布表示，这样在学习embedding的时候会带来很大的偏差。
挖掘正样本时也尝试了下面2种方法
实验结果显示两种选择方式同样有效，基于点击和曝光的正样本有相同的数据容量，产生相似的召回结果，增加曝光数据没有提供额外的增益。
以上的研究表明使用点击作为正样本和随机样本作为负样本能提供合理的模型表现，未来会探索负例挖掘的策略提升模型的能力。
统一的embedding模型的一个优点就是除了文本特征还能合并其他不同的特征来提升模型表现，统一embedding模型相对于文本embedding更有效，例如对于事件搜索，文本embedding转到统一的embedding，召回效果提升18%，人群搜索，提升16%。统一的embedding的有效性高度依赖于特征，Table 1显示加不同的新特征带来的提升。
Character n − g r a m n-gram n−gram是表示文本到文本embedding的通用方法，相比于word n − g r a m n-gram n−gram有2个优点
词 n − g r a m n-gram n−gram是将文本表示成文本embedding的通用方法，相对于句子embedding，有2点优势
比较了基于词 n − g r a m n-gram n−gram和基于句子的模型结果，前者更好。对于三词的 g r a m gram gram，包含句子 g r a m gram gram能带来小但是持续的模型改进（1.5%的召回提升）。
对于Facebook实体，提取文本特征的主要字段是人员实体的名称或者非人员实体的标题，相对于布尔词匹配的系统，基于纯文本特征训练的embedding尤其擅长下面几个场景
位置特征在本地商业、群组、事件的搜索中非常有帮助。在查询端，增加搜索者的城市、地域、国家和语言，在文档端，增加公开可用的信息，像管理员标记的人群信息。和文本特征一起，模型能学到查询和文档的隐式位置匹配。Table 2展示了基于文本特征的模型和基于文本+位置特征的模型top相似的返回结果，我们能看到模型能将位置信号融合到embedding中。
为了利用Facebook丰富的社交网络关系图，基于社交网络的用户和实体，对用户训练了一个单独的embedding，帮助融合社交网络信息到最终的embedding结果中。
我们开发了一个基于ANN查找的倒排索引方法，有以下几个优点：
embedding量化有2个主要的组成部分，一个是粗量化（coarse quantization），通过K-means将embedding向量粗聚类，另外一个是点乘（product quantization），用来有效计算embedding的距离。有几个重要的参数需要调优
我们构建了离线的数据通道来调整这些参数，另外还有线上实验来决策最终的参数，下面分享ANN调优的trick。
T
u
n
e
r
e
c
a
l
l
a
g
a
i
n
s
t
n
u
m
b
e
r
o
f
s
c
a
n
n
e
d
d
o
c
u
m
e
n
t
s
Tune\ recall\ against\ number\ of\ scanned\ documents
Tune recall against number of scanned documents，比较了不同的粗量化算法，在相同的聚类数量和nprobe条件。数据分析发现，聚类是不均衡的，尤其是IMI算法，一半的类只有几个样本，这会造成扫描文档集的差异，因此我们将扫描文档的数量作为评估指标。如图Figure 3所示
C
h
o
o
s
e
p
q
b
y
t
e
s
t
o
b
e
d
/
4.
Choose\ pq_bytes\ to\ be\ d/4.
Choose pqbytes to be d/4.点乘量化将向量压缩到
x
x
x字节，对于
x
x
x的选择，和embedding向量的维度
d
d
d相关，更大的
x
x
x有更高的搜索准确度，但是增加了内存成本，根据经验结果，准确度提升在
x
>
d
/
4
x>d/4
x>d/4之后带来的提升就有限了
T
u
n
e
n
p
r
o
b
e
,
n
u
m
c
l
u
s
t
e
r
s
,
a
n
d
p
q
b
y
t
e
s
o
n
l
i
n
e
t
o
u
n
d
e
r
s
t
a
n
d
t
h
e
r
e
a
l
p
e
r
f
i
m
p
a
c
t
Tune\ nprobe,\ num_clusters,\ and\ pq_bytes\ online\ to\ understand\ the\ real\ perf\ impact
Tune nprobe, numclusters, and pqbytes online to understand the real perf impact离线调整这些参数很重要，我们发现在线上设置几组ANN配置的实验也很重要，这也是减少离线和在线差距。
为提升EBR的效率和质量，进行查询和索引选择。查询选择用来克服过度触发、大容量成本等问题，EBR不擅长处理他们，不会提供额外的价值。例如用户简单的搜索，是在找之前搜索或者点击过的结果。索引选择，目的是加快搜索，例如，只选择月活跃用户、最近的事件、流行的页面和群组。
Facebook搜索是一个复杂的多阶段系统，每个阶段更进一步优化前一个阶段的结果。最底层是检索召回层，后面是排序及过滤层。每一个阶段都需要最优化的结果。然而现在的排序阶段是为现存的召回检索场景设计的，会导致基于embedding的新的召回结果被排序模块打分不是最优的，为解决这个问题，提出两个方法
EBR需要继续广泛的研究来提升性能，我们研究了embedding建模的2个重要领域，负例挖掘和embedding集成，来进一步推进EBR的研究
在数据空间中，检索任务有不同的数据分布相对于文本/语义/社交，对于embedding模型设计训练数据去有效的学习非常重要。为解决这个问题，负例挖掘是一个主要的方向，同时在embedding模型中也是一个活跃的研究。但是大部分研究来自原计算机视觉，目的是分类任务，检索任务没有”类“的概念，因此是个独特的问题，现在的方案无法解决。在这个方向上，我们将我们的解决方案分为两部分：hard负例挖掘和hard正例挖掘。
当分析搜索人(people)的embedding模型时，我们发现给定查询时，embedding的topK结果经常是相同的名字，并且模型给目标结果的打分并不比其他结果高，尽管社交特征存在。这促使我们认为模型无法恰当的利用社交特征，这很可能因为训练数据的负例太简单了，因为是随机的，他们的名字经常是不同的。为使模型更好的区分相似结果，我们在训练时使用和正例相似的样本作为hard负例。
模型训练基于小批量更新，hard负例可以在每个batch内动态选取。每个batch包含n个正例 { ( q i , d + ( i ) ) } i = 1 n \{ (q^{i},d_+^{(i)})\}_{i=1}^n {(qi,d+(i))}i=1n,对于每个查询 q i q^{i} qi，使用其他正例文档构建一个小的文档候选池， { d + ( 1 ) , d + ( 2 ) , . . . , d + ( n ) ∣ j ≠ i } \{ d_+^{(1)},d_+^{(2)},...,d_+^{(n)} \vert j \neq i \} {d+(1),d+(2),...,d+(n)∣j=i}选择最相似的文档作为最hard的负例。在各个垂直领域都效果显著，人的搜索+8.38%，人群搜索+7%，事件搜索+5.33%。同时，我们观察到最优设置是每个查询至多2个hard负例，超过2个模型质量会下降。
在线HNM的一个限制是从随机样本中产生hard负例的概率较低，可能无法产生足够的hard负例，下面介绍从整个候选池中挖掘hard负例，成为离线hard负例挖掘
经过以下4步产生
在线负例挖掘和离线负例挖掘做了很多实验，一个发现是仅简单使用hard负例并不比使用随机负例效果好，另外一个发现是基于hard负例的模型给了非文本特征更多权重，在文本匹配上面比基于easy负例的模型要差，因此调整了采样策略。
第一个观点是关于hard负例选择策略，我们发现最hard的样本并不是最好的策略，我们比较了从不同排序打分位置的候选集，发现介于排序打分位置101-500的负样本是最好的，第二个观点是关于召回检索任务最优化，easy负例仍然有必要存在，因为召回模型的输入是整个候选集空间，包含了不同水平的hard样本，而且大部分都是非常easy的负例。因此我们探索了几种合并随机负例和hard负例的方法，包括从hard模型迁移学习到easy模型
训练数据的每个数据点都计算KNN结果非常耗时，重要的是需要有一个高效的topK负例挖掘算法，ANN搜索是一个解决办法。
embedding模型使用点击或者曝光作为正例，为最大化EBR的收益，从用户日志中挖掘潜在的正例，仅仅使用hard正例可以得到相似的召回结果，但是数据量只有原来的4%。可以进一步通过结合hard正例和曝光作为正例来提升模型。(具体怎么挖掘论文未说明)
HNM实验表明easy和hard负例对模型都很重要，hard负例提升模型精度，easy负例表示召回检索的空间。使用随机负样本的模型模拟了召回的数据分布，在K很大是最优的，但是topK里的K如果很小精度就比较差，另一方面，使用曝光未点击做负例或者用离线hard负例挖掘的样本作为负例，擅长对相似的结果排序，但是对于大的候选集比较无力。因此我们提出结合不同hard程度训练的模型，称为多阶段方法，第一阶段聚焦在召回上，第二阶段聚焦在区分第一阶段产生的相似的结果。我们探索了不同的embedding集成方式，包括带权拼接和级联模型
不同的模型对同一个pair(query,document)打的cosine相似度分数不同，使用cosine相似度的加权和来定义这个pair的距离。给定一系列模型的集合
{
M
1
,
M
2
,
.
.
.
,
M
n
}
\{M_1,M_2,...,M_n \}
{M1,M2,...,Mn}，以及相应的权重
α
1
,
α
2
,
.
.
.
,
α
n
>
0
\alpha_1,\alpha_2,...,\alpha_n>0
α1,α2,...,αn>0，对于查询
Q
Q
Q和文档
D
D
D，定义加权集成相似度分数
S
w
(
Q
,
D
)
S_w(Q,D)
Sw(Q,D)为
S
w
(
Q
,
D
)
=
∑
i
=
1
n
α
i
c
o
s
(
V
Q
,
i
,
U
D
,
i
)
S_w(Q,D) =\sum_{i=1}^n\alpha_icos(V_{Q,i},U_{D,i})
Sw(Q,D)=i=1∑nαicos(VQ,i,UD,i)
V
Q
,
i
，
1
≤
i
≤
n
V_{Q,i}，1\leq i \leq n
VQ,i，1≤i≤n表示查询
Q
Q
Q由模型
M
i
M_i
Mi得到的查询向量
U
D
,
i
,
1
≤
i
≤
n
U_{D,i}, 1 \leq i \leq n
UD,i,1≤i≤n表示文档
D
D
D有模型
M
i
M_i
Mi得到的文档向量
对于查询和文档，我们分别需要将多个embedding向量集成为一个单独的向量表示，构造的查询向量和文档向量如下
E
Q
=
(
α
1
V
Q
,
1
∥
V
Q
,
1
∥
,
.
.
,
α
n
V
Q
,
n
∥
V
Q
,
n
∥
)
(
4
)
E_Q = (\alpha_1 \frac {V_{Q,1}} {\parallel V_{Q,1} \parallel },..,\alpha_n \frac {V_{Q,n}} {\parallel V_{Q,n} \parallel })\ \ \ \ \ \ \ \ \ (4)
EQ=(α1∥VQ,1∥VQ,1,..,αn∥VQ,n∥VQ,n) (4)
D
Q
=
(
U
Q
,
1
∥
U
Q
,
1
∥
,
.
.
,
U
Q
,
n
∥
U
Q
,
n
∥
)
(
5
)
D_Q = (\frac {U_{Q,1}} {\parallel U_{Q,1} \parallel },.., \frac {U_{Q,n}} {\parallel U_{Q,n} \parallel })\ \ \ \ \ \ \ \ \ (5)
DQ=(∥UQ,1∥UQ,1,..,∥UQ,n∥UQ,n) (5)
可以看出
E
Q
E_Q
EQ和
E
D
E_D
ED的cosine相似度等价于
S
w
(
Q
,
D
)
S_w(Q,D)
Sw(Q,D)
c
o
s
(
E
Q
,
E
D
)
=
S
w
(
Q
,
D
)
∑
i
=
1
n
α
i
2
⋅
n
(
6
)
cos(E_Q,E_D) = \frac {S_w(Q,D)} {\sqrt {\sum_{i=1}^n\alpha_i^2} \cdot \sqrt n}\ \ \ \ \ \ \ \ \ (6)
cos(EQ,ED)=∑i=1nαi2
⋅n
Sw(Q,D) (6)
权重的选择根据实际经验。embedding集成离线提升较小，但是在线提升显著。
不像并行集成用加权集成来结合，级联模型使用第一阶段的输出作为模型第二阶段的输入。
实现统一的embedding模型仅仅是第一步，最优化端到端系统还有很长的路要走，我们介绍了我们在模型上面的经验，在线serving调优，后阶段优化的经验。我们认为这是有价值的经验来帮助人们将EBR应用到实际的搜索引擎中，EBR在生产环境的成功应用为利用最新语义embedding的持续改进打开了一扇门。我们还介绍了hard负例挖掘和embedding集成经验。
未来有巨大的机会来不断改进这个系统，重要有2个方向：
联系客服
