Abstraction-Refinement for Hierarchical Probabilistic Models

• URL: http://arxiv.org/abs/2206.02653v1
• Date: Mon, 6 Jun 2022 14:44:36 GMT
• Title: Abstraction-Refinement for Hierarchical Probabilistic Models
• Authors: Sebastian Junges, Matthijs T. J. Spaan
• Abstract summary: We exploit a hierarchical structure with repetitive parts to verify Markov decision processes. In this paper, we focus on a local case, in which the subroutines have a limited effect on the overall system state. The key ideas to accelerate analysis of such programs are (1) to treat the behavior of the subroutine as uncertain and only remove this uncertainty by a detailed analysis if needed, and (2) to abstract similar subroutines into a parametric template, and then analyse this template.
• Score: 8.959154445409057
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Markov decision processes are a ubiquitous formalism for modelling systems with non-deterministic and probabilistic behavior. Verification of these models is subject to the famous state space explosion problem. We alleviate this problem by exploiting a hierarchical structure with repetitive parts. This structure not only occurs naturally in robotics, but also in probabilistic programs describing, e.g., network protocols. Such programs often repeatedly call a subroutine with similar behavior. In this paper, we focus on a local case, in which the subroutines have a limited effect on the overall system state. The key ideas to accelerate analysis of such programs are (1) to treat the behavior of the subroutine as uncertain and only remove this uncertainty by a detailed analysis if needed, and (2) to abstract similar subroutines into a parametric template, and then analyse this template. These two ideas are embedded into an abstraction-refinement loop that analyses hierarchical MDPs. A prototypical implementation shows the efficacy of the approach.

Related papers

• Improving Probabilistic Bisimulation for MDPs Using Machine Learning [0.0]
  We propose a new technique to partition the state space of a given model to its probabilistic bisimulation classes. The approach can decrease significantly the running time compared to state-of-the-art tools.
  arXiv  Detail & Related papers  (2023-07-30T12:58:12Z)
• Splitter Orderings for Probabilistic Bisimulation [0.0]
  We propose techniques to accelerate iterative processes to partition state space of a given probabilistic model to its bisimulation classes. The proposed approaches are implemented and run on several conventional case studies and reduce the running time by one order of magnitude on average.
  arXiv  Detail & Related papers  (2023-07-17T16:30:19Z)
• Assembly Planning from Observations under Physical Constraints [65.83676649042623]
  The proposed algorithm uses a simple combination of physical stability constraints, convex optimization and Monte Carlo tree search to plan assemblies. It is efficient and, most importantly, robust to the errors in object detection and pose estimation unavoidable in any real robotic system.
  arXiv  Detail & Related papers  (2022-04-20T16:51:07Z)
• Abstracting Noisy Robot Programs [17.04153879817609]
  We describe an approach to abstraction of probabilistic and dynamic systems. Based on a variant of the situation calculus with probabilistic belief, we define a notion of bisimulation. We obtain abstract Golog programs that omit unnecessary details and which can be translated back to a detailed program for actual execution.
  arXiv  Detail & Related papers  (2022-04-07T16:04:19Z)
• Scalable Intervention Target Estimation in Linear Models [52.60799340056917]
  Current approaches to causal structure learning either work with known intervention targets or use hypothesis testing to discover the unknown intervention targets. This paper proposes a scalable and efficient algorithm that consistently identifies all intervention targets. The proposed algorithm can be used to also update a given observational Markov equivalence class into the interventional Markov equivalence class.
  arXiv  Detail & Related papers  (2021-11-15T03:16:56Z)
• Symbolic Regression by Exhaustive Search: Reducing the Search Space Using Syntactical Constraints and Efficient Semantic Structure Deduplication [2.055204980188575]
  Symbolic regression is a powerful system identification technique in industrial scenarios where no prior knowledge on model structure is available. In this chapter we introduce a deterministic symbolic regression algorithm specifically designed to address these issues. A finite enumeration of all possible models is guaranteed by structural restrictions as well as a caching mechanism for detecting semantically equivalent solutions.
  arXiv  Detail & Related papers  (2021-09-28T17:47:51Z)
• Complex Event Forecasting with Prediction Suffix Trees: Extended Technical Report [70.7321040534471]
  Complex Event Recognition (CER) systems have become popular in the past two decades due to their ability to "instantly" detect patterns on real-time streams of events. There is a lack of methods for forecasting when a pattern might occur before such an occurrence is actually detected by a CER engine. We present a formal framework that attempts to address the issue of Complex Event Forecasting.
  arXiv  Detail & Related papers  (2021-09-01T09:52:31Z)
• Mitigating Performance Saturation in Neural Marked Point Processes: Architectures and Loss Functions [50.674773358075015]
  We propose a simple graph-based network structure called GCHP, which utilizes only graph convolutional layers. We show that GCHP can significantly reduce training time and the likelihood ratio loss with interarrival time probability assumptions can greatly improve the model performance.
  arXiv  Detail & Related papers  (2021-07-07T16:59:14Z)
• Tractable Inference in Credal Sentential Decision Diagrams [116.6516175350871]
  Probabilistic sentential decision diagrams are logic circuits where the inputs of disjunctive gates are annotated by probability values. We develop the credal sentential decision diagrams, a generalisation of their probabilistic counterpart that allows for replacing the local probabilities with credal sets of mass functions. For a first empirical validation, we consider a simple application based on noisy seven-segment display images.
  arXiv  Detail & Related papers  (2020-08-19T16:04:34Z)
• Structural Causal Models Are (Solvable by) Credal Networks [70.45873402967297]
  Causal inferences can be obtained by standard algorithms for the updating of credal nets. This contribution should be regarded as a systematic approach to represent structural causal models by credal networks. Experiments show that approximate algorithms for credal networks can immediately be used to do causal inference in real-size problems.
  arXiv  Detail & Related papers  (2020-08-02T11:19:36Z)
• Probabilistic Performance-Pattern Decomposition (PPPD): analysis framework and applications to stochastic mechanical systems [8.975760915194765]
  The paper proposes a framework to obtain structuralized characterizations on behaviors of systems. The framework is named Probabilistic Performance-Pattern Decomposition (PPPD)
  arXiv  Detail & Related papers  (2020-03-04T17:18:43Z)

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.