A doctor reasoning about a new ICU patient often asks, "Which past patients looked like this one, and what happened to them?" A nearest-neighbor Gaussian process (GP) works the same way. A GP is a Bayesian regression model that returns both a prediction and an honest error bar. The nearest-neighbor version makes it fast by having each prediction look only at the few dozen most similar training points. For such a model, the prediction is an explicit weighted average of those neighbors' outcomes, and the error bar widens when the neighbors are far away or disagree. The explanation therefore is the computation, not a story told after the fact. The weak point is the word "similar." Current scalable versions find neighbors by plain Euclidean distance on raw features. Their own authors flag this as a limitation, and it is badly suited to clinical records, where variables are correlated, differently scaled, and mostly irrelevant to any single outcome.
We propose to learn the similarity itself as a short list of sparse, readable directions, each a weighted combination of a handful of clinical variables. Directions are added one at a time, and each new direction is chosen to most improve the GP's own held-out predictions on its neighbors. The result is a model with three properties that are rare to find together. It scales to tens of thousands of patients and hundreds of features without the cubic-cost matrix projections that usually make learned distances expensive. Its similarity notion can be read off as, for example, "direction 1: lactate up, mean arterial pressure down." Every prediction comes with the specific historical patients that produced it and a calibrated statement of how much to trust them. The accuracy–interpretability trade-off becomes a dial with two settings: how many directions are allowed, and how many variables each may use. We will measure that dial directly.
Core Claim
Learning a low-rank Mahalanobis metric (a distance that first projects inputs onto a few learned directions, then measures ordinary distance there) by greedy sparse rank-one additions has three consequences. The objective is the nearest-neighbor GP's own leave-one-out likelihood, not a classification margin. With a small number of directions $r$ (we expect $r \le 10$) and a small number of variables per direction, it should match the predictive accuracy of the same GP with an unconstrained learned metric. It should also beat Euclidean and per-feature-lengthscale neighbor GPs on clinical prediction, and produce variance estimates that flag errors under hospital-to-hospital shift. A full metric matrix is never stored or eigen-decomposed, because each step needs only the leading sparse eigenvector of a gradient that we access through matrix–vector products.
Concretely, let $x_i \in \mathbb{R}^d$ be patient features, $y_i$ outcomes, and $M = \sum_{j=1}^{r} w_j v_j v_j^\top$ with weights $w_j \ge 0$ and sparse unit vectors $v_j$. Then $M$ is positive semi-definite by construction. Let $N_M(i)$ be the $K$ nearest neighbors of $i$ under $d_M$, and let $p(y_i \mid y_{N_M(i)}, M)$ be the local GP predictive density at $x_i$ given those neighbors, using a unit-lengthscale kernel on the projected coordinates. We maximize
$$ \mathcal{L}(M) = \sum_{i=1}^{n} \log p\big(y_i \mid y_{N_M(i)}, M\big). $$
At each round, with neighbor sets held fixed, the next direction is
$$ v_{r+1} = \arg\max_{\|v\|_2 = 1,\ \|v\|_0 \le s} \; v^\top G v, \qquad G = \nabla_M \mathcal{L}(M), $$
followed by refitting the weights $w \ge 0$ and recomputing neighbors in the new $r{+}1$-dimensional projected space. Here $s$ is the per-direction variable budget. The gradient $G$ is a weighted sum of outer products $(x_a - x_b)(x_a - x_b)^\top$ over neighbor pairs. Multiplying it by a vector therefore costs $O(nK^2 d)$ without ever forming the $d \times d$ matrix, and a truncated power method finds the sparse leading direction at a cost linear in $d$. Neighbor search runs in $r$ dimensions rather than $d$, which sidesteps the retrieval slowdown that limits high-dimensional nearest-neighbor GPs.
Where This Sits
Three bodies of work supply the pieces, and none of them assembles this combination.
The method comes from scalable metric learning. Efficiently Learning a Distance Metric for Large Margin Nearest Neighbor Classification builds a metric as a non-negative sum of rank-one terms, each found as a leading eigenvector. This cuts per-step cost from $O(d^3)$ to $O(d^2)$ and gives up to 200x speedups over standard large-margin nearest neighbor learning on spambase. We reuse the rank-one construction but change two things. The objective becomes a GP predictive likelihood rather than a classification triplet margin, and the eigenvector is constrained to be sparse. That paper's own "tailing-off" near the optimum matters less for us, because we deliberately stop after a few directions.
Efficient distance metric learning by adaptive sampling and mini-batch SGD motivates the cost concern. It identifies the full eigen-decomposition as the bottleneck and reduces isolet runtime from over 35,000 seconds to under 4,000. We avoid that projection entirely rather than amortizing it.
Compressive Mahalanobis Metric Learning Adapts to Intrinsic Dimension shows that metric-learning error tracks intrinsic rather than ambient dimension. We read this as support for our premise: clinical outcomes depend on a few directions, so a low-rank metric loses little. Its random projections, however, give no readable directions.
The regime and the open problem come from local GPs. Variational nearest neighbor Gaussian process (VNNGP) conditions each point on its $K$ nearest neighbors through a sparse precision prior and beats an inducing-point GP with 1,024 inducing points using $K=32$. Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression (GPnn) estimates kernel parameters on a subset, predicts from test-point neighbors, recalibrates variance cheaply, and handles $1.6 \times 10^6$ points in about 30 seconds. Both use Euclidean neighbors, and GPnn reports that neighbor search degrades as dimension grows. Our contribution is to learn the neighbor geometry for these models. We keep GPnn's prediction and calibration machinery unchanged so that any gain is attributable to the metric.
The closest prior combination is Variational Inference for Mahalanobis Distance Metrics in Gaussian Process Regression (VDMGP). It learns a projection $z = Wx$ inside an inducing-point GP with a relevance prior that prunes inputs, for example finding 4 of 32 relevant dimensions on Puma. We differ in three ways. Our GP is local, which avoids the over-smoothing of global low-rank approximations. Our directions are sparse and added greedily in order of importance rather than learned jointly and densely. And we target clinical classification under site shift, which VDMGP never tested.
The interpretability motivation comes from clinical case-based reasoning. Safe and Interpretable Estimation of Optimal Treatment Regimes learns a matching metric over 995 ICU patients and treats patients by interpolating matched successful cases. It reports a 23.6 percentage-point estimated reduction in adverse outcomes and wins against 49 baselines in simulation. This is the strongest evidence in the file that matching-based models can be both auditable and competitive. Its matching is deterministic, though, and its metric learning was not built for large cohorts. Our proposal is in effect a probabilistic, scalable version of that design for prediction (not treatment choice).
Concept bottleneck and prototype models, such as those examined in Is ProtoPNet Really Explainable?, constrain the design. They show that learned prototypes can drift away from meaningful content. In our model the "prototypes" are real retrieved patients by construction, and the risk moves to whether the learned directions are themselves meaningful. We test that risk directly with the sparsity budget.
Research Program
The first component is the learner. We will implement the greedy loop described above with a Gaussian likelihood for regression. For binary clinical outcomes, we will use a local probit likelihood fit by a Laplace approximation on each $K$-point neighborhood, which is cheap because $K$ is 32 to 64. The loop has four steps:
- Fit the leave-one-out objective on a random subset of a few thousand anchor points, following GPnn's observation that parameter estimation can be done cheaply on subsets.
- Compute the sparse leading direction through matrix–vector products.
- Refit the non-negative weights with a few gradient steps.
- Rebuild neighbor indices in the projected space.
Prediction then uses GPnn's procedure, including its variance recalibration, in the learned space.
The second component is the explanation object. For each prediction, we report two things. The first is the $K$ retrieved patients with their GP weights, the vector $k_*^\top (K_{NN} + \sigma^2 I)^{-1}$, which exactly reproduces the predicted mean. The second is the $r$ directions with their nonzero clinical variables. We will also report where the query and each neighbor fall along each direction, so that a reader can see why two patients were considered close.
The third component is the trade-off map. We sweep the number of directions $r$ from 1 to 20 and the per-direction budget $s$ over 3, 5, 10, and unrestricted, and trace accuracy and calibration across that grid. The scientific question is how quickly the curve flattens. If a handful of five-variable directions captures most of the gain from an unconstrained metric, the trade-off is mild in this regime. If it does not, we will report that directly.
The data come from MIMIC-III processed by MIMIC-Extract. We use summary statistics of its 104 hourly clinical aggregates over the first 24 hours, giving several hundred features, for in-hospital mortality and ventilation/vasopressor onset. The second clinical dataset is the publicly released hospital systems of the PhysioNet/CinC 2019 sepsis challenge. We train on Hospital A and test on Hospital B, since Hospital C is hidden. For sanity checks against published scalable-GP settings, we use the UCI regression sets from GPnn, especially the higher-dimensional Ctslice, Song, and Protein.
Baselines
The naive reference point is GPnn with Euclidean neighbors on standardized features, run with its published defaults and our variance calibration. Any learned metric must beat this. We will match $K$ and retrieval code exactly.
The most dangerous competitor is GPnn with per-feature lengthscales estimated on the same anchor subset, with neighbors then retrieved in the rescaled space. This is a diagonal learned metric that is cheap, standard, and arguably interpretable already. To beat it, our sparse metric must improve held-out negative log likelihood and, for classification, AUPRC, beyond seed-to-seed variation across five patient-level splits.
The strongest unconstrained competitor uses our own objective with a dense factorized metric $M = L^\top L$ of the same rank $r$, trained by Adam with an equal wall-clock budget. This isolates whether sparsity and greedy ordering cost accuracy. We count the comparison as a success if our method stays within a small margin of it, around one standard error, while using a fraction of the nonzero variables.
A second ablation keeps our sparse rank-one learner but replaces the GP objective with the large-margin triplet loss of the column-generation LMNN paper. It tests whether optimizing the metric for the downstream GP is the key ingredient.
From the GP side, we include VNNGP with Euclidean neighbors and the inducing-point model of VDMGP with matched rank. The file gives no numeric VDMGP results (no reported result found on Lacuna for VDMGP NMSE values), nor numeric GPnn MSE tables, so we will rerun both ourselves.
From the clinical side, we include gradient-boosted trees and logistic regression with equal tuning budgets. The reference numbers in the file are mortality AUROC between 0.85 and 0.90 across logistic regression, random forests, GRU-D, CNN and LSTM, and AUPRC "often below 0.50" (MIMIC-Extract). For a different cohort, a hybrid LSTM reaches 0.87 ICU mortality AUROC on MIMIC-IV CKD patients (MIMIC-IV pipeline). Our goal on MIMIC-Extract mortality is to land inside the 0.85–0.90 band while being fully case-based. Sepsis challenge utility scores of 0.33–0.36 were measured on the hidden hospital and are not directly comparable to our A-to-B split. We will instead rerun the boosted-tree baseline on that split.
Why not just…?
Why not just use per-feature lengthscales, which GPnn already estimates? This is the alternative most likely to win, and it is our main comparison. Its weakness in principle is that clinical signals are correlated. Blood pressure measures, heart rate, and lactate often matter jointly along an oblique direction, and a diagonal metric can only stretch axes. Clinical labs are also strongly redundant, which a diagonal metric double-counts. Whether this matters in practice is exactly what the baseline settles. If the diagonal metric matches us, we will report that the oblique directions add nothing in this setting, and the contribution reduces to the GP-targeted objective and the uncertainty analysis.
Why not just factorize $M = L^\top L$ and run gradient descent on the same objective? That approach also avoids projections, and it may reach equal accuracy. The file notes that factorized variational training in VDMGP was slow and non-convex, but that is weak evidence for a point-estimate version. The real difference is the output. A dense $L$ yields rotated, unordered directions that mix all variables, while the greedy method yields a ranked list of sparse ones and a natural stopping point. The dense-factorization ablation measures the accuracy price of that readability. Adding an L1 penalty to $L$ is a fair middle ground, and we will include it.
Why not just train boosted trees and explain them with SHAP? Trees will likely match or beat us on raw AUROC, and we do not claim otherwise. What they do not provide is a prediction that is literally composed of identifiable past patients, or a posterior variance that grows when a patient is unlike anyone seen. The second property is testable. We will compare our variance against tree ensemble spread and against conformal-style residual scores as signals for which Hospital B predictions are wrong.
Why not just do deterministic case-based matching, as in the treatment-regime work? That design already proved both auditable and competitive. Our addition is uncertainty, so the comparison is a $K$-nearest-neighbor average under our learned metric with no GP weighting or variance. If it matches the GP on accuracy and the variance adds no selective-prediction value, the GP layer is unjustified.
Decisive Checks
Three results would settle the proposal.
The first is the trade-off curve on MIMIC-Extract mortality and intervention onset. We need held-out log likelihood and AUPRC at $r \le 10$ and $s = 5$ to come within one standard error of the dense learned metric and to exceed the diagonal-lengthscale GPnn. If the sparse model falls clearly short at every small budget, the core claim fails.
The second is shift detection on the sepsis Hospital A to Hospital B split. Ranking test patients by predictive variance and discarding the most uncertain 10–30% should raise AUPRC on the retained set more than doing the same with tree-ensemble spread does. We will also check whether the learned directions avoid variables known to shift across hospitals, such as EtCO2 and TroponinI, and whether constraining them away from those variables improves transfer.
The third is faithfulness and scale. Removing the top-weighted retrieved neighbors and re-predicting should change the output in proportion to their weights, which holds by construction and serves to verify the implementation. Wall-clock time to learn the metric should grow roughly linearly in $d$ on Ctslice and Song, compared against a projected-gradient learner that eigen-decomposes a $d \times d$ matrix each step.
References
- Efficiently Learning a Distance Metric for Large Margin Nearest Neighbor Classification
- Efficient distance metric learning by adaptive sampling and mini-batch stochastic gradient descent (SGD)
- Compressive Mahalanobis Metric Learning Adapts to Intrinsic Dimension
- Variational nearest neighbor Gaussian process
- Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression
- Variational Inference for Mahalanobis Distance Metrics in Gaussian Process Regression
- Safe and Interpretable Estimation of Optimal Treatment Regimes
- Is ProtoPNet Really Explainable? Evaluating and Improving the Interpretability of Prototypes
- MIMIC-Extract: a data extraction, preprocessing, and representation pipeline for MIMIC-III
- Early Prediction of Sepsis from Clinical Data: the PhysioNet/Computing in Cardiology Challenge 2019
- An Extensive Data Processing Pipeline for MIMIC-IV