近似最近邻检索

概述

在大规模向量空间中快速找到与查询向量最相似的 Top-N 个向量的技术，是推荐系统候选生成阶段的核心检索方式。

关键内容

1. 问题定义：给定一个查询向量 u（用户 embedding）和一个包含数十亿向量的集合 V（视频 embedding 空间），快速找到与 u 内积（或余弦相似度）最大的 Top-N 个向量。精确最近邻搜索需要遍历所有向量，复杂度 O(V)，在超大规模场景下不可行。

2. 在 YouTube DNN 中的应用：Deep Neural Networks for YouTube Recommendations 中，训练完成后每个视频对应一个 embedding 向量 v_i（softmax 层权重），每个用户请求时通过神经网络前向计算得到 embedding 向量 u。推荐问题转化为：在视频 embedding 空间中找到与用户 embedding u 最近的 Top-N 个视频——这是一个经典的近似最近邻（ANN）检索问题。

3. 训练-服务不对称：训练时用 softmax 分类 + 采样 Softmax，服务时用 ANN 检索。这种"训练时用分类，服务时用检索"的不对称设计是整篇论文最精髓的工程思想之一。

4. 主流 ANN 算法：

5. 基于树的方法：KD-Tree、Ball Tree、Annoy（Spotify 开发）
6. 基于哈希的方法：LSH（Locality Sensitive Hashing）
7. 基于图的方法：HNSW（Hierarchical Navigable Small World）——当前最主流的方案
8. 基于量化的方法：IVF-PQ（Inverted File with Product Quantization）

9. Google ScaNN：专为大规模推荐系统优化的 ANN 库

10. 向量检索生态：YouTube DNN 中"训练时用 softmax，服务时用 ANN 检索"的思路，直接推动了向量检索技术在推荐系统中的广泛应用。Faiss（Facebook）、ScaNN（Google）、Milvus、Pinecone 等向量数据库和检索库的兴起，都与这一范式的流行密切相关。

11. 性能指标：ANN 检索的核心权衡是速度 vs. 精度。好的 ANN 算法能在亚线性时间（通常 O(log V) 或 O(1)）内完成检索，同时保持较高的召回率（通常 95%+ 的精确最近邻召回率）。

来源

• 07-youtube-dnn.md — Deep Neural Networks for YouTube Recommendations 深度解读

相关

• Deep Neural Networks for YouTube Recommendations — 将 ANN 引入推荐系统的论文
• 双塔模型 — 产生 embedding 的模型架构
• 候选生成 — ANN 的应用场景
• Embedding — ANN 检索的输入
• Faiss — Facebook 的 ANN 检索库
• ScaNN — Google 的 ANN 检索库