📘

Information Gain

EasyDecision Trees 📚 Machine 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:

First, we calculate the entropy of the parent set: $H(parent) = -\left(\frac{2}{4} \log_2\left(\frac{2}{4}\right) + \frac{2}{4} \log_2\left(\frac{2}{4}\right)\right) = -\left(\frac{1}{2} \log_2\left(\frac{1}{2}\right) + \frac{1}{2} \log_2\left(\frac{1}{2}\right)\right) = 1$
Then, we calculate the entropy of the left and right child sets: $H(left) = -\left(\frac{2}{2} \log_2\left(\frac{2}{2}\right)\right) = 0$ and $H(right) = -\left(\frac{2}{2} \log_2\left(\frac{2}{2}\right)\right) = 0$
Next, we apply the information gain formula: $IG = H(parent) - \frac{|left|}{|parent|} H(left) - \frac{|right|}{|parent|} H(right) = 1 - \frac{2}{4} \cdot 0 - \frac{2}{4} \cdot 0 = 1$
The final output is $1.0$ after rounding to 4 decimal places

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

More from Machine Learning 1

RBF Kernel MatrixHard Polynomial KernelMedium Hinge LossEasy Linear Decision BoundaryEasy Gradient Boosting Residual StepHard

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

0/0

Run code to see test results.