Incorporating Path Constraints into Bayesian network under the Sparse Parent Graph

When a Bayesian network (BN) is used to model a practical problem, sufficient prior knowledge is required, which is in the form of path constraints. Dynamic programming (DP) approach is one of the exact algorithms that is used for structure learning of BNs by optimizing a decomposable score function. In this study, we attempt to provide an efficient and compact method for incorporating the path constraints in DP with the guidance of sparse parent graph (SPG) and drive algorithms, which is used to obtain the optimal BN satisfying the given constraints. We use a rigorous deduction theory to provide useful insights on the implementation of path constraints in the DP algorithm. Our experiments demonstrate that the proposed approach reduces the time and space complexities significantly.