Random Forests — An Intuitive Understanding

It is intriguing to see how simply and easily a Random Forest can yield extremely useful results. Random Forest is a Supervised Machine Learning algorithm. Examples of other supervised learning algorithms are Linear Regression, Logisitic Regression and Neural Networks.

Random Forests are essentially an ensemble of Decision Trees.

Decision trees are

• easy to create,
• easy to implement and
• easy to interpret

But in practice they don’t prove to be very useful. Nevertheless, to understand Random Forests one must know the basic intuition behind Decision Trees.

In its simplest form a Decision tree is a sequence of choices.

As far as accuracies of prediction go Decision Trees are quite inaccurate. Even one mis-step in the choice of the next node, can lead you to a completely different end. Choosing the right branch instead of the left could lead you to the furthest end of the tree. You would be off by a huge margin!

They work great with the data used to create them a.k.a The Training Set but the perform horribly with previously unseen data. This new data is generally called The Validation Set or The Test Set.

A huge number of decision trees created randomly using input data comprise the Random Forest. The randomness of creation combined with simplicity of a Decision Tree lends Random Forests their awesomness!

Random Forests = Simplicity of DT + Accuracy Through Randomness

Random forests (Breiman, 2001) were originally conceived as a method of combining several CART (Classification And Regression Trees) (Breiman et al.,1984) style decision trees using bagging (Breiman, 1996). In the years since their introduction, random forests have grown from a single algorithm to an entire framework of models (Criminisi et al., 2011), and have been applied to great effect in a wide variety of fields — Computer Vision, Medical Image Analysis, Drug Discovery, Chemoinformatics etc.

Without going into further praise of Random Forests let’s see how to deal with them

• How to build a RF?
• Why does it work?
• How to test a RF?

1) Building a Random Forest

Random Forest algorithm is a classifier based on primarily two methods. We will touch upon only the 1st method — Bagging.

• Bootstrapping/Bagging
• Random subspace method.

Step 1 —Bootstrapping /Bagging— To begin building a random forest we need to first create “Bootstrapped Datasets” from our original dataset. Bootstrapping is a statistical technique to pick up samples randomly from our dataset. In doing so we are allowed to pick up the same sample twice or even thrice or any number of times. In Statistical Jargon it’s known as Sampling with replacement.

Generally if there are S number of trees in the Random Forest we create S Bootstrapped Datasets.

Example

Let’s say we have Olympics 2020 coming up. Our Random Forest has to predict whether a player will win a medal this year or not. It takes the following 4 variables into account

1. Has the player won Gold Medal previously?
2. Has the player had any recent injury?
3. Is there sponsorship available for the player?
4. Player’s current world rank.

Also, for example’s sake let’s consider our dataset has only 4 players. Each row is a record/datapoint. So we already know that player with the ranks 49 and 50 player are predicted to not win any medals. Just the players with rank 2 and 7 are predicted to win.

Now let’s create the bootstrapped dataset as step 1 of understanding what Random Forests are!

Let’s begin by choosing one row from the above table randomly. We end up picking row 4. It goes as row/record 1 in the Bootstrapped Table.

Next we pick row 1 from the original table. Note that bootstrapped dataset has the same number of datapoints/rows as the original dataset.

2 more samples later we have our bootstrapped dataset. Note that row 1 is picked twice randomly (it goes as row 2 and 4 in the bootstrapped table) and row 2 is never picked!!

Step 2 —Create a Decision Tree — Once we have a bootstrapped dataset we create a decision tree from it. Remember the most important thing while creating a decision tree is to know which is the best question to ask. As explained in the Decision Tree article Gini Impurity gives a measure of which question separates the data best.

• Select a random subset (=say 2) of the 4 variables (Previous Gold, Injury, Sponsorship status and world ranking) as candidates for the root node.
• Compute the Gini Impurity and figure out the best candidate out of the 2. i.e. which candidate best separates the data.
• For the next node again select a random subset of the remaining 3 variables and repeat the process until no more variables are left. In jargon terms, this is called picking a random subset.

Step 3 — Rinse and Repeat — Once you have 1 decision tree start the whole iteration all over again. Create a new bootstrapped dataset and considering only a subset of variables at each step you can come up with a wide variety of Decision Trees. Keep repeating steps 1 and 2. Ideally you would need 100s of trees but for representation purpose we just show 6 trees below. Note each tree comes from a different bootstrapped dataset.

• This randomness in the tree creation process is what lends flexibility and high accuracy to Random Forest

2) Why does it work?

Consider a company that is hiring for the position of CTO. A few people are assigned the role of interviewing the candidates, according to their own strengths.

• CEO — Judges the leadership qualities
• Tech. Director — Judges the technological awareness
• HR Director — Judges the personality and cultural fit
• Board Members — Judge the managerial qualities
• A few star employees — Judge depth of knowledge in specific segments

Each of these interviewers have their own strengths that they have acquired over many years of experience. But these strengths also become biases! Each interviewer is poised to choose a candidate who’s strong in their own expertise area.

If it were upto just the Star Employees they would end up hiring a CTO who works great as an independent contributor but might not a be a visionary leader (which was CEOs role to judge).

Random Forest works similarly. Each tree is an interviewer. Each tree is biased to give results favouring a particular variable. Their combined results although come out to be pretty accurate. The whole company is the Random Forest and churns out more accurate results than an average employee a.k.a Decision Tree

Going with the example Dataset used before. Let’s say a new player registers for the race. His variables are as follows:

• Previous Gold Winner : No
• Any Recent Injury : No
• Sponsorship Available : No
• World Ranking : 7

The question is Will the player win a medal in this race?

Let’s see how and what does the Random Forest predict?

The process given above is called Bagging

Bootstrapping the data & using an aggregate of ‘individual results’ to obtain the ‘final result’ is called Bagging

3) How do we test the Random Forest?

How do we know if the results that our random forest gives us are correct? How do we trust and test it?

We use a subset of our original data to check if the Random Forest’s predictions match with the actual data.

In most Machine Learning algorithms we divide our whole dataset into Training Set(90%) and Test Set(10%). The models are trained on Training Data and the Test Data is never shown to these models. Once trained the real accuracy of any model is shown through the Test Set/Test Data.

Trivia

In a lot of cases we also use Validation Set. This is used to fine tune the parameters of the model once it is trained. The split in this case generally is Training Set— 60% Validation Set — 20% Test Set — 20%

In Random Forest we don’t need to set aside some data for test set. Due to bootstrapping we automatically get a subset of original data that can be used for testing!

Remember, while creating the bootstrapped dataset some rows are never chosen! They are left out because during the bootstrapping process we sample with replacement. We let the same data point be included multiple times. E.g. We let row 1 be included twice in the bootstrapped dataset. That resulted in row 3 being left out completely from the bootstrapped dataset. This left out data forms our test set. And it has a special name too— Out-Of-Bag-Dataset

Each bootstrap sample leaves out about 37% of the examples — Leo Breiman

A study by Leo Breiman, a distinguished statistician at the University of California, Berkeley, proved that the out-of-bag estimate is as accurate as using a test set of the same size as the training set. Therefore, using the out-of-bag error estimate removes the need for a set aside test set.

• These left-out rows in our original dataset form the “Out-Of-Bag-Dataset”.
• Since we already know the prediction output of the Out-Of-Bag-Data we can run it through our Random Forest and See how many examples are predicted correctly.

Testing the RF

Let’s say

• The total number of datapoints in our original dataset = N
• Number of points in Bootstrapped Dataset = N
• Number of unique points in Bootstrapped Dataset = 70% of N (assume the rest 30% is repeated, the actual statistic is most often close to 37%)

Therefore, the size of Out-Of-Bag-Dataset = 30% of N. Let’s call this quantity M.

Now the procedure for testing the accuracy of our Random Forest is as follows:

• Run each of these M datapoints through our Random Forest.
• Subject them to the same kind of Bagging process as shown above.
• For each data point the Random Forest will predict the result based on majority voting of the trees.
• Let’s say No. of mistakes that our random forest makes = C
• So the number of correct predictions = M-C
• Therefore, accuracy % of our Random Forest = 100*(M-C)/M

As an example let’s say our original data had 15 samples. So N = 15. Therefore M = 5. Let’s say number of mistakes C = 1.

=> Accuracy = 100*(5–1)/5 = 80%

C being the number of mistakes our Random Forest makes on the Out-Of-Bag-Dataset is called the Out-Of-Bag-Error.

As an example Out-Of-Bag-Dataset has 5 data rows. For each of those random forest predicts. At the end we calculate the accuracy of the Random Forest.

TL;DR

Random Forests algorithm is a classifier based on primarily two methods -

• Bagging
• Random subspace method.

We explain the bagging method in this article and show how to compute a Random Forest’s accuracy.

Suppose we decide to have S number of trees in our forest then we first create S datasets of "same size as original" created from random resampling of data in T with-replacement (n times for each dataset). This will result in {T1, T2, ... TS} datasets. Each of these is called a bootstrap dataset. Due to "with-replacement" every dataset Ti can have duplicate data records and Ti can be missing several data records from original datasets. This is called Bootstrapping.

After creating the classifiers (S trees), for each (Xi,yi) in the original training set i.e. T, select all Tk which does not include (Xi,yi). This subset, pay attention, is a set of boostrap datasets which does not contain a particular record from the original dataset. This set is called out-of-bag examples.

— StackOverFlow

References

• http://proceedings.mlr.press/v32/denil14.pdf
• https://www.youtube.com/watch?v=J4Wdy0Wc_xQ
• https://stackoverflow.com/users/83602/manoj-awasthi

X8 aims to organize and build a community for AI that not only is open source but also looks at the ethical and political aspects of it. More such simplified AI concepts will follow. If you liked this or have some feedback or follow-up questions please comment below.

Thanks for Reading!