📊 statistics

Distributional Approximate Nearest Neighbour Search for Uncertainty-Aware Retrieval

本文介绍了 DINOSAUR，这是一个通过为用户和物品采样多个嵌入向量，将嵌入不确定性引入近似最近邻搜索的框架，从而在保持与现有基础设施兼容并最小化召回损失的同时，提升了对多样化长尾内容的检索能力。

原作者： Olivier Jeunen

发布于 2026-06-04

📖 1 分钟阅读☕ 轻松阅读

原作者： Olivier Jeunen

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正走在一座拥有数百万本书籍的巨大图书馆中。你想根据自己当下的心情找到一本完美的书。在现代推荐系统中，这座图书馆由一个机器人管理员运行，它使用一张特殊的地图来寻找那些看起来与你以前喜欢的书籍相似的书。

问题所在：“完美”地图过于僵化

目前，机器人管理员将每本书和每个读者都视为地图上的一个单一、固定的点。

热门书籍： 想想像《哈利·波特》这样的畅销书。管理员已经见过它们成千上万次了。它们在地图上的位置清晰且精确。
小众书籍： 现在想想一本关于特定类型蘑菇的晦涩自出版小说。管理员只见过它寥寥数次。由于数据稀疏，管理员其实并不确定这本书“真正”应该属于地图上的哪个位置。

缺陷： 因为机器人被设定得非常僵化，它只会挑选那些与你的位置完全最近的书。如果那本晦涩的蘑菇书因为管理员的不确定性而稍微偏离了中心，它就会永远被忽略。这创造了一个系统，其中只有著名的、热门的项目才能获得推荐，而独特的、小众的或“长尾”的内容则会被剥夺关注。

解决方案：遇见“Dinosaur”

该论文提出了一种名为 dinosaur 的新方法（用于不确定性感知检索的分布近似最近邻搜索，Distributional Approximate Nearest Neighbour Search for Uncertainty-Aware Retrieval）。

与其将一本书视为地图上的一个点，dinosaur 将不确定的书籍视为一种可能性的云团。

创意类比：“模糊云团” vs. “锐利点”

旧方法（点估计）： 想象管理员用一个微小、锐利的图钉标记了蘑菇书的位置。如果你的请求落在那个图钉哪怕仅仅一毫米之外，这本书就会被拒绝。
Dinosaur 方法（分布式）： 想象管理员意识到：“我不百分之百确定这本蘑菇书应该属于哪里。”所以，他们没有使用一个图钉，而是在那个大致区域周围投下了一个模糊的图钉云团。
- 对于一本热门畅销书，云团很小很紧凑（因为管理员非常确定）。
- 对于一本小众书籍，云团很大很分散（因为管理员不确定）。

当你寻求推荐时，机器人不仅仅检查一个点；它会检查你的请求是否落在这些模糊的云团之中的任何地方。因为小众书籍拥有更大的云团，它有更高的概率被“击中”并包含在你的列表中。

在实践中如何运作

论文解释说，这不需要建立一个新的图书馆或改变机器人的大脑。这是一个聪明的技巧：

采样： 在你到达之前，系统会将小众书籍的“模糊云团”在地图周围生成多个副本，使其散布开来。
搜索： 当你进行搜索时，系统会寻找距离最近的副本。
去重： 如果它找到了三个相同的蘑菇书副本，它只会将其计为一次推荐。

这就像是撒开一张更宽的网。你更有可能捕捉到稀有的鱼（小众项目），而不会丢失常见的鱼（热门项目）。

结果：更多的多样性，几乎没有成本

作者在大型电影推荐数据集（MovieLens）上测试了该方法。

权衡： 通常，如果你试图展示更多多样性，你可能会不小心向人们展示他们不喜欢的东西，从而降低你的“准确性”得分。
Dinosaur 的发现： 论文表明，通过使用这些模糊云团，他们可以使向用户展示的电影多样性增加三倍（将“目录覆盖率”从约 23% 提高到约 63%）。
代价： 他们的“准确性”（他们挑选出用户真正喜欢的电影的频率）下降了一个微小的、几乎不可察觉的幅度（不到 0.5%）。

为什么这很重要

论文认为，这是运行一个更公平的市场的方式。

对于创作者： 小众卖家和创作者得到了“数学上的助力”。因为他们的项目具有不确定性，他们会获得一个“更大的云团”，从而在不需要人工经理进行人为干预的情况下，获得一个更公平的被看见的机会。
对于用户： 你可以发现那些在僵化系统中会被过滤掉的、具有偶然惊喜感的独特内容。

总结

Dinosaur 是一种简单且聪明的方法，它告诉推荐机器人：“如果你不确定这个项目属于哪里，不要忽略它。给它一点呼吸的空间，这样它才有机会被发现。” 它将机器人的不确定性转化为发现的机会，帮助长尾内容在不破坏系统的情况下生存下来。

技术摘要：面向不确定性感知检索的分布式近似最近邻搜索 (dinosaur)

1. 问题陈述

现代大规模推荐系统在候选生成阶段依赖近似最近邻 (Approximate Nearest Neighbour, ANN) 搜索，将数百万个项目过滤为可管理的集合。标准的实现方式将用户和项目的表示视为共享潜空间中的确定性点估计（单个向量）。

本文指出这种范式存在一个根本性的缺陷：

内在的不确定性： 从稀疏交互数据中学习到的嵌入本质上具有不确定性。这种不化由两部分组成：
- 认知不确定性 (Epistemic)： 由于缺乏交互数据，长尾项具有高方差。
- 偶然不确定性 (Aleatoric)： 低秩潜在因子模型固有的信息损失。
系统性偏差： 确定性的 ANN 检索创建了僵化的几何边界。对于那些具有高不确定性（通常是利基、长尾内容）的项，即使其真实相关性可能很高，但由于其点估计均值略有偏差，它们会被永久排除在 top- $k$ 候选名单之外。
后果： 这导致了流行度偏差 (Popularity Bias) 和“富者愈富”的反馈循环，其中头部项占据了主导地位，而长尾创作者和多样化内容则系统性地被剥夺了曝光机会。现有的补救措施（例如事后重排序或多样性目标）通常是启发式的，且与根源问题脱节。

2. 方法论：`dinosaur` 框架

作者提出了 dinosaur（用于不确定性感知检索的分布式近似最近邻搜索），该框架通过直接在候选生成过程中引入嵌入不确定性，而无需更改底层的 ANN 基础设施或评分模型。

核心机制

与其为每个项目 $i$ 索引一个单一的点估计 $\mu_i$ ，dinosaur 将项目视为分布 $P(v_i)$ （由均值 $\mu_i$ 和协方差 $\Sigma_i$ 表征）。

索引构建（离线）： 对于每个项目 $i$ ，系统从其嵌入分布 $P(v_i)$ 中抽取 $S_i$ 个独立的样本 $v_i^{(j)}$ 。ANN 索引基于这组扩充后的向量集进行构建。
查询执行（在线）： 在服务时，从用户的分布 $P(v_u)$ 中采样一个用户嵌入 $v_u$ 。ANN 索引被用来寻找该采样向量的最近邻。
去重： 检索到的向量被映射回其原始的项目标识符，并移除重复项，直到返回恰好 $k$ 个不同的项目。

关键特性

基础设施兼容性： 该方法不需要更改 ANN 索引算法（如 FAISS、HNSW、ScaNN）或评分模型。它只需要一个能够处理更多向量的索引即可。
双向 vs 单向： 虽然该框架支持对用户和项目同时进行采样，但论文重点讨论了项目侧不确定性以驱动探索。这在实时用户采样可能违反延迟约束的动态市场中特别有用。
自适应采样： 为了管理内存成本（索引膨胀），论文提出了自适应采样 (Adaptive Sampling)，其中样本预算 $S_i$ 取决于项目的确定性。高置信度的头部项接收 $S_i=1$ ，而具有不确定性的长尾项接收 $S_i > 1$ 。

理论基础

论文为该框架提供了理论保证：

收敛性： 当嵌入方差消失（ $\sigma^2 \to 0$ ）时，dinosaur 收敛于标准的确定性点估计检索。
单调覆盖扩张： 对于任何位于确定性 top- $k$ 之外的项目，其被检索的概率随其嵌入方差的增加而严格递增。这在数学上保证了不确定性项目获得了“检索阶段的探索奖励”，在不引入随机噪声的情况下，结构化地倾向于长尾内容。
与 Thompson Sampling 的联系： 该机制在形式上与 Thompson Sampling 相关联，即通过从后验分布中采样来平衡探索与利用。

3. 实验设置

作者在 MovieLens-32M 数据集（3200 万次交互，约 20 万用户，约 8.4 万项目）上评估了 dinosaur。

基准模型： 精确内积搜索 (Flat) 和近似搜索 (IVFFlat)。
不确定性代理： 由于基础模型 (iALS) 是确定性的，作者构建了一个合成的认知后验，其中标准差 $\sigma_i$ 与项目的交互次数 $n_i$ 成反比： $\sigma_i = \alpha / (1 + n_i)^\gamma$ 。
指标：
- Recall@K： 标准的离线效用指标。
- Catalogue Coverage@K： 出现在至少一个用户 top- $K$ 列表中的总目录项目比例。
- 分层覆盖率 (Stratified Coverage)： 按流行度五分位数进行的分析（B0 = 最热门，B4 = 最冷门）。

4. 关键结果

巨大的覆盖率提升： 将样本预算从 $S=1$ （基准）增加到 $S=5$ ，几乎使全局目录覆盖率翻了三倍（在 $K=1000$ 时从 23.52% 提升至 62.97%）。
微乎其微的 Recall 损失： 这种覆盖率的扩张是以极小的离线 Recall 损失为代价的，在 Recall@1000 上仅下降了 0.0041。
长尾曝光：
- 标准 IVFFlat 对最不热门的项目（Bucket B4）实现了 0.00% 的覆盖率。
- dinosaur ( $S=5$ ) 在 Bucket B4 实现了 81.88% 的覆盖率，确保了超过 13% 的用户收到了来自最冷门项目的推荐。
帕累托支配 (Pareto Dominance)： 与 $\epsilon$ -greedy 启发式方法相比，dinosaur 表现出严格的帕累托优势，在各种检索深度（ $K \in \{100, 500, 1000\}$ ）下，针对相同比例的探索性推荐实现了更高的 Recall。

5. 重要性与主张

论文声称 dinosaur 为检索阶段的探索-利用权衡提供了一种原则性的、基础设施兼容的解决方案。

范式转移： 它将处理不确定性的负担从事后重排序或启发式多样化转移到了检索阶段本身。
打破反馈循环： 通过允许不确定性项目进入候选集，它打破了确定性策略阻止长尾项目获得曝光从而无法进行学习的算法反馈循环。
实用性： 该方法除了样本计数外不需要新的超参数，并且可以与现有的生产级 ANN 库协同工作。
承认局限性： 作者指出，他们的不确定性代理是基于交互计数而非学习到的分布，且离线指标 (Recall) 受非随机缺失 (MNAR) 数据的影响。他们建议未来的工作应结合倾向性感知 (propensity-aware) 的离线评估以及在线 A/B 测试，以衡量真实的业务市场影响。

总之，dinosaur 证明了将嵌入视为分布而非点，可以在几乎不降低标准检索效用的情况下，显著提高目录多样性和长尾曝光。