Active Learning for Non-Parametric Regression Using Purely Random Trees
Active learning is the task of using labelled data to select additional points to label, with the goal of fitting the most accurate model with a fixed budget of labelled points. In binary classification active learning is known to produce faster rates than passive learning for a broad range of settings. However in regression restrictive structure and tailored methods were previously needed to obtain theoretically superior performance. In this paper we propose an intuitive tree based active learning algorithm for non-parametric regression with provable improvement over random sampling. When implemented with Mondrian Trees our algorithm is tuning parameter free, consistent and minimax optimal for Lipschitz functions.
•Post review comments: Assuming the authors will indeed address the unclear parts that I indicated, and in particular the proof of cor. 4.6 I am updating my score. Yet, I still think that their results (including those appearing in their response) are not showing significant gains as seen in other Active Learning settings.   The paper addresses the problem of active learning for regression with random trees. The authors introduce a simple ‘oracle’ algorithm and a risk variance is provided for this criterion. Authors provide a risk minimizing query criteria and claim it is better than the random selection criterion An estimation algorithm is presented that provides the necessary statistics at its first stage to allow an approximation to the ‘oracle’ algorithm. Numerical results are presented in which improved performance over random and uncertainty sample is provided for simulated data, and no improvement for real UCI data.  Strengths:  • The paper provides both an algorithm and theoretical analysis with empirical results. Theoretical analysis for active learning algorithms is a challenging task, lacking in many of the state-of-the-art heuristic algorithms for active learning • The organization of the paper’s sections is good Weaknesses: 1. There are many unclear parts in the paper, lacking formalism in some places which leaves the reader confused. I will give some examples for that in the order in which they appear a. Introduction, 2nd paragraph – the example requires the authors to make some analogy between the chemical quantities of the systems and concepts in active learning. It is completely unclear to me how this example makes a case for active learning. b. The authors make first reference to a leaf in the setting and background in page 2 line 54. However, no definition of a tree has been made yet, or even a simple reference to such.  c. Authors refer to n and d in line 93 and in algorithm 1 however it was never made clear what they are.  ‘n’, for example: Is ‘n’ the total size of data? Is it the test set size? Pool set size? d. Preposition 4.1 is not clear are we looking at the post selected leaf-set X after q_k proportion was selected? e. Most important: Key Corollary 4.6 proof is unclear, short, informal and confusing: what minimum and average are your referring to? This is a key result of the paper and it should be very clearly explained and proved! 2. Author should explain and motivate their decision to let $a_k=\frac{p_k}{\sgima^2_{Y,k}} in line 156. Why should the multiplicative factor have such a form? 3. Experimental results: Results are not convincing in demonstrating that the method is advantageous for real data. Authors should provide such examples or improve their algorithm. 4. In addition: a. Authors should provide basic data sizes for the datasets they experiment with in order for the reader to evaluate the efficiency of their method by, for example, comparing the size of the training set with the size of the full data set. b. Please provide reference for Breiman trees 5. Minor: many typos exist, authors should proof read their paper.