Out-of-Bag Score

MediumClassical ML

Problem statement

In bagging, each estimator is trained on a bootstrap sample, so some rows are left out of its training set; those rows are its out-of-bag (OOB) samples. Scoring each row only with the estimators that never saw it gives a free estimate of generalization accuracy.

Implement calculate_oob_score(n_samples, bootstrap_indices, predictions, y_true):

  • bootstrap_indices[e]: the row indices used to train estimator e (may contain duplicates). Rows not in this list are OOB for e.
  • predictions[e]: estimator e's predicted labels for all n_samples rows.
  • y_true: the true labels.

For each row, collect the predictions of the estimators for which it is OOB and take the majority vote; if several labels tie, use the smallest label. Rows that are in-bag for every estimator are excluded. Return the accuracy over the remaining rows, rounded to 4 decimals, or 0.0 if no row has any OOB prediction.

Example

Input:

calculate_oob_score(5, [[0, 1, 2], [1, 2, 3], [2, 3, 4]],
                    [[0, 1, 1, 1, 0], [0, 1, 1, 1, 0], [0, 1, 1, 1, 0]],
                    [0, 1, 1, 1, 0])

Output:

1.0

Reasoning: Row 0 is OOB for estimators 1 and 2 (vote 0, correct); row 1 for estimator 2 (vote 1, correct); row 2 is in-bag everywhere and excluded; row 3 for estimator 0 (correct); row 4 for estimators 0 and 1 (correct). Accuracy is 4/4.

Show hint

For a given row, which estimators are allowed to vote on it if the estimate is to be honest?

Relevant roles: Data Scientist, ML Engineer and Applied Scientist.

Related free problems