our first ensemble technique is called bagging and is a classic technique for
generating lots of predictors
and combining the two gether in a simple way to do a better job
ensemble methods try to use
a collection of predictors to do a better job than any single predictor
would alone
our first instance if this is called
bagging stance for bootstrap aggregation
banking is a technique for learning many classifiers each using only portions of
the data
and then combining them through a model averaging technique
the idea behind this is to reduce overfitting
up a classic models so recall that when we over fit we would memorize the
dataset
and we would get a far lower training air on
on that training dataset then we would see on say a new validation testator
so we did techniques like cross-validation to try to test or check
to see whether we had over fit
cross-validation we would take our dataset and we would repeatedly split it
up
into one part which would trade a model with a
given complexity level and another part which would check
to see whether we had over fit so this was a way to use the entire training set
but still do some kind of a verification
whether or not we were beginning to over fit on the data
the idea behind backing is to to a similar kind of data splitting or
or a free sampling technique but instead of using them to check to see whether we
over fit
we instead try to combine them so that we produce a better classifier
predictor bagging relies on a classical statistical technique called the
bootstrap
which creates a random new subset of data
by sampling from a given dataset so
the idea is that we have a particular dataset a
and we'd like to generate a similar dataset up by
sampling from that with replacement so this is used in statistics to generate
confidence values a confidence intervals estimates
on and understand what that variation
due to the particular realization in the dataset is
to do it we take a collection of n data points
and we can generate a new imaginary data set up size and prime
by simply drawing those employed dataset data points from our collection
using replacement they're very into this that use without replacement but we
won't really focus on those
backing
then uses bootstrap as a sub routine a bit slurs
so it creates kahler nurse each of which is created independently
we take the original training set and each learner generates
its own I'll training datasets so
data sets up a lie bite drawing
n prime data points from the original full training set
using replacement it then trains a classifier
on these data that the state will were drawn with replacement
so some of them will be repeated and other data points will be left out
we just learn all these in parallel
and then to test we predict on all k have the predictors
and we have them doing unweighted accommodation so a classifier would do a
majority vote
and a refresher what do you say and unweighted average
so this technique is used to reduce the complexity or reduce overfitting
and you can see why it might reduce complexity to some degree has some
complexity control
it's harder for any particular bag classifier to memorize the data
since each one is seeing its own individually generated training dataset
and that training dataset was sampled
from the original one so it's left some points out so those points won't be seen
by that particular classifier
and even if it really is a severely overfitting
typeof classifier even if it never rises
its training set it will be missing some data from the original training data
and so it won't be able to memorize the full training except
up so it should control complex TIF to some degree because
every element of it will be unable to fully memorized the data
so I should say that this doesn't work on predictors that are linear functions
above the input data since
the average up a linear function will just be another linear function so it
doesn't really do very much
on it does work with anything that has nonlinearity so things like perceptrons
where we have a linear function but its threshold so
actual protection is not a linear function to the puts
its fine backing is fundamentally trading of fun
bias variance balance that we find in under and overfitting
the idea behind bias and variance was that
um the two effects that we were worried about in our training
were one bias which represents our inability to represent
the true function in the class a function's that we're willing to
tolerate
so biased tends to be something that pulls us toward a particular function or
class a function's
regardless if the data and this might be something simple like
a only looking at a certain class of functions like
linear or quadratic functions or it might be something
a in softer like a strong regulars Asian which
will forces toward models that tend to have zeros in the parameters or or
have small parameter values on the other hand
when we didn't invoke any such bias
we ended up with models that were quite complex they could fit very complex
functions
but they had high variance so they were extremely dependent on the exact data
that they
were trained on so in particular if we had
let's say a hundred training examples and we trained what are these
very complex models
it would be able to fit whatever function explain those data
but it would be quite likely the free true 100 new examples from the same
concept
that the model we trade on the new data would be very different
than the first model and so any particular realization
love the dataset produces a high degree of variation in the predictor
so the the model itself has high variance
bagging works on the high variance and at the spectrum
by taking a collection above low bias
height variance models and averaging them together
so the averaging works to reduce variance
but without Inc significantly increasing the bias
so it's simply tries to move this curve downward
here's an example bootstrap into backing using decision trees
on the IRESS data so
here up in the upper right is the actual
IRESS data with three classes blue green red being plotted
and a decision tree with earth fault Epson no complex the control
%uh and the function that it learns on those data being plotted
as well so the bootstrap procedure takes these data
and it draws a new set of data in this case %uh the same size
using replacement to try to simulate some
equally likely data set that we could have seen in a different universe
so here's that dataset right it's a on a slightly different scale so it's a heart
a little hard to compare but um you can see if you stare that
a few data points are missing um
in particular this red point here
has vanished from this data set on
it's a it's particularly hard to tell oh and this this red point here also has
vanished
um it's particularly hard to tell data that have been sampled twice since those
points are right on top of each other
but their presence as well so this is a new dataset
up the same size simulated from the original dataset
and being slightly different it learns a slightly different decision tree model
here's yet another dataset sampled in exactly the same way
again being slightly different it learns a slightly different decision tree model
here's a third again slightly different
a fourth in the fifth
the randomness created in the bootstrap data generation process
produces 5 equally likely models
in some sense that we could have gotten from the same data
had we just been say differently lucky
so now we take that collection and combine it into an overall
average within unweighted some to in this case for classifying so I mean we
take a majority vote
so if the majority of classifiers pics a particular class we predict that one
this reduces the memorization effect since not every predictor can see each
data point
um in particular a region will only be protected to a class
if it has enough support among all the data points
that in most up the decision trees we learned that region
is still assigned to the class so this a lower the complexity of the overall
predictor
and typically lead us to better generalization performance than the
single predictor we learned first
so here's an example where we are we've learned the five treys shown on the
previous slide in average them together
and you can see already regions like this that were assigned to green by the
influence of a single data point
have now been overwhelmed by some the other predictors that too but perhaps
have that data point in it
by 25 trees we're starting to see what I think a human would start to assign
so blue is taking a more
I'll oblong region in the upper left
red in the right hand side in green in lower center
and we're starting to see that shape emerge from our collection
tree is by a hundred trees that shape is generally prevalent
and many other the artifacts that we saw in the single decision tree
have vanished so that now we find that green has a relatively
sensible looking support in the center
and blue and red have also taken on fairly sensible
looking supports as well
practically speaking bagging isn't easy procedure to implement
to here's MATLAB code just showing how easy the first thing we do is we create
a container for our set of classifiers in this case a cell array
cell arrays in Matlab can represent collections UHV
arbitrary types objects although in this case will probably just be using the
same
typeof classifier within iterate over the number of classifiers would like to
learn
and we do is procedure to generate are bootstrap data sample
so if we'd like to generate and use data points
valued between one and an with replacement
which is generate a NU's red numbers between one and so we can do that just
by uniformly generating random numbers
multiplying the by and then rounding them up using the ceiling function
we select out those data points that will contain several values that is the
same so we'll
get some repetition in our data just by
a extracting data set RI
to be X love those indices and we extract out the targets as well
and then we call our classifier function so this is some
black box function the trains a classifier on the new bootstrap dataset
XI with targets while I
we store the result in our set of classifiers when we go to test
we just create a collection of predictions so we need
the number of data that we're testing on times the number I love
classifiers that we've trained we predict
up on that vector UHV test data
for each classifier intern and then at the end we do a procedure to
do a majority vote so this is a simple one-line majority vote between
outputs 1&2 if you have a multi-class classifier you need to do a slightly
more complex procedure
a particularly common application %uh backing is the
you serve them using decision trees and a
algorithm called random forests
so one problem that arises when you apply bagging
to decision trees is that if you have a large enough amount of data
often the decision trees that you learn are very different so if you have enough
data for example
the root node even if you resample those data
with replacement will look generally the same into the first variable selected
the first feature
and the first bullet point will be fairly similar
and so the class have trees that you learn in your bag in procedure
is not really %uh different enough it's not really diverse enough to help
the solution is to introduce some extra variability in Miller
and inject some extra randomness into this procedure
and so the way random forest do that is at every step
%uh the decision tree training process
instead of searching overall features we just a search over some subset of
features
so this is going to create diversity among our trees
because at any particular node
in want reverses another the same set of features will not be available
so in one tree the best feature among it's allowed set
will be different the best feature among a different trees allowed set
that'll produce a larger variability in our collection of trees
and then we just average over them in the same way
this is again extremely simple to implement so
in our decision tree recur sieve data splitting function
%uh instead love recur saying attentive searching over every possible features
in every possible split
we first generate a random subset of the features have some size
and search only over that set and all split
otherwise the procedure works exactly the same way as before
in summary bagging is that classic ensemble technique
producing better predictors than any single predictor
it stands for bootstrap aggregation and it's a technique that tries to reduce
the complexity of a model class
see choose a model class that's very prone to overfitting
and apply backing to provide a collection a full learners in that class
that are less complex and less prone to overfitting
in practice it's quite simple to implement which us resalable the data
once
for each learner each learner is trained on individual resettling
and we create a predictor that might over fit on that sample
but then by averaging them together produces something that's robust
to small variations in the data
essentially plays on the bias variance trade-off choosing something that's
prone to overfitting and this has low bias the reducing its variants or model
averaging
the price is this a course is the computational cost
which if we learn k back predictors
our prediction time computation becomes k times larger than it would have been
before