面向推荐系统的校准近似最近邻检索：保真度、排名保留与模态权衡

《Information Sciences》：Calibrated approximate nearest-neighbor retrieval for recommender systems: Fidelity, rank retention, and modality trade-offs

　　

摘要
近似最近邻 (ANN) 索引加速候选检索，但无关的检索保真度比较可能会产生误导性的系统选择。我们在四个公共交互数据集上评估了精确 Flat、HNSW、IVF-Flat、IVF-PQ 和 Flat-PQ，并将用户到物品与物品到物品的检索分开。仅 CPU 协议在校准可调索引时，以 0.90、0.95 和 0.98 的协议召回率目标为基准，对照精确 Flat 进行校准。留出项排名代理与精确邻居保真度分开报告。因为存档管道在构建留一查询之前从完整的过滤交互矩阵中学习物品表示，所以这个代理是传递式的，而不是对样本外推荐质量的估计。该研究结合了 40 个主要条件、查询级不一致性、对三个非冗余结果的修正配对推断、曝光代理、SVD 加权敏感性和存储与保真度合成缩放。HNSW 和 IVF-Flat 在校准样本上达到了所有目标，而测试的 IVF-PQ 配置在八个场景中的两个达到了 0.90，从未达到 0.95。在选定的 0.95 设置下的扩展样本评估中，HNSW 在七个场景中保留了目标，IVF-Flat 在六个场景中保留了目标，揭示了有限样本的迁移不确定性。HNSW 和 IVF-Flat 平均仅改变了 0.03% 和 0.11% 查询的留出项前 10 名排名，而 IVF-PQ 为 5.23%，Flat-PQ 为 6.01%。修正的 20,000 重采样分析拒绝了 96 个霍尔姆调整比较中的 18 个，主要涉及 Recall@100；每个拒绝都倾向于精确 Flat。结果支持约束优先的索引选择，其中协议阈值是从应用程序特定的下游或在线服务指标中可容忍的退化中得出的，而不是作为通用的技术常数。

引言
候选检索是推荐架构中的核心系统组件。表示模型将用户、上下文和物品映射为向量，而搜索索引选择一组易于处理的后继排名候选集。穷举向量搜索提供精确参考，但其时间和存储成本随目录增长。近似最近邻 (ANN) 索引通过图遍历、粗略分区、向量压缩或这些机制的组合来降低服务成本。FAISS 提供了这些家族的广泛使用的实现，并能够在常见的软件堆栈上进行受控评估 [1]。

只有在明确检索保真度时，比较才是公平的。HNSW 搜索广度和探测的 IVF 列表数量决定了执行多少工作以及结果在多大程度上匹配穷举搜索。因此，比较无关的默认值可能会将延迟优势归因于索引家族，而此时它部分反映了更低保真度的运行点。通用 ANN 基准测试通过相对于精确邻居的召回率来解决这个问题 参考文献 [2]。面向推荐的研究可以增加第二个独立的诊断：近似是否改变了记录正例的排名。在当前的存档管道中，物品向量是从完整的过滤交互矩阵传递式估计的，因此该诊断是留出项排名代理，而不是样本外推荐质量估计。因此，ANN 协议和此排名代理必须保持独立。

三个部署考量因素使这种区别具有重要意义。首先，查询几何结构随检索模式变化。用户到物品 (U2I) 查询平均物品向量历史，可能与锚定在目录向量上的物品到物品 (I2I) 查询占据表示空间的不同区域。为一种模式选择的参数不一定能迁移到另一种模式。其次，压缩不仅可以改变延迟和存储，还可以改变目录覆盖范围和推荐槽位的流行度组成。这些是有用的曝光代理，但它们不是已实现注意力或公平性的证据 [3]。第三，在有限校准样本上选择的参数看起来充足，然后在更大的查询样本上低于目标。校准达成和扩展样本验证必须是独立的声明。

离线推荐协议引入了进一步的脆弱性来源。候选采样、不一致的分割和弱基线可以逆转明显的进展 [4]。对神经推荐的重新评估也表明，不受控制的实验选择可能会夸大改进 [5]。MovieLens 的发现取决于如何解释其记录的交互 [6]。因此，我们通过一份涵盖总体过滤、传递式表示阶段、时间查询构建、精确参考、校准深度、评估截止、硬件策略和配对查询标识符的证据契约来定义该研究。

本文研究在 MovieLens 1M、MovieLens 20M、Goodbooks 和 Amazon Books 上的校准 ANN 检索。主要表示是 128 维的 BM25 加权截断 SVD，物品向量从完整的用户过滤交互矩阵中学习并进行 L2 归一化。查询历史和留出标签随后通过时间留一法产生。精确 Flat、HNSW、IVF-Flat、IVF-PQ 和 Flat-PQ 针对 U2I 和 I2I 进行评估。HNSW、IVF-Flat 和 IVF-PQ 在 0.90、0.95 和 0.98 的协议召回率目标上进行校准。精确 Flat 和 Flat-PQ 不作为运行时校准方法呈现。主要网格使用在 0.95 处选择的参数，并保留目标失败作为可见项。

五个研究问题组织了调查：
RQ1. 在明确的 ANN 协议召回率设计点上，索引家族在留出项排名保留和描述性单查询延迟方面有何不同？
RQ2. 校准迁移、候选不一致性和留出项排名影响在 U2I 和 I2I 之间有何不同？
RQ3. 图遍历、倒排索引和向量压缩如何改变内存、目录覆盖率和长尾曝光代理？
RQ4. 主要索引结论在替代的 SVD 加权方案中是否持续存在？
RQ5. 序列化存储和精确邻居保真度如何随合成目录规模变化？

本研究有四个贡献。首先，它指定了一种特定模式的校准协议，区分了校准样本达成、扩展样本协议和传递式留出项排名代理。其次，它引入了一种查询级不一致性分析，报告候选集变化的频率、留出项前 10 名排名变化的频率，以及在精确 Flat 检索到 100 个候选者内的正例的子集上发生了什么。第三，它将保真度和排名保留与描述性单次传递延迟、覆盖率、曝光集中度、长尾槽位份额、SVD 加权敏感性和合成存储缩放联系起来。第四，它推导了一种约束优先的选择程序，在比较可行索引之前，先根据外部指定的保真度服务目标拒绝失败。该贡献是一种评估方法和经验系统研究，而不是新的 ANN 算法、推荐模型、样本外推荐评估或通用保真度阈值。

第 2 节将本研究定位在 ANN 基准测试、推荐检索、压缩和评估研究中。第 3 节定义了校准框架，第 4 节详述了实验。第 5 节回答了研究问题。第 6 节阐述了部署意义，第 7 节列出了局限性，第 8 节是结论。

章节片段
向量检索与 ANN 评估
ANN 索引通过不同的结构假设用精确性换取资源使用。早期的可导航小世界搜索确立了图遍历作为高维空间中空间分区的替代方案 [7]。HNSW 增加了层级，提供了强大的内存内召回率 - 吞吐量行为，但存储图链接且构建成本可能很高 [8]。NSG 追求控制出度的稀疏可导航图 [9]。DiskANN 将基于图的搜索扩展到十亿点...

总体、表示与查询模式
每个数据集归一化为包含用户、物品和交互顺序的三元组 (??,??,??)。MovieLens 评分至少为 3.5 和 Goodbooks 评分至少为 4 被视为正例。Amazon Books 使用 McAuley Books 五核心存档中的每个评论，通过源文件名 reviews_Books_5.json.gz [29] 识别。在主要 SVD 表示、查询构建、流行度估计和数据集统计之前，移除少于五次保留交互的用户。

数据集与评估总体
这四个数据集涵盖两个媒体领域和不同的规模、密度和流行度机制。MovieLens 1M 是最密集的保留矩阵，允许对所有符合条件的用户进行评估。MovieLens 20M 提供最大的交互数量。Goodbooks 贡献了具有规则用户活动但只有伪时间顺序的紧凑书籍目录。Amazon Books 过滤后是最稀疏且最大的目录。它的 8,898,041 交互、603,668 用户和 367,982 物品识别了 McAuley Books...

RQ1：校准保真度、排名保留与延迟
校准样本将两种未压缩近似方法与测试的压缩条件分开。HNSW 和 IVF-Flat 在所有八个数据集 - 模式场景中达到了 0.90、0.95 和 0.98。IVF-PQ 在两个场景中达到了 0.90，并在任何场景中均未达到 0.95 或 0.98（图 2 和表 3）。其最佳配置点保留为失败。

在 1000 个查询上的参数选择不均匀地迁移。在选定的 0.95 设置下，扩展样本 AR@100 保持在...

校准比较的经验教训
匹配保真度的校准将比较从延迟排名转变为可行性问题，但可行性阈值必须来自应用程序而不是 ANN 基准测试。从业者应首先指定离线排名指标或在线关键绩效指标的最大可容忍变化，将该容忍度映射到最小协议水平??SLO，然后才校准索引。在 1000 个查询的校准样本上，HNSW 和 IVF-Flat 占据了评估...

结构效度。
ANN 协议召回率衡量与精确 Flat 的重叠，而不是用户效用。第二个结果是一个传递式的留出项排名代理：记录的正例从查询历史中移除，但贡献于从中学习物品表示的完整过滤交互矩阵。因此，它不能被解释为样本外推荐质量或下一次交互泛化。精确 Flat 仅在 8.1% 到 40.1% 的查询中在 100 个候选者内检索到该正例，因此...

结论
面向推荐检索的 ANN 索引比较只有在精确邻居保真度、下游排名代理、查询模式和系统成本保持独立时才是合理的。跨越四个数据集，HNSW 和 IVF-Flat 达到了请求的校准样本设计点，并通常在扩展查询总体上保留了主要的 0.95 点。迁移不足表明，在 1000 个查询上的校准需要随后的验证，而不是无保留的达成声明。

CRediT 作者贡献声明
查拉夫·哈米迪：方法论。萨尔玛·加乌：方法论。穆罕默德·巴迪：方法论。维纳亚库马尔·拉维：方法论。穆罕默德·哈利法·布塔希尔：方法论。希查姆·特里巴克：方法论。

生成式 AI 和 AI 辅助技术在写作过程中的声明
在准备本工作期间，作者使用了 OpenAI ChatGPT 进行语言和结构编辑。使用此工具后，作者根据需要审查和编辑了内容，并对发表文章的内容承担全部责任。

资金
本研究未从公共、商业或非营利部门的资助机构获得任何特定拨款。

竞争利益声明
作者声明他们没有已知的竞争性财务利益或个人关系，可能看起来影响了本论文报告的工作。

致谢
作者感谢领域编辑和匿名审稿人提出的建设性意见，这有助于改善本工作的范围、方法论清晰度和经验展示。

查拉夫·哈米迪 | 萨尔玛·加乌 | 穆罕默德·巴迪 | 维纳亚库马尔·拉维 | 穆罕默德·哈利法·布塔希尔 | 希查姆·特里巴克
工程科学实验室，伊本·佐尔大学，阿加迪尔科学学院，阿加迪尔，摩洛哥