On Testing Whether an Embedded Bayesian Network Represents a Probability Model
This addresses a fundamental challenge in Bayesian network validation for researchers and practitioners dealing with hidden variables, though it is incremental in focusing on tree structures.
The paper tackles the problem of testing whether probabilistic models with hidden variables are compatible with observed data, showing that this task generally requires an exponential number of independence evaluations, but reduces to a polynomial number for tree-structured networks. It also provides an efficient algorithm to construct or recognize such tree-structured networks.
Testing the validity of probabilistic models containing unmeasured (hidden) variables is shown to be a hard task. We show that the task of testing whether models are structurally incompatible with the data at hand, requires an exponential number of independence evaluations, each of the form: "X is conditionally independent of Y, given Z." In contrast, a linear number of such evaluations is required to test a standard Bayesian network (one per vertex). On the positive side, we show that if a network with hidden variables G has a tree skeleton, checking whether G represents a given probability model P requires the polynomial number of such independence evaluations. Moreover, we provide an algorithm that efficiently constructs a tree-structured Bayesian network (with hidden variables) that represents P if such a network exists, and further recognizes when such a network does not exist.