Bootstrap Sample

easyFREEEnsemble MethodsMachine Learning 1

Generate a bootstrap sample (sampling with replacement) using a given list of random indices.

Given a dataset of $n$ items, a bootstrap sample draws $n$ items with replacement. To make this deterministic, you are given a list of indices to draw.

Return the selected items as a list.

Example

Input

data = ['a', 'b', 'c', 'd']
indices = [0, 2, 2, 1]

Output

['a', 'c', 'c', 'b']

Reasoning

data is the original dataset: $n = 4$ items, 'a', 'b', 'c', 'd', sitting at positions $0$ to $3$ . indices is a pre-drawn list of $n = 4$ positions $(i_1, i_2, i_3, i_4) = (0, 2, 2, 1)$ , standing in for the random draws so the result is reproducible.
Draw $k$ simply returns the item at position $i_k$ , i.e. output $_k = d_{i_k}$ : position $0$ gives 'a', position $2$ gives 'c', position $2$ again gives 'c', and position $1$ gives 'b'.
Keeping the draws in order gives ['a', 'c', 'c', 'b'] — the same length $n$ as the original, holding the items themselves (strings here), not their positions.
Notice that 'c' appears twice while 'd' never appears: that is what sampling with replacement means. A drawn item stays available for later draws, so some items repeat and others are left out.
Here $3$ of the $4$ distinct items made it in; for large $n$ a bootstrap sample contains about $1 - (1 - 1/n)^n \approx 63.2\%$ of them, and the missing ones are called out-of-bag.

Constraints

data: list of items
indices: list of integer indices (0 to len(data)-1, may repeat)
Return the items at the given indices

Learn this in

Probability & StatisticsFoundations Introduction to MLML Study Plan Ensemble MethodsML Study Plan

More from Machine Learning 1

RBF Kernel Matrixhard Polynomial Kernelmedium Hinge Losseasy Linear Decision Boundaryeasy Gradient Boosting Residual Stephard

Concept primer

Background Knowledge

In Machine Learning, particularly in the context of Ensemble Methods, a bootstrap sample is a technique used to generate multiple datasets from a single original dataset. This is done by sampling with replacement, meaning that each item in the original dataset can be selected more than once. The purpose of creating bootstrap samples is to simulate the variability of the dataset, which can be useful for training and evaluating machine learning models.

The concept of sampling with replacement is crucial here. Unlike sampling without replacement, where each item can only be selected once, sampling with replacement allows for the possibility of selecting the same item multiple times. This is analogous to drawing cards from a deck with replacement, where after each draw, the card is put back into the deck, allowing it to be drawn again.

In the context of this problem, we are given a list of random indices to draw from the original dataset. This list of indices determines which items to select from the dataset to form the bootstrap sample. The use of predetermined indices makes the process deterministic, meaning that given the same indices, the same bootstrap sample will always be generated.

Algorithm/Approach

The general approach to solving this problem involves using the given list of indices to select items from the original dataset. This can be achieved by iterating over the list of indices and using each index to access the corresponding item in the dataset. The selected items are then collected into a new list, which represents the bootstrap sample.

Step-by-Step Strategy

To implement the solution:

Initialize an empty list to store the bootstrap sample.
Iterate over the list of given indices.
For each index, use it to access the corresponding item in the original dataset.
Add the selected item to the bootstrap sample list.
After iterating over all indices, return the bootstrap sample list.

Common Pitfalls

Ensure that the indices are 0-based, meaning the first item in the dataset is at index 0.
Be aware of the length of the dataset to avoid index out-of-range errors.
Remember that the bootstrap sample can contain duplicate items since sampling is done with replacement.

Time & Space Complexity

Time Complexity: The time complexity of this algorithm is $O(n)$ , where $n$ is the number of items in the dataset (or the number of indices given), because we are iterating over the list of indices once.
Space Complexity: The space complexity is also $O(n)$ , as in the worst case, we might need to store all $n$ items in the bootstrap sample list.

solution.py

Python 3.13

Test results