# Learning using decision trees

I have a quick question that I'm stumped on. This is about constructing a decision tree using information gain (entropy). Let's say we have a dataset with two input attributes such that the information gain at the root of the tree for both attributes is zero, but this tree is still a decision tree of depth two (so two questions must be asked) that is consistent with the data.

How would this be constructed? I don't understand how I can get to a deeper depth without knowing have any information gain...

Without looking at specifics, growing a tree using information gain is a greedy procedure and won't always get you to the smallest tree consistent with the data, even if one exists. If there are ties among attributes, you break them arbitrarily.

I will use the following formula for information gain:

$G(S,A)=E(S)-\sum_{u\epsilon Values(A)}\frac{|S_{u}|}{|S|}E(S_{u})$

$A$ is a candidate for the separation attribute, that can take values from the set $Values(A)$ , $S_{u}$ is the dataset entries such that $A=u$ and $E(X)$ is the information entropy , where $X$ is a (data)set.

If $E(S)$, the dataset entropy is zero, the information gain for all attributes will also be zero. However, this means that no decision process is required for this dataset, so we'll consider it a trivial case.

If we demand $E(S)$ to be nonzero, we have that : $|S| E(S) = \sum_{u\epsilon Values(A)} |S_{U}| E(S_{u})$

This equality tells us that if we separate the dataset with the attribute A, the entropy will be the same (therefore the information gain is 0). If this is true for all attribute, you should follow the algorithm when the information gains of 2 or more attributes are equal and choose one arbitrarily. It is possible that in the next step the information gain of an attribute will be non-zero, for example:

Assume that we have a dataset of 1000 people on whether or not they like going to the movies. We have recorded each person's age as young or old and its gender as either male or female. 800 people like going to the movies while 200 don't. Therefore, the initial entropy is $E(S) = 0.72$. If 80% of males and 80% of females do so, there is no information gain. Likewise for young and old people. We arbitrarily choose gender as the separating attribute. Now assume that for some reason, young males are more fond of going to the movies than older males, while the trend is reverse for females. In each respected subset of the original dataset, we will be able to use age to have non-zero information gain and thus give some meaning into continuing building the decision tree.

This applies for "vanilla" decision-tree building. The use of any number of attributes for separation could locate the pattern in the example in just one step. There is a variety of techniques for how you should separate the dataset, that have spanned from problems like this.