AdaBoost : Data Science Concepts

Key Takeaways

[Music] hey everyone in this video we're going to be talking about attaboost or the adaptive boost this isn't exactly a machine learning algorithm in the same way that decision trees or svms are it's kind of officially called meta learning but it basically in simpler words means that it takes existing machine learning algorithms and organizes them in a certain way so that we get a really good final product and the philosophy of adaboost and we'll see this all throughout this video is that we're going to combine several weak learners in order to make a strong learner so what that means in a nutshell is that the exact type of learner you're using for adaboost is really up to you the most common one and the one we'll look at in this video is decision trees but you can really use any type of classifier you want you can use svm you can use k nearest neighbor as long as at each step you're building a weak version of that classifier and how this adaboost proceeds is that at each step you build a weak decision tree for example we'll look at that in just a second and then you build on that or you boost that weak decision tree with another weak decision tree which fixes the mistakes of the first one and then you just keep going like that so you can think of this as kind of even a metaphor for just your life right at each point in your life you're maybe learning new things you're not good at something but you're building on the mistakes that you're making in the past iteration so this is the philosophy of at a boost so let's get right into it so as we know we're going to combine several weak things into a strong thing and here's how that works first of all let's just say you have some data set that i just said doesn't even really matter just to take an example from previous video let's say we're trying to predict whether or not a student will get into their top choice medical school so our responses are ones and negative ones one if they get in and negative one if they don't and let's say we have n students and we have p predictors so things like their gpa their mcat score various things about the student now step one of adaboost is to build a weak classifier and since we'll be using decision trees today a weak decision tree actually has a kind of funny name it's called a decision stump the reason it's called a decision stump is that we just pick one feature one predictor from these p and that's the end of the model we just split on that one feature and whatever gets classified as one is once and whatever gets classified as negative one is that the student does not get into their top choice medical school and this is called a decision stump so it's just a one level decision tree now we're not going to pick just anyone we're going to be smart about it at each point along the way so we're going to pick the best decision stump possible and what does best mean of course we need to organize some kind of loss function in order to know what best means we're going to be using the following loss function for the first iteration of our ataboost and this is our loss function now i know that just looking at this equation it doesn't really enlighten you it is difficult to see what anything means so i've labeled everything and let's talk through the story of this formula so we're summing over i equals 1 to n so we're summing over all the observations in the training set and for each one we're calculating a measure of error about how far away our candidate decision stump would be from the truth about the student the truth about that student is y sub i so this is the true class of the student either one or negative one if they get in or do not get in alpha 1 is just a coefficient in order to scale the next thing we'll see and the next thing is the predicted class so k1 here is the choice of decision stump so for every single predictor we can think of any of these p predictors we're going to have a different choice for k1 and of course the question we're trying to answer right now is which predictor should i choose which decision stump should i build first so the story of this is basically that let's say that y i is equal to 1 which means that the student truly does get in that means that we would like the decision stump we pick to also predict that the student gets in we want it to match up we want a good accuracy right so for that reason we would want k1 of that student to be equal to 1. now if k1 is equal to 1 and y i is equal to 1 and alpha is positive then we're going to have e to the power of a negative number which is going to be small and that is why this is a measure of error officially it's called the exponential loss i'll link my loss functions video below it might be helpful to watch that first but either way this is just to measure about how far away we are from the truth and it also works if y i is equal to negative one for example if y i is negative one alpha 1 is still positive then in order to make this quantity as small as possible we want the exponent to be negative of course which means that we need k 1 of this to be negative which means it should be negative 1. so no matter what y i is if it's one or negative one this quantity is going to measure our error when we pick our best k one and alpha one that's going to fully define our first level model our first level model c one is going to be alpha one k one so k k1 again is the decision stump we chose and alpha one is the coefficient which is scaling this negative one or one appropriately so that is how we build our first level decision stump now this is at the end of the day even though we picked the best decision stump possible it's still just a one-level decision tree so it can't do too well because there's probably a lot of different intricacies in this data and just choosing one predictor is not going to capture all of them so we're going to have some level of error on each of our students some of the students we might get correct but at this point at the first level we're not going to be expecting to get most of the students correct so let's make a measure about how far away we are from the truth for each student and we've already seen this measure we're going to be using the exponential loss in order to measure how far away we are from the truth for each student so let's talk through this again this is going to be our measure of error for each student after choosing the first classifier in attaboost now why i is again the truth and c one of x i which again is alpha one k one is going to be our prediction for the student so the lower this quantity is the better we are doing a job at predicting the student the higher this quantity is the worst job we are doing at predicting the student correctly and for that reason we're going to give each student this weight and so therefore the higher this weight is the worse this classifier did on that student the lower this weight is the better this classifier did on the students so here's a look at that graphically let's just say there's five students for simplicity so looking at this graph we see that student one two and five have very low weights or very low exponential losses which means they're doing a good job this classifier did a good job on them but looking at this graph it's pretty obvious we're doing a bad job on students three and four and this is where the adda or adaptive part of adaptive boost comes in which means that now we're going to build a second classifier but we're not just going to build it blindly we're going to build it with the knowledge of the first classifier and we're going to build it such that we are correcting for the biggest mistakes in the first classifier which are students three and four and so we proceed in the same way step two is to pick a next decision stump k2 so now you look through all the predictors again and say i want to choose my next predictor in order to build my next decision stump k2 and now we want to minimize a very similar looking quantity to this one in fact they look almost the same there's just one difference which is this term w i 2. so let's again label each term of this formula so you can see the full story that it's trying to tell us okay so this first term is the weight of each observation and as we saw the biggest weights are given to observations three and four and this term is crucial because it means that we are giving the biggest emphasis we are putting the biggest priority on stuff that we were very wrong about before so imagine that for students one two and five this term is very small so the entire contribution in the summation is not going to be that important we are mostly concerned with stuff that was predicted wrong in the previous classifier so this is a weight now moving on what is this part right here alpha 2 k2 this looks a lot similar to alpha 1 k1 and that's because it's serving the same role this is our new classifier so again we're building a new decision stump k2 and we have a new scaling constant alpha 2 and these two things together alpha 2 k2 are going to be our new weak learner or our new week classified all right and the last part of the story is what is this total term here this exponent e to the power of this new week learner that is a measure of the loss of each of these observations from one to n using the new week learner okay so if we're using the new week learner alone this is the loss we would get on each observation x x i so now what does it mean that we're trying to minimize this whole quantity what it means to minimize this whole quantity is that for observations that we were doing really poorly on previously which are going to have high weights so for observations who have big w i's we need the next term to be very small which means that the new loss which is attributed to the new classifier we're using has a low loss on things that we were not doing very well at in the past so in words we prefer a new weak learner alpha2k2 so this guy who fixes old mistakes so we take a look at the mistakes that are biggest the biggest problems from the previous week learner and we pick the new weak learner who is going to fix these mistakes who is going to minimize them take them closer to zero and that is why adaptive boost is so elegant and so powerful because it's basically at each step not building a very smart algorithm at all if you think about k1 or k2 by themselves they're not doing a good job but because they're building on each other and you can imagine i just showed you two steps because it just kind of continues from there but you can imagine i'm going to build a next week learning k3 then k4 and each time they're not just being born blind they're being born with the knowledge of how well we're doing on the previous iteration and that's what make this adaptive and the boost comes from the fact that each of these is boosting on the current story so far so just to finish this video and show you mathematically what they look like so our current model now at this step after we've chosen an alpha 2 and a k2 so our new model c2 is given by our old model c1 again c1 is alpha 1 k1 so our new model is that old model plus the boost and the boost is alpha 2 k2 which is going to build on or fix the mistakes of the previous classifier and these alphas now you can see their role a little bit better they're basically weights on how much of each weak learner we want right because this guy is alpha 1 times k1 and this guy is alpha 2 times k2 so alpha 1 and alpha 2 kind of tell the story about how much of the first one do you want how much of the second one do you want how much of the third one do you want it's possible that we might want more of a certain weak learner than another and our alphas allow us to control that maybe the last thing i'll say in this video is a couple of warnings in attaboost so some of you might get the inkling that this could lead to overfitting because aren't we kind of just fixing our mistakes each time so at some point it's going to get too finely tuned to the training data and you're correct if we continue this process way too long and don't have a stopping point it's going to learn all of the signal and noise in this data so that's going to lead to overfitting so one of the art of adaboost is knowing when to stop say that okay i'm happy with my classifiers up to this point and my final classifier is going to be this weighted sum of all of my classifiers along the way so that's one source of overfitting another source of overfitting which is not really the model's fault but is really the fault of the person who is building it is that you might choose weak classifiers that aren't actually weak for example if you're using like a very complicated neural network as your weak classifier then it kind of defeats the whole purpose of adaboost so make sure that you're using a truly dumb truly weak classifier at each step in order to prevent this overfitting also one last issue with adaboost is that we might have stubborn observations which means that we might have observations whose weights are high in this step whose weights are high in the next step and whose weights just consistently stay high they're like just really hard to predict for whatever reason the reason that this is a problem in adaboost is because it's going to just keep focusing on that observation it's going to say this is the problem this is the problem and each weak learner is going to try and fix that and maybe not be concerned so much with all the other ones but it might be better if we just eliminated that from our data set in the beginning so that it could learn the entire data set as a whole instead of just focusing on that one problematic observation okay so that's all i had to say about adaboost i really hope you enjoyed this video if you did please like and subscribe for more videos just like this any comments are always welcome below and i will see you next time