精选Apple Machine Learning Research论文
倒排索引遍历的P完全性：布尔查询DAG评估的复杂性
本文研究了在倒排索引上执行复杂布尔查询的理论极限。作者形式化了一种基于DAG的检索语言L_R，并证明其评估问题是P完全的。为解决该问题，他们提出了ComputePN算法，通过正负对偶表示和DAG记忆化，将评估时间严格限制在O(|Q|·|U_active|)，避免了指数级展开和全量扫描的开销，为计算检索奠定了理论基础。
现代AI智能体日益依赖搜索基础设施来执行复杂的神经符号推理工作流。这些工作流通常会被编译为针对文本字段的深度嵌套、非单调布尔查询。然而，基于倒排索引的标准查询评估策略在处理这些结构时面临严重的理论限制。有状态迭代器模型（Document-at-a-Time）在结构上受限于NC^1公式求值，在展开重汇聚逻辑时，查询复杂度会遭遇最坏情况下O(2^|Q|)的指数级爆炸。相反，递归物化模型（Term-at-a-Time）在评估文档全集上的逻辑否定时，会产生Ω(|U|)的空间复杂度代价（即全表扫描）。
在本文中，我们确立了在倒排索引上原生执行复杂逻辑的理论边界。我们形式化了一种基于有向无环图（DAG）的检索语言（L_R），并证明其求值问题是严格P完全的。为了使求值可处理，我们引入了ComputePN，一种确定性的、感知稀疏性的求值算法。通过一种新颖的正-负对偶表示将逻辑否定与全集规模物化解耦，并利用原生DAG记忆化，ComputePN将求值时间严格限制在O(|Q| · |U_active|)内。该方法能够在索引上原生评估P完全查询，同时避免组合树展开瓶颈和全表扫描代价，为计算检索奠定了形式化基础。
相关阅读与更新。
基于Wally的可扩展私有搜索
本文介绍了Wally，一种私有搜索系统，支持针对大型数据库的高效语义搜索和关键词搜索查询。当有足够多的客户端发起查询时，Wally的性能显著优于以往系统。在以往的私有搜索系统中，对于每个客户端查询，服务器必须对数据库中的每个条目执行至少一次昂贵的密码学操作。因此，性能会急剧下降……
使用大语言模型为虚拟助手生成合成查询
本文被SIGIR 2024工业界分会场接收。
虚拟助手（VA）是重要的信息检索平台，帮助用户通过语音命令完成各种任务。语音识别系统（语音转文本）使用仅基于文本训练的查询先验，来区分发音上容易混淆的候选词。因此，生成与现有VA使用模式相似的合成查询可以显著改善……
探索机器学习领域的机遇。
我们的机器学习研究每天都在取得新的突破。