提出可在开放世界中高效进行关系型概率推理的新方法
Polynomial-Time Relational Probabilistic Inference in Open Universes
- 基于期望的平方和逻辑，实现关系推理的可计算性
- 在限定度数和量化阶数下，复杂度为多项式时间
- 适用于无限对象集，适合需高效推理的智能系统
不确定性推理是人工智能的核心挑战之一。语言表达力与计算可处理性之间常存在两难。受人类推理启发，本文提出一种一阶关系概率推理方法，同时满足表达力与可计算性要求，并支持混合变量（离散与连续）。具体地，将期望的平方和逻辑扩展至关系设置，证明在有界度数片段中，对于有界量化阶的知识库，即使对象集事先未知或可数无穷，也可实现多项式时间的提升推理。关键在于，其可计算性以证明论框架定义，超越语言或查询的语法属性。我们能基于给定度数与规模的证明推导出最紧上界，并在固定度数下建立平方和归谬的完备性。
原文摘要 · Abstract (English)
Reasoning under uncertainty is a fundamental challenge in Artificial Intelligence. As with most of these challenges, there is a harsh dilemma between the expressive power of the language used, and the tractability of the computational problem posed by reasoning. Inspired by human reasoning, we introduce a method of first-order relational probabilistic inference that satisfies both criteria, and can handle hybrid (discrete and continuous) variables. Specifically, we extend sum-of-squares logic of expectation to relational settings, demonstrating that lifted reasoning in the bounded-degree fragment for knowledge bases of bounded quantifier rank can be performed in polynomial time, even with an a priori unknown and/or countably infinite set of objects. Crucially, our notion of tractability is framed in proof-theoretic terms, which extends beyond the syntactic properties of the language or queries. We are able to derive the tightest bounds provable by proofs of a given degree and size and establish completeness in our sum-of-squares refutations for fixed degrees.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。