Bounding the complexity of structural expectation-maximization

Structural expectation-maximization is the most common approach to address the problem of learning Bayesian networks from incomplete datasets. Its main limitation is that its computational cost is usually extremely demanding when the number of variables or the number of instances is not small. The bottleneck of this algorithm is the inference complexity of the model candidates. Thus, bounding the inference complexity of each Bayesian network during the learning process is key to make structural expectation-maximization efficient. In this paper, we propose a tractable adaptation of structural expectation-maximization and perform experiments to analyze its performance