Budgeted Interaction Search for Ordinal Clinical Risk Scores

Clinical risk tools usually have to do three things at once. They must sort patients into ordered stages (healthy, mild, severe), where calling a severe case healthy is far worse than calling it moderate. They must use only a handful of inexpensive measurements. And they must capture the fact that risk factors combine non-additively, as when a modest drop in blood pressure matters only in an older patient with a raised heart rate. Today these steps are done one after another. Variables are pruned first, by stepwise selection or an L1 penalty (a penalty on the absolute size of weights that pushes many of them to exactly zero). A flexible model is then fit to whatever survives. This proposal argues that the order is wrong. A variable whose value shows up only in combination with others looks useless to a size penalty applied before interactions are modeled, so it is removed before the interaction model can use it.

We propose to treat the choice of variables and the choice of how they interact as a single constrained architecture search. The building block, or "cell," is a small interaction unit: a learned function of at most three chosen variables. A model is a sum of such cells feeding one latent severity score. That score is cut into stages by ordered thresholds, so the stage predictions can never contradict one another. The total cost of acquiring the chosen variables is a hard budget. Following the lesson from tabular architecture search that soft penalties trap the search, the budget is enforced by discarding over-budget candidates rather than by penalizing them. The claim we test is simple. Under a fixed measurement budget, this search keeps conditionally useful variables that penalty-based and greedy selection throw away, and it gives better ordinal accuracy per unit of acquisition cost.

Core Claim

The mechanism comes from TabNAS. That work searches the layer widths of tabular networks under a parameter limit. It showed that adding a penalty to the reward makes a factorized search controller (one that samples each choice independently) penalize wide layers wherever they occur. As a result, it misses asymmetric narrow–wide–narrow "bottleneck" networks. On Criteo it settles on 32-64-96 instead of the optimum 32-144-24. TabNAS fixes this with rejection sampling, which silently drops models that violate the limit, plus a Monte-Carlo correction to the policy gradient.

Our hypothesis is that feature selection has the same pathology. An expensive or individually weak variable is penalized every time it is sampled, even though it pays off only inside a particular interaction cell. We therefore move the TabNAS mechanism from the internal width of a network to which inputs the model uses. This is a question TabNAS explicitly leaves untouched, since it keeps the input fixed.

The cell constraint does two jobs. Searching over arbitrary interaction graphs on dozens of clinical variables is exactly the combinatorial blow-up that curriculum search warns about. Capping each cell at order three and stacking cells additively keeps the space small. It also keeps every component auditable as a slice plot. This deliberately extends NODE-GAM, whose differentiable oblivious trees are annealed to use one or two features each. NODE-GAM gives up three-way interactions for the sake of 2D visualization, and it applies a uniform pairwise structure to all variables rather than searching which variables earn an interaction.

The ordinal head is a constraint, not the novelty. We use a cumulative-link form

$$P(y > k \mid x) = \sigma\big(s(x) - \theta_k\big), \quad \theta_1 < \dots < \theta_{K-1},$$

where $s(x)$ is the sum of cell outputs, $\theta_k$ are learned ordered cutpoints, $\sigma$ is the logistic function, and $K$ is the number of stages. Because every stage boundary is a level set of the same score, boundaries cannot cross. NORDIC achieves non-crossing for kernel SVMs, where each stage gets its own decision function, through quadratic or mixed-integer programs that do not scale. We get non-crossing for free, at the price of a single shared score. That price is real, and we measure it against NORDIC-style decomposition below.

Research Program

Search space. The model has up to $C$ cells. Each cell chooses an order (one, two or three) and that many variables from a pool of candidate measurements. Each variable $j$ carries an acquisition cost $c_j$, set by a cost tier: demographics, bedside vitals, routine labs, specialized assays, imaging. A candidate is valid only if the summed cost of the distinct variables it uses is at most a budget $B$. A variable reused across several cells is paid for once. This is the asymmetry a per-use penalty gets wrong.

Cells and training. Each cell is a small multilayer network or a soft oblivious tree on its chosen inputs. Cells are trained jointly under the ordinal head.

Search procedure. A factorized REINFORCE controller (a policy-gradient method that learns which choices lead to good models) samples cell configurations. Over-budget samples are rejected, and the gradient is reweighted by the estimated acceptance probability, as in TabNAS. Candidates are scored on validation quadratic weighted kappa. Because the per-candidate models are small tabular networks, we can train them standalone or with a short warm-up. This sidesteps the shared-weight ranking errors noted for one-shot search in TNAS.

Pareto frontier. Sweeping $B$ traces a curve of ordinal accuracy against acquisition cost, and this curve is the main deliverable. It speaks directly to the tension in the file between data-hungry imaging models (DCP, the liver fibrosis staging system) and evidence that a few cheap signals suffice. Examples of the latter are vitals nearly matching vitals plus 34 labs for in-hospital cardiac arrest in Ueno et al., and a single plasma p-Tau217 matching amyloid PET in the MCI survival study.

Analysis. For every variable that the search keeps and the baselines drop, we report its single-variable importance and its importance within its cell. This tests whether the mechanism is really conditional value rather than chance.

Baselines

The naive reference point is the cheapest sensible clinical tool. For ADNI staging, that is a cumulative-link ordinal logistic model on demographics plus one cognitive score. For conversion prediction, it is the single p-Tau217 marker. The strongest reported number for that marker is a 4-year conversion AUROC of 0.787, against 0.758 for amyloid PET, from a Random Survival Forest in the MCI survival study. We will reproduce that setting on whatever ADNI plasma subset is available and report our model at matched and at lower cost. We will not treat 0.787 as directly comparable unless the cohort matches. For the imaging-based ordinal models, DCP reports a conversion AUC of 0.7957 (versus 0.7345 for SuStaIn), and HOPE reports 72.0% accuracy on ADNI. Both use full MRI or diffusion imaging. They serve as high-cost anchors at the expensive end of the frontier, not as competitors at equal cost. For the public ordinal Wine-quality target, no reported result was found on Lacuna for ordinal metrics; NODE-GAM evaluates on Wine, but the file gives no per-dataset figure.

The strongest competitor on the actual question is greedy budgeted forward selection wrapped around gradient-boosted trees (LightGBM with cumulative binary targets, monotone across thresholds by post-hoc sorting). At each step it adds the variable with the best validation-kappa gain per unit cost until the budget is spent. This baseline is dangerous because it evaluates each candidate with the interactions trees capture natively. The pTNAS paper found boosting competitive across 11 tabular datasets, even though its searched networks had the best average rank (pTNAS).

The second strong competitor is NODE-GA²M with our ordinal head and a group-L1 penalty on per-feature gates, swept over penalty strength to hit each budget. It isolates whether learned pairwise interactions plus a soft penalty already suffice.

We also run NORDIC-1 on the variables our search selects. This prices the shared-score restriction, and if NORDIC's flexible boundaries win on the same inputs, we say so.

All methods get the same splits and the same per-budget pool of candidate fits (equal numbers of trained models and equal wall-clock on one GPU or CPU node). All use the same hyperparameter-search budget for the downstream learner. We count beating a baseline as a higher area under the kappa-versus-cost frontier over three or more random splits, with a paired bootstrap interval excluding zero.

The key ablation keeps our exact search space and controller but replaces rejection sampling with a cost penalty in the reward. A second ablation caps cell order at two. A third replaces the ordinal head with multiclass cross-entropy.

Why not just…?

Why not just run greedy forward selection with gradient-boosted trees? This is the real threat. Because trees model interactions while each variable is being evaluated, greedy selection may already avoid the pruning failure we target. Its known weak spot is variables that help only as a pair added together: a one-step-lookahead greedy method sees no gain from either alone. The synthetic experiment plants exactly this case. Clinical datasets will show whether it matters in practice. If greedy GBDT matches our frontier on ADNI and Wine, we will report that constrained search is unnecessary there. The contribution then reduces to the cost-aware ordinal benchmark and the synthetic diagnosis.

Why not just use NODE-GA²M or an Explainable Boosting Machine with an L1 penalty? These are glass-box models: additive models of one- and two-variable functions whose components can be plotted. They give interpretability directly. NODE-GAM reports beating the Explainable Boosting Machine by up to 7.3% on large datasets, and spline GAMs running out of memory on 5 of 6 (NODE-GAM). Neither model, however, has a budget over distinct variables, and both drop three-way terms. TabNAS's Criteo result is direct evidence that penalty shaping misallocates capacity under factorized sampling. Our penalty-versus-rejection ablation, run inside one search space, tests whether the same holds for input selection.

Why not just use the single best biomarker? For MCI conversion this is a strong answer (AUROC 0.787 for p-Tau217). Parsimonious tools are also known to degrade under shifts in setting: the ICU collapse to about 0.58–0.64 AUC in Ueno et al., and geographic transfer loss in Zhang et al.. Single markers also give no ordinal staging across three or more levels. The single-marker point sits on our frontier. If nothing beats it at modestly higher cost, that is itself the finding.

Why not just enumerate all small feature subsets? With roughly 30 variables and five chosen, there are about 142,000 subsets, which is enumerable with fast learners. Adding interaction-structure choices multiplies the count far beyond that. We will run exhaustive enumeration on the synthetic task and on the smallest budget level as a ground-truth check on how close the search gets.

Proposed Experiments

Synthetic task. Twenty to forty variables, a five-level ordinal outcome generated from a latent score, and a planted three-way interaction among two cheap variables and one expensive variable that has zero marginal effect. The decisive check is whether each method keeps the expensive variable once the budget allows it. We expect the penalty-based and greedy baselines to keep it less often than rejection-sampled search across 20 seeds. Exhaustive enumeration provides the oracle.

ADNI tabular staging. NC, MCI and AD staging from ADNI tabular data, with cost tiers spanning demographics, cognitive batteries, plasma markers, CSF and PET-derived summaries. A second ordinal task bins MCI time-to-conversion into stable, late converter and early converter. This addresses the discrete-only framing HOPE leaves open. External transfer to NACC follows HOPE's protocol (which reports 67.6%), if variable overlap allows.

Wine quality. The NODE-GAM suite's Wine-quality target as a public ordinal sanity check.

Metrics. Quadratic weighted kappa, mean absolute stage error, boundary-crossing rate for the decomposition baselines (zero for ours by construction), acquisition cost, and area under the kappa-versus-cost frontier.

Falsification. The proposal fails if the penalty-shaped ablation matches rejection sampling, or if greedy GBDT matches the full method on all real datasets. In that case, the synthetic pruning failure is not practically relevant.