So, continuing the exploration of large
scale machine learning topics today we
will focus on a different algorithm,
called the decision tree al, algorithm.
And the idea here is that, instead of
modelling the decision space between,
let's say, positive and negative examples
using single, single line, we will,
we will learn much more
complicated decision boundaries.
And this will allow us doing a,
kind of much more fine grained way to
represent the differences between,
let's say, positive and negative examples,
if we are talking about classification.
So just to remind you, what we
are talking about or thinking about,
is that given, given a given attribute,
let's say a wealth of a person,
we want to predict the value of
this attribute by the means of
some other features or attributes
available, available to us, right.
So in a sense, what we would like to
do is, we would like to figure out,
how wealthy is the person, given various
other characteristics of this person.
The way we can think about this is,
is that we can think of
input attributes as the features
that we know about the person.
So, for example, imagine that every person
is described by a set of d features x1,
to x sub d.
And then each feature,
let's call it j, has a domain o sub j.
Right.
When I say a domain,
I mean what is the number of, or
what are all the different values that
this feature, or this attribute can take.
For example, if the feature x sub j is a,
favorite color of a person,
this would be what we call
categorical attribute,
right it can take values red,
green, blue and so on.
Another thing for example, would be if I
can numerical features in a sense that,
for example if I ask what's
the weight of that person or
how old is that person that is,
that is nicely a number and, and
a given variable, in this case a feature,
would have a domain that is
let's say a non negative real numbers if
we are asking about a weight of a person.
And now, of course, the same thing
happens to what is the value of y,
which is the value that we want
to predict, we will call this
the dependent variable, or this is the
thing, the quantity we want to predict.
So, now our idea is, is the following
that's kind of we started last time.
We are given a set of data d, we're given,
if we are given a set of n we
will call them training examples,
x sub, x sub y comma y sub i.
Where basically the idea is that x sub
i is a d-dimensional feature vector.
Right?
So d, d-dimension's from up here.
And then, y is simply the variable
that we want to predict.
An, and, and now, based.
What we want to do is we
want to learn the mapping,
that maps the features, of a given
person to the, wealth of a given person.
So that is our goal.
And now the question is,
how is this function that takes
the feature sentence forming them
into the value we want to predict?
How does this function look like?
right?
So the idea will be that basic decision
trees is is tree-structure plan that given
a set of variables it wants to test that
set of variables, and predict the outcome.
So, to be a bit more concrete, here is
an example of a, of a decision tree.
Right?
A decision tree is a,
is a tree hierarchical structure
where I have two types of nodes.
I have what we will call internal decision
nodes, and I have prediction nodes.
Here are,
here are the nodes of the hexagons.
And this tree can be you know, as deep as
we want, as wide as we want, and so on.
And the important thing here is that,
in this tree we have the as I mentioned,
decision nodes, they basically examine
the value of a given attribute and ask,
you know, is this predicate satisfied,
yes or no?
And then we have the internal the leaf
nodes, which we can call decision nodes,
which then say, okay, for this set of
examples, let's predict the value.
So, the idea is that the, as I mentioned,
internal notes have the split values,
the leaf nodes make predictions and
in particular what we will look at
today is only decision nodes that,
that are based on binary splits so,
basically every node has
at most two children.
So, kind of the,
there is a predicate or a condition and
then whether that condition
is satisfied or not.
Right?
So kind of if condition is satisfied we
go to the left, and
if it's not we go to the right.
We will be talking about
numerical attributes, and we will
think about regression, which means y
will be let's call it a real number.
So this is the setting that
we want to talk about.
So, the hard part here is,
how do we build the tree?
Right.
now, the easy part is,
how do we make a prediction?
So, making a prediction is very easy,
right?
And so given that somebody,
that we already built a tree, given our
training example, we want to predict what
is the y value for that training example.
So the idea is that we want to
take this x sub, x sub i and
kind of drop it throughout
throughout the tree and
see which which prediction node it ends,
it ends in and then predict that value.
For example,
imagine that I have a particular trend,
example that comes in here.
I can first evaluate, right?
Is the first feature of
this training example.
Is it, does it have value less than v1?
If the answer is yes, I move to the left.
I end up in the prediction node,
and my predicted value is 0.42.
If the condition is not satisfied,
and the answer is no to my,
to my condition, I would move to
the right, and I would keep kind of
moving down the tree until somewhere
I would hit my prediction node, and
I would make a prediction for that case.
Right?
So the idea is that
basically every node examines one,
individual feature.
Looks at it and then makes a decision
is the condition satisfied or not, and
then kind of moves either to the left
branch or to the ri, to the right branch.
So, to have an idea of what
decision trees are really doing and
what kind of interesting
decision surfaces they can find,
let's look at this simple
two dimensional example.
Where I have set of data points in
this two dimensional space, and
imagine we want to do classification.
We want to,
we want to separate pluses from minuses.
So the way, the decision tree building
procedure would would start is
that given this kind of,
training data set.
We want to go and recursively kind
of split this space into smaller and
smaller pieces, such that each
individual region in this space is
uniformly populated by either all
pluses or, or, or all minuses.
So, for example, what we could do is,
is to say first we have our first node
in the decision tree, and
we want to decide what is the first split.
And imagine that we say the first
split is at value e1, so we say
is the value x1 of a given, of a given
data point, imagine the data point here.
Is the x, the value x1 less or
more than the value v1.
Right?
So I have v1.
And now if the answer is yes,
I go to the left and
otherwise I go, I go to the right.
And now I could now go and
find the second split.
So I will take the all,
all the data that is, that is down here.
This is everything that kind
of goes to the left and
I ask okay, how can I now split pluses and
minuses in this case.
And maybe I find then you,
decide to draw a line here.
So now I would have the value v2 and
I can draw another decision out and ask,
you know, is x2 less than v2 and
then I say is, is, is it or is it not.
If it is right then I notice
I have all the pluses, so
if the value is less than v2 then I
here I say yes, let's predict plus.
If the value, is, not less than v2,
I still have this messy part.
So, for example, I would want to maybe
split again along this dimension and
split along that dimension.
And similarly, on the top I would want
to split here, and this way build the,
build it three throughout throughout
again where I have the prediction.
So this is kind of one idea how we can
think about building a decision tree.
What is now interesting here is that we
have this complicated decision boundary,
that splits pluses and
minuses from each other.
And we see that we kind of have this
area where there are minuses, and
then we have this other area here
where there are pluses, and we
see that we could never kind of separate
these two pluses out with a single line,
but we can use decision trees to learn
this more complicated decision boundary.