Out-of-Bag Error

Estimate the test error of a bagged ensemble without a test set.

In bagging, every model trains on a bootstrap sample: n rows drawn from the training set with replacement. Each bootstrap sample leaves out about a third of the rows. For any row, the models that did not see it can predict it honestly, as if it were test data. Scoring each row with only those models gives the out-of-bag (OOB) error.

You get:

• y, the true labels, shape (n,)
• predictions, shape (n_models, n), where predictions[m, i] is what model m predicts for row i
• bootstrap_indices, a list with one array per model, holding the row indices that model was trained on (with repeats)

For each row, collect the predictions of the models whose bootstrap sample does not contain that row. Combine them by majority vote, with ties going to the smallest label. Rows that every model saw are skipped. Return the fraction of the remaining rows whose vote is wrong.

Function signature

def oob_error(y, predictions, bootstrap_indices):

Example

Input

y = np.array([0, 1, 1, 0])
predictions = np.array([
    [0, 1, 0, 0],
    [1, 1, 1, 0],
    [0, 0, 1, 1],
])
bootstrap_indices = [np.array([0, 0, 1, 2]), np.array([1, 2, 3, 3]), np.array([0, 1, 1, 3])]
oob_error(y, predictions, bootstrap_indices)

Output

0.3333333333

Reasoning

Model 0 never saw row 3, model 1 never saw row 0, and model 2 never saw row 2. Every model saw row 1, so it is skipped. Row 0 gets one vote, 1, which is wrong. Row 2 gets 1, which is right. Row 3 gets 0, which is right. One of three scored rows is wrong.

Constraints and notes

• Labels are non-negative integers.
• If no row is out of bag for any model, return 0.0.