Decision Tree

First Principles Question

Which question, asked about your data, reduces your uncertainty the most?

The Core Idea

A decision tree greedily asks this question at every step. At each node, it tries every possible feature and threshold, picks the one that gives the highest information gain (or lowest Gini impurity), and splits the data. Repeat recursively until a stopping criterion is met.

The Math

Entropy:          H(S) = -Σ pᵢ·log₂(pᵢ)
Information Gain: IG = H(S) - Σ (|Sₐ|/|S|)·H(Sₐ)
Gini Impurity:    G = 1 - Σ pᵢ²

Split on the feature that maximizes IG (or minimizes G)

Key Hyperparameters

• max_depth — limits tree size, controls overfitting
• min_samples_leaf — minimum samples needed at a leaf
• criterion — entropy vs gini

Why Trees Overfit

An unpruned tree will keep splitting until every leaf is pure — it memorizes training data. This is exactly the problem Random Forest and Gradient Boosting Tree solve differently.

For Regression

Use MSE instead of entropy/Gini. Split to minimize variance in each child node.

Prerequisites

Information Theory · Probability & Distributions

Builds To

Random Forest · Gradient Boosting Tree

Content Ideas

Obsidian note: “Decision trees are just repeated questions about uncertainty. Here’s the math behind choosing the right question.” X post: “A decision tree is not magic. It just keeps asking: which question reduces my confusion the most? That question has a precise answer: entropy.” GitHub: ml-from-scratch — build a decision tree from scratch, visualize splits