# Nearest Neighbor Classifiers over Incomplete Information: From Certain Answers to Certain Predictions

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 May 2020.

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

- [Data Collection and Quality Challenges in Deep Learning: A Data-Centric AI Perspective](https://mlsanity.com/paper/2112.06409/) (2021)
- [A Data Quality-Driven View of MLOps](https://mlsanity.com/paper/2102.07750/) (2021)
- [Learning from data with structured missingness](https://mlsanity.com/paper/2304.01429/) (2023)
- [Data Debugging with Shapley Importance over End-to-End Machine Learning Pipelines](https://mlsanity.com/paper/2204.11131/) (2022)
- [REIN: A Comprehensive Benchmark Framework for Data Cleaning Methods in ML Pipelines](https://mlsanity.com/paper/2302.04702/) (2023)
- [DiffPrep: Differentiable Data Preprocessing Pipeline Search for Learning over Tabular Data](https://mlsanity.com/paper/2308.10915/) (2023)
- [Data Cleaning and Machine Learning: A Systematic Literature Review](https://mlsanity.com/paper/2310.01765/) (2023)
- [A Unified Framework for Task-Driven Data Quality Management](https://mlsanity.com/paper/2106.05484/) (2021)
- [Data Collection and Labeling Techniques for Machine Learning](https://mlsanity.com/paper/2407.12793/) (2024)
- [Towards Trustworthy Machine Learning in Production: An Overview of the Robustness in MLOps Approach](https://mlsanity.com/paper/2410.21346/) (2024)
- [Certifiable Robustness for Nearest Neighbor Classifiers](https://mlsanity.com/paper/2201.04770/) (2022)
- [In-Database Data Imputation](https://mlsanity.com/paper/2401.03359/) (2024)
- [Naive Bayes Classifiers over Missing Data: Decision and Poisoning](https://mlsanity.com/paper/2303.04811/) (2023)
- [Certain and Approximately Certain Models for Statistical Learning](https://mlsanity.com/paper/2402.17926/) (2024)
- [Still More Shades of Null: An Evaluation Suite for Responsible Missing Value Imputation](https://mlsanity.com/paper/2409.07510/) (2024)
- [AutoCure: Automated Tabular Data Curation Technique for ML Pipelines](https://mlsanity.com/paper/2304.13636/) (2023)
- [Enhancing Sentiment Analysis Results through Outlier Detection Optimization](https://mlsanity.com/paper/2311.16185/) (2023)
- [Learning from Uncertain Data: From Possible Worlds to Possible Models](https://mlsanity.com/paper/2405.18549/) (2024)
- [Learning Over Dirty Data with Minimal Repairs](https://mlsanity.com/paper/2503.13921/) (2025)
- [Learning from Anonymized and Incomplete Tabular Data](https://mlsanity.com/paper/2602.01217/) (2026)

## Abstract (arXiv)

Machine learning (ML) applications have been thriving recently, largely attributed to the increasing availability of data. However, inconsistency and incomplete information are ubiquitous in real-world datasets, and their impact on ML applications remains elusive. In this paper, we present a formal study of this impact by extending the notion of Certain Answers for Codd tables, which has been explored by the database research community for decades, into the field of machine learning. Specifically, we focus on classification problems and propose the notion of "Certain Predictions" (CP) -- a test data example can be certainly predicted (CP'ed) if all possible classifiers trained on top of all possible worlds induced by the incompleteness of data would yield the same prediction. We study two fundamental CP queries: (Q1) checking query that determines whether a data example can be CP'ed; and (Q2) counting query that computes the number of classifiers that support a particular prediction (i.e., label). Given that general solutions to CP queries are, not surprisingly, hard without assumption over the type of classifier, we further present a case study in the context of nearest neighbor (NN) classifiers, where efficient solutions to CP queries can be developed -- we show that it is possible to answer both queries in linear or polynomial time over exponentially many possible worlds. We demonstrate one example use case of CP in the important application of "data cleaning for machine learning (DC for ML)." We show that our proposed CPClean approach built based on CP can often significantly outperform existing techniques in terms of classification accuracy with mild manual cleaning effort.