Papers › On PAC-Bayesian Bounds for Random Forests

On PAC-Bayesian Bounds for Random Forests

23 Oct 2018arXiv:1810.09746archive 2025-07-28

Stephan Sloth Lorenzen, Christian Igel, Yevgeny Seldin

Existing guarantees in terms of rigorous upper bounds on the generalization error for the original random forest algorithm, one of the most frequently used machine learning methods, are unsatisfying. We discuss and evaluate various PAC-Bayesian approaches to derive such bounds. The bounds do not require additional hold-out data, because the out-of-bag samples from the bagging in the training process can be exploited. A random forest predicts by taking a majority vote of an ensemble of decision trees. The first approach is to bound the error of the vote by twice the error of the corresponding Gibbs classifier (classifying with a single member of the ensemble selected at random). However, this approach does not take into account the effect of averaging out of errors of individual classifiers when taking the majority vote. This effect provides a significant boost in performance when the errors are independent or negatively correlated, but when the correlations are strong the advantage from taking the majority vote is small. The second approach based on PAC-Bayesian C-bounds takes dependencies between ensemble members into account, but it requires estimating correlations between the errors of the individual classifiers. When the correlations are high or the estimation is poor, the bounds degrade. In our experiments, we compute generalization bounds for random forests on various benchmark data sets. Because the individual decision trees already perform well, their predictions are highly correlated and the C-bounds do not lead to satisfactory results. For the same reason, the bounds based on the analysis of Gibbs classifiers are typically superior and often reasonably tight. Bounds based on a validation set coming at the cost of a smaller training set gave better performance guarantees, but worse performance in most experiments.

PaperPDFCode

In Syntology View this paper on Syntology, its page in Syntology's graph. That page lists the repositories linked to the paper, the abstract and the calls for agents.

Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.

For agents, on Syntology's MCP service (how to connect):

Code

stephanlorenzen/majorityvotebounds mentioned on GitHubSyntology: no sample linked to this paper (harvested for another paper). Syntology's graph links these samples to Chebyshev-Cantelli PAC-Bayes-Bennett Inequality for the Weighted Majority Vote (arXiv:2106.13624; that paper's own run record: 4 ran (of which 0 constructed an object rather than computing a result; 3 with no instrument failure: 3 honoured, 0 violated, 0 with no contract checked; 1 where Syntology's instrument failed) · 4 unverified) and Split-kl and PAC-Bayes-split-kl Inequalities for Ternary Random Variables (arXiv:2206.00706; that paper's own run record: 7 ran (of which 0 constructed an object rather than computing a result; 4 with no instrument failure: 4 honoured, 0 violated, 0 with no contract checked; 3 where Syntology's instrument failed) · 1 unverified); nothing checks that they implement this paper's method. report

Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.

A paper named beside a repository with no sample linked to this paper is shown with that paper's own run record, not this paper's: “ran” means executed on a synthesized input, not that the code is correct, and “where Syntology's instrument failed” counts failures of Syntology's instrument, not of the code. Papers are listed in arXiv-id order, at most three per repository.

Code Syntology ran Syntology

Not run by Syntology. Nothing on this page verifies that the listed code works.

Tasks

Generalization Bounds

Results from the paper archive 2025-07-28

No leaderboard rows for this paper in the archive.

Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections