Information gain of the root node Recently I saw this question and answer as attached in following image

Anyone can add details how this solution achieved?
 A: Assume you split based on minimizing the the (total) variance of the pieces. Let us sort the first feature values
$$
\begin{array}{cc}
 f_1: & 2 & 4 & 6 & 9 \\
 y:& 0 & 0 & 1 & 1
\end{array}
$$
Splitting based on $f_1 > 4$  leads to the partition $\{2,4\}$ and $\{6,9\}$. The function values over these pieces are $\{0,0\}$ and $\{1,1\}$. The empirical variance of $y$ over each piece is 0 (the function is constant over each piece.) Since zero is the smallest possible variance, this is definitely optimal. There could be other optimal splits though. We can check the other choices:

*

*Splitting based on $f_1 > 2$, we have a nonzero variance for the set $\{4,6,9\}$ since the values are $\{0,1,1\}$.

For $f_2$, again let us sort the values of the feature:
$$
\begin{array}{cc}
 f_1: & 2 & 3 & 6 & 7 \\
 y:& 0 & 1 & 1 & 0
\end{array}
$$

*

*The split $f_2 > 3$ gives the pieces with values $\{0,1\}$  and $\{1,0\}$, both having nonzero variance (the function is not constant).

*The split $f_2 > 6$ gives a piece with values $\{0,1,1\}$, again with nonzero variance.


Suppose instead of the variance, we split based on the "information gain" which in the context of decision trees usually means how much the entropy changes as a result of the split (conditional on the split). Assume that you put equal mass/weight ($=\frac14$) on all the data points, which is the default assumption. The entropy of $Y$ is ($Y$ takes two values, $0$ and $1$ with equal probability):
$$
H(Y) = -(p_0 \log p_0 + p_1 \log p_1) = -\Big(\frac12 \log_2 \frac12 +  \frac12 \log_2 \frac12\Big) = \log_2(2) = 1
$$
The entropy of $Y$ conditional on the split $f_1 > 4$ can be compute as follows:
Think of a new variable $X = $ indicator of the event $\{f_1 > 4\}$ so that $X = 1$ if $f_1 > 4$ and zero if $f_1 \le 4$. So what happens if we condition on $X=1$, that is, $\{f_1 > 4\}$? The response variable $Y$ will take values $1$ and $1$ with equal probability, that is, it takes value 1 with probability one (it becomes a constant random variable). Hence $H(Y \mid X = 1) = 0$. Similarly, you can argue that $H(Y \mid X = 0) = 0$. Thus,
\begin{align}
H(Y | X) &= H(Y | X = 0) P(X=0) + H(Y | X = 1) P(X=1)  \\
&=  H(Y | X = 0) \frac12 + H(Y | X = 1)\frac12 \\ &= 0.
\end{align}
So the information gain as the result of $f_1 > 4$ split is $H(Y) - H(Y|X) = 1$. For any the other split (like $f_2 > 6$) with indicator variable $X'$, $H(Y |X')$  is strictly bigger that zero since the underlying distributions after the split are not constant. Hence, $H(Y) - H(Y | X') < 1$. This shows that the most gain occurs for the split based on $f_1 > 4$. Note that this is similar to splitting based on the variance: you get the most reduction in variance for $f_1 > 4$ because things become constant after the split (can't get better than this).
Exercise. Let $X'$ be the indicator variable of the event $f_1 > 2$. Argue that $$H(Y \mid X' = 1) \approx 0.918, $$ and ... hence $H(Y\mid X') \approx 0.689$. (All entropies are in base 2.) Information gain in this case is $H(Y) - H(Y\mid X') \approx 0.311$.
