.biased.md

,sand-box.md

Sand-box

tricks for sampling lasrge space of inductive bias.

http://tiny.cc/sand-box

Run

make demo

to see our current results.

.gitignore

__pycache__/
*.pyc

active.py

#!/usr/bin/env python3 -B
"""active.py: greedy active learner on a quantile-pruned spine.

Label `start` rows. Each level: on the region's labelled rows,
pick the best min-variance feature; keep the best `keep` fraction
of the WHOLE region by that feature (drop the worst rest as an
exit leaf); label `grow` fresh rows in what stays; repeat -- until
the region is too small or the label `budget` runs out. Keeping
75% (not a 50/50 cut) decays slowly, so the budget buys a deep
spine.

Two models: the pruning spine (elite), and a normal min-variance
tree fit on the acquired labels (standard). Scored by ezr's hold-
out win: split rows in half, sort the held-out half by the model,
check the top `check`, score the best.

Flags are `-<key> val` (see `the`); commands: --spine, --tree.
 eg: python3 -B active.py -file ../optimiz/config_SS-N.csv --spine
"""
import sys, random
from pathlib import Path
sys.path.append(str(Path(__file__).resolve().parent.parent/"nuff"))
from nuff import (o, csv, Data, clone, disty, norm, Num, Sym,
                  add, mix, isa)

the = o(seed=1234567891, bins=7, start=8, grow=4, keep=0.75,
        budget=50, check=5, leaf=3, repeats=20,
        file="../optimiz/auto93.csv")
BIG = 1e32

# ---- cuts: min-variance splits over the x-columns -------------
def memo(fn):
  c = {}
  def f(r):
    if (k := id(r)) not in c: c[k] = fn(r)
    return c[k]
  return f

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

def cuts(data, rows, y):
  "Yield (score, at, lo, hi, bin-Num) candidate splits."
  ys = [y(r) for r in rows]
  for at in data.x:
    col, tot, bins, hi = data.cols[at], Num(), {}, {}
    for r, z in zip(rows, ys):
      if (v := r[at]) == "?": continue
      k = v if isa(col, Sym) else int(the.bins * norm(col, v))
      bins[k] = add(bins.get(k) or Num(), z)
      tot, hi[k] = add(tot, z), (v if isa(col, Sym)
                                 else max(hi.get(k, -BIG), v))
    if isa(col, Sym):
      for k, b in bins.items():
        yield b[2] + mix(tot, b, -1)[2], at, hi[k], hi[k], b
    else:
      left = Num()
      for k in sorted(bins)[:-1]:
        left = mix(left, bins[k])
        yield left[2]+mix(tot,left,-1)[2], at, -BIG, hi[k], left

def bestCut(data, rows, y):
  "Lowest-variance cut whose bin holds >= leaf rows."
  cs = [c for c in cuts(data, rows, y) if c[4][0] >= the.leaf]
  return min(cs, key=lambda c: c[0])[1:4] if cs else None

# ---- elite: a quantile-pruned acquisition spine ---------------
def active(data):
  "Acquire labels down the kept-best region: spine + labels."
  y = memo(lambda r: disty(data, r))
  seen = set()
  def label(r): seen.add(id(r)); return y(r)
  def mu(rs):
    z = [y(r) for r in rs if id(r) in seen]
    return sum(z)/len(z) if z else BIG
  pool = data.rows[:]; random.shuffle(pool)
  for r in pool[:the.start]: label(r)
  node, spine = pool, []
  while len(seen) < the.budget and len(node) >= 2*the.leaf:
    lab = [r for r in node if id(r) in seen]
    if len(lab) < 2*the.leaf: break
    if not (cut := bestCut(data, lab, y)): break
    s, good = keepers(data, node, cut, mu)
    if len(good) < the.leaf or len(good) == len(node): break
    spine += [s]
    for r in [x for x in good if id(x) not in seen][:the.grow]:
      if len(seen) >= the.budget: break
      label(r)
    node = good
  return o(spine=spine, final=mu(node)), \
         [r for r in pool if id(r) in seen]

def keepers(data, node, cut, mu):
  "Keep best `keep` of node by the feature; leaf + kept rows."
  at, lo, hi = cut
  yes = lambda r: has(r[at], lo, hi)
  good = mu([r for r in node if yes(r)]) <= \
         mu([r for r in node if not yes(r)])
  if isa(data.cols[at], Sym):                 # keep good category
    keep = [r for r in node if yes(r) == good]
  else:                                       # keep best `keep`%
    asc = sorted((r for r in node if r[at] != "?"),
                 key=lambda r: r[at] if good else -r[at])
    keep = asc[:max(the.leaf, int(the.keep*len(node)))]
    edge = keep[-1][at]
    lo, hi, good = (-BIG, edge, 1) if good else (edge, BIG, 1)
  kept = set(map(id, keep))
  drop = [r for r in node if id(r) not in kept]
  return o(at=at, lo=lo, hi=hi, yes=good, exit=mu(drop)), keep

def elite(model, row):
  "Predicted disty: exit the spine into a leaf, else the final."
  for s in model.spine:
    if has(row[s.at], s.lo, s.hi) != s.yes: return s.exit
  return model.final

# ---- standard: a normal binary min-variance tree --------------
def grow(data, rows, y, lvl=0):
  z = [y(r) for r in rows]
  t = o(at=None, mu=sum(z)/len(z), n=len(rows))
  if len(rows) >= 2*the.leaf and lvl < 12 and \
     (cut := bestCut(data, rows, y)):
    at, lo, hi = cut
    yes = [r for r in rows if has(r[at], lo, hi)]
    no  = [r for r in rows if not has(r[at], lo, hi)]
    if len(yes) >= the.leaf and len(no) >= the.leaf:
      t.at, t.lo, t.hi = at, lo, hi
      t.left  = grow(data, yes, y, lvl+1)
      t.right = grow(data, no,  y, lvl+1)
  return t

def leafmu(t, row):
  while t.at is not None:
    t = t.left if has(row[t.at], t.lo, t.hi) else t.right
  return t.mu

# ---- hold-out win (ezr metric) --------------------------------
def wins(data):
  ys = sorted(disty(data, r) for r in data.rows)
  ten = len(ys)//10
  lo, med, sd = ys[0], ys[5*ten], (ys[9*ten]-ys[ten])/2.56
  def f(row):
    x = disty(data, row)
    if x < lo + 0.35*sd: x = lo
    return max(-100, int(100*(1-(x-lo)/(med-lo+1e-32))))
  return f

def pick(hold, score, full):
  "Sort hold by model, check top `check`, best by true disty."
  return min(sorted(hold, key=score)[:the.check],
             key=lambda r: disty(full, r))

def holdout(data):
  win, eW, sW, rW = wins(data), Num(), Num(), Num()
  for _ in range(the.repeats):
    rows = data.rows[:]; random.shuffle(rows)
    h = len(rows)//2
    d, hold = clone(data, rows[:h]), rows[h:]
    y = memo(lambda r: disty(d, r))
    model, lab = active(d)
    std = grow(d, lab, y)
    rr = d.rows[:]; random.shuffle(rr)
    rnd = grow(d, rr[:the.budget], y)
    eW = add(eW, win(pick(hold, lambda r: elite(model, r), data)))
    sW = add(sW, win(pick(hold, lambda r: leafmu(std, r), data)))
    rW = add(rW, win(pick(hold, lambda r: leafmu(rnd, r), data)))
  return eW[1], sW[1], rW[1]

# ---- printers + start-up --------------------------------------
def showSpine(data, model, lab):
  print("# elite spine: %s  (%d labels, depth %d)"
        % (the.file, len(lab), len(model.spine)))
  for s in model.spine:                       # the EXIT cue
    nm = data.names[s.at]
    if   s.lo == s.hi: c = f"{nm} {'!=' if s.yes else '=='} {s.lo}"
    elif s.lo == -BIG: c = f"{nm} > {round(s.hi, 2)}"
    else:              c = f"{nm} < {round(s.lo, 2)}"
    print("  if %-22s then d2h %.3f" % (c, s.exit))
  print("  %-25s then d2h %.3f  <- best"
        % ("(else)", model.final))

def showTree(data, t, lvl=0, tag=""):
  pad = "|  " * lvl
  if t.at is None:
    print(f"{pad}{tag}d2h {t.mu:.3f}  n={t.n}"); return
  nm = data.names[t.at]
  c = (f"{nm} == {t.lo}" if t.lo == t.hi
       else f"{nm} <= {round(t.hi, 2)}")
  print(f"{pad}{tag}{c} ?   (n={t.n} d2h {t.mu:.3f})")
  showTree(data, t.left,  lvl+1, "yes  ")
  showTree(data, t.right, lvl+1, "no   ")

def main():
  data = Data(csv(the.file))
  if "--spine" in sys.argv:
    showSpine(data, *active(data))
  elif "--tree" in sys.argv:
    _, lab = active(data)
    print("# standard tree: %s (%d labels)" % (the.file, len(lab)))
    showTree(data, grow(data, lab, memo(lambda r: disty(data, r))))
  else:
    print("elite %.0f  standard %.0f  random %.0f  (ezr ~94)"
          % holdout(data))

if __name__ == "__main__":
  for f, v in zip(sys.argv, sys.argv[1:]):
    if f[:1] == "-" and (k := f[1:]) in vars(the):
      old = getattr(the, k)
      setattr(the, k, v if isinstance(old, str) else type(old)(v))
  random.seed(the.seed)
  main()

active_matrix.txt

dataset                                    random standard elite ezr
auto93                                         91       81    91  94
behavior_data_all_players                      81       93    90  95
behavior_data_player_statistics_cleaned_final     91       91    87 100
behavior_data_student_dropout                 100       85    80  95
behavior_data_WA_Fn-UseC_-HR-Employee-Attrition     96       87    86  94
binary_config_billing10k                       67       64    77  67
binary_config_FFM-1000-200-0.50-SAT-1          61       60    79  55
binary_config_FFM-125-25-0.50-SAT-1            70       56    68  66
binary_config_FFM-250-50-0.50-SAT-1            65       69    82  69
binary_config_FFM-500-100-0.50-SAT-1           75       64    76  61
binary_config_FM-500-100-0.25-SAT-1            61       65    75  55
binary_config_FM-500-100-0.50-SAT-1            60       64    72  71
binary_config_FM-500-100-0.75-SAT-1            60       63    87  71
binary_config_FM-500-100-1.00-SAT-1            68       78    88  63
binary_config_Scrum100k                        52       51    70  54
binary_config_Scrum10k                         60       60    83  64
binary_config_Scrum1k                          78       58    83  75
config_Apache_AllMeasurements                 100       96    97 100
config_HSMGP_num                              100       95   100 100
config_rs-6d-c3_obj1                          100      100    90 100
config_rs-6d-c3_obj2                          100      100   100 100
config_sol-6d-c2-obj1                         100      100   100 100
config_SQL_AllMeasurements                     79       80    91  77
config_SS-A                                   100      100   100 100
config_SS-B                                    98       95   100 100
config_SS-C                                   100       90   100 100
config_SS-D                                    81       78    67  80
config_SS-E                                    87       75    85  92
config_SS-F                                    81       65    69  72
config_SS-G                                    72       68    68  77
config_SS-H                                    89       96    91 100
config_SS-I                                    91       94    91  98
config_SS-J                                   100       97    98 100
config_SS-K                                    91       96    89  96
config_SS-L                                    98       95    98  95
config_SS-M                                   100      100   100 100
config_SS-N                                    78       74    71  83
config_SS-O                                    96       90    89  94
config_SS-P                                    98       85    89  98
config_SS-Q                                   100      100   100 100
config_SS-R                                    77       73    81  74
config_SS-S                                   100       95    97 100
config_SS-T                                   100      100    98 100
config_SS-U                                    97       79    87 100
config_SS-V                                    99      100    97 100
config_SS-W                                    68       59    75  67
config_SS-X                                    84       96    98  95
config_wc-6d-c1-obj1                           95       93    78 100
config_wc+rs-3d-c4-obj1                        89       87    82 100
config_wc+sol-3d-c4-obj1                       92       81    82 100
config_wc+wc-3d-c4-obj1                        92       82    81 100
config_X264_AllMeasurements                   100      100   100 100
financial_data_BankChurners                    52       45    60  57
financial_data_home_data_for_ml_course         41       41    40  36
financial_data_Loan                            48       60    59  69
financial_data_WA_Fn-UseC_-Telco-Customer-Churn    100      100   100 100
health_data_Data_COVID19_Indonesia             88       92    84  89
health_data_Life_Expectancy_Data              100      100   100  97
health_data_Medical_Data_and_Hospital_Readmissions     90      100   100  90
hpo_Health-ClosedIssues0000                   100      100   100 100
hpo_Health-ClosedIssues0001                    50       51    51  51
hpo_Health-ClosedIssues0002                   100      100   100 100
hpo_Health-ClosedIssues0003                    74       57    52  80
hpo_Health-ClosedIssues0004                    15       16    10  10
hpo_Health-ClosedIssues0005                    76       77    76  74
hpo_Health-ClosedIssues0006                    93       96    90  94
hpo_Health-ClosedIssues0007                    44       42    46  38
hpo_Health-ClosedIssues0008                    78       77    73  79
hpo_Health-ClosedIssues0009                    38       30    23  21
hpo_Health-ClosedIssues0010                    61       58    59  59
hpo_Health-ClosedIssues0011                   100      100   100 100
hpo_Health-ClosedPRs0000                      100      100   100 100
hpo_Health-ClosedPRs0002                       86       87    86  82
hpo_Health-ClosedPRs0003                      100      100   100 100
hpo_Health-ClosedPRs0004                       90       92    90  90
hpo_Health-ClosedPRs0005                      100       95    95 100
hpo_Health-ClosedPRs0006                       56       62    54  78
hpo_Health-ClosedPRs0007                       92       88    96  84
hpo_Health-ClosedPRs0008                        3        5     2   2
hpo_Health-ClosedPRs0009                       57       65    62  59
hpo_Health-ClosedPRs0010                       38       51    42  40
hpo_Health-ClosedPRs0011                      100      100    95 100
hpo_Health-Commits0000                        100      100   100 100
hpo_Health-Commits0001                        100      100    95 100
hpo_Health-Commits0002                         33       52    37  28
hpo_Health-Commits0003                         73       69    71  75
hpo_Health-Commits0004                         21       18    17   9
hpo_Health-Commits0005                         50       67    57  51
hpo_Health-Commits0006                         67       64    62  68
hpo_Health-Commits0007                         57       54    67  65
hpo_Health-Commits0008                         56       49    44  50
hpo_Health-Commits0009                        100       98    98  99
hpo_Health-Commits0010                         88       81    83  84
hpo_Health-Commits0011                        100       96   100 100
misc_auto93                                    91       81    91  94
misc_Car_price_cleaned                         61       47    48  69
misc_multiLabel                               100      100   100 100
misc_Wine_quality                              45       55    63  57
process_coc1000                                39       52    39  43
process_nasa93dem                              71       51    64  58
process_pom3a                                  71       74    78  70
process_pom3b                                  64       65    72  74
process_pom3c                                  57       58    53  51
process_pom3d                                  72       66    74  73
process_xomo_flight                            99      100   100  96
process_xomo_ground                            90       91    95  95
process_xomo_osp                               93       95    95  98
process_xomo_osp2                              61       70    78  75
rl_A2C_Acrobot                                 55       50    51  53
rl_A2C_CartPole                                50       45    48  47
sales_data_accessories                         13        8    14  13
sales_data_dress-up                            41       42    34   8
sales_data_Marketing_Analytics                 59       64    60  52
sales_data_socks                               97      100   100 100
sales_data_wallpaper                           96       84    81  70
systems_7z                                    100      100   100 100
systems_BDBC                                  100      100   100 100
systems_dconvert                              100      100   100 100
systems_deeparch                              100      100   100 100
systems_exastencils                            92       95    96  95
systems_HSQLDB                                100      100   100 100
systems_javagc                                100      100   100 100
systems_LLVM                                  100       98   100 100
systems_PostgreSQL                            100      100   100 100
systems_redis                                  77       71    62  69
systems_storm                                 100      100   100 100
systems_x264                                   88       83    79  92
test_dataset120                                90       90    87  92
test_dataset600                                86       94    93  84

active_results.txt

# active.py hold-out win — 129 optimiz datasets (keep=0.75, grow=4)
# elite=quantile-pruned spine; standard=tree on its labels;
# random=tree on 50 random labels; ezr=ezr acquire20.
# one row per treatment, sorted | fmt -70.

## random    n=129 mean=79 median=88
  3 13 15 21 33 38 38 39 41 41 44 45 48 50 50 50 52 52 55 56 56 57 57 57
  59 60 60 60 61 61 61 61 61 64 65 67 67 68 68 70 71 71 72 72 73 74 75
  76 77 77 78 78 78 79 81 81 81 84 86 86 87 88 88 88 89 89 90 90 90 90
  91 91 91 91 91 92 92 92 92 93 93 95 96 96 96 97 97 98 98 98 99 99 100
  100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100
  100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100
  100 100

## standard  n=129 mean=78 median=83
  5 8 16 18 30 41 42 42 45 45 47 49 50 51 51 51 51 52 52 54 55 56 57 58
  58 58 59 60 60 60 62 63 64 64 64 64 64 65 65 65 65 66 67 68 69 69 70
  71 73 74 74 75 77 77 78 78 79 80 81 81 81 81 82 83 84 85 85 87 87 87
  88 90 90 90 91 91 92 92 93 93 94 94 95 95 95 95 95 95 95 96 96 96 96
  96 96 97 98 98 100 100 100 100 100 100 100 100 100 100 100 100 100 100
  100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100

## elite     n=129 mean=79 median=86
  2 10 14 17 23 34 37 39 40 42 44 46 48 48 51 51 52 53 54 57 59 59 60 60
  62 62 62 63 64 67 67 68 68 69 70 71 71 72 72 73 74 75 75 76 76 77 78
  78 78 79 79 80 81 81 81 82 82 82 83 83 83 84 85 86 86 87 87 87 87 88
  89 89 89 90 90 90 90 91 91 91 91 91 93 95 95 95 95 95 96 96 97 97 97
  98 98 98 98 98 100 100 100 100 100 100 100 100 100 100 100 100 100 100
  100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100

## ezr       n=129 mean=80 median=90
  2 8 9 10 13 21 28 36 38 40 43 47 50 51 51 51 52 53 54 55 55 57 57 58
  59 59 61 63 64 65 66 67 67 68 69 69 69 69 70 70 71 71 72 73 74 74 74
  75 75 75 77 77 78 79 80 80 82 83 84 84 84 89 90 90 92 92 92 94 94 94
  94 94 95 95 95 95 95 95 96 96 97 98 98 98 99 100 100 100 100 100 100
  100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100
  100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100
  100 100 100 100

bang.awk

# bang.awk: count how often each method is top-ranked (a "!" in its
# tier column) in far_trees.csv. The method's name sits one column
# left of the "!" (the *_win header), cached from line 1.
#   gawk -F, -f bang.awk far_trees.csv
NR==1 { for(i=1; i<=NF; i++) name[i]=$i; next }      # cache header
      { for(i=1; i<=NF; i++) if($i=="!") bang[name[i-1]]++ }
END   { for(m in bang) { k=m; sub(/_win/,"",k)
                         print bang[m], k | "sort -n" } }

banner.txt

 _                  _
| |___ __ _ _ _ ___(_)_ _  __ _
| / -_) _` | ' \___| | ' \/ _` |
|_\___\__,_|_||_|  |_|_||_\__, |
     "less noise == more signal" |___/

de.py

#!/usr/bin/env python3 -B
"""
de, random-cluster forest engine + confusion (library)
(c) 2025, Tim Menzies <timm@ieee.org>, MIT license

Generic services: Data, disty, tree (random axis-cut cluster),
treeLeaf (router), treeShow (printer), confused (pd/pf/.. from
(want,got) pairs), cli/the. No task knowledge -- see compas.py.

Options:
 -s --seed    random seed        seed=1234567891
 -p --p       distance exponent  p=2
 -R --Round   repr decimals      Round=2
 -b --budget  eval budget        budget=50
 -G --gens    number of gens     gens=5
 -N --NP      population size    NP=30
 -C --CR      crossover ration   CR=0.9
 -F --F       mutation factor    F=0.8
 -f --file    data file          file=../optimiz/auto93.csv
"""
import sys, re
from math import exp
from random import shuffle,sample,choice,seed
from random import random as rand
from random import randrange as randin
BIG = 1E32

# ## constructors -----------------------------------------------
def Num(txt="", at=0):
  return o(it=Num, at=at, txt=txt, n=0, mu=0, m2=0, sd=0,
           goal=0 if txt.endswith("-") else 1)

def Sym(txt="", at=0):
  return o(it=Sym, at=at, txt=txt, n=0, has={})

def Data(src=[]):
  return adds(src, o(it=Data, cols=None, rows=[]))

def Cols(names):
  cols,x,y,klass = [],[],[],None
  for at, s in enumerate(names):
    cols += [col := (Num if s[0].isupper() else Sym)(s, at)]
    if   s[-1] in "-+!" : y += [col]      
    elif s[-1] != "X"   : x += [col]   
    if   s[-1] == "!"   : klass = col
  return o(it=Cols, all=cols, x=x,y=y, names=names, klass=klass)

def add(i, v):
  if i.it is Data:
    if not i.cols: i.cols = Cols(v)
    else:
      i.rows += [v]
      for c in i.cols.all: add(c, v[c.at])
  elif v == "?": pass
  elif i.it is Sym:
    i.n += 1; i.has[v] = i.has.get(v, 0) + 1
  elif i.it is Num: 
    i.n += 1; d = v - i.mu
    i.mu += d / i.n
    i.m2 += d * (v - i.mu)
    i.sd = (i.m2/(i.n-1))**0.5 if i.n > 1 else 0
  return v

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

def clone(root, rows):
  return adds(rows, adds([root.cols.names],Data()))

def memo(fn):
  b4 = {}
  def go(x):
    k = id(x)
    if k in b4: return b4[k]
    out = b4[k] = fn(x)
    return out
  return b4,go

def de(data, pop):
  lab, err = memo(lambda r: disty(data,nearest(data, pop, r)))
  xs  = [col.at for col in data.cols.x]
  for k in range(the.gens * len(pop)):
    if len(lab) > the.budget: break
    a, b, c = choice(pop), choice(pop), choice(pop)
    r, new  = choice(xs), a[:]            
    for j in xs:
      if j == r or rand() < the.CR:
        new[j] = mutate(a[j], b[j], c[j])
    j = k % len(pop)
    if err(new) < err(pop[j]):
      pop[j] = new
  return min(pop, key=err)

def mutate(a,b,c):
  if a=="?" or b=="?" or c=="?": return a
  if isinstance(a,(float,int)): return a + the.F*(b - c)
  return b if rand() < 0.5 else c

# ## metrics ----------------------------------------------------
def norm(num, v):
  if v=="?": return v
  z = (v - num.mu) / (num.sd + 1/BIG)
  return 1 / (1 + exp(-1.7 * max(-3, min(3, z))))

def disty(data, row):
  s, n, p = 0, 0, the.p
  for col in data.cols.y:
    n += 1; s += abs(norm(col, row[col.at]) - col.goal)**p
  return (s/n)**(1/p) if n else 0

def distx(data, row1, row2):               
  s, n, p = 0, 0, the.p
  for col in data.cols.x:
    n += 1
    v1, v2 = row1[col.at], row2[col.at]
    if v1=="?" and v2=="?": s += 1; continue
    if col.it is Sym: s += 0 if v1==v2 else 1
    else:
      v1, v2 = norm(col, v1), norm(col, v2)
      v1 = v1 if v1!="?" else (0 if v2>.5 else 1)
      v2 = v2 if v2!="?" else (0 if v1>.5 else 1)
      s += abs(v1-v2)**p
  return (s/n)**(1/p)

def nearest(data,rows,row1):
  return min(rows, key = lambda row2: distx(data,row1,row2))

# ## lib -------------------------------------------------------
class o(dict):  
  __getattr__ = dict.get;__setattr__ = dict.__setitem__;
  def __repr__(i):
    return "{" + " ".join(":%s %s" % (k, onum(i[k])) for k in i
                          if str(k)[0]!="_") + "}"
def onum(v):
  if isinstance(v,float):
    return int(v) if v==int(v) else round(v, the.Round)
  return v

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

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 settings(doc):              # key=val defaults from doc
  return o(**{k: of(v)
              for k, v in re.findall(r'(\w+)=(\S+)', doc)})

# ## cli -------------------------------------------------------
def cli(the, doc, egs={}):      # --x runs test_x()
  flags = {f: l.lstrip("-")
           for s,l in re.findall(r"(-\w) (--\w+)",doc)
           for f in (s,l)}
  for j, s in enumerate(sys.argv):
    if fn := egs.get("test_" + s.lstrip("-")):
      seed(the.seed); fn()
    elif k := flags.get(s):
      v = the[k]
      if isinstance(v, bool): v = not v
      elif j+1 < len(sys.argv): v = of(sys.argv[j+1])
      the[k] = v
    elif re.match(r"-\D", s):
      sys.exit("bad flag: %s\n%s" % (s, doc))
  return the

# ## egs (run via --name) --------------------------------------
def test_the():                 # show the config
  print(the)

def test_de():
  d=Data(csv(the.file))
  a=Num()
  b=Num()
  for _ in range(the.budget):
     pop = sample(d.rows, min(the.NP, len(d.rows)))
     add(a, disty(d,de(d,pop)))
     add(b, min(disty(d,r) for r in pop))
  print(onum(a.mu),round(a.mu- b.mu,2))

# ## main -------------------------------------------------------
the = settings(__doc__)
seed(the.seed)
if __name__ == "__main__":
  cli(the, __doc__, globals())

de2.py

#!/usr/bin/env python3 -B
"""de2: diff-evo, reservoir cols. (c) 2025 T. Menzies, MIT.

Options:
 -s --seed    random seed       seed=1234567891
 -p --p       distance exponent p=2
 -R --Round   repr decimals     Round=2
 -b --budget  eval budget       budget=50
 -G --gens    number of gens    gens=5
 -N --NP      population size   NP=10
 -C --CR      crossover ratio   CR=0.9
 -F --F       mutation factor   F=0.8
 -K --K       reservoir cap     K=256
 -O --O       oracle size       O=128
 -f --file    data file         file=../optimiz/auto93.csv
"""
import sys, re
from random import sample, choice, choices, seed
from random import randrange as randin
from random import random as rand

class o(dict):
  __getattr__=dict.get; __setattr__=dict.__setitem__
  def __repr__(i):
    return "{"+" ".join(f":{k} {qty(v)}"
                        for k,v in i.items())+"}"

nump = lambda c: isinstance(c, list)
symp = lambda c: isinstance(c, dict)

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

# ## data -------------------------------------------------------
def Data(src):
  data = o(x=[], y=[], goal={}, cols={}, rows=[], stale=False)
  dataHead(data, next(src := iter(src)))
  for v in src: dataAdd(data, v)
  return data

def dataHead(data, row):
  data.names = row
  for at, s in enumerate(row):
    data.cols[at] = [] if s[0].isupper() else {}
    if s[-1] in "-+!":
      data.y += [at]
      data.goal[at] = 0 if s[-1]=="-" else 1
    elif s[-1] != "X": data.x += [at]

def dataKeep(col, v, n):
  if symp(col): col[v] = col.get(v, 0) + 1
  elif len(col) < the.K: col.append(v)
  else:
    j = randin(n)
    if j < the.K: col[j] = v

def dataAdd(data, row):
  data.stale = True
  data.rows += [row]
  for at, v in enumerate(row):
    if v != "?": dataKeep(data.cols[at], v, len(data.rows))

# ## status ---------------------------------------------------
def ok(data):
  if data.stale:
    for col in data.cols.values():
      if nump(col): col.sort()
    data.stale = False
  return data

def norm(data, at, v):
  if v == "?": return v
  num = ok(data).cols[at]
  return where(num, v) / (len(num) or 1)

# ## distance ---------------------------------------------------
def disty(data, row):
  p, s, n = the.p, 0, 0
  for at in data.y:
    n += 1
    s += abs(norm(data,at,row[at]) - data.goal[at])**p
  return (s/n)**(1/p) if n else 0

def distx(data, row1, row2):
  p, s, n = the.p, 0, 0
  for at in data.x:
    n += 1; v1, v2 = row1[at], row2[at]
    if v1=="?" and v2=="?": s += 1; continue
    if symp(data.cols[at]):
      s += 0 if v1==v2 else 1
    else:
      v1, v2 = norm(data,at,v1), norm(data,at,v2)
      v1 = v1 if v1!="?" else (0 if v2>.5 else 1)
      v2 = v2 if v2!="?" else (0 if v1>.5 else 1)
      s += abs(v1-v2)**p
  return (s/n)**(1/p) if n else 0

def nearest(data, rows, row):
  return min(rows, key=lambda row2: distx(data, row, row2))

def guess(data):
  return [choices(list(c),list(c.values()))[0]
          if symp(c) else choice(c)
          for c in data.cols.values()]

def mate(data):
  r1, r2 = choice(data.rows), choice(data.rows)
  return [r1[at] if rand()<.5 else r2[at]
          for at in range(len(data.names))]

# ## de ---------------------------------------------------------
def mutate(a, b, c):
  if "?" in (a,b,c): return a
  if isinstance(a,(int,float)): return a + the.F*(b-c)
  return b if rand() < .5 else c

def de(xs, pop, y):
  cache, score = memo(y)
  for k in range(the.gens * len(pop)):
    if len(cache) > the.budget: break
    a, b, c = choice(pop), choice(pop), choice(pop)
    r, new = choice(xs), a[:]
    for j in xs:
      if j==r or rand() < the.CR:
        new[j] = mutate(a[j], b[j], c[j])
    i = k % len(pop)
    if score(new) < score(pop[i]): pop[i] = new
  return min(pop, key=score)

# ## lib ---------------------------------------------------
def mu(lst): return sum(lst)/len(lst)

def where(num, v):
  lo, hi = 0, len(num)
  while lo < hi:
    m = (lo + hi) // 2;
    if num[m] < v: lo = m + 1
    else: hi = m
  return lo

def memo(fn):
  cache = {}
  def wrapper(x):
    k = id(x)
    if k not in cache: cache[k] = fn(x)
    return cache[k]
  return cache, wrapper

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 settings(doc):
  return o(**{k: of(v)
              for k,v in re.findall(r'(\w+)=(\S+)', doc)})

def cli(the, doc, egs):
  flags = {}
  for s, l in re.findall(r"(-\w) (--\w+)", doc):
    name = l.lstrip("-")
    flags.setdefault(s, name); flags.setdefault(l, name)
  for j, s in enumerate(sys.argv):
    if fn := egs.get("test_" + s.lstrip("-")):
      seed(the.seed); fn()
    elif k := flags.get(s):
      v = the[k]
      the[k] = (not v) if isinstance(v,bool) else of(
                 sys.argv[j+1])
  return the

# ## egs --------------------------------------------------------
def test_de():
  data = Data(csv(the.file))
  a, b, c = [], [], []
  for _ in range(the.budget):
    ref = sample(data.rows, min(the.O, len(data.rows)))
    y = lambda r: disty(data, nearest(data, ref, r))
    popA = [mate(data) for _ in range(the.NP)]
    popB = sample(data.rows, min(the.NP, len(data.rows)))
    a += [y(de(data.x, popA, y))]
    b += [y(de(data.x, popB, y))]
    c += [min(disty(data, r) for r in ref)]
  print(qty(mu(a)), qty(mu(b)), qty(mu(c)), the.file)

the = settings(__doc__)
seed(the.seed)
if __name__ == "__main__":
  cli(the, __doc__, globals())

ezr_bc.png

fair.py

import sys, random, glob
from collections import Counter
from nothing import Data, csv, covers, isa, Sym
sys.path.insert(0, "../nuff")
from nuff import confuse

random.seed(1)

def randrange(rows, at, sym):           # one (lo,hi) condition
  while True:
    v = random.choice(rows)[at]
    if v != "?": break
  if sym: return (v, v)
  vs = [r[at] for r in rows if r[at] != "?"]
  d  = random.choice([1, 3, 10])        # whole / third / tenth span
  w  = (max(vs) - min(vs)) / d / 2
  return (v - w, v + w)

def randrule(data):                     # 1..3 random conditions
  ats = random.sample(data.x, min(random.randint(1,3), len(data.x)))
  return [(at, *randrange(data.rows, at, isa(data.cols[at], Sym)))
          for at in ats]

def evalrule(rows, rule, klass, pos, sens):
  got  = [1 if covers(rule, r) else 0 for r in rows]
  want = [1 if r[klass] == pos else 0 for r in rows]
  c    = confuse(list(zip(want, got)))
  rec  = c[1].pd                         # recall of positive class
  pf   = c[1].pf                         # false alarm
  spd  = 0                               # worst statistical parity diff
  for at in sens:
    cnt = Counter(r[at] for r in rows if r[at] != "?")
    if len(cnt) < 2: continue
    (a,_), (b,_) = cnt.most_common(2)
    ga = [g for g,r in zip(got,rows) if r[at] == a]
    gb = [g for g,r in zip(got,rows) if r[at] == b]
    if ga and gb:
      spd = max(spd, abs(sum(ga)/len(ga) - sum(gb)/len(gb)))
  d2h = (((1-rec)**2 + pf**2 + spd**2) / 3) ** .5   # recall^,pf_,spd_
  return d2h, rec, pf, spd

def pct(xs, p): return sorted(xs)[min(len(xs)-1, int(p/100*len(xs)))]

def main(file, N=1000, sub=100):
  data  = Data(csv(file))
  klass = [at for at,s in enumerate(data.names) if s[-1]=="!"][0]
  sens  = [at for at,s in enumerate(data.names) if s[-1]=="~"]
  data.x = [a for a in data.x if a != klass]   # never split on klass
  rows  = data.rows[:]; random.shuffle(rows)
  train = rows[:sub]; test = rows[sub:]
  data.rows = train                      # ranges built from train only
  pos   = Counter(r[klass] for r in train).most_common()[-1][0]
  print("file ", file.split("/")[-1],
        " train", len(train), " test", len(test), " pos", pos)
  # build + score 1000 rules on TRAIN
  pool  = [(evalrule(train, ru, klass, pos, sens), ru)
           for ru in (randrule(data) for _ in range(N))]
  pool.sort(key=lambda x: x[0][0])       # by train d2h
  hdr = "%-6s %7s %7s %7s %7s" % ("","d2h","recall","pf","max_spd")
  def row(tag, m): print("%-6s %7.3f %7.3f %7.3f %7.3f" % (tag,*m))
  print("\nbest rule (lowest train d2h):")
  best = pool[0][1]
  rnd = lambda v: round(v,2) if isinstance(v,(int,float)) else v
  print(" ", [(data.names[a],rnd(lo),rnd(hi)) for a,lo,hi in best])
  print("\n"+hdr)
  row("train", pool[0][0])
  row("test ", evalrule(test, best, klass, pos, sens))
  # also: top-5 train rules, each on test, to see the gap
  print("\ntop-5 train rules: train vs test\n"+hdr)
  for sc,ru in pool[:5]:
    row("train", sc)
    row("test ", evalrule(test, ru, klass, pos, sens))

if __name__ == "__main__":
  main(sys.argv[1] if len(sys.argv)>1 else "../fairnez/compas.csv")

far.md

Far.py: related work

Far.py optimizes by peeling: project examples best-to-worst along a FastMap axis¹, drop the worst fraction, keep the survivors, repeat. It is pool-based (a fixed set of unlabeled rows; the algorithm chooses which few to label), label-frugal (only survivors pay the cost of a y evaluation), and mixed-type (FastMap distance handles numeric and symbolic columns alike). The methods below share Far's drop-worst-keep-survivors skeleton but each differs on at least one of those three axes. None is a fair empirical baseline; they are cited to position the work, not to benchmark against.

The methods, in brief

PRIM (Patient Rule Induction Method)². Bump-hunting: finds a high-mean "box" by peeling a small fraction α (≈0.05–0.1) off one axis-aligned face per step, then optionally "pastes" back. Closest ancestor — Far's per-pass drop is PRIM's α. But PRIM peels attribute boundaries one column at a time and assumes every label is free.

Cross-Entropy Method (CEM)³. Keep the elite ρ-quantile, refit a sampling distribution, resample, repeat. Chases the good region like Far, but synthesizes fresh samples each round (membership-query) and assumes free evaluations.

Successive Halving⁴ / Hyperband⁵. Sample many configs, give each a small compute budget, keep the top fraction, give survivors more budget, repeat. The thing peeled is compute per config, not a region of data. Vanilla Hyperband is modelless and samples configs from the space (query synthesis), not from a pool. BOHB⁶ / DEHB⁷ add a surrogate model on top.

Racing (irace⁸, Hoeffding races⁹). Eliminate inferior candidates as statistical evidence accumulates; survivors race on. Like Far it discards losers early, but candidates are algorithm configs evaluated on free instances, not pool members bought under a label budget.

Truncation selection in (μ,λ)-ES / CMA-ES¹⁰. Each generation keep the top fraction, discard the rest, mutate survivors. Hardwired to continuous numeric search (Gaussian mutation, covariance adaptation) — no native mixed/symbolic types, and labels (fitness calls) are assumed cheap.

How Far differs

Axis	Others	Far.py
Label cost	free / cheap	frugal — only survivors labeled
Query mode	synthesis or config-space	pool-based selection
Cut geometry	axis-aligned box / numeric mutation	FastMap projection hyperplane
Data types	mostly numeric	numeric + symbolic

One-line story: we revive PRIM's peeling but make it label-cheap, pool-based, and geometry-driven via a FastMap projection.

Citations (MLA)

Citations (BibTeX)

@article{friedman1999bump,
  author  = {Friedman, Jerome H. and Fisher, Nicholas I.},
  title   = {Bump Hunting in High-Dimensional Data},
  journal = {Statistics and Computing},
  volume  = {9},
  number  = {2},
  pages   = {123--143},
  year    = {1999}
}

@book{rubinstein2004cem,
  author    = {Rubinstein, Reuven Y. and Kroese, Dirk P.},
  title     = {The Cross-Entropy Method: A Unified Approach to Combinatorial
               Optimization, Monte-Carlo Simulation and Machine Learning},
  publisher = {Springer},
  year      = {2004}
}

@article{li2017hyperband,
  author  = {Li, Lisha and Jamieson, Kevin and DeSalvo, Giulia and
             Rostamizadeh, Afshin and Talwalkar, Ameet},
  title   = {Hyperband: A Novel Bandit-Based Approach to Hyperparameter
             Optimization},
  journal = {Journal of Machine Learning Research},
  volume  = {18},
  number  = {1},
  pages   = {6765--6816},
  year    = {2017}
}

@inproceedings{jamieson2016sha,
  author    = {Jamieson, Kevin and Talwalkar, Ameet},
  title     = {Non-stochastic Best Arm Identification and Hyperparameter
               Optimization},
  booktitle = {Proceedings of AISTATS},
  pages     = {240--248},
  year      = {2016}
}

@inproceedings{falkner2018bohb,
  author    = {Falkner, Stefan and Klein, Aaron and Hutter, Frank},
  title     = {{BOHB}: Robust and Efficient Hyperparameter Optimization at Scale},
  booktitle = {Proceedings of ICML},
  pages     = {1437--1446},
  year      = {2018}
}

@inproceedings{awad2021dehb,
  author    = {Awad, Noor and Mallik, Neeratyoy and Hutter, Frank},
  title     = {{DEHB}: Evolutionary Hyperband for Scalable, Robust and Efficient
               Hyperparameter Optimization},
  booktitle = {Proceedings of IJCAI},
  pages     = {2147--2153},
  year      = {2021}
}

@article{lopezibanez2016irace,
  author  = {L{\'o}pez-Ib{\'a}{\~n}ez, Manuel and Dubois-Lacoste, J{\'e}r{\'e}mie
             and P{\'e}rez C{\'a}ceres, Leslie and Birattari, Mauro and
             St{\"u}tzle, Thomas},
  title   = {The irace Package: Iterated Racing for Automatic Algorithm
             Configuration},
  journal = {Operations Research Perspectives},
  volume  = {3},
  pages   = {43--58},
  year    = {2016}
}

@inproceedings{maron1994hoeffding,
  author    = {Maron, Oden and Moore, Andrew W.},
  title     = {Hoeffding Races: Accelerating Model Selection Search for
               Classification and Function Approximation},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  pages     = {59--66},
  year      = {1994}
}

@article{hansen2001cmaes,
  author  = {Hansen, Nikolaus and Ostermeier, Andreas},
  title   = {Completely Derandomized Self-Adaptation in Evolution Strategies},
  journal = {Evolutionary Computation},
  volume  = {9},
  number  = {2},
  pages   = {159--195},
  year    = {2001}
}

@inproceedings{faloutsos1995fastmap,
  author    = {Faloutsos, Christos and Lin, King-Ip},
  title     = {{FastMap}: A Fast Algorithm for Indexing, Data-Mining and
               Visualization of Traditional and Multimedia Datasets},
  booktitle = {Proceedings of ACM SIGMOD},
  pages     = {163--174},
  year      = {1995}
}

Footnotes

1. Faloutsos, Christos, and King-Ip Lin. "FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets." Proceedings of ACM SIGMOD, 1995, pp. 163–174. ↩

2. Friedman, Jerome H., and Nicholas I. Fisher. "Bump Hunting in High-Dimensional Data." Statistics and Computing, vol. 9, no. 2, 1999, pp. 123–143. ↩

3. Rubinstein, Reuven Y., and Dirk P. Kroese. The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation and Machine Learning. Springer, 2004. ↩

4. Jamieson, Kevin, and Ameet Talwalkar. "Non-stochastic Best Arm Identification and Hyperparameter Optimization." Proceedings of AISTATS, 2016, pp. 240–248. ↩

5. Li, Lisha, et al. "Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization." Journal of Machine Learning Research, vol. 18, no. 1, 2017, pp. 6765–6816. ↩

6. Falkner, Stefan, Aaron Klein, and Frank Hutter. "BOHB: Robust and Efficient Hyperparameter Optimization at Scale." Proceedings of ICML, 2018, pp. 1437–1446. ↩

7. Awad, Noor, Neeratyoy Mallik, and Frank Hutter. "DEHB: Evolutionary Hyperband for Scalable, Robust and Efficient Hyperparameter Optimization." Proceedings of IJCAI, 2021, pp. 2147–2153. ↩

8. López-Ibáñez, Manuel, et al. "The irace Package: Iterated Racing for Automatic Algorithm Configuration." Operations Research Perspectives, vol. 3, 2016, pp. 43–58. ↩

9. Maron, Oden, and Andrew W. Moore. "Hoeffding Races: Accelerating Model Selection Search for Classification and Function Approximation." Advances in Neural Information Processing Systems (NeurIPS), 1994, pp. 59–66. ↩

10. Hansen, Nikolaus, and Andreas Ostermeier. "Completely Derandomized Self-Adaptation in Evolution Strategies." Evolutionary Computation, vol. 9, no. 2, 2001, pp. 159–195. ↩

far.py

#!/usr/bin/env python3 -B
"""far.py: a FastMap active learner -- keep the best 66% per level.

Each level: eval `grow` new rows (plus the survivors handed down
from the parent). From those labelled rows take the two most
distant (by distx) as the ends of a line; orient it by disty so
the better pole is `west`. Project EVERY row (labelled +
unlabelled) onto the line with the FastMap cosine law (distx, so
unlabelled rows project too), keep the best 2/3 (drop the worst
third), recurse -- until the region is too small or the label
`budget` runs out. Labelled rows == the memo's cache keys.

Then feed the labelled rows to nuff.tree, sort a held-out half by
the tree, check the top `check`, score the best (ezr hold-out win,
mean over `repeats`).

 eg: python3 -B far.py -file ../optimiz/auto93.csv   (needs ../nuff)
"""
import sys, random
from nuff import (o, csv, Data, clone, disty, distx, Num, add,
                  shuffle, some, tree, treePredict)

the = o(seed=1234567891, grow=4, keep=0.66, budget=50, cap=1024,
        check=5, leaf=3, repeats=20, file="../optimiz/auto93.csv")
TINY = 1e-32

def memo(fn):
  "Cache fn(row) by value; return (lookup fn, its cache dict)."
  cache = {}
  def f(r):
    if r not in cache: cache[r] = fn(r)
    return cache[r]
  return f, cache

# ---- FastMap acquisition (a la ezr.half, kept side only) ------
def project(rows, d,y):
  "FastMap poles O(2N), west=better; return a projection key fn."
  far = lambda r: max(rows, key=lambda z: d(z, r))
  east = far(rows[0])
  west = far(east)
  if y(east) < y(west): east, west = west, east     # west = better
  c = d(east,west) + 1E-32
  return lambda r: (d(east, r)**2 + c*c - d(west, r)**2) / (2*c)

def landscape(data):
  "Each level: label grow worst-survivors; poles from local labels."
  d = lambda r1, r2: distx(data, r1, r2)
  y, ys = memo(lambda r: disty(data, r))     # ys: labelled-row cache
  pool = shuffle(data.rows)                  # rows are hashable tuples
  while len(ys) < the.budget - the.grow and len(pool) >= 2*the.leaf:
    lab, k = [], 0
    for r in pool:                           # one pass: poles = survivors
      if r in ys: lab.append(r)
      elif k < the.grow: y(r); lab.append(r); k += 1  # label worst grow
    n = max(1, int((1-the.keep)*len(pool)))   # drop >=1 so pool shrinks
    pool = sorted(pool, key=project(lab, d, y))[n:]
  return list(ys)

# ---- hold-out win (ezr metric) --------------------------------
def wins(data):
  ys = sorted(disty(data, r) for r in data.rows)
  ten = len(ys)//10
  lo, med, sd = ys[0], ys[5*ten], (ys[9*ten] - ys[ten])/2.56
  def f(row):
    v = disty(data, row)
    if v < lo + 0.35*sd: v = lo
    return max(-100, int(100*(1 - (v-lo)/(med-lo + TINY))))
  return f

def pick(hold, score, full):
  "Sort hold by model, check top `check`, best by true disty."
  return min(sorted(hold, key=score)[:the.check],
             key=lambda r: disty(full, r))

def holdout(data):
  win, out = wins(data), Num()
  for _ in range(the.repeats):
    rows = some(data.rows, the.cap)            # rows already hashable
    h = len(rows)//2
    d, hold = clone(data, rows[:h]), rows[h:]
    t = tree(d, landscape(d))
    best = pick(hold, lambda r: treePredict(t, r), data)
    out = add(out, win(best))
  return out[1]

def main():
  data = Data(csv(the.file))
  print(f"{holdout(data):.0f}\t{the.file.split('/')[-1]}")

if __name__ == "__main__":
  for f, v in zip(sys.argv, sys.argv[1:]):
    if f[:1] == "-" and (k := f[1:]) in vars(the):
      old = getattr(the, k)
      setattr(the,k, v if isinstance(old,str) else type(old)(v))
  random.seed(the.seed)
  main()

far1.py

#!/usr/bin/env python3 -B
"""far1.py: far.py + the nuff bits it needs, all in one file.

Standalone copy -- no `from nuff import`. Carries only the minimum
nuff closure: typed csv, the Sym/Num columns, Data, distance, and the
min-variance tree. (No stats, bayes, ffts, or pretty-printers.)

 eg: python3 -B far1.py -file ../optimiz/auto93.csv
"""
import sys, random
from math import exp
from types import SimpleNamespace as o
isa = isinstance
BIG, TINY = 1e32, 1e-32

# ===== nuff (minimal) =========================================
# ---- io: typed rows ------------------------------------------
def thing(s):
  "Coerce a string to int, float, bool, else str."
  s = s.strip()
  for fn in (int, float):
    try: return fn(s)
    except ValueError: pass
  return {"True": True, "False": False}.get(s, s)

def csv(file, clean=lambda s: s.partition("#")[0].split(",")):
  "Yield typed, hashable rows from a CSV ('#' starts a comment)."
  with open(file, encoding="utf-8") as f:
    for line in f:
      row = clean(line)
      if any(x.strip() for x in row):
        yield tuple(thing(x) for x in row)

def shuffle(lst, rng=random):
  "Shuffled copy via the given RNG."
  lst = lst[:]; rng.shuffle(lst); return lst

def some(lst, k=512, rng=random):
  "Up to k items sampled without replacement."
  return rng.sample(lst, min(k, len(lst)))

# ---- columns: Sym={value:count}, Num=(n,mu,m2) ---------------
Sym = dict
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 sd(num):
  "Standard deviation of a Num from its m2."
  n, mu, m2 = num
  return 0 if n < 2 else (max(0, m2) / (n - 1)) ** 0.5

def welford(num, v, inc=1):
  "Num + v (inc=-1 removes); returns a new (n, mu, m2)."
  n, mu, m2 = num
  if (n := n + inc) <= 0: return Num()
  d = v - mu; mu += inc * d / n
  return n, mu, m2 + inc * d * (v - mu)

def norm(num, v):
  "Map v to 0..1 via a logistic on its z-score (Num only)."
  if v == "?": return v
  z = (v - mu_(num)) / (sd(num) + TINY)
  return 1 / (1 + exp(-1.7 * max(-3, min(3, z))))

def mix(i, j, inc=1):
  "Combine two same-type cols; inc=-1 removes j from i."
  if isa(i, Sym):
    return {k: i.get(k, 0) + inc * j.get(k, 0) for k in i | j}
  (ni, mui, m2i), (nj, muj, m2j) = i, j
  n = ni + inc * nj
  if n <= 0: return Num()
  d  = muj - mui
  mu = (ni * mui + inc * nj * muj) / n
  m2 = m2i + inc * m2j + inc * d * d * ni * nj / n
  return Num(n, mu, m2)

# ---- table: roles in Data, columns by at-index ---------------
def Data(src=None):
  "Table o(names, cols{at:col}, x, y, goal, klass, rows)."
  src = iter(src or [])
  data = o(names=[], cols={}, x=[], y=[], goal={}, klass=None, rows=[])
  roles(data, next(src, []))
  return adds(src, data)

def roles(data, names):
  "Read header names into column roles (mutates data)."
  data.names = names
  for at, s in enumerate(names):
    data.cols[at] = Num() if s[0].isupper() else Sym()
    if s[-1] == "X": continue
    if s[-1] in "+-!":
      data.y.append(at)
      data.goal[at] = s[-1] == "+"
      if s[-1] == "!": data.klass = at
    else: data.x.append(at)

def add(it, v, inc=1):
  "Add to a Sym/Num/Data; RETURNS the (new) it. Skips '?'."
  if isa(it, Sym):
    if v != "?": it[v] = it.get(v, 0) + inc
    return it
  if isa(it, tuple):                          # Num
    return welford(it, v, inc) if v != "?" else it
  (it.rows.append if inc == 1 else it.rows.remove)(v)  # row
  for at in it.cols: it.cols[at] = add(it.cols[at], v[at], inc)
  return it

def adds(src, it=None):
  "Fold src into it (a fresh Num by default); returns it."
  if it is None: it = Num()
  for v in src: it = add(it, v)
  return it

def clone(data, src=None):
  "New Data with data's columns; optionally seed src rows."
  return Data([data.names] + (src or []))

def mid(col):
  "Central tendency: mode (Sym) or mean (Num)."
  return max(col, key=col.get) if isa(col, Sym) else mu_(col)

def mids(data):
  "Central tendency of every column, keyed by at-index."
  return {at: mid(col) for at, col in data.cols.items()}

# ---- distance ------------------------------------------------
def minkowski(vals, p=2):
  "Aggregate per-item distances via the p-norm."
  total, n = 0, 0
  for v in vals: total += v ** p; n += 1
  return (total / (n or 1)) ** (1 / p)

def disty(data, row, **kw):
  "Distance of a row to the best goals (0 = ideal)."
  return minkowski(
    (abs(norm(data.cols[at], row[at]) - data.goal[at])
     for at in data.y if row[at] != "?"), **kw)

def distx(data, r1, r2, **kw):
  "Distance between two rows over the x-columns."
  return minkowski((gap(data.cols[at], r1[at], r2[at])
                    for at in data.x), **kw)

def gap(col, u, v):
  "Distance between two values of one column (0..1)."
  if u == v == "?": return 1
  if isa(col, Sym): return u != v
  u, v = norm(col, u), norm(col, v)
  if u == "?": u = 1 if v < 0.5 else 0
  if v == "?": v = 1 if u < 0.5 else 0
  return abs(u - v)

# ---- tree: min-variance binary tree over the x-columns -------
def has(v, lo, hi): return v == "?" or lo <= v <= hi

def _separate(data, rows, y):
  "Yield each (score, at, lo, hi, yes-Num, no-Num) split candidate."
  ys = {r: y(r) for r in rows}             # cache disty per (hashable) row
  for at in data.x:
    sym = isa(data.cols[at], Sym)
    rs  = sorted((r for r in rows if r[at] != "?"), key=lambda r: r[at])
    tot = Num()
    for r in rs: tot = add(tot, ys[r])
    yes = run = Num()
    for k, r in enumerate(rs):
      run = add(run, ys[r])
      if k+1 < len(rs) and rs[k+1][at] == r[at]: continue   # cut at boundaries
      grp = run if sym else (yes := mix(yes, run)); run = Num()
      no  = mix(tot, grp, -1)
      lo  = r[at] if sym else -BIG
      yield m2_(grp) + m2_(no), at, lo, r[at], grp, no

def treeCut(data, rows, y, leaf=3):
  "The lowest-variance cut (whole tuple), or None."
  ok = (c for c in _separate(data, rows, y) if n_(c[4]) >= leaf)
  return min(ok, key=lambda c: c[0], default=None)

def tree(data, rows=None, y=None, leaf=3, lvl=0, maxDepth=12):
  "Min-variance binary tree; leaves keep the disty mean. yes=match."
  rows = data.rows if rows is None else rows
  y = y or (lambda r: disty(data, r))
  ys = [y(r) for r in rows]
  m = mids(clone(data, rows))
  t = o(at=None, mu=sum(ys)/len(ys), n=len(rows),
        ymid=[m[a] for a in data.y])
  if len(rows) >= 2*leaf and lvl < maxDepth and \
     (cut := treeCut(data, rows, y, leaf)):
    at, lo, hi = cut[1:4]
    yes, no = [], []
    for r in rows:
      (yes if has(r[at], lo, hi) else no).append(r)
    if len(yes) >= leaf and len(no) >= leaf:
      t.at, t.lo, t.hi, t.yes = at, lo, hi, True
      t.left  = tree(data, yes, y, leaf, lvl+1, maxDepth)
      t.right = tree(data, no,  y, leaf, lvl+1, maxDepth)
  return t

def treePredict(t, row):
  "Walk a tree to a leaf; return its disty mean."
  while t.at is not None:
    t = t.left if has(row[t.at], t.lo, t.hi) == t.yes else t.right
  return t.mu

# ===== far ====================================================
the = o(seed=1234567891, grow=4, keep=0.66, budget=50, cap=1024,
        check=5, leaf=3, repeats=20, file="../optimiz/auto93.csv")

def memo(fn):
  "Cache fn(row) by value; return (lookup fn, its cache dict)."
  cache = {}
  def f(r):
    if r not in cache: cache[r] = fn(r)
    return cache[r]
  return f, cache

def project(rows, d, y):
  "FastMap poles O(2N), west=better; return a projection key fn."
  far = lambda r: max(rows, key=lambda z: d(z, r))
  east = far(rows[0]); west = far(east)
  if y(east) < y(west): east, west = west, east     # west = better
  c = d(east, west) + TINY
  return lambda r: (d(east, r)**2 + c*c - d(west, r)**2) / (2*c)

def landscape(data):
  "Each level: label grow worst-survivors; poles from local labels."
  d = lambda r1, r2: distx(data, r1, r2)
  y, ys = memo(lambda r: disty(data, r))     # ys: labelled-row cache
  pool = shuffle(data.rows)
  while len(ys) < the.budget - the.grow and len(pool) >= 2*the.leaf:
    lab, k = [], 0
    for r in pool:                           # one pass: poles = survivors
      if r in ys: lab.append(r)
      elif k < the.grow: y(r); lab.append(r); k += 1
    n = max(1, int((1-the.keep)*len(pool)))   # drop >=1 so pool shrinks
    pool = sorted(pool, key=project(lab, d, y))[n:]
  return list(ys)

def wins(data):
  ys = sorted(disty(data, r) for r in data.rows)
  ten = len(ys)//10
  lo, med, sd = ys[0], ys[5*ten], (ys[9*ten] - ys[ten])/2.56
  def f(row):
    v = disty(data, row)
    if v < lo + 0.35*sd: v = lo
    return max(-100, int(100*(1 - (v-lo)/(med-lo + TINY))))
  return f

def pick(hold, score, full):
  "Sort hold by model, check top `check`, best by true disty."
  return min(sorted(hold, key=score)[:the.check],
             key=lambda r: disty(full, r))

def holdout(data):
  win, out = wins(data), Num()
  for _ in range(the.repeats):
    rows = some(data.rows, the.cap)
    h = len(rows)//2
    d, hold = clone(data, rows[:h]), rows[h:]
    t = tree(d, landscape(d))
    best = pick(hold, lambda r: treePredict(t, r), data)
    out = add(out, win(best))
  return out[1]

def main():
  data = Data(csv(the.file))
  print(f"{holdout(data):.0f}\t{the.file.split('/')[-1]}")

if __name__ == "__main__":
  for f, v in zip(sys.argv, sys.argv[1:]):
    if f[:1] == "-" and (k := f[1:]) in vars(the):
      old = getattr(the, k)
      setattr(the, k, v if isinstance(old, str) else type(old)(v))
  random.seed(the.seed)
  main()

far_bc.png

far_bc_dfan.png

far_bc_ifan.png

far_ezr.csv

far_growkeep.png

far_ifan.txt

# auto93
  if Volume > 121             then d2h 0.57 n=9
  if origin != 1              then d2h 0.31 n=21
  (else)                       d2h 0.42 n=2
# depth 2
# behavior_data_player_statistics_cleaned_final
  if Avg assists <= 6.60      then d2h 0.64 n=10
  if GoldPerMin > 360         then d2h 0.36 n=3
  (else)                       d2h 0.16 n=5
# depth 2
# behavior_data_student_dropout
  if FINAL_GRADE > 9          then d2h 0.67 n=31
  if NUMBER_OF_FAILURES > 0   then d2h 0.02 n=3
  if GRADE_2 > 8              then d2h 0.02 n=1
  (else)                       d2h 0.02 n=1
# depth 3
# behavior_data_WA_Fn-UseC_-HR-Employee-Attrition
  if YearsSinceLastPromotion <= 2 then d2h 0.63 n=27
  if JobLevel > 2             then d2h 0.29 n=13
  (else)                       d2h 0.31 n=2
# depth 2
# binary_config_billing10k
  if prepaid == 1             then d2h 0.57 n=21
  if editcustomerdetails != 0 then d2h 0.50 n=4
  if testcase6 == 0           then d2h 0.50 n=9
  if cheque != 0              then d2h 0.42 n=2
  (else)                       d2h 0.37 n=4
# depth 4
# binary_config_FFM-125-25-0.50-SAT-1
  if o_17 != 0                then d2h 0.64 n=15
  if o_1_1 != 0               then d2h 0.59 n=8
  if o_41 != 1                then d2h 0.52 n=7
  if o_43 != 0                then d2h 0.37 n=4
  (else)                       d2h 0.39 n=10
# depth 4
# behavior_data_all_players
  if Ball Control <= 63       then d2h 0.63 n=10
  if Jumping > 71             then d2h 0.27 n=19
  if Dribbling > 63           then d2h 0.43 n=11
  (else)                       d2h 0.57 n=1
# depth 3
# binary_config_FFM-250-50-0.50-SAT-1
  if g_2_1_8 != 0             then d2h 0.62 n=10
  if g_2_1_9 == 1             then d2h 0.55 n=15
  if g_45_4 != 0              then d2h 0.67 n=1
  if g_2_1_4 != 0             then d2h 0.46 n=9
  (else)                       d2h 0.40 n=7
# depth 4
# binary_config_Scrum10k
  if atd3 == 1                then d2h 0.62 n=18
  if t_15_minutes != 0        then d2h 0.60 n=3
  if ppo1 != 1                then d2h 0.56 n=6
  if t_5_minutes != 1         then d2h 0.54 n=4
  (else)                       d2h 0.45 n=13
# depth 4
# binary_config_Scrum1k
  if refinery_requirements != 0 then d2h 0.58 n=18
  (else)                       d2h 0.46 n=25
# depth 1
# config_Apache_AllMeasurements
  if keepAlive == 1           then d2h 0.64 n=12
  if handle == 1              then d2h 0.22 n=9
  if hostnameLookups == 0     then d2h 0.35 n=1
  if accessLog != 1           then d2h 0.28 n=1
  (else)                       d2h 0.15 n=4
# depth 4
# config_HSMGP_num
  if smoother_GSACBE == 1     then d2h 0.77 n=6
  if Post > 0.33              then d2h 0.34 n=17
  if NumCore <= 0.24          then d2h 0.30 n=17
  (else)                       d2h 0.41 n=3
# depth 3
# config_rs-6d-c3_obj1
  if Sorters <= 2             then d2h 0.17 n=18
  if Max_spout > 1000         then d2h 0.92 n=3
  if Emit_freq > 120          then d2h 0.37 n=2
  if Chunk_size > 100000      then d2h 0.40 n=12
  (else)                       d2h 0.34 n=5
# depth 4
# binary_config_FFM-500-100-0.50-SAT-1
  if g_15_6_17 == 1           then d2h 0.61 n=23
  if g_15_6_13 == 0           then d2h 0.54 n=7
  if g_15_6_11 != 1           then d2h 0.37 n=8
  if g_15_6_19 != 1           then d2h 0.49 n=1
  (else)                       d2h 0.52 n=2
# depth 4
# binary_config_FM-500-100-0.25-SAT-1
  if g_45_2 == 1              then d2h 0.60 n=18
  if g_45_1 == 1              then d2h 0.53 n=10
  if g_45_7 != 0              then d2h 0.49 n=5
  if g_14_9_6 != 0            then d2h 0.48 n=1
  (else)                       d2h 0.36 n=7
# depth 4
# config_rs-6d-c3_obj2
  if Sorters <= 2             then d2h 0.54 n=6
  if Chunk_size > 2000000     then d2h 0.37 n=2
  if Max_spout > 1000         then d2h 0.41 n=3
  if Emit_freq > 60           then d2h 0.37 n=7
  (else)                       d2h 0.37 n=25
# depth 4
# config_sol-6d-c2-obj1
  if Message_size <= 10000    then d2h 0.59 n=23
  if Max_spout <= 1           then d2h 0.17 n=7
  if Bolts <= 1               then d2h 0.17 n=3
  if Topology_level > 3       then d2h 0.17 n=8
  (else)                       d2h 0.17 n=7
# depth 4
# binary_config_FM-500-100-0.50-SAT-1
  if g_14_9_2 != 0            then d2h 0.61 n=16
  if g_45_2 != 0              then d2h 0.68 n=2
  if g_45_5 == 0              then d2h 0.51 n=17
  if g_45_9 != 0              then d2h 0.48 n=1
  (else)                       d2h 0.43 n=7
# depth 4
# config_SS-B
  if A > 2                    then d2h 0.66 n=8
  if B > 2                    then d2h 0.20 n=15
  (else)                       d2h 0.02 n=3
# depth 2
# config_SQL_AllMeasurements
  if sQLITE_TEMP_STOREtwo == 1 then d2h 0.66 n=3
  if sQLITE_TEMP_STOREone != 0 then d2h 0.56 n=6
  if sQLITE_TEMP_STOREzero != 0 then d2h 0.22 n=7
  if chooseSQLITE_TEMP_STORE != 1 then d2h 0.30 n=22
  (else)                       d2h 0.42 n=4
# depth 4
# config_SS-A
  if Spout_wait > 100         then d2h 0.81 n=1
  if Counters <= 14           then d2h 0.38 n=22
  if Spliters > 3             then d2h 0.30 n=21
  (else)                       d2h 0.29 n=3
# depth 3
# config_SS-D
  if Max_spout <= 1           then d2h 0.69 n=6
  if Spliters <= 3            then d2h 0.51 n=11
  if Counters > 9             then d2h 0.34 n=6
  (else)                       d2h 0.41 n=4
# depth 3
# config_SS-C
  if Spout_wait > 100         then d2h 0.68 n=3
  (else)                       d2h 0.34 n=39
# depth 1
# config_SS-E
  if Max_spout <= 10          then d2h 0.68 n=11
  if Counters <= 6            then d2h 0.44 n=20
  if Spliters > 1             then d2h 0.41 n=10
  (else)                       d2h 0.46 n=3
# depth 3
# config_SS-F
  if Max_spout <= 1           then d2h 0.67 n=6
  if Spliters > 3             then d2h 0.38 n=10
  if Counters > 15            then d2h 0.55 n=2
  (else)                       d2h 0.49 n=9
# depth 3
# config_SS-G
  if Max_spout <= 1           then d2h 0.68 n=6
  if Spliters > 3             then d2h 0.37 n=10
  if Counters > 15            then d2h 0.53 n=2
  (else)                       d2h 0.49 n=9
# depth 3
# config_SS-H
  if Multiplier > 2           then d2h 0.61 n=18
  (else)                       d2h 0.22 n=11
# depth 1
# config_SS-I
  if Count <= 1               then d2h 0.85 n=4
  if Spout > 2                then d2h 0.53 n=5
  if Buffer_size > 1050000    then d2h 0.37 n=16
  if Split > 2                then d2h 0.32 n=12
  (else)                       d2h 0.44 n=7
# depth 4
# config_SS-J
  if Sorters <= 3             then d2h 0.74 n=6
  if Spouts > 1               then d2h 0.53 n=6
  if Max_spout <= 1000        then d2h 0.48 n=18
  if Message_size > 10000     then d2h 0.29 n=1
  (else)                       d2h 0.29 n=14
# depth 4
# config_SS-K
  if Max_spout <= 2           then d2h 0.65 n=19
  if Spout_wait > 10          then d2h 0.56 n=2
  if Counters > 3             then d2h 0.38 n=11
  if Spliters > 1             then d2h 0.41 n=12
  (else)                       d2h 0.72 n=1
# depth 4
# config_SS-L
  if J > 0                    then d2h 0.66 n=18
  if H <= 0                   then d2h 0.59 n=11
  if K > 0                    then d2h 0.52 n=1
  if G > 0                    then d2h 0.32 n=4
  (else)                       d2h 0.15 n=6
# depth 4
# config_SS-M
  if crypt_blowfish == 1      then d2h 0.84 n=4
  if encryption != 0          then d2h 0.29 n=6
  if compressed_script != 0   then d2h 0.25 n=14
  if detailed_logging != 0    then d2h 0.27 n=1
  (else)                       d2h 0.27 n=14
# depth 4
# config_SS-O
  if delayedInnodbLogWrite != 0 then d2h 0.28 n=22
  if delayedInnodbLogFlush != 0 then d2h 0.60 n=9
  if InnodbBufferPoolSize > 8 then d2h 0.63 n=5
  if binaryLog != 1           then d2h 0.90 n=1
  (else)                       d2h 0.75 n=5
# depth 4
# config_SS-P
  if k == 1                   then d2h 0.65 n=25
  if h == 0                   then d2h 0.63 n=9
  if j != 1                   then d2h 0.13 n=6
  if g != 1                   then d2h 0.58 n=2
  (else)                       d2h 0.64 n=1
# depth 4
# config_SS-Q
  if rtQuality != 0           then d2h 0.23 n=29
  if bestQuality != 1         then d2h 0.68 n=7
  (else)                       d2h 0.78 n=5
# depth 2
# config_SS-R
  if columnTiling == 1        then d2h 0.65 n=17
  if bestQuality == 1         then d2h 0.60 n=9
  if goodQuality != 1         then d2h 0.41 n=4
  if Threads > 1              then d2h 0.31 n=8
  (else)                       d2h 0.34 n=3
# depth 4
# config_SS-S
  if Max_spout > 100          then d2h 0.60 n=13
  if Emit_freq > 120          then d2h 0.29 n=1
  if Sorters > 15             then d2h 0.33 n=3
  if Chunk_size > 1000000     then d2h 0.34 n=6
  (else)                       d2h 0.34 n=18
# depth 4
# binary_config_FM-500-100-0.75-SAT-1
  if g_14_9_2 != 0            then d2h 0.62 n=16
  if m_17_8 == 1              then d2h 0.56 n=8
  if g_14_9_1 == 1            then d2h 0.31 n=1
  if o_18 != 0                then d2h 0.36 n=6
  (else)                       d2h 0.46 n=12
# depth 4
# config_SS-T
  if ProcessorCount <= 1      then d2h 0.31 n=19
  if compressionZpaq != 0     then d2h 0.82 n=4
  if compression != 1         then d2h 0.29 n=3
  if compressionLzo != 0      then d2h 0.36 n=7
  (else)                       d2h 0.63 n=12
# depth 4
# config_SS-U
  if core2 != 1               then d2h 0.55 n=31
  if ref_1 != 0               then d2h 0.30 n=6
  if ref_9 != 0               then d2h 0.55 n=3
  (else)                       d2h 0.45 n=1
# depth 3
# binary_config_FM-500-100-1.00-SAT-1
  if g_22_3_14 == 1           then d2h 0.63 n=17
  if g_22_3_12 == 1           then d2h 0.49 n=10
  if o_9_1 != 0               then d2h 0.42 n=4
  if o_9_9 != 1               then d2h 0.41 n=9
  (else)                       d2h 0.35 n=4
# depth 4
# config_SS-V
  if ssl == 1                 then d2h 0.72 n=17
  if journalCompression != 0  then d2h 0.28 n=6
  if journalCommitInterval == 1 then d2h 0.44 n=2
  if dataCompression != 1     then d2h 0.10 n=8
  (else)                       d2h 0.24 n=8
# depth 4
# config_wc+rs-3d-c4-obj1
  if Max_spout <= 1           then d2h 0.10 n=4
  if Spliters > 2             then d2h 0.49 n=11
  if Counters > 6             then d2h 0.73 n=5
  (else)                       d2h 0.48 n=5
# depth 3
# config_wc+sol-3d-c4-obj1
  if Max_spout <= 1           then d2h 0.09 n=6
  if Counters > 3             then d2h 0.59 n=15
  (else)                       d2h 0.28 n=6
# depth 2
# config_wc-6d-c1-obj1
  if Max_spout > 10           then d2h 0.64 n=17
  if Spout_wait <= 1          then d2h 0.47 n=1
  if Counters > 1             then d2h 0.19 n=15
  if Spliters > 1             then d2h 0.15 n=6
  (else)                       d2h 0.11 n=3
# depth 4
# config_wc+wc-3d-c4-obj1
  if Max_spout <= 1           then d2h 0.08 n=6
  if Counters > 3             then d2h 0.60 n=15
  (else)                       d2h 0.25 n=6
# depth 2
# config_X264_AllMeasurements
  if ref_1 != 0               then d2h 0.13 n=30
  if ref_9 != 0               then d2h 0.86 n=6
  if no_mbtree != 0           then d2h 0.75 n=1
  (else)                       d2h 0.47 n=4
# depth 3
# financial_data_BankChurners
  if income_Category != $120K + then d2h 0.55 n=37
  (else)                       d2h 0.24 n=4
# depth 1
# financial_data_home_data_for_ml_course
  if neighborhood == Crawfor  then d2h 0.18 n=4
  if GARAGEYRBLT > 1950       then d2h 0.58 n=35
  (else)                       d2h 0.33 n=3
# depth 2
# config_SS-W
  if called_value_propagation == 1 then d2h 0.59 n=21
  if ee_instrument == 1       then d2h 0.57 n=7
  if pgo_memop_opt != 0       then d2h 0.36 n=3
  if basicaa != 0             then d2h 0.48 n=2
  (else)                       d2h 0.24 n=9
# depth 4
# config_SS-N
  if Crf <= 31.70             then d2h 0.62 n=21
  if Seek > 665               then d2h 0.31 n=17
  if Keyint > 275             then d2h 0.49 n=2
  if Rc_lookahead > 56        then d2h 0.71 n=1
  (else)                       d2h 0.73 n=1
# depth 4
# config_SS-X
  if simd_avoidUnaligned != 0 then d2h 0.86 n=4
  (else)                       d2h 0.21 n=38
# depth 1
# financial_data_WA_Fn-UseC_-Telco-Customer-Churn
  if internetService == Fiber_optic then d2h 0.74 n=10
  if deviceProtection != Yes  then d2h 0.17 n=31
  (else)                       d2h 0.65 n=1
# depth 2
# health_data_Life_Expectancy_Data
  if Polio <= 87              then d2h 0.59 n=11
  if Diphtheria <= 89         then d2h 0.35 n=1
  if Alcohol <= 3.84          then d2h 0.39 n=5
  if Life expectancy > 77.90  then d2h 0.13 n=12
  (else)                       d2h 0.31 n=13
# depth 4
# hpo_Health-ClosedIssues0000
  if Min_sample_leaves > 6    then d2h 0.74 n=15
  (else)                       d2h 0.13 n=27
# depth 1
# hpo_Health-ClosedIssues0001
  if criterion != absolute_error then d2h 0.37 n=38
  if Min_sample_leaves > 19   then d2h 0.74 n=2
  (else)                       d2h 0.74 n=3
# depth 2
# hpo_Health-ClosedIssues0002
  if criterion != absolute_error then d2h 0.74 n=9
  if Min_impurity_decrease > 3.25 then d2h 0.14 n=27
  if Max_depth > 7            then d2h 0.14 n=3
  if Min_sample_leaves > 9    then d2h 0.14 n=1
  (else)                       d2h 0.14 n=3
# depth 4
# hpo_Health-ClosedIssues0003
  if Min_sample_leaves <= 1   then d2h 0.92 n=6
  if Min_impurity_decrease > 0.25 then d2h 0.39 n=34
  (else)                       d2h 0.71 n=2
# depth 2
# financial_data_Loan
  if MonthlyIncome <= 4024.33 then d2h 0.64 n=13
  if Age <= 39                then d2h 0.57 n=8
  if LoanApproved <= 0        then d2h 0.50 n=8
  if BaseInterestRate > 0.22  then d2h 0.45 n=7
  (else)                       d2h 0.38 n=6
# depth 4
# hpo_Health-ClosedIssues0004
  if Min_sample_leaves <= 11  then d2h 0.67 n=9
  if criterion != poisson     then d2h 0.48 n=14
  if N_estimators <= 60       then d2h 0.45 n=3
  if Min_impurity_decrease > 0 then d2h 0.45 n=16
  (else)                       d2h 0.47 n=1
# depth 4
# hpo_Health-ClosedIssues0005
  if criterion != absolute_error then d2h 0.60 n=10
  if N_estimators > 150       then d2h 0.31 n=4
  if Min_sample_leaves <= 12  then d2h 0.25 n=24
  if Min_impurity_decrease > 3.25 then d2h 0.24 n=3
  (else)                       d2h 0.25 n=2
# depth 4
# hpo_Health-ClosedIssues0006
  if criterion == squared_error then d2h 0.81 n=5
  if Min_sample_leaves > 9    then d2h 0.41 n=24
  if Min_impurity_decrease > 0.50 then d2h 0.47 n=14
  (else)                       d2h 0.76 n=1
# depth 3
# hpo_Health-ClosedIssues0007
  if criterion == squared_error then d2h 0.68 n=5
  if Min_sample_leaves <= 6   then d2h 0.53 n=6
  if Min_impurity_decrease <= 2.25 then d2h 0.48 n=3
  if N_estimators > 10        then d2h 0.46 n=28
  (else)                       d2h 0.47 n=1
# depth 4
# hpo_Health-ClosedIssues0008
  if criterion != squared_error then d2h 0.61 n=14
  if Min_sample_leaves > 9    then d2h 0.59 n=3
  if Max_depth <= 13          then d2h 0.41 n=6
  if Min_impurity_decrease > 0.75 then d2h 0.19 n=16
  (else)                       d2h 0.52 n=1
# depth 4
# hpo_Health-ClosedIssues0009
  if Min_sample_leaves <= 7   then d2h 0.58 n=5
  if Max_depth > 15           then d2h 0.48 n=14
  if N_estimators > 10        then d2h 0.49 n=17
  (else)                       d2h 0.58 n=2
# depth 3
# hpo_Health-ClosedIssues0010
  if Min_sample_leaves <= 3   then d2h 0.64 n=6
  if criterion != absolute_error then d2h 0.50 n=6
  if Min_impurity_decrease <= 1.75 then d2h 0.48 n=2
  if Max_depth > 10           then d2h 0.37 n=21
  (else)                       d2h 0.37 n=8
# depth 4
# hpo_Health-ClosedIssues0011
  if criterion != absolute_error then d2h 0.74 n=9
  if Min_sample_leaves <= 11  then d2h 0.43 n=13
  if N_estimators > 150       then d2h 0.30 n=2
  if Min_impurity_decrease > 5.25 then d2h 0.06 n=9
  (else)                       d2h 0.18 n=8
# depth 4
# hpo_Health-ClosedPRs0000
  if criterion != poisson     then d2h 0.24 n=39
  (else)                       d2h 0.93 n=3
# depth 1
# hpo_Health-ClosedPRs0002
  if criterion != absolute_error then d2h 0.76 n=9
  if Min_impurity_decrease > 3.25 then d2h 0.11 n=27
  if Max_depth > 7            then d2h 0.11 n=3
  if Min_sample_leaves > 9    then d2h 0.11 n=1
  (else)                       d2h 0.11 n=3
# depth 4
# hpo_Health-ClosedPRs0003
  if criterion != absolute_error then d2h 0.76 n=9
  if Min_impurity_decrease <= 3.25 then d2h 0.10 n=7
  if Max_depth > 7            then d2h 0.10 n=11
  if Min_sample_leaves > 9    then d2h 0.10 n=14
  (else)                       d2h 0.10 n=2
# depth 4
# hpo_Health-ClosedPRs0004
  if criterion != absolute_error then d2h 0.70 n=9
  if Min_sample_leaves <= 9   then d2h 0.35 n=5
  if Min_impurity_decrease > 7.50 then d2h 0.25 n=6
  if N_estimators > 150       then d2h 0.35 n=2
  (else)                       d2h 0.34 n=22
# depth 4
# hpo_Health-ClosedPRs0005
  if criterion != absolute_error then d2h 0.76 n=9
  if Min_impurity_decrease > 5.25 then d2h 0.09 n=19
  if Max_depth > 7            then d2h 0.09 n=7
  if Min_sample_leaves > 9    then d2h 0.19 n=5
  (else)                       d2h 0.09 n=3
# depth 4
# health_data_Data_COVID19_Indonesia
  if Total_Cases_per_Million > 4397.22 then d2h 0.36 n=17
  if Total_Cases > 14511      then d2h 0.58 n=2
  (else)                       d2h 0.68 n=28
# depth 2
# hpo_Health-ClosedPRs0006
  if criterion == squared_error then d2h 0.74 n=5
  if Min_sample_leaves > 6    then d2h 0.43 n=31
  (else)                       d2h 0.48 n=5
# depth 2
# hpo_Health-ClosedPRs0007
  if criterion != absolute_error then d2h 0.65 n=9
  if Min_impurity_decrease > 9.50 then d2h 0.07 n=2
  if Min_sample_leaves <= 9   then d2h 0.42 n=5
  if N_estimators > 60        then d2h 0.43 n=19
  (else)                       d2h 0.18 n=8
# depth 4
# hpo_Health-ClosedPRs0008
  if criterion != absolute_error then d2h 0.56 n=38
  if Min_impurity_decrease > 0.25 then d2h 0.64 n=3
  (else)                       d2h 0.64 n=2
# depth 2
# hpo_Health-ClosedPRs0009
  if criterion != absolute_error then d2h 0.62 n=9
  if N_estimators <= 60       then d2h 0.50 n=5
  if Max_depth <= 3           then d2h 0.59 n=2
  if Min_sample_leaves > 17   then d2h 0.30 n=6
  (else)                       d2h 0.37 n=21
# depth 4
# hpo_Health-ClosedPRs0010
  if criterion != absolute_error then d2h 0.61 n=9
  if Max_depth > 7            then d2h 0.44 n=13
  if Min_impurity_decrease > 3.25 then d2h 0.43 n=18
  (else)                       d2h 0.41 n=4
# depth 3
# hpo_Health-ClosedPRs0011
  if criterion != absolute_error then d2h 0.71 n=9
  if Min_impurity_decrease <= 3.25 then d2h 0.21 n=7
  if Max_depth <= 7           then d2h 0.21 n=16
  if Min_sample_leaves > 9    then d2h 0.21 n=10
  (else)                       d2h 0.21 n=1
# depth 4
# hpo_Health-Commits0000
  if Min_sample_leaves > 6    then d2h 0.76 n=15
  (else)                       d2h 0.07 n=27
# depth 1
# hpo_Health-Commits0001
  if criterion != absolute_error then d2h 0.78 n=9
  if Min_impurity_decrease > 3.25 then d2h 0.08 n=27
  if Max_depth > 7            then d2h 0.25 n=3
  if Min_sample_leaves > 9    then d2h 0.08 n=1
  (else)                       d2h 0.08 n=3
# depth 4
# hpo_Health-Commits0002
  if criterion == absolute_error then d2h 0.49 n=34
  if Min_impurity_decrease > 3.25 then d2h 0.66 n=3
  (else)                       d2h 0.66 n=6
# depth 2
# binary_config_FFM-1000-200-0.50-SAT-1
  if g_8_3_6_14 != 1          then d2h 0.47 n=17
  if g_8_3_6_13 != 0          then d2h 0.61 n=10
  if g_8_3_6_10 != 0          then d2h 0.58 n=8
  if o_8_3_5 != 0             then d2h 0.53 n=4
  (else)                       d2h 0.43 n=3
# depth 4
# hpo_Health-Commits0003
  if criterion != absolute_error then d2h 0.62 n=19
  if Min_sample_leaves <= 11  then d2h 0.56 n=2
  if Min_impurity_decrease > 7.25 then d2h 0.35 n=14
  if N_estimators > 130       then d2h 0.28 n=8
  (else)                       d2h 0.49 n=1
# depth 4
# hpo_Health-Commits0004
  if Min_sample_leaves <= 9   then d2h 0.72 n=6
  if criterion == squared_error then d2h 0.36 n=8
  if Min_impurity_decrease > 6.25 then d2h 0.30 n=11
  if Max_depth > 12           then d2h 0.35 n=1
  (else)                       d2h 0.33 n=15
# depth 4
# hpo_Health-Commits0005
  if criterion != absolute_error then d2h 0.66 n=9
  (else)                       d2h 0.46 n=35
# depth 1
# hpo_Health-Commits0006
  if criterion != absolute_error then d2h 0.27 n=35
  if Min_impurity_decrease > 0.25 then d2h 0.75 n=3
  (else)                       d2h 0.82 n=2
# depth 2
# hpo_Health-Commits0007
  if Min_sample_leaves <= 3   then d2h 0.73 n=6
  if criterion != absolute_error then d2h 0.57 n=6
  (else)                       d2h 0.38 n=31
# depth 2
# misc_auto93
  if Volume > 121             then d2h 0.57 n=9
  if origin != 1              then d2h 0.31 n=21
  (else)                       d2h 0.42 n=2
# depth 2
# hpo_Health-Commits0009
  if criterion == absolute_error then d2h 0.69 n=5
  if Min_impurity_decrease <= 0.50 then d2h 0.55 n=1
  if N_estimators > 120       then d2h 0.28 n=11
  (else)                       d2h 0.26 n=29
# depth 3
# hpo_Health-Commits0008
  if Min_sample_leaves <= 8   then d2h 0.67 n=5
  if criterion != poisson     then d2h 0.56 n=9
  if Min_impurity_decrease <= 1 then d2h 0.59 n=1
  if Max_depth > 13           then d2h 0.38 n=17
  (else)                       d2h 0.47 n=12
# depth 4
# hpo_Health-Commits0010
  if criterion != absolute_error then d2h 0.66 n=27
  if Min_sample_leaves <= 14  then d2h 0.45 n=3
  if Min_impurity_decrease > 4.50 then d2h 0.29 n=7
  (else)                       d2h 0.27 n=3
# depth 3
# misc_Car_price_cleaned
  if ENGINESIZE > 0.34        then d2h 0.38 n=8
  (else)                       d2h 0.62 n=23
# depth 1
# hpo_Health-Commits0011
  if criterion != absolute_error then d2h 0.72 n=9
  if Min_sample_leaves > 16   then d2h 0.64 n=4
  if N_estimators > 190       then d2h 0.64 n=1
  (else)                       d2h 0.20 n=30
# depth 3
# process_nasa93dem
  if time != n                then d2h 0.69 n=4
  if data != l                then d2h 0.53 n=2
  if plex != h                then d2h 0.49 n=11
  (else)                       d2h 0.52 n=4
# depth 3
# misc_Wine_quality
  if Density > 1.00           then d2h 0.42 n=13
  if Sulphates > 0.51         then d2h 0.51 n=12
  if Volatileacidity > 0.64   then d2h 0.57 n=3
  if Citricacid > 0.43        then d2h 0.69 n=1
  (else)                       d2h 0.59 n=5
# depth 4
# process_coc1000
  if TIME > 3                 then d2h 0.56 n=36
  if FLEx > 2                 then d2h 0.52 n=3
  (else)                       d2h 0.34 n=3
# depth 2
# misc_multiLabel
  if FDP_method <= 1          then d2h 0.66 n=18
  if FANOUT_method > 6        then d2h 0.09 n=11
  (else)                       d2h 0.46 n=5
# depth 2
# process_pom3d
  if Criticality Modifier > 0.35 then d2h 0.66 n=14
  if Criticality > 0.24       then d2h 0.46 n=15
  if Plan > 0.55              then d2h 0.25 n=4
  (else)                       d2h 0.40 n=2
# depth 3
# process_pom3a
  if Dynamism > 0.21          then d2h 0.61 n=23
  if Initial Known <= 0.50    then d2h 0.56 n=7
  if Inter-Dependency <= 0.29 then d2h 0.31 n=5
  if Size > 0.34              then d2h 0.58 n=2
  (else)                       d2h 0.32 n=2
# depth 4
# process_pom3b
  if Size > 0.77              then d2h 0.69 n=6
  if Criticality > 0.83       then d2h 0.61 n=3
  if Culture > 0.60           then d2h 0.59 n=7
  if Team Size > 0.36         then d2h 0.38 n=16
  (else)                       d2h 0.48 n=10
# depth 4
# process_pom3c
  if Criticality Modifier > 0.39 then d2h 0.65 n=13
  if Culture > 0.33           then d2h 0.47 n=10
  if Initial Known > 0.87     then d2h 0.31 n=4
  if Inter-Dependency > 0.81  then d2h 0.47 n=2
  (else)                       d2h 0.44 n=13
# depth 4
# rl_A2C_Acrobot
  if Nsteps > 18              then d2h 0.22 n=1
  if Learninrate <= -3.66     then d2h 0.66 n=8
  if Maxgrad_norm <= 3.92     then d2h 0.61 n=9
  if Vfcoef > 0.80            then d2h 0.55 n=2
  (else)                       d2h 0.47 n=6
# depth 4
# rl_A2C_CartPole
  if Learning_rate <= -3.87   then d2h 0.62 n=12
  if Gamma > 0.96             then d2h 0.56 n=3
  if Lambda <= 0.92           then d2h 0.48 n=1
  if Vfcoef > 0.70            then d2h 0.41 n=10
  (else)                       d2h 0.46 n=4
# depth 4
# sales_data_accessories
  if source != Mom            then d2h 0.53 n=41
  (else)                       d2h 0.68 n=1
# depth 1
# sales_data_dress-up
  if dIY != No                then d2h 0.35 n=1
  (else)                       d2h 0.55 n=41
# depth 1
# process_xomo_ground
  if KLOC > 147.54            then d2h 0.52 n=14
  if RELY <= 3.22             then d2h 0.40 n=15
  if SITE <= 4.18             then d2h 0.27 n=4
  if CPLx > 2.31              then d2h 0.20 n=6
  (else)                       d2h 0.29 n=1
# depth 4
# process_xomo_flight
  if KLOC > 195.61            then d2h 0.65 n=14
  if AEXP <= 2.56             then d2h 0.42 n=16
  if PVOL > 3.26              then d2h 0.37 n=6
  (else)                       d2h 0.23 n=7
# depth 3
# process_xomo_osp
  if LTEx <= 2.08             then d2h 0.63 n=14
  if KLOC > 232.84            then d2h 0.50 n=3
  if PVOL <= 2.84             then d2h 0.25 n=11
  if PLEx > 1.85              then d2h 0.32 n=11
  (else)                       d2h 0.55 n=1
# depth 4
# sales_data_socks
  if Sell > 150               then d2h 0.62 n=9
  if Internal ID > 8930       then d2h 0.16 n=23
  (else)                       d2h 0.31 n=1
# depth 2
# sales_data_wallpaper
  if vFX_Type != NA           then d2h 0.77 n=1
  (else)                       d2h 0.49 n=29
# depth 1
# systems_BDBC
  if hAVE_CRYPTO != 0         then d2h 0.58 n=12
  if pS32K != 0               then d2h 0.27 n=5
  if hAVE_VERIFY == 0         then d2h 0.24 n=9
  if hAVE_REPLICATION != 1    then d2h 0.24 n=14
  (else)                       d2h 0.24 n=4
# depth 4
# binary_config_Scrum100k
  if atd8 == 1                then d2h 0.59 n=25
  if atd3 != 0                then d2h 0.56 n=4
  if atd5 == 0                then d2h 0.49 n=4
  if apo14 != 0               then d2h 0.50 n=3
  (else)                       d2h 0.42 n=7
# depth 4
# systems_deeparch
  if conv_2_num_filters == 1  then d2h 0.56 n=15
  if conv_1_num_filters != 0  then d2h 0.37 n=12
  if conv_3_num_filters != 0  then d2h 0.19 n=5
  if batch_size != 0          then d2h 0.13 n=1
  (else)                       d2h 0.10 n=8
# depth 4
# systems_HSQLDB
  if crypt_blowfish == 1      then d2h 0.89 n=9
  if crypt_aes != 1           then d2h 0.27 n=11
  (else)                       d2h 0.27 n=18
# depth 2
# systems_dconvert
  if web != 1                 then d2h 0.41 n=26
  (else)                       d2h 0.17 n=17
# depth 1
# sales_data_Marketing_Analytics
  if MNTGOLDPRODS <= 20       then d2h 0.66 n=8
  if MNTTOTAL > 263           then d2h 0.50 n=31
  (else)                       d2h 0.59 n=2
# depth 2
# systems_LLVM
  if inline != 0              then d2h 0.54 n=22
  if gvn == 1                 then d2h 0.38 n=4
  if licm != 0                then d2h 0.13 n=5
  if instcombine != 1         then d2h 0.04 n=10
  (else)                       d2h 0.18 n=1
# depth 4
# health_data_Medical_Data_and_Hospital_Readmissions
  if diabetesMed_Yes != FALSE then d2h 0.61 n=30
  if Num_medications > 10     then d2h 0.18 n=5
  if payer_code != FALSE      then d2h 0.18 n=4
  (else)                       d2h 0.41 n=3
# depth 3
# systems_redis
  if HashMaxZiplistEntries <= 446 then d2h 0.57 n=7
  if ActiveDefragIgnoreBytes <= 124 then d2h 0.49 n=11
  if ListMaxZiplistSize <= -4 then d2h 0.31 n=9
  if Hz > 435                 then d2h 0.28 n=1
  (else)                       d2h 0.24 n=14
# depth 4
# process_xomo_osp2
  if TOOL <= 2.16             then d2h 0.71 n=7
  if DATA > 2.98              then d2h 0.52 n=19
  (else)                       d2h 0.39 n=16
# depth 2
# systems_storm
  if topology.serialized.message.size.metrics != 0 then d2h 0.74 n=5
  if Message.size <= 10       then d2h 0.40 n=15
  if Topology.max.spout.pending <= 1 then d2h 0.23 n=14
  if topology.priority != 29  then d2h 0.23 n=3
  (else)                       d2h 0.23 n=6
# depth 4
# systems_PostgreSQL
  if fsync == 1               then d2h 0.51 n=15
  if fullPageWrites != 0      then d2h 0.33 n=7
  if TempBuffers <= 8         then d2h 0.32 n=15
  if trackActivities != 0     then d2h 0.31 n=4
  (else)                       d2h 0.36 n=1
# depth 4
# test_dataset120
  if Lcovfaulty <= 0.56       then d2h 0.70 n=11
  if Numobs > 49              then d2h 0.31 n=28
  (else)                       d2h 0.74 n=2
# depth 2
# test_dataset600
  if Bcovfixed > 0.79         then d2h 0.25 n=23
  (else)                       d2h 0.62 n=18
# depth 1
# systems_7z
  if Xval > 6                 then d2h 0.71 n=6
  if BlockSize > 2048         then d2h 0.25 n=1
  if mtOff != 0               then d2h 0.28 n=13
  if lZMA2 != 0               then d2h 0.26 n=3
  (else)                       d2h 0.27 n=17
# depth 4
# systems_exastencils
  if Poly_tileSize_y <= 10    then d2h 0.63 n=16
  if opt_unroll == 3          then d2h 0.33 n=3
  if Poly_tileSize_x > 16     then d2h 0.27 n=12
  if opt_useAddressPrecalc != 0 then d2h 0.20 n=4
  (else)                       d2h 0.47 n=6
# depth 4
# systems_x264
  if Crf <= 23.40             then d2h 0.76 n=18
  if Qp > 23                  then d2h 0.29 n=16
  (else)                       d2h 0.25 n=6
# depth 2
# systems_javagc
  if XXNewRatio > 8           then d2h 0.71 n=4
  (else)                       d2h 0.39 n=41
# depth 1

far_results.txt

# far (FastMap, cap=1024) vs ezr acquire20 -- hold-out win
# 129 optimiz, 20 reps, budget=50 check=5. far 79.2/37.5s ezr 79.7/127.9s
# dataset far ezr
auto93.csv                                  94  94
behavior_data_all_players.csv               89  95
behavior_data_player_statistics_cleaned_final.csv  86 100
behavior_data_student_dropout.csv           90  95
behavior_data_WA_Fn-UseC_-HR-Employee-Attrition.csv  83  94
binary_config_billing10k.csv                61  67
binary_config_FFM-1000-200-0.50-SAT-1.csv   55  55
binary_config_FFM-125-25-0.50-SAT-1.csv     69  66
binary_config_FFM-250-50-0.50-SAT-1.csv     62  69
binary_config_FFM-500-100-0.50-SAT-1.csv    67  61
binary_config_FM-500-100-0.25-SAT-1.csv     58  55
binary_config_FM-500-100-0.50-SAT-1.csv     59  71
binary_config_FM-500-100-0.75-SAT-1.csv     62  71
binary_config_FM-500-100-1.00-SAT-1.csv     66  63
binary_config_Scrum100k.csv                 47  54
binary_config_Scrum10k.csv                  60  64
binary_config_Scrum1k.csv                   62  75
config_Apache_AllMeasurements.csv          100 100
config_HSMGP_num.csv                        95 100
config_rs-6d-c3_obj1.csv                   100 100
config_rs-6d-c3_obj2.csv                   100 100
config_sol-6d-c2-obj1.csv                  100 100
config_SQL_AllMeasurements.csv              90  77
config_SS-A.csv                            100 100
config_SS-B.csv                             96 100
config_SS-C.csv                            100 100
config_SS-D.csv                             76  80
config_SS-E.csv                             95  92
config_SS-F.csv                             86  72
config_SS-G.csv                             76  77
config_SS-H.csv                             99 100
config_SS-I.csv                             93  98
config_SS-J.csv                            100 100
config_SS-K.csv                             96  96
config_SS-L.csv                             93  95
config_SS-M.csv                            100 100
config_SS-N.csv                             76  83
config_SS-O.csv                             93  94
config_SS-P.csv                            100  98
config_SS-Q.csv                            100 100
config_SS-R.csv                             74  74
config_SS-S.csv                            100 100
config_SS-T.csv                            100 100
config_SS-U.csv                             98 100
config_SS-V.csv                             98 100
config_SS-W.csv                             63  67
config_SS-X.csv                             97  95
config_wc-6d-c1-obj1.csv                   100 100
config_wc+rs-3d-c4-obj1.csv                100 100
config_wc+sol-3d-c4-obj1.csv               100 100
config_wc+wc-3d-c4-obj1.csv                100 100
config_X264_AllMeasurements.csv            100 100
financial_data_BankChurners.csv             65  57
financial_data_home_data_for_ml_course.csv  40  36
financial_data_Loan.csv                     67  69
financial_data_WA_Fn-UseC_-Telco-Customer-Churn.csv  99 100
health_data_Data_COVID19_Indonesia.csv      86  89
health_data_Life_Expectancy_Data.csv        96  97
health_data_Medical_Data_and_Hospital_Readmissions.csv 100  90
hpo_Health-ClosedIssues0000.csv            100 100
hpo_Health-ClosedIssues0001.csv             49  51
hpo_Health-ClosedIssues0002.csv            100 100
hpo_Health-ClosedIssues0003.csv             84  80
hpo_Health-ClosedIssues0004.csv             16  10
hpo_Health-ClosedIssues0005.csv             75  74
hpo_Health-ClosedIssues0006.csv             85  94
hpo_Health-ClosedIssues0007.csv             51  38
hpo_Health-ClosedIssues0008.csv             80  79
hpo_Health-ClosedIssues0009.csv             25  21
hpo_Health-ClosedIssues0010.csv             65  59
hpo_Health-ClosedIssues0011.csv            100 100
hpo_Health-ClosedPRs0000.csv               100 100
hpo_Health-ClosedPRs0002.csv                86  82
hpo_Health-ClosedPRs0003.csv               100 100
hpo_Health-ClosedPRs0004.csv                82  90
hpo_Health-ClosedPRs0005.csv               100 100
hpo_Health-ClosedPRs0006.csv                75  78
hpo_Health-ClosedPRs0007.csv                96  84
hpo_Health-ClosedPRs0008.csv                 4   2
hpo_Health-ClosedPRs0009.csv                59  59
hpo_Health-ClosedPRs0010.csv                43  40
hpo_Health-ClosedPRs0011.csv               100 100
hpo_Health-Commits0000.csv                 100 100
hpo_Health-Commits0001.csv                 100 100
hpo_Health-Commits0002.csv                  36  28
hpo_Health-Commits0003.csv                  69  75
hpo_Health-Commits0004.csv                  20   9
hpo_Health-Commits0005.csv                  60  51
hpo_Health-Commits0006.csv                  66  68
hpo_Health-Commits0007.csv                  67  65
hpo_Health-Commits0008.csv                  59  50
hpo_Health-Commits0009.csv                 100  99
hpo_Health-Commits0010.csv                  82  84
hpo_Health-Commits0011.csv                 100 100
misc_auto93.csv                             94  94
misc_Car_price_cleaned.csv                  43  69
misc_multiLabel.csv                        100 100
misc_Wine_quality.csv                       54  57
process_coc1000.csv                         41  43
process_nasa93dem.csv                       48  58
process_pom3a.csv                           69  70
process_pom3b.csv                           67  74
process_pom3c.csv                           60  51
process_pom3d.csv                           69  73
process_xomo_flight.csv                    100  96
process_xomo_ground.csv                     86  95
process_xomo_osp.csv                        85  98
process_xomo_osp2.csv                       66  75
rl_A2C_Acrobot.csv                          58  53
rl_A2C_CartPole.csv                         41  47
sales_data_accessories.csv                  14  13
sales_data_dress-up.csv                     38   8
sales_data_Marketing_Analytics.csv          61  52
sales_data_socks.csv                       100 100
sales_data_wallpaper.csv                    62  70
systems_7z.csv                             100 100
systems_BDBC.csv                           100 100
systems_dconvert.csv                       100 100
systems_deeparch.csv                       100 100
systems_exastencils.csv                     98  95
systems_HSQLDB.csv                         100 100
systems_javagc.csv                         100 100
systems_LLVM.csv                            98 100
systems_PostgreSQL.csv                     100 100
systems_redis.csv                           65  69
systems_storm.csv                          100 100
systems_x264.csv                            84  92
test_dataset120.csv                         81  92
test_dataset600.csv                         88  84

far_tree_d4.png

far_tree_deep.png

far_tree_full.png

far_trees.csv

far_trees.py

#!/usr/bin/env python3 -B
"""far_trees.py: 2 sorters on the SAME acquired labels.

Each rep: `landscape` (far) acquires labels; sort the held-out half
two ways -- a full binary tree (natural depth), and the best dfan FFT
(depth-D fan, via nuff.dfan) -- top-check, best, win. `top_tier` marks
the tie ("!" else "_"). CSV line: num,!|_ per sorter (nuff, dfan), name.

 eg: python3 -B far_trees.py -file ../optimiz/auto93.csv   (needs ../nuff)
     python3 -B far_trees.py --dfan -file ...   (show the dfan FFT)
"""
import sys, random
import far as F
from nuff import (Data, csv, disty, tree, fft, treePredict,
                  top_tier, say, BIG)

the = F.the
D, LFFT, LPLAIN = 4, 1, 3       # fft depth, fft leaf, plain-tree leaf

def sorters(d, lab, y):
  "2 predict fns over the same labels: full tree, dfan FFT."
  full = tree(d, lab, y, leaf=LPLAIN)
  f    = fft(tree(d, lab, y, leaf=LFFT, maxDepth=D))
  return [lambda r: treePredict(full, r),
          lambda r: treePredict(f, r)]

def holdoutN(data, n=2):
  win, W = F.wins(data), [[] for _ in range(n)]
  for _ in range(the.repeats):
    rows = F.some(data.rows, the.cap)
    h = len(rows)//2
    d, hold = F.clone(data, rows[:h]), rows[h:]
    y = F.memo(lambda r: disty(d, r))
    lab = F.landscape(d)
    for i, s in enumerate(sorters(d, lab, y)):
      W[i].append(win(F.pick(hold, s, data)))
  mu = [round(sum(w)/len(w)) for w in W]
  tier = top_tier({i: [-x for x in W[i]] for i in range(n)})  # hi=best
  return mu, ["!" if i in tier else "_" for i in range(n)]

def fftShow(data, t):
  "Print an FFT as a decision-list; return its depth (cue count)."
  d = 0
  while t.at is not None:
    nm = data.names[t.at]
    if   t.lo == t.hi: c = f"{nm} {'==' if t.yes else '!='} {say(t.lo)}"
    elif t.lo == -BIG: c = f"{nm} {'<=' if t.yes else '>'} {say(t.hi)}"
    else:              c = f"{nm} {'>=' if t.yes else '<'} {say(t.lo)}"
    print(f"  if {c:24} then d2h {t.left.mu:.2f} n={t.left.n}")
    t = t.right; d += 1
  print(f"  {'(else)':27}  d2h {t.mu:.2f} n={t.n}")
  return d

def dfanShow():
  "Acquire once; show the selected dfan FFT + depth."
  data = Data(csv(the.file))
  rows = [tuple(r) for r in F.some(data.rows, the.cap)]
  d = F.clone(data, rows[:len(rows)//2])
  y = F.memo(lambda r: disty(d, r))
  f = fft(tree(d, F.landscape(d), y, leaf=LFFT, maxDepth=D))
  print(f"# {the.file.split('/')[-1][:-4]}")
  print(f"# depth {fftShow(d, f)}")

def main():
  if "--dfan" in sys.argv: return dfanShow()
  mu, mark = holdoutN(Data(csv(the.file)))
  cells = [str(v) for pair in zip(mu, mark) for v in pair]
  print(",".join(cells) + "," + the.file.split("/")[-1][:-4])

if __name__ == "__main__":
  for f, v in zip(sys.argv, sys.argv[1:]):
    if f[:1] == "-" and (k := f[1:]) in vars(the):
      old = getattr(the, k)
      setattr(the, k, v if isinstance(old, str) else type(old)(v))
  random.seed(the.seed)
  main()

fft.gleam

//// fft.gleam -- port of fft.lisp (lithp) to Gleam.
//// Min-impurity FFT (fast-and-frugal) trees over CSV data.
//// (c) 2026 Tim Menzies timm@ieee.org, MIT license.
////
//// UNTESTED: no gleam toolchain on the porting host. To run:
////   gleam new fftproj && cd fftproj
////   gleam add simplifile
////   cp fft.gleam src/fftproj.gleam   (rename module main)
////   gleam run
//// Needs the `simplifile` package for file IO; rest is stdlib.
//// Lisp's defmethod num/hash dispatch -> the `Col` variant.
//// Lisp's mixed row cells (num | str | ?) -> the `V` variant.
//// A tree is the FFT chain that `grows` builds: each Node is one
//// cut whose "yes" side exits to a leaf, "no" side continues.

import gleam/dict.{type Dict}
import gleam/float
import gleam/int
import gleam/io
import gleam/list
import gleam/option.{type Option, None, Some}
import gleam/string
import simplifile

// ---- settings ------------------------------------------------
const p = 2.0

const bins = 7

const depth = 4

const big = 1.0e32

const file = "../optimiz/auto93.csv"

// ---- core types ----------------------------------------------
/// A cell value: number, symbol, or missing ("?").
pub type V {
  Num(Float)
  Sym(String)
  Skip
}

/// A column summary: a numeric (n, mu, m2) or a symbol counts dict.
pub type Col {
  NumC(n: Float, mu: Float, m2: Float)
  SymC(Dict(String, Float))
}

/// A split candidate carrying the y-summary of its "yes" group.
pub type Cut {
  NumCut(at: Int, lo: Float, hi: Float, leaf: Col)
  SymCut(at: Int, val: String, leaf: Col)
}

/// An FFT: a leaf y-summary, or a cut whose no-side continues.
pub type Tree {
  Leaf(Col)
  Node(Cut, Tree)
}

pub type Data {
  Data(
    names: List(String),
    x: List(Int),
    y: List(Int),
    goal: Dict(Int, Float),
    cols: Dict(Int, Col),
    rows: List(List(V)),
  )
}

// ---- erlang math (no exp/pow/sqrt in gleam stdlib) -----------
@external(erlang, "math", "exp")
fn exp(x: Float) -> Float

@external(erlang, "math", "pow")
fn pow(x: Float, y: Float) -> Float

@external(erlang, "math", "sqrt")
fn sqrt(x: Float) -> Float

// ---- tiny helpers --------------------------------------------
fn num() -> Col {
  NumC(0.0, 0.0, 0.0)
}

fn sym() -> Col {
  SymC(dict.new())
}

fn mu(c: Col) -> Float {
  case c {
    NumC(_, m, _) -> m
    SymC(_) -> 0.0
  }
}

fn n_of(c: Col) -> Float {
  case c {
    NumC(n, _, _) -> n
    SymC(d) -> list.fold(dict.values(d), 0.0, fn(a, v) { a +. v })
  }
}

fn at_of(c: Cut) -> Int {
  case c {
    NumCut(a, _, _, _) -> a
    SymCut(a, _, _) -> a
  }
}

fn leaf_of(c: Cut) -> Col {
  case c {
    NumCut(_, _, _, l) -> l
    SymCut(_, _, l) -> l
  }
}

fn get(row: List(V), at: Int) -> V {
  case list.drop(row, at) {
    [v, ..] -> v
    [] -> Skip
  }
}

fn nth(xs: List(a), at: Int, default: a) -> a {
  case list.drop(xs, at) {
    [v, ..] -> v
    [] -> default
  }
}

fn butlast(xs: List(a)) -> List(a) {
  case list.reverse(xs) {
    [_, ..t] -> list.reverse(t)
    [] -> []
  }
}

fn r2(x: Float) -> Float {
  int.to_float(float.round(x *. 100.0)) /. 100.0
}

// ---- 1. columns ----------------------------------------------
fn sd(c: Col) -> Float {
  case c {
    NumC(n, _, m2) ->
      case n <. 2.0 {
        True -> 0.0
        False -> sqrt(float.max(0.0, m2) /. { n -. 1.0 })
      }
    SymC(_) -> 0.0
  }
}

fn welford(c: Col, v: Float, w: Float) -> Col {
  case c {
    NumC(n0, mu0, m20) -> {
      let n = n0 +. w
      case n <. 1.0 {
        True -> num()
        False -> {
          let d = v -. mu0
          let mu1 = mu0 +. w *. d /. n
          NumC(n, mu1, m20 +. w *. d *. { v -. mu1 })
        }
      }
    }
    SymC(_) -> c
  }
}

fn add_w(c: Col, v: V, w: Float) -> Col {
  case v, c {
    Skip, _ -> c
    Num(x), NumC(_, _, _) -> welford(c, x, w)
    Sym(s), SymC(d) ->
      SymC(dict.upsert(d, s, fn(o) {
        case o {
          Some(k) -> k +. w
          None -> w
        }
      }))
    _, _ -> c
  }
}

fn add(c: Col, v: V) -> Col {
  add_w(c, v, 1.0)
}

fn norm(c: Col, v: Float) -> Float {
  case c {
    NumC(_, m, _) -> {
      let z = { v -. m } /. { sd(c) +. 1.0e-32 }
      1.0 /. { 1.0 +. exp(-1.7 *. float.max(-3.0, float.min(3.0, z))) }
    }
    SymC(_) -> v
  }
}

fn mix(i: Col, j: Col, w: Float) -> Col {
  case i, j {
    NumC(ni, mui, m2i), NumC(nj, muj, m2j) -> {
      let m = ni +. w *. nj
      let d = muj -. mui
      case m <. 1.0 {
        True -> num()
        False ->
          NumC(
            m,
            { ni *. mui +. w *. nj *. muj } /. m,
            m2i +. w *. m2j +. w *. d *. d *. ni *. nj /. m,
          )
      }
    }
    SymC(a), SymC(b) ->
      SymC(dict.fold(b, a, fn(acc, k, v) {
        dict.upsert(acc, k, fn(o) {
          case o {
            Some(x) -> x +. w *. v
            None -> w *. v
          }
        })
      }))
    _, _ -> i
  }
}

// ---- 2. data -------------------------------------------------
fn col(d: Data, at: Int) -> Col {
  let assert Ok(c) = dict.get(d.cols, at)
  c
}

fn goal_get(d: Data, at: Int) -> Float {
  let assert Ok(g) = dict.get(d.goal, at)
  g
}

fn first_char(s: String) -> String {
  case string.pop_grapheme(s) {
    Ok(#(c, _)) -> c
    Error(_) -> ""
  }
}

fn last_char(s: String) -> String {
  string.slice(s, string.length(s) - 1, 1)
}

fn is_upper(ch: String) -> Bool {
  string.uppercase(ch) == ch && string.lowercase(ch) != ch
}

fn role(d: Data, s: String, at: Int) -> Data {
  let c = case is_upper(first_char(s)) {
    True -> num()
    False -> sym()
  }
  let cols = dict.insert(d.cols, at, c)
  case last_char(s) {
    "X" -> Data(..d, cols: cols)
    "+" ->
      Data(
        ..d,
        cols: cols,
        y: list.append(d.y, [at]),
        goal: dict.insert(d.goal, at, 1.0),
      )
    "-" | "!" ->
      Data(
        ..d,
        cols: cols,
        y: list.append(d.y, [at]),
        goal: dict.insert(d.goal, at, 0.0),
      )
    _ -> Data(..d, cols: cols, x: list.append(d.x, [at]))
  }
}

fn build(names: List(String), rows: List(List(V))) -> Data {
  let init = Data(names, [], [], dict.new(), dict.new(), [])
  let d = list.index_fold(names, init, fn(acc, name, at) { role(acc, name, at) })
  let cols =
    list.fold(rows, d.cols, fn(cs, row) {
      list.index_fold(row, cs, fn(cc, v, at) {
        case dict.get(cc, at) {
          Ok(c) -> dict.insert(cc, at, add(c, v))
          Error(_) -> cc
        }
      })
    })
  Data(..d, cols: cols, rows: rows)
}

fn thing(s: String) -> V {
  case s {
    "?" -> Skip
    _ ->
      case float.parse(s) {
        Ok(f) -> Num(f)
        Error(_) ->
          case int.parse(s) {
            Ok(k) -> Num(int.to_float(k))
            Error(_) -> Sym(s)
          }
      }
  }
}

fn cells(line: String) -> List(String) {
  string.split(line, ",") |> list.map(string.trim)
}

fn read_csv(path: String) -> List(List(String)) {
  let assert Ok(txt) = simplifile.read(path)
  string.split(txt, "\n")
  |> list.map(string.trim)
  |> list.filter(fn(l) { l != "" && !string.starts_with(l, "#") })
  |> list.map(cells)
}

fn data(path: String) -> Data {
  let assert [header, ..body] = read_csv(path)
  build(header, list.map(body, fn(r) { list.map(r, thing) }))
}

// ---- 3. discretization ---------------------------------------
fn bin(c: Col, v: Float) -> Int {
  float.truncate(int.to_float(bins) *. norm(c, v))
}

fn cuts_at(c: Col, rows: List(List(V)), ys: List(Float), at: Int) -> List(Cut) {
  case c {
    NumC(_, _, _) -> {
      let #(b, hi) =
        list.fold(list.zip(rows, ys), #(dict.new(), dict.new()), fn(acc, ry) {
          let #(bmap, himap) = acc
          let #(r, y1) = ry
          case get(r, at) {
            Num(v) -> {
              let k = bin(c, v)
              let cur = case dict.get(bmap, k) {
                Ok(cc) -> cc
                Error(_) -> num()
              }
              let oldhi = case dict.get(himap, k) {
                Ok(h) -> h
                Error(_) -> 0.0 -. big
              }
              #(
                dict.insert(bmap, k, add(cur, Num(y1))),
                dict.insert(himap, k, float.max(oldhi, v)),
              )
            }
            _ -> acc
          }
        })
      let keys = dict.keys(b) |> list.sort(int.compare)
      let #(_, out) =
        list.fold(butlast(keys), #(num(), []), fn(st, k) {
          let #(l, acc) = st
          let leaf = mix(l, nth_col(b, k), 1.0)
          let h = case dict.get(hi, k) {
            Ok(v) -> v
            Error(_) -> 0.0
          }
          #(leaf, [NumCut(at, 0.0 -. big, h, leaf), ..acc])
        })
      list.reverse(out)
    }
    SymC(_) -> {
      let b =
        list.fold(list.zip(rows, ys), dict.new(), fn(bmap, ry) {
          let #(r, y1) = ry
          case get(r, at) {
            Sym(s) -> {
              let cur = case dict.get(bmap, s) {
                Ok(cc) -> cc
                Error(_) -> num()
              }
              dict.insert(bmap, s, add(cur, Num(y1)))
            }
            _ -> bmap
          }
        })
      dict.fold(b, [], fn(acc, s, leaf) { [SymCut(at, s, leaf), ..acc] })
    }
  }
}

fn nth_col(d: Dict(Int, Col), k: Int) -> Col {
  case dict.get(d, k) {
    Ok(c) -> c
    Error(_) -> num()
  }
}

fn cuts(d: Data, rows: List(List(V)), y: fn(List(V)) -> Float) -> List(Cut) {
  let ys = list.map(rows, y)
  list.flat_map(d.x, fn(at) { cuts_at(col(d, at), rows, ys, at) })
}

// ---- 4. grow trees -------------------------------------------
fn mink(xs: List(Float)) -> Float {
  let count = int.to_float(list.length(xs))
  pow(
    list.fold(xs, 0.0, fn(a, x) { a +. pow(float.absolute_value(x), p) })
      /. count,
    1.0 /. p,
  )
}

fn disty(d: Data, row: List(V)) -> Float {
  mink(
    list.map(d.y, fn(at) {
      let g = goal_get(d, at)
      case get(row, at) {
        Num(x) -> norm(col(d, at), x) -. g
        _ -> 0.0 -. g
      }
    }),
  )
}

fn has(cut: Cut, v: V) -> Bool {
  case cut, v {
    _, Skip -> True
    NumCut(_, lo, hi, _), Num(x) -> lo <=. x && x <=. hi
    SymCut(_, val, _), Sym(s) -> s == val
    _, _ -> False
  }
}

fn pick(cs: List(Cut), keep: fn(Float, Float) -> Bool) -> Cut {
  let assert [head, ..] = cs
  list.fold(cs, head, fn(best, c) {
    case keep(mu(leaf_of(c)), mu(leaf_of(best))) {
      True -> c
      False -> best
    }
  })
}

fn splits(
  d: Data,
  root: Data,
  y: fn(List(V)) -> Float,
) -> List(#(String, Cut)) {
  let enough = pow(int.to_float(list.length(root.rows)), 0.33)
  let cs =
    cuts(d, d.rows, y)
    |> list.filter(fn(c) { n_of(leaf_of(c)) >. enough })
  case cs {
    [] -> []
    _ ->
      [#("0", fn(a, b) { a <. b }), #("1", fn(a, b) { a >. b })]
      |> list.filter_map(fn(bp) {
        let #(bit, keep) = bp
        let cut = pick(cs, keep)
        let no =
          list.filter(d.rows, fn(r) { !has(cut, get(r, at_of(cut))) })
        case no {
          [] -> Error(Nil)
          _ -> Ok(#(bit, cut))
        }
      })
  }
}

fn adds_y(rows: List(List(V)), y: fn(List(V)) -> Float) -> Col {
  list.fold(rows, num(), fn(c, r) { add(c, Num(y(r))) })
}

fn grows(
  d: Data,
  y: fn(List(V)) -> Float,
  root: Data,
  d_left: Int,
) -> List(#(String, Tree)) {
  let sub = case d_left > 0 {
    True ->
      list.flat_map(splits(d, root, y), fn(s) {
        let #(bit, cut) = s
        let no = list.filter(d.rows, fn(r) { !has(cut, get(r, at_of(cut))) })
        let kid = build(d.names, no)
        list.map(grows(kid, y, root, d_left - 1), fn(bt) {
          let #(bias, r) = bt
          #(bit <> bias, Node(cut, r))
        })
      })
    False -> []
  }
  case sub {
    [] -> [#("", Leaf(adds_y(d.rows, y)))]
    _ -> sub
  }
}

// ---- 5. use trees --------------------------------------------
fn predict(t: Tree, row: List(V)) -> Float {
  case t {
    Leaf(c) -> mu(c)
    Node(cut, rest) ->
      case has(cut, get(row, at_of(cut))) {
        True -> mu(leaf_of(cut))
        False -> predict(rest, row)
      }
  }
}

fn err(t: Tree, rows: List(List(V)), y: fn(List(V)) -> Float) -> Float {
  list.fold(rows, 0.0, fn(a, r) {
    a +. float.absolute_value(y(r) -. predict(t, r))
  })
  /. int.to_float(list.length(rows))
}

fn tune(
  cands: List(Tree),
  rows: List(List(V)),
  y: fn(List(V)) -> Float,
) -> Tree {
  let assert [head, ..] = cands
  list.fold(cands, head, fn(best, t) {
    case err(t, rows, y) <. err(best, rows, y) {
      True -> t
      False -> best
    }
  })
}

fn rule(d: Data, cut: Cut) -> String {
  let name = nth(d.names, at_of(cut), "")
  case cut {
    SymCut(_, val, _) -> name <> " == " <> val
    NumCut(_, lo, hi, _) ->
      case lo == 0.0 -. big {
        True -> name <> " <= " <> float.to_string(r2(hi))
        False -> name <> " >= " <> float.to_string(r2(lo))
      }
  }
}

fn show(d: Data, t: Tree) -> Nil {
  case t {
    Leaf(c) ->
      io.println(
        "leaf  d2h "
        <> float.to_string(r2(mu(c)))
        <> " n="
        <> int.to_string(float.truncate(n_of(c))),
      )
    Node(cut, rest) -> {
      let l = leaf_of(cut)
      io.println(
        "if "
        <> rule(d, cut)
        <> " then d2h "
        <> float.to_string(r2(mu(l)))
        <> " n="
        <> int.to_string(float.truncate(n_of(l))),
      )
      show(d, rest)
    }
  }
}

// ---- 6. main -------------------------------------------------
pub fn main() {
  let d = data(file)
  let y = fn(r) { disty(d, r) }
  let trees = grows(d, y, d, depth) |> list.map(fn(bt) { bt.1 })
  show(d, tune(trees, d.rows, y))
}

fft.nim

# fft.nim -- fft.lisp (lithp) ported to Nim. MIT, T.Menzies.
# Min-impurity fast-and-frugal trees over CSV.  nim r fft.nim
import std/[math, tables, strutils, sequtils, algorithm]

const                                      # settings
  P = 2.0
  Bins = 7
  Depth = 4
  Big = 1e32
  File = "../optimiz/auto93.csv"

type
  Cell = object                            # one row value
    case skip: bool
    of true: discard
    of false:
      f: float
      s: string
  Col = object                             # num or sym summary
    case isNum: bool
    of true:
      n, mu, m2: float
    of false:
      counts: Table[string, float]
  Cut = object                             # a split + its leaf
    at: int
    lo, hi: float
    sv: string
    leaf: Col
  Tree = ref object                        # FFT: leaf, or cut+rest
    cut: Cut
    rest: Tree                             # nil rest => leaf
  Data = object
    names: seq[string]
    x, y: seq[int]
    goal: Table[int, float]
    cols: Table[int, Col]
    rows: seq[seq[Cell]]
  YFun = proc(r: seq[Cell]): float

# --- cells & columns -----------------------------------------
func num(): Col = Col(isNum: true)
func sym(): Col = Col(isNum: false)
func f(x: float): Cell = Cell(skip: false, f: x)
func skip(): Cell = Cell(skip: true)

func mu(c: Col): float = (if c.isNum: c.mu else: 0.0)
func n(c: Col): float =
  if c.isNum: c.n else: sum(toSeq c.counts.values)

func sd(c: Col): float =
  if c.isNum and c.n >= 2: sqrt(max(0.0, c.m2)/(c.n-1)) else: 0

func add(c: Col, v: Cell, w = 1.0): Col =
  result = c
  if v.skip: return
  if c.isNum:
    let m = c.n + w
    if m < 1: return num()
    let d = v.f - c.mu
    result.n = m
    result.mu = c.mu + w*d/m
    result.m2 = c.m2 + w*d*(v.f - result.mu)
  else:
    result.counts[v.s] = c.counts.getOrDefault(v.s) + w

func norm(c: Col, x: float): float =
  let z = (x - c.mu)/(sd(c) + 1e-32)
  1.0/(1.0 + exp(-1.7*max(-3.0, min(3.0, z))))

func mix(i, j: Col, w = 1.0): Col =
  if i.isNum:
    let m = i.n + w*j.n
    if m < 1: return num()
    let d = j.mu - i.mu
    result = Col(isNum: true, n: m,
        mu: (i.n*i.mu + w*j.n*j.mu)/m,
        m2: i.m2 + w*j.m2 + w*d*d*i.n*j.n/m)
  else:
    result = i
    for k, v in j.counts:
      result.counts[k] = i.counts.getOrDefault(k) + w*v

# --- read a CSV into a Data ----------------------------------
func thing(s: string): Cell =
  if s == "?": skip()
  else:
    try: f(parseFloat s)
    except ValueError: Cell(skip: false, s: s)

proc readCsv(path: string): seq[seq[string]] =
  for ln in readFile(path).splitLines:
    let l = ln.strip
    if l.len > 0 and l[0] != '#':
      result.add l.split(',').mapIt(it.strip)

func role(d: var Data, s: string, at: int) =
  d.cols[at] = if s[0] in {'A'..'Z'}: num() else: sym()
  case s[^1]
  of 'X': discard
  of '+', '-', '!':
    d.y.add at
    d.goal[at] = if s[^1] == '+': 1.0 else: 0.0
  else: d.x.add at

func build(names: seq[string], rows: seq[seq[Cell]]): Data =
  result.names = names
  result.rows = rows
  for at, s in names: role(result, s, at)
  for row in rows:
    for at, v in row:
      result.cols[at] = add(result.cols[at], v)

proc data(path: string): Data =
  let raw = readCsv(path)
  build(raw[0], raw[1..^1].mapIt(it.mapIt(thing it)))

# --- distance to ideal ---------------------------------------
func at(row: seq[Cell], i: int): Cell =
  if i < row.len: row[i] else: skip()

func disty(d: Data, row: seq[Cell]): float =
  var s = 0.0
  for i in d.y:
    let c = row.at(i)
    let g = d.goal[i]
    s += pow(abs((if c.skip: 0.0 else: norm(d.cols[i], c.f)) - g), P)
  pow(s/float(d.y.len), 1.0/P)

# --- candidate cuts per x-column -----------------------------
func bin(c: Col, x: float): int = int floor(float(Bins)*norm(c, x))

func cutsAt(c: Col, rows: seq[seq[Cell]],
            ys: seq[float], at: int): seq[Cut] =
  if c.isNum:
    var leaves: Table[int, Col]
    var hi: Table[int, float]
    for i, r in rows:
      let v = r.at(at)
      if not v.skip:
        let k = bin(c, v.f)
        leaves[k] = add(leaves.getOrDefault(k, num()), f(ys[i]))
        hi[k] = max(hi.getOrDefault(k, -Big), v.f)
    var l = num()
    for k in toSeq(leaves.keys).sorted[0..^2]:   # butlast
      l = mix(l, leaves[k])
      result.add Cut(at: at, lo: -Big, hi: hi[k], leaf: l)
  else:
    var leaves: Table[string, Col]
    for i, r in rows:
      let v = r.at(at)
      if not v.skip:
        leaves[v.s] = add(leaves.getOrDefault(v.s, num()), f(ys[i]))
    for s, leaf in leaves:
      result.add Cut(at: at, sv: s, leaf: leaf)

func has(cut: Cut, v: Cell): bool =
  if v.skip: true
  elif cut.sv.len > 0: v.s == cut.sv
  else: cut.lo <= v.f and v.f <= cut.hi

# --- grow every FFT, keep the most accurate ------------------
proc grows(d: Data, y: YFun, root: Data,
           left: int): seq[(string, Tree)] =
  if left > 0:
    let enough = pow(float(root.rows.len), 0.33)
    let ys = d.rows.mapIt(y(it))
    var cs: seq[Cut]
    for i in d.x:
      for c in cutsAt(d.cols[i], d.rows, ys, i):
        if n(c.leaf) > enough: cs.add c
    if cs.len > 0:
      for big in [false, true]:                  # least, then most
        var cut = cs[0]
        for c in cs:
          if (mu(c.leaf) > mu(cut.leaf)) == big: cut = c
        let no = d.rows.filterIt(not has(cut, it.at(cut.at)))
        if no.len > 0:
          for (bias, r) in grows(build(d.names, no), y, root, left-1):
            result.add ($int(big) & bias,
                        Tree(cut: cut, rest: r))
  if result.len == 0:
    var leaf = num()
    for r in d.rows: leaf = add(leaf, f(y(r)))
    result = @[("", Tree(cut: Cut(leaf: leaf), rest: nil))]

func predict(t: Tree, row: seq[Cell]): float =
  if t.rest == nil: mu(t.cut.leaf)
  elif has(t.cut, row.at(t.cut.at)): mu(t.cut.leaf)
  else: predict(t.rest, row)

proc err(t: Tree, rows: seq[seq[Cell]], y: YFun): float =
  var s = 0.0
  for r in rows: s += abs(y(r) - predict(t, r))
  s/float(rows.len)

# --- show the chosen tree ------------------------------------
func rule(d: Data, cut: Cut): string =
  let nm = d.names[cut.at]
  if cut.sv.len > 0: nm & " == " & cut.sv
  elif cut.lo == -Big: nm & " <= " & cut.hi.formatFloat(ffDecimal, 2)
  else: nm & " >= " & cut.lo.formatFloat(ffDecimal, 2)

proc show(d: Data, t: Tree) =
  let l = t.cut.leaf
  if t.rest == nil:
    echo "leaf  d2h ", mu(l).formatFloat(ffDecimal, 2), " n=", int n(l)
  else:
    echo "if ", rule(d, t.cut), " then d2h ",
         mu(l).formatFloat(ffDecimal, 2), " n=", int n(l)
    show(d, t.rest)

proc main() =
  let d = data(File)
  let y: YFun = proc(r: seq[Cell]): float = disty(d, r)
  let trees = grows(d, y, d, Depth).mapIt(it[1])
  show d, trees.foldl(if err(b, d.rows, y) < err(a, d.rows, y): b
                      else: a)

main()

fft.py

#!/usr/bin/env python3 -B
"""fft.py: fast-frugal multi-objective tree.
(c) 2025 T. Menzies, MIT. needs lib.py.

No cut search: split each numeric at its mean (x<=mu),
each sym by value; score a bin by mean d2h. A tree is a
frugal CHAIN: take the best (or worst) bin as a leaf,
recurse on the rest. Keep the chain of least error.

Options:
 -s seed     seed=1234567891
 -p dist exp  p=2
 -d depth     depth=4
 -R Round     Round=2
 -f file      file=/Users/timm/gits/moot/optimize/misc/auto93.csv
"""
from lib import *
opts(__doc__)

def cuts(data, rows, y):         # (mu, at, lo, hi, leaf)
  out = []
  for at in data.x:
    c, ys = data.cols[at], {}
    for r in rows:
      if (v := r[at]) == "?": continue
      k = v if symp(c) else v <= c[1]      # sym val | x<=mu
      ys[k] = add(ys.get(k, (0,0,0)), y(r))
    for k, s in ys.items():
      lo, hi = ((k, k) if symp(c) else
                (-BIG, c[1]) if k else (c[1], BIG))
      out.append((s[1], at, lo, hi, s))
  return out

def statOf(rows, y):             # leaf: (n,mu,m2) of y
  s = (0, 0, 0)
  for r in rows: s = add(s, y(r))
  return s

def kids(rows, at, lo, hi):      # split rows on a condition
  yes, no = [], []
  for r in rows:
    v = r[at]
    (yes if v=="?" or lo <= v <= hi else no).append(r)
  return yes, no

def grow(data, y, root, d):      # yield candidate chains
  sub = False
  cs  = sorted(cuts(data, data.rows, y)) if d<=the.depth else []
  if cs:
    for how, (_, at, lo, hi, leaf) in enumerate((cs[-1], cs[0])):
      yes, no = kids(data.rows, at, lo, hi)
      if len(yes) > len(root.rows)**.33 and no:
        for right in grow(clone(data, no), y, root, d+1):
          sub = True
          yield o(at=at, lo=lo, hi=hi, left=leaf,
                  bias=how, right=right)
  if not sub:
    yield statOf(data.rows, y)

def predict(t, row):             # walk chain to a leaf mu
  while not isinstance(t, tuple):
    v = row[t.at]
    t = t.left if v=="?" or t.lo <= v <= t.hi else t.right
  return t[1]

def tune(cands, rows, y):        # chain of least mean error
  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 isinstance(t, tuple):
    print("%-33s leaf  d2h %.2f n=%d" % ("", t[1], t[0]))
    return
  nm = data.names[t.at]
  if   t.lo == t.hi: c = f"{nm} == {t.lo}"
  elif t.lo == -BIG: c = f"{nm} <= {qty(t.hi)}"
  else:              c = f"{nm} >= {qty(t.lo)}"
  L = t.left
  print("if %-30s then d2h %.2f n=%d" % (c, L[1], L[0]))
  show(data, t.right)

if __name__ == "__main__":
  random.seed(the.seed)
  data = Data(csv(the.file))
  y    = lambda r: disty(data, r)
  show(data, tune(list(grow(data, y, data, 1)), data.rows, y))

fft1.py

#!/usr/bin/env python3 -B
"""
fft1.py, random-cluster forest engine + confusion (library)
(c) 2025, Tim Menzies <timm@ieee.org>, MIT license

Generic services: Data, disty, tree (random axis-cut cluster),
treeLeaf (router), treeShow (printer), confused (pd/pf/.. from
(want,got) pairs), cli/the. No task knowledge -- see compas.py.

Options:
 -s --seed  random seed       seed=1234567891
 -p --p     distance exponent p=2
 -R --Round repr decimals     Round=2
 -S --stop  leaf size         stop=None
 -n --N     demo row sample   N=50
 -f --file  data file
            file=/Users/timm/gits/moot/optimize/misc/auto93.csv

eg: python3 fft1.py -f FILE -n 50 --tree
"""
import random, math, sys, re
from functools import reduce
BIG = math.inf

# ## constructors -----------------------------------------------
def Num(at=0, txt=""):
  return o(it=Num, at=at, txt=txt, n=0, mu=0, m2=0, sd=0,
           lo=BIG, hi=-BIG, goal=0 if txt.endswith("-") else 1)

def Sym(at=0, txt=""):
  return o(it=Sym, at=at, txt=txt, n=0, has={})

def Data(src=[]):
  return adds(src, o(it=Data, cols=None, rows=[]))

def Cols(names):
  cols,x,y,klass = [],[],[],None
  for at, s in enumerate(names):
    z = s[-1]
    cols += [col := (Num if s[0].isupper() else Sym)(at, s)]
    if z in "-+!":
      y += [col]      
      if z == "!": klass = col
    elif z != "X":  x += [col]   
  return o(
    it=Cols, all=cols, x=x,y=y, names=names, klass=klass or y[0])

def Tree(): pass                    # interior tag (leaf=Data)

# ## add (one polymorphic) --------------------------------------
def add(i, v):
  if i.it is Data:
    if not i.cols: i.cols = Cols(v)
    else:
      i.rows += [v]
      for c in i.cols.all: add(c, v[c.at])
  elif v == "?": pass
  elif i.it is Sym:
    i.n += 1; i.has[v] = i.has.get(v, 0) + 1
  else:                                # add a number
    i.n += 1; d = v - i.mu
    i.mu += d / i.n
    i.m2 += d * (v - i.mu)
    i.sd = (i.m2/(i.n-1))**0.5 if i.n > 1 else 0
    if v < i.lo: i.lo = v
    if v > i.hi: i.hi = v
  return v

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

def clone(root, rows):
  return adds(rows, adds([root.cols.names],Data()))

# ## merge (s=+1 add, s=-1 subtract) ----------------------------
def merge(a, b, s=1):
  if a.it is Sym:
    has = dict(a.has)
    for k, v in b.has.items():
      has[k] = has.get(k, 0) + s*v
    has = {k: v for k, v in has.items() if v > 0}
    return o(it=Sym, at=a.at, txt=a.txt, n=a.n + s*b.n, has=has)
  n = a.n + s*b.n
  if n <= 0: return Num(a.at, a.txt)
  mu = (a.n*a.mu + s*b.n*b.mu) / n
  d  = b.mu - a.mu
  m2 = max(0, a.m2 + s*b.m2 + s*d*d*a.n*b.n / n)
  c  = Num(a.at, a.txt)
  c.n, c.mu, c.m2 = n, mu, m2
  c.lo, c.hi = min(a.lo, b.lo), max(a.hi, b.hi)
  return c

# ## metrics ----------------------------------------------------
def norm(c, v):
  return v if v=="?" else (v - c.lo) / (c.hi - c.lo + 1E-32)

def binOf(c, x, bins):               # key = cut value (rep edge for Num)
  if c.it is Sym: return x
  k = min(bins-1, int(bins*(x-c.lo)/(c.hi-c.lo+1E-32)))
  return c.lo + (k+1)*(c.hi-c.lo)/bins

def disty(d, r):
  s, n, p = 0, 0, the.p
  for c in d.cols.y:
    n += 1; s += abs(norm(c, r[c.at]) - c.goal)**p
  return (s/n)**(1/p) if n else 0

def distx(d, r1, r2):                # over x-cols, missing-tolerant
  s, n, p = 0, 0, the.p
  for c in d.cols.x:
    n += 1; v1, v2 = r1[c.at], r2[c.at]
    if v1=="?" and v2=="?": s += 1; continue
    if c.it is Sym: s += 0 if v1==v2 else 1
    else:
      v1 = norm(c,v1) if v1!="?" else (0 if norm(c,v2)>.5 else 1)
      v2 = norm(c,v2) if v2!="?" else (0 if v1>.5 else 1)
      s += abs(v1-v2)**p
  return (s/n)**(1/p)

# ## fmtree (fastmap-split, stochastic poles, train-worth) -----
def FMTree(): pass                   # tag for fmtree inner nodes

def fmtree(root, stop=None, k=30):
  stop = stop or int(len(root.rows)**.5)
  def far(ref, some):
    return max(some, key=lambda r: distx(root, ref, r))
  def grow(rows):
    if len(rows) <= stop:
      mu = sum(disty(root, r) for r in rows)/max(1, len(rows))
      return o(it=Data, rows=rows, worth=mu)
    some = random.sample(rows, min(k, len(rows)))
    A = far(random.choice(some), some); B = far(A, some)
    c = distx(root, A, B) + 1e-32
    proj = lambda r:(distx(root,r,A)**2 + c*c
                     - distx(root,r,B)**2)/(2*c)
    keyed = [(proj(r), r) for r in rows]
    keyed.sort(key=lambda x: x[0])
    m = len(keyed)//2
    L = grow([r for _,r in keyed[:m]])
    R = grow([r for _,r in keyed[m:]])
    return o(it=FMTree, A=A, B=B, c=c, cut=keyed[m][0],
             left=L, right=R, worth=max(L.worth, R.worth))
  return grow(root.rows)

def fmleaf(root, t, row):
  while t.it is FMTree:
    pr = (distx(root,row,t.A)**2 + t.c**2
          - distx(root,row,t.B)**2)/(2*t.c)
    t = t.left if pr <= t.cut else t.right
  return t

def fmleaves(t):                     # yield leaf Datas
  if t.it is Data: yield t
  else: yield from fmleaves(t.left); yield from fmleaves(t.right)

# ## tree (random attr, min-variance cut) ----------------------
# ONE random x-col/node. cuts() bins rows (binOf: Num -> `bins`
# edges, Sym -> category) into a Num of yfun(row) per bin, then
# sweeps for the min child-variance cut: total = merge(all bins),
# each split's R = merge(total, L, -1) (unmerge); impurity =
# L.m2+R.m2. default yfun = klass; caller can swap target.
def cutgo(c, x, v):                  # x -> left branch?
  return x != "?" and (x == v if c.it is Sym else x <= v)

def tree(root, stop=None, yfun=None, bins=7):
  yfun = yfun or (lambda r: r[root.cols.klass.at])
  stop = stop or the.stop or len(root.rows)**.5

  def cuts(c, rows):                 # yield (impurity, cut-value) over bins
    hist = {}
    for r in rows:
      if (x := r[c.at]) != "?":
        add(hist.setdefault(binOf(c, x, bins), Num()), yfun(r))
    bs = sorted(hist.items())
    if not bs: return
    total = reduce(merge, (v for _, v in bs))
    if c.it is Sym:
      for k, v in bs:
        R = merge(total, v, -1)
        if v.n and R.n: yield v.m2 + R.m2, k
    else:
      L = Num()
      for k, v in bs[:-1]:
        L = merge(L, v)
        R = merge(total, L, -1)
        if L.n and R.n: yield L.m2 + R.m2, k

  def grow(rows):
    if len(rows) <= stop: return clone(root, rows)
    for _ in range(10):              # retry till a real 2-way cut
      c = random.choice(root.cols.x)
      _, v = min(cuts(c, rows), default=(BIG, "?"))
      if v == "?": continue
      ok, no = [], []
      for r in rows:
        (ok if cutgo(c, r[c.at], v) else no).append(r)
      if ok and no: break
    else:
      return clone(root, rows)       # no good cut -> leaf
    return o(it=Tree, at=c.at, cut=v, left=grow(ok), right=grow(no))

  return grow(root.rows)

def treeLeaf(root, t, row):          # route row to leaf
  while t.it is Tree:
    c = root.cols.all[t.at]
    t = t.left if cutgo(c, row[t.at], t.cut) else t.right
  return t

def leaves(t):                       # yield the leaf Datas of a tree
  if t.it is Data: yield t
  else: yield from leaves(t.left); yield from leaves(t.right)

def treeShow(root, t):               # ygoal, goal means, tree
  ys  = [c for c in root.cols.y if c.it is Num]
  rowsOf = lambda t: t.rows if t.it is Data else \
                     rowsOf(t.left) + rowsOf(t.right)
  dy  = lambda rs: adds(disty(root,r) for r in rs).mu
  hdr = "".join("%7s" % c.txt for c in ys)
  print("%6s%s %5s  tree" % ("ygoal", hdr, "n"))
  def show(t, lvl, txt):
    rs = rowsOf(t)
    g = "".join("%7.1f" %
                adds(r[c.at] for r in rs if r[c.at]!="?").mu
                for c in ys)
    print("%6.2f%s %5d  %s%s" %
          (dy(rs), g, len(rs), "|  "*lvl, txt))
    if t.it is Tree:
      c  = root.cols.all[t.at]
      lo, hi = ("<="," >") if c.it is Num else ("==","!=")
      for kid, op in sorted([(t.left, lo), (t.right, hi)],
                       key=lambda k: dy(rowsOf(k[0]))):
        show(kid, lvl+1, "%s %s %s" % (c.txt, op, t.cut))
  show(t, 0, "")

# ## confusion (pd, pf, ... from (want,got) pairs) --------------
def confused(pairs):            # pairs = [(want, got), ...]
  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:                       # one-vs-rest per label
    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+1e-32), fp/(fp+tn+1e-32)    # recall, fpr
    prec   = tp/(tp+fp+1e-32)
    out[k] = o(it=o, label=k, tp=tp, fp=fp, fn=fn, tn=tn,
               pd=pd, pf=pf, prec=prec, acc=(tp+tn)/(N+1e-32),
               f1=2*prec*pd/(prec+pd+1e-32))
  return out

# ## lib -------------------------------------------------------
class o(dict):  
  __getattr__ = dict.get;__setattr__ = dict.__setitem__;
  def __repr__(i):
    def f(v):
      if isinstance(v,float):
        return int(v) if v==int(v) else round(v, the.Round)
      return v
    return "{" + " ".join(":%s %s" % (k, f(i[k])) for k in i
                          if str(k)[0]!="_") + "}"

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

def coerce(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 settings(doc):              # key=val defaults from doc
  return o(**{k: coerce(v)
              for k, v in re.findall(r'(\w+)=(\S+)', doc)})

def cli(the, doc, egs={}):      # --x runs test_x()
  flags = {f: l.lstrip("-")
           for s,l in re.findall(r"(-\w) (--\w+)",doc)
           for f in (s,l)}
  for j, s in enumerate(sys.argv):
    if fn := egs.get("test_" + s.lstrip("-")):
      random.seed(the.seed); fn()
    elif k := flags.get(s):
      v = the[k]
      if isinstance(v, bool): v = not v
      elif j+1 < len(sys.argv): v = coerce(sys.argv[j+1])
      the[k] = v
    elif re.match(r"-\D", s):
      sys.exit("bad flag: %s\n%s" % (s, doc))
  return the

# ## egs (run via --name) --------------------------------------
def test_the():                 # show the config
  print(the)

def test_tree():                # tree on N rows of -f
  head, *body = csv(the.file)
  rows = random.sample(body, min(the.N, len(body)))
  d = Data([head] + rows)
  treeShow(d, tree(d))

def test_fmtree():              # 30 fmtrees, runtime + worth dist
  import time
  head, *body = csv(the.file)
  rows = random.sample(body, min(the.N, len(body)))
  d    = Data([head] + rows)
  t0   = time.time()
  trees = [fmtree(d) for _ in range(30)]
  dt   = time.time() - t0
  ws   = sorted(t.worth for t in trees)
  best = min(trees, key=lambda t: t.worth)
  nLeaves = sum(1 for _ in fmleaves(best))
  print("# 30 fmtrees on %s (N=%d)" % (the.file.split("/")[-1], len(rows)))
  print("time         %.3fs  (%.1f ms/tree)" % (dt, 1000*dt/30))
  print("worth min    %.4f" % ws[0])
  print("worth med    %.4f" % ws[15])
  print("worth max    %.4f" % ws[-1])
  print("picked tree: worth=%.4f, %d leaves, stop=%d" %
        (best.worth, nLeaves, int(len(rows)**.5)))
  print("# all worths sorted:")
  for w in ws: print("  %.4f" % w)

# ## main -------------------------------------------------------
the = settings(__doc__)
random.seed(the.seed)
if __name__ == "__main__":
  cli(the, __doc__, globals())

gen.py

#!/usr/bin/env python3 -B
"""gen.py: regenerate far_ezr.csv + the *_bc / growkeep heatmaps.

No multiprocessing -- parallelize with xargs (see Makefile `bc-*`).
  one csv row : python3 -B gen.py csv1 FILE        -> "delta,ezr,far,name"
  assemble    : python3 -B gen.py csvjoin < rows   -> far_ezr.csv
  trial batch : python3 -B gen.py trials KIND N S  -> "xi yi win" lines
  plot        : python3 -B gen.py plot KIND < lines-> KIND's png
KIND in far|ezr|dfan (check x budget) | growkeep (grow x keep).
"""
import sys, os, glob, random
sys.path[:0] = [os.path.expanduser("~/gists/nuff"),
                os.path.expanduser("~/gists/ezr")]
import far as F                                   # noqa: E402
import ezr as E                                   # noqa: E402
from nuff import same, disty, tree, fft, treePredict   # noqa: E402

FILES = sorted(glob.glob(os.path.expanduser("~/gists/optimiz/*.csv")))
F.the.leaf = 3
E.the.learn.start, E.the.learn.leaf = 8, 3

HEAT = {  # out, title, xlab, ylab, extent, nx, ny, star
 "far":  ("far_bc.png", "far: mean best-win, grow=4 keep=.66 leaf=3",
          "check", "budget", (.5,10.5,10,200), 10, 19, (5,50)),
 "ezr":  ("ezr_bc.png", "ezr: mean best-win, start=8 leaf=3",
          "check", "budget", (.5,10.5,10,200), 10, 19, (5,50)),
 "dfan": ("far_bc_dfan.png", "far+dfan FFT: mean best-win, grow=4 keep=.66",
          "check", "budget", (.5,10.5,10,200), 10, 19, (5,50)),
 "full": ("far_tree_full.png", "full tree: mean best-win, cap=1028 leaf=3",
          "check", "budget", (.5,10.5,10,200), 10, 19, (5,50)),
 "d4":   ("far_tree_d4.png", "fft depth=4: mean best-win, cap=128",
          "check", "budget", (.5,10.5,10,200), 10, 19, (5,50)),
 "deep": ("far_tree_deep.png", "fft deep: mean best-win, cap=1028 leaf=3",
          "check", "budget", (.5,10.5,10,200), 10, 19, (5,50)),
 "growkeep": ("far_growkeep.png", "far: mean best-win, check=5 budget=50",
          "grow", "keep", (.5,10.5,.50,.95), 10, 9, (4,.66))}

# 3 tree policies: (cap pool, build(d,lab,y) -> tree or dfan FFT).
# full & deep share a cap=1028 leaf=3 tree -- they differ only in how
# they PREDICT (walk the whole tree, vs dfan the best FFT from it).
POLICY = {
 "full": (1028, lambda d, lab, y: tree(d, lab, y, leaf=3)),
 "d4":   (128,  lambda d, lab, y: fft(tree(d, lab, y, leaf=1, maxDepth=4))),
 "deep": (1028, lambda d, lab, y: fft(tree(d, lab, y, leaf=3)))}

# ---- one holdout rep per learner ------------------------------
def far_rep(data, win, check, budget, grow=4, keep=.66):
  F.the.check, F.the.budget, F.the.grow, F.the.keep = check, budget, grow, keep
  rows = F.some(data.rows, F.the.cap)
  h = len(rows)//2
  d, hold = F.clone(data, rows[:h]), rows[h:]
  t = F.tree(d, F.landscape(d))
  return win(F.pick(hold, lambda r: F.treePredict(t, r), data))

def fft_rep(data, win, check, budget):
  "Sort the holdout with the best dfan FFT (per-node cuts, depth 4)."
  F.the.check, F.the.budget = check, budget
  rows = F.some(data.rows, F.the.cap)
  h = len(rows)//2
  d, hold = F.clone(data, rows[:h]), rows[h:]
  y = F.memo(lambda r: disty(d, r))
  f = fft(tree(d, F.landscape(d), y, leaf=1, maxDepth=4))
  return win(F.pick(hold, lambda r: treePredict(f, r), data))

def policy_rep(data, win, check, budget, pol):
  "far-acquire on a cap-sized pool, build per POLICY[pol], holdoutWin."
  cap, build = POLICY[pol]
  F.the.check, F.the.budget = check, budget
  rows = F.some(data.rows, cap)
  h = len(rows)//2
  d, hold = F.clone(data, rows[:h]), rows[h:]
  y = F.memo(lambda r: disty(d, r))
  t = build(d, F.landscape(d), y)
  return win(F.pick(hold, lambda r: treePredict(t, r), data))

def ezr_rep(data, win, check, budget):
  E.the.learn.check, E.the.learn.budget = check, budget
  rows = data.rows[:]; E.shuffle(rows)
  half = len(rows)//2
  train, hold = rows[:half], rows[half:]
  lab = E.acquire(E.clone(data, train))
  tr = E.treeGrow(lab, lab.rows)
  ranked = sorted(hold, key=lambda r: E.treeLeaf(tr, r).ynum.mu)
  best = min(ranked[:E.the.learn.check], key=lambda r: E.disty(data, r))
  return win(best)

# ---- far_ezr.csv (xargs over files) ---------------------------
def csv1(f):
  random.seed(F.the.seed)
  d = F.Data(F.csv(f));  fwin = F.wins(d)
  d2 = E.Data(E.csv(f)); ewin = E.wins(d2)
  fa = [far_rep(d, fwin, 5, 50) for _ in range(20)]
  ez = [ezr_rep(d2, ewin, 5, 50) for _ in range(20)]
  delta = 0 if same(ez, fa, cliff=0.35) else round(sum(ez)/20-sum(fa)/20)
  print(f"{delta},{round(sum(ez)/20)},{round(sum(fa)/20)},"
        f"{os.path.basename(f)[:-4]}")

def csvjoin():
  rows = [ln.strip().split(",") for ln in sys.stdin if ln.strip()]
  rows.sort(key=lambda r: int(r[0]))
  out = os.path.expanduser("~/gists/sand-box/far_ezr.csv")
  with open(out, "w") as fp:
    fp.write("delta,ezr_mu,far_mu,name\n")
    for r in rows: fp.write(",".join(r) + "\n")
  print("wrote", out, len(rows), "rows")

# ---- heatmaps (xargs: trials -> plot) -------------------------
def trials(kind, n, seed):
  rng = random.Random(seed); cache = {}
  for _ in range(n):
    f = rng.choice(FILES)
    if f not in cache:
      mod = E if kind == "ezr" else F
      d = mod.Data(mod.csv(f)); cache[f] = (d, mod.wins(d))
    data, win = cache[f]
    try:
      if kind == "growkeep":
        g = rng.randint(1, 10); k = rng.uniform(.50, .95)
        w, xi, yi = far_rep(data, win, 5, 50, g, k), g-1, min(8, int((k-.5)/.05))
      else:
        ch = rng.randint(1, 10); bu = rng.randint(10, 200)
        w = (ezr_rep(data, win, ch, bu) if kind == "ezr"
             else fft_rep(data, win, ch, bu) if kind == "dfan"
             else policy_rep(data, win, ch, bu, kind) if kind in POLICY
             else far_rep(data, win, ch, bu))
        xi, yi = ch-1, min(18, (bu-10)//10)
    except Exception: continue
    print(xi, yi, round(w, 3))

def plot(kind):
  import numpy as np
  out, title, xlab, ylab, ext, nx, ny, star = HEAT[kind]
  tot, cnt = np.zeros((ny, nx)), np.zeros((ny, nx))
  for ln in sys.stdin:
    p = ln.split()
    if len(p) != 3: continue                      # skip xargs-interleaved
    try: xi, yi, w = int(p[0]), int(p[1]), float(p[2])
    except ValueError: continue
    if 0 <= xi < nx and 0 <= yi < ny:
      tot[yi, xi] += w; cnt[yi, xi] += 1
  grid = np.where(cnt > 0, tot/np.maximum(cnt, 1), np.nan)
  import matplotlib; matplotlib.use("Agg")
  import matplotlib.pyplot as plt
  fig, ax = plt.subplots(figsize=(7, 6))
  im = ax.imshow(grid, cmap="RdYlGn", origin="lower", aspect="auto",
                 vmin=40, vmax=90, extent=ext)
  xs = np.linspace(ext[0], ext[1], nx); ys = np.linspace(ext[2], ext[3], ny)
  cs = ax.contour(xs, ys, grid, levels=[50,60,70,80,85], colors="k",
                  linewidths=.6)
  ax.clabel(cs, inline=True, fontsize=8)
  ax.plot(*star, "*", color="black", markersize=16)
  ax.set(title=title, xlabel=xlab, ylabel=ylab)
  fig.colorbar(im, label="mean best-win")
  p = os.path.expanduser("~/gists/sand-box/" + out)
  fig.savefig(p, dpi=120, bbox_inches="tight"); print("wrote", p)

if __name__ == "__main__":
  cmd, rest = sys.argv[1], sys.argv[2:]
  if   cmd == "csv1":    csv1(rest[0])
  elif cmd == "csvjoin": csvjoin()
  elif cmd == "trials":  trials(rest[0], int(rest[1]), int(rest[2]))
  elif cmd == "plot":    plot(rest[0])

grammar.md

Grammar of the random-cloud / fastmap design space

These scripts (tree, pick.py, fair.py, fmtree, fmpick.py, ablate.py, etc.) are all samples from one small grammar. Spelling it out makes it obvious which knob is being twisted, and which arrangements have not yet been tried.

EBNF-ish

ALGO       ::= REPEAT { PROTOCOL }

PROTOCOL   ::= SPLIT_DATA  BUILD_CLOUD  SELECT  EVAL

SPLIT_DATA ::= "shuffle" "->" (TRAIN | TRAIN VAL | TRAIN VAL TEST)
            ;  fractions ∈ {0/0/100, 80/0/20, 60/20/20, 50/25/25}

BUILD_CLOUD ::= "for" M "in" 1..MODELS ":" BUILD_TREE

BUILD_TREE ::= BAG  TREE  LEAVES
BAG        ::= "random" k "rows from train"           ; k ∈ {16,32,64,128,all}
            |  "ratio-sweep" (10..90 % pos, fixed n)  ; class-balanced
            |  "all train"
TREE       ::= "while" leaf_size>STOP ":"
                  SPLIT_RULE  ROUTE_RULE
              "end"
SPLIT_RULE ::= "random-attr" (RANDOM_CUT | MED_CUT | BEST_CUT)
            |  "fastmap"      POLE_PICK PROJ_CUT
            |  "all-attr"     BEST_CUT
SPLIT_RULE += FEAT_SUBSPACE                            ; sqrt-cols, all
RANDOM_CUT ::= "v ~ Uniform(c.lo, c.hi)"
MED_CUT    ::= "v = median(c)"
BEST_CUT   ::= "v = argmin sum_{side}(impurity)"
            ;  impurity ∈ {gini, variance/m2, entropy, label-ratio}
            ;  candidates ∈ {all values, B quantile-edges, midpoints}
POLE_PICK  ::= "A,B = far-far over random subsample of size k"
            ;  k ∈ {2, 30, 64, all_rows}
PROJ_CUT   ::= "split at median proj(r) onto A-B line"

LEAVES     ::= (BAG | LOAD_POOL | TRAIN | none) -> "leaf.vote = mean/majority"
LOAD_POOL  ::= "sample N rows of train, route to leaves"

STOP       ::= 4 | 8 | 16 | sqrt(n) | sqrt(bag_n)
ROUTE_RULE ::= "x <= v"        (axis Num)
            |  "x == v"        (axis Sym)
            |  "proj(x) <= cut"(fastmap)

SELECT     ::= NONE                            ; first / only tree
            |  ON_TRAIN  WORTH_FN              ; intrinsic
            |  ON_VAL    WORTH_FN              ; held-out
            |  PARETO_FRONT
            |  VOTE_ENSEMBLE                   ; no select; aggregate all

WORTH_FN   ::= "heaven(recall, prec, fair)"    ; pick.py
            |  "max_{leaf}(mean d2h)"          ; fmtree minimax
            |  "mean_{leaf}(mean d2h)"
            |  "min_{leaf}(mean d2h)"          ; best-leaf only
            |  "leaf-purity weighted by size"

EVAL       ::= TEST_METRIC                     ; single best tree
            |  TEST_METRIC + AGG               ; ensemble
TEST_METRIC::= "(recall, prec, fair)"
            |  "(d2h)"
            |  "(ROC-AUC)"

GOAL_TYPE  ::= REGRESSION       (d2h over Num y-cols)
            |  CLASSIFICATION   (heaven over recall/prec/fair)

DISTANCE   ::= MINKOWSKI(p ∈ {1,2}, cols, missing-rule)
            ;  cols ∈ {x only, x+y, y only}
            ;  missing-rule = "if both ?: 1; if one ?: extreme other"

Algorithms in this codebase, as instances

name	bag	split	pole pick	leaves	select	worth
tree (fft1.py)	all rows	random-attr + best-cut (L2)	hist B=7	bag	none	n/a
pick.py	ratio-sweep 64	L2 random-attr	best	bag	val	heaven
fair.py	all train	fastmap	random poles	bag	threshold sweep	Pareto
fmtree	all rows	fastmap	far-far (k=30 samp.)	full recur	train	min(max leaf d2h)
fmpick.py	64	fastmap	far-far (k=64)	Load pool	val	heaven
compas.py/ablate.py	various	various	various	bag	val	heaven

What past sweeps tuned

• Bag size: 64 wins (cheap, ratio-sweep gives diversity).
• Split mechanism: random-attr ≈ fastmap on quality; axis 2.3× faster.
• Cut target: L2 best-cut wins (L0/L1 underfit, L3 overfits, collapses cloud).
• Bins: all-values ≈ 7 quantile-edges at bag=64 (tree shape dominates).
• Selection: val-pick necessary; train-self overfits.
• Vote vs pick: pick wins (majority vote regresses to base-rate).

What the grammar suggests is unexplored

• Pareto-front selection (multi-objective) — only fair.py touches it.
• Mixed bag (ratio-sweep + fastmap poles).
• WORTH_FN = "minimax over leaves" applied to classification (fmtree style on heaven instead of d2h).
• Adaptive depth — bigger trees for harder leaves.
• Stochastic far-pole picks per recursion using random.sample(k) rather than full sort (fmtree uses k=30, fmpick uses k=64).

Empirical relations

• Many operators are inert (ablate.py): split mechanism, cut target, bag size, ratio-sweep variants — almost no effect on test heaven. The active levers are:
  • bag (ratio-sweep gives cloud spread)
  • selection (val-pick beats train-pick and vote)
  • data ceiling (small protected groups cap fairness scatter)
• fmpick on compas (img/l2fmap.pdf) reproduces this: comparable to L2-pick.py heaven, marginally worse cloud shape. Confirms split-is-inert under the grammar.

Reading the grammar

A new experiment = one assignment of every nonterminal to a terminal or to a small range. Pre-register that assignment before running; "new algorithm" usually = a new tuple from this grammar, not a new primitive.

holdout.py

import glob, random, nothing as n
from nothing import (Data, csv, disty, adds, ranges, score,
                     front, covers, the, sd)

random.seed(1)
BIG = 1e32

def whichpop(data, Y):                  # like which() but return stack
  pop = sorted((score(data,[c],Y), [c])
               for at in data.x for c in ranges(data, at))
  for _ in range(the.rounds):
    rule = sorted(set(front(pop)[1]) | set(front(pop)[1]))
    if any(rule == r for _,r in pop): continue   # no duplicates
    pop  = sorted(pop + [(score(data, rule, Y), rule)])[:the.stack]
  return pop

def winsT(train, test, sel):            # % gap to best closed, on test
  ds = [disty(train, r) for r in test]
  lo, b4 = min(ds), sum(ds)/len(ds)
  now = sum(disty(train, r) for r in sel)/len(sel)
  return 100 * (1 - (now-lo)/((b4-lo) or 1e-32))

def trial(f):
  g = csv(f); names = next(g); rows = list(g)
  if len(rows) > 2000: rows = random.sample(rows, 2000)
  random.shuffle(rows)
  k = len(rows)//2
  tr, te = rows[:k], rows[k:]
  train = Data(iter([names] + tr))
  if not train.y or len(te) < 10: return None
  Y   = lambda r: disty(train, r)
  pop = whichpop(train, Y)
  top = pop[:5]
  # current approach: best rule, applied to test
  best = [r for r in te if covers(top[0][1], r)] or te
  w_rule = winsT(train, te, best)
  # top5 vote: predict test row by mean covering-rule train-score
  def pred(r):                          # row as good as its best rule
    ss = [s for s,rule in top if covers(rule, r)]
    return min(ss) if ss else BIG
  sel = sorted(te, key=pred)[:len(best)]   # match rule's sample size
  w_top5 = winsT(train, te, sel)
  return w_rule, w_top5

files = random.sample(glob.glob("../optimiz/*.csv"), 10)
print("%-42s %8s %8s" % ("dataset", "rule", "top5"))
R = T = nok = 0
for f in files:
  try: out = trial(f)
  except Exception as e: out = None
  nm = f.split("/")[-1][:42]
  if out is None: print("%-42s %8s %8s" % (nm, "skip", "skip")); continue
  wr, wt = out; R += wr; T += wt; nok += 1
  print("%-42s %8.1f %8.1f" % (nm, wr, wt))
if nok:
  print("%-42s %8.1f %8.1f" % ("MEAN", R/nok, T/nok))

l2.png

lib.py

#!/usr/bin/env python3 -B
"""lib.py: shared de2 data, (n,mu,m2) stats, distance.
(c) 2025 T. Menzies, MIT. import *, then opts(__doc__).

Cols: a Sym is a {value:weight} dict, a Num is an
(n,mu,m2) moment. add(c,v,w) grows (w=1) or shrinks
(w=-1). norm = logistic of z (no reservoir). disty =
distance to heaven. opts(doc) reads `key=val` defaults
from a docstring, lets `-k val` (first letter) override.
"""
import math, random, re, sys

BIG = 1E32

class o(dict):
  __getattr__=dict.get; __setattr__=dict.__setitem__
  def __repr__(i):
    return "{"+" ".join(f":{k} {qty(v)}"
                        for k,v in i.items()
                        if str(k)[0]!="_")+"}"

the  = o()                       # filled by opts(__doc__)
symp = lambda c: isinstance(c, dict)   # Num = tuple

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

# ## options ----------------------------------------------
def coerce(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 opts(doc):                   # key=val defaults; -k override
  for k, v in re.findall(r"(\w+)=(\S+)", doc):
    the[k] = coerce(v)
  for k in list(the):
    for flag,val in zip(sys.argv,sys.argv[1:]):
      if ("-" + k[0]) == flag:
        the[k] = coerce(val)
  return the

# ## data -------------------------------------------------
def Num(at): return (0,0,0,-BIG)
def Sym()  : return {}
def symp(x): return isinstance(x,dict)

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

  i = o(x=[], y=[], goal={}, klass=None, cols={}, rows=[])
  src = iter(src)
  roles(next(src))
  for v in src: adds(i, v)
  return i

def adds(data, row):             # add one row to a Data
  data.rows += [row]
  for at, v in enumerate(row):
    data.cols[at] = add(data.cols[at], v)

def clone(data, rows=[]):
  return Data([data.names] + rows)

# ## stat -------------------------------------------------
def add(c, v, w=1):              # w=+1 grow, w=-1 shrink
  if v == "?": return c
  if isinstance(c, dict):
    c[v] = c.get(v, 0) + w
    return c
  n, mu, m2, hi, at= c
  n += w
  if n <= 0: return (0, 0, 0)
  d   = v - mu
  mu += w * d / n
  m2 += w * d * (v - mu)
  return (n, mu, m2)

# ## distance ---------------------------------------------
def norm(data, at, v):           # 0..1 logistic of z (~CDF)
  if v == "?": return v
  n, mu, m2 = data.cols[at]
  sd = (m2/(n-1))**.5 if n > 1 else 0
  z  = (v - mu) / (sd + 1/BIG)
  return 1 / (1 + math.exp(-1.7 * max(-3, min(3, z))))

def disty(data, row):            # d2h: distance to heaven
  p, s, n = the.p, 0, 0
  for at in data.y:
    n += 1
    s += abs(norm(data,at,row[at]) - data.goal[at])**p
  return (s/n)**(1/p) if n else 0

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

def print2d(rows):               # left-justify all columns
  rows = [[str(x) for x in r] for r in rows]
  w = [max(len(r[c]) for r in rows) for c in range(len(rows[0]))]
  for r in rows:
    print("  ".join(x.ljust(w[c]) for c, x in enumerate(r)))

def shuffle(lst): random.shuffle(lst); return lst

Makefile

# vim: ts=2 sw=2 sts=2 et :
# knobs only; generic targets (help doctor check push hist sh vi mux pdf)
# live in $(KONFIG)/Makefile
KONFIG ?= ../konfig

APP     := sand-box
MAIN    := thesis.py
EXT     := py
LANG    := python
COMMENT := \#
LINT     = ruff check *.py
TOOLS   := python3:run ruff:check
PKG     := python3 ruff gawk a2ps ghostscript 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

## sand-box-specific -------------------------------------------

zhi: l2.png ## regenerate l2.png on compas
	@echo "regenerated l2.png"

l2.png: thesis.py pick.py fft1.py compas.csv ## thesis.py on compas -> l2.png
	@python3 -B thesis.py compas

MOOT ?= /Users/timm/gits/moot/optimize
JOBS ?= 8
OUT  := $(HOME)/tmp/sand-box_de2.txt

$(OUT): de2.py ## run de2 over all moot csvs -> $(OUT)
	@mkdir -p $(dir $@)
	@find $(MOOT) -name "*.csv" | \
	  xargs -P$(JOBS) -n1 -I{} python3 -B de2.py -f {} --de > $@
	@echo "wrote $@ ($$(wc -l < $@) lines)"

trees: tree.py ## min-var tree on a 50-row sample of every optimiz csv
	@for f in ../optimiz/*.csv; do \
	  echo "==== $$f ===="; \
	  PYTHONPATH=../nuff python3 -B tree.py "$$f" || echo "FAIL $$f"; \
	done

OPT  ?= ../optimiz
FAR  := $(HOME)/tmp/far.txt
ACQ  := $(HOME)/tmp/acq20.txt

$(FAR): far.py ## far hold-out win over all optimiz (xargs -P)
	@mkdir -p $(dir $@)
	@ls $(OPT)/*.csv | PYTHONPATH=../nuff xargs -P$(JOBS) -n1 -I{} \
	  python3 -B far.py -file {} | sort -k2 > $@
	@echo "wrote $@ ($$(wc -l < $@) rows)"

$(ACQ): ## ezr acquire20 win over all optimiz (xargs -P)
	@mkdir -p $(dir $@)
	@ls $(OPT)/*.csv | xargs -P$(JOBS) -n1 -I{} \
	  python3 -B ../ezr/cli.py --acquire20 {} 2>/dev/null | sort -k2 > $@
	@echo "wrote $@ ($$(wc -l < $@) rows)"

cmp: $(FAR) $(ACQ) ## compare far vs ezr acquire20, per-dataset + mean
	@join -1 2 -2 2 $(FAR) $(ACQ) | \
	  gawk '{printf "%-42s far=%3s ezr=%3s\n",$$1,$$2,$$3; f+=$$2; e+=$$3; n++} \
	        END{printf "\nMEAN  far=%.1f  ezr=%.1f  (n=%d)\n",f/n,e/n,n}'

N    ?= 40000
bc-%: gen.py far.py ## heatmap (KIND=far|ezr|dfan|full|d4|deep|growkeep)
	@seq 0 7 | PYTHONPATH=../nuff xargs -P$(JOBS) -I% \
	  python3 -B gen.py trials $* $$(( $(N) / 8 )) % > /tmp/gen_$*.txt
	@PYTHONPATH=../nuff python3 -B gen.py plot $* < /tmp/gen_$*.txt

far_ezr.csv: gen.py far.py ## far vs ezr per-dataset (xargs -P)
	@ls ../optimiz/*.csv | PYTHONPATH=../nuff xargs -P$(JOBS) -n1 -I{} \
	  python3 -B gen.py csv1 {} | PYTHONPATH=../nuff python3 -B gen.py csvjoin

nothing.py

import re, sys, random, traceback
from random import random as rand
from math import log2, log, exp, sqrt, pi
from bisect import bisect_left, bisect_right
from types import SimpleNamespace as o   # o(a=1).a == 1
isa = isinstance
BIG = 1e32
TINY = 1e-32

the = o(keep=1024, bins=16, N=8, Min=8, stack=32, rounds=64,
        grow=4, budget=50, leaf=3, keepf=0.66,
        seed=1, file="../optimiz/misc_auto93.csv")

#-- Cols --------------------------------------------------------
Sym = dict
def Num(n=0, mu=0, m2=0): return (n, mu, m2)

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

def welford(v, n, mu, m2):
  n += 1; d  = v - mu; mu += d / n
  return (n, mu, m2 + d * (v - mu))

def entropy(d):                      
  N = sum(d.values()) or 1
  return -sum(v/N*log2(v/N) for v in d.values() if v)

def mix(i, j, inc=1):
  if isa(i, Sym):
    return {k: i.get(k, 0) + inc * j.get(k, 0) for k in i | j}
  (ni, mui, m2i), (nj, muj, m2j) = i, j
  n = ni + inc * nj
  if n <= 0: return Num()
  d  = muj - mui
  mu = (ni * mui + inc * nj * muj) / n
  m2 = m2i + inc * m2j + inc * d * d * ni * nj / n
  return Num(n, mu, m2)

#-- Data -------------------------------------------------------
def Data(src):
  src  = iter(src)
  data = o(names=next(src), cols={}, x=[], y=[], goal={},
           klass=None, protect=[], rows=[])
  return adds(src, roles(data))

def roles(data):
  for at, s in enumerate(data.names):
    data.cols[at] = Num() if s[0].isupper() else Sym()
    if s[-1] == "X": continue
    if s[-1] in "+-!":
      data.y += [at]; data.goal[at] = s[-1] == "+"   # +max -min
      if s[-1] == "!": data.klass = at
    else:
      data.x += [at]                       # predictor...
      if s[-1] == "~": data.protect += [at]   # ...also sensitive
  return data

#-- Dist --------------------------------------------------------
def sd(num): n,mu,m2 = num; return 0 if n<2 else (m2/(n-1))**.5

def norm(num, v):                     # v -> 0..1 logistic z
  if v == "?": return v
  z = (v - mu_(num)) / (sd(num) + 1e-32)
  return 1 / (1 + exp(-1.7 * max(-3, min(3, z))))

def minkowski(vals, p=2):             # p-norm of per-item dists
  tot = nn = 0
  for v in vals: tot += v**p; nn += 1
  return (tot / (nn or 1)) ** (1/p)

def gap(col, u, v):                   # 0..1 dist of two values
  if u == v == "?": return 1
  if isa(col, Sym): return u != v
  u, v = norm(col, u), norm(col, v)
  if u == "?": u = 1 if v < .5 else 0
  if v == "?": v = 1 if u < .5 else 0
  return abs(u - v)

def disty(data, row, **kw):           # row -> goals, 0=best
  return minkowski(
    (abs(norm(data.cols[at], row[at]) - data.goal[at])
     for at in data.y if row[at] != "?"), **kw)

def distx(data, r1, r2, **kw):        # row<->row over x-cols
  return minkowski((gap(data.cols[at], r1[at], r2[at])
                    for at in data.x), **kw)

def wins(data):                       # -> fn(rows) % gap to best
  ys = sorted(disty(data,r) for r in data.rows)
  lo, b4 = ys[0], ys[ len(ys)//2 ]
  return lambda sel: 100 * (1 - (mu_(adds(
    disty(data,r) for r in sel)) - lo) / ((b4-lo) or 1e-32))

#-- Landscape ---------------------------------------------------
def shuffle(lst): return random.sample(lst, len(lst))

def memo(fn):                         # cached fn + cache dict
  cache = {}
  def f(r):
    if r not in cache: cache[r] = fn(r)
    return cache[r]
  return f, cache

def project(rows, d, y):              # row -> east-west pos
  far  = lambda r: max(rows, key=lambda z: d(z, r))
  east = far(rows[0]); west = far(east)
  if y(east) < y(west): east, west = west, east
  c = d(east, west) + TINY
  return lambda r: (d(east,r)**2 + c*c - d(west,r)**2) / (2*c)

def landscape(data):                  # active-learn by disty
  d = lambda r1, r2: distx(data, r1, r2)
  y, ys = memo(lambda r: disty(data, r))
  pool = shuffle(data.rows)
  while len(ys) < the.budget-the.grow and len(pool)>=2*the.leaf:
    lab, k = [], 0
    for r in pool:
      if r in ys: lab.append(r)
      elif k < the.grow: y(r); lab.append(r); k += 1
    n = max(1, int((1-the.keepf)*len(pool)))
    pool = sorted(pool, key=project(lab, d, y))[n:]
  return sorted(ys, key=y)

def adds(src, i=None):
  i = i or Num()
  for v in src: i = add(i,v)
  return i

def add(i,v):
  if isa(i,o):
    for at,col in i.cols.items(): i.cols[at] = add(col,v[at]) 
    i.rows += [v]
  elif v != "?":
    if isa(i,Sym): i[v] = i.get(v,0) + 1
    else: i = welford(v, *i)
  return i

#-- Tree --------------------------------------------------------
def maybe(n): 
  return lambda r : -BIG if r[n]=="?" else r[n]

def impurity(col):                        
  if not isa(col, Sym): return m2_(col)
  return entropy(col) * sum(col.values()) 

def split(data,at,Y):
  xs  = [r for r in data.rows if r[at] != "?"]
  tot = adds(Y(r) for r in xs)
  cut = lambda l,k: (impurity(l)+impurity(mix(tot,l,-1)), at, k)
  if isa(data.cols[at], Sym):              
    for k in {r[at] for r in xs}:
      yield cut(adds(Y(r) for r in xs if r[at]==k), k)
  else:                                 
    xs.sort(key=maybe(at)); n=len(xs); l=Num()
    for j,row in enumerate(xs):
      l = add(l, Y(row))
      if j+1 < n and j*the.bins//n != (j+1)*the.bins//n:
        yield cut(l, row[at])

#-- Which -------------------------------------------------------
# rule = set of ranges; (at,lo,hi). Sym: lo==hi==value.
def ranges(data, at):                  
  vs = [r[at] for r in data.rows if r[at] != "?"]
  if isa(data.cols[at], Sym): return [(at,v,v) for v in set(vs)]
  lo, hi = min(vs), max(vs); w = (hi-lo)/the.N or 1
  return [(at, lo+i*w, lo+(i+1)*w) for i in range(the.N)]

def cover(v, lo, hi): return v != "?" and lo <= v <= hi

def covers(rule, r):           # OR within attr, AND across attrs
  by = {}
  for at,lo,hi in rule: by[at] = by.get(at,[]) + [(lo,hi)]
  return all(any(cover(r[at], lo, hi) for lo,hi in v)
             for at,v in by.items())

def score(data, rule, Y):                
  ys = adds(Y(r) for r in data.rows if covers(rule, r))
  return BIG if n_(ys) < the.Min else mu_(ys)

def front(pop):                         # bias to best (index 0)
  return pop[int(len(pop) * rand()**2)]

def which(data, Y):                      # grow good from good
  pop = sorted((score(data,[c],Y), [c])
               for at in data.x for c in ranges(data, at))
  for _ in range(the.rounds):
    rule = sorted(set(front(pop)[1]) | set(front(pop)[1]))
    new  = (score(data, rule, Y), rule)
    pop  = sorted(pop + [new])[:the.stack]
  return pop[0]

#-- Misc --------------------------------------------------------
def thing(s):
  if (s[1:] if s[:1] == "-" else s).isdigit(): return int(s)
  try: return float(s)
  except ValueError: return s=="True" or (s!="False" and s)

def csv(file, clean=lambda s: s.partition("#")[0].split(",")):
  with open(file, encoding="utf-8") as f:
    for line in f:
      row = [x.strip() for x in clean(line)]  
      if any(row):                           
        yield tuple(thing(x) for x in row)  

#-- Main --------------------------------------------------------
def main(file):
  data = Data(csv(file))
  Y    = lambda r: disty(data, r)
  sc, rule = which(data, Y)
  sel  = [r for r in data.rows if covers(rule, r)]
  show = lambda a,lo,hi: (data.names[a], round(lo,2),round(hi,2))
  print("rule  ", [show(*r) for r in rule])
  print("cover %d/%d  wins=%.1f%%" % (
        len(sel), len(data.rows), wins(data)(sel)))

if __name__ == "__main__":
  random.seed(the.seed)
  main(sys.argv[1] if len(sys.argv) > 1 else the.file)

overfit_results.txt

# acquire20 win: binned (active.grow) vs exact (tree.tree)
# same acquired labels, 20 reps, 129 optimiz datasets
# bin exact dataset
85   94   auto93.csv
90   88   behavior_data_WA_Fn-UseC_-HR-Employee-Attrition.csv
94   97   behavior_data_all_players.csv
90   93   behavior_data_player_statistics_cleaned_final.csv
85   95   behavior_data_student_dropout.csv
52   52   binary_config_FFM-1000-200-0.50-SAT-1.csv
67   67   binary_config_FFM-125-25-0.50-SAT-1.csv
60   60   binary_config_FFM-250-50-0.50-SAT-1.csv
71   71   binary_config_FFM-500-100-0.50-SAT-1.csv
60   60   binary_config_FM-500-100-0.25-SAT-1.csv
57   57   binary_config_FM-500-100-0.50-SAT-1.csv
50   50   binary_config_FM-500-100-0.75-SAT-1.csv
67   67   binary_config_FM-500-100-1.00-SAT-1.csv
64   64   binary_config_Scrum100k.csv
57   57   binary_config_Scrum10k.csv
60   60   binary_config_Scrum1k.csv
66   66   binary_config_billing10k.csv
100  100  config_Apache_AllMeasurements.csv
100  100  config_HSMGP_num.csv
87   87   config_SQL_AllMeasurements.csv
93   93   config_SS-A.csv
94   94   config_SS-B.csv
96   96   config_SS-C.csv
72   73   config_SS-D.csv
75   88   config_SS-E.csv
69   80   config_SS-F.csv
72   65   config_SS-G.csv
85   100  config_SS-H.csv
98   97   config_SS-I.csv
100  100  config_SS-J.csv
83   99   config_SS-K.csv
94   94   config_SS-L.csv
100  100  config_SS-M.csv
83   90   config_SS-N.csv
84   88   config_SS-O.csv
81   81   config_SS-P.csv
100  100  config_SS-Q.csv
74   74   config_SS-R.csv
90   90   config_SS-S.csv
100  100  config_SS-T.csv
81   81   config_SS-U.csv
97   97   config_SS-V.csv
60   60   config_SS-W.csv
91   91   config_SS-X.csv
100  100  config_X264_AllMeasurements.csv
100  100  config_rs-6d-c3_obj1.csv
100  100  config_rs-6d-c3_obj2.csv
97   100  config_sol-6d-c2-obj1.csv
77   97   config_wc+rs-3d-c4-obj1.csv
88   100  config_wc+sol-3d-c4-obj1.csv
73   100  config_wc+wc-3d-c4-obj1.csv
74   100  config_wc-6d-c1-obj1.csv
56   64   financial_data_BankChurners.csv
61   73   financial_data_Loan.csv
100  100  financial_data_WA_Fn-UseC_-Telco-Customer-Churn.csv
33   34   financial_data_home_data_for_ml_course.csv
82   77   health_data_Data_COVID19_Indonesia.csv
100  99   health_data_Life_Expectancy_Data.csv
100  100  health_data_Medical_Data_and_Hospital_Readmissions.csv
100  98   hpo_Health-ClosedIssues0000.csv
50   49   hpo_Health-ClosedIssues0001.csv
100  100  hpo_Health-ClosedIssues0002.csv
65   80   hpo_Health-ClosedIssues0003.csv
17   13   hpo_Health-ClosedIssues0004.csv
76   76   hpo_Health-ClosedIssues0005.csv
94   98   hpo_Health-ClosedIssues0006.csv
44   46   hpo_Health-ClosedIssues0007.csv
68   74   hpo_Health-ClosedIssues0008.csv
23   17   hpo_Health-ClosedIssues0009.csv
60   62   hpo_Health-ClosedIssues0010.csv
100  95   hpo_Health-ClosedIssues0011.csv
100  100  hpo_Health-ClosedPRs0000.csv
87   88   hpo_Health-ClosedPRs0002.csv
100  100  hpo_Health-ClosedPRs0003.csv
93   95   hpo_Health-ClosedPRs0004.csv
100  100  hpo_Health-ClosedPRs0005.csv
58   61   hpo_Health-ClosedPRs0006.csv
90   85   hpo_Health-ClosedPRs0007.csv
8    28   hpo_Health-ClosedPRs0008.csv
68   71   hpo_Health-ClosedPRs0009.csv
41   43   hpo_Health-ClosedPRs0010.csv
100  100  hpo_Health-ClosedPRs0011.csv
98   100  hpo_Health-Commits0000.csv
100  100  hpo_Health-Commits0001.csv
45   68   hpo_Health-Commits0002.csv
77   77   hpo_Health-Commits0003.csv
10   16   hpo_Health-Commits0004.csv
63   57   hpo_Health-Commits0005.csv
67   66   hpo_Health-Commits0006.csv
61   64   hpo_Health-Commits0007.csv
47   43   hpo_Health-Commits0008.csv
100  100  hpo_Health-Commits0009.csv
84   89   hpo_Health-Commits0010.csv
95   95   hpo_Health-Commits0011.csv
49   53   misc_Car_price_cleaned.csv
58   55   misc_Wine_quality.csv
85   95   misc_auto93.csv
100  97   misc_multiLabel.csv
39   39   process_coc1000.csv
35   35   process_nasa93dem.csv
71   74   process_pom3a.csv
71   63   process_pom3b.csv
58   59   process_pom3c.csv
71   68   process_pom3d.csv
98   91   process_xomo_flight.csv
92   96   process_xomo_ground.csv
93   94   process_xomo_osp.csv
67   67   process_xomo_osp2.csv
57   53   rl_A2C_Acrobot.csv
48   45   rl_A2C_CartPole.csv
52   67   sales_data_Marketing_Analytics.csv
8    8    sales_data_accessories.csv
48   48   sales_data_dress-up.csv
100  100  sales_data_socks.csv
75   75   sales_data_wallpaper.csv
100  100  systems_7z.csv
100  100  systems_BDBC.csv
100  100  systems_HSQLDB.csv
95   95   systems_LLVM.csv
100  100  systems_PostgreSQL.csv
95   95   systems_dconvert.csv
94   94   systems_deeparch.csv
87   96   systems_exastencils.csv
100  100  systems_javagc.csv
72   80   systems_redis.csv
100  100  systems_storm.csv
92   89   systems_x264.csv
91   96   test_dataset120.csv
87   97   test_dataset600.csv

MEAN  binned=77.2  exact=79.4

pick.py

#!/usr/bin/env python3 -B
"""
pick.py, honest train/select/test loop on a moot CSV.
reps times: shuffle; 80 train / 20 test; build a model cloud on a
fit-slice of train, pick the model nearest heaven (recall,prec,fair
all =1) on a validation-slice of train; report that model on test.

Options:
 -s --seed   random seed     seed=1234567891
 -m --models models per run  models=300
 -r --reps   repeats         reps=25
 -n --N      total rows (60/20/20) N=4000
 -v --Val    max val rows    Val=99999
 -p --p      distance exp    p=2
 -R --Round  repr decimals Round=2
 -S --stop   leaf size     stop=None
 -g --group  protected col group=race
 -f --file   data file     file=/Users/timm/gits/moot/classify/COMPAS53.csv
"""

# fft1.py = engine. Generic. Tree, stats, confused, cli. Zero
# fairness knowledge.
#
# pick.py = task. Imports engine, adds problem stuff:
# label/protected col,
# heaven=(recall,prec,fair), 60/20/20 protocol, model cloud.
#
# Why: one engine, many tasks (pick, ablate, thesis, ensemble all
# import fft1). Write tree
# once. Findings bake into engine, all tasks inherit.

import random, os, math
from collections import Counter
import fft1
from fft1 import o, Data, clone, tree, treeLeaf, leaves, confused, csv

the = fft1.settings(__doc__); fft1.the = the

d = lab = grp = groups = None                    # set in load() after cli

def load():
  global d, lab, grp, groups
  d   = Data(list(csv(the.file)))
  yat = next(c.at for c in d.cols.all if str(c.txt).endswith("!"))
  gat = next(c.at for c in d.cols.all if c.txt == the.group)
  lab = {id(r): (0 if r[yat] in ("?", "") else int(r[yat])) for r in d.rows}
  grp = {id(r): r[gat] for r in d.rows}
  groups = [g for g, _ in Counter(grp.values()).most_common(2)]

def setVotes(t):                              # leaf majority, computed ONCE
  for lf in leaves(t):
    lf.vote = int(2*sum(lab[id(r)] for r in lf.rows) > len(lf.rows))

def metrics(train, t, rows):                  # -> (recall, prec, fair)
  pairs = []; gpairs = {g: [] for g in groups}
  for r in rows:
    got = treeLeaf(train, t, r).vote          # precomputed -> just a lookup
    pairs.append((lab[id(r)], got))
    if grp[id(r)] in groups: gpairs[grp[id(r)]].append((lab[id(r)], got))
  c   = confused(pairs).get(1, o(pd=0, prec=0))
  fpr = [confused(gp).get(1, o(pf=0)).pf for gp in gpairs.values()]
  return c.pd, c.prec, min(fpr)/(max(fpr)+1e-32)

def heaven(m): return math.sqrt(sum((1-v)**2 for v in m))   # dist to (1,1,1)

if __name__ == "__main__":
  fft1.cli(the, __doc__)
  load()                                          # load AFTER cli sets -f/-g
  random.seed(the.seed)
  rows = d.rows[:]
  if len(rows) > the.N: rows = random.sample(rows, the.N)
  name = "%s / %s" % (os.path.basename(the.file).split(".")[0], the.group)
  cloud, te_rows = [], []
  for i in range(the.reps):
    random.shuffle(rows)
    n1, n2 = int(.6*len(rows)), int(.8*len(rows))
    fit, val, test = rows[:n1], rows[n1:n2], rows[n2:]      # 60/20/20
    if len(val) > the.Val: val = random.sample(val, the.Val)  # cap if huge
    base = clone(d, fit)
    pos  = [r for r in fit if lab[id(r)] == 1]
    neg  = [r for r in fit if lab[id(r)] == 0]
    best, bestd = None, 1e9
    for _ in range(the.models):
      x   = random.randint(10, 90)
      nps = min(len(pos), round(64*x/100))    # bag 64: ablation-cheap
      bag = random.sample(pos, nps) + random.sample(neg, min(len(neg), 64-nps))
      sub = clone(base, bag); t = tree(sub, 16); setVotes(t)
      mv  = metrics(sub, t, val)                         # held-out selection
      if i == 0: cloud.append(mv)                        # train chart = 1 run
      if heaven(mv) < bestd: bestd, best = heaven(mv), (sub, t)
    te_rows.append(metrics(best[0], best[1], test))         # selected -> test
  print("#", name)                                          # rows: TAG recall fair prec
  for r, p, f in cloud:   print("CLOUD %.4f %.4f %.4f" % (r, f, p))
  for r, p, f in te_rows: print("TEST  %.4f %.4f %.4f" % (r, f, p))

prep.py

#!/usr/bin/env python3 -B
"""prep.py, convert raw fairness CSVs to moot format (4 datasets).
- keep only listed columns (drops leaky/id cols)
- numeric cols -> Uppercase-first (fft1 Num); label -> 'klass!' 0/1
- optional numeric age -> symbolic 'agegrp' (terciles)"""
def isnum(xs):
  n = ok = 0
  for x in xs[:800]:
    n += 1
    try: float(x); ok += 1
    except: pass
  return ok > 0.95*n

def prep(inf, outf, label, positive, keep, age=None):
  rows = [[c.strip().strip('"') for c in ln.split(",")]
          for ln in open(inf) if ln.strip()]
  head, body = rows[0], rows[1:]
  idx = {h: j for j, h in enumerate(head)}
  cols = list(zip(*body))
  agi  = idx[age] if age else None
  if agi is not None:
    av = sorted(float(v) for v in cols[agi])
    q1, q2 = av[len(av)//3], av[2*len(av)//3]
    agrp = lambda v: "lo" if float(v)<q1 else "mid" if float(v)<q2 else "hi"
  out_cols = [h for h in keep]                       # column order to emit
  nh = []
  for h in out_cols:
    if h == label:        nh.append("klass!")
    elif isnum(cols[idx[h]]): nh.append(h[0].upper()+h[1:])
    else:                 nh.append(h.lower())
  if age: nh.append("agegrp")
  with open(outf, "w") as f:
    f.write(",".join(nh)+"\n")
    for r in body:
      vals = [("1" if r[idx[h]] == positive else "0") if h == label
              else r[idx[h]] for h in out_cols]
      if age: vals.append(agrp(r[agi]))
      f.write(",".join(vals)+"\n")
  print("wrote %s  (%d rows, label %s=%s+)" % (outf, len(body), label, positive))

if __name__ == "__main__":
  H = "/Users/timm/tmp/"
  # adult: clean, age->agegrp ; protected gender/race/agegrp
  prep(H+"adultc.csv", H+"adult.csv", "Class-label", "1",
       keep=["age","workclass","education","educational-num","marital-status",
             "occupation","relationship","race","gender","hours-per-week",
             "capital-gain","capital-loss","Class-label"], age="age")
  # dutch: age->agegrp ; protected sex/country_birth/agegrp
  prep(H+"dutch.csv", H+"dutchf.csv", "occupation", "1",
       keep=["sex","age","household_position","household_size","citizenship",
             "country_birth","edu_level","economic_status","marital_status",
             "occupation"], age="age")
  # compas: keep pre-decision only (drop decile_score/is_recid/etc leaks)
  prep(H+"compasC.csv", H+"compas.csv", "two_year_recid", "1",
       keep=["age","priors_count","juv_fel_count","juv_misd_count",
             "juv_other_count","sex","race","age_cat","c_charge_degree",
             "two_year_recid"])
  # diabetes: protected race/gender/age (age already categorical bracket)
  prep(H+"diabetes-clean.csv", H+"diab.csv", "readmitted", "<30",
       keep=["race","gender","age","time_in_hospital","num_lab_procedures",
             "num_procedures","num_medications","number_diagnoses",
             "number_inpatient","number_emergency","readmitted"])

REPRODUCE.md

REPRODUCE: far_ezr.csv, far_bc.png, ezr_bc.png

Prompts for another Claude to regenerate the three artifacts. Each is self-contained once the shared-facts block is pasted in.

Shared facts (paste into any prompt)

Repos live under ~/gists. far.py is in ~/gists/sand-box (imports nuff; run with PYTHONPATH=~/gists/nuff). ezr is ~/gists/ezr/cli.py (command --acquire20, knobs --learn.budget/.check/.start/.leaf). Datasets: 129 CSVs in ~/gists/optimiz/*.csv. nuff (~/gists/nuff/nuff.py) has same(xs, ys, cliff=0.195, conf=1.36) (Cliff's-delta + KS equivalence test).

"best-win" = one holdout rep: shuffle rows, split in half, acquire labels on the train half, grow a tree, sort the held-out half by the tree, take the top check, pick the best of those by true disty, score with wins(data) (0..100, higher = better).

Gotchas: macOS has no timeout; far's landscape must drop >=1 row per level (n = max(1, int((1-keep)*len(rows)))) or high keep infinite- loops; use 8 parallel workers (physical cores) -- don't oversubscribe.

far settings here: grow=4, keep=.66, leaf=3. ezr settings here: start=8, leaf=3.

far_ezr.csv

Compare ezr vs far at budget=50, check=5 over all 129 optimiz datasets. Per dataset: run 20 holdout reps of far (grow=4, keep=.66, leaf=3) and 20 of ezr (start=8, leaf=3), collecting each rep's win. Compute far_mu, ezr_mu (means). delta = round(ezr_mu - far_mu), BUT if nuff.same(ezr_wins, far_wins, cliff=0.35) is True (indistinguishable), set delta = 0. Write CSV columns delta,ezr_mu,far_mu,name, sorted ascending by delta. name = filename minus .csv and minus a category prefix (config_, binary_config_, hpo_, systems_, rl_, sales_, financial_, process_, misc_, ...), trimmed to the shortest unique token; if prefix-stripping collides (e.g. auto93 vs misc_auto93), keep the prefix tag. Parallelize across datasets (xargs -P8). Save to ~/gists/sand-box/far_ezr.csv.

far_bc.png

Heatmap of far's mean best-win over check x budget, fixed grow=4 (every level), keep=.66, leaf=3. Run ~100,000 random trials: each picks a random dataset, check = randint(1,10), budget = randint(10,200), one holdout rep -> win. Bin x=check (10 cols, 1..10), y=budget (10-wide bins, 10..200 -> 19 rows); cell = mean win. imshow with cmap RdYlGn, origin="lower", FIXED vmin=40, vmax=90, extent=[0.5,10.5,10,200]. Overlay black contours at 50/60/70/80/85 (labelled), star at defaults (check=5, budget=50). Parallelize xargs -P8 with a 10%-step progress bar. Save ~/gists/sand-box/far_bc.png.

ezr_bc.png

Same recipe as far_bc.png but for ezr (acquire + tree): fixed start=8, leaf=3; vary check 1..10 and budget 10..200; mean best-win over ~100,000 random trials; same bins, same FIXED scale 40..90, same contours 50/60/70/80/85, star at (5,50). Title: "ezr: mean best-win, start=8 leaf=3". Save ~/gists/sand-box/ezr_bc.png.

TODO.md

TODO: generalize y-target beyond optimization (disty / d2h):

• regression: y = a numeric column; leaf mu predicts it
• classification: y = class likelihood; score by entropy/gini not m2
• optimization: y = disty (current); multi-objective d2h

prompts.md

Ablation prompts — find what gives diversity fastest, drop the inert

Two questions per knob:

1. Does it raise cloud-spread per ms? — keep, dial it to the sweet spot.
2. Does it move test (recall, prec, fair)? — if NO, DROP to its cheapest setting and forget it. (ablate.py found most knobs are inert; the win is bag-ratio-sweep + val-selection.)

Engine fft1.py. Harness pick.py. Driver thesis.py panels. Data compas.csv. Run make zhi for the headline figure.

Common protocol (fix unless varied)

• N=2000 rows, 60/20/20 split, reps=10.
• Bag: ratio-sweep, size=64.
• Split: random-attr L2 best-cut, hist B=7.
• Stop: leaf=16.
• Select: val-pick by heaven(recall, prec, fair).
• p=2.

Metrics

spread     stdev(test-heaven) across cloud (first rep)   ; diversity
uniq       # distinct top-leaf row-sets across cloud      ; geom diversity
ms/model   wall(build all M)/M                            ; cost
heaven     median best-on-val test-heaven (across reps)   ; quality
Δheaven    heaven(this setting) - heaven(reference)       ; effect size

Decision rule (apply to every study)

if |Δheaven| < 0.02 across all values tested:
    DROP slot — pick the cheapest (fastest) setting forever
elif a single value dominates heaven AND raises spread/ms:
    KEEP that setting — it's a real lever
else:
    KEEP with sweet spot from heaven curve

0.02 ≈ ablate.py's noise floor. Tune.

Prompt 1 — BAG SIZE

Q1: does k change cost / spread?
Q2: does k change heaven?
Vary:  k ∈ {16, 32, 64, 128, all-train}
Fix:   ratio-sweep, L2
Drop-if: |Δheaven| < 0.02 across k → DROP, pin k=16 (cheapest)
Expect: small k = high spread, low cost; heaven flat per ablate.
Likely DROP.

Prompt 2 — BAG STRATEGY

Q1: ratio-sweep vs uniform vs 50/50
Q2: does strategy move heaven?
Vary:  bag in {ratio-sweep 10..90%, uniform.sample, class-balanced}
Fix:   k=64, L2
Drop-if: same heaven across all → DROP, pick fastest
Expect: ratio-sweep keeps spread; KEEP per past finding (it's the
ACTIVE lever).

Prompt 3 — SPLIT MECHANISM

Q1: ms/model
Q2: heaven impact
Vary:  random-attr  | fastmap | all-attr best-cut
Fix:   bag=64 ratio-sweep
Drop-if: heaven flat → DROP, pin to cheapest (axis ~2.3× faster)
Expect: heaven flat. DROP. (Confirms ablate; fmpick.py reproduces.)

Prompt 4 — CUT TARGET (the L ladder)

Q: best-cut vs random/median; L2 vs L3?
Vary: cut in {random L0, median L1, best L2, all-attr best L3}
Fix:  bag=64
Drop-if: L0=L1 (label-blind), L2=L3 → DROP toward L2 (cheap, optimal)
Expect: L0=L1 underfit; L2 win; L3 collapses cloud diversity.
KEEP L2 (active lever per levels.py).

Prompt 5 — POLE-PICK SUBSAMPLE k (fastmap)

Q: how few random rows for far-pole selection?
Vary: k ∈ {2, 8, 30, 64, all-rows}
Fix:  SPLIT=fastmap, bag=64
Drop-if: heaven flat → DROP, pin k=8 (tiny, fast).
Spread: smaller k = noisier poles = more diversity. Trade vs stability.

Prompt 6 — STOP / LEAF SIZE

Q: depth?
Vary: stop in {4, 8, 16, 32, sqrt(bag)}
Fix:  bag=64 L2
Drop-if: heaven flat → DROP, pin stop=16 (balance).
Expect: deeper = overfit small bag → heaven drops slightly. Sweet
spot ≈ leaf 16 (CLAUDE.md hardwired).

Prompt 7 — BIN COUNT (cut candidates)

Vary: B ∈ {0=all values, 5, 7, 10, 20}
Fix:  bag=64 L2
Drop-if: heaven flat (per bins.py) → DROP, pin B=7 or all-values.
Expect: candidate count NOT the cost; tree shape is.
DROP.

Prompt 8 — SELECT MECHANISM

Vary: SELECT in {val-pick, train-self, pareto-front, majority-vote}
Fix:  bag=64 L2
Drop-if: NONE — this is the ACTIVE lever per ablate.
Expect: val-pick wins; train-self overfits; vote regresses; pareto unexplored.
KEEP val-pick. Try pareto as new variant.

Prompt 9 — WORTH FUNCTION

Vary: WORTH in {heaven, max-leaf-d2h, min-leaf-d2h, leaf-purity*size}
Fix:  SELECT=on-val
Drop-if: heaven flat across worth fns → DROP, pin heaven.
Expect: heaven dominates classification.
Likely KEEP heaven, drop others.

Prompt 10 — MODELS PER RUN

Vary: M ∈ {30, 100, 300, 800, 2000}
Fix:  bag=64 L2 val-pick
Plot: spread(M), heaven(M), build cost(M).
Drop-if: heaven plateaus by M=300 → fix M=300 (cheap, no quality loss).
This is COST tuning, not a behavior lever.

Prompt 11 — VALIDATION SIZE

Vary: -v in {50, 100, 200, 500, 800}
Fix:  bag=64 L2 M=300
Drop-if: heaven flat by v=200 → pin v=200 (cheap selection).
Below v=100 selection noise dominates → bad.
Find knee.

Prompt 12 — FEATURE SUBSPACE

Q: split over one random col vs subspace of sqrt(cols)?
Vary: subspace ∈ {1 col, sqrt(cols), all-cols}
Fix:  bag=64 L2
Drop-if: heaven flat → DROP, pin 1-col (cheapest, also keeps cloud spread).
Expect (per rf.py): subspace>1 hurts heaven AND collapses diversity.
DROP. Pin 1.

Composite: what should remain in the grammar?

After running 1–12, expected survivors (the real levers):

slot	active?	recommended setting
BAG strategy (ratio-sweep)	YES	10..90% pos sweep, k=16..64
SELECT (val-pick heaven)	YES	held-out val, heaven dist
CUT (L2 best-cut)	YES	best-cut on label
SPLIT mechanism	NO	random-attr (cheapest)
BAG size (within 16..128)	NO	16 or 64 (cheapest in plateau)
FEAT subspace	NO	1 col (cheapest, biggest spread)
BIN count	NO	7 quantile-edges (cheap)
POLE-PICK k	n/a	only if SPLIT=fastmap kept
STOP	NO	16
WORTH fn	NO	heaven
M (models)	tune	M=300 (plateau)
V (val rows)	tune	v=200

Output format

Append rows to learning/ablation.csv:

study,knob,value,spread,uniq,ms_model,heaven,d_heaven_vs_ref
b

r.py

results.md

ruff.toml

rule.py

shorten.py

thesis.py

tree.py