Generating Random Logic Programs Using Constraint Programming

• URL: http://arxiv.org/abs/2006.01889v2
• Date: Fri, 11 Sep 2020 16:40:31 GMT
• Title: Generating Random Logic Programs Using Constraint Programming
• Authors: Paulius Dilkas, Vaishak Belle
• Abstract summary: We present a novel approach to generating random logic programs using constraint programming. We show how the model scales with parameter values, and use the model to compare probabilistic inference algorithms across a range of synthetic problems.
• Score: 12.47276164048813
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Testing algorithms across a wide range of problem instances is crucial to ensure the validity of any claim about one algorithm's superiority over another. However, when it comes to inference algorithms for probabilistic logic programs, experimental evaluations are limited to only a few programs. Existing methods to generate random logic programs are limited to propositional programs and often impose stringent syntactic restrictions. We present a novel approach to generating random logic programs and random probabilistic logic programs using constraint programming, introducing a new constraint to control the independence structure of the underlying probability distribution. We also provide a combinatorial argument for the correctness of the model, show how the model scales with parameter values, and use the model to compare probabilistic inference algorithms across a range of synthetic problems. Our model allows inference algorithm developers to evaluate and compare the algorithms across a wide range of instances, providing a detailed picture of their (comparative) strengths and weaknesses.

Related papers

• Solving Decision Theory Problems with Probabilistic Answer Set Programming [1.4999444543328293]
  We introduce the possibility to encode decision theory problems with Probabilistic Answer Set Programming. Our algorithm can manage non trivial instances of programs in a reasonable amount of time.
  arXiv  Detail & Related papers  (2024-08-21T06:44:16Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms. In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
  arXiv  Detail & Related papers  (2023-12-19T13:17:43Z)
• Marginal Inference queries in Hidden Markov Models under context-free grammar constraints [0.348097307252416]
  We address the question of computing the likelihood of context-free grammars (CFGs) in Hidden Models (HMMs) We show that the problem is NP-Hard, even with the promise that CFG has a degree of ambiguity less than or equal to 2. We then propose a fully randomized approximation scheme to approximate the likelihood for the case of ambiguous CFGs.
  arXiv  Detail & Related papers  (2022-06-26T12:44:18Z)
• An Application of a Multivariate Estimation of Distribution Algorithm to Cancer Chemotherapy [59.40521061783166]
  Chemotherapy treatment for cancer is a complex optimisation problem with a large number of interacting variables and constraints. We show that the more sophisticated algorithm would yield better performance on a complex problem like this. We hypothesise that this is caused by the more sophisticated algorithm being impeded by the large number of interactions in the problem.
  arXiv  Detail & Related papers  (2022-05-17T15:28:46Z)
• Program Analysis of Probabilistic Programs [3.299672391663527]
  dissertation presents three novel techniques to improve probabilistic programming using program analysis. The techniques analyse a probabilistic program and adapt it to make inference more efficient, sometimes in a way that would have been tedious or impossible to do by hand.
  arXiv  Detail & Related papers  (2022-04-14T10:40:54Z)
• Logical Credal Networks [87.25387518070411]
  This paper introduces Logical Credal Networks, an expressive probabilistic logic that generalizes many prior models that combine logic and probability. We investigate its performance on maximum a posteriori inference tasks, including solving Mastermind games with uncertainty and detecting credit card fraud.
  arXiv  Detail & Related papers  (2021-09-25T00:00:47Z)
• A Unified View of Algorithms for Path Planning Using Probabilistic Inference on Factor Graphs [2.4874504720536317]
  This work looks at the specific recursions that arise from various cost functions that, although they may appear similar in scope, bear differences, at least when applied to typical path planning problems. We show how this unified approach, presented both in probability space and in log space, provides a very general framework that includes the Sum-product, the Max-product, Dynamic programming and mixed Reward/Entropy criteria-based algorithms.
  arXiv  Detail & Related papers  (2021-06-19T07:13:15Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  We develop a two-stage framework, in which reinforcement learning (RL) and traditional operations research (OR) algorithms are combined together. The scheduling problem is solved in two stages, including a finite Markov decision process (MDP) and a mixed-integer programming process, respectively. Results show that the proposed algorithms could stably and efficiently obtain satisfactory scheduling schemes for agile Earth observation satellite scheduling problems.
  arXiv  Detail & Related papers  (2021-03-10T03:16:12Z)
• A Constraint-Based Algorithm for the Structural Learning of Continuous-Time Bayesian Networks [70.88503833248159]
  We propose the first constraint-based algorithm for learning the structure of continuous-time Bayesian networks. We discuss the different statistical tests and the underlying hypotheses used by our proposal to establish conditional independence.
  arXiv  Detail & Related papers  (2020-07-07T07:34:09Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)
• Stochastic Probabilistic Programs [1.90365714903665]
  We introduce the notion of a probabilistic program and present a reference implementation of a probabilistic programming facility supporting specification of programs and inference in them. We give several examples of probabilistic programs, and compare the programs with corresponding deterministic probabilistic programs in terms of model specification and inference.
  arXiv  Detail & Related papers  (2020-01-08T17:54:40Z)

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.