Decision Trees
A recap of Andrew Ng course (Machine Learning Specialization) on Coursera
Course 2 Week 4
Processes to build a decision tree
Given a training set of 10 examples of cats and dogs, the first step is to decide what feature to use as the root node, for example, ear shape. we separate the 10 examples based on the ear shape.
The second step is focusing just on the left part (aka left branch of the decision tree) to decide what node to put there (what feature to use to make the next split for the left brach examples). For example, we pick face shape.
Finally, all the left examples after the second split are all cats, so rather than splitting further, we create a leaf node that makes a prediction that things that get down to that node are cats.
For the right examples after the second split, we also notice that the example is dog, so we can also stop splitting.
Next, we move on to the right branch, we need to pick some features to split the five examples. For example, whiskers are present or absent. After the split, we notice that each of the leaf node is “pure”, meaning that the nodes are all cats or all not cats. We can stop splitting and make predictions.
This is the process of building decision trees. There are several key decisions
- How to choose what feature to split on at each node?
We split by choosing a feature that maximizes purity, by which means that the subsets are as close as possible to all cats or all dogs. The cat DNA feature would be the best feature because it gives highest purity. But since we don’t have a DNA feature in our dataset, the decision tree model has to choose between ear shape, face shape, and whiskers, which of these features result in the greatest purity of the labels on the left and right sub-branches. Because with the subset that has the highest purity, we could either predict cat or not cat and get high accuracy. We will learn how to estimate impurity using entropy.
2. The second key decision we need to learn to make is when to stop splitting
The criteria we used in the simple example above is when the subset reaches 100% cats or dogs. Alternatively, we can also decide to stop splitting when splitting a node further will result in the tree exceeding the maximum depth, which is a parameter we can choose. The third option is to stop splitting if splitting the nodes result in minimum improvements (we can set threshold to this) to purity, or actually decreases in impurity but the gains are too small then we might not bother. The last option is if the number of examples at a node is below a certain threshold, then we might also decide to stop splitting. We stop splitting to keep the tree small and prevent from overfitting.
All these different criteria and key decisions to make may seem complicated and messy but all these different pieces fit together into a very effective learning algorithm which is a very popular and powerful model widely used in real-world scenarios.
Entropy: measurement of impurity of a data
Let’s say we have a data set with 3 cats and 3 dogs. We define p1 as the fraction of examples that are cats or the fraction of the positive examples. Next, we can plot entropy as a function of p1, H(p1), which measures impurity. If the split results in all cats or all dogs, the impurity should be 0. Therefore, if the split is 50% cats and 50% dogs, the impurity should be the highest, equals to 1.
Another way to look at entropy is probability of an event.
(When the entropy equals to 1, it means that the probability of event is 0.5) The probability of the event happening is totally predictable. Thus, the entropy shows the degree of predictability of an event.
Equation of H(p1):
Get Aimyo’s stories in your inbox
Join Medium for free to get updates from this writer.
We have a new variable p0 which stands for the fraction of the examples that are not cat. The entropy function is defined as show below. By convention, when computing entropy, we take logs to base 2 rather than to base e (natural logarithms). The reason we take logs to base 2 is to make the peak of the entropy curve equal to one.
Note: log of 0 is undefined (negative infinity), but by convention when calculating entropy, we will take log of 0 equal to 0.
Note: In open source packages, we may also hear about Gini criteria, which is another function that looks a lot like the entropy function. Entropy usually works well for most of the cases.
Choosing a split: information gain
In decision tree learning, the reduction of entropy (reduction of impurity) is called information gain.
In the following examples, we calculate the entropy of each sub-branches for all the features available for us to split on. Rather than looking at these entropy numbers and comparing which one is lowest, it would be useful to take a weighted average of them.
For example, if there is a node with a lot of examples in it, with high entropy, that seems worse than if there was a node with just a few examples in it with high entropy. Entropy is worse if you have a very large and impure dataset compared to just a few examples in a branch of a tree that is very impure. So the key decision in the picture above is, of these three possible choices of features to use at the root node, which one do we want to use.
Associated with each split is two numbers, the entropy of the left and right sub branches. In order to compare, we will combine these two numbers into just one number by taking weighted average. Because if there are more examples pushed into the left subbranch, then it is more important to make sure the left subbranch has low entropy. We will pick the split that gives us the lowest weighted entropy.
A further step for the convention of decision tree is, instead of calculating the weighted entropy, we calculate the reduction of entropy compared to if we hadn’t split at all. So, we need to go back to the root node and calculate the entropy there. We then substract the weighted entropy from the root node entropy to get information gain. If the information gain is too small, then we don’t bother making this new split which will make the tree more complicated.
Finally, since the information gain for the ear shape split is the largest, we pick that split.
Formal definition of information gain
We introduce a new variable to represent the fraction of total examples that went to the sub-branch, W-left and W-right.
Formal Decision Tree Process:
After finding the feature to split the root node, we move on to the next node (either the left sub-branch or the right sub-branch), and we now do the same process as if we were splitting the root node, which means this algorithm is a recursive algorithm. Recursion in computer science refers to writing code that calls itself, and the way this comes up in building a decision tree is you build the overall decision tree by building smaller sub-decision trees and then putting them all together.
How to choose maximum depth:
One intuition is the larger the maximum depth, the bigger the decision tree you’re willing to build, which is like fitting a higher degree polynomial or training a larger neural network
How to split on continuous variable:
We pick threshold to split the examples. One convention is to sort all of the examples according to the value on the feature and take all the values that are the midpoints between the sorted examples as the values for consideration for the threshold. This way, if we have 10 examples, we need to try 9 different split and pick the threshold that gives us the highest information gain.
Regression with Decision Trees:
If we need to predict the weight of the animals instead of predicting whether it is a cat or not a cat, we can still create the tree in the same way but when creating the leaf node, we can take the average of the weights from all the animals in the leaf node. This will be the prediction for new cases.
The only difference is that when we are choosing a split, we don’t use entropy, we now measure the variance of the weights for the animals in the leaf node. We also need to take the weighted average of the variances from the left and right branches and then pick the split that gives us the lowest weighted variance. Similar to the information gain, we also need to measure the reduction of variance and pick the split that has the highest reduction in variance.
