Smoothness and Structure Learning by Proxy
This addresses the computational bottleneck in structure learning for data scientists, though it is incremental as it builds on existing proxy methods.
The paper tackles the problem of slow structure learning in large datasets by using a Gaussian Process regressor as a proxy for the true scoring function in Bayesian network learning, proving smoothness bounds and achieving equivalent or better scores in a fraction of the time.
As data sets grow in size, the ability of learning methods to find structure in them is increasingly hampered by the time needed to search the large spaces of possibilities and generate a score for each that takes all of the observed data into account. For instance, Bayesian networks, the model chosen in this paper, have a super-exponentially large search space for a fixed number of variables. One possible method to alleviate this problem is to use a proxy, such as a Gaussian Process regressor, in place of the true scoring function, training it on a selection of sampled networks. We prove here that the use of such a proxy is well-founded, as we can bound the smoothness of a commonly-used scoring function for Bayesian network structure learning. We show here that, compared to an identical search strategy using the network?s exact scores, our proxy-based search is able to get equivalent or better scores on a number of data sets in a fraction of the time.