Decision Trees and Overfitting Management

Decision-Making and Machine Learning Models: When faced with a dataset, a machine learning engineer may not know which classifier is optimal. It often involves a process of "hit and trial."
The Paracetamol Analogy: Just as one might take paracetamol as a default treatment for a fever with high confidence it will work, the Random Forest is considered a default classifier that works well on a variety of different datasets.
Random Forest as an "Out of Shelf" Model: It is described as a model that can be taken "off the shelf" and used effectively with minimal specific knowledge of the problem initially. The building blocks of a Random Forest are Decision Trees.
Conceptual Overview: A Decision Tree is a flowchart-like structure used to approximate discrete-valued functions. It is represented as a series of if-then rules to enhance human readability.

Traversal Process: Instances are classified by sorting them down the tree from the root node to a leaf node.
Root Node: The top-level node where the first attribute test occurs. For example, in the tennis dataset, "Outlook" is the root node.
Internal Nodes: Every node that is not a leaf node specifies a test of a discrete-valued attribute of the instance.
Branches: Each branch descending from a node corresponds to one of the possible values for that attribute.
Leaf Nodes: These represent the final classification or label. In a classification tree, leaf nodes contain the prediction (e.g., "Yes" if tennis will be played, "No" if it will not).
- Paths: A prediction for a sunny day with normal humidity can be represented as: "If Outlook = Sunny AND Humidity = Normal, then Play Tennis = Yes."

Dataset Composition: This classic dataset contains 14 examples ( $n = 14$ ) with four features and one label.
Features and Cardinality:
- Outlook: Sunny, Overcast, Rain (3 possible values).
- Temperature: Hot, Mild, Cool (3 possible values).
- Humidity: High, Normal (2 possible values).
- Wind: Weak, Strong (2 possible values).
Label: Play Tennis (Yes/No).
Statistical Breakdown: In the provided 14-day data, 5 samples are negative ("No") and 9 samples are positive ("Yes").
Interpreting the Resulting Tree:
- If Outlook is Overcast, tennis is always played (Yes).
- If Outlook is Sunny, check Humidity. If Humidity is Normal, result is Yes; if High, result is No.
- If Outlook is Rain, check Wind. If Wind is Weak, result is Yes; if Strong, result is No.

The Concept of Confusion: A decision tree is built to minimize confusion regarding the label. If all 14 examples were positive, no tree would be needed. Confusion arises when labels are mixed.
Entropy ( $H$ ): A statistical property that measures the randomness or impurity in a dataset.
- Formula: $H(s) = -p_{+} \text{log}_2(p_{+}) - p_{-} \text{log}_2(p_{-})$
Entropy Thresholds:
- Maximum Entropy ( $1$ ): Occurs when the collection contains an equal number of positive and negative examples ( $50/50$ split).
- Minimum Entropy ( $0$ ): Occurs when all members of the dataset belong to the same class.
Entropy Calculation Example (Play Tennis):
- $p_{+} = \frac{9}{14}$
- $p_{-} = \frac{5}{14}$
- $H = -(\frac{9}{14}) \text{log}_2(\frac{9}{14}) - (\frac{5}{14}) \text{log}_2(\frac{5}{14}) = 0.94$
Information Gain ( $IG$ ): This measures how well a given attribute separates the training examples according to the target classification. It is the reduction in entropy caused by partitioning the examples according to an attribute.

Gini Impurity: An alternative measure to entropy that looks at the mixing of labels. The goal is to select attributes that lead to "pure" decisions.
Formula: $Gini(D) = 1 - \text{sum}(p_i^2)$ , where $p_i$ is the probability of an object being classified into a particular class.
Example Calculation for "Wind" Attribute:
- Total samples: $14$ .
- Weak Wind ( $8/14$ ): 2 No, 6 Yes. Gini = $1 - (\frac{6}{8})^2 - (\frac{2}{8})^2 = 0.375$ .
- Strong Wind ( $6/14$ ): 3 No, 3 Yes. Gini = $1 - (\frac{3}{6})^2 - (\frac{3}{6})^2 = 0.5$ .
- Weighted Gini for Wind: $(\frac{8}{14} \times 0.375) + (\frac{6}{14} \times 0.5) = 0.4286$ .
Selection Criteria: The attribute with the lowest weighted Gini impurity (or highest Gini Index/reduction) is chosen as the split node.

Definition: Overfitting occurs when a tree is grown to perfectly fit the training data, capturing noise or outliers rather than a general pattern.
Noisy Labels: A single incorrectly labeled example (e.g., a Sunny/Normal day labeled as "No") can force the tree to add unnecessary nodes, complicating the model.
Generalization vs. Memorization: The goal is to learn a general pattern (e.g., Attendance < 33 implies Fail) rather than simply "mugging up" the training data.
The Overfitting Graph: As the number of nodes increases, training accuracy continues to rise (potentially reaching $100\%$ ), while validation/test accuracy peaks and then drops.

Pruning Objective: To address the problem of overfitting by removing sections of the tree that provide little power to classify instances.
Pre-Pruning (Forward Pruning):
- Mechanism: Stops the tree growth before it becomes too complex.
- Constraints: Max depth limits, minimum sample split thresholds (e.g., "do not split if less than 10 samples are left"), or minimum samples at a leaf node.
- Trade-off: Can lead to underfitting if the thresholds are too strict.
Post-Pruning (Backward Pruning):
- Mechanism: Allows the tree to grow fully and then chops off subtrees starting from the bottom.
- Evaluation: Uses a validation set. If removing a subtree does not decrease validation accuracy, the subtree is replaced with a single leaf node representing the majority class of the removed samples.
- Pros/Cons: More computationally expensive and memory-intensive than pre-pruning but generally leads to better generalization.

On Feature Relationships: A student asked how a day can be "Sunny" but "Cool." The instructor explained that in European climates (e.g., London, Switzerland), a bright sunny morning can still be cold, unlike typical conditions in India.
On Gini vs. Entropy: The instructor clarified that Gini Impurity is like Entropy (measure of mixed labels), while Gini Index is like Information Gain (measure of reduction in impurity).
On Data Splitting: Machine learning involves splitting data into three parts: Training (to learn), Validation (internal testing/tuning), and Testing (final evaluation).
Industry and Research Discussion:
- AI Sovereignty: Discussion regarding the "BharatGen" project and indigenous LLM foundation models involving IIT Mandi faculty.
- AI in Agriculture: The instructor shared her work on AI models tailored for the Indian landscape to assist farmers.
- Banking Applications: A student from the banking sector inquired about sovereign AI models to avoid proprietary systems like Microsoft/OpenAI due to privacy and sovereignty concerns; the instructor recommended connecting on LinkedIn via "vidosha.in" for consultancy discussions.