MAP Inference for Probabilistic Logic Programming

• URL: http://arxiv.org/abs/2008.01394v3
• Date: Tue, 1 Sep 2020 07:27:13 GMT
• Title: MAP Inference for Probabilistic Logic Programming
• Authors: Elena Bellodi, Marco Alberti, Fabrizio Riguzzi, Riccardo Zese
• Abstract summary: We consider the Maximum-A-Posteriori (MAP) inference task and the Most Probable Explanation (MPE) task. We present a novel algorithm, included in the PITA reasoner, which tackles these tasks by representing each problem as a Binary Decision Diagram. We compare our algorithm with the version of ProbLog that admits annotated disjunctions and can perform MAP and MPE inference.
• Score: 0.30586855806896046
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In Probabilistic Logic Programming (PLP) the most commonly studied inference task is to compute the marginal probability of a query given a program. In this paper, we consider two other important tasks in the PLP setting: the Maximum-A-Posteriori (MAP) inference task, which determines the most likely values for a subset of the random variables given evidence on other variables, and the Most Probable Explanation (MPE) task, the instance of MAP where the query variables are the complement of the evidence variables. We present a novel algorithm, included in the PITA reasoner, which tackles these tasks by representing each problem as a Binary Decision Diagram and applying a dynamic programming procedure on it. We compare our algorithm with the version of ProbLog that admits annotated disjunctions and can perform MAP and MPE inference. Experiments on several synthetic datasets show that PITA outperforms ProbLog in many cases.

Related papers

• Probabilistic Answer Set Programming with Discrete and Continuous Random Variables [0.18416014644193066]
  Probabilistic Answer Set Programming (PASP) extends Answer Set Programming with probabilistic facts that represent uncertain information. We propose Hybrid Probabilistic Answer Set Programming (HPASP) We discuss, implement, and assess the performance of two exact algorithms based on projected answer set enumeration and knowledge compilation.
  arXiv  Detail & Related papers  (2024-09-30T13:24:42Z)
• 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)
• 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)
• Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach [57.788675205519986]
  We learn high-quality traces from POMDP executions generated by any solver. We exploit data- and time-efficient Indu Logic Programming (ILP) to generate interpretable belief-based policy specifications. We show that learneds expressed in Answer Set Programming (ASP) yield performance superior to neural networks and similar to optimal handcrafted task-specifics within lower computational time.
  arXiv  Detail & Related papers  (2024-02-29T15:36:01Z)
• Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP [81.00800920928621]
  We study representation learning in partially observable Markov Decision Processes (POMDPs) We first present an algorithm for decodable POMDPs that combines maximum likelihood estimation (MLE) and optimism in the face of uncertainty (OFU) We then show how to adapt this algorithm to also work in the broader class of $gamma$-observable POMDPs.
  arXiv  Detail & Related papers  (2023-06-21T16:04:03Z)
• $\omega$PAP Spaces: Reasoning Denotationally About Higher-Order, Recursive Probabilistic and Differentiable Programs [64.25762042361839]
  $omega$PAP spaces are spaces for reasoning denotationally about expressive differentiable and probabilistic programming languages. Our semantics is general enough to assign meanings to most practical probabilistic and differentiable programs. We establish the almost-everywhere differentiability of probabilistic programs' trace density functions.
  arXiv  Detail & Related papers  (2023-02-21T12:50:05Z)
• SMProbLog: Stable Model Semantics in ProbLog and its Applications in Argumentation [17.71804768917815]
  SMProbLog is a generalization of the probabilistic logic programming language ProbLog. We show how SMProbLog can be used to reason about probabilistic argumentation problems.
  arXiv  Detail & Related papers  (2021-10-05T12:29:22Z)
• pRSL: Interpretable Multi-label Stacking by Learning Probabilistic Rules [0.0]
  We present the probabilistic rule stacking (pRSL) which uses probabilistic propositional logic rules and belief propagation to combine the predictions of several underlying classifiers. We derive algorithms for exact and approximate inference and learning, and show that pRSL reaches state-of-the-art performance on various benchmark datasets.
  arXiv  Detail & Related papers  (2021-05-28T14:06:21Z)
• 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)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Planning in Markov Decision Processes with Gap-Dependent Sample Complexity [48.98199700043158]
  We propose MDP-GapE, a new trajectory-based Monte-Carlo Tree Search algorithm for planning in a Markov Decision Process. We prove an upper bound on the number of calls to the generative models needed for MDP-GapE to identify a near-optimal action with high probability.
  arXiv  Detail & Related papers  (2020-06-10T15:05:51Z)

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.