Efficient Bayesian Network Structure Learning via Parameterized Local Search on Topological Orderings

In Bayesian Network Structure Learning (BNSL), one is given a variable set and parent scores for each variable and aims to compute a DAG, called Bayesian network, that maximizes the sum of parent scores, possibly under some structural constraints. Even very restricted special cases of BNSL are compu...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-04
Main Authors: Grüttemeier, Niels, Komusiewicz, Christian, Morawietz, Nils
Format: Article
Language:English
Subjects:
Bayesian analysis
Inversions
Machine learning
Parameter modification
Run time (computers)
Search algorithms
Topology
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In Bayesian Network Structure Learning (BNSL), one is given a variable set and parent scores for each variable and aims to compute a DAG, called Bayesian network, that maximizes the sum of parent scores, possibly under some structural constraints. Even very restricted special cases of BNSL are computationally hard, and, thus, in practice heuristics such as local search are used. A natural approach for a local search algorithm is a hill climbing strategy, where one replaces a given BNSL solution by a better solution within some pre-defined neighborhood as long as this is possible. We study ordering-based local search, where a solution is described via a topological ordering of the variables. We show that given such a topological ordering, one can compute an optimal DAG whose ordering is within inversion distance \(r\) in subexponential FPT time; the parameter \(r\) allows to balance between solution quality and running time of the local search algorithm. This running time bound can be achieved for BNSL without structural constraints and for all structural constraints that can be expressed via a sum of weights that are associated with each parent set. We also introduce a related distance called `window inversions distance' and show that the corresponding local search problem can also be solved in subexponential FPT time for the parameter \(r\). For two further natural modification operations on the variable orderings, we show that algorithms with an FPT time for \(r\) are unlikely. We also outline the limits of ordering-based local search by showing that it cannot be used for common structural constraints on the moralized graph of the network.
ISSN:2331-8422