Learning Bayesian networks with ancestral constraints
We consider the problem of learning Bayesian networks optimally, when subject to background knowledge in the form of ancestral constraints. Our approach is based on a recently proposed framework for optimal structure learning based on non-decomposable scores, which is general enough to accommodate ancestral constraints. The proposed framework exploits oracles for learning structures using decomposable scores, which cannot accommodate ancestral constraints since they are non-decomposable. We show how to empower these oracles by passing them decomposable constraints that they can handle, which are inferred from ancestral constraints that they cannot handle. Empirically, we demonstrate that our approach can be orders-of-magnitude more efficient than alternative frameworks, such as those based on integer linear programming.
This paper concerns the constrained optimisation problem of learning Bayesian networks from local scores with ancestral constraints. The search is branch-and-bound where the nodes in the search tree are CPDAGs and we 'move down' from CPDAG1 to CPDAG2 by (roughly) choosing a parent set for a BN variable which is not a node in CPDAG1. Sensible symmetry breaking is effected. The search is A* where the URLearning system is used to provide a heuristic. (Details of how this happens are not given here but are available in an earlier paper).
Given ancestral constraints, some pruning of the search tree is possible. Lemma 3 (supplementary material) is the key result here. I believe it to be true, but I don't understand the proof. The phrase "By the EC tree edge generation rules, G_k also contains edge Z - > W" needs more explanation.   In addition there are implied constraints ( "implied constraints" is the standard terminology, here they are called "projected constraints"). A bunch of ancestral constraints will imply constraints on edges which can be used for pruning.  Constraints on permissible topological orderings are also inferred ("ordering constraints"). The approach to doing this is not properly explained. We have the statement that we "can infer Y < Z from Z not an ancestor of Y". The issue is the word "can". Clearly there are DAGs with Z is not an ancestor of Y but Y < Z is a consistent order: the graph with vertices Z and Y and no edges, for example. The authors, of course, know this! What they mean to say is that if "Z not an ancestor of Y" then we can *choose* to add the constraint Y < Z. So the idea is to 'infer' as many consistent ordering constraints as possible (not just those which are entailed). The authors are careful not to 'infer' too many and use a MAXSAT approach to do the inference.  Experiments are conducted where the number of variables, datapoints and ancestral constraints are varied. There is a comparison with the GOBNILP system where the current system is shown to be far faster than GOBNILP. As the authors note, without ancestral constraints, GOBNILP performs worse than A* approaches when there is no limit on parent set cardinality. In the current experiments there is no such limit, so it is difficult to tell whether GOBNILP's poor performance here is due to its 'normal' failure to deal with many parent sets or is more specifically down to dealing with ancestral constraints poorly.  Also the encoding of ancestral constraints ( given in the supplementary material) is based on a MAXSAT encoding from [Cussens, 2008] rather than, say, the ILP encoding found in Section 3.1.1 of [Cussens, 2010]. And this MAXSAT encoding is a poor formulation for an ILP system. Why not just have the A(X,Y) binary variables in addition to the I(Z,U) variables and omit the (cubic number of!) E(X,Y,Z) variables? I think all that is then needed is the transitivity constraints on the A(X,Y) variables and the following constraints linking A and I variables:  A(X,Y) \geq \sum_{U:X \in U} I(Y,U)  In other words if X is a parent of Y then X is an ancestor of Y. This formulation provides a far tighter linear relaxation and should provide much better performance. This is the approach of Section 3.1.1 of [Cussens, 2010] for a total ordering on variables but with a constraint dropped since ancestor is a partial, not total oder.  I am confident that even with a sensible ILP formulation of ancestral constraints the current system will outperform GOBNILP, but the paper is weakened by comparing to a poor formulation rather than a sensible one.   It would be interesting to compare the current method to that of van Beek and Hoffmann, particularly since it often outperforms GOBNILP. I don't think it would be too hard to adapt that method to allow ancestral constraints to be posted. The paper by van Beek and Hoffmann is not mentioned by the current authors.   [Cussens, 2010] James Cussens. Maximum likelihood pedigree reconstruction using integer programming". WCB'10.  Peter van Beek and Hella-Franziska Hoffmann. Machine learning of Bayesian networks using constraint programming. Proceedings of CP 2015, Cork, Ireland, August, 2015.