Decision trees, SVM and ensemble methods notes — Unit 3

A non-parametric supervised learning method used for both classification and regression. The goal is to create a model that predicts the value of a target variable by learning simple decision rules inferred from the data features.

⇒1.1 Structure

• Root Node: Represents the entire dataset, which is split into two or more homogeneous sets.
• Decision Node: A node that splits into further sub-nodes based on a condition (e.g., 'Age > 30?').
• Leaf Node: A terminal node that carries the final classification label (or regression value).

Decision trees are highly interpretable ('White Box' models). You can exactly trace why a prediction was made.

How does the tree decide which feature to split on first? It uses mathematical metrics to find the feature that best separates the classes.

⇒2.1 Entropy

A measure of impurity or randomness in a set of data. If a node has 50% cats and 50% dogs, Entropy is maximum (1.0). If a node has 100% cats, Entropy is minimum (0.0). The algorithm aims to reduce entropy.

⇒2.2 Information Gain

The difference in Entropy before and after the split. The algorithm calculates the Information Gain for every possible feature and chooses the feature that provides the highest gain for the split.

An alternative to Entropy, widely used by the CART (Classification and Regression Trees) algorithm.

⇒3.1 Gini Impurity

Measures the probability of incorrectly classifying a randomly chosen element from the dataset if it were randomly labeled according to the distribution of labels in the node.

Gini is computationally slightly faster than Entropy because it does not require calculating logarithms, though the resulting trees are often identical.

⇒3.2 The Overfitting Problem

If left unrestricted, a decision tree will grow until every leaf node has 100% purity (Entropy = 0). This results in a massive tree that perfectly memorizes the training data but fails on test data (Severe Overfitting). We solve this by Pruning (setting max depth, or requiring a minimum number of samples per leaf).

A powerful, mathematically rigorous algorithm for classification. Instead of just finding any line to separate two classes, SVM finds the best possible line.

⇒4.1 The Hyperplane and Margin

The separating line in N-dimensional space is called a Hyperplane. The 'Margin' is the distance between the Hyperplane and the closest data points of either class. SVM's entire goal is to maximize the margin.

⇒4.2 Support Vectors

The data points that lie exactly on the edge of the margin. They are called support vectors because they literally 'support' the margin. If you delete all other data points in the dataset, the SVM model will not change; only the support vectors matter.

What if the two classes are not linearly separable? (e.g., A cluster of red dots surrounded by a ring of blue dots). You cannot draw a straight line between them.

⇒5.1 Projecting into Higher Dimensions

SVM solves this by mapping the 2D data into 3D space (e.g., adding a Z-axis based on distance from center). In 3D space, the classes might become separable by a flat 2D plane. When projected back down to 2D, that flat plane becomes a perfect circular boundary.

⇒5.2 The Math (Kernel Trick)

Actually computing all those new dimensions is incredibly computationally expensive. The Kernel Trick is a mathematical shortcut that calculates the relationships between points in higher dimensions without ever explicitly computing the coordinates in that higher dimension.

The Wisdom of Crowds. Why rely on one model when you can train 100 models and have them vote on the answer? Ensemble methods combine multiple weak learners to create one strong learner.

⇒6.1 Bagging (Bootstrap Aggregating)

You take your training dataset and create 100 new mini-datasets by sampling with replacement. You train 100 separate models in parallel (usually Decision Trees), one on each mini-dataset. For a new prediction, all 100 models vote, and the majority wins.

Bagging massively reduces Variance (Overfitting). The most famous bagging algorithm is Random Forest.

Unlike Bagging which trains models in parallel independently, Boosting trains models sequentially, with each new model trying to correct the mistakes of the previous one.

⇒7.1 How it works

• 1. Train a weak model (like a tree with a depth of 1).
• 2. Identify which data points it got wrong.
• 3. Assign a higher 'weight' (importance) to those misclassified points.
• 4. Train the next model, forcing it to pay special attention to the highly weighted points.
• 5. Repeat.

Boosting reduces Bias (Underfitting). Famous examples include AdaBoost, Gradient Boosting, and XGBoost.