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

The given dataset is data = ['a', 'b', 'c', 'd'] and the list of indices to draw is indices = [0, 2, 2, 1].
We use the indices to select items from the dataset with replacement, so the first index 0 corresponds to 'a', the second index 2 corresponds to 'c', the third index 2 again corresponds to 'c', and the fourth index 1 corresponds to 'b'.
The selected items are then combined into a list in the order they were drawn: ['a', 'c', 'c', 'b'].
The final output is this list of selected items.

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