[MUSIC] So now that we've talked about
several models, let's dive in into boosting more generally, and then a
specific example of a boosting algorithm. So think about a learning
problem where we take some data, we learn a classifier which
gives us some output, f(x), and we use it to predict on some data so
we say that y hat is a sign of f(x). So if we take some data and we try to make a prediction,
we might learn see a decision stop. So let's say you try to split on income,
we look at folks with income greater than 100,000,
folks with income less than 100,000, and how do we learn the actual
predictions that we make? Well, we look at the rows of our data, the rows where the income was greater
than 100,000, and we see that for those, 3 were safe loans and 1 was a risky loan,
so we're going to predict y hat = safe. Now, if we look at incomes of less than
100,000, we'll see that we have 4 safe and 3 risky, so again we predict safe, so
both sides we're going to predict safe. As it turns out that we do this first
decision stump, seems okay, but it doesn't seem great on the data. And so, decision stump wasn't enough
to capture the information with the limited data. So a boosting will do is
take that decision stump, evaluate it, look at how well
it's doing in our data, and learn a next decision stump,
a next weak classifier and then next the classifier is going to focus on the
data points where the first one was bad. So in other words,
this is a very important point. In other words, we're going to look at
where we're making mistakes so far and want to increase,
see the proportion or the impact or how much we care about the points
where we've made mistakes. And we load in another classifier that
takes care of the points that made mistakes and then we load another one and
another one. And eventually, as we'll see, will
actually converge to a great classifier. What does it mean to learn the data
points were made mistakes? What it means is that we're
going to assign a weight, alpha i to the positive number to
every data point in our dataset. And that weight, when it's higher, it
means that data point is more important. So you can imagine a learning problem
where we have data, not just like we've done so far in this course, but we
have data with weights associated with it. And now we're going to
learn from weighted data. What there is to learn from weighted data,
the way to think about it is that, those alpha is correspond to kind of data points counting more than
one time if its greater than one. So for example, if alpha i is 2, you can think about that data
point is counting twice. If the data point was half you could
think about data point counting as half of a data point. But everything in the learning
algorithm stays exactly the same. It just that instead of counting data
points you count kind of weights of data points. What happens in our
decision stump approach? So we had that first decision stump,
it was not a great, especially for folks with lower income and so we learned
it's weight, which are higher for the places where we've made mistakes and
now we learn the new decision stump. Let's say again we split the columns,
again, written 100,000 less 100,000. When we look at the classifications
decisions that we make, for greater than 100,000 what we do is we sum the weight
of the data points that were risky, and incomes greater than 100,000. So in this case we're summing 0.5, 0.8, 0.7 which adds up to 2 and then for
the risky ones it's 1.2 and so we're going to make
a prediction of y hat is safe. So it's the weighted
sum of the data points. For income less than 100,000,
same kind of idea. We'll go through the data points,
look at the ones that were risk and ones that were safe and
sum up the weight of those. And we see the total
weight of risky that 65, the total weight of safe loans is 3, so
we're going to predict what is risky. So this decision stump is now
going to be a bit better. So we're going to combine this one
with the previous one and others and others until we create
this ensemble classifier. Now, this idea of learning from weighted
data is not just about decision stumps. It's the result that most machine
learning algorithms accept weighted data. So I'm going to show you very briefly
what happens if you are doing logistical regression and you have weighted data. So if you look at the equation on the
bottom here, that's exactly the equation of logistic regressions derivative,
or the update function that we do. This is the thing that you would implement
if you run a logistic regression model. Now, you say, I have this weighted data, I have to reimplement
everything from scratch. My god, my god, my god. And it turns out that it's very simple. You should look at
the middle of the equation, we have the sum over
data points over here. And now, so we just sum our data points. We're just going to weigh
the contribution of each data point. So we just add that weight alpha i to
each term in the sum and we're done. We now have logistic regression for
weighted data. So we showed you two examples, decision
stumps and logistics regression but in general it's quite easy
to learn with the data. So boosting can be viewed
as a greedy algorithm for learning an ensemble from data. We train the first classssifier,
let's say f1(x), if you just have f1(x) just predict
the sign of f1 to be your output of y hat. Now, then you re-weight your data by weighting more data points where we
made mistakes, where f1 makes mistakes. And now we run another classifier, f2 and we learn the coefficients which for
these classifiers, and now our prediction if we just do 2 steps
of this is w hat 1, f1 + w hat 2, f2. And the sign of that is y hat. So that is kind of like the keep
adding new classifiers, optimizing the weights to focus
on more difficult data points and then learning the coefficients
between different classifiers. [MUSIC]