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.
翻译:学习 Bayesian 网络结构的计分算法可以用于精确的和近似的解决办法。 虽然与变量数相比,学习规模比变量数要接近,但是在高维数据存在的情况下,这种算法可以计算得比较昂贵。 本文描述了对候选父母配方(CPS)进行平行抽样的大致算法,可以被视为MINOBS的延伸,这是从高维数据中学习结构的最先进的算法。 我们称之为平行抽样MINOBS(PS-MINOBS)的修改算法,通过对每种变量的CPS取样来构建图表。 在假设Bayesian 评分为每个变量标定时, CPS的分布是半正常的同时进行。 从半正常分布中取样可以确保抽样的CPS有可能是产生较高分数的。 Empical结果显示,在大多数情况下,在两种算法都限于同一运行时,拟议的算法发现比MINOBS 更高的评分结构。