type
Post
status
Published
date
Nov 16, 2022
slug
2022.11.16 再读 fb embedding-based 召回的老文章
summary
2022.11.16 再读 fb embedding-based 召回的老文章
tags
算法
召回
推荐
category
算天算地系列
icon
password
Embedding-based Retrieval in Facebook Search, 2020
文章里,Facebook 针对社交搜索场景的向量召回,介绍了从样本选择、特征工程、模型设计、离线评估、在线 Serving 的全流程,当然最有意思的部分还属“样本选择”部分,召回本来就是负样本的艺术,这篇文章讲的很接地气,类似 google 的很多文章,都让人感觉很踏实,大道至简,贴合业务,解决实际问题,不搞花里胡哨的东西。如今 2 年多过去,无意中从书架上看到,再读一遍此文,又有不一样的感受,在原来的理解基础上补充了近几年的一些想法。
1. 背景
不同于传统的网络搜索,社交网络上的检索问题不仅仅关注于 query 的文字信息,还要关注于上下文信息的相关性。虽然向量召回在其他的搜索引擎中有了广泛运用,FB 之前的搜索还是主要在使用布尔匹配。所以这篇文章讨论了 FB 向量召回的实践方案。
2. 模型训练
2.1 离线评估指标
模型返回的 top K 结果集合 ,目标结果集合:,基于某种准则,比如用户点击或者专家排序等。在这篇文章里,作者采样了 10000 个搜索结果,去收集 <query, target result> pair 对,然后取平均的 recall@K 作为结果。也就是拿Top K 召回结果与用户实际点击做交集,然后计算 precision/recall;
在其他公司的实践中,离线评估的指标各有不同,比如 Airbnb 所使用的方法是看“用户实际点击”在“召回结果”中的平均位置;
另外,召回要做离线评估是很难的,因为召回的结果未被用户点击,不能说明用户不喜欢,而可能是因为这个召回结果在 ranking 阶段被干掉了,根本没有给用户曝光过。
2.2 损失函数
本文用的是 triplet loss,给定 triplet ,其中 是 query, 和 分别是正和负样本,triplet loss ,其中距离函数 D = 1 - cosine相似度,而 cosine 相似度则用 query 和 doc 塔输出的 embedding 计算。 作为 margin value 用来决定 positive pair 和 negative pair 之间的距离,是一个可以调节的超参数,对效果有显著影响,文章中提到不同的参数会影响 5-10% KNN recall variance。
但是,我认为用 BPR loss = 可能效果更好,因为少了 m 这个超参数,而且在 hinge loss 中,当距离之差大于 m 后,这一个样本对 loss 的贡献就变成 0 了,而 BPR 则没有限制,两者距离越大越好。
2.3 模型结构
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fafdd680a-876e-4511-91a1-e1f4fcf8337b%2Ff015bece-7d91-44ed-a7aa-5c2edbb6dd70%2FUntitled.png%3Ftable%3Dblock%26id%3Dd646ef95-df0c-450b-a599-f72e5e61bcab%26spaceId%3Dafdd680a-876e-4511-91a1-e1f4fcf8337b%26expirationTimestamp%3D1725681600000%26signature%3DbiN1cwvnYHlZHcNXerMRBcFQbwbj95HCiTLQ7zwjL3U?table=block&id=d646ef95-df0c-450b-a599-f72e5e61bcab&cache=v2)
2.4 样本选择
- 本文用“点击正例”和“随机负例”已经达到了很好的效果。如果召回候选池大小是 N,每个正例采样 n 个负例,大致保证 K = N/n。
- “随机负例” (从负例池里随机采样) 的效果要远好于“展现未点击负例” (从 session 里展现未点击样本里随机采样);
- 原因很简单,能展现的样本都是经过 ranking 筛选的,相对点击样本来说已经是 hard 样本了,而召回要面对的绝大多数都是 easy 样本。
- “点击正例”和“展现正例” (即有展现的 doc 都算正例),在同样数据量的情况下,模型效果持平,“展现正例”并没有带来明显增益;
- Hard Negative Mining
- Online hard negative mining:一种 in-batch 的 hard 负例,即对每个正例的 query,都从同一个 batch 内其他正例的 doc 里按相似度降序采样 n 个,组成一个新的样本作为 hard 负例。文章里 n = 2 效果最好,过了效果就开始下降。
- Offline hard negative mining:
- (1) generate top K results for each query (用 ANN). (2) select hard negatives based on hard selection strategy. (3) retrain embedding model using the newly generated triplets. (4) the procedure can be iterative.
- hard selection strategy:最 hard 的样本反而不是最好的,本文发现 rank 在 101-500 的能获得最好的效果。
- 只用 hard 负例打不过“随机负例”,原因是 the "hard" model put more weights on non-text features but did worse in text match than the "easy" model.
- 混合 easy 负例和 hard 负例效果最好,本文实测最好比例 easy:hard=100:1
- 从 “hard” 模型向 “easy” 模型做 transfer learning 能提升效果,反过来不行。
- Hard Positive Mining
- 寻找没有被召回但依然是 positive 的样本,“To this aim, we mined potential target results for failed search sessions from searchers’ activity log“,文章里仅用这种 hard positive 都能与用“点击正例”获得相同 level 的结果,数据量仅有“点击正例”的 4%;
- 即使是“随机负例”这么简单的东西,其实也不简单,随机并不意味着是等概率随机,因为有高热 item 以及其他各种工程实现问题的存在,如果只是等概率随机,也容易导致效果不行,具体关于负样本的选择技巧,可以参考之前总结的这篇文章 2021.03.04 召回-负例的艺术(wip) 。
- “展现未点击” 样本似乎啥用也没有。
3. 特征工程
没啥可说的,比较常规。
- Text features. 非常有用,注意用法
- We compared models trained with character n-grams vs word n-grams and found the former can yield a better model.
- on top of character trigrams, including word n-gram representations additionally provides small but consistent model improvement
- Location features. 非常有用
- Social embedding features. 感觉一般
4. 线上服务
4.1 ANN(Approximate Nearest Neighbor)
本文比较了多种实现方法以及多种参数,并有几点发现:
树方法,如 KD-tree,Ball-tree,Annoy 哈希方法,如 Local Sensitive Hashing (LSH) 量化方法,如 Product Quantization (PQ) 近邻图方法,如 Hierarchical Navigable Small World (HNSW)
- Tune recall against number of scanned documents:聚类是不均匀的,因此不能只考虑聚类数,还要考虑被 scan 的 doc 数。
- Tune ANN parameters when there is non-trivial model change:ANN 的参数和模型有关,如果模型发生了重大的变更,比如增加了 hard 样本之类的,需要试着调下 ANN 的参数。
- Always try OPQ:OPQ 是个好东西。
- Choose pq_bytes to be d/4:对于 PQ 算法,经验上的参数选择,d 是向量维度。
- Tune nprobe, num_clusters, and pq_bytes online to understand the real perf impact:不要一直离线测,重要的还是在线测。
4.2 系统部署
- 在 location 和 term text 的索引基础上,增加了关于 nn 模型的信息。added a (nn <key> :radius <radius>) query operator which matches all documents whose <key> embedding is within the specified radius of the query embedding.
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fafdd680a-876e-4511-91a1-e1f4fcf8337b%2F20b44fd0-2f4b-4fbd-ad79-72c31128ffa1%2FUntitled.png%3Ftable%3Dblock%26id%3D39577881-a5d4-45ea-a23e-dc9006152a6d%26spaceId%3Dafdd680a-876e-4511-91a1-e1f4fcf8337b%26expirationTimestamp%3D1725681600000%26signature%3DZ6GG1eKc6dZFgyAZYu1IzcxEeW58CAFwWCkyE593mZc?table=block&id=39577881-a5d4-45ea-a23e-dc9006152a6d&cache=v2)
4.3 Query and Index Selection
query selection:为避免 over-triggering, huge capacity cost and junkiness increase,对于一些特定的 query,比如用户想搜索他们之前搜过或者点过的内容,如果 nn 召回不能带来有效的信息增益,那么就不会触发这一次的 nn 召回。
index selection:在建索引的时候,只选择了月活用户,近期事件,热门的事件,以及热门 group。大部分公司在构建索引的时候都会采取这样的策略,很多长时间不活跃的内容可以不构建索引,以减少存储消耗。
5. 召回后链路的优化
优化链路一致性问题,担心新召回路的 doc 不被现有的 ranking 认可,导致推不出去。本文给出的解决方案主要有下面两种:
- Embedding as ranking feature,尝试将 query 和 doc 的 embedding 之间的 cosine 相似度,Hadamard 积,甚至 embedding 本身传给下游的 ranking 模型进行学习,本文发现 cosine 相似度效果最好。
- Training data feedback loop,文章认为向量化召回的召回率高但是精度低 (就是容易召回一些不相关的 doc),因此人工对向量化召回的结果进行标注,然后 re-train the relevance model,用于过滤掉那些不相关的召回结果。
6. 进一步的优化
6.1 hard 样本的挖掘
已经融合到 2.4 节样本选择里了,主要是 hard 负例的挖掘,比如 in-batch 负例,以及离线 hard 负例,即离线模拟召回过程,取排序在中段的样本作为 hard 负例。
6.2 Embedding Ensemble
- easy 样本让模型学习到整个召回候选空间的样本分布,因此召回率很高,但是精度不高 (即排在前面的可能不如后面的更好);
- hard 样本可以帮助优化精度,在一个小候选集上能做到很好的 ranking,但是面对大规模的候选,召回率不行。
因此,本文提到了一种 multi-stage 的方式,具体做法有两种:
- bagging 方式,多个模型的结果进行加权求和的方式,Weighted Concatenation
- 线上召回时,为了能够使用 FAISS,必须将多个模型产出的 embedding 融合成一个向量。做法也非常简单,将权重乘在 user embedding 或 item embedding 一侧,然后将各个模型产出的 embedding concat 起来即可。这样能够保证拼接向量之间的 cosine 相似度,与各单独向量 cosine 之后的加权和,是成正比的;
- 本文发现,使用“曝光未点击”作为 hard negative 训练出来的 hard model,离线指标好,但是线上没有效果;
- 反而,利用 offline hard negative 训练出来的 hard model,与 easy model 融合后效果最好。
- boosting 方式,就是把召回分成了 easy 阶段和 hard 阶段,hard 阶段类似一个小粗排,文章提到使用“曝光未点击”作为 hard negative 训练出来的 hard model 没效果,用 offline hard negative 训练出来的 hard model 有效果。