Interpretable Quantile Regression by Optimal Decision Trees

1. Problem Statement

Machine learning models are increasingly required to be not only accurate but also interpretable and robust, particularly in high-stakes domains like healthcare and business strategy. While standard decision trees are interpretable, they traditionally predict the mean of the target variable using a Mean Squared Error (MSE) heuristic. This approach has two main limitations:

1. Lack of Distributional Insight: Predicting only the mean provides limited insight into the complete conditional distribution of the target variable.
2. Quantile Regression Challenges: While quantile regression (predicting specific percentiles, e.g., 10th or 90th) offers robustness to outliers and allows for motivated over/under-estimation (e.g., inventory management), existing methods face trade-offs:
   • Heuristic-based trees (e.g., Random Forests): Efficient but do not guarantee optimality and often require complex ensembles to approximate distributions.
   • Optimal Decision Trees (e.g., DL8.5): Guarantee the best tree for a specific loss function but traditionally require a separate, exhaustive search for each quantile parameter ($q$), leading to high computational costs if multiple quantiles are needed.
   • Post-hoc explanations: Often fail to explain the full decision process or remain complex.

The core problem addressed is how to learn multiple optimal decision trees (one for each quantile) simultaneously to model the full target distribution without incurring the massive computational overhead of running independent searches for each tree.

2. Methodology: Quantile DL8.5 (QDL8.5)

The authors propose Quantile DL8.5 (QDL8.5), an extension of the DL8.5 algorithm (an optimal decision tree learner using dynamic programming and branch-and-bound).

Core Algorithmic Innovations

1. Simultaneous Tree Learning:

   • Instead of running the DL8.5 search independently for each quantile $q$, QDL8.5 explores the tree search space only once.
   • The algorithm maintains a cache of "itemsets" (collections of feature constraints). When a node (itemset) is visited, the algorithm computes the optimal split and error metrics for all requested quantiles simultaneously.
   • Pruning Logic: A branch is pruned only if all quantile-specific searches fail to find a solution or exceed their respective upper bounds. This ensures that common structural parts of the trees (which are likely similar for adjacent quantiles) are computed once and reused.

2. Efficient Quantile Loss Computation:

   • The naive computation of quantile loss (Equation 1) for $N$ samples and $|q|$ quantiles takes $O(|q|N)$ time.
   • Optimization: The authors pre-sort the target values ($y$) for each itemset.
     • Quantile values are retrieved in $O(1)$ or $O(|q|)$ time using the sorted array.
     • The quantile loss is reformulated to rely on the sum of values above and below the predicted quantile. By traversing the sorted data once, the algorithm computes the necessary sums for all quantiles in $O(N + |q|)$ time.
   • This reduces the overall complexity to effectively $O(N)$ per node, making the cost of learning 100 trees comparable to learning one.

3. Output and Interpretation:

   • Prediction: For a given sample, the model outputs an array of quantile values.
   • Distribution Estimation: These quantiles can be combined using Kernel Density Estimators (KDE) (specifically Gaussian kernels with Scott's rule) to reconstruct the full conditional probability density function (PDF) of the target variable.

3. Key Contributions

1. Algorithmic Extension: The first method to extend optimal decision tree learning (DL8.5) to perform simultaneous quantile regression. It learns an optimal tree for every quantile while exploring the search space only once.
2. Computational Efficiency: Demonstrates that learning a set of trees for multiple quantiles incurs virtually no additional computational overhead compared to learning a single tree. The execution time is nearly independent of the number of quantiles.
3. Interpretability & Robustness: Provides inherently interpretable models where each tree corresponds to a specific, human-understandable quantile (e.g., "the tree for the 90th percentile"). The method is robust to outliers and provides a complete view of the conditional distribution without prior assumptions about its shape.
4. Empirical Validation: A comprehensive evaluation showing that QDL8.5 matches or exceeds the accuracy of state-of-the-art methods (Quantile Random Forests, CaDET) while offering superior interpretability.

4. Experimental Results

The authors evaluated QDL8.5 on four datasets (one synthetic with known ground-truth distribution, and three real-world: Air Quality, Solar Flares, Stock Portfolio Performance) against Quantile Random Forests (QRF) and CaDET.

• Accuracy:

  • QDL8.5 achieved the best or second-best performance across all metrics (Mean Integrated Squared Error, Negative Log Likelihood, Mean Quantile Error, CRPS) on all datasets.
  • It successfully modeled complex conditional distributions, often outperforming ensemble methods despite using shallow trees (depth 3–4) compared to deeper ensembles.

• Efficiency:

  • Naive Approach: Training time scales linearly with the number of trees.
  • QDL8.5: Training time is virtually constant regardless of the number of trees.
  • Speedup: For 5 trees, QDL8.5 was 4.74x faster than the naive approach; the speedup increases as more trees are added.

• Interpretability:

  • Tree Similarity: Analysis using the Jaccard index on tree partitions revealed that trees for adjacent quantiles are highly similar (Jaccard index > 0.4, often much higher).
  • Insight: This implies that an analyst only needs to inspect a few representative trees (e.g., one per "zone" of the distribution) to understand the entire model's behavior.
  • Tail vs. Center: The method correctly identified that trees for the distribution tails (extreme quantiles) differ structurally from the center, justifying the need for quantile-specific modeling.

5. Significance

This work bridges the gap between high-performance optimization and human interpretability in probabilistic machine learning.

• Trust: By providing optimal trees for specific quantiles, users can trust the model's predictions in risk-sensitive scenarios (e.g., "What is the worst-case demand at the 95th percentile?") without relying on black-box ensembles.
• Scalability: It solves the computational bottleneck of optimal quantile regression, making it feasible to model full distributions in real-time or resource-constrained environments.
• Distribution Modeling: It offers a non-parametric, assumption-free way to estimate conditional distributions using simple, shallow decision trees, avoiding the complexity of density estimation methods that require heavy parameter tuning.

In summary, QDL8.5 demonstrates that one does not need to sacrifice accuracy or computational efficiency to gain deep, interpretable insights into the full distribution of a target variable.