Trans-Causalizing NAT-Modeled Bayesian Networks

IEEE Trans Cybern. 2022 May;52(5):3553-3566. doi: 10.1109/TCYB.2020.3009929. Epub 2022 May 19.

Abstract

Conditional independence encoded in Bayesian networks (BNs) avoids combinatorial explosion on the number of variables. However, BNs are still subject to exponential growth of space and inference time on the number of causes per effect variable in conditional probability tables. A number of space-efficient local models exist that allow efficient encoding of dependency between an effect and its causes, and can also be exploited for improved inference efficiency. We focus on the Nonimpeding Noisy-AND Tree (NIN-AND Tree or NAT) models because of multiple merits. We present a novel framework, trans-causalization of NAT-modeled BNs, by which causal independence embedded in NAT models is exploited for more efficient inference. We show that trans-causalization is exact and yields polynomial space complexity. We demonstrate significant efficiency gain on inference based on lazy propagation and sum-product networks.

MeSH terms

  • Algorithms*
  • Bayes Theorem