# A Confidence Machine for Sparse High-Order Interaction Model

arXiv: https://arxiv.org/abs/2205.14317 · HTML: https://mlsanity.com/paper/2205.14317/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 56 references that are in the map.
- First posted on arXiv 28 May 2022.

## Builds on (most cited first, 24 of 24)

- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [Uncertainty Sets for Image Classifiers using Conformal Prediction](https://mlsanity.com/paper/2009.14193/) (2020)
- [Conformal prediction beyond exchangeability](https://mlsanity.com/paper/2202.13415/) (2022)
- [Least Ambiguous Set-Valued Classifiers with Bounded Error Levels](https://mlsanity.com/paper/1609.00451/) (2016)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Predictive inference with the jackknife+](https://mlsanity.com/paper/1905.02928/) (2019)
- [Conformal Inference of Counterfactuals and Individual Treatment Effects](https://mlsanity.com/paper/2006.06138/) (2020)
- [Testing for Outliers with Conformal p-values](https://mlsanity.com/paper/2104.08279/) (2021)
- [Exact post-selection inference, with application to the lasso](https://mlsanity.com/paper/1311.6238/) (2013)
- [Nested conformal prediction and quantile out-of-bag ensemble methods](https://mlsanity.com/paper/1910.10562/) (2019)
- [Optimal Inference After Model Selection](https://mlsanity.com/paper/1410.2597/) (2014)
- [Few-shot Conformal Prediction with Auxiliary Tasks](https://mlsanity.com/paper/2102.08898/) (2021)
- [Distribution-Free Prediction Sets for Two-Layer Hierarchical Models](https://mlsanity.com/paper/1809.07441/) (2018)
- [Computing Valid p-value for Optimal Changepoint by Selective Inference using Dynamic Programming](https://mlsanity.com/paper/2002.09132/) (2020)
- [Conformal prediction for text infilling and part-of-speech prediction](https://mlsanity.com/paper/2111.02592/) (2021)
- [Multi Split Conformal Prediction](https://mlsanity.com/paper/2103.00627/) (2021)
- [Fast Exact Conformalization of Lasso using Piecewise Linear Homotopy](https://mlsanity.com/paper/1708.00427/) (2017)
- [Computing Full Conformal Prediction Set with Approximate Homotopy](https://mlsanity.com/paper/1909.09365/) (2019)
- [Fast and More Powerful Selective Inference for Sparse High-order Interaction Model](https://mlsanity.com/paper/2106.04929/) (2021)
- [Safe Pattern Pruning: An Efficient Approach for Predictive Pattern Mining](https://mlsanity.com/paper/1602.04548/) (2016)
- [Approximating Full Conformal Prediction at Scale via Influence Functions](https://mlsanity.com/paper/2202.01315/) (2022)
- [Exact Optimization of Conformal Predictors via Incremental and Decremental Learning](https://mlsanity.com/paper/2102.03236/) (2021)
- [Root-finding Approaches for Computing Conformal Prediction Set](https://mlsanity.com/paper/2104.06648/) (2021)
- [The Well Tempered Lasso](https://mlsanity.com/paper/1806.03190/) (2018)

## Built on by (most cited first, 1 of 1)

- [Feature Importance Measurement based on Decision Tree Sampling](https://mlsanity.com/paper/2307.13333/) (2023)

## Abstract (arXiv)

In predictive modeling for high-stake decision-making, predictors must be not only accurate but also reliable. Conformal prediction (CP) is a promising approach for obtaining the confidence of prediction results with fewer theoretical assumptions. To obtain the confidence set by so-called full-CP, we need to refit the predictor for all possible values of prediction results, which is only possible for simple predictors. For complex predictors such as random forests (RFs) or neural networks (NNs), split-CP is often employed where the data is split into two parts: one part for fitting and another to compute the confidence set. Unfortunately, because of the reduced sample size, split-CP is inferior to full-CP both in fitting as well as confidence set computation. In this paper, we develop a full-CP of sparse high-order interaction model (SHIM), which is sufficiently flexible as it can take into account high-order interactions among variables. We resolve the computational challenge for full-CP of SHIM by introducing a novel approach called homotopy mining. Through numerical experiments, we demonstrate that SHIM is as accurate as complex predictors such as RF and NN and enjoys the superior statistical power of full-CP.