Optimization of Hierarchical Regression Model with Application to Optimizing Multi-Response Regression K-ary Trees

AAAI 2019 · DOI · DBLP

Note: This paper has been marked as RETRACTED. The following summary is provided for academic review of the technical methodologies and claims presented in the original document.

Introduction

Decision trees are foundational tools in machine learning, prized for their interpretability and exceptional inference speed. However, their performance is often hampered by the "greedy" nature of their construction. Standard algorithms like CART make locally optimal splits at each node without considering the global impact on the final tree structure. While ensemble methods such as Random Forests and Gradient Boosted Trees mitigate these issues and achieve higher accuracy, they do so at the expense of increased memory usage and significantly slower query times.

This paper introduces OHMR (Optimization of Hierarchical Model for Regression), a meta-algorithm designed to bridge the gap between the efficiency of a single decision tree and the predictive power of complex ensembles. By moving beyond greedy initialization, OHMR refines existing tree structures to achieve "forest-level" accuracy while maintaining the lightning-fast performance of a single hierarchical model.

The OHMR Meta-Algorithm

The core innovation of OHMR is its iterative approach to tree optimization. Rather than building a tree from scratch and accepting the greedy splits, OHMR takes a pre-trained tree and optimizes its parameters node-by-node.

Node-by-Node Optimization

The algorithm traverses the tree structure, focusing on one node at a time while keeping the parameters of all other nodes fixed. This localized optimization allows for a more granular refinement of the decision boundaries.

Splits as Cost-Sensitive Classification

A key insight of the OHMR framework is the redefinition of split node optimization. At any given split node, the task is treated as an instance-based cost-sensitive classification problem. For every data point reaching the node, the algorithm calculates the potential regression error (the "cost") of sending that point to each available child node. The split parameters—whether univariate or multivariate (oblique)—are then updated to minimize this total cost.

To handle the non-differentiable nature of 0-1 misclassification loss, the authors employ a modified logistic regression as a surrogate loss function. This allows for smooth, gradient-based updates to the split boundaries.

Leaf Node Refinement

At the leaf nodes, the optimization is straightforward: the optimal prediction is calculated as the mean of the target values for the samples that have reached that specific leaf.

Computational Efficiency

Despite the iterative nature of the refinement process, the authors demonstrate that OHMR maintains linear scalability ($O(N)$) relative to the number of samples. This makes the meta-algorithm viable for large-scale datasets where traditional global optimization techniques would be computationally prohibitive.

Experimental Evaluation

The authors tested OHMR across a wide variety of benchmarks, including standard regression tasks and classification problems treated as multi-response regression.

Datasets

The evaluation included:

  • Regression: Concrete Compressive Strength (CCS), Airfoil Self-Noise, CT Slice Localization, California Housing (CADATA), and Year Prediction MSD.
  • Classification: MNIST handwritten digits, Spambase, Breast Cancer, and Pendigits.

Key Results

  • Significant Error Reduction: OHMR consistently reduced both training and test errors by 25% to 50% compared to standard greedy algorithms like CART or Multivariate Regression Trees (MRT).
  • Matching Ensembles: In several benchmarks, a single oblique tree optimized with OHMR (OC1-OHMR) achieved accuracy comparable to or exceeding that of Random Forests consisting of over 100 trees.
  • Superior Query Speed: Because the final model remains a single tree, its query time is often orders of magnitude faster than ensemble models, which must traverse multiple trees for every prediction.
  • MNIST Performance: When applied to the MNIST dataset as a multi-response regression problem, the model achieved 90% accuracy at a depth of only 4 and reached 95.39% accuracy at depth 12, demonstrating high efficiency in complex feature spaces.

Discussion and Insights

The most significant contribution of OHMR is the elegant framing of tree optimization as a cost-sensitive classification task. This perspective allows researchers to leverage well-established classification solvers to improve regression models. Furthermore, OHMR is particularly efficient for multi-response problems; unlike standard methods that build separate trees for each output, OHMR optimizes a single tree to predict multiple variables simultaneously, drastically reducing the model's memory footprint.

The authors also provide a convergence guarantee, proving that the algorithm will reach a stable state in a finite number of iterations due to the bounded nature of the loss function and the finite permutations of sample assignments.

Limitations and Future Work

While OHMR significantly improves the parameters of a tree, it does so within a fixed topology. The algorithm optimizes weights and thresholds but does not dynamically "grow" or restructure the tree branches beyond what was provided during initialization (though pruning is possible). Future research might explore combining OHMR with non-greedy topology generation.

Additionally, as with any high-capacity model, deeper trees optimized with OHMR carry an increased risk of overfitting, necessitating robust cross-validation strategies. Finally, given the paper's retracted status, researchers are advised to exercise caution and verify the underlying data and methodology before implementing these specific findings in production environments.

Summary updated

BibTeX
@inproceedings{2019optimization,
  title = {{Optimization of Hierarchical Regression Model with Application to Optimizing Multi-Response Regression K-ary Trees}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33015133},
}

Loading related content...

Figure