Research: shorter and faster TDL hypotheses by pruning tree rules (plus negative results for forest variants) #672

Update (after #673): the feature-matrix mismatch in follow-up 9 is fixed and merged. All numbers in this body were measured before the fix. A full rerun after the fix gives the same conclusions (F1 about +0.004 for every config; pruned_full_l geo length 21 vs 38, retrieval faster on 18/20 problems), see the comment below. Raw rows: e_fixed_matrix_all.jsonl.gz on the research branch. Follow-up 9 is done.

TL;DR

Pruning the rules of TDL's decision tree gives class expressions that are about half as long and that retrieve their instances roughly 40% as fast on average (5–10× faster on Mutagenesis), with no measurable loss in F1 on the 20 problems tested. This is a simplification of TDL's hypotheses, not an accuracy improvement.

Nothing here supports "strictly better than TDL". Equal F1 was shown as "not significantly different", not as non-inferior within a margin (see Caveats). I'm writing this up so somebody else can continue; the follow-up experiments are at the end.

Along the way I also tried several random-forest-style variants of TDL. None beat a single tuned tree (details and numbers below), which is a useful negative result.

Code: branch feat/tdl-hypothesis-pool (on top of feat/tdl-forest, from develop; both pushed, no PR open), new class TDLForest, files ontolearn/learners/tree_learner_forest.py, ontolearn/learners/tdl_forest_utils.py, tests/test_tdl_forest.py, examples/benchmark_tdl_forest.py. TDL itself is untouched.

Motivation

TDL fits one decision tree on binary class-expression features and reads a class expression back from it. The question was whether a random forest could improve it. A forest's vote has no compact class expression, so the problem becomes: either keep a single hypothesis, or keep a pool of final hypotheses and refine / derefine them. The experiments below start with derefinement (step 1 of the plan: derefine, then refine, then combine).

The approach

Features

As in TDL: every example is a row of binary features; a column is one OWL class expression and is 1 iff the example is an instance of it. The rows are put in a canonical order (positives first, then by IRI) because TDL lists them in set iteration order, which changes with PYTHONHASHSEED, and bagging indexes rows by position.

Rules

A rule is a conjunction of literals (column, holds): the column's expression, or its complement if holds is false. The hypothesis is the union of the rules of a decision tree's positive leaves (root-to-leaf paths ending in a leaf that predicts the positive class).

Derefinement (prune_rules)

Reduced-error pruning on class expressions. Given rules R and rows (X, y):

floor = F1(R) - tolerance                      # measured against the UNPRUNED rules, so edits cannot drift
repeat:
    candidate edits = for each rule:  drop the whole rule        (if more than one rule is left)
                                      drop one literal of it     (if it has more than one literal)
    take the edit with the best F1 on (X, y)   (the first one among equal edits: deterministic)
    stop if that F1 < floor, else apply it

Dropping a literal generalizes a conjunction, dropping a rule specializes the union; both shorten the expression. With tolerance = 0 ties are resolved in favour of the simpler hypothesis, which removes redundancy without changing F1 (lossless on the rows used). The implementation keeps a per-row cover count so one round is cheap.

Which rows decide what is pruned gives the variants:

pruned_full configurations in the tables: pruned_full0 (tolerance=0, lossless), pruned_full_t (tolerance in {0, .01, .02, .05, .1} tuned for inner-CV F1), pruned_full_l (same grid, tuned for F1 - 0.01 * log2(length)).

Evaluation protocol

• 20 problems: 18 synthetic Family tasks (LPs/Family/lps.json), Mutagenesis, Carcinogenesis.
• Repeated stratified 5-fold CV, 4 repeats: 20 outer folds per problem. Features are extracted from the training fold only.
• Nested tuning: hyperparameters are chosen by an inner stratified 3-fold CV on the training fold; the test fold is never seen. Tree grid: max_depth in {None, 3, 5} x min_samples_leaf in {1, 2, 5}.
• Scoring by reasoner semantics: the hypothesis is retrieved from the KB (kb.individuals(h)) and compared with the test labels. (TDL's own feature matrix is not used for scoring, see the last follow-up.)
• Statistics at the problem level: the problem is the independent unit. Paired Wilcoxon on per-problem mean differences, Holm correction within a family of comparisons, bootstrap CI over problems, Friedman test over problems, and the Nadeau-Bengio corrected resampled t-test within a problem.
• Length = characters of the DL rendering of the hypothesis. Retrieval time = time for kb.individuals(h) after one warm-up (the structural reasoner's per-class/per-property caches are warm), minimum of 3 runs, measured inside the same fold and process for all configurations (8 workers on 22 cores).

Results

All configurations (mean over the 20 problems of the per-problem mean over 20 folds)

tree is the default TDL; tree_t is the tree with the grid above tuned by inner CV; tree_l the same tuned for F1 - 0.01 * log2(length); _t = tuned; _l = tuned with the length term. Lengths are geometric means over folds then over problems (arithmetic means are dominated by Mutagenesis/Carcinogenesis).

Per-problem F1

Per-problem median length (chars) / median retrieval time (ms)

Paired comparisons (problem level, F1)

Friedman test over the 14 configurations of the first two runs: chi2 = 127.4, p < 0.0001.

Retrieval time against default TDL (tree), problem level

Difference of log2 retrieval time per problem (negative = faster), paired:

• Length predicts retrieval time: Spearman 0.78 over all folds, 0.94 on Mutagenesis and Carcinogenesis.
• Time falls faster than length: pruned_full0 is 0.25 doublings shorter but 0.84 doublings faster. The redundant sub-expressions that are removed seem to be the expensive ones.
• pruned_full_l was faster than tree in all 156 folds in which it was shorter.
• On the 18 Family problems retrieval takes well under a millisecond either way: the gain matters for the two large KBs.
• Reproducibility: the lengths of the re-run (2,800 rows) match the original run exactly.

Length-aware views

S = F1 - lambda * log2(length) (a doubling of the length costs lambda F1). Mean score at lambda = 0.01: pruned_full_l 0.8969, tree_l 0.8937, tree_t 0.8925, pruned_full_t 0.8917, tree 0.8873. By average rank over problems the untuned tree is best at every lambda (rank 3.5 at 0.01 against 5.5 for pruned_full_l): the shorter configurations win on a few large problems, tree wins on more problems. The conclusion depends on the aggregator. The Pareto front on (F1, length) among the configurations in the table above is {tree_l, pruned_full_l}. Break-even lambda of pruned_full_t against tree_t is 0.011 (CI [0.002, 0.027]); of pruned_full_l it is 0.005 (CI [-0.002, 0.015]).

Negative results (forest variants)

Nothing beat a single tuned tree:

• Majority-vote forests (forest_vote_t) are statistically indistinguishable from tree_t (-0.003, CI [-0.012, +0.007]) but fit about 10x slower (7.6 s vs 0.7 s) and have no compact class expression; the exact vote as a class expression grows combinatorially.
• Selecting high-precision rules from the bagged trees by out-of-bag precision and greedy set cover (rules_t) loses 2.8 F1 points.
• Feature selection by forest importance (fs_t) loses 0.6 points (n.s.).
• A single bagged tree loses about 4 F1 points against a tree on all rows (best_tree_t vs tree_t): it sees about 63% of the distinct rows. Pruning it on its out-of-bag rows (pruned_t) makes it about 5x shorter at no extra F1 loss, but does not recover the gap.
• Tuning the tree (depth, leaf size) is the only thing that raised F1 (0.939 to 0.945, n.s. with Holm, p=0.075 uncorrected). TDL.fit already has its own grid search; I did not compare the two.

Caveats (read before building on this)

1. Equality of F1 is not proven. The F1 differences between pruned_full* and tree are not significant, which is not the same as non-inferior. A real test needs a margin fixed in advance (e.g. 0.01 F1) and an equivalence test (TOST).
2. The metric choices were made after seeing results: lambda in F1 - lambda * log2(length), the use of characters as length, geometric means. The _l configurations were tuned with the same lambda they are scored with at 0.01.
3. Small and skewed sample: 18 of the 20 problems are synthetic Family tasks over one KB (not independent, tiny trees; pruning changes nothing on most of them). Only Mutagenesis and Carcinogenesis resemble real data, and Carcinogenesis often reverses the ranking (e.g. pruned_t is best there and worst on Family).
4. Extraction difference: TDLForest modes read the union of predicted-positive leaf conjunctions, TDL default (positive_paths) uses leaves holding positive training rows. Their mean F1/length agree (tree = full_rules = 0.9393) but I did not prove the hypotheses are equivalent per fold.
5. About 25 configurations were tried; only comparisons inside a stated family have a Holm correction.
6. Timing was done with 8 parallel workers. Within-fold pairing cancels most of the load, but absolute numbers are not clean. Cold-start retrieval is not measured.
7. The raw result rows (about 8,400 JSONL lines from three runs plus the timing run) are in the repository, gzipped, in examples/benchmark_results/tdl_forest/ on the branch (see its README); the tables above are the problem-level aggregates of them.

Follow-up experiments (suggested order)

1. Pre-registered non-inferiority test. Fix, before running anything: margin (0.01 F1), the length measure, lambda or none, the aggregator, the statistic (TOST at the problem level, or a mixed model over folds nested in problems). Then test pruned_full0 (lossless, no tuning, simplest to defend) and pruned_full_l against TDL default and against the tuned tree. Use more repeats to tighten the CI.
2. More and more realistic problems. Add the other KGs/LPs shipped with Ontolearn, noisy labels, larger and deeper trees, and a SPARQL triplestore backend (TripleStore) where the retrieval time of a long expression is a network round trip and the gain should be largest. The two real KBs are where the whole effect lives.
3. A structural length measure and a clean timing harness. Use concept_len / the library's expression-length metric instead of characters; time with no parallel workers, cold and warm caches, and report the number of reasoner calls too.
4. Put the lossless step inside TDL. pruned_full0 removes redundancy without changing training F1. If it is equivalent to TDL's output apart from redundancy, it could be an extraction option (like hypothesis_extraction) rather than a new class. Check the extraction difference of caveat 4 first.
5. Better simplification than literal/rule dropping.
   • Ontology-aware simplification: drop a conjunct entailed by another (e.g. exists r.T next to exists r.C), merge disjuncts that subsume each other (reasoner subsumption checks).
   • Minimal DNF over the feature columns (Quine-McCluskey / Espresso) on the training rows.
   • Put the length into the pruning criterion itself (F1 - lambda * size) instead of tuning a tolerance.
   • Cross-fitted pruning: prune the full-data tree using held-out predictions of K fold-trees.
6. The original plan, not done yet: refine (local search from the pruned expressions with a refinement operator such as CELOE's or EvoLearner's mutations, scored by out-of-bag quality plus a length penalty) and combine (union/intersection of a pool chosen by out-of-bag score). The negative results suggest this must beat the regularization from tuning, which a plain tuned tree already provides.
7. Why does a bagged tree lose 4 points? Try subsampling at 90%, no bootstrap with feature subsampling, and stability selection of rules that appear in many fold-trees, so that the gap to the full-data tree can be closed before pruning.
8. Tuning fairness. Compare against TDL's built-in grid search, not only my grid, and give all methods the same tuning budget.
9. Fix a related TDL issue and re-run everything. TDL trains on a feature matrix that disagrees with the reasoner for a few columns. On the Family Uncle problem, 4 of 352 columns (123 of 26,752 cells, 0.46%) say False in the matrix where the reasoner says True; all four are forall r^-.T (hasChild, hasParent, hasSibling, married). Reproduction:

   import json
   from owlapy.owl_individual import OWLNamedIndividual as I
   from ontolearn.knowledge_base import KnowledgeBase
   from ontolearn.learners import TDL
   from ontolearn.learning_problem import PosNegLPStandard
   s = json.load(open('examples/synthetic_problems.json')); e = s['problems']['Uncle']
   lp = PosNegLPStandard(pos={I(i) for i in e['positive_examples']}, neg={I(i) for i in e['negative_examples']})
   kb = KnowledgeBase(path=s['data_path'][3:])
   m = TDL(knowledge_base=kb, verbose=0, report_classification=False).fit(lp)
   for c in m.X.columns:
       retrieved = set(kb.individuals(c))
       n = sum((i in retrieved) != bool(m.X.loc[i, c]) for i in m.X.index)
       if n:
           print(c, n)

   I do not know the cause or whether fixing it changes accuracy.

Reproduction

# tests
pytest tests/test_tdl_forest.py -p no:warnings          # 33 tests
# the three result sets (results are resumable), new configs go to a new file
PYTHONPATH=$PWD python examples/benchmark_tdl_forest.py run --repeats 4 --workers 16 --out a.jsonl
PYTHONPATH=$PWD python examples/benchmark_tdl_forest.py run --repeats 4 --workers 16 --configs best_tree,pruned,best_tree_t,pruned_t --out b.jsonl
PYTHONPATH=$PWD python examples/benchmark_tdl_forest.py run --repeats 4 --workers 16 --configs full_rules,pruned_full0,pruned_full_t,tree_l,pruned_full_l --out c.jsonl
# the retrieval-time run
PYTHONPATH=$PWD python examples/benchmark_tdl_forest.py run --repeats 4 --workers 8 --configs tree,tree_t,tree_l,full_rules,pruned_full0,pruned_full_t,pruned_full_l --out d.jsonl
# the report (merges several files; includes the length-aware section)
PYTHONPATH=$PWD python examples/benchmark_tdl_forest.py report --out a.jsonl --out b.jsonl --out c.jsonl

Data (KGs/, LPs/) must be downloaded as described in the README. LD_PRELOAD=/usr/lib/x86_64-linux-gnu/libstdc++.so.6 was needed for pytest in my environment.