Lifted Inference beyond First-Order Logic

• URL: http://arxiv.org/abs/2308.11738v3
• Date: Thu, 14 Nov 2024 17:50:53 GMT
• Title: Lifted Inference beyond First-Order Logic
• Authors: Sagar Malhotra, Davide Bizzaro, Luciano Serafini,
• Abstract summary: 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"
• Score: 8.577974472273256
• License:
• Abstract: Weighted First Order Model Counting (WFOMC) is fundamental to probabilistic inference in statistical relational learning models. As WFOMC is known to be intractable in general ($\#$P-complete), logical fragments that admit polynomial time WFOMC are of significant interest. Such fragments are called domain liftable. Recent works have shown that the two-variable fragment of first order logic extended with counting quantifiers ($\mathrm{C^2}$) is domain-liftable. However, many properties of real-world data, like acyclicity in citation networks and connectivity in social networks, cannot be modeled in $\mathrm{C^2}$, or first order logic in general. In this work, we expand the domain liftability of $\mathrm{C^2}$ with multiple such properties. We show that any $\mathrm{C^2}$ sentence remains domain liftable when one of its relations is restricted to represent a directed acyclic graph, a connected graph, a tree (resp. a directed tree) or a forest (resp. a directed forest). All our results rely on a novel and general methodology of "counting by splitting". Besides their application to probabilistic inference, our results provide a general framework for counting combinatorial structures. We expand a vast array of previous results in discrete mathematics literature on directed acyclic graphs, phylogenetic networks, etc.

Related papers

• Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
  We show that for a broad class of data structures their bounds cannot be significantly improved. This is a novel emphstatistical-computational trade-off for density estimation.
  arXiv  Detail & Related papers  (2024-10-30T15:03:33Z)
• 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)
• The Quantified Boolean Bayesian Network: Theory and Experiments with a Logical Graphical Model [0.0]
  We show how a probabilistic Network can be configured to represent the logical reasoning underlying human language. For inference, we investigate the use of Loopy Belief Propagation (LBP), which is not guaranteed to converge. Our experiments show that LBP indeed does converge very reliably, and our analysis shows that a round of LBP takes time $O(N2n)$, where $N$ bounds the number of variables considered.
  arXiv  Detail & Related papers  (2024-02-09T17:15:45Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  We study the power of query access for the task of agnostic learning under the Gaussian distribution. We show that query access gives significant runtime improvements over random examples for agnostically learning MIMs.
  arXiv  Detail & Related papers  (2023-12-27T15:50:47Z)
• 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)
• Lifted Inference with Linear Order Axiom [0.0]
  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$.
  arXiv  Detail & Related papers  (2022-11-02T14:38:01Z)
• Efficient Hierarchical Domain Adaptation for Pretrained Language Models [77.02962815423658]
  Generative language models are trained on diverse, general domain corpora. We introduce a method to scale domain adaptation to many diverse domains using a computationally efficient adapter approach.
  arXiv  Detail & Related papers  (2021-12-16T11:09:29Z)
• The Performance of the MLE in the Bradley-Terry-Luce Model in $\ell_{\infty}$-Loss and under General Graph Topologies [76.61051540383494]
  We derive novel, general upper bounds on the $ell_infty$ estimation error of the Bradley-Terry-Luce model. We demonstrate that the derived bounds perform well and in some cases are sharper compared to known results.
  arXiv  Detail & Related papers  (2021-10-20T23:46:35Z)
• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results [58.277290855841976]
  We study tradeoffs of computational cost and expressive power of Graph Neural Networks (GNNs) We show that a new model can count subgraphs of size $k$, and thereby overcomes a known limitation of low-order GNNs. In several cases, the proposed algorithm can greatly reduce computational complexity compared to the existing higher-order $k$-GNNs.
  arXiv  Detail & Related papers  (2020-12-06T03:42:54Z)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  We study the power of graph neural networks (GNNs) via their ability to count attributed graph substructures. We distinguish between two types of substructure counting: inducedsubgraph-count and subgraphcount-count, and both positive and negative answers for popular GNN architectures.
  arXiv  Detail & Related papers  (2020-02-10T18:53:30Z)

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.