==============================================================================================
RAHUL'S ML BLOG -- notes on machine learning, worked out by hand est. 2026
==============================================================================================
home | about | archive | glossary | contact
----------------------------------------------------------------------------------------------
CHAPTER 5 . QUESTION CHARTS AND COMMITTEES . PART 2 OF 3
The Mixing Ruler: Gini, Information Gain, and Pruning
============================================================================================
A question chart is a stack of yes/no questions.
A patient walks them top to bottom and lands in a final pile (a leaf), where the guess waits.
The chart is built by splitting the crowd into ever-cleaner piles.
At each split the chart scores every possible cut by a BADNESS number and keeps the smallest.
For a NUMBER answer the badness was the sum of squared misses around each pile's mean.
(miss = answer minus the pile mean; square each, add them up.)
That made sense because a number can be averaged.
Now the answer is yes/no -- sick or well, 0 or 1.
Therefore averaging stops making sense.
You cannot take the mean of {yes, yes, no}.
So the badness ruler must change.
The new ruler counts how MIXED each side is -- how many yes vs how many no.
Then the chart picks the cut that leaves the sides LEAST mixed.
That ruler is Gini impurity.
This post derives Gini by hand from four counts.
The second half of this post solves a different problem.
Even a good tree grows too bushy and memorises noise.
Pruning snips the weak branches after the fact.
An alpha tax (a charge per leaf) decides which branches to fire.
You are choosing which yes/no question to split 20 patients on. Two candidates,
and both cut the pile clean in half:
Question A Question B
---------- ----------
[10 sick, 10 well] [20 sick, 0 well]
[10 sick, 10 well] [ 0 sick, 20 well]
Both look "balanced." But A's two halves are each as muddled as the pile you
began with -- it learned nothing. B's halves are clean: ask the question and you
KNOW the answer. Same split size, opposite worth. Counting heads per side cannot
tell them apart, so you need a number for how MIXED each bucket is.
That number is Gini impurity: a bucket that is all one kind scores 0, a 50/50
bucket scores 0.5.
A: 0.5 and 0.5 -> total left = 0.5 (no gain over the start)
B: 0.0 and 0.0 -> total left = 0.0 (solved)
Pick the question that leaves the lowest impurity behind, and the useless split
is punished while the clean one wins -- automatically, by arithmetic.
CLASSIFICATION TREE: ONE CHANGE AT THE BOTTOM
The build hunt is the SAME shape as for a number answer.
Sort each column, try every midpoint as a cut, score each cut's badness, keep the smallest.
That smallest-badness cut is the column's champion.
Race the column champions; the best of them is the champion of champions -- this room's question.
Then recurse into each new pile.
Two tiny things change:
NUMBER tree (Part 1):
each final pile -> AVERAGE of the answers -> one number guess
badness = sum of squared misses around that average
YES/NO tree (this post):
each final pile -> MAJORITY vote -> a bin (yes or no)
badness = how MIXED each side is (Gini)
same hunt, same recursion
only the "ruler for badness" and the "guess at the bottom" differ
FROM 4 COUNTS TO 1 NUMBER: THE GINI RULER
At the first pairwise midpoint from the sorted column, draw a line:
below: 3 yes, 1 no (4 people)
above: 1 yes, 4 no (5 people)
----------
9 people total. 4 counts. that's ALL you need.
First, write each count as a fraction (the "share"):
below: yes = 3 out of 4 = 3/4 . no = 1 out of 4 = 1/4
above: yes = 1 out of 5 = 1/5 . no = 4 out of 5 = 4/5
Then compute each side's mixed-ness.
Each side: "how likely are two random grabs to DISAGREE?"
mixed-ness = 1 - (share_yes)^2 - (share_no)^2
all match match
For the BELOW side (4 people: 3 yes, 1 no):
share_yes = 3/4 . squared = 3/4 * 3/4 = (3*3)/(4*4) = 9/16
share_no = 1/4 . squared = 1/4 * 1/4 = (1*1)/(4*4) = 1/16
match = 9/16 + 1/16 = 10/16 = 5/8
differ = 1 - 5/8 = 3/8 = 0.375
(By pencil: split 8 into 8 eighths. 5/8 match, so 3/8 differ.)
For the ABOVE side (5 people: 1 yes, 4 no):
share_yes = 1/5 . squared = 1/5 * 1/5 = (1*1)/(5*5) = 1/25
share_no = 4/5 . squared = 4/5 * 4/5 = (4*4)/(5*5) = 16/25
match = 1/25 + 16/25 = 17/25
differ = 1 - 17/25 = 8/25 = 0.32
(25/25 - 17/25 = 8/25. 8 / 25 = 0.32, since 25 * 0.32 = 8.)
Then combine the two sides into one badness number.
Weight each side by how many people are on it.
below has 4 people out of 9 total -> weight = 4/9
above has 5 people out of 9 total -> weight = 5/9
cut badness = (4/9)*(3/8) + (5/9)*(8/25)
First term: 4/9 * 3/8 = (4*3)/(9*8) = 12/72 = 1/6
Second term: 5/9 * 8/25 = (5*8)/(9*25) = 40/225 = 8/45
Add: 1/6 + 8/45
= 15/90 + 16/90 (common denominator: 90. 1/6=15/90, 8/45=16/90)
= 31/90 ~ 0.344
There it is. 4 counts -> one number (0.344) for this cut.
A different side holds 2 yes and 3 no (made-up). Work its Gini on the slate.
check your slate: shares -- yes 2/5 = 0.4, no 3/5 = 0.6; Gini = 1 - 0.4^2 -
0.6^2 = 1 - 0.16 - 0.36 = 0.48. Close to the half-half worst of 0.5 -- this
side is badly mixed, a poor place to stop.
pure side (all yes): 0 <- can't be cleaner
half-half: 0.5 <- worst possible
this cut: 0.344 <- somewhere in between
each Gini costs only a handful of strokes.
but the hunt is wide.
330 cuts x 10 columns = 3,300 Gini numbers at THIS node (room) alone.
and a tree grows many rooms.
so the clerk-work stacks up fast as the chart deepens.
each of the 330 cuts in a column -> one Gini number.
smallest Gini in that column = the column's champion (its cleanest split).
A REAL CANCER CUT: RADIUS AND TEXTURE
The earlier example used abstract "yes" and "no."
Here is the same ruler tied to the actual cancer sheet the lab works with.
Four lumps, two measurements (radius and texture), one answer:
lump radius texture answer
---------------------------------
p1 15 0.20 sick
p2 8 0.10 well
p3 22 0.30 sick
p4 10 0.15 well
The tree looks for the cleanest cut. Try radius first.
Cut radius > 12:
Below: p2(well), p4(well) -> pure well -> GINI = 0 (weight 2/4)
Above: p1(sick), p3(sick) -> pure sick -> GINI = 0 (weight 2/4)
Weighted GINI = 0.5 x 0 + 0.5 x 0 = 0 <- perfect, no mixing left
Cut radius > 15:
Below: p2(well), p4(well), p1(sick) -> 1 sick, 2 well
share_sick = 1/3, share_well = 2/3
GINI = 1 - (1/3)^2 - (2/3)^2 = 1 - 1/9 - 4/9 = 4/9 ~ 0.444
Weight = 3/4 = 0.75
Above: p3(sick) -> pure sick -> GINI = 0 (weight 1/4)
Weighted GINI = 0.75 x 0.444 + 0.25 x 0 = 0.333
Champion for radius: cut > 12, weighted GINI = 0 (perfectly clean).
Now try texture.
Cut texture > 0.12:
Below: p2(well) -> pure well -> GINI = 0 (weight 1/4)
Above: p1(sick), p3(sick), p4(well) -> 2 sick, 1 well
share_sick = 2/3, share_well = 1/3
GINI = 1 - (2/3)^2 - (1/3)^2 = 1 - 4/9 - 1/9 = 4/9 ~ 0.444
Weight = 3/4 = 0.75
Weighted GINI = 0.25 x 0 + 0.75 x 0.444 = 0.333
Champion of champions:
column cut weighted GINI
---------------------------------
radius > 12 0 <- champion
texture > 0.12 0.333
First question: "radius > 12?"
Which gives pure sick piles and pure well piles.
Then each pure pile stops, because GINI = 0 means nothing is left to clean.
The abstract "3 yes, 1 no" from earlier is the same math.
It is just wrapped in real column names from the cancer lab the machine actually touches.
IN HAND so far: a cut turned 4 counts into one mixed-ness number.
Below side 3 yes 1 no gave 0.375.
Above side 1 yes 4 no gave 0.32.
Weighted together they gave 0.344.
On this ruler 0 is pure (no mixing) and 0.5 is half-half (worst mixing).
This section shows that the formula 1 - p^2 - q^2 is no magic spell.
(p = share of yes, q = share of no, on one side.)
A cut drops the parent's mixing from 0.48 down to a weighted-children 0.30 (both
made-up). How much did the cut buy -- its information gain?
check your slate: gain = parent Gini - weighted child Gini = 0.48 - 0.30 = 0.18.
A positive gain means the cut left the two sides cleaner than the parent; the
champion cut is the one with the biggest gain.
WHY THAT FORMULA IS NOT ASTROLOGY
The formula 1 - p^2 - q^2 looks pulled from thin air.
It isn't.
It counts something you can see with your hands.
(p = share of yes, q = share of no, on one side.)
Gini = the chance two random grabs from a side DISAGREE.
Use the below side: 3 yes, 1 no (4 people).
Reach into the pile, grab one person, write down yes or no.
PUT THEM BACK.
Grab another.
Chance BOTH yes?
first grab: "3 out of 4 are yes" -> 3/4 chance
second grab: same pile (you put the first back), same odds -> 3/4
"OF" means MULTIPLY. Three-quarters OF three-quarters:
3/4 * 3/4 = (3*3)/(4*4) = 9/16
Why multiply? Because you need BOTH events to happen.
"both yes" = "first yes AND second yes" = multiply the fractions.
(By pencil: 3/4 of 3/4 is 9/16 of the whole. You can draw a 4-by-4
grid, shade 3 across and 3 down -- 9 shaded squares out of 16.)
Chance BOTH no?
1/4 * 1/4 = 1/16
Chance they MATCH (both-yes OR both-no)?
"OR" means ADD. 9/16 + 1/16 = 10/16 = 5/8
Chance they DIFFER (don't match)?
1 - 5/8 = 3/8 = 0.375
That 0.375 is the Gini for this side.
No formula pulled from thin air.
Just counting what happens when you grab two people from the pile.
Check the edges:
pure side (all yes): 4 yes, 0 no
both yes = 4/4 * 4/4 = 1. both no = 0. match = 1. differ = 0. OK.
half-half: 2 yes, 2 no
both yes = 2/4 * 2/4 = 4/16. both no = 2/4 * 2/4 = 4/16. match = 8/16 = 1/2.
differ = 1 - 1/2 = 1/2 = 0.5. OK.
Gini is the DEFAULT ruler because it is fast -- no logarithms, just multiply and subtract.
The other option is entropy (also called cross-entropy).
Entropy uses a log instead of squares.
Entropy often gives the same champion as Gini.
But a log is slow to compute.
So sklearn's default is criterion='gini' for speed.
(criterion = which mixing ruler the tree scores cuts with.)
criterion='gini' -> 1 - p^2 - q^2 fast (multiply and subtract)
criterion='entropy' -> -p log p - q log q slow (log is expensive)
INFORMATION GAIN: THE DROP
Information gain = how much a cut DROPS the mixing from parent to children.
(parent = the room before the cut; children = the two piles after it.)
gain = Gini(parent) - weighted_Gini(children)
parent: whole pile, Gini = 0.49
after cut: left 0.375, right 0.32, weighted = 0.344
gain = 0.49 - 0.344 = 0.146
Higher gain = cleaner split.
The champion is the cut with the HIGHEST gain.
That is the same as picking the LOWEST weighted Gini.
It is just measured from the other direction.
STRATIFY: KEEP THE MIX EVEN
The cancer sheet is ~63% well, ~37% sick.
A plain random split might deal 71% well into the exam pile by luck.
Which is unfair -- the exam pile no longer looks like the whole sheet.
stratify=y_cls forces both piles to mirror the whole sheet's ratio.
(stratify = split each class separately so the ratio is preserved.)
plain split (luck): stratify split (forced):
study 60% well study 63% well <- same as whole
exam 71% well <- skewed exam 63% well <- same as whole
One flag in the split call.
No new idea -- just insurance against a lopsided deal.
PRUNING: THE ALPHA TAX
A full-grown tree memorises every quirk.
Which means its exam error is high.
One fix is to cap depth -- but a depth cap is a blunt ceiling, the same haircut everywhere.
Pruning instead SNIPS weak branches after the tree is fully grown.
The idea: charge a TAX per end-room (leaf).
A leaf = a final pile at the bottom of the tree, where a guess sits.
A branch survives only if the wrongness it removes is worth more than the tax:
chart's total cost = (total wrongness on study people) + alpha x (number of leaves)
+-- fit the data ---+ +--- stay humble ---+
alpha = 0 -> leaves are FREE -> keep all -> overgrown, memorises
alpha small -> cheap -> snip only the weakest twigs
alpha big -> leaves expensive -> snip hard -> down toward a stump
a doctor splits a room into 2:
wrongness dropped by 5400? tax for +1 room = alpha
if 5400 > alpha -> keep the doctor (earns its keep)
if 5400 < alpha -> FIRE him, merge rooms back (not worth the tax)
THIS ALPHA IS ADDED ON, NOT A DENOMINATOR
A straight-stick rule called Ridge also had an alpha.
Ridge guesses by a weighted sum, one dial (multiplier) per column.
Ridge's alpha sat in the BOTTOM of a fraction, roughly dial = top / (bottom + alpha).
So a bigger Ridge alpha squeezed every dial toward zero.
Here alpha is ADDED instead -- a flat tax per leaf.
So a bigger alpha here snips whole branches off.
Same letter, opposite machinery.
One shrinks a number; the other deletes a room.
Do not carry the denominator picture across.
As the tax climbs, the leaf count drops.
MAX_DEPTH IS A CEILING; CCP_ALPHA IS A TAX
max_depth: chops ALL corridors at height N. blunt, same haircut everywhere.
ccp_alpha: snips weak twigs ANYWHERE, keeps strong deep branches. smart, uneven.
WHERE DOES THE ALPHA MENU COME FROM?
You do NOT guess random alpha values. The tree hands you the exact list of alphas
where a branch would snip:
cost_complexity_pruning_path(X_train, y_train) -> ccp_alphas
[0.0, 12.5, 80.0, ..., 1755] <- the staircase of snip-points
Between these alphas, nothing changes. The tree pre-computes them.
CCP_ALPHAS (THE LIST) vs CCP_ALPHA (THE KNOB)
ccp_alphas = a list the machine hands you (all the meaningful snip-points)
ccp_alpha = a single knob you set on a new tree ("how hard to prune")
Plural = the menu. Singular = the setting.
A REAL alpha menu from the diabetes tree:
alpha what it does leaves left
-------------------------------------------------------------
0.0 no snips, full-grown tree 331 leaves
12.5 snipped 1 twig (drop < 12.5) 330
80.0 a whole weak branch collapses 310
204.7 another branch, ~20 leaves gone 290
550.0 half the tree gone 160
1755.0 everything collapsed to a stump 1
Each alpha is ONE branch's saved-mess. The tree pre-computes them by
walking bottom-up: for each internal room, compute "how much wrongness
does this room's children remove?" That number = the alpha where that
branch gets snipped. The tree doesn't invent alphas -- it reads them
off its own branches.
SNIP != REBUILD
The tree was ALREADY fully grown. Pruning collapses rooms; it does
NOT rebuild from scratch. No new .fit. Just room closure.
ALPHA VALUES COME FROM THE TREE, NOT THE TEACHER
You do not guess alpha=[0.1, 1, 10]. The tree hands you exact values
where branches would fire. Your job is to pick WHICH one works best
on the exam -- not to make up alphas.
NESTED AVERAGES LADDER
To pick the best alpha, the same 5-slice check from Chapter 4. Three averages,
stacked, each doing a different job:
RUNG 1 -- one person's guess (mean of targets in his leaf):
leaf holds {120, 140, 160} -> guess = 140
RUNG 2 -- one round's error (mean of misses over covered people):
person guess truth miss^2
p1 140 150 100
p2 90 80 100
p3 210 220 100
round error = mean = (100+100+100)/3 = 100
RUNG 3 -- one alpha's score (mean of the 5 round-errors):
round1 round2 round3 round4 round5
100 120 90 110 80
alpha's score = 500/5 = 100
TOP -- pick best alpha (MIN over scores, NOT an average):
alpha=12.5 -> 105
alpha=80.0 -> 100 <-- smallest -> alpha_hat
alpha=300 -> 140
targets in a leaf --avg--> guess (rung 1)
misses over people --avg--> round error (rung 2)
5 round-errors --avg--> alpha score (rung 3)
alpha scores --MIN--> alpha_hat (top, not avg)
A few wrong pictures I had to untangle, each one a thing that feels right.
ccp_alphas and ccp_alpha read like one word abbreviated two ways. They are two
different things:
ccp_alphas (plural) = a list the machine hands back -- the MENU
ccp_alpha (singular) = one number YOU set on a new tree -- the KNOB
Plural is the menu of options; singular is the dial you pick from it.
It looks like you must grow a tree, then read its pruning menu off it:
WRONG: tree.fit(X, y) -> pruning_path(tree)
RIGHT: cost_complexity_pruning_path(X, y) builds its own tree inside
The call IS the builder -- it grows a throwaway tree internally just to read the
menu. No separate .fit.
The alpha values look like reasonable guesses someone typed, [0, 0.01, 0.1, 1]. They
are not chosen at all:
each branch's saved-mess -> one alpha
the tree computes them from its own branches; the teacher never touches them
Pruning sounds like it refits the tree from scratch on the smaller shape. It does
not:
grow fully ONCE --> ccp_alpha collapses some rooms --> done
(no new .fit, no rebuild, just closure)
The tree was already grown; alpha only folds rooms shut.
In boosting it feels like you re-sort the columns against the new leftover each
round. You do not:
round 1: sort bmi/age/bp -> target = answer
round 2: sort bmi/age/bp -> target = leftover1 (the SAME column sort)
round 3: sort bmi/age/bp -> target = leftover2
Only the TARGET changes (answer -> leftover -> leftover); the column order is fixed,
and the leftover is not one of the 10 body columns to sort on anyway.
Last, both rungs are "a mean of some numbers", so they blur together -- but they
average across different things:
Rung 2: mean of misses ACROSS PEOPLE, inside one fold (per-fold)
Rung 3: mean of fold-errors ACROSS FOLDS, for one alpha (cross-fold)
Different granularity, different job -- mixing them is the classic cross-validation
confusion.
ANY ROOM HAS A WRONGNESS -- NOT JUST LEAVES
"You only measure wrongness at the end -- how can you measure it in the middle?"
Every room has a wrongness by asking "what if I stopped here?" Its guess would be
the mean of everyone in the room:
middle room, 6 people, targets {100,120,140,160,180,200}
if I STOP here: guess = mean = 150
wrongness = (100-150)^2 + (120-150)^2 + ... + (200-150)^2 = 7000
after split: {100,120,140} mean 120, wrong 800
{160,180,200} mean 180, wrong 800
total = 1600
drop = 7000 - 1600 = 5400 <- this doctor's worth
Wrongness is NOT leaf-only. Any room can be graded by "pretend it's a leaf."
Plain term used above Standard label
----------------------------------- ------------------------------------------
mixed-ness / how mixed Gini impurity
the drop in mixing information gain
share yes / share no class proportion / p, q
pure side a node with Gini = 0 (homogeneous)
half-half (worst) maximum Gini = 0.5 (for 2 classes)
the 4 counts class counts per child node
the weighted combine weighted average Gini of children
the alpha tax cost-complexity pruning (ccp_alpha)
the staircase of snip-points the effective-alpha sequence
fire a doctor prune a subtree
keep the sick:well ratio even stratified train/test split
Nothing above needed a computer -- only pencils, clerks, and patience. This last
section is for the day you meet one: the same counts, spoken in Python.
First the Gini ruler by hand -- the exact four counts from the worked example, each side
on its own line, no loop, so you watch 0.375, 0.32, and 0.344 print back:
The split, drawn -- 9 people cut into two buckets:
below: [ Y Y Y N ] 3 yes, 1 no (4 people)
above: [ Y N N N N ] 1 yes, 4 no (5 people)
BELOW SIDE: 3 YES, 1 NO (4 PEOPLE). GINI = CHANCE TWO RANDOM GRABS DISAGREE
below = 1 - (3/4)**2 - (1/4)**2 # 1 - 9/16 - 1/16 = 0.375
ABOVE SIDE: 1 YES, 4 NO (5 PEOPLE)
above = 1 - (1/5)**2 - (4/5)**2 # 1 - 1/25 - 16/25 = 0.32
WEIGHTED BADNESS OF THE CUT: WEIGHT EACH SIDE BY ITS HEAD-COUNT (4 OF 9, 5 OF 9)
cut = (4/9)*below + (5/9)*above
print(round(below,3), round(above,3), round(cut,3)) # 0.375 0.32 0.344
Now the same ruler racing two cuts on the four cancer lumps, each cut spelled out:
CUT RADIUS > 12 : BELOW {WELL, WELL} PURE -> 0 ; ABOVE {SICK, SICK} PURE -> 0
radius_12 = (2/4)*0.0 + (2/4)*0.0 # 0.0 <- perfectly clean
CUT RADIUS > 15 : BELOW {WELL, WELL, SICK} = 1 SICK 2 WELL ; ABOVE {SICK} PURE
below_15 = 1 - (1/3)**2 - (2/3)**2 # 4/9 = 0.444
radius_15 = (3/4)*below_15 + (1/4)*0.0 # 0.333
print(round(radius_12,3), round(radius_15,3)) # 0.0 0.333 -> cut>12 wins
No loop: the cuts are written out so you see each side's mix. A real tree races hundreds
of cuts across ten columns -- THAT is where the loop earns its keep, and the toolbox below
runs the identical Gini-and-weight on every cut for you:
>> NEW TO PYTHON? Each named once:
DecisionTreeClassifier() -- a question-chart machine for bin answers
criterion='gini' -- the mixing ruler (default) -- our 'cut', automated
cost_complexity_pruning_path -- the staircase of alpha snip-points
KFold -- the 5-slice splitter for the alpha check
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score, confusion_matrix
CLASSIFICATION TREE
tree_cls = DecisionTreeClassifier(criterion='gini', random_state=42)
tree_cls.fit(X_train_cls, y_train_cls)
acc = accuracy_score(y_test_cls, tree_cls.predict(X_test_cls))
PRUNING: GET ALPHA MENU, 5-SLICE CHECK, PICK WINNER
path = DecisionTreeRegressor(random_state=42).fit(X_train, y_train) \
.cost_complexity_pruning_path(X_train, y_train)
ccp_alphas = path.ccp_alphas # the staircase
from sklearn.model_selection import KFold
kf = KFold(n_splits=5, shuffle=True, random_state=42)
FOR EACH ALPHA: 5-FOLD CV -> MEAN MSE -> PICK ARGMIN -> ALPHA_HAT
THEN: TREE_PRUNED = DECISIONTREEREGRESSOR(CCP_ALPHA=ALPHA_HAT, ...)
TREE_PRUNED.FIT(X_TRAIN, Y_TRAIN) <- REBUILD WITH THE TAX
----------------------------------------------------------------------------------------------
IN THIS CHAPTER (Chapter 5 -- Question Charts and Committees):
Part 1 -- Question Charts by Hand .
Part 2 (this post) .
Part 3 -- Committees
<- Back to all posts
----------------------------------------------------------------------------------------------
home . source on GitHub
==============================================================================================