A glossary of tiny lectures, part 4

Week 4: cuts, trees, and explanation

By Tim Menzies, published 2026-09-07, updated 2026-09-07

Summary: Week 3 grouped rows by geometry (glossary 3). This week we ask a business question of the groups: WHICH single test — which column, cut where — best separates good from bad? Answer that recursively and you get a decision tree small enough to read aloud, which is this course's idea of explainable AI. Machinery verbatim from ezr.lua and ezr-lib.lua; each entry a tiny lecture: hook, idea, math if any, then the code.

Cuts, trees, XAI

New acronyms: XAI.

cut: One test on one x column: numbers split at a threshold (x ≤ v), symbols split by equality (x == v) — the holds slot of the columnProtocol (glossary 1). A good cut is one whose two sides are each more SETTLED about y than the whole was: split on "cylinders ≤ 4" and maybe the light, thrifty cars land on one side and the tanks on the other. The craft is scoring thousands of candidate cuts, cheaply.

Two lines hold that whole difference — and note the third rule hiding in both: an unknown cell says yes to everything, so a "?" never loses a row. (Glossary 1's Aha doctrine again: with no information, assume the answer that costs least.)
```
function SYM.holds(i,x,v) return x == "?" or x == v  end

function NUM.holds(i,x,v) return x == "?" or x <= v  end
```
So one call site, c:holds(row[c.at], v), sends a row left or right without ever asking which kind of column it holds — which is why divide, TREE.leaf and the cut scorers are each a line shorter than they would otherwise be.
div, recalled (sd and entropy): Everything below scores a split by asking each side one question: "how settled are you about y?" That question is div from glossary 1 — one protocol slot, two spellings. A Num answers with the standard deviation; a Sym answers with the entropy; both read 0 when the column has entirely made up its mind, and grow as it wriggles.

Entropy deserves an intuition: it is the average cost of playing twenty-questions against a column. Hunt one symbol in a bag; each yes/no question halves the candidates, so a thing filling fraction p of the bag is cornered after log₂(1/p) questions — common things fast, rare things slowly. But you hunt things as often as they occur: with probability p you run a hunt costing log₂(1/p), so the average effort per search is
- e = ∑ p · log₂(1/p) = -∑ p log₂ p
Check it: {a,a,a,a} — the search is over before it starts, 0 bits. A fair coin {a,b} — one question, 1 bit. {a,b,c,d} even — two questions, 2 bits. Skewed {a,a,a,b} — hunting a costs log₂(4/3) ≈ 0.4, hunting b costs 2, but you hunt a three times as often: 0.75·0.4 + 0.25·2 ≈ 0.81 bits. Skew is cheaper than fair, because mostly you are hunting the easy thing — which is exactly why entropy falls as a column settles. (Glossary 1's paper-strip story is this game in costume: one fold = one question.)

So val, below, reads as: the expected number of questions still to ask about y after the cut. A good cut pre-answers most of the search — pay one question at the branch, save many at the leaves. Trees are search-effort arbitrage. The code:
```
function NUM.div(i)
  return i.n < 2 and 0 or sqrt(max(i.m2,0) / (i.n-1)) end

function SYM.div(i)
  return sum(i.has, function(n,    p)
    p = n / i.n
    return -p * log(p) / log(2) end) end
```
Because both spellings answer the same call, nothing below ever asks which kind of column it is holding.
expected value: The probability-weighted average. If value f_i arrives with probability p_i, then on average you meet
- E[f] = ∑ p_i · f_i
Now split n rows into two sides holding n_a and n_b. Pick a random row after the split: you land on side a with probability n_a/n. So "how much diversity does a randomly-chosen row live with, after this cut?" is
- (div_a · n_a + div_b · n_b) / n
— the expected diversity. That one number scores a cut, and it is the next entry, verbatim.
val (expected diversity): How good is a cut? Summarize y on each side, ask each summary its diversity (previous entries), and weight by size — the expected value of the diversity a random row lives with after the split. Lower is better: a low val says both sides have (mostly) made up their minds.
```
function val(a,b)
  return (a:div()*a.n + b:div()*b.n) / (a.n + b.n + TINY) end
```
Note what this does NOT ask: whether y is numeric or symbolic. Any summary answering div can play, so the same tree code will handle regression, classification, and (via disty) multi-objective optimization. The protocol keeps paying.

Quinlan: Induction of decision trees. J.R. Quinlan. Machine Learning 1 (1986), 81-106.
least (the champion closure): Thousands of candidate cuts are coming, and no list of them will ever be built. least returns a closure holding one thing: the best candidate seen so far. Call it with a candidate to offer one; call it empty to read the winner.
```
function least(    lo)
  return function(x)
    if x and (lo == nil or x[1] < lo[1]) then lo = x end
    return lo end end
```
In SE-theory terms this is a visitor pattern: a little visitor, handed to whoever walks the data, memo-ing the best thing seen so far. The walker never knows what the visitor collects; the visitor never knows the walking order — open-closed, both ways. Every column feeds its cuts to the same visitor, and the champion rides home in the closure (glossary 2, again): O(1) memory over any number of candidates.
```
function TBL.bestcut(i,rows,Y,acc,best)
  for _,c in ipairs(i.cols.x) do i:cuts(rows,c,Y,acc,best) end
  return best() end
```
one-pass cuts: The dumb way first. A numeric column with n distinct values offers n-1 candidate cuts, and the obvious score for one cut is: build a left y-summary and a right y-summary from scratch, then take val. Building those summaries is a pass over all n rows — so scoring EVERY cut is O(n²):
```
-- dumb: n-1 cuts, each rebuilding summaries from n rows
for _,cut in ipairs(cuts) do          -- n-1 laps...
  l, r = acc(), acc()
  for _,p in ipairs(xy) do            -- ...of n rows each
    (p[1] <= cut and l or r):add(p[2]) end
  best{val(l, r), c.at, cut} end
```
Fine at 398 rows; death at a million. So: can we do O(n)? Yes, with week 1's machinery. Sort the (x,y) pairs once, then walk left to right ADDING each y to one growing left summary — and the right summary is never built at all: it is tot - here, by the pool algebra of glossary 2. Every cut scored in one linear pass; this is why week 1 insisted summaries must subtract.
```
function NUM.cuts(c,xy,tot,acc,best,    here)
  table.sort(xy, function(a,b) return a[1] < b[1] end)
  here = acc()
  for j,p in ipairs(xy) do
    here:add(p[2])
    if j < #xy and p[1] ~= xy[j+1][1] and big(j, #xy) then
      best{val(here, tot - here),c.at,p[1]} end end end
```
Can we do better still — O(m), for some m < n? Also yes, and it is gloss3's trick wearing new clothes: nothing is sacred about scoring cuts on ALL the rows. Hand the cuts machinery a small random sample (m = a few hundred, the.few style) and it finds nearly the same champion, for the same reason a 128-row sample found good enough poles. The recurring moral, third appearance: before optimizing the computation, ask how little of the data the computation actually needs.

Two guards ride along: cuts only fall between DISTINCT sorted values, and big refuses any cut leaving fewer than the.leaf rows on either side — tiny splits are memorization wearing a costume.
```
function big(lo,n)
  return the.leaf <= lo and lo <= n - the.leaf end
```

tree: Take the champion cut, divide the rows into yes and no, recurse on each side; stop at the.maxd levels or when a side gets small. Each node remembers its cut, its rows, and its loss. By default Y is disty, so this tree does multi-objective optimization — but hand it any Y and any accumulator and the same dozen lines do classification or regression.

function Tree(tbl,rows,Y,acc,    recurse)
  function recurse(rows,lvl,    ys,t,b,c,yes,no)
    ys = adds(map(rows, Y), acc())
    t  = new(TREE, {at=nil, v=nil, mu=ys:mid(), leafs=1,
                    here = tbl:clone(rows),
                    loss = ys.has and ys:div() or ys:mid()})
    t.val = t.loss
    if #rows >= 2*the.leaf and lvl < the.maxd then
      b = tbl:bestcut(rows, Y, acc, least())
      if b then
        c = tbl.cols.all[b[2]]
        yes, no = tbl:divide(rows, c, b[3])
        if #yes > 0 and #no > 0 then
          t.at, t.v = b[2], b[3]
          t.yes   = recurse(yes, lvl+1)
          t.no    = recurse(no,  lvl+1)
          t.val   = min(t.yes.val, t.no.val)
          t.leafs = t.yes.leafs + t.no.leafs end end end
    return t
  end -- recurse
  Y   = Y or tbl:Y()
  acc = acc or Num
  return recurse(rows, 0) end

To predict for a new row, walk it down and answer the leaf's mean:

function TREE.leaf(t,tbl,row,    c)
  while t.at do
    c = tbl.cols.all[t.at]
    t = c:holds(row[t.at], t.v) and t.yes or t.no end
  return t.mu end

XAI (explainable AI): An explanation is a model small enough to argue with. A tree of depth four is a paragraph: "under these tests, these rows; the best leaf is here." ezr's tree printer works for that arguability: one row per node, each goal's mean in its own column, best leaf marked with a triangle, and siblings printed better-branch-first so the top of the page is always the way to heaven. Contrast the rival offer — a black box plus an after-the-fact rationale. When the model itself is small, the model IS the explanation, and a business user can push back on any line of it ("three developers, not seven" is an arguable sentence; a weight matrix is not).

Note what kind of answer a tree gives. Attribution methods (SHAP, LIME and friends) rank columns: tires are important, the cap is important, tree is important. A tree ranks column-and-value together, because a branch is a test, not a name: bald tires, the cap turned through 180 degrees, an oak tree. The first kind tells you where to look; only the second tells you what to do — and what to do is the whole reason anyone asked.

Rudin: Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Cynthia Rudin. Nature Machine Intelligence 1 (2019), 206-215.