When building regression trees, whether in standalone models or ensembles like Random Forests and Gradient Boosted Trees, the key objective is to decide the best way to split nodes for optimal predictive performance. Traditionally, this has been done using Mean Squared Error (MSE) as a split criterion. However, many modern implementations — such as those in LightGBM, XGBoost, and scikit-learn’s HistGradientBoostingRegressor — use a mathematically equivalent but computationally superior alternative: Friedman MSE.

This article demystifies the idea behind Friedman MSE, compares it to classic MSE, and explains why it’s increasingly the preferred method in scalable tree-based machine learning.

Classic MSE in Regression Trees

In a traditional regression tree, splits are chosen to minimize the variance of the target variable $y$ in the resulting child nodes. The goal is to maximize the gain, or reduction in impurity, achieved by splitting a node.

The gain from a potential split is calculated using:

\[\text{Gain} = \text{Var}(y_{\text{parent}}) - \left( \frac{n_{\text{left}}}{n_{\text{parent}}} \cdot \text{Var}(y_{\text{left}}) + \frac{n_{\text{right}}}{n_{\text{parent}}} \cdot \text{Var}(y_{\text{right}}) \right)\]

Where:

  • \(\text{Var}(y)\) is the variance of the target variable in a node.
  • \(n\) denotes the number of samples in each respective node.

This formulation effectively measures how much more “pure” (less variance) the child nodes become after a split. It works well in many cases but has some computational and numerical limitations, especially at scale.

The Friedman MSE Formulation

Jerome Friedman, while developing Gradient Boosting Machines (GBMs), introduced a smarter way to compute split gain without explicitly calculating variances or means. His formulation is based on sums of target values, which are cheaper and more stable to compute:

\[\text{FriedmanMSE} = \frac{\left( \sum y_{\text{left}} \right)^2}{n_{\text{left}}} + \frac{\left( \sum y_{\text{right}} \right)^2}{n_{\text{right}}} - \frac{\left( \sum y_{\text{parent}} \right)^2}{n_{\text{parent}}}\]

This method retains the goal of minimizing squared error but eliminates the need for floating-point division and subtraction of means, which can be error-prone.

Mathematical Equivalence and Efficiency

Despite looking different, Friedman’s method is algebraically equivalent to minimizing MSE under squared loss. To see this, note that variance can be expressed in terms of the mean squared values, which in turn relate to sums of values.

By using only the sum and count of target values, this method:

  • Avoids recomputation of sample means for every candidate split.
  • Allows incremental updates of statistics during tree traversal.
  • Greatly speeds up histogram-based methods where feature values are bucketed and pre-aggregated.

This efficiency is a major reason why libraries like LightGBM can scan millions of potential splits across thousands of features without breaking a sweat.

Numerical Stability and Practical Robustness

Computing variance requires subtracting the mean from each data point — a step that introduces floating-point rounding errors, especially when target values are large or nearly identical.

Friedman MSE avoids this by working only with sums and counts, both of which are more robust under finite precision arithmetic. As a result, it tends to:

  • Be less sensitive to large-magnitude values,
  • Handle outliers more gracefully,
  • Reduce the risk of numerical instability in deep trees.

This becomes particularly important when dealing with real-world datasets that often contain outliers, duplicates, or unscaled values.

Comparative Table: Classic MSE vs Friedman MSE

Feature Classic MSE Friedman MSE
Formula Variance reduction Sum of squares (per count)
Computational Cost Moderate Low (sums and counts only)
Outlier Sensitivity Higher Lower
Numerical Stability Moderate High
Used In Small regression trees Gradient boosting, histogram trees

Use Cases and When to Use Each

While both methods aim to minimize prediction error via informative splits, they differ in suitability based on context:

  • Small Datasets with Clean Targets: Classic MSE works well and is interpretable.
  • Large Tabular Datasets: Friedman MSE is more scalable and efficient.
  • Gradient Boosted Trees: Friedman’s approach aligns with the boosting objective and is the default in most frameworks.
  • High Cardinality Features: Efficient computation via histograms makes Friedman MSE ideal.
  • Presence of Noise or Outliers: The robustness of Friedman MSE makes it a better default.

In practice, if you’re using libraries like LightGBM, XGBoost, or scikit-learn’s HistGradientBoostingRegressor, you’re already benefiting from Friedman MSE — often without realizing it.

Historical Origins and Impact

The method is named after Jerome Friedman, the statistician who introduced it while developing the MART (Multiple Additive Regression Trees) algorithm, which later evolved into what we know as Gradient Boosting Machines.

By reformulating the split criterion to depend only on aggregate statistics, Friedman laid the foundation for fast, scalable, and robust boosting algorithms. This innovation, though mathematically simple, had a profound impact on how tree-based models are implemented today.

Summary Insights

Friedman MSE exemplifies how a clever mathematical simplification can drive both speed and accuracy in machine learning systems. While classic MSE is still valid and sometimes preferable in small-scale or academic scenarios, Friedman’s formulation dominates in real-world applications.

By leveraging only sums and counts, it reduces computational overhead, increases numerical stability, and integrates seamlessly with histogram-based algorithms. It’s a powerful example of how understanding the internals of a model — even a minor detail like the split criterion — can help practitioners make more informed choices and build better-performing systems.

References

You may also enjoy