Neel Mishra
← All Posts
From Scratch · C++ · ML · Gradient Boosted Machines · Part 3

GBM Regularization and Evaluation in C++

July 2026 · 16 min read

The first two implementation posts built working GBM models. This final post adds the controls that make them usable: options, row subsampling, validation curves, early stopping, and permutation importance. The goal is not a full XGBoost clone; it is the practical scaffolding that turns the core loop into a model that can be tuned and inspected.

Options Struct

Collecting hyperparameters in one struct makes experiments reproducible:

struct GBMOptions {
    int rounds = 300;
    int treeDepth = 3;
    int minSamples = 8;
    double learningRate = 0.05;
    double rowSample = 0.8;       // fraction of rows used per tree
    int earlyStoppingRounds = 25;
    unsigned seed = 42;
};

rounds is now a maximum. Early stopping will choose how many fitted trees to keep.

Row Subsampling

Row subsampling trains each tree on a random subset of rows while still updating predictions for all rows after the tree is fitted. This is stochastic gradient boosting.

vector<int> sample_rows(int n, double fraction, mt19937& rng) {
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    shuffle(idx.begin(), idx.end(), rng);
    int keep = max(1, (int)round(fraction * n));
    idx.resize(keep);
    return idx;
}

Matrix take_rows(const Matrix& X, const vector<int>& idx) {
    Matrix out;
    out.reserve(idx.size());
    for (int i : idx) out.push_back(X[i]);
    return out;
}

vector<double> take_values(const vector<double>& y, const vector<int>& idx) {
    vector<double> out;
    out.reserve(idx.size());
    for (int i : idx) out.push_back(y[i]);
    return out;
}
Train on a subset, update all rows. The tree sees only the sampled rows during fitting. Once fitted, it predicts for every training row so the ensemble state remains complete.

Validation Curve

For regression, the training loop can evaluate validation RMSE after every round:

struct FitHistory {
    vector<double> trainRmse;
    vector<double> validRmse;
    int bestRound = 0;
    double bestValid = numeric_limits<double>::infinity();
};

FitHistory fit_with_validation(RegressionGBM& model,
                               const Matrix& Xtr,
                               const vector<double>& ytr,
                               const Matrix& Xva,
                               const vector<double>& yva,
                               const GBMOptions& opt) {
    mt19937 rng(opt.seed);
    FitHistory hist;
    model.F0 = accumulate(ytr.begin(), ytr.end(), 0.0) / ytr.size();
    vector<double> predTr(Xtr.size(), model.F0);
    model.trees.clear();

    int stale = 0;
    for (int m = 0; m < opt.rounds; ++m) {
        vector<double> residual(Xtr.size());
        for (size_t i = 0; i < Xtr.size(); ++i)
            residual[i] = ytr[i] - predTr[i];

        vector<int> rows = sample_rows((int)Xtr.size(), opt.rowSample, rng);
        Matrix Xsub = take_rows(Xtr, rows);
        vector<double> rsub = take_values(residual, rows);

        RegTree tree(opt.treeDepth, opt.minSamples);
        tree.fit(Xsub, rsub);

        for (size_t i = 0; i < Xtr.size(); ++i)
            predTr[i] += opt.learningRate * tree.predict(Xtr[i]);

        model.trees.push_back(move(tree));

        double trainScore = rmse(model, Xtr, ytr);
        double validScore = rmse(model, Xva, yva);
        hist.trainRmse.push_back(trainScore);
        hist.validRmse.push_back(validScore);

        if (validScore < hist.bestValid) {
            hist.bestValid = validScore;
            hist.bestRound = m + 1;
            stale = 0;
        } else if (++stale >= opt.earlyStoppingRounds) {
            break;
        }
    }

    model.trees.resize(hist.bestRound);
    return hist;
}

The model keeps the best validation round, not the final attempted round. This mirrors the early-stopping workflow in the XGBoost walkthrough.

Example Curve

round 20 train RMSE=0.318 valid RMSE=0.351 round 60 train RMSE=0.168 valid RMSE=0.224 round 100 train RMSE=0.128 valid RMSE=0.211 round 140 train RMSE=0.102 valid RMSE=0.219 early stop: best round = 104, valid RMSE = 0.209
best round train valid boosting rounds
The validation curve bottoms out before training loss finishes falling.

Permutation Importance

A simple model inspection tool measures how much validation error increases when one feature column is shuffled:

vector<double> permutation_importance(const RegressionGBM& model,
                                      Matrix X,
                                      const vector<double>& y,
                                      mt19937& rng) {
    int d = (int)X[0].size();
    double base = rmse(model, X, y);
    vector<double> imp(d);

    for (int f = 0; f < d; ++f) {
        vector<double> original;
        for (auto& row : X) original.push_back(row[f]);

        vector<double> shuffled = original;
        shuffle(shuffled.begin(), shuffled.end(), rng);
        for (size_t i = 0; i < X.size(); ++i) X[i][f] = shuffled[i];

        imp[f] = rmse(model, X, y) - base;

        for (size_t i = 0; i < X.size(); ++i) X[i][f] = original[i];
    }
    return imp;
}

The original column is restored before moving to the next feature. If shuffling a feature destroys validation performance, the model relied on that feature.

GBM Implementation Checklist

  1. Use a held-out validation set, or cross-validation for small datasets.
  2. Fit each preprocessing transform on training data only.
  3. Start with shallow trees and a small learning rate.
  4. Use early stopping to choose the number of trees.
  5. Report both the metric being optimized and the metric used by the application.

The resulting C++ GBM is still compact: one CART regression tree, one additive loop, and a small evaluation harness. That compactness is the purpose of implementing it from scratch; the core idea is visible enough to connect directly back to the conceptual GBM series.