This post will explore the mathematics behind information gain. We’ll start with the base intuition behind information gain, but then explain why it has the calculation that it does.
What is information gain?
Information gain is a measure frequently used in decision trees to determine which variable to split the input dataset on at each step in the tree. Before we formally define this measure we need to first understand the concept of entropy. Entropy measures the amount of information or uncertainty in a variable’s possible values.
How to calculate entropy
Entropy of a random variable X is given by the following formula:
-Σi[p(Xi) * log2(p(Xi))]
Here, each Xi represents each possible (ith) value of X. p(xi) is the probability of a particular (the ith) possible value of X.
Why is it calculated this way?
First, let’s build some intuition behind the entropy formula. The formula has several useful properties. For example, it’s always non-negative. Also, entropy as a function is monotonically decreasing in the probability, p. In other words, the amount of information about an event (or value) of X decreases as the probability of that event increases.
That may sound a little abstract at first, so let’s consider a specific example. Suppose you’re expecting how much a movie will make in revenue. One of your anticipators is a binary indicator – 1 if the record refers to a movie, and 0 otherwise. Well – that anticipator is useless! Mathematically speaking, it’s useless because every record in the dataset is a movie – so there’s a 100% probability of that event (i.e. the record being a movie) occurring. This means that the variable provides no real information about the data. The closer you get to a variable having a single possible value, the less information that single value gives you.
Why the log2? Technically, entropy can be calculated using a logarithm of a different base (e.g. natural log). However, it’s common to use base 2 because this returns a result in terms of bits. In this way, entropy can be thought of as the average number of bits needed to encode a value for a specific variable.
Information gain in the context of decision trees is the reduction in entropy when splitting on variable X. Let’s do an example to make this clear. In the below mini-dataset, the label we’re trying to anticipate is the type of fruit. This is based off the size, color, and shape variables.
Suppose we want to calculate the information gained if we select the color variable. 3 out of the 6 records are yellow, 2 are green, and 1 is red. Proportionally, the probability of a yellow fruit is 3 / 6 = 0.5; 2 / 6 = 0.333… for green, and 1 / 6 = 0.1666… for red. Using the formula from above, we can calculate it like this:
-([3/6 * log2(3/6)] + [2/6 * log2(2/6)] + [1/6 * log2(1/6)])
Likewise, we want to get the information gain for the size variable.
-([3/6 * log2(3/6)] + [2/6 * log2(2/6)] + [1/6 * log2(1/6)])
In this case, 3 / 6 of the fruits are medium-sized, 2 / 6 are small, 1 / 6 is big.
Lastly, we have the shape variable. Here, 5 / 6 of the fruits are round and 1 / 6 is thin.
-([5/6 * log2(5/6)] + [1/6 * log2(1/6)])
How to calculate information gain in R
So, how do we calculate information gain in R? Thankfully, this is fairly simple to do using the FSelector package:
info <- data.frame(fruits = c("watermelon", "apple", "banana", "grape", "grapefruit", "lemon"))
info$sizes <- c("big", "medium", "medium","small" ,"medium", "small")
info$colors <- c("green", "red", "yellow", "green", "yellow", "yellow")
info$shapes <- c("round", "round", "thin", "round", "round", "round")
# get information gain results
That’s all for now! Information gain is just one of many possible feature importance methods, and I’ll have more articles in the future to explore other possibilities. If you liked this post, please follow my blog on Twitter!.
Visit TheAutomatic.net to get additional insight on this topic: http://theautomatic.net/2020/02/18/how-is-information-gain-calculated/
Disclosure: Interactive Brokers
Information posted on IBKR Traders’ Insight that is provided by third-parties and not by Interactive Brokers does NOT constitute a recommendation by Interactive Brokers that you should contract for the services of that third party. Third-party participants who contribute to IBKR Traders’ Insight are independent of Interactive Brokers and Interactive Brokers does not make any representations or warranties concerning the services offered, their past or future performance, or the accuracy of the information provided by the third party. Past performance is no guarantee of future results.
This material is from TheAutomatic.net and is being posted with permission from TheAutomatic.net. The views expressed in this material are solely those of the author and/or TheAutomatic.net and IBKR is not endorsing or recommending any investment or trading discussed in the material. This material is not and should not be construed as an offer to sell or the solicitation of an offer to buy any security. To the extent that this material discusses general market activity, industry or sector trends or other broad based economic or political conditions, it should not be construed as research or investment advice. To the extent that it includes references to specific securities, commodities, currencies, or other instruments, those references do not constitute a recommendation to buy, sell or hold such security. This material does not and is not intended to take into account the particular financial conditions, investment objectives or requirements of individual customers. Before acting on this material, you should consider whether it is suitable for your particular circumstances and, as necessary, seek professional advice.
In accordance with EU regulation: The statements in this document shall not be considered as an objective or independent explanation of the matters. Please note that this document (a) has not been prepared in accordance with legal requirements designed to promote the independence of investment research, and (b) is not subject to any prohibition on dealing ahead of the dissemination or publication of investment research.
Any trading symbols displayed are for illustrative purposes only and are not intended to portray recommendations.