Certified approximation improves training landmark rankings in AI models
Certified Approximation for Interpretable Representer Landmarks
Machine Learning
Summary
Explaining how AI models make decisions often involves identifying key data points that influence their internal understanding. The authors developed a new method called CAIRN that more accurately tracks errors in approximations used to find these important data points, ensuring the top choices are reliably identified. Their approach measures uncertainty better than previous techniques and shows faster and more precise results on standard datasets. This makes it easier to trust explanations for AI behavior and guides where to focus computing effort.
What this means in practice
- •For machine learning engineers: Produce more reliable explanations for self-supervised AI models by certifying the accuracy of influential training data points.
- •For data scientists: Optimize computational resources when selecting informative landmarks by accurately estimating error and effective dimension without costly matrix decompositions.
- •For financial model developers: Increase trust in model interpretations by deploying error-certified rankings of training examples that explain model decisions.$Commercial implications: Supports building explainability products that improve transparency and compliance in AI-driven financial systems.
Authors
Jayanta Mukherjee, Shourya Verma, Mengbo Wang, Jasorsi Ghosh, Ananth Grama
Abstract
Representer explanations rank the training landmarks that most influence a self-supervised representation. At scale, this ranking rests on up to four stacked approximations of the empirical neural tangent kernel (eNTK). These are random output heads, a parameter sketch, landmark sampling and a coefficient fit. Existing analyses bound each approximation separately, but none certifies the top-$K$ set against their combined error. We introduce CAIRN (Certified Approximation for Interpretable Representer laNdmarks), a framework that carries this error through to the ranking. We derive the exact variance of the sketched multi-head eNTK, which matches measurement within $4\%$ where Johnson-Lindenstrauss bounds err by up to $2.5\times$. This yields a high-probability top-$K$ certificate for a fixed coefficient fit, alongside exact residual-trace certificates for discarded spectral mass. An exact product-variance identity separates kernel error from fit variability and identifies when a larger kernel budget can still sharpen a ranking. Stochastic Lanczos Quadrature (SLQ) estimates the effective dimension within $0.72\%$ and guides the landmark budget without dense eigendecomposition. We show that residual mass does not control class coverage, and residual-greedy selection cuts the worst coverage excess of $k$-means++ from $8.5\times$ to $1.55\times$ ($4\times$ on the sketched eNTK). Cross-view initializers outperform principal-component initialization in five (AUI) to all six (CSI) settings. Against the KREPES Gauss-Newton solver, CAIRN converges $2.5$ to $11.3\times$ faster, trails by at most $0.31$ points and gains up to $3.14$ points on MNIST. Together, these results make the reliability of representer explanations measurable and show where approximation budgets are best spent.