Assemble models by trying many inductive biases.

,fft.md

http://tiny.cc/fft

A fast-and-frugal tree (FFT) makes urgent binary choices via a few yes/no questions, deliberately ignoring most of the data: fast since little computation, frugal since it often stops after one or two cues. Here: fft.py is the core (one pass = 16 candidate trees, one per bias string, from min-variance cuts on incremental Welford stats; ~240 lines, pure Python, no deps); eval.py samples many such trees and picks winners cheaply (successive halving, Hoeffding racing), scoring accuracy plus fairness. Data is CSV; column-name suffix tags type and goal.

# install and test
git clone http://tiny.cc/optimiz && git clone http://tiny.cc/fft fft
cd fft && python3 -B fft.py -f ../optimiz/auto93.csv

Sections: NAME | SYNOPSIS | OPTIONS | DATA | TESTS | TREE OUTPUT | EXIT | SEE ALSO | LICENSE | AUTHOR

Files: fft.py | eval.py

NAME

fft - fast-frugal multi-objective trees; eval - sample + race them

SYNOPSIS

python3 -B fft.py  [-flag VAL]... [--grows|--trees]
python3 -B eval.py [-flag VAL]... [--sha|--csv|--final]

OPTIONS

fft.py (defaults from its docstring; SSOT):

  -s seed     random seed              (1234567891)
  -p dist     distance exponent        (2)
  -b bins     numeric bin count        (7)
  -d depth    max tree depth           (4)
  -R Round    display decimals         (2)
  -F fan      cue fan: ifan | dfan     (ifan)
  -f file     data file                ($DOOT/optimiz/auto93.csv)

eval.py:

  -f file     data file                ($DOOT/fairnez/adult.csv)
  -t trainN   train rows per sample    (200; 100 in --sha/--final)
  -P pos      positive label           (auto: labels.py, else minority)
  -r repeats  resamples of trainN rows (10)
  -S start    first rung, rows         (50; --sha/--final only)

DATA

CSV with header row. Each column name encodes type + role
via first char (case) and last char (suffix):

  first char UPPER  -> numeric (Num)
  first char lower  -> symbolic (Sym)
  suffix '+'        -> numeric goal, maximize
  suffix '-'        -> numeric goal, minimize
  suffix '!'        -> symbolic goal (klass)
  suffix '~'        -> protected attribute (fairness)
  suffix 'X'        -> ignore
  else              -> predictor

Missing values: '?'. Example header:

  Clndrs,Volume,HpX,Model,origin,Lbs-,Acc+,Mpg+

TESTS

fft.py (multi-goal regression to distance-to-heaven):

  (none)      grow 16 trees, show the lowest-error one
  --trees     show all 16 candidate trees + their bias + error
  --grows     timing: trees/second over repeated samples

eval.py (binary classification + fairness, e.g. fairnez CSVs):

  (none)      table: every tree x (pd, pf, prec, spd...) by disty
  --sha       full grid vs successive-halving vs Hoeffding race
  --csv       same comparison, one CSV row (for make ens)
  --final     race on train, report winner on test (make best)

TREE OUTPUT

fft.py prints one decision spine: each line is a cue; rows
matching it stop there (their distance-to-heaven d2h, 0=best),
all others fall through to the next cue.

  if Volume <= 83        then d2h 0.28 n=18
  if Model <= 74         then d2h 0.65 n=140
  ...
                         leaf d2h 0.66 n=99

Example:

  python3 -B fft.py -f ../optimiz/config_SS-N.csv --trees

EXIT

0  success
1  bad file / flag

SEE ALSO

http://tiny.cc/fairnez  fairness CSVs scored by eval.py
http://tiny.cc/optimiz  example CSVs (auto93, config_SS-N, ...)
http://tiny.cc/konfig   shared Makefile, bashrc, nvim, tmux

LICENSE

MIT.  https://choosealicense.com/licenses/mit/
(c) 2025 Tim Menzies.

AUTHOR

Tim Menzies <timm@ieee.org>

banner.txt

  __  __ _   
 / _|/ _| |_ 
| |_| |_| __|
|  _|  _| |_ 
|_| |_|  \__|
             
fast-frugal multi-objective trees. http://tiny.cc/fft
"a few sharp questions beat a big model."

eval.py

#!/usr/bin/env python3 -B
"""eval.py: score each fft tree on perf + fairness goals.

Build trees on -t trainN sampled rows (seeded), eval on the rest.
Per tree report: pd, pf, prec, ard, aaod (one each) + spd per
protected (~) col. pos label from fairnez/labels.py (else minority).

Uses fft.py as-is (trees/predict/Data/csv); y = 1.0 if pos else 0.0,
leaf mean thresholded at 0.5 = predicted class.

Options:
 -f file     data file  ($DOOT/fairnez/adult.csv)
 -t trainN   train rows  (200)
 -P pos      positive label  (auto)
"""
import sys, os, random, importlib.util
import fft
from fft import Data, trees, predict, csv, of, o

EPS = 1e-32

#-- confusion / metrics -----------------------------------------
def confused(pairs):                 # pairs=[(want,got),...] one-vs-rest
  n, labels, N = {}, set(), len(pairs)
  for wg in pairs:
    n[wg] = n.get(wg, 0) + 1
    labels |= set(wg)
  out = {}
  for k in labels:
    tp = n.get((k, k), 0)
    fn = sum(c for (w, g), c in n.items() if w == k and g != k)
    fp = sum(c for (w, g), c in n.items() if w != k and g == k)
    tn = N - tp - fn - fp
    pd, pf = tp/(tp+fn+EPS), fp/(fp+tn+EPS)
    prec   = tp/(tp+fp+EPS)
    out[k] = dict(tp=tp, fp=fp, fn=fn, tn=tn, pd=pd, pf=pf, prec=prec,
                  acc=(tp+tn)/(N+EPS))
  return out

def rate(m): return (m["tp"]+m["fp"]) / (m["tp"]+m["fp"]+m["fn"]+m["tn"]+EPS)
def spd(a, b, pos): return abs(rate(a[pos]) - rate(b[pos]))

#-- protected grouping ------------------------------------------
def groups(rows, at, isnum):         # -> (g1rows,g1, g2rows,g2)
  if isnum:                          # median (mean) split
    vs  = [r[at] for r in rows if r[at] != "?"]
    med = sum(vs)/len(vs) if vs else 0
    return ([r for r in rows if r[at] != "?" and r[at] <= med], "lo",
            [r for r in rows if r[at] != "?" and r[at] >  med], "hi")
  freq = {}                          # top-2 most-frequent syms
  for r in rows:
    if r[at] != "?": freq[r[at]] = freq.get(r[at], 0) + 1
  top = sorted(freq, key=freq.get, reverse=True)[:2]
  if len(top) < 2: return ([], None, [], None)
  g1, g2 = top
  return ([r for r in rows if r[at] == g1], g1,
          [r for r in rows if r[at] == g2], g2)

#-- pos label ---------------------------------------------------
def lookupPos(path):                 # fairnez/labels.py POSITIVE map
  lab = os.path.join(os.path.dirname(os.path.abspath(path)), "labels.py")
  if not os.path.exists(lab): return None
  spec = importlib.util.spec_from_file_location("labels", lab)
  mod  = importlib.util.module_from_spec(spec); spec.loader.exec_module(mod)
  return getattr(mod, "POSITIVE", {}).get(os.path.basename(path))

#-- print -------------------------------------------------------
def print2d(rows, sep="  "):
  rows = [[str(x) for x in r] for r in rows]
  ws = [max(len(r[c]) for r in rows if c < len(r))
        for c in range(max(len(r) for r in rows))]
  for r in rows:
    print(sep.join(r[c].rjust(ws[c]) for c in range(len(r))))

def scoreTree(t, test, klass, prot, names, lab, got):  # -> [pd,pf,prec,*spds]
  m = confused([(lab(r[klass]), got(t, r)) for r in test])["pos"]
  spds = []
  for at, s in prot:
    isnum = names[at][0].isupper()
    g1, n1, g2, n2 = groups(test, at, isnum)
    if not g1 or not g2: spds.append(0); continue
    a = confused([(lab(r[klass]), got(t, r)) for r in g1])
    b = confused([(lab(r[klass]), got(t, r)) for r in g2])
    if "pos" not in a or "pos" not in b: spds.append(0); continue
    spds.append(spd(a, b, "pos"))
  return [m["pd"], m["pf"], m["prec"]] + spds

def d2h(scores, names2):             # disty per score row vs the board
  board = Data([names2] + scores)
  return [fft.disty(board, r) for r in scores]

#-- shared setup ------------------------------------------------
def prep(file, pos):
  rows = list(csv(file))
  names, body = rows[0], rows[1:]
  klass = next(at for at, s in enumerate(names) if s[-1] == "!")
  prot  = [(at, s) for at, s in enumerate(names) if s.endswith("~")]
  if pos in (None, "", "auto"): pos = lookupPos(file)
  if pos is None:                    # minority label
    cnt = {}
    for r in body: cnt[r[klass]] = cnt.get(r[klass], 0) + 1
    pos = min(cnt, key=cnt.get)
  names2 = ["idX", "biasX", "Pd+", "Pf-", "Prec+"] \
           + ["Spd_" + s.rstrip("~") + "-" for _, s in prot]
  ctx = o(names=names, body=body, klass=klass, prot=prot, pos=pos,
          names2=names2,
          y   =lambda r: 1.0 if r[klass] == pos else 0.0,
          lab =lambda v: "pos" if v == pos else "neg",
          got =lambda t, r: "pos" if predict(t, r) >= 0.5 else "neg")
  return ctx

def score1(c, t, test):              # [idless] score row goals only
  return scoreTree(t, test, c.klass, c.prot, c.names, c.lab, c.got)

#-- main: full table --------------------------------------------
def main(file, trainN, pos, repeats):
  c = prep(file, pos)
  scores = []
  for rep in range(1, repeats + 1):
    shuf = random.sample(c.body, len(c.body))
    train, test = shuf[:trainN], shuf[trainN:]
    data = Data([c.names] + train)
    for bias, t in trees(data, c.y):
      scores.append([len(scores)+1, "%d:%s" % (rep, bias or "-")]
                    + score1(c, t, test))
  ds     = d2h(scores, c.names2)
  ranked = sorted(zip(ds, scores), key=lambda x: x[0])
  header = ["disty"] + [s[:-1] if s[-1] == "X" else s for s in c.names2]
  table  = [header] + [["%.3f" % d, r[0], r[1]]
                       + ["%.2f" % v for v in r[2:]] for d, r in ranked]
  print(os.path.basename(file),
        " pos=%s train=%d repeats=%d rows=%d  (sorted by disty)" %
        (c.pos, trainN, repeats, len(scores)))
  print2d(table)

#-- compare: full grid vs successive halving --------------------
# cands = pool of trees (built once). full = score every cand on the
# whole test pool. SHA = score on `start` test rows, keep top half by
# d2h, double test rows, repeat until 1 survivor. cost = predictions
# = sum(survivors * testrows). winner judged by its FULL-pool d2h.
def buildCands(c, trainN, repeats):
  pool = random.sample(c.body, len(c.body))
  cut  = int(0.5 * len(pool))
  test, trainpool = pool[:cut], pool[cut:]   # fixed test pool
  cands = []
  for _ in range(repeats):
    tr   = random.sample(trainpool, min(trainN, len(trainpool)))
    data = Data([c.names] + tr)
    cands += [t for _, t in trees(data, c.y)]
  return cands, test

def evalPool(c, cands, test):        # d2h of every cand on `test`
  scores = [[i, ""] + score1(c, t, test) for i, t in enumerate(cands)]
  return d2h(scores, c.names2)       # aligned to cands order

def full(c, cands, test):
  ds   = evalPool(c, cands, test)
  best = min(range(len(cands)), key=lambda i: ds[i])
  cost = len(cands) * len(test)
  return best, cost

def sha(c, cands, test, start=50):
  alive = list(range(len(cands)))
  n, cost = start, 0
  while len(alive) > 1 and n <= len(test):
    sub  = test[:n]
    ds   = evalPool(c, [cands[j] for j in alive], sub)
    cost += len(alive) * len(sub)
    order = sorted(range(len(alive)), key=lambda k: ds[k])
    keep  = max(1, len(alive) // 2)
    alive = [alive[k] for k in order[:keep]]
    n    *= 2
  if len(alive) > 1:                 # tie-break survivors on full test
    ds    = evalPool(c, [cands[j] for j in alive], test)
    cost += len(alive) * len(test)
    alive = [alive[min(range(len(alive)), key=lambda k: ds[k])]]
  return alive[0], cost

def race(c, cands, test, start=50, delta=0.1):
  # Hoeffding-style race: keep any cand within a noise margin of the
  # current best; margin = sqrt(ln(2/delta)/2n) shrinks as test grows.
  # losers die fast (cheap); the true best is never culled on noise.
  from math import log, sqrt
  alive, n, cost, ds = list(range(len(cands))), start, 0, [0]
  while len(alive) > 1 and n < len(test):
    ds     = evalPool(c, [cands[j] for j in alive], test[:n])
    cost  += len(alive) * n
    best   = min(ds)
    margin = sqrt(log(2/delta) / (2*n))
    keep   = [k for k, d in enumerate(ds) if d <= best + margin]
    alive  = [alive[k] for k in keep]
    ds     = [ds[k] for k in keep]              # decide on biggest rung seen
    n     *= 2
  return alive[min(range(len(alive)), key=lambda k: ds[k])], cost

#-- final: race on train, report best tree's goals on test ------
# split body 50:50. learn `repeats`x16 trees on 100-row train samples.
# race over ALL training rows -> 1 best tree. score it on TEST. one row.
# every goal cell = fit/train/test (integer percents). fit = the 100
# rows the winning tree actually grew on; train = all train rows;
# test = held-out. fit>>test gap = overfitting.
FINALHEAD = ["data", "pos", "Pd+", "Pf-", "Prec+", "SpdMean-", "spds"]

def finalRun(file, trainN, pos, repeats, start, asCsv=False):
  c = prep(file, pos)
  shuf = random.sample(c.body, len(c.body))
  cut  = len(shuf) // 2
  train, test = shuf[:cut], shuf[cut:]
  cands, fits = [], []                          # 160 trees + their fit rows
  for _ in range(repeats):
    tr = random.sample(train, min(trainN, len(train)))
    d  = Data([c.names] + tr)
    for _, t in trees(d, c.y): cands.append(t); fits.append(tr)
  best, _ = race(c, cands, train, start)        # race on ALL train data
  gfi = score1(c, cands[best], fits[best])      # goals on FIT rows (seen)
  gtr = score1(c, cands[best], train)           # goals on all TRAIN
  gte = score1(c, cands[best], test)            # goals on held-out TEST
  pct = lambda v: round(100*v)
  ftt = lambda f, a, b: "%d/%d/%d" % (pct(f), pct(a), pct(b))
  sfi, str_, ste = gfi[3:], gtr[3:], gte[3:]
  mean   = lambda xs: sum(xs)/len(xs) if xs else 0
  detail = ";".join("%s=%s" % (s.rstrip("~"), ftt(f, a, b))
                    for (_, s), f, a, b in zip(c.prot, sfi, str_, ste))
  vals = [os.path.basename(file), c.pos,
          ftt(gfi[0], gtr[0], gte[0]), ftt(gfi[1], gtr[1], gte[1]),
          ftt(gfi[2], gtr[2], gte[2]),
          ftt(mean(sfi), mean(str_), mean(ste)), detail]
  if asCsv: print(",".join(str(x) for x in vals))
  else:     print2d([FINALHEAD, vals])

CSVHEAD = ["data", "test", "cands", "full_s", "sha_s", "race_s",
           "full_rank", "sha_rank", "race_rank",
           "full_d2h", "sha_d2h", "race_d2h",
           "full_cost", "sha_cost", "race_cost"]

def compare(file, trainN, pos, repeats, start, asCsv=False):
  import time
  c = prep(file, pos)
  cands, test = buildCands(c, trainN, repeats)
  fullds = evalPool(c, cands, test)            # ground-truth ranking
  order  = sorted(range(len(cands)), key=lambda i: fullds[i])
  rank   = {i: k for k, i in enumerate(order)}

  res = {}                                      # method -> (winner,cost,time)
  for name, fn in (("full", lambda: full(c, cands, test)),
                   ("sha",  lambda: sha(c, cands, test, start)),
                   ("race", lambda: race(c, cands, test, start))):
    t0 = time.perf_counter()
    win, cost = fn()
    res[name] = (win, cost, time.perf_counter() - t0)

  if asCsv:
    nm = os.path.basename(file)
    print(",".join(str(x) for x in [
      nm, len(test), len(cands),
      *["%.3f" % res[m][2] for m in ("full", "sha", "race")],
      *[rank[res[m][0]] for m in ("full", "sha", "race")],
      *["%.3f" % fullds[res[m][0]] for m in ("full", "sha", "race")],
      *[res[m][1] for m in ("full", "sha", "race")]]))
    return
  out = [["method", "winner", "full_d2h", "rank", "cost(preds)", "time_s"]]
  for m in ("full", "sha", "race"):
    win, cost, t = res[m]
    out.append([m, win, "%.3f" % fullds[win], rank[win], cost, "%.3f" % t])
  print(os.path.basename(file),
        " pos=%s cands=%d test=%d  (rank 0 = true best)" %
        (c.pos, len(cands), len(test)))
  print2d(out)

if __name__ == "__main__":
  a   = sys.argv
  get = lambda f, d: of(a[a.index(f)+1]) if f in a else d
  fft.the.file = file = get("-f", os.path.expandvars("$DOOT/fairnez/adult.csv"))
  random.seed(fft.the.seed)
  if   "--csvhead" in a: print(",".join(CSVHEAD))
  elif "--finalhead" in a: print(",".join(FINALHEAD))
  elif "--final" in a: finalRun(file, get("-t", 100), get("-P", "auto"),
                                get("-r", 10), get("-S", 50), asCsv=True)
  elif "--csv" in a: compare(file, get("-t", 100), get("-P", "auto"),
                             get("-r", 10), get("-S", 50), asCsv=True)
  elif "--sha" in a: compare(file, get("-t", 100), get("-P", "auto"),
                             get("-r", 10), get("-S", 50))
  else:              main(file, get("-t", 100), get("-P", "auto"), get("-r", 10))

fft.py

#!/usr/bin/env python3 -B
"""fft.py: fast-frugal multi-objective tree.
(c) 2025, Tim Menzies timm@ieee.org, MIT license

Options:
 -s seed     seed=1234567891
 -p dist     distance exponent  p=2
 -b bins     bins=7
 -d depth    depth=4
 -R Round    Round=2
 -D disc     discretize once|many  Discretize=once
 -f file     file=$DOOT/optimiz/auto93.csv

"""
import sys, re, random, os
from math import sqrt, exp
from types import SimpleNamespace as o
BIG = 1E32

#-- 1. Columns --------------------------------------------------
# if Num as tuples +  memos on disty, then (66..100)% faster s
# for small to large files.  
def Sym()  : return {}
def Num(n=0, mu=0, m2=0): return (n, mu, m2) 

def n_(x) : return x[0]       
def mu_(x): return x[1]      
def m2_(x): return x[2]     

def symp(x): return isinstance(x,dict)
def nump(x): return isinstance(x,tuple)

def sd(num):
  n, mu, m2 = num
  return 0 if n < 2 else sqrt(max(0, m2)/(n-1))

def welford(num, v, w=1):    
  n, mu, m2 = num
  if (n := n + w) <= 0: return Num()
  d = v - mu; mu += w * d / n
  return n, mu, m2 + w * d * (v - mu)

def norm(num,v):
  n, mu, m2 = num
  z = (v - mu)/ (sd(num) + 1/BIG)
  return 1/(1+ exp(-1.7*max(-3, min(3, z))))

def merge(i, j, w=1):
  if symp(i):
     return {k: i.get(k,0) + w*j.get(k,0) for k in i | j}
  i_n,i_mu,i_m2 = i
  j_n,j_mu,j_m2 = j
  n = i_n + w*j_n
  if n <= 0: return Num()
  mu = (i_n*i_mu + w*j_n*j_mu) / n
  d  = j_mu - i_mu
  m2 = i_m2 + w*j_m2 + w*d*d*i_n*j_n / n
  return Num(n, mu, m2)

#-- 2. Data -----------------------------------------------------
def Data(src=[]):
  def roles(names):
    it.names = names
    for at, s in enumerate(names):
      z = s[-1]
      it.cols[at] = Sym() if s[0].islower() else Num()
      if z in "-+!":
        it.y += [at]
        it.goal[at] = z=="+"
      elif z != "X": it.x += [at]
      if z=="!": it.klass=at

  src = iter(src)
  it=o(names=[],klass=None, x=[], y=[], goal={}, cols={},rows=[])
  roles(next(src))
  return adds(src, it)

def add(it, v, w=1):
  if v != "?":
    if   symp(it): it[v] = it.get(v, 0) + w
    elif nump(it): it = welford(it, v, w)
    else:
      (it.rows.append if w==1 else it.rows.remove)(v)
      for at, x in enumerate(v):
        it.cols[at] = add(it.cols[at], x, w)
  return it

def adds(src, it=None):
  if it is None: it = Num()
  for x in src: it = add(it, x)
  return it

##-- 3. Discetization --------------------------------------------
def cuts(data, rows, y):
  ys = [y(r) for r in rows]
  for at in data.x:
    c, tot, bins, hi = data.cols[at], Num(), {}, {}
    for r, y1 in zip(rows, ys):
      if (v := r[at]) == "?": continue
      k  = v if symp(c) else int(the.bins*norm(c,v))
      bins[k] = add(bins.get(k) or Num(), y1)
      tot     = add(tot, y1)
      hi[k]   = v if symp(c) else max(hi.get(k, -BIG), v)
    yield from (symCuts if symp(c) else numCuts)(bins,tot,hi,at)

def symCuts(bins, tot, hi, at):
  for k, l in bins.items():
    score = m2_(l) + m2_(merge(tot, l, -1))
    yield (score, at, hi[k], hi[k], l)

def numCuts(bins, tot, hi, at):
  l = Num()
  for k in sorted(bins)[:-1]:
    l = merge(l, bins[k])
    score = m2_(l) + m2_(merge(tot, l, -1))
    yield (score, at, -BIG, hi[k], l)

#-- 4. build a tree ---------------------------------------------
def disty(data, row):
  p, s, n = the.p, 0, 0
  for at in data.y:
    if (v := row[at]) == "?": continue
    s += abs(norm(data.cols[at], v) - data.goal[at])**p
    n += 1
  return (s/n)**(1/p) if n else 0

def has(v, lo, hi): return v == "?" or lo <= v <= hi

def tree(data, y=None):
  # Build ONE binary tree: split rows matched/rest, recurse. The only
  # discretize once|many difference is `pick` (global vs per-node cuts).
  y    = memo(y or (lambda r: disty(data, r)))
  pick = (many if the.Discretize == "many" else once)(data, y)
  return build(data, data.rows, 0, y, pick)

def build(data, rows, lvl, y, pick):
  # node = o(cut, ys, left=matched-subtree, right=rest-subtree);
  # leaf = a Num of d2h. Splits only where both sides are non-empty.
  ys = adds(y(r) for r in rows)
  if cut := pick(rows, lvl):
    at, lo, hi = cut
    yes, no = [], []
    for r in rows: (yes if has(r[at], lo, hi) else no).append(r)
    if yes and no:
      return o(at=at, lo=lo, hi=hi, ys=ys,
               left =build(data, yes, lvl + 1, y, pick),
               right=build(data, no,  lvl + 1, y, pick))
  return ys

def once(data, y):
  # discretize ONCE on root: rank cues, every node at level lvl splits
  # on order[lvl] (an oblivious tree).
  best = {}
  for c in cuts(data, data.rows, y): best[c[1]] = min(best.get(c[1], c), c)
  order = [c[1:4] for c in sorted(best.values())[:the.depth]]
  return lambda rows, lvl: order[lvl] if lvl < len(order) else None

def many(data, y):
  # discretize per node: re-cut this node's rows, split on the best cut.
  floor = len(data.rows) ** .33
  def pick(rows, lvl):
    if lvl < the.depth:
      cs = [c for c in cuts(data, rows, y) if n_(c[4]) > floor]
      if cs: return min(cs, key=lambda c: c[0])[1:4]
  return pick

#-- 5. FFTs: post-process a tree into the exit-pattern fan ------
def trees(data, y=None):
  # Fan a binary tree into FFTs: at each level one child exits as a
  # leaf, the other continues. 2^depth patterns = 2^depth walks.
  return walk(tree(data, y))

def leaf(t): return t if nump(t) else t.ys   # a node collapsed to its Num

def walk(t):
  if nump(t):
    yield "", t
  else:
    for yes in (False, True):                 # which child exits as a leaf
      exit, cont = (t.left, t.right) if yes else (t.right, t.left)
      for bias, rest in walk(cont):
        yield str(int(yes)) + bias, o(at=t.at, lo=t.lo, hi=t.hi, yes=yes,
                 left=leaf(exit), right=rest)

def predict(t, row):
  while not nump(t):              # left = exit leaf, right = fall-through
    t = t.left if has(row[t.at], t.lo, t.hi) == t.yes else t.right
  return mu_(t)

def tune(cands, rows, y):
  err = lambda t: sum(abs(y(r)-predict(t,r))
                      for r in rows)/len(rows)
  return min(cands, key=err)

def show(data, t):
  if nump(t):
    print("%-33s leaf  d2h %.2f n=%d" % ("", mu_(t), n_(t)))
    return
  nm = data.names[t.at]                       # negate cue if exit is rest-side
  if   t.lo == t.hi: c = f"{nm} {'==' if t.yes else '!='} {t.lo}"
  elif t.lo == -BIG: c = f"{nm} {'<=' if t.yes else '>'} {qty(t.hi)}"
  else:              c = f"{nm} {'>=' if t.yes else '<'} {qty(t.lo)}"
  L = t.left
  print("if %-30s then d2h %.2f n=%d" % (c, mu_(L), n_(L)))
  show(data, t.right)

#-- 6. lin -------------------------------------------------------
def memo(fn):               # cache fn(row) by row identity
  cache = {}
  def f1(row):
    if (k := id(row)) not in cache: cache[k] = fn(row)
    return cache[k]
  return f1

def of(z):
  for f in (int, float):
    try: return f(z)
    except: pass
  z = z.strip()
  return {'True':True,'False':False,'None':None}.get(z, z)

def csv(file):
  for ln in open(file):
    ln = ln.strip()
    if ln and ln[0] != "#":
      yield [of(x) for x in ln.split(",")]

def qty(v):
  if isinstance(v, float):
    return int(v) if int(v)==v else round(v, the.Round)
  return v

#-- 7. Dests/ demos --------------------------------------------
def test_main():
  data  = Data(csv(the.file))
  y     = memo(lambda r: disty(data, r))
  cands = [t for _, t in trees(data, y)]
  show(data, tune(cands, data.rows, y))

def test_grows(repeats=10, k=100):
  import time
  rows = list(csv(the.file))
  names, body = rows[0], rows[1:]
  t = time.perf_counter()
  for _ in range(repeats):
    data = Data([names] + random.sample(body, k))
    cands = list(trees(data))
  t = time.perf_counter() - t
  print("%dx (sample %d, %d trees): %.3f s  -> %.1f ms/round"
        % (repeats, k, len(cands), t, t/repeats*1000))

def test_trees():
  data = Data(csv(the.file))
  y    = memo(lambda r: disty(data, r))
  err  = lambda t: sum(abs(y(r)-predict(t,r)) 
                       for r in data.rows)/len(data.rows)
  for i, (bias, t) in enumerate(trees(data), 1):
    print("===== tree %2d   bias %-5s   err %.3f =====" % (
         i, bias, err(t)))
    show(data, t)
    print()

#-- 8. Start-up -------------------------------------------------
os.environ.setdefault("DOOT",
  os.path.dirname(os.path.dirname(os.path.abspath(__file__))))
the=o(**{k:of(v) for k,v in re.findall(r"(\w+)=(\S+)", __doc__)})
the.file=os.path.expandvars(the.file)
random.seed(the.seed)

if __name__ == "__main__":
  for f, v in zip(sys.argv, sys.argv[1:]):
    for k in vars(the):
      if f == "-"+k[0]: setattr(the, k, of(v))
  if   "--grows" in sys.argv: test_grows()
  elif "--trees" in sys.argv: test_trees()
  else: test_main()

Makefile

# vim: ts=2 sw=2 sts=2 et :
# knobs  only; all targets live in $(KONFIG)/Makefile
KONFIG ?= ../konfig

APP   := fft
MAIN  := fft.py
EXT   := py
LANG  := python
LINT  := ruff check *.py
TOOLS := python3:run-py ruff:lint
PKG   := python3 gawk ruff neovim tmux

# loud failure if konfig not cloned (include resolves at parse time)
$(KONFIG)/Makefile:
	@test -f $@ || { echo "missing konfig: git clone http://tiny.cc/konfig $(KONFIG)"; exit 1; }
include $(KONFIG)/Makefile

# ---- ensemble eval -------------------------------------------------
# 160-line per-tree score table (.txt) + full/sha/race compare (.csv).
# pretty: column -s, -t ~/tmp/fft_ens.csv
TMP   ?= $(HOME)/tmp
DOOT  ?= $(abspath $(KONFIG)/..)
DATA  ?= $(DOOT)/fairnez/adult.csv
SETS  := adult bank communities compas german law

$(TMP)/fft_ens.txt: eval.py fft.py
	@mkdir -p $(TMP)
	python3 -B eval.py -f $(DATA) -t 100 -r 10 > $@
	@echo "wrote $@"

$(TMP)/fft_ens.csv: eval.py fft.py
	@mkdir -p $(TMP)
	python3 -B eval.py --csvhead > $@
	@for s in $(SETS); do \
	  python3 -B eval.py -f $(DOOT)/fairnez/$$s.csv -t 100 -r 10 --csv >> $@; \
	done
	@echo "wrote $@; pretty: column -s, -t $@"

.PHONY: ens
ens: $(TMP)/fft_ens.txt $(TMP)/fft_ens.csv

# best-tree-per-dataset: race on train, report goals on test. one row/set.
# pretty: column -s, -t ~/tmp/fft_best.csv
$(TMP)/fft_best.csv: eval.py fft.py
	@mkdir -p $(TMP)
	python3 -B eval.py --finalhead > $@
	@for s in $(SETS); do \
	  python3 -B eval.py -f $(DOOT)/fairnez/$$s.csv -t 100 -r 10 --final >> $@; \
	done
	@echo "wrote $@; pretty: column -s, -t $@"

.PHONY: best
best: $(TMP)/fft_best.csv

# ---- tests: one UPPERCASE rule each; `make test` finds them --------
TREE: ## test: grow 16 trees, show the best
	@python3 -B fft.py

TREES: ## test: show all 16 candidate trees
	@python3 -B fft.py --trees

GROWS: ## test: tree-building speed
	@python3 -B fft.py --grows

test: ## run every UPPERCASE test rule
	@gawk -F: '/^[A-Z][A-Z_]*:[^=]/ {print $$1}' $(MAKEFILE_LIST) | \
	  sort -u | while read t; do \
	    printf "\n=== %s ===\n" "$$t"; $(MAKE) -s $$t; done

todo.md

fft todo

QuickEst-style regression list (idea, measured, not yet in fft.py)

Context: explored whether FFTs do regression (continuous target, here d2h). They do -- QuickEst (Hertwig, Hoffrage & Martignon 1999), the regression sibling of classification FFTs (Martignon'08, Woike'17). All the FFT-classification papers compare vs CART/logistic but the task is binary; "regression" there is only CART's name. QuickEst is the real continuous one: leaf stores a mean, lexicographic one-reason scan.

Key realisation: it is NOT a tree. It is a flat decision list. The tree shape only matters if a leaf value depends on the path; with a fixed cue order it collapses to a list + two loops. Conditioning the tags (below) is just a shrinking row-set in the learn loop, not branching.

Final pseudocode (plain QuickEst, conditional tags)

# LEARN
make_list(rows):
    features = every "value-in-range" test, 1+ per column
    sort features by support, smallest first   # support = #rows that PASS f
    live = rows
    for f in features:                          # walk in that order
        exiting = live rows that FAIL f         # rows that stop here
        f.tag   = average target of exiting     # CONDITIONAL: only these
        live    = live rows that PASS f          # survivors carry forward
    catchall = average target of live            # passed everything
    return features, catchall

# GUESS (one-reason: stop at first failed test)
guess(features, row):
    for f in features:
        if row FAILS f: return f.tag
    return catchall

Frugal: smallest-support-first => first test is one almost no row passes => most rows fail it and exit at line 1 with the common-case average. Only unusual rows walk deep; the rare all-pass rows hit catchall. Most guesses cost one question.

Three knobs (each ~0.03-0.04 RMSE on 5 optimiz sets)

knob        QuickEst (simple)        ifan (accurate, = fft.py now)
--------    ----------------------   ----------------------------
1 order     by support               by variance-reduction score
2 direction fixed (exit fail side)   fan both sides, keep best on train
3 tag       marginal (all rows)      conditional (survivors only)

QuickEst = all knobs left; fft.py's ifan = all knobs right.

Ranges: bottom-up fuse (supervised discretizer, orthogonal to knobs)

Start 10 bins/col; merge adjacent bins while merged sd <= weighted-avg of parts' sd. Recurse to fixpoint. Splits survive only where y shifts; yields ~2-6 ranges/col. Clean ~8 lines using existing merge/sd/n_.

fuse(bins):
    repeat until no change:
        for adjacent a,b:
            c = merge(a,b)
            if sd(c) <= (a.n*sd(a)+b.n*sd(b))/c.n: replace a,b with c
    return bins

Verdict (measured, 30 + 5 datasets, 5 seeds, 50/50)

• As a PREDICTOR (RMSE): ifan (current fft.py) beats every QuickEst/rake /list variant on all sets; loses to gradient boosting (>=16 trees) on fine-grained config data (e.g. SS-N) by the d+1-leaf vocabulary ceiling.
• As an OPTIMIZER (rank test by tree, look up top-5, return best): tree adds +23 win pts over random-5 (76 vs 53); coarse ranking is enough, so the d+1 ceiling stops mattering. This is eval.py's bob/acquire game.
• QuickEst list: simplest, tree-free, citeable; a few RMSE pts behind ifan because of marginal tags + support order + fixed direction.

Next (optional, unbuilt)

• Feed fused cut-points into ifan's cuts (knob 1, sharper thresholds) -- only combination not yet measured.
• Ship the flat list as quicklist.py sibling for teaching contrast (same FFT family; one design choice decides tree vs list).