Lifted Inference with Linear Order Axiom

• URL: http://arxiv.org/abs/2211.01164v1
• Date: Wed, 2 Nov 2022 14:38:01 GMT
• Title: Lifted Inference with Linear Order Axiom
• Authors: Jan T\'oth, Ond\v{r}ej Ku\v{z}elka
• Abstract summary: We consider the task of weighted first-order model counting (WFOMC) We show that WFOMC of any logical sentence with at most two logical variables can be done in time in $n$. We present a new dynamic programming-based algorithm which can compute WFOMC with linear order in time in $n$.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $\phi$, domain size $n$ and a pair of weight functions, what is the weighted sum of all models of $\phi$ 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 $\phi$ to introduce a linear ordering of the domain elements in each model of $\phi$) 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.

Related papers

• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  We show that for any $K$, there is a universal set" $U subset [n]$ of size independent of $n$, such that for any $Q$ and any row $i$, the large attention scores $A_i,j$ in row $i$ of $A$ all have $jin U$. We empirically show the benefits of our scheme for vision transformers, showing how to train new models that use our universal set while training as well.
  arXiv  Detail & Related papers  (2024-10-07T19:47:13Z)
• Bridging Weighted First Order Model Counting and Graph Polynomials [6.2686964302152735]
  We use Weak Connectedness Polynomial and Strong Connectedness Polynomials for first-order logic sentences. We can use them to solve WFOMC with all of the existing axioms known to be tractable.
  arXiv  Detail & Related papers  (2024-07-16T16:01:25Z)
• Lifted Inference beyond First-Order Logic [8.577974472273256]
  We show that any $mathrmC2$ sentence remains domain liftable when one of its relational properties is a directed acyclic graph, a connected graph, a tree or a forest. Our results rely on a novel and general methodology of "counting by splitting"
  arXiv  Detail & Related papers  (2023-08-22T18:58:21Z)
• Weighted First Order Model Counting with Directed Acyclic Graph Axioms [7.766921168069532]
  Probabilistic inference and learning in many SRL can be reduced to Weighted First Model Counting (WFOMC) WFOMC is known to be intractable ($mathrm#P$ complete) We show that the fragment $mathrmC2$ with a Directed Acyclic Graph (DAG)exclusion, i.e., a axiomatized to represent axiom DAG, is domain liftable.
  arXiv  Detail & Related papers  (2023-02-20T08:35:13Z)
• On Exact Sampling in the Two-Variable Fragment of First-Order Logic [8.784424696800214]
  We show that there exists a sampling algorithm for $mathbfFO2$ that runs in time in the domain size. Our proposed method is constructive, and the resulting sampling algorithms have potential applications in various areas.
  arXiv  Detail & Related papers  (2023-02-06T12:15:41Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  We consider episodic reinforcement learning in reward-mixing Markov decision processes (RMMDPs) Our goal is to learn a near-optimal policy that nearly maximizes the $H$ time-step cumulative rewards in such a model.
  arXiv  Detail & Related papers  (2022-10-05T22:52:00Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n. We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
  arXiv  Detail & Related papers  (2022-09-04T10:01:39Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  One of its most powerful and successful modalities approximates every distribution to an $ell$ distance essentially at most a constant times larger than its closest $t$-piece degree-$d_$. We provide a method that estimates this number near-optimally, hence helps approach the best possible approximation.
  arXiv  Detail & Related papers  (2022-02-15T03:49:28Z)
• On polynomially many queries to NP or QMA oracles [0.0]
  We study the complexity of problems solvable in deterministic time with access to an NP or Quantum Merlin-Arthur (QMA)-oracle. We first show that for any verification class $CinNP,MA,QMA,QMA(2),NEXP,QMA_exp$, any $PC$ machine with a query graph of "separator number" $s$ can be simulated. We then show how to combine Gottlob's "admissible-weighting function" framework with the "flag-qubit" framework.
  arXiv  Detail & Related papers  (2021-11-03T15:29:01Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
  arXiv  Detail & Related papers  (2020-12-14T18:14:08Z)
• On the Modularity of Hypernetworks [103.1147622394852]
  We show that for a structured target function, the overall number of trainable parameters in a hypernetwork is smaller by orders of magnitude than the number of trainable parameters of a standard neural network and an embedding method.
  arXiv  Detail & Related papers  (2020-02-23T22:51:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.