×

zbMATH — the first resource for mathematics

Finding optimal Bayesian network given a super-structure. (English) Zbl 1225.68206
Summary: 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
Software:
pcalg
PDF BibTeX XML Cite
Full Text: Link