Variance Computation for Weighted Model Counting with Knowledge Compilation Approach

• URL: http://arxiv.org/abs/2601.03523v1
• Date: Wed, 07 Jan 2026 02:20:41 GMT
• Title: Variance Computation for Weighted Model Counting with Knowledge Compilation Approach
• Authors: Kengo Nakamura, Masaaki Nishino, Norihito Yasuda,
• Abstract summary: weighted model counting (WMC) has been applied to probabilistic inference on various models, such as Bayesian networks.<n>One possible approach is to regard the inference outcome as a random variable by introducing distributions for the parameters and evaluate the variance of the outcome.<n>We show that our algorithm can evaluate the variance of the marginal probability on real-world Bayesian networks.
• Score: 19.25442573044106
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: One of the most important queries in knowledge compilation is weighted model counting (WMC), which has been applied to probabilistic inference on various models, such as Bayesian networks. In practical situations on inference tasks, the model's parameters have uncertainty because they are often learned from data, and thus we want to compute the degree of uncertainty in the inference outcome. One possible approach is to regard the inference outcome as a random variable by introducing distributions for the parameters and evaluate the variance of the outcome. Unfortunately, the tractability of computing such a variance is hardly known. Motivated by this, we consider the problem of computing the variance of WMC and investigate this problem's tractability. First, we derive a polynomial time algorithm to evaluate the WMC variance when the input is given as a structured d-DNNF. Second, we prove the hardness of this problem for structured DNNFs, d-DNNFs, and FBDDs, which is intriguing because the latter two allow polynomial time WMC algorithms. Finally, we show an application that measures the uncertainty in the inference of Bayesian networks. We empirically show that our algorithm can evaluate the variance of the marginal probability on real-world Bayesian networks and analyze the impact of the variances of parameters on the variance of the marginal.

Related papers

• Contrastive Normalizing Flows for Uncertainty-Aware Parameter Estimation [0.0]
  Estimating physical parameters from data is a crucial application of machine learning (ML) in the physical sciences.<n>We introduce a novel approach based on Contrastive Normalizing Flows (CNFs), which achieves top performance on the HiggsML Uncertainty Challenge dataset.
  arXiv  Detail & Related papers  (2025-05-13T16:14:34Z)
• Deep Operator Networks for Bayesian Parameter Estimation in PDEs [0.0]
  We present a novel framework combining Deep Operator Networks (DeepONets) with Physics-Informed Neural Networks (PINNs) to solve partial differential equations (PDEs)<n>By integrating data-driven learning with physical constraints, our method achieves robust and accurate solutions across diverse scenarios.
  arXiv  Detail & Related papers  (2025-01-18T07:41:05Z)
• Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methods [59.779795063072655]
  Chain-of-Thought (CoT) prompting and its variants have gained popularity as effective methods for solving multi-step reasoning problems. We analyze CoT prompting from a statistical estimation perspective, providing a comprehensive characterization of its sample complexity.
  arXiv  Detail & Related papers  (2024-08-25T04:07:18Z)
• Proximal Interacting Particle Langevin Algorithms [0.0]
  PIPLA family can be the de facto choice for parameter estimation problems in non-differentiable latent variable models.<n>We show that PIPLA family can be the de facto choice for parameter estimation problems in non-differentiable latent variable models.
  arXiv  Detail & Related papers  (2024-06-20T13:16:41Z)
• Partially factorized variational inference for high-dimensional mixed models [0.0]
  Variational inference is a popular way to perform such computations, especially in the Bayesian context.<n>We show that standard mean-field variational inference dramatically underestimates posterior uncertainty in high-dimensions.<n>We then show how appropriately relaxing the mean-field assumption leads to methods whose uncertainty quantification does not deteriorate in high-dimensions.
  arXiv  Detail & Related papers  (2023-12-20T16:12:37Z)
• Towards stable real-world equation discovery with assessing differentiating quality influence [52.2980614912553]
  We propose alternatives to the commonly used finite differences-based method. We evaluate these methods in terms of applicability to problems, similar to the real ones, and their ability to ensure the convergence of equation discovery algorithms.
  arXiv  Detail & Related papers  (2023-11-09T23:32:06Z)
• Learning to Bound Counterfactual Inference in Structural Causal Models from Observational and Randomised Data [64.96984404868411]
  We derive a likelihood characterisation for the overall data that leads us to extend a previous EM-based algorithm. The new algorithm learns to approximate the (unidentifiability) region of model parameters from such mixed data sources. It delivers interval approximations to counterfactual results, which collapse to points in the identifiable case.
  arXiv  Detail & Related papers  (2022-12-06T12:42:11Z)
• Statistical and Computational Trade-offs in Variational Inference: A Case Study in Inferential Model Selection [27.817156428797567]
  Variational inference has emerged as a popular alternative to the classical Markov chain Monte Carlo. We study the statistical and computational trade-offs in variational inference via a case study in inferential model selection. We prove that, given a fixed computation budget, a lower-rank inferential model produces variational posteriors with a higher statistical approximation error.
  arXiv  Detail & Related papers  (2022-07-22T17:16:05Z)
• Marginal Inference queries in Hidden Markov Models under context-free grammar constraints [0.348097307252416]
  We address the question of computing the likelihood of context-free grammars (CFGs) in Hidden Models (HMMs) We show that the problem is NP-Hard, even with the promise that CFG has a degree of ambiguity less than or equal to 2. We then propose a fully randomized approximation scheme to approximate the likelihood for the case of ambiguous CFGs.
  arXiv  Detail & Related papers  (2022-06-26T12:44:18Z)
• BayesIMP: Uncertainty Quantification for Causal Data Fusion [52.184885680729224]
  We study the causal data fusion problem, where datasets pertaining to multiple causal graphs are combined to estimate the average treatment effect of a target variable. We introduce a framework which combines ideas from probabilistic integration and kernel mean embeddings to represent interventional distributions in the reproducing kernel Hilbert space.
  arXiv  Detail & Related papers  (2021-06-07T10:14:18Z)
• Accounting for Unobserved Confounding in Domain Generalization [107.0464488046289]
  This paper investigates the problem of learning robust, generalizable prediction models from a combination of datasets. Part of the challenge of learning robust models lies in the influence of unobserved confounders. We demonstrate the empirical performance of our approach on healthcare data from different modalities.
  arXiv  Detail & Related papers  (2020-07-21T08:18:06Z)
• Neural Methods for Point-wise Dependency Estimation [129.93860669802046]
  We focus on estimating point-wise dependency (PD), which quantitatively measures how likely two outcomes co-occur. We demonstrate the effectiveness of our approaches in 1) MI estimation, 2) self-supervised representation learning, and 3) cross-modal retrieval task.
  arXiv  Detail & Related papers  (2020-06-09T23:26:15Z)

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.