Information Gain

easyFREEDecision TreesMachine Learning 1

Compute the information gain from splitting a dataset.

Given a parent set of labels and the labels in two child subsets after a split, compute:

$IG = H(parent) - \frac{|left|}{|parent|} H(left) - \frac{|right|}{|parent|} H(right)$

where $H$ is the entropy: $H = -\sum_{k=1}^{K} p_k \log_2(p_k)$

Use $0 \log_2(0) = 0$ by convention. Return the information gain rounded to 4 decimal places.

Example

Input

parent = [1, 1, 0, 0]
left = [1, 1]
right = [0, 0]

Output

1.0

Reasoning

Inputs: parent holds the 4 class labels before the split (two 1s and two 0s); left and right are the two groups they were divided into, here [1, 1] and [0, 0].
Parent entropy: each class has proportion $p = \frac{2}{4} = \frac{1}{2}$ , so $H(parent) = -\left(\frac{1}{2}\log_2\frac{1}{2} + \frac{1}{2}\log_2\frac{1}{2}\right) = -\left(-\frac{1}{2} - \frac{1}{2}\right) = 1$ bit, the maximum for two classes.
Child entropies: each child is pure, so its only class has $p = 1$ and $H = -1 \cdot \log_2 1 = 0$ . Both $H(left)$ and $H(right)$ are $0$ .
Weighting: each child holds 2 of the 4 labels, so both weights are $\frac{2}{4} = 0.5$ . The weighted child entropy is $0.5 \cdot 0 + 0.5 \cdot 0 = 0$ .
Output: $IG = 1 - 0 = 1$ , shown rounded to 4 decimal places as 1.0.
Notice that a perfect split removes all of the parent's uncertainty. Splitting the same parent into $\{1, 0\}$ and $\{1, 0\}$ instead leaves each child at 1 bit, giving a gain of $0$ .

Constraints

parent, left, right are lists of class labels
left and right together form the parent
Return information gain rounded to 4 decimal places
Use log base 2

Learn this in

Mathematical FoundationsFoundations Decision TreesML Study Plan

More from Machine Learning 1

RBF Kernel Matrixhard Polynomial Kernelmedium Hinge Losseasy Linear Decision Boundaryeasy Gradient Boosting Residual Stephard

Concept primer

Background Knowledge

The concept of information gain is crucial in decision trees, as it helps determine the best split for a node. Information gain is calculated as the difference between the entropy of the parent node and the weighted sum of the entropy of the child nodes. Entropy, in this context, measures the amount of uncertainty or randomness in a dataset. The formula for entropy is given by $H = -\sum_{k=1}^{K} p_k \log_2(p_k)$ , where $p_k$ is the probability of each class label.

In the context of decision trees, the goal is to find the split that results in the highest information gain, which corresponds to the split that reduces the entropy the most. This is because a split with high information gain is one that effectively separates the classes, reducing the uncertainty or randomness in the child nodes. The information gain formula takes into account the size of the child nodes relative to the parent node, ensuring that the split is evaluated based on the proportion of samples in each child node.

The information gain calculation relies on the convention that $0 \log_2(0) = 0$ , which is necessary to handle cases where a child node has only one class label. This convention allows us to calculate the entropy of a node even when one or more class labels have a probability of zero.

Algorithm/Approach

The general approach to solving this problem involves calculating the entropy of the parent node and the child nodes, and then using these values to compute the information gain. This requires:

Calculating the probability of each class label in the parent and child nodes
Using these probabilities to calculate the entropy of each node
Applying the information gain formula to obtain the final result

Step-by-Step Strategy

To implement the solution, follow these steps:

Calculate the probability of each class label in the parent node and the child nodes.
Use these probabilities to calculate the entropy of the parent node and the child nodes using the formula $H = -\sum_{k=1}^{K} p_k \log_2(p_k)$ .
Apply the information gain formula: $IG = H(parent) - \frac{|left|}{|parent|} H(left) - \frac{|right|}{|parent|} H(right)$ .
Round the result to 4 decimal places.

Common Pitfalls

When implementing the solution, watch out for:

Forgetting to handle the case where $0 \log_2(0) = 0$
Incorrectly calculating the probabilities or entropy values
Failing to round the final result to 4 decimal places

Time & Space Complexity

The time complexity of the solution is expected to be O(n), where n is the total number of labels in the parent and child nodes, since we need to iterate over all labels to calculate the probabilities and entropy values. The space complexity is expected to be O(n) as well, as we need to store the probabilities and entropy values for each node. However, the actual complexity may vary depending on the specific implementation details.

solution.py

Python 3.13

Test results