提出高效计算加权模型计数方差的方法，解决概率推理中的不确定性量化问题。
Variance Computation for Weighted Model Counting with Knowledge Compilation Approach
- 基于结构化d-DNNF构造多项式时间方差计算算法
- 证明d-DNNF、FBDD等结构下方差计算为困难问题
- 可应用于真实贝叶斯网络的边际概率不确定性分析
加权模型计数（WMC）是知识编译中最重要的查询之一，已广泛应用于贝叶斯网络等模型的概率推理。实际推理任务中，模型参数因从数据学习而存在不确定性，因此需要量化推理结果的不确定性。一种方法是将推理结果视为随机变量，通过引入参数分布来评估其方差。然而，该方差的可计算性尚不明确。本文研究了WMC方差的可计算性：首先，针对输入为结构化d-DNNF的情况，提出多项式时间算法；其次，证明在结构化DNNF、d-DNNF和FBDD下该问题为困难问题，这一结果令人意外，因为后两者支持多项式时间的WMC；最后，展示了在贝叶斯网络推理中测量不确定性的真实应用。实验表明，该算法能有效评估真实世界贝叶斯网络中边际概率的方差，并分析参数方差对边际方差的影响。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。