Weighted First Order Model Counting with Directed Acyclic Graph Axioms

• URL: http://arxiv.org/abs/2302.09830v2
• Date: Mon, 8 May 2023 16:01:39 GMT
• Title: Weighted First Order Model Counting with Directed Acyclic Graph Axioms
• Authors: Sagar Malhotra and Luciano Serafini
• Abstract summary: 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.
• Score: 7.766921168069532
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Statistical Relational Learning (SRL) integrates First-Order Logic (FOL) and probability theory for learning and inference over relational data. Probabilistic inference and learning in many SRL models can be reduced to Weighted First Order Model Counting (WFOMC). However, WFOMC is known to be intractable ($\mathrm{\#P_1-}$ complete). Hence, logical fragments that admit polynomial time WFOMC are of significant interest. Such fragments are called domain liftable. Recent line of works have shown the two-variable fragment of FOL, extended with counting quantifiers ($\mathrm{C^2}$) to be domain-liftable. However, many properties of real-world data can not be modelled in $\mathrm{C^2}$. In fact many ubiquitous properties of real-world data are inexressible in FOL. Acyclicity is one such property, found in citation networks, genealogy data, temporal data e.t.c. In this paper we aim to address this problem by investigating the domain liftability of directed acyclicity constraints. We show that the fragment $\mathrm{C^2}$ with a Directed Acyclic Graph (DAG) axiom, i.e., a predicate in the language is axiomatized to represent a DAG, is domain-liftable. We present a method based on principle of inclusion-exclusion for WFOMC of $\mathrm{C^2}$ formulas extended with DAG axioms.

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)
• Data subsampling for Poisson regression with pth-root-link [53.63838219437508]
  We develop and analyze data subsampling techniques for Poisson regression. In particular, we consider the Poisson generalized linear model with ID- and square root-link functions.
  arXiv  Detail & Related papers  (2024-10-30T10:09:05Z)
• 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)
• 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)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• 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)
• 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)
• Diffusion Models for Causal Discovery via Topological Ordering [20.875222263955045]
  emphTopological ordering approaches reduce the optimisation space of causal discovery by searching over a permutation rather than graph space. For ANMs, the emphHessian of the data log-likelihood can be used for finding leaf nodes in a causal graph, allowing its topological ordering. We introduce theory for updating the learned Hessian without re-training the neural network, and we show that computing with a subset of samples gives an accurate approximation of the ordering.
  arXiv  Detail & Related papers  (2022-10-12T13:36:29Z)
• Learning from aggregated data with a maximum entropy model [73.63512438583375]
  We show how a new model, similar to a logistic regression, may be learned from aggregated data only by approximating the unobserved feature distribution with a maximum entropy hypothesis. We present empirical evidence on several public datasets that the model learned this way can achieve performances comparable to those of a logistic model trained with the full unaggregated data.
  arXiv  Detail & Related papers  (2022-10-05T09:17:27Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  We develop effective Monte Carlo algorithms to approximate the optimal bounds from an arbitrary combination of observational and experimental data. Our algorithms are validated extensively on synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2021-10-12T02:21:30Z)
• Weighted Model Counting in the two variable fragment with Cardinality Constraints: A Closed Form Formula [7.766921168069532]
  Weighted First-Order Model Counting (WFOMC) computes the weighted sum of the models of a first-order theory on a given finite domain. We introduce the concept of lifted interpretations as a tool for formulating inferences for WFOMC. We then expand this closed-form to incorporate existential quantifiers and cardinality constraints without losing domain-liftability.
  arXiv  Detail & Related papers  (2020-09-25T13:50:18Z)

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.