Extraction of NAT Causal Structures Based on Bipartition

Non-impeding noisy-And Trees (NATs) provide a general, expressive, and efficient causal model for conditional probability tables (CPTs) in discrete Bayesian networks (BNs). A BN CPT may either be directly expressed as a NAT model or be compressed into one. Once CPTs in BNs are so expressed or compressed, complexity of inference (both space and time) can be significantly reduced. The most important operation in encoding or compressing CPTs into NAT models is extracting the NAT structure from interaction patterns between causes. The existing method does so by referencing a NAT database and an associated search tree. Although both are constructed offline, their complexity is exponential on the number of causes. In this work, we propose a novel method for NAT extraction from causal interaction patterns based on bipartition of causes. The method does not require the support of a NAT database and the related search tree, making NAT extraction more efficient and flexible.