Symbolic Parallel Adaptive Importance Sampling for Probabilistic Program Analysis

• URL: http://arxiv.org/abs/2010.05050v2
• Date: Thu, 17 Jun 2021 19:32:14 GMT
• Title: Symbolic Parallel Adaptive Importance Sampling for Probabilistic Program Analysis
• Authors: Yicheng Luo, Antonio Filieri, Yuan Zhou
• Abstract summary: Probabilistic software analysis aims at quantifying the probability of a target event occurring during the execution of a program. We present SYMbolic Parallel Adaptive Importance Sampling (SYMPAIS), a new inference method tailored to analyze path conditions generated from the symbolic execution of programs.
• Score: 9.204612164524947
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Probabilistic software analysis aims at quantifying the probability of a target event occurring during the execution of a program processing uncertain incoming data or written itself using probabilistic programming constructs. Recent techniques combine symbolic execution with model counting or solution space quantification methods to obtain accurate estimates of the occurrence probability of rare target events, such as failures in a mission-critical system. However, they face several scalability and applicability limitations when analyzing software processing with high-dimensional and correlated multivariate input distributions. In this paper, we present SYMbolic Parallel Adaptive Importance Sampling (SYMPAIS), a new inference method tailored to analyze path conditions generated from the symbolic execution of programs with high-dimensional, correlated input distributions. SYMPAIS combines results from importance sampling and constraint solving to produce accurate estimates of the satisfaction probability for a broad class of constraints that cannot be analyzed by current solution space quantification methods. We demonstrate SYMPAIS's generality and performance compared with state-of-the-art alternatives on a set of problems from different application domains.

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)
• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [61.580419063416734]
  A recent stream of structured learning approaches has improved the practical state of the art for a range of optimization problems. The key idea is to exploit the statistical distribution over instances instead of dealing with instances separately. In this article, we investigate methods that smooth the risk by perturbing the policy, which eases optimization and improves the generalization error.
  arXiv  Detail & Related papers  (2024-07-24T12:00:30Z)
• Embedding Trajectory for Out-of-Distribution Detection in Mathematical Reasoning [50.84938730450622]
  We propose a trajectory-based method TV score, which uses trajectory volatility for OOD detection in mathematical reasoning. Our method outperforms all traditional algorithms on GLMs under mathematical reasoning scenarios. Our method can be extended to more applications with high-density features in output spaces, such as multiple-choice questions.
  arXiv  Detail & Related papers  (2024-05-22T22:22:25Z)
• Bayesian sequential design of computer experiments for quantile set inversion [0.0]
  We consider an unknown multivariate function representing a system-such as a complex numerical simulator. Our objective is to estimate the set of deterministic inputs leading to outputs whose probability is less than a given threshold.
  arXiv  Detail & Related papers  (2022-11-02T10:14:05Z)
• Semantic Probabilistic Layers for Neuro-Symbolic Learning [83.25785999205932]
  We design a predictive layer for structured-output prediction (SOP) It can be plugged into any neural network guaranteeing its predictions are consistent with a set of predefined symbolic constraints. Our Semantic Probabilistic Layer (SPL) can model intricate correlations, and hard constraints, over a structured output space.
  arXiv  Detail & Related papers  (2022-06-01T12:02:38Z)
• 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)
• 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)
• SPPL: Probabilistic Programming with Fast Exact Symbolic Inference [2.371061885439857]
  Sum-Product Probabilistic Language (SPPL) delivers exact solutions to a broad range of probabilistic inference queries. SPPL translates probabilistic programs into sum-product expressions, a new symbolic representation and associated semantic domain. We implement a prototype of SPPL with a modular architecture and evaluate it on benchmarks the system targets.
  arXiv  Detail & Related papers  (2020-10-07T15:42:37Z)
• Transforming Probabilistic Programs for Model Checking [0.0]
  We apply static analysis to probabilistic programs to automate large parts of two crucial model checking methods. Our method transforms a probabilistic program specifying a density function into an efficient forward-sampling form. We present an implementation targeting the popular Stan probabilistic programming language.
  arXiv  Detail & Related papers  (2020-08-21T21:06:34Z)
• A Framework for Sample Efficient Interval Estimation with Control Variates [94.32811054797148]
  We consider the problem of estimating confidence intervals for the mean of a random variable. Under certain conditions, we show improved efficiency compared to existing estimation algorithms.
  arXiv  Detail & Related papers  (2020-06-18T05:42:30Z)
• 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.