Scaling up Hybrid Probabilistic Inference with Logical and Arithmetic Constraints via Message Passing

• URL: http://arxiv.org/abs/2003.00126v2
• Date: Wed, 19 Aug 2020 22:41:13 GMT
• Title: Scaling up Hybrid Probabilistic Inference with Logical and Arithmetic Constraints via Message Passing
• Authors: Zhe Zeng, Paolo Morettin, Fanqi Yan, Antonio Vergari, Guy Van den Broeck
• Abstract summary: Weighted model integration allows to express the complex dependencies of real-world problems. Existing WMI solvers are not ready to scale to these problems. We devise a scalable WMI solver based on message passing, MP-WMI.
• Score: 38.559697064390015
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Weighted model integration (WMI) is a very appealing framework for probabilistic inference: it allows to express the complex dependencies of real-world problems where variables are both continuous and discrete, via the language of Satisfiability Modulo Theories (SMT), as well as to compute probabilistic queries with complex logical and arithmetic constraints. Yet, existing WMI solvers are not ready to scale to these problems. They either ignore the intrinsic dependency structure of the problem at all, or they are limited to too restrictive structures. To narrow this gap, we derive a factorized formalism of WMI enabling us to devise a scalable WMI solver based on message passing, MP-WMI. Namely, MP-WMI is the first WMI solver which allows to: 1) perform exact inference on the full class of tree-structured WMI problems; 2) compute all marginal densities in linear time; 3) amortize inference inter query. Experimental results show that our solver dramatically outperforms the existing WMI solvers on a large set of benchmarks.

Related papers

• MR-Ben: A Meta-Reasoning Benchmark for Evaluating System-2 Thinking in LLMs [55.20845457594977]
  Large language models (LLMs) have shown increasing capability in problem-solving and decision-making. We present a process-based benchmark MR-Ben that demands a meta-reasoning skill. Our meta-reasoning paradigm is especially suited for system-2 slow thinking.
  arXiv  Detail & Related papers  (2024-06-20T03:50:23Z)
• A Deep Instance Generative Framework for MILP Solvers Under Limited Data Availability [66.37474135424637]
  We propose G2MILP, the first deep generative framework for MILP instances. G2MILP represents MILP instances as bipartite graphs, and applies a masked variational autoencoder to iteratively corrupt and replace parts of the original graphs to generate new ones. We design a suite of benchmarks to evaluate the quality of the generated MILP instances.
  arXiv  Detail & Related papers  (2023-10-04T13:34:34Z)
• Multi-Grained Multimodal Interaction Network for Entity Linking [65.30260033700338]
  Multimodal entity linking task aims at resolving ambiguous mentions to a multimodal knowledge graph. We propose a novel Multi-GraIned Multimodal InteraCtion Network $textbf(MIMIC)$ framework for solving the MEL task.
  arXiv  Detail & Related papers  (2023-07-19T02:11:19Z)
• Enhancing SMT-based Weighted Model Integration by Structure Awareness [10.812681884889697]
  Weighted Model Integration (WMI) emerged as a unifying formalism for probabilistic inference in hybrid domains. We develop an algorithm that combines SMT-based enumeration, an efficient technique in formal verification, with an effective encoding of the problem structure.
  arXiv  Detail & Related papers  (2023-02-13T08:55:12Z)
• A robust estimator of mutual information for deep learning interpretability [2.574652392763709]
  We present GMM-MI, an algorithm that can be applied to both discrete and continuous settings. We extensively validate GMM-MI on toy data for which the ground truth MI is known. We then demonstrate the use of our MI estimator in the context of representation learning.
  arXiv  Detail & Related papers  (2022-10-31T18:00:02Z)
• SMT-based Weighted Model Integration with Structure Awareness [18.615397594541665]
  We develop an algorithm that combines SMT-based enumeration, an efficient technique in formal verification, with an effective encoding of the problem structure. This allows our algorithm to avoid generating redundant models, resulting in substantial computational savings.
  arXiv  Detail & Related papers  (2022-06-28T09:46:17Z)
• FERMI: Fair Empirical Risk Minimization via Exponential R\'enyi Mutual Information [17.57634911587209]
  We show that ERMI is a strong fairness violation notion in the sense that it provides upper bound guarantees on existing notions of fairness violation. We then propose the Fair Empirical Risk Minimization via ERMI regularization framework, called FERMI.
  arXiv  Detail & Related papers  (2021-02-24T22:15:44Z)
• 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)
• CLUB: A Contrastive Log-ratio Upper Bound of Mutual Information [105.73798100327667]
  We propose a novel Contrastive Log-ratio Upper Bound (CLUB) of mutual information. We provide a theoretical analysis of the properties of CLUB and its variational approximation. Based on this upper bound, we introduce a MI minimization training scheme and further accelerate it with a negative sampling strategy.
  arXiv  Detail & Related papers  (2020-06-22T05:36:16Z)
• Monte Carlo Anti-Differentiation for Approximate Weighted Model Integration [13.14502456511936]
  We introduce textit Monte Carlo anti-differentiation (MCAD) which computes MC approximations of anti-derivatives. Our experiments show that equipping existing WMI solvers with MCAD yields a fast yet reliable approximate inference scheme.
  arXiv  Detail & Related papers  (2020-01-13T23:45: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.