7.10 Tree ensembles | Sampling with replacement --[Machine Learning | Andrew Ng]
 In order to build a tree ensemble, we're going to need a technique called sampling with replacement. Let's take a look at what that means. In order to illustrate how sampling with replacement works, I'm going to show you a demonstration of sampling with replacement using four tokens that are colored red, yellow, green, and blue. So I actually have here with me four tokens of colors red, yellow, green, and blue, and I'm going to demonstrate what sampling with replacement using them looks like. Here is a black velvet bag empty, and I'm going to take this example of four tokens and drop them in, and I'm going to sample four times with replacement out of this bag. And what that means is I'm going to shake it up and can't see what I'm picking. Pick up one token, turns out to be green. And the term with replacement means that if I take out the next token, I'm going to take this and put it back in and shake it up again, and then take out another one, yellow, replace it, that's the with replacement part, and then go again, blue, replace it again, and then pick up one more, which is blue again. So that sequence of tokens I got was green, yellow, blue, blue. Notice that I got blue twice and didn't get red even a single time. If you were to repeat this sampling with replacement procedure multiple times, if you were to do the game, you might get red, yellow, red, green, or green, green, blue, red, or you might also get red, blue, yellow, green. Notice that the with replacement part of this is critical because if I were not replacing a token every time I sample, then if I were to pull out four tokens from my bag of four, I will always just get the same four tokens. That's why replacing a token after I pull it out each time is important to make sure I don't just get the same four tokens every single time. The way that sampling with replacement applies to building an ensemble of trees is as follows. We are going to construct multiple random training sets that are all slightly different from our original training set. In particular, we're going to take our 10 examples of cats and dogs, and we're going to put the 10 training examples in a theoretical bag. Please don't actually put a real cat or dog in a bag. That sounds inhumane, but you can take a training example and put it in a theoretical bag if you want. And using this theoretical bag, we're going to create a new random training set of 10 examples of the exact same size as the original data set. And the way we'll do so is we'll reach in and pick out one random training example, and let's say we get this training example. Then we put it back into the bag, and then again, randomly pick out one training example, and see you get that, and you pick again, and again, and again. And notice now this fifth training example is identical to the second one that we had up there, but that's fine. And you keep going and keep going, and we get another repeated example, and so on and so forth, until eventually you end up with 10 training examples, some of which are repeats. And you notice also that this training set does not contain all 10 of the original training examples, but that's okay. That is part of the sampling with replacement procedure. The process of sampling with replacement lets you construct a new training set that's a little bit similar to, but also pretty different from your original training set. It turns out that this would be the key building block for building an ensemble of trees. Let's take a look in the next video at how you could do that.
[{"start": 0.0, "end": 8.88, "text": " In order to build a tree ensemble, we're going to need a technique called sampling with replacement."}, {"start": 8.88, "end": 11.200000000000001, "text": " Let's take a look at what that means."}, {"start": 11.200000000000001, "end": 17.36, "text": " In order to illustrate how sampling with replacement works, I'm going to show you a demonstration"}, {"start": 17.36, "end": 24.52, "text": " of sampling with replacement using four tokens that are colored red, yellow, green, and blue."}, {"start": 24.52, "end": 30.4, "text": " So I actually have here with me four tokens of colors red, yellow, green, and blue, and"}, {"start": 30.4, "end": 35.7, "text": " I'm going to demonstrate what sampling with replacement using them looks like."}, {"start": 35.7, "end": 42.480000000000004, "text": " Here is a black velvet bag empty, and I'm going to take this example of four tokens"}, {"start": 42.480000000000004, "end": 47.480000000000004, "text": " and drop them in, and I'm going to sample four times with replacement out of this bag."}, {"start": 47.480000000000004, "end": 52.0, "text": " And what that means is I'm going to shake it up and can't see what I'm picking."}, {"start": 52.0, "end": 54.68, "text": " Pick up one token, turns out to be green."}, {"start": 54.68, "end": 59.84, "text": " And the term with replacement means that if I take out the next token, I'm going to take"}, {"start": 59.84, "end": 66.48, "text": " this and put it back in and shake it up again, and then take out another one, yellow, replace"}, {"start": 66.48, "end": 73.8, "text": " it, that's the with replacement part, and then go again, blue, replace it again, and"}, {"start": 73.8, "end": 77.0, "text": " then pick up one more, which is blue again."}, {"start": 77.0, "end": 81.4, "text": " So that sequence of tokens I got was green, yellow, blue, blue."}, {"start": 81.4, "end": 85.28, "text": " Notice that I got blue twice and didn't get red even a single time."}, {"start": 85.28, "end": 90.56, "text": " If you were to repeat this sampling with replacement procedure multiple times, if you were to do"}, {"start": 90.56, "end": 99.12, "text": " the game, you might get red, yellow, red, green, or green, green, blue, red, or you"}, {"start": 99.12, "end": 104.56, "text": " might also get red, blue, yellow, green."}, {"start": 104.56, "end": 110.88000000000001, "text": " Notice that the with replacement part of this is critical because if I were not replacing"}, {"start": 110.88, "end": 116.39999999999999, "text": " a token every time I sample, then if I were to pull out four tokens from my bag of four,"}, {"start": 116.39999999999999, "end": 119.0, "text": " I will always just get the same four tokens."}, {"start": 119.0, "end": 124.52, "text": " That's why replacing a token after I pull it out each time is important to make sure"}, {"start": 124.52, "end": 128.12, "text": " I don't just get the same four tokens every single time."}, {"start": 128.12, "end": 135.56, "text": " The way that sampling with replacement applies to building an ensemble of trees is as follows."}, {"start": 135.56, "end": 141.24, "text": " We are going to construct multiple random training sets that are all slightly different"}, {"start": 141.24, "end": 143.68, "text": " from our original training set."}, {"start": 143.68, "end": 148.24, "text": " In particular, we're going to take our 10 examples of cats and dogs, and we're going"}, {"start": 148.24, "end": 153.88, "text": " to put the 10 training examples in a theoretical bag."}, {"start": 153.88, "end": 157.04, "text": " Please don't actually put a real cat or dog in a bag."}, {"start": 157.04, "end": 162.12, "text": " That sounds inhumane, but you can take a training example and put it in a theoretical bag if"}, {"start": 162.12, "end": 163.24, "text": " you want."}, {"start": 163.24, "end": 170.32000000000002, "text": " And using this theoretical bag, we're going to create a new random training set of 10"}, {"start": 170.32000000000002, "end": 174.0, "text": " examples of the exact same size as the original data set."}, {"start": 174.0, "end": 178.88, "text": " And the way we'll do so is we'll reach in and pick out one random training example,"}, {"start": 178.88, "end": 181.60000000000002, "text": " and let's say we get this training example."}, {"start": 181.60000000000002, "end": 188.48000000000002, "text": " Then we put it back into the bag, and then again, randomly pick out one training example,"}, {"start": 188.48, "end": 194.51999999999998, "text": " and see you get that, and you pick again, and again, and again."}, {"start": 194.51999999999998, "end": 198.79999999999998, "text": " And notice now this fifth training example is identical to the second one that we had"}, {"start": 198.79999999999998, "end": 201.04, "text": " up there, but that's fine."}, {"start": 201.04, "end": 205.64, "text": " And you keep going and keep going, and we get another repeated example, and so on and"}, {"start": 205.64, "end": 211.83999999999997, "text": " so forth, until eventually you end up with 10 training examples, some of which are repeats."}, {"start": 211.83999999999997, "end": 217.48, "text": " And you notice also that this training set does not contain all 10 of the original training"}, {"start": 217.48, "end": 218.79999999999998, "text": " examples, but that's okay."}, {"start": 218.79999999999998, "end": 221.84, "text": " That is part of the sampling with replacement procedure."}, {"start": 221.84, "end": 227.2, "text": " The process of sampling with replacement lets you construct a new training set that's a"}, {"start": 227.2, "end": 232.0, "text": " little bit similar to, but also pretty different from your original training set."}, {"start": 232.0, "end": 236.95999999999998, "text": " It turns out that this would be the key building block for building an ensemble of trees."}, {"start": 236.96, "end": 248.08, "text": " Let's take a look in the next video at how you could do that."}]