70487227
lOMoARcPSD| 70487227
Cs229 Decision trees notes
Decision Trees
We now turn our attention to decision trees, a simple yet flexible class of
algorithms. We will first consider the non-linear, region-based nature of
decision trees, continue on to define and contrast region-based loss
functions, and close off with an investigation of some of the specific
advantages and disadvantages of such methods. Once finished with their nuts
and bolts, we will move on to investigating different ensembling methods
through the lens of decision trees, due to their suitability for such techniques.
1 Non-linearity
Importantly, decision trees are one of the first inherently non-linear
machine learning techniques we will cover, as compared to methods such as
vanilla SVMs or GLMs. Formally, a method is linear if for an input x ∈ Rn (with
interecept term x0 = 1) it only produces hypothesis functions h of the form:
h(x) = θTx
where θ ∈ Rn. Hypothesis functions that cannot be reduced to the form
above are called non-linear, and if a method can produce non-linear
hypothesis functions then it is also non-linear. We have already seen that
kernelization of a linear method is one such method by which we can achieve
non-linear hypothesis functions, via a feature mapping φ(x).
Decision trees, on the other hand, can directly produce non-linear
hypothesis functions without the need for first coming up with an
appropriate feature mapping. As a motivating (and very Canadien) example,
let us say we want to build a classifier that, given a time and a location, can
, lOMoAR cPSD| 70487227
CS229 Fall 2
predict whether or not it would be possible to ski nearby. To keep things
simple, the time is represented as month of the year and the location is
represented as
1
a latitude (how far North or South we are with −90◦, 0◦, and 90◦ being the
South Pole, Equator, and North Pole, respectively).
0 10 111 7 212 8 30 9 41 10 25 11 36 12 Time (months) 74 Time (months) 58 69
A representative dataset is shown above left. There is no linear boundary
that would correctly split this dataset. However, we can recognize that there
are different areas of positive and negative space we wish to isolate, one such
division being shown above right. We accomplish this by partitioning the
input space X into disjoint subsets (or regions) Ri:
s.t. Ri ∩ Rj = ∅ for i 6= j
where n ∈ Z+.
2 Selecting Regions
In general, selecting optimal regions is intractable. Decision trees generate
an approximate solution via greedy, top-down, recursive partitioning. The
method is top-down because we start with the original input space X and
split it into two child regions by thresholding on a single feature. We then
take one of these child regions and can partition via a new threshold. We
continue the training of our model in a recursive manner, always selecting a
leaf node, a feature, and a threshold to form a new split. Formally, given a
parent region Rp, a feature index j, and a threshold t ∈ R, we obtain two child
regions R1 and R2 as follows:
R1 = {X | Xj < t,X ∈ Rp}
R2 = {X | Xj ≥ t,X ∈ Rp}
lOMoARcPSD| 70487227
Cs229 Decision trees notes
Decision Trees
We now turn our attention to decision trees, a simple yet flexible class of
algorithms. We will first consider the non-linear, region-based nature of
decision trees, continue on to define and contrast region-based loss
functions, and close off with an investigation of some of the specific
advantages and disadvantages of such methods. Once finished with their nuts
and bolts, we will move on to investigating different ensembling methods
through the lens of decision trees, due to their suitability for such techniques.
1 Non-linearity
Importantly, decision trees are one of the first inherently non-linear
machine learning techniques we will cover, as compared to methods such as
vanilla SVMs or GLMs. Formally, a method is linear if for an input x ∈ Rn (with
interecept term x0 = 1) it only produces hypothesis functions h of the form:
h(x) = θTx
where θ ∈ Rn. Hypothesis functions that cannot be reduced to the form
above are called non-linear, and if a method can produce non-linear
hypothesis functions then it is also non-linear. We have already seen that
kernelization of a linear method is one such method by which we can achieve
non-linear hypothesis functions, via a feature mapping φ(x).
Decision trees, on the other hand, can directly produce non-linear
hypothesis functions without the need for first coming up with an
appropriate feature mapping. As a motivating (and very Canadien) example,
let us say we want to build a classifier that, given a time and a location, can
, lOMoAR cPSD| 70487227
CS229 Fall 2
predict whether or not it would be possible to ski nearby. To keep things
simple, the time is represented as month of the year and the location is
represented as
1
a latitude (how far North or South we are with −90◦, 0◦, and 90◦ being the
South Pole, Equator, and North Pole, respectively).
0 10 111 7 212 8 30 9 41 10 25 11 36 12 Time (months) 74 Time (months) 58 69
A representative dataset is shown above left. There is no linear boundary
that would correctly split this dataset. However, we can recognize that there
are different areas of positive and negative space we wish to isolate, one such
division being shown above right. We accomplish this by partitioning the
input space X into disjoint subsets (or regions) Ri:
s.t. Ri ∩ Rj = ∅ for i 6= j
where n ∈ Z+.
2 Selecting Regions
In general, selecting optimal regions is intractable. Decision trees generate
an approximate solution via greedy, top-down, recursive partitioning. The
method is top-down because we start with the original input space X and
split it into two child regions by thresholding on a single feature. We then
take one of these child regions and can partition via a new threshold. We
continue the training of our model in a recursive manner, always selecting a
leaf node, a feature, and a threshold to form a new split. Formally, given a
parent region Rp, a feature index j, and a threshold t ∈ R, we obtain two child
regions R1 and R2 as follows:
R1 = {X | Xj < t,X ∈ Rp}
R2 = {X | Xj ≥ t,X ∈ Rp}
