2022.11.16 再读 fb embedding-based 召回的老文章

type

Post

status

Published

date

Nov 16, 2022

slug

2022.11.16 再读 fb embedding-based 召回的老文章

summary

2022.11.16 再读 fb embedding-based 召回的老文章

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 模型结构

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.

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 有效果。