Bayesian Decision Trees Inspired from Evolutionary Algorithms
This incremental improvement addresses efficiency issues for users of Bayesian Decision Trees in handling uncertain data.
The paper tackles the slow burn-in time in Bayesian Decision Trees by replacing MCMC with Sequential Monte Carlo and an Evolutionary Algorithm-inspired sampling strategy, achieving more accurate results in 100 times fewer iterations.
Bayesian Decision Trees (DTs) are generally considered a more advanced and accurate model than a regular Decision Tree (DT) because they can handle complex and uncertain data. Existing work on Bayesian DTs uses Markov Chain Monte Carlo (MCMC) with an accept-reject mechanism and sample using naive proposals to proceed to the next iteration, which can be slow because of the burn-in time needed. We can reduce the burn-in period by proposing a more sophisticated way of sampling or by designing a different numerical Bayesian approach. In this paper, we propose a replacement of the MCMC with an inherently parallel algorithm, the Sequential Monte Carlo (SMC), and a more effective sampling strategy inspired by the Evolutionary Algorithms (EA). Experiments show that SMC combined with the EA can produce more accurate results compared to MCMC in 100 times fewer iterations.