Yes, another tree classifier. Here's what building one from scratch taught me.

I spent way too long building a tabular classifier from scratch. It doesn't
beat XGBoost. I'm publishing it anyway — with honest benchmarks — because
the honest result seems more useful than a drawer full of code.

Repo: https://github.com/cloudlesson95-arch/hypothesis-tree

The idea

I wanted a tree that makes decisions purely on the input data, where every
decision can be traced back to that data. Not "feature 3 > 0.7 somewhere in
tree #412 of the ensemble" — an actual training row you can print and look
at: this sample matched the cluster anchored on that row, on these
features, within these bounds.

The hope was that finding the proper feature combinations was the key —
that if the model carved multi-feature boxes around groups of errors
instead of splitting one threshold at a time, it could beat the other trees
at their own game.

So the model is a tree of "clusters". Each cluster is a stored training row
(an exemplar), a mask saying which features it cares about, a tolerance box
around it, and a class label. Prediction is routing: a sample descends the
tree through parent-vs-children competitions, and the deepest matching box
wins. Training only grows the tree where it makes mistakes:

seed the root from the first training row
repeat:
    route every training row through the tree
    zero errors? -> done (with some patience)
    for each cluster that caught errors:
        widen it to own its correct rows
        scan features for ranges where errors concentrate
        AND the ranges into a box, carve the box out as a child

How it works — one carve, end to end

Easiest way to show it is a real run. Seven rows, two features, class A in
the lower-left, class B to the right:

row	x0	x1	class
0	1.0	1.0	A ← seeds the root
1	1.5	2.0	A
2	2.0	1.0	A
3	1.2	1.8	A
4	4.0	1.0	B
5	4.5	2.0	B
6	4.2	1.5	B

epoch 0: errors=3 new_clusters=1 total_clusters=2
epoch 1: errors=0 new_clusters=0 total_clusters=2

One carve fixed everything. Here's what happened inside epoch 0.

Everything routes to the root. The root is row 0 with infinite
tolerance — it matches anything, so the untrained model predicts A for all
seven rows. The three B rows are errors ("bads"); the four A rows are
"goods". From here on everything works in diff space — each row expressed
as its offset from the root's anchor [1, 1]:

bad diffs  (rows 4-6):  [3.0, 0.0]  [3.5, 1.0]  [3.2, 0.5]
good diffs (rows 0-3):  [0.0, 0.0]  [0.5, 1.0]  [1.0, 0.0]  [0.2, 0.8]

The parent claims its goods. Before carving, the root's infinite box
collapses to exactly the envelope of its good diffs — [1, 1] to [2, 2]
in absolute terms. The parent now owns precisely the territory it
classifies correctly; the child gets sized against that.

Which feature separates the errors? For each feature, put the bad and
good values on a number line and run a max-subarray scan (Kadane's
algorithm) on the running (bads − goods) count:

feature	best range	bads	goods	net
x0	[3.0, 3.5]	3	0	3
x1	[0.5, 0.5]	1	0	1

x0 is decisive: all three bad diffs sit far from every good diff. x1 is
nearly useless — its value line interleaves bads and goods:

value:  0.0   0.5   0.8   1.0
bads:    1     1     0     1
goods:   2     0     1     1
score:  -1    +1    -1     0     -> best range [0.5, 0.5], net 1

Try to AND features together. The family starts as x0's box (net 3),
then tries adding x1: restricted to the family's rows, x1's best range
would keep only 1 bad — net drops from 3 to 1, so x1 is rejected. The child
will care about x0 only. This greedy AND is the whole point of the stage:
when single features are individually weak but jointly strong, the
intersection can reach a positive net that no single feature has. (Here it
simply had nothing to add.)

Anchor and tolerances. The anchor is the actual bad row closest to the
family's median — row 6, [4.2, 1.5]. Tolerances are the family's extent
around it: -0.2 / +0.3 on x0, so the child's box is [4.0, 4.5] —
precisely the span of the three B rows.

A sanity gate. Before committing, simulate routing for the parent's
four good rows: would any of them now prefer the child? They sit at 0.0–1.0
on x0, hopelessly far from a box starting at 3.0 — the parent keeps all
four. (If a proposed child would swallow its parent's population, its box
gets collapsed to a point instead.)

Commit. The box holds 3 bads and 0 goods — a clean separation, so the
child takes the bads' label:

cluster 1: anchor=[4.2, 1.5], label=B, mask=[1 0],
           tolerance -0.2/+0.3 on x0, parent=0, confidence 1.00

Next epoch, the three B rows descend into the new box and predict B. Zero
errors. And a sample it never saw, [4.1, 1.2], routes [0, 1] → B,
with the explanation being concrete: it matched the cluster anchored on
training row [4.2, 1.5], on feature x0, within [-0.2, +0.3].

The full version of this walkthrough (with the guard rails real datasets
need) is in the repo:
https://github.com/cloudlesson95-arch/hypothesis-tree/blob/main/docs/how_it_works.md

The honest benchmarks

One note before the tables. Everything below runs the basic version of
the algorithm, on defaults — I kept it that way so the idea stays visible
and the code stays readable (~900 lines of NumPy). There are plenty of
tweaks left on the table (just prompt an AI to improve the score). I tried
a bunch of them in another version of this algorithm — and with every tweak
it started looking closer and closer to the methods that already exist. So
this version stays as close to the original idea as possible.

5-fold stratified CV, default parameters everywhere, cells are
accuracy / ROC-AUC / mean fit time.

Dataset	HypothesisTree	DecisionTree	RandomForest	HistGradientBoosting
moons (400x2)	0.843 / 0.842 / 20ms	0.890 / 0.890 / 1ms	0.920 / 0.958 / 72ms	0.915 / 0.961 / 354ms
iris (150x4)	0.933 / 0.950 / 11ms	0.953 / 0.965 / 1ms	0.947 / 0.994 / 62ms	0.940 / 0.986 / 81ms
wine (178x13)	0.826 / 0.866 / 21ms	0.893 / 0.919 / 1ms	0.977 / 0.999 / 67ms	0.966 / 0.998 / 93ms
breast_cancer (569x30)	0.902 / 0.882 / 91ms	0.910 / 0.900 / 6ms	0.956 / 0.989 / 118ms	0.958 / 0.991 / 128ms

And the same protocol over 14 OpenML datasets:

Dataset	HypothesisTree	DecisionTree	RandomForest	HistGradientBoosting
banknote (1372x4)	0.926 / 0.927 / 97ms	0.983 / 0.983 / 2ms	0.993 / 1.000 / 123ms	0.994 / 1.000 / 442ms
blood-transfusion (748x4)	0.762 / 0.532 / 54ms	0.710 / 0.573 / 1ms	0.749 / 0.686 / 84ms	0.749 / 0.691 / 195ms
diabetes (768x8)	0.706 / 0.667 / 505ms	0.700 / 0.672 / 5ms	0.769 / 0.824 / 293ms	0.746 / 0.799 / 592ms
ionosphere (351x34)	0.892 / 0.895 / 226ms	0.897 / 0.889 / 11ms	0.934 / 0.978 / 290ms	0.943 / 0.968 / 349ms
sonar (208x60)	0.669 / 0.658 / 352ms	0.712 / 0.712 / 8ms	0.827 / 0.927 / 267ms	0.841 / 0.935 / 207ms
vehicle (846x18)	0.609 / 0.741 / 1.0s	0.692 / 0.795 / 10ms	0.733 / 0.929 / 340ms	0.771 / 0.928 / 2.4s
qsar-biodeg (1055x41)	0.808 / 0.743 / 1.9s	0.817 / 0.797 / 22ms	0.871 / 0.935 / 455ms	0.882 / 0.936 / 892ms
kc1 (2109x21)	0.850 / 0.594 / 907ms	0.814 / 0.609 / 9ms	0.861 / 0.825 / 188ms	0.857 / 0.776 / 164ms
pc1 (1109x21)	0.924 / 0.610 / 284ms	0.910 / 0.675 / 5ms	0.937 / 0.848 / 127ms	0.930 / 0.833 / 149ms
steel-plates-fault (1941x33)	0.853 / 0.792 / 1.6s	1.000 / 1.000 / 9ms	0.993 / 1.000 / 237ms	1.000 / 1.000 / 91ms
climate-crashes (540x20)	0.896 / 0.510 / 126ms	0.881 / 0.620 / 4ms	0.917 / 0.813 / 106ms	0.906 / 0.844 / 101ms
segment (2310x18)	0.913 / 0.951 / 350ms	0.956 / 0.974 / 11ms	0.972 / 0.998 / 240ms	0.980 / 0.999 / 755ms
wilt (4839x5)	0.938 / 0.530 / 2.2s	0.977 / 0.885 / 9ms	0.982 / 0.989 / 349ms	0.984 / 0.986 / 166ms
phoneme (5404x5)	0.775 / 0.715 / 3.7s	0.872 / 0.843 / 18ms	0.910 / 0.961 / 570ms	0.896 / 0.952 / 156ms

Mean accuracy rank (1 = best): HistGradientBoosting 1.46, RandomForest
1.79, DecisionTree 3.25, HypothesisTree 3.50.

Reading guide: accuracy lands in single-decision-tree territory (it beats
the tree outright on 5 of 14 and is best of all four models on exactly one
dataset, blood-transfusion). The ensembles win, as they do against nearly
everything on tabular data. On imbalanced datasets accuracy holds up but
AUC collapses toward 0.5 — probabilities come from per-cluster confidence,
and most clusters saturate at 1.0, so there's almost no ranking signal.
That one is the weakest part of the model, and it's documented in the
README rather than hidden.

What surprised me

1. A hyperparameter I designed, tuned, and then proved does nothing (as
   probably most of them). The match score is exp(-d/softness) — which is
   monotonic in d, so within any competition the ranking never changes,
   no matter what softness is. I tuned that knob more than once before
   noticing.

2. I tried to make a general learning algorithm — I made a tree. Boxes
   in feature space, growth driven by errors, parent-child structure...
   every design decision that worked pulled the thing closer to the shape
   of the methods I was trying to out-do. There's probably a lesson in
   there about why trees keep winning on tabular data.

3. The tree still overfits to noise, and a neural net handles it much
   better (what a real shock) Error-driven carving means every noisy
   point eventually earns its own little box if you let it — you can see it
   on the moons dataset (noise=0.25), where my model drops below even a
   plain decision tree while smoother models shrug.

Was it worth it?

I started this when nobody around cared about AI, and I genuinely hoped it would beat the established methods. It didn't, and watching the benchmark table say so, fold after fold, was not a great time.

But the gains don't fit in a table. I can derive every decision this model makes from first principles. I learned to benchmark honestly instead of hopefully.

And where a drawer full of code used to be, there's now a tested, documented repo with benchmark tables I don't have to apologize for. That trade I'd take again.

What's next

I'm probably done with the current tree. Maybe PyPI, if anyone cares.

The next thing I want to try is merging MLPs and trees — trees are fast and
well-optimized, neural nets deal with noise and unstructured data, and
surprise #3 suggests they'd cover each other's blind spots.

Repo: https://github.com/cloudlesson95-arch/hypothesis-tree — issues,
benchmarks disputes, and pointers to related work I've missed (RCE networks
and PRIM box-hunting are the closest relatives I found) are all welcome.

Comments

[Luis Cruz]

I appreciate the author's emphasis on transparency and honesty in publishing the results, even when the model doesn't outperform XGBoost. The idea of using a tree of "clusters" where each cluster is a stored training row with a mask and tolerance box is intriguing, and I can see how it could lead to more interpretable results. The use of Kadane's algorithm to find the best range for each feature is also a nice touch. One potential area for improvement could be exploring different methods for combining features, such as using a more sophisticated technique than the greedy AND approach, to see if that could lead to better performance. What are the author's thoughts on exploring other feature combination methods, and do they think that could be a fruitful area for further research?

[new_char]

Honesty, no. I don't think that exploring other feature combination methods can bring any more gain. Spending so much time on it, I now can see why we need some early validation gate to cut off wrong 'hypothesis' fast and not trying to overfit on them further. And the reason why we need to find and follow the gradient to avoid getting stuck in the noise data.

[Sachin Kr. Rajput]

The AUC collapse you flag as the weakest part has a cheap, well-studied fix, and it isn't in the algorithm — it's in how cluster confidence becomes a probability.

AUC is purely rank-based. If most clusters saturate at 1.0 you don't have a weak ranking, you have a massive tie, and ties drag AUC toward 0.5 mechanically no matter how good the boxes are. Accuracy holding up while AUC craters is the signature of exactly that, which is why those two columns disagree so violently on your imbalanced sets.

Instead of p = k/n per cluster — which hits 1.0 the moment a box is pure, as in your worked example committing 3 bads / 0 goods at confidence 1.00 — use a Laplace estimate: (k+1)/(n+2). That pure 3/0 box becomes 4/5 = 0.80. A pure 30/0 box becomes 31/32 = 0.97. Nothing about the tree changes, but support now breaks the tie, so well-evidenced boxes outrank lucky small ones. That is precisely the signal AUC is looking for.

Provost and Domingos went at this directly in "Tree Induction for Probability-Based Ranking" (Machine Learning, 2003). Their result was that Laplace correction plus not pruning is what makes tree probability estimates rankable, and that accuracy and AUC pull against each other for exactly this reason. Your error-driven carving already gives you the unpruned half for free.

If you want finer resolution inside a cluster, normalised distance to the box edge gives you a continuous margin — deep inside the box should score above clinging to the boundary.

On surprise #2, though: I'd push back on reading it as a failure. Axis-aligned boxes plus error-driven growth is the tree hypothesis space. Once you picked those two commitments the convergence was structural, not a shortage of imagination.