Consider a binary classification problem with 29 positve labels and 35 negative. You are building a decision tree and are trying to figure out whether to split on feature A1 or A2. Given the following information, which feature is the better choice?  You should calculate IG as an exercise.


University of Michigan - Ann Arbor


We define information gain as $$IG(X,Y) = H(Y) - H(Y\mid X)$$. 

We interpret information gain as the amount of information we learn about the label $$Y$$, given a specific feature $$X$$. 

Note that if the feature $$X$$ is completely uncorrelated with the label $$Y$$, then $$H(Y\mid X) = H(Y)$$. Therefore $$IG(X,Y) = 0$$. 

As such when we choose the next feature to split on we should choose the one that maximizes information gained. 


Information Gain

https://github.com/eecs445-f16/umich-eecs445-f16/blob/master/lecture11_info-theory-decision-trees/lecture11_info-theory-decision-trees.pdf

Open Source EECS 445 Slides from 2016

How should we split?

Information Gain tries to split trees on the basis of the most relevant feature X, however it does NOT take into account the number of values that X can take. If a feature A has a higher information gain and can take multiple distinct values that can exactly span the testing data, it can lead to overfitting. 

Learn Before

Related