Learning Bayesian Network Structure from Correlation-Immune Data
  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.
