Synthesising Recursive Functions for First-Order Model Counting:
Challenges, Progress, and Conjectures
- URL: http://arxiv.org/abs/2306.04189v1
- Date: Wed, 7 Jun 2023 06:49:01 GMT
- Title: Synthesising Recursive Functions for First-Order Model Counting:
Challenges, Progress, and Conjectures
- Authors: Paulius Dilkas, Vaishak Belle
- Abstract summary: First-order model counting (FOMC) is a computational problem that asks to count the models of a sentence in finite-domain first-order logic.
We relax the restrictions that typically accompany domain recursion to work with directed graphs that may contain cycles.
These improvements allow the algorithm to find efficient solutions to counting problems that were previously beyond its reach.
- Score: 12.47276164048813
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: First-order model counting (FOMC) is a computational problem that asks to
count the models of a sentence in finite-domain first-order logic. In this
paper, we argue that the capabilities of FOMC algorithms to date are limited by
their inability to express many types of recursive computations. To enable such
computations, we relax the restrictions that typically accompany domain
recursion and generalise the circuits used to express a solution to an FOMC
problem to directed graphs that may contain cycles. To this end, we adapt the
most well-established (weighted) FOMC algorithm ForcLift to work with such
graphs and introduce new compilation rules that can create cycle-inducing edges
that encode recursive function calls. These improvements allow the algorithm to
find efficient solutions to counting problems that were previously beyond its
reach, including those that cannot be solved efficiently by any other exact
FOMC algorithm. We end with a few conjectures on what classes of instances
could be domain-liftable as a result.
Related papers
- When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation [49.1574468325115]
We show how no (randomised) algorithm can determine the correct support sets (with probability $> 1/2$) of minimisers of LASSO when reading approximate input.
For ill-posed inputs, the algorithm runs forever, hence, it will never produce a wrong answer.
For any algorithm defined on an open set containing a point with infinite condition number, there is an input for which the algorithm will either run forever or produce a wrong answer.
arXiv Detail & Related papers (2023-12-18T18:29:01Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
Constrained optimization problems abound in industry, from portfolio optimization to logistics.
One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space.
In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
arXiv Detail & Related papers (2022-11-16T18:59:54Z) - Output-sensitive ERM-based techniques for data-driven algorithm design [29.582038951852553]
We study techniques to develop efficient learning algorithms for data-driven algorithm design.
Our approach involves two novel ingredients -- an output-sensitive algorithm for enumerating polytopes induced by a set of hyperplanes.
We illustrate our techniques by giving algorithms for pricing problems, linkage-based clustering and dynamic-programming based sequence alignment.
arXiv Detail & Related papers (2022-04-07T17:27:18Z) - Scalable Anytime Algorithms for Learning Formulas in Linear Temporal
Logic [2.631744051718347]
We consider the problem of learning formulas for classifying traces.
Existing solutions suffer from two limitations: they do not scale beyond small formulas, and they may exhaust computational resources without returning any result.
We introduce a new algorithm addressing both issues: our algorithm is able to construct formulas an order of magnitude larger than previous methods, and it is anytime.
arXiv Detail & Related papers (2021-10-13T13:57:31Z) - Strengthening Probabilistic Graphical Models: The Purge-and-merge
Algorithm [0.0]
purge-and-merge algorithm is designed to nudge a malleable graph structure towards a tree structure by selectively merging factors.
This approach is evaluated on a number of constraint-satisfaction puzzles such as Sudoku, Fill-a-pix, and Kakuro.
Although these tasks were limited to the binary logic of CSP, we believe it holds promise for extension to general PGM inference.
arXiv Detail & Related papers (2021-09-30T21:20:52Z) - Dynamic programming by polymorphic semiring algebraic shortcut fusion [1.9405875431318445]
Dynamic programming (DP) is an algorithmic design paradigm for the efficient, exact solution of intractable, problems.
This paper presents a rigorous algebraic formalism for systematically deriving DP algorithms, based on semiring.
arXiv Detail & Related papers (2021-07-05T00:51:02Z) - Non-approximate Inference for Collective Graphical Models on Path Graphs
via Discrete Difference of Convex Algorithm [19.987509826212115]
This paper proposes a new method for MAP inference for Collective Graphical Model (CGM) on path graphs.
First we show that the MAP inference problem can be formulated as a (non-linear) minimum cost flow problem.
In our algorithm, important subroutines in DCA can be efficiently calculated by minimum convex cost flow algorithms.
arXiv Detail & Related papers (2021-02-18T07:28:18Z) - Boosting Data Reduction for the Maximum Weight Independent Set Problem
Using Increasing Transformations [59.84561168501493]
We introduce new generalized data reduction and transformation rules for the maximum weight independent set problem.
Surprisingly, these so-called increasing transformations can simplify the problem and also open up the reduction space to yield even smaller irreducible graphs later in the algorithm.
Our algorithm computes significantly smaller irreducible graphs on all except one instance, solves more instances to optimality than previously possible, is up to two orders of magnitude faster than the best state-of-the-art solver, and finds higher-quality solutions than solvers DynWVC and HILS.
arXiv Detail & Related papers (2020-08-12T08:52:50Z) - Sparsified Linear Programming for Zero-Sum Equilibrium Finding [89.30539368124025]
We present a totally different approach to the problem, which is competitive and often orders of magnitude better than the prior state of the art.
With experiments on poker endgames, we demonstrate, for the first time, that modern linear program solvers are competitive against even game-specific modern variants of CFR.
arXiv Detail & Related papers (2020-06-05T13:48:26Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
A fundamental component of neural network verification is the computation of bounds on the values their outputs can take.
We propose a novel approach based on Lagrangian Decomposition.
We show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time.
arXiv Detail & Related papers (2020-02-24T17:55:10Z) - Polynomial-Time Exact MAP Inference on Discrete Models with Global
Dependencies [83.05591911173332]
junction tree algorithm is the most general solution for exact MAP inference with run-time guarantees.
We propose a new graph transformation technique via node cloning which ensures a run-time for solving our target problem independently of the form of a corresponding clique tree.
arXiv Detail & Related papers (2019-12-27T13:30:29Z)
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.