Finding optimal Bayesian network given a super-structure.

*(English)*Zbl 1225.68206Summary: Classical approaches used to learn a Bayesian network structure from data have disadvantages in terms of complexity and lower accuracy of their results. However, a recent empirical study has shown that a hybrid algorithm improves sensitively accuracy and speed: it learns a skeleton with an independency test (IT) approach and constrains on the directed acyclic graphs (DAG) considered during the search-and-score phase. Subsequently, we theorize the structural constraint by introducing the concept of super-structure \(S\), which is an undirected graph that restricts the search to networks whose skeleton is a subgraph of \(S\). We develop a super-structure constrained optimal search (COS): its time complexity is upper bounded by \(O(\gamma _{m}^{n})\), where \(\gamma _{m}<2\) depends on the maximal degree \(m\) of \(S\). Empirically, complexity depends on the average degree \(\tilde{m}\) and sparse structures allow larger graphs to be calculated. Our algorithm is faster than an optimal search by several orders and even finds more accurate results when given a sound super-structure. Practically, \(S\) can be approximated by IT approaches; significance level of the tests controls its sparseness, enabling to control the trade-off between speed and accuracy. For incomplete super-structures, a greedily post-processed version (COS+) still enables to significantly outperform other heuristic searches.

##### MSC:

68T05 | Learning and adaptive systems in artificial intelligence |

62M45 | Neural nets and related approaches to inference from stochastic processes |