Ontology-Backoff Decision Lists for Tiny Clinical Cohorts

A decision list is a stack of if-then rules read from the top down. The first rule that matches a patient gives the answer, and every rule below it is ignored. Yarowsky-style lists order their rules by how lopsided each feature's class split is, measured as the absolute log-likelihood ratio between the two classes. This works very well when every feature is seen many times. In a hospital cohort of 36 or 100 patients, that assumption breaks. Most diagnosis and medication codes appear once or twice, so a code seen once in a patient who died gets an extreme ratio and jumps to the top of the list. The proposal is to fix this ranking step in two ways. First, estimates for rare codes are borrowed from their parents in the medical code hierarchy; for example, a rare ICD code borrows strength from its three-digit category and chapter. Second, rules are ranked by a pessimistic lower confidence bound on the ratio rather than by its point estimate. As a result, each rule is stated at whatever level of the hierarchy the data can actually support, and a spurious one-patient rule cannot outrank a well-supported one.

This matters because the methods that currently cope with tiny clinical cohorts do so by giving up transparency. MiME builds the visit→diagnosis→treatment hierarchy into neural embeddings. GraphCare anchors codes to medical knowledge graphs and reports that training on 36 MIMIC-III patients matches baselines trained on 720. Both show that hierarchical medical structure is what makes small-data learning possible, and both produce representations a clinician cannot read. The question is whether the same structural prior, placed directly in the ranking statistic of a rule list, recovers much of that data efficiency while keeping a checklist a clinician can audit.

Core Claim

Let $c$ be a code feature and let $a_1(c), a_2(c), \dots$ be its ancestors in the ontology, with $a_0(c)=c$. Let $n_{\ell,y}$ be the number of training patients with class $y$ who carry ancestor $a_\ell(c)$. We estimate class probabilities at each level by shrinking toward the next level up:

$$\tilde p_\ell(y) = \frac{n_{\ell,y} + m\,\tilde p_{\ell+1}(y)}{n_{\ell} + m},$$

Here $n_\ell=\sum_y n_{\ell,y}$, $m$ is a pseudo-count chosen by nested cross-validation, and the root level is anchored at the class prior. The rule proposed for $c$ is stated at the level that maximizes a lower confidence bound on the absolute log ratio:

$$\text{score}(c) = \max_{\ell}\; \mathrm{LB}_\alpha\!\left(\left|\log \frac{\tilde p_\ell(y_1)}{\tilde p_\ell(y_2)}\right|\right).$$

$\mathrm{LB}_\alpha$ is a one-sided bound at level $\alpha$. We will compute it by a Beta-posterior interval on the shrunk counts, and check it against a bootstrap.

The list is then built Yarowsky-style: rules are sorted by this score, a rule is dropped once its bound falls below zero, and patients covered by earlier rules are removed before later rules are rescored, as in CN2's covering loop. The claim to be tested has two parts. At training sizes of roughly 36 to 720 patients, this list will match or beat fixed-level rollups and unregularized decision lists in AUROC at equal list length. It will also produce rule orderings that are markedly more stable across resamples and far less likely to contain rules when labels are pure noise.

Relation to Prior Work

The ranking statistic comes from Decision Lists for Lexical Ambiguity Resolution, which ranks collocations by absolute log-likelihood ratio and exceeds 99% accuracy on accent restoration using corpora of tens of millions of words. We keep the statistic and the first-match semantics and change what happens when counts are tiny. The same statistic was reused on small, flat feature sets in Decision Lists for English and Basque and Metonymy Resolution as a Classification Task; neither uses hierarchical backoff.

The CN2 Induction Algorithm supplies the covering procedure and a precedent for significance filtering. It uses a likelihood-ratio test to reject rules that do not differ from chance, evaluated on Ljubljana cohorts of 148–339 patients. It also constrains our design, since it reportedly still found spurious rules under 100% label noise. We therefore treat pure-noise behavior as a first-class measurement rather than assuming a significance cutoff is enough. CN2 also works on flat attributes and has no way to move a rule up a hierarchy.

Probabilistic scoring lists is the closest existing work. It attaches Clopper-Pearson intervals to the probabilities output at each stage so that downstream stages with little data report epistemic uncertainty. Our proposal differs in two ways. PSL uses the interval to report uncertainty about a prediction, whereas we use it to decide which rule goes first and at what level of abstraction. PSL also adds points across features, whereas we keep the non-compensatory first-match structure and use the ontology.

Global rule-list optimizers, Falling Rule Lists and Scalable Bayesian Rule Lists, search over orderings of pre-mined itemsets. They are complementary: our backoff estimates could supply their candidate rules. But they inherit whatever feature granularity they are given, and FRL was not tested below 100 samples.

Two results bound what we should expect. Comparative Experiments on Disambiguating Word Senses showed that additive models beat decision lists when evidence is spread over many weak features. A Comparison between Supervised Learning Algorithms for Word Sense Disambiguation showed rule systems collapsing under domain shift. We address both head-on in the experiments rather than assuming them away.

Research Program

We will build the estimator and list inducer over the ICD-9 diagnosis hierarchy (code → three-digit category → chapter) and a medication class hierarchy for MIMIC-III. We will then establish three properties.

The first is statistical. Under a simple generative model, where child codes inherit their parent's class ratio plus noise, we will show that ranking by the lower bound is consistent. We will also show that the chosen level moves down toward the leaf as $n$ grows, at the rate at which the bound's width shrinks, which is roughly $1/\sqrt{n_\ell}$ from the Beta posterior's variance. This yields a testable prediction: the average depth of selected rules should increase with cohort size.

The second is empirical accuracy and parsimony against strong baselines at matched list length.

The third is reliability, measured as rule stability across bootstrap resamples and the false-rule rate under permuted labels.

Baselines

The naive reference point is the majority-class predictor together with an unregularized Yarowsky list on leaf codes, ranked by point-estimate log ratio with add-0.5 smoothing. This is the "do nothing" version of the direction. It should show the failure mode directly: extreme ratios on singleton codes.

The strongest transparent competitor is L1-regularized logistic regression on the union of indicator features at all three hierarchy levels. The regularization lets the model choose its own level. It is strong because additive models won in the many-weak-indicators comparison, and logistic regression reached 0.82 AUROC versus FRL's 0.80 on the ~8,000-patient readmission data in Falling Rule Lists. We will cap its number of nonzero coefficients to match our list length and also report it uncapped.

The strongest rule-list competitor is SBRL, run with the sbrl R package, on features rolled up to a fixed hierarchy level. Each level is tried and the best one is chosen on validation data, so this baseline gets the hierarchy but without per-rule adaptivity. We will also run Probabilistic scoring lists on the same multi-level features.

As an opaque ceiling we cite GraphCare. Its reported figure is a 17.6% AUROC gain on MIMIC-III mortality from the knowledge-graph augmentation, and it matches 2.0%-data baselines with 0.1% data. We found no reported absolute AUROC on Lacuna for GraphCare at the 36-patient subset. We will therefore rerun it on our splits if its code is available, and otherwise report only the relative comparison.

All methods get identical patient subsamples (36, 100, 360, 720 training patients, 20 random draws each), the same feature extraction, and the same nested cross-validation budget of 50 configurations. Beating the logistic baseline means matching its AUROC within the bootstrap confidence interval at equal size while giving higher top-5 rule stability. Beating SBRL-with-rollup means higher AUROC at equal list length at the two smallest sizes.

Two ablations isolate the ingredients. One ranks by point estimate with backoff. The other ranks by lower bound without backoff, on leaves only.

Why not just…?

Why not just use L1 logistic regression on all hierarchy levels? This is the real threat. If evidence for mortality is diffuse, it may win on AUROC at every size, as Mooney's results predict. We do not argue around this. The experiment reports AUROC at matched size, and if logistic regression dominates, the remaining contribution is narrower: a first-match list with the same accuracy but a stable, readable ordering. We will say plainly whether that narrower result holds. We will also measure the fraction of test patients decided by a single top-3 rule. This shows whether the task has "smoking gun" structure at all, and so whether a decision list is the right tool for it.

Why not just roll codes up to a fixed level and run an ordinary decision list or SBRL? A fixed level either wastes data-rich leaf codes (a specific sepsis code seen 40 times) or keeps useless singletons. The fixed-rollup SBRL baseline, tuned over levels, tests this directly. If per-rule adaptivity adds nothing over the best fixed level, the backoff estimator is unnecessary, and the ablations will show it.

Why not just use probabilistic scoring lists, which already model epistemic uncertainty? PSL's intervals quantify uncertainty in outputs, not in the ranking. PSL also does not use the ontology. Running PSL on the same multi-level features separates the value of hierarchy from the value of our ranking criterion.

Why not just fine-tune a pre-trained model or use GraphCare? Evidence from Unveiling COVID-19 from Chest X-ray shows that high-capacity models on 447 images learn site artifacts: sensitivity was 0.54, and deeper networks overfit more. GraphCare avoids this with knowledge graphs but produces representations clinicians cannot inspect, and its 2-hop sampling injected noise that clinicians had to check. We treat it as an accuracy ceiling, not as a competitor for the same use.

Proposed Experiments

The main benchmark is MIMIC-III in-hospital mortality and readmission, using the GraphCare-style subsample sizes, with AUROC, list length, and top-5 rule Jaccard stability across bootstraps as metrics.

The first decisive check is a pure-noise test: labels are permuted and we count how many rules each method emits. CN2's reported spurious rules make this a direct test of whether the lower bound fixes that failure. The target is zero rules in at least 95% of permutations, with $\alpha=0.05$.

The second check is the depth prediction from the theory: the mean hierarchy level of selected rules should decrease monotonically, toward leaves, from 36 to 720 patients.

The third check is shift. We train on MIMIC-III and test on MIMIC-IV admissions from later years. We found no reported result on Lacuna for small-cohort MIMIC-IV mortality, so all numbers there are new. This shift is temporal and within one institution, so we will describe it as a weak portability test, not a cross-site one. The prediction is that hierarchy-level rules degrade less than leaf rules because they depend less on site-specific coding habits.

A secondary sanity check reruns the Ljubljana Lymphography cohort, where CN2 reports 82% accuracy with 12 selectors. It has no ontology, so it tests only the lower-bound ranking. Our list should match that accuracy at comparable size.