Fast Non-Parametric Conditional Density Estimation using Moment Trees

In many machine learning tasks, one tries to infer unknown quantities such as the conditional density p(Y |X) from observed ones X. Conditional density estimation (CDE) constitutes a challenging problem due to the trade-off between model complexity, distribution complexity, and overfitting. In case of online learning, where the distribution may change over time (concept drift) or only few data points are available at once, robust, non-parametric approaches are of particular interest. In this paper we present a new, non-parametric tree-ensemble-based method for CDE that reduces the problem to a simple regression task on the transformed input data and a (unconditional) density estimation. We prove the correctness of our approach and show its usefulness in empirical evaluation on standard benchmarks. We show that our method is comparable to other state-of-the-art methods, but is much faster and more robust.