EUVIMEDEUVIMED entdecken
Crossref

Variance Computation for Weighted Model Counting with Knowledge Compilation Approach

Kengo Nakamura, Masaaki Nishino, Norihito Yasuda

Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (23) · 19312-19320

DOI: 10.1609/aaai.v40i23.39007 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Kengo Nakamura und 2 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Nakamura, K., Nishino, M., & Yasuda, N. (2026). Variance Computation for Weighted Model Counting with Knowledge Compilation Approach. Proceedings of the AAAI Conference on Artificial Intelligence, 40(23), 19312-19320. https://doi.org/10.1609/aaai.v40i23.39007

Vancouver

Nakamura K, Nishino M, Yasuda N. Variance Computation for Weighted Model Counting with Knowledge Compilation Approach. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(23):19312-19320. doi:10.1609/aaai.v40i23.39007

BibTeX
@article{Nakamura2026,
  author = {Nakamura, Kengo and Nishino, Masaaki and Yasuda, Norihito},
  title = {Variance Computation for Weighted Model Counting with Knowledge Compilation Approach},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2026},
  volume = {40},
  number = {23},
  pages = {19312--19320},
  doi = {10.1609/aaai.v40i23.39007}
}
Kostenlos starten →