  Score-based algorithms that learn the structure of Bayesian networks can be
used for both exact and approximate solutions. While approximate learning
scales better with the number of variables, it can be computationally expensive
in the presence of high dimensional data. This paper describes an approximate
algorithm that performs parallel sampling on Candidate Parent Sets (CPSs), and
can be viewed as an extension of MINOBS which is a state-of-the-art algorithm
for structure learning from high dimensional data. The modified algorithm,
which we call Parallel Sampling MINOBS (PS-MINOBS), constructs the graph by
sampling CPSs for each variable. Sampling is performed in parallel under the
assumption the distribution of CPSs is half-normal when ordered by Bayesian
score for each variable. Sampling from a half-normal distribution ensures that
the CPSs sampled are likely to be those which produce the higher scores.
Empirical results show that, in most cases, the proposed algorithm discovers
higher score structures than MINOBS when both algorithms are restricted to the
same runtime limit.
