论文标题
用线性阶公理提起推理
Lifted Inference with Linear Order Axiom
论文作者
论文摘要
我们考虑用于在统计关系学习领域中用于概率推断的加权一阶模型计数（WFOMC）的任务。给定公式$ ϕ $，域尺寸$ n $和一对权重功能，在大小$ n $的域上，所有$ ϕ $的所有型号的加权总和是多少？结果表明，使用最多两个逻辑变量的任何逻辑句子计算wfomc可以在$ n $中进行多项式进行。但是，还表明该任务是$ \ texttt {＃} p_1 $ -complete，一旦我们添加了第三个变量，这启发了搜索两变量片段的扩展，该片段仍将允许$ n $中的运行时间多项式。这种扩展之一是带计数量词的两变量片段。在本文中，我们证明添加线性订单公理（$ ϕ $中的一个谓词之一在每个型号的$ ϕ $中引入域元素的线性顺序）在计数量词之上仍然允许计算时间在域大小中的计算时间多项式。我们提出了一种新的基于动态编程的算法，该算法可以在$ n $中按时间多项式计算WFOMC，从而证明了我们的主要索赔。
We consider the task of weighted first-order model counting (WFOMC) used for probabilistic inference in the area of statistical relational learning. Given a formula $ϕ$, domain size $n$ and a pair of weight functions, what is the weighted sum of all models of $ϕ$ over a domain of size $n$? It was shown that computing WFOMC of any logical sentence with at most two logical variables can be done in time polynomial in $n$. However, it was also shown that the task is $\texttt{#}P_1$-complete once we add the third variable, which inspired the search for extensions of the two-variable fragment that would still permit a running time polynomial in $n$. One of such extension is the two-variable fragment with counting quantifiers. In this paper, we prove that adding a linear order axiom (which forces one of the predicates in $ϕ$ to introduce a linear ordering of the domain elements in each model of $ϕ$) on top of the counting quantifiers still permits a computation time polynomial in the domain size. We present a new dynamic programming-based algorithm which can compute WFOMC with linear order in time polynomial in $n$, thus proving our primary claim.
