So welcome to today's lecture in the Big
Data Analytics summer school at Caltech.
My name is Thomas Fuchs.
I'm a research technologist at JPL and
a visiting scientist at Caltech.
And I will speak about decision trees and
random forests today.
So we will start by
introducing Decision Trees.
How they work?
How they are inferred and
how they are tested?
Decision Trees are then used in one of
the next modules as base classifier for
random forests.
Decision trees are widely used in science
and in practice due to their simplicity,
their speed and their applicability
to a lot of different problems.
So in general a decision
tree is a set of nodes.
On the left side we see
general tree structure.
The tree starts at a root node that's zero
in that case then we have intermediate
split nodes where decisions are made and
then the trees splits up in sub
partitions and then at the end we
have terminal nodes or leaf nodes.
So, in practice you can
imagine a very simple example,
as you can see on the right.
In this scenario we want to classify
images, to belong to one of two classes.
One is outdoor images,
the other one is indoor images.
So, you can think of
asking a set of questions.
So the first question could be,
is the top part of the image blue?
If yes, you could go to the right and
then ask the next question,
is the bottom part of the image blue?
If yes, you would go right,
if no you would go left.
And so on until you reach one of these
leaf nodes and the leaf node then
indicates if the image is actually
an indoor image or an outdoor image.
So this is naturally a very simple
example it will fail most of the time but
it should give you an intuition
how these procedures work.
In medicine you would for example ask
questions about gene expression or
protein concentration, or any other value
you can measure and which is interesting,
and the leaf nodes for example would
indicate if a patient has cancer or not.
In space exploration, we would be
interested, for example, in surface
features and asteroids, and we will talk
about that in one of the later modules.
So, in practice we represent samples
in our data set with a feature vector.
So, features or
attributes describe objects.
So, in this case we have a two
dimensional Feature Space, and
we have two kinds of objects.
A positive class with red pluses and
a negative class with the green minuses.
And they are described by two features,
x1 and x2.
So these could be for example,
weight and height of persons.
These could be two genes,
these could be two visual features.
This could be two astronomical features
describing stars, for example.
And what you can see is that the feature
space is in the feature space,
the two classes are very mixed.
And if you want to now train a classifier,
to differentiate these two classes,
it's not entirely trivial.
So in practice,
one could think of a linear classifiers or
combinations of these features and
try to split the data set
based on some linear combination of x1 and
x2 which in this case
clearly would not work regardless where
we try to make this decision boundary.
So in practice, what we want to do
is we want to use a method which can
flexibly partition the feature
space into sub-partitions where
each partition at the end
will presents a leaf node.
So when we learn a decision tree and
I will explain decision tree learning
based on what we do for random forests.
There are lot of different techniques
how that could be done, but
I will talk about the most
commonly used one.
So in decision tree learning, you would
start by looking at all the different
axis, the different kinds of feature and
try all possible split nodes and
then choose one of them satisfying
some kind of criterium.
In this case it could be
the misclassification rate.
So you want to find the vertical split
number one, which past separates
into two sets of samples into
both positive or negative ones.
Then in the next step you would
go recursively down the tree and
then look only on the left part so
and, after you split with
a feature one and then you would decide
what kind of feature this could be
again in our scenario feature one or
two would separate this classes best.
So, in the case on the left,
there is a quite nice operation, which
optimizes the misclassification rate.
On the right side, again,
you try to separate the space and
come up with a feature.
Then, this is continued until
one of these classes is pure.
So in decision tree learning for random
forest, we would stop learning if you
only have one sample within
one of the sub-classes or
sub-leaves or if the partition or samples
in this partition would be from one class,
we'll be able to have a pure leaf.
In this case it's partition A,
and everything inside would
be the negative class.
We then can continue that in all sub parts
until we end up with a completely grown
tree which completely separates
the features space in only pure classes.
So you can see at the leaf
nodes on the right,
some leafs represent the positive class,
some represent the negative class.
In practice,
what you see here is over fitting example.
So we completely over-fitted the feature
space to nicely separate the classes.
In practice this will lead to
excellent training error, but
to very poor generalization.
And in practice, to overcome that,
if one only trains one tree,
one would use pruning strategies
where you actually limit the depth
of this trees to generalize better or
you could use something
like random forests where all these tress
are learned from different kinds of data.
So now during testing we
could just go down this tree.
Let's see we now have a model.
We get a new sample and that's a new
person with height and weight or
a new biologic example with expression
of two genes that's the yellow
star on the left and if you want to
classify it for being either red or green.
So we would start at
the top of this tree and
then successively ask all these question.
So the first question would be,
is feature one,
which is our x axis, larger than the
threshold at one, then we go to the right,
then we check the threshold on
feature b for, split node three.
And we also go to the right, and
we come to, number six which, again,
checks the feature, does,
split on feature two and so
on, until we end up at a leaf node.
And this leaf node, in this case
the partition F, is completely green, so
that's a negative class.
So we would classify the new
sample as green, in this case.
So, what you can see here are different
properties of a random forest already.
So, first of all, in practice, you would
not only two features as in this case but
you would,
would have a whole set of features.
So, for vision examples,
the number of features quite often go into
the millions for DNA micro-arrays,
you would have hundreds of thousands.
For some astronomic scenarios,
you would have very sophisticated
features which go into the hundreds.
But the tree would, first of all,
operate in a much more high dimensional
case as in this simple example.
But regardless how big the space is,
during test time, when we
actually go down this tree, we would only
check this, in this case, four conditions.
So it's very fast.
It can be implemented enormously fast and
that gives you a huge benefit for real
time applications like autonomous driving
for robots or decision making in medicine.
So in the example before,
we used split nodes or
also they are also cal, called weak
learners, which were decision stops.
So these are axis parallel splits,
at each split node.
But theoretically, we could use any
kind of function at these nodes.
So, we could, for example, use linear
combinations of features as seen in
in the center plot or as seen on the right
plot, we could use for example, conic cuts
to get a more localized
estimation of these features.
Theoretically, one could actually
use trees, neural network or
support vector machines
that these splits but
that would actually defy
the reason to use these trees and
that's this enormous simplicity and
transparence of the final model.
[SOUND] So,
another difference which is important for
our applications is that,
what I showed you before,
was a tree which was learned
until you only have poor classes.
So, every leaf node
represents only one class.
But nowadays, in most examples we
would not do that especially if
you have millions of samples like
in the image specification tasks.
You would not want to trend trees which,
which are thousands of level deep or
hundreds of levels deep.
But you would like to stop earlier and
then you would have a mixture
of samples at each leaf node, and
that gives rise to a posterior estimate.
So, the histograms at every leaf are a
proxy for a posterior for a random forest.
So, if you have, for example, in this
case, we have four different classes blue,
yellow, red and green,
evenly balanced on the right.
And, then if you go down the tree, and
the, the leaf nodes are not pure,
but you would have a dominant class.
For example, at the bottom right you
would have red which is dominating, but
you would also have the other classes.
That then can be used to actually
quantify the uncertainty of the tree.
So, if all the classes have nearly
equal weight, that would indicate that,
that classifier is quite unsure of what's
a prominent class but if you would have,
as in this case, dominating class,
you would, with high confidence,
classify and use sample as red.
Thank you.