Tractable probabilistic models and computational complexity

doi:10.1007/s10618-025-01101-x

2025-04-24

David Ricardo Cruz *

Jorge Batista

DOI：10.1007/s10618-025-01101-x

原文链接

原文求助

摘要

En 中文

可计算的边缘化概率模型是指那些涉及变量边缘化的证据查询保证能在模型规模的多项式时间内计算出来的模型。当前可计算概率模型类的边缘化可计算性是通过对其分解函数施加结构性质来实现的，而是否存在比当前更一般的具有可计算边缘化的概率模型类仍是一个开放性问题。本文通过使用布尔电路来表达模型解决了这一问题。一方面，用于解决问题所需的简单和局部操作的数量的界限被用作复杂度度量；另一方面，电路值问题的复杂度保证由其门数量的多项式函数所界定。研究表明，变量定义的选择对电路描述长度有影响，因为它们对于简单性和局部性的定义至关重要。所提出的框架基于数据集的电路表示构造以及定义以该电路为输入的问题，使得问题的答案对应于感兴趣的值。基于此，定义了一组电路值问题，使得给定能识别感兴趣查询的输入，对应的输出值即为这些电路的计算结果。这种方法比当前的方法更为通用，因为对于任何在模型上以多项式时间运行的算法，都存在一个门数量由算法执行时间多项式函数界定的电路。

Keyword:

Tractable probabilistic models

Model counting

Circuit value problem

Polynomial time