From Probabilistic Programming to Complexity-based Programming

• URL: http://arxiv.org/abs/2307.15453v2
• Date: Mon, 11 Sep 2023 14:06:27 GMT
• Title: From Probabilistic Programming to Complexity-based Programming
• Authors: Giovanni Sileno, Jean-Louis Dessalles
• Abstract summary: The paper presents the main characteristics and a preliminary implementation of a novel computational framework named CompLog. Inspired by probabilistic programming systems like ProbLog, CompLog builds upon the inferential mechanisms proposed by Simplicity Theory. The proposed system enables users to compute ex-post and ex-ante measures of unexpectedness of a certain situation.
• Score: 0.5874142059884521
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The paper presents the main characteristics and a preliminary implementation of a novel computational framework named CompLog. Inspired by probabilistic programming systems like ProbLog, CompLog builds upon the inferential mechanisms proposed by Simplicity Theory, relying on the computation of two Kolmogorov complexities (here implemented as min-path searches via ASP programs) rather than probabilistic inference. The proposed system enables users to compute ex-post and ex-ante measures of unexpectedness of a certain situation, mapping respectively to posterior and prior subjective probabilities. The computation is based on the specification of world and mental models by means of causal and descriptive relations between predicates weighted by complexity. The paper illustrates a few examples of application: generating relevant descriptions, and providing alternative approaches to disjunction and to negation.

Related papers

• Symbolic Parameter Learning in Probabilistic Answer Set Programming [0.16385815610837165]
  We propose two algorithms to solve the formalism of Proabilistic Set Programming. The first solves the task using an off-the-shelf constrained optimization solver. The second is based on an implementation of the Expectation Maximization algorithm.
  arXiv  Detail & Related papers  (2024-08-16T13:32:47Z)
• Advancing Algorithmic Approaches to Probabilistic Argumentation under the Constellation Approach [0.0]
  We develop an algorithm for the complex task of computing the probability of a set of arguments being a complete extension. An experimental evaluation shows promise of our approach.
  arXiv  Detail & Related papers  (2024-07-06T12:08:38Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  We discuss the problem of bounding partially identifiable queries, such as counterfactuals, in Pearlian structural causal models. A recently proposed iterated EM scheme yields an inner approximation of those bounds by sampling the initialisation parameters. We show how a single symbolic knowledge compilation allows us to obtain the circuit structure with symbolic parameters to be replaced by their actual values.
  arXiv  Detail & Related papers  (2023-10-05T07:10:40Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  Low-Rank Markov Decision Processes offer a simple, yet expressive framework for RL with function approximation. Existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions. We propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs.
  arXiv  Detail & Related papers  (2023-07-08T15:41:48Z)
• Scalable Neural-Probabilistic Answer Set Programming [18.136093815001423]
  We introduce SLASH, a novel DPPL that consists of Neural-Probabilistic Predicates (NPPs) and a logic program, united via answer set programming (ASP) We show how to prune the insignificantally insignificant parts of the (ground) program, speeding up reasoning without sacrificing the predictive performance. We evaluate SLASH on a variety of different tasks, including the benchmark task of MNIST addition and Visual Question Answering (VQA)
  arXiv  Detail & Related papers  (2023-06-14T09:45:29Z)
• Compositional Probabilistic and Causal Inference using Tractable Circuit Models [20.07977560803858]
  We introduce md-vtrees, a novel structural formulation of (marginal) determinism in structured decomposable PCs. We derive the first polytime algorithms for causal inference queries such as backdoor adjustment on PCs.
  arXiv  Detail & Related papers  (2023-04-17T13:48:16Z)
• Multivariate Systemic Risk Measures and Computation by Deep Learning Algorithms [63.03966552670014]
  We discuss the key related theoretical aspects, with a particular focus on the fairness properties of primal optima and associated risk allocations. The algorithms we provide allow for learning primals, optima for the dual representation and corresponding fair risk allocations.
  arXiv  Detail & Related papers  (2023-02-02T22:16:49Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  This work proposes a formal definition of statistically meaningful (SM) approximation which requires the approximating network to exhibit good statistical learnability. We study SM approximation for two function classes: circuits and Turing machines.
  arXiv  Detail & Related papers  (2021-07-28T04:28:55Z)
• Online Learning Probabilistic Event Calculus Theories in Answer Set Programming [70.06301658267125]
  Event Recognition (CER) systems detect occurrences in streaming time-stamped datasets using predefined event patterns. We present a system based on Answer Set Programming (ASP), capable of probabilistic reasoning with complex event patterns in the form of rules weighted in the Event Calculus. Our results demonstrate the superiority of our novel approach, both terms efficiency and predictive.
  arXiv  Detail & Related papers  (2021-03-31T23:16:29Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  We propose an efficient method for computing the partition function or MAP estimate in a pairwise MRF. We extend semidefinite relaxations from the typical binary MRF to the full multi-class setting, and develop a compact semidefinite relaxation that can again be solved efficiently using the solver.
  arXiv  Detail & Related papers  (2020-12-04T15:36:29Z)
• Information-Theoretic Abstractions for Planning in Agents with Computational Constraints [16.565205172451662]
  We show how a path-planning problem in an environment can be systematically approximated by solving a sequence of easier to solve problems on abstractions of the original space. A numerical example is presented to show the utility of the approach and to corroborate the theoretical findings.
  arXiv  Detail & Related papers  (2020-05-19T17:32:10Z)

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.