论文标题
贝叶斯推断的参数化复杂性结果
Parameterized Complexity Results for Bayesian Inference
论文作者
论文摘要
我们提出了有关两个不同参数化的贝叶斯网络中推断的完整性结果，即变量数量和拓扑顶点分离数。为此，我们介绍了参数化的复杂性类$ \ Mathsf {w [1] pp} $和$ \ Mathsf {Xlpp} $，它与$ \ Mathsf {w [1]} $和$ \ Mathsf {xnlp {xnlp} $分别为$ \ Mathsf {pp} $ {第二个参数旨在将路径概念的自然翻译与定向无环形图的情况进行自然翻译，因此，它是一个比更常见的参数更强的参数。基于最近的猜想，此参数的完整性结果表明，推理的确定性算法需要在路径宽和扩展树宽方面的指数空间。这些结果旨在有助于对贝叶斯推断的参数化复杂性以及其所需的计算资源的参数复杂性有助于在时间和空间上。
We present completeness results for inference in Bayesian networks with respect to two different parameterizations, namely the number of variables and the topological vertex separation number. For this we introduce the parameterized complexity classes $\mathsf{W[1]PP}$ and $\mathsf{XLPP}$, which relate to $\mathsf{W[1]}$ and $\mathsf{XNLP}$ respectively as $\mathsf{PP}$ does to $\mathsf{NP}$. The second parameter is intended as a natural translation of the notion of pathwidth to the case of directed acyclic graphs, and as such it is a stronger parameter than the more commonly considered treewidth. Based on a recent conjecture, the completeness results for this parameter suggest that deterministic algorithms for inference require exponential space in terms of pathwidth and by extension treewidth. These results are intended to contribute towards a more precise understanding of the parameterized complexity of Bayesian inference and thus of its required computational resources in terms of both time and space.
