Tree-Width and the Computational Complexity of MAP Approximations in Bayesian Networks
Authors: Johan Kwisthout
JAIR 2015 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We prove that efficient value-approximations, structure-approximations, and rank-approximations of MAP instances with high tree-width will violate the Exponential Time Hypothesis. In contrast, we show that MAP can sometimes be efficiently expectation-approximated, even in instances with high tree-width, if the most probable explanation has a high probability. We introduce the complexity class FERT, analogous to the class FPT, to capture this notion of fixed-parameter expectation-approximability. |
| Researcher Affiliation | Academia | Johan Kwisthout EMAIL Radboud University Nijmegen Donders Institute for Brain, Cognition and Behaviour Montessorilaan 3, 6525 HR Nijmegen, The Netherlands |
| Pseudocode | No | The paper describes algorithms conceptually, for instance, discussing a 'simple forward sampling strategy' in Section 5.2, but does not present any structured pseudocode or algorithm blocks. For example: 'To show that {q} Constrained-MAP is in FERT, for the parameter q = Pr(H = true), we give the following approximation algorithm. Observe that H is a binary sink node (i.e., has no outgoing edges) and that B has no evidence. A simple forward sampling strategy (Henrion, 1986) can approximate the distribution of H by sampling values for the variables in the network according to the probability distribution in the CPTs.' |
| Open Source Code | No | The paper does not contain any explicit statements about code availability, links to source code repositories, or mentions of code being provided in supplementary materials for the methodology described. |
| Open Datasets | No | The paper focuses on theoretical computational complexity, defining problems like 'Lex Sat' and 'Constraint Satisfaction instance' for proofs and reductions, rather than using specific datasets for experimental evaluation. There is no mention of any publicly available or open datasets with concrete access information. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets; therefore, there is no mention of training/test/validation dataset splits. |
| Hardware Specification | No | The paper is a theoretical work on computational complexity and does not describe any experimental setup or specific hardware used for running experiments. |
| Software Dependencies | No | The paper is a theoretical work on computational complexity and does not describe any experimental setup or specific software dependencies with version numbers. |
| Experiment Setup | No | The paper focuses on theoretical proofs and complexity analysis, not on empirical experiments. Therefore, there are no specific experimental setup details, hyperparameters, or training configurations provided in the main text. |