Riemann-Lebesgue Forest for Regression

Authors: Tian Qin, Wei-Min Huang
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords: RandomForest; Lebesgue Partition; asymptotic normality;

Abstract:
We propose a novel ensemble method called Riemann-Lebesgue Forest (RLF) for regression. The core idea in RLF is to mimic the way how a measurable function can be approximated by partitioning its range into a few intervals. With this idea in mind, we develop a new tree learner named Riemann-Lebesgue Tree (RLT) which has a chance to perform Lebesgue type cutting,i.e splitting the node from response Y
 at certain non-terminal nodes. In other words, we introduce the "splitting type randomness" in our ensemble method. We show that the optimal Lebesgue type cutting results in larger variance reduction in response Y than ordinary CART  cutting (an analogue of Riemann partition). Such property is beneficial to the ensemble part of RLF. We also generalize the asymptotic normality of RLF under different parameter settings. Two one-dimensional examples are provided to illustrate the flexibility of RLF. The competitive performance of RLF against original random forest  is demonstrated by experiments in simulation data and real world datasets.

Decision: reject
Reviewer scores: 5, 3, 8, 5

Reviews and discussion:
<thread>
creation date:
1730197682693

thread_type:
official_review

<thread_object>
creator: reviewer_fs4m

<content>
summary:
The author(s) present a new ensemble learning method named Riemann-Lebesgue Forest (RLF) for regression tasks. Traditional random forest methods use "Riemann" sense partitioning to approximate a function that best fits the observed data. The proposed method applies a "Lebesgue" sense partitioning based on the range of the response variable Y, aiming to achieve a more accurate model with reduced error. Additionally, the paper addresses the proposed method from a theoretical points, including proofs of asymptotic normality and a complexity analysis.

strengths:
- RLF introduces a new way of dividing data in regression trees, called "Lebesgue" cutting, which enhances accuracy in situations where traditional random forests (RF) struggle, especially in high-noise or low-data scenarios.
- The paper explains the main theories behind RLF, giving a solid mathematical base.

weaknesses:
- The paper lacks a publicly accessible GitHub repository or similar platform for the proposed methods.
- RLF generally requires more wall-clock time than RF, especially for large datasets, and does not show significant performance improvements in terms of time complexity.

questions:
RLF is more accurate but takes more time to run. Is this extra accuracy worth it for real-life use, especially when time is important? It would help to explain and show the level of contribution the approach makes to accuracy.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730638079548

thread_type:
official_review

<thread_object>
creator: reviewer_78ay

<content>
summary:
The authors introduce Reimann-Lebesgue Forest (RLF), a new ensemble method for regression that mimics Lebesgue integration by occasionally splitting nodes based on the response variable Y. They also establish the asymptotic normality of RLF and demonstrate its competitive performance against Random Forests on both simulated and real-world datasets.

strengths:
1. The authors propose an interesting “Riemann-Lebesgue” splitting criterion for CART that directly incorporates the response variable splitting, making it a novel approach worth exploring.
2. The authors provide a solid theoretical justification for their approach.
3. The approach demonstrates effectiveness compared to traditional Random Forests across various synthetic and real datasets.

weaknesses:
1. The notation in Section 2.1 could be clarified. In lines 112 and 133, the dimension is denoted as d, whereas in lines 127 and 136, it appears to be represented by p. For better readability, it would be preferable to use consistent notation for dimension throughout. Additionally, since  m_{try}  is an integer, the set  C_R  in line 135 is not well defined.
2. I don’t believe it’s impractical to keep partitioning in practice, as suggested in line 53. For example, the default min_samples_leaf parameter in Scikit-Learn’s Random Forest Regressor is set to 1 (M_node = 1), which allows the trees to grow very deep. A follow-up concern is whether the difference between RLF and RF would diminish if RF trees were allowed to go deeper, while it runs faster than RLF. Specifically, the paper used a minimum node size of M_node = 5 for real datasets, as shown in Appendix A.10. What would happen if M_node were reduced to 1?
3. While Section 3.3 addresses the training complexity, I believe the contrast in prediction complexity is even more significant. Has any analysis been conducted on the prediction time complexity?
4. The introduction of ‘Lebesgue’ partitioning could complicate interpretation, particularly for calculating values like TreeSHAP [1], although the paper’s primary focus is on predictive performance.

Some typos: 

1. In algorithm 1, “repeat steps 1 - 15” in line 8 and line 12. The final line also has an alignment issue.
2. Line 658 “glocal” trees
3. Table S4 shows the SE of running time for RF on dataset FF as 5432.01 which is quite high, I guess the author used the MSE in Table 1.

questions:
When noise levels are high, splitting on signal features tends to be less effective, and intuitively, ‘Riemann’ type splitting might also be expected to underperform. Could the authors provide intuition for why ‘Riemann’ type cuttings achieve better performance at higher noise levels, as suggested in lines 434-435?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730680224192

thread_type:
official_review

<thread_object>
creator: reviewer_aezj

<content>
summary:
The paper considers learning a variation of Random Forests, where each decision tree is learned using CART-type tree induction, but instead of considering only input features to split, it considers the target output also as a splitting criteria. But during the test time, we need the value of the target during inference (at decision nodes that splits on the target), and those are computed (predicted) using Random Forest (which will also be trained locally at decision nodes that splits on target). The paper has some theoretical analysis, and experimental comparison with Random Forests.

strengths:
Using target values as one of the splitting criteria in tree learning is an interesting idea.

weaknesses:
1. The novelty of the paper is not on learning a forest in a novel way but rather learning a single decision tree using splits on the target. As such, the new tree learning method should be compared on its own with other tree learning methods such as CART, C5.0, GUIDE, TAO and PyDL8.5. According to theorem 3.1, shouldn't it be better than CART?
2. Using local Random Forest to predict the output that is used at a decision node splitting on the target is quite a heuristic approach. Is there any theory or intuitive motivation behind it?
3. No comparison with gradient boosting. XGBoost and LightGBM are the widely established methods in tree ensembles. Given the fact that tree ensembles are mostly evaluated empirically, having a comparison with gradient boosting is important.
4. Theoretical analysis of section 3 looks very complicated, especially the bounds of theorem 3.2. They do not seem to add any practical value.

questions:
No questions.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730724024072

thread_type:
official_review

<thread_object>
creator: reviewer_gnln

<content>
summary:
The paper introduces a new ensemble regression method called the Riemann-Lebesgue Forest (RLF), which leverages a novel tree structure, the Riemann-Lebesgue Tree (RLT). RLF improves traditional Random Forests by utilizing "Lebesgue-type" partitioning, which splits based on response values rather than predictor values alone. This approach, combining both Riemann and Lebesgue partitioning, is shown to reduce variance in predictions and improve mean squared error, particularly in sparse or noisy data scenarios. The authors provide theoretical analyses, demonstrating the asymptotic normality of RLF and evaluating its performance on both simulated and real-world data, highlighting RLF's competitive edge in regression tasks over conventional method.

strengths:
- **Originality**: The paper introduces a novel ensemble method, the Riemann-Lebesgue Forest (RLF), which creatively combines Riemann and Lebesgue partitioning within decision trees. This innovative approach, applying response-based splits (Lebesgue-type) rather than traditional feature-based splits, offers a fresh perspective on ensemble methods, especially in handling regression tasks in sparse models.

- **Quality**: The research is thorough, with extensive theoretical analysis and rigorous experimentation. The authors carefully examine the variance reduction and asymptotic normality properties of the RLF, providing proofs that establish the foundation of the method's performance. 

- **Significance**: The introduction of the Lebesgue-type partitioning extends the applicability of ensemble methods to settings where traditional Random Forests might underperform, particularly in high-dimensional or noisy environments.

weaknesses:
- **Clarity in the Splitting Criteria**: The connection between Eq. (2) (simple function approximations) and Eq. (5) (the splitting criterion) is unclear, which weakens the reader's understanding of the novel splitting mechanism. It is really needed to expand the explanation on this connection.

- **Overly Strong Claims**: The claim that "a RLT will have smaller \(L_2\) training error than an ordinary CART tree" is not straightforward and needs more explanation. Furthermore, the expected reduction in mean squared error due to bias-variance decomposition analysis does not explain the fact that the new proposed method overfits. This overfitting is usually the result of a method having high variance. This needs to be much better explained.

- **Limited Experimental Improvements**: The empirical results, while promising, show only modest improvements over traditional Random Forests. 

- **Dependency on a Local Model**: The requirement of a secondary random forest model within each Riemann-Lebesgue Tree as a local model presents computational and interpretative limitations. This reliance could be explored in greater depth, addressing alternative local models or the impact of this dependency on scalability and performance. This limitation should, at least, much better discussed.

questions:
Please try to answer each of the weaknesses discussed above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731472888439

thread_type:
official_comment

<thread_object>
creator: area_chair_yc8x

<content>
title:
authors - reviewers discussion open until November 26 at 11:59pm AoE

comment:
Dear authors & reviewers,

The reviews for the paper should be now visible to both authors and reviewers. The discussion is open until November 26 at 11:59pm AoE.

Your AC
</content>
</thread_object>

</thread>
<thread>
creation date:
1731494259331

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
First of all, we'd like to appreciate the reviewers' interest in our work and we are grateful for their valuable suggestions and feedback. We address each reviewer's specific questions in separate response to their reviews. We hope our additional explanations help to clarify the issues or concerns and hope you find it satisfactory and we are happy to have any further discussions.

In summary, we want to highlight few distinctive characteristics of our RLF.
1.  The introduction of the probability $\tilde{p}$, which controls the type of splitting (Riemann or Lebesgue) at each non-terminal node, makes the RLF more flexible in detecting complex patterns in response Y. Recall that the traditional random forests introduce an extra randomness called "feature bagging", which makes RF different from ordinary bagging ensemble methods. Essentially, the control probability $\tilde{p}$ in RLF provides another randomness in forest methods, which can be interpreted as "splitting type randomness".

2.  In section 4.3, we provided two one-dimensional exmaples illustrating the flexibility of RLF with tuned $\tilde{p}$. More specifically, in datasets with small signal-to-noise ratio (example1), RLF favors more Riemann type splitting. This is intuitive as we typically don't want to split from Y if it's too noisy. On the other hand, when the response Y has mixture distribution (example 2), experiments show that tuned RLF favors more Lebesgue type splitting. This also makes sense as when the response has complicated pattern, the Riemann type cutting might be too simple to capture the pattern of response Y. What's more, when the feature space X has redundant features, i.e sparse model, RLF also prefers more Lebesgue type splitting to avoid learning noise from X space. (See section 4.1)

3.  The performance of RLF in real-world datasets indeed demonstrates the significant superiority over traditional RF. For example, Table 1  shows that RLF with data-driven $\tilde{p}$ outperforms RF in **20** datasets where **eight** of them are significant.  Table 2 shows that RLF with tuned $\tilde{p}$ outperform RF in **23** datasets where **twelve** of them are statistically significant. However, RF only significantly outperforms RLF in two datasets. Table 1 also shows that RLF reduces testing MSE by **15%** on average, which is a decent improvement. Similar improvement can be observed in Table 2. Note that in Table 1 we have **30** datasets in total and Table 2 involves **26** datasets(due to the time efficiency of parameter tuning).  

4.  Time complexity of RLF is mainly due to the local random forests and the nature of tree ensemble method. To reduce the time complexity of RLF, we can construct single RLT in parallel and employ a more efficient local model for nodes with Lebesgue splitting, which will be our future work.

We also corrected some typos  in original manuscript where the modified texts are highlighed in blue.  See updated pdf file.
</content>
</thread_object>

</thread>


Metareview: