Learning Bayesian Network Structure from Correlation-Immune Data
This addresses a limitation in Bayesian network learning for data with specific statistical properties, but it is incremental as it builds on an existing algorithm.
The paper tackles the problem of learning Bayesian network structures from data with correlation-immune relationships, such as parity, which existing heuristics like the Sparse Candidate algorithm cannot handle. By extending Sparse Candidate with a 'skewing' technique that changes input distributions, the method discovers approximately correlation-immune relationships with significantly lower computational cost than alternatives.
Searching the complete space of possible Bayesian networks is intractable for problems of interesting size, so Bayesian network structure learning algorithms, such as the commonly used Sparse Candidate algorithm, employ heuristics. However, these heuristics also restrict the types of relationships that can be learned exclusively from data. They are unable to learn relationships that exhibit "correlation-immunity", such as parity. To learn Bayesian networks in the presence of correlation-immune relationships, we extend the Sparse Candidate algorithm with a technique called "skewing". This technique uses the observation that relationships that are correlation-immune under a specific input distribution may not be correlation-immune under another, sufficiently different distribution. We show that by extending Sparse Candidate with this technique we are able to discover relationships between random variables that are approximately correlation-immune, with a significantly lower computational cost than the alternative of considering multiple parents of a node at a time.