Many diagnostic problems are naturally trees. Alzheimer's staging runs from healthy, to mild cognitive impairment, to a split between patients whose impairment will worsen and those whose impairment stays stable. Tumor typing runs from organ system to cancer type to subtype. These datasets also tend to have far more measured variables than patients, such as thousands of genes or hundreds of brain regions. That imbalance forces two shortcuts. Researchers collapse the tree into a string of yes/no problems, and they discard variables by scoring each one on its own. Both shortcuts fail in the same place. A combination of genes may separate two subtypes only inside one branch of the tree, while each gene looks like noise at the top. A top-down classifier that trims features at each node will then send some patients down the wrong branch. The model waiting in that branch was built only from correctly routed training patients, so it has no features that could flag the patient as misplaced.
We propose to select features at each internal node of the tree using the patients who actually reach that node under a held-out version of the upstream classifier, not the patients who should have reached it. Each node's selection criterion becomes a multi-way contrast among its children plus one extra group, "intruders," meaning misrouted patients. The node then learns both which child a patient belongs to and whether the patient should be sent back up. The criterion also looks at features in combination rather than one at a time, so it can catch groups of features that are informative only jointly. The claim is testable. In small-sample hierarchical data where some feature synergies exist only within a subtree, this procedure should reduce clinically weighted error relative to three alternatives: univariate per-node selection, global multi-class selection, and flat classification on all features. Most of the gain should come from the intruder group.
Core Claim and What Is New
Error propagation in hierarchical classifiers is usually treated as a routing problem, to be fixed with soft probabilities, stacking, or retreat to an ancestor node. We argue that when features are pruned per node, part of the propagation is caused by feature selection itself. A node's feature subset is optimized for a clean distribution it never sees at test time. Fixing this requires changing what selection is computed on, and this is the new ingredient.
The closest work embeds feature selection inside top-down hierarchies. Embedding feature selection for large-scale hierarchical classification selects features adaptively per node with Gini, Kruskal-Wallis, or MRMR. It reports roughly 2% Micro/Macro-F1 gains and 45% memory savings, but it uses greedy hard routing, filters that miss nonlinear synergies, and nodes trained on clean data. A Hierarchical Feature and Sample Selection Framework and Its Application for Alzheimer's Disease Diagnosis jointly weights features and samples on ADNI-1. It still solves AD vs. NC, MCI vs. NC, and pMCI vs. sMCI as separate binary tasks, and it permanently discards the bottom 5% of samples at each level. That is the opposite of our approach, which keeps ambiguous, misrouted samples and models them explicitly. Neither paper selects features for detecting misrouting.
The method builds on two further papers. Few-Sample Feature Selection via Feature Manifold Learning (ManiFeSt) compares per-class feature-association kernels on the manifold of positive definite matrices. It recovers XOR-100 perfectly and survives on Madelon with 23 samples, but its contrast is between two classes. Stacked Hierarchical Labeling trains lower levels on out-of-fold parent predictions so they learn to distrust parents, but its features are fixed. We extend the ManiFeSt contrast from binary to multi-way. We use the stacking protocol to generate realistic arrival distributions, and we let those distributions drive selection.
Two papers motivate the design. Scalable Feature Selection for Multi-class Problems shows the "accumulative effect": global multi-class filters discard features that matter only for rare classes. This is the flat analogue of our subtree-conditional synergy. Deep Learning for identifying radiogenomic associations in breast cancer documents the cost of forcing a four-subtype problem into Luminal A versus the rest because of small samples, reaching a test AUC of 0.65.
Method
The procedure has three steps. First, fit the tree top-down with K-fold cross-fitting, recording for every training patient the node it reaches under an upstream model that never saw it. Second, at each internal node $v$, form groups for each child of $v$ from correctly routed arrivals, plus one intruder group $I_v$ of arrivals whose true label lies outside the subtree of $v$. For each group $c$, build an RBF kernel $K_c$ over features, compute the geodesic mean $M$ of all group kernels, and map each group to the tangent space as $D_c = \mathrm{Log}_M(K_c)$. Third, score each feature $j$ by how strongly it drives any group's departure from the mean:
$$s_j = \sum_{c \in \mathrm{children}(v) \cup \{I_v\}} \sum_{k} \lambda_{c,k}^2\, \phi_{c,k}(j)^2,$$
Here $\lambda_{c,k}, \phi_{c,k}$ are the eigenvalues and eigenvectors of $D_c$, and $\phi_{c,k}(j)$ is feature $j$'s entry. With two groups and no intruder, this reduces to a ManiFeSt-style binary contrast. Using the tangent space means features are scored through their pattern of association with other features, which is what lets the method detect XOR-type synergy.
Each node's classifier then predicts over its children plus a "send back" output. Predicting "send back" returns the patient to the parent, which reroutes to its next-best child. This is bounded by one retry per level so search does not explode. At inference, the Climbing rule of Hierarchical Selective Classification lets the model stop at a confident ancestor, calibrated by split conformal risk control.
For ultra-high-dimensional nodes (TCGA RNA-seq has 20,530 genes), the $d \times d$ eigendecomposition becomes the bottleneck. We would compute it on a random-block partition of the features with refinement of the top blocks, and we report whether this partition itself loses synergies.
Evaluation Lens
Generic accuracy hides what matters clinically. Evaluating Progress in Automatic Chest X-Ray Radiology Report Generation shows that error-aware metrics like RadCliQ (Kendall-tau b of 0.522 with radiologists) diverge sharply from surface metrics. It also shows that current models beat random retrieval by only 5.5% under the clinical metric. We carry that lesson to structured prediction.
The primary metric is expected clinical cost under a cost matrix $C(y,\hat y)$ over tree nodes, fixed before any experiment. Predicting an ancestor of the truth incurs a small "vagueness" cost. Clinically dangerous confusions, such as calling a pMCI patient NC, cost most. Because any single cost matrix is a choice, we also report three things. First, a sensitivity sweep over a family of cost matrices. Second, the Hierarchical Win of Hierarchical loss for classification. Third, hierarchical risk-coverage curves. A method counts as better only if it wins across the sweep, not at a tuned point.
Research Program
The work has three parts, and the first two decide whether the third is worth running.
First, we build a synthetic "hierarchical XOR" family. The root split is driven by marginally informative features. One subtree's child split is driven by an XOR over features that carry zero marginal signal at the root and at the other subtree. We vary sample size, synergy order, and correlation between irrelevant and causal features. The correlation knob tests ManiFeSt's known "guilt by association" failure. This setting gives a ground truth for which features should be selected where.
Second, we measure the intruder mechanism in isolation. For each node, we quantify how many test-time arrivals are misrouted and how many of those are caught and returned.
Third, we run the full system on real cohorts. ADNI-1 structural MRI (93 ROIs) and SNPs (2,098) are reorganized as the tree NC / impaired → {sMCI, pMCI, AD}. The TCGA Meta-Dataset gene-expression tasks are organized into an organ-system → cancer-type → phenotype hierarchy, using its few-shot splits of 50 train and 100 test.
Baselines
The naive reference point has two parts. One is the majority classifier. The other is flat L2- or L1-regularized multinomial logistic regression on all features, with the cost-minimizing Bayes decision applied to its posteriors. On the TCGA Meta-Dataset, The TCGA Meta-Dataset Clinical Benchmark reports average accuracy of 66.18% for majority, 68.78% for logistic regression, and 71.19% for an MLP across its 174 tasks. We reproduce those protocols exactly and add our cost metrics. Beating the MLP's 71.19% in accuracy is not required. Beating flat logistic regression and the MLP in expected clinical cost, on the tasks where we construct a hierarchy, is required.
The strongest existing per-node method is adaptive per-node selection from Embedding feature selection for large-scale hierarchical classification, run with each of its filters (Gini, Kruskal-Wallis, MRMR) and greedy routing. It is the most direct competitor because it already does node-local selection in the same architecture. The only differences are the scoring criterion and the training distribution.
The strongest global multi-class selector is FCCF from Scalable Feature Selection for Multi-class Problems. It raised average accuracy from 81.57% (FCBF) to 84.32% on its 17 datasets and directly addresses minority-class features without a hierarchy. The strongest synergy-aware selector is ManiFeSt applied one-vs-rest at the leaves.
For error recovery without adaptive selection, we use Stacked Hierarchical Labeling with a global feature set. It reports 78% on MSRC-21, and no reported result found on Lacuna for it on ADNI or TCGA.
On ADNI, the reference numbers are the binary results of A Hierarchical Feature and Sample Selection Framework and Its Application for Alzheimer's Disease Diagnosis: 92.4% AD vs. NC, 80.1% MCI vs. NC, and 80.8% pMCI vs. sMCI accuracy. We will report our tree model's induced pairwise accuracies on the same pairs to show that unification does not cost binary performance. No reported result found on Lacuna for any unified multi-class ADNI hierarchy under a clinical cost metric, so that comparison is new ground.
Fairness rules apply to every method. All methods use identical splits and the same downstream classifier family at each node (logistic regression and RBF-SVM). All get an equal feature budget per node and the same hyperparameter search budget, with 50 configurations each, tuned on inner folds.
The ablations isolate the key ingredient. We remove the intruder group but keep cross-fitted arrivals. We select on ground-truth-routed samples. We replace the manifold score with a univariate score while keeping the intruder group. We use hard routing with no send-back. The proposal's mechanism is confirmed only if removing the intruder group accounts for most of the cost reduction.
Why not just…?
Why not just train a flat multi-class model on all features and apply a cost-sensitive decision rule? This is the most serious threat. The Bayes rule under a cost matrix is optimal given calibrated posteriors, and it uses no hierarchy at all. Its weakness is estimation, not decision. With 50 training samples and 20,530 genes, flat posteriors for rare branches are poorly estimated. The accumulative effect documented by Chidlovskii and Lecerf suggests regularization will shrink away subtree-specific features. Still, if the flat cost-sensitive model matches us on ADNI and TCGA, then the hierarchy is not earning its place in these regimes. We would report that and restrict the claim to the synthetic regime where the answer is known.
Why not just use a strong global multi-class selector such as FCCF or one-vs-rest ManiFeSt? Global selection can keep minority-class features. However, FCCF scores features one at a time and cannot see XOR structure. One-vs-rest ManiFeSt contrasts a leaf against a pooled "rest," which dilutes a synergy that exists only against a sibling. The hierarchical-XOR experiments test this directly by measuring recovery of the planted within-subtree features by each selector.
Why not just use soft routing, or climb to an ancestor when uncertain, instead of changing selection? Soft routing and the Climbing rule of Hierarchical Selective Classification reduce the damage of an uncertain parent. They cannot help when the parent is confidently wrong and the child lacks the features to notice. We apply Climbing to every baseline as well as our method, so any remaining gap is attributable to selection. The ablation that removes only the intruder group measures how much misrouting is invisible to confidence-based retreat.
Decisive Checks
Three results would each change what the proposal can claim. First, on hierarchical XOR, the intruder-aware manifold selector should recover planted subtree synergies that univariate per-node filters and global selectors miss. It should also return a measurable fraction of misrouted test samples. If it recovers the features but catches no intruders, the error-propagation half of the claim fails.
Second, on ADNI-1 and the TCGA Meta-Dataset hierarchies, expected clinical cost should fall relative to both adaptive univariate per-node selection and the flat cost-sensitive logistic model, across the entire cost-matrix sweep. The drop should appear specifically in dangerous confusions such as pMCI called NC, not only in cheap vagueness costs.
Third, the ablation must show that selecting on cross-fitted arrivals with an intruder group, rather than on clean routed data, drives the improvement. If manifold scoring alone explains the gain, the contribution reduces to "multi-way ManiFeSt per node." That is a smaller but still reportable result.
References
- Embedding feature selection for large-scale hierarchical classification
- A Hierarchical Feature and Sample Selection Framework and Its Application for Alzheimer’s Disease Diagnosis
- Few-Sample Feature Selection via Feature Manifold Learning
- Stacked Hierarchical Labeling
- Scalable Feature Selection for Multi-class Problems
- Deep learning for identifying radiogenomic associations in breast cancer
- Hierarchical Selective Classification
- Evaluating progress in automatic chest X-ray radiology report generation
- Hierarchical loss for classification
- The TCGA Meta-Dataset Clinical Benchmark