Part 5

A complete tree repeats one small decision until a stopping rule fires.

This page turns information gain into an algorithm, traces a mixed-data loan prediction, derives class probabilities at leaves, and explains what the fitted model actually stores.

One node as an optimization problem

Node question

At a node containing only some training rows, what exactly is the algorithm optimizing?

Let \(Q_m\) be the rows reaching node \(m\). A numeric candidate \(\theta=(j,t)\) uses feature \(j\) and threshold \(t\):

\[ Q_m^{left}(\theta)=\{(x,y)\in Q_m:x_j\le t\} \]

\[ Q_m^{right}(\theta)=Q_m\setminus Q_m^{left}(\theta) \]

Intuition: a candidate is just one yes/no question and the two piles of rows created by its answer.

Score and choose the candidate

\[ G(Q_m,\theta)=\frac{n_L}{n_m}H(Q_L)+\frac{n_R}{n_m}H(Q_R) \]

\[ \theta^*=\arg\min_\theta G(Q_m,\theta) \]

Minimizing weighted child impurity is equivalent to maximizing information gain because the parent impurity is fixed while candidates at the same node are compared.

\[ \arg\max_\theta\left[H(Q_m)-G(Q_m,\theta)\right] =\arg\min_\theta G(Q_m,\theta) \]

Intuition: every candidate starts from the same parent, so the winner is simply the candidate leaving the cleanest children.

The recursive algorithm

Recursion question

After selecting a root split, do child nodes need a different learning algorithm?

grow(rows, depth): compute the node prediction and impurity if a stopping condition is true: return a leaf generate every valid question choose the question with maximum gain grow(left rows, depth + 1) grow(right rows, depth + 1) return the decision node

Intuition: each child receives fewer rows but solves the same problem: find the next question that most reduces local uncertainty.

Stopping cases

Stopping case	Why stop?	Leaf prediction
Pure node	No uncertainty remains.	The only class present.
Maximum depth	The allowed complexity has been reached.	Local majority class.
Too few samples	Further groups would be unreliable.	Local majority class.
No useful gain	No candidate meaningfully improves purity.	Local majority class.
No features/candidates	No valid question remains.	Local majority class.

A learned loan tree

One fully grown tree consistent with the tiny sample can reuse a numeric feature at different thresholds.

CreditScore ≤ 622.5? ├── yes → Decline └── no ├── LoanAmount > 32.5 → Decline └── LoanAmount ≤ 32.5 ├── CreditScore > 645 → Approve └── Income ≤ 31? ├── yes → Approve └── no → Decline

This is one possible fully grown tree; ties can produce an equivalent alternative structure.

Trace a new application

Prediction question

For CreditScore 680, LoanAmount ₹22L, and Income ₹55k/month, which path is followed?

\(680\le622.5\) is false, so move right.
\(22>32.5\) is false, so move toward the smaller-loan branch.
\(680>645\) is true, so reach the Approve leaf.

\[ \hat y=\text{Approve} \]

Intuition: entropy is used to train the questions. Prediction only follows the stored questions; it does not recalculate information gain.

Leaf probabilities

Confidence question

If a leaf contains 7 approvals and 2 declines, should it report 100% approval probability?

\[ \hat P(Y=k\mid x\in leaf\ m)=\frac{N_{mk}}{N_m} \]

\[ \hat P(Approve)=\frac{7}{9}\approx0.778,\qquad \hat P(Decline)=\frac{2}{9}\approx0.222 \]

Intuition: every row reaching the same leaf receives the same empirical class distribution.

Small leaves can produce extreme probabilities from very little evidence. Larger `min_samples_leaf`, ensembles, or probability calibration may improve reliability.

What the trained model stores

A fitted tree stores a hierarchy of nodes rather than one global coefficient vector.

Stored at a decision node	Stored at a leaf
Feature index, threshold, child pointers, sample count, impurity, class counts	Prediction, class counts or mean target, sample count, impurity

Prediction time is proportional to path length, approximately \(O(depth)\) per row for a balanced tree.

Ties and instability

Tie question

If two candidate questions have exactly the same gain, which one is correct?

Both are equally good according to the current criterion. An implementation uses a deterministic or randomized tie-breaking rule. Because the selected root changes all later subsets, a small data change can produce a visibly different tree.

Fix `random_state` for reproducibility where the implementation uses randomness, but remember that reproducibility does not remove statistical instability.