Anytime Learning of Sum-Product and Sum-Product-Max Networks

Prominent algorithms for learning sum-product networks (SPN) and sum-product-max networks (SPMN) focus on learning models from data that deliver good modeling performance without regard to the size of the learned network. Consequently, the learned networks can get very large, which negatively impacts inference time. In this paper, we introduce anytime algorithms for learning SPNs and SPMNs. These algorithms generate intermediate but provably valid models whose performance progressively improves as more time and computational resources are allocated to the learning. They flexibly trade off good model performance with reduced learning time, offering the benefit that SPNs and SPMNs of small sizes (but with reduced likelihoods) can be learned quickly. We comprehensively evaluate the anytime algorithms on two testbeds and demonstrate that the network performance improves with time and reflects the expected performance profile of an anytime algorithm. We expect these anytime algorithms to become the default learning techniques for SPNs and SPMNs given their clear benefit over classical batch learning techniques.