Research map / Learning theory and algorithms / Prediction and decision losses
Naive Bayes Classifiers over Missing Data: Decision and Poisoning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives polynomial-time algorithms for certifiable robustness (decision problem) of Naive Bayes classifiers over incomplete data with missing values, and studies the data poisoning problem (optimal for one test point, NP-complete for multiple).
Problem
Deciding whether test points are certifiably robust for Naive Bayes classifiers over datasets with missing values (i.e., prediction is the same across all cleaned possible worlds), and finding the minimum number of cells to set to NULL to make all test points certifiably non-robust (data poisoning).
Approach
For NBC, the max and min support of a label over all possible worlds are attained at extreme worlds where every missing cell agrees or disagrees with the test point, enabling an O(nd)-time decision check; for poisoning, a greedy two-operation (A1/A2) procedure solves the single-point case optimally, while multi-point poisoning is shown NP-complete.
Key results
- Iterate+Index is almost 20x faster than Iterate for decision checking and about 10x faster for 16 test points.
- For single-point poisoning, the greedy GS algorithm is provably optimal and has the lowest poisoning rate among RP, SR and GS.
- Multi-point data poisoning is NP-complete for datasets with at least three features (d >= 3).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use indexing when certifying multiple test points | Iterate+Index versus Iterate · Decision Problem, 16 test points across different datasets | running time: almost 20× faster | Helped |
| Use indexing when certifying multiple test points | Iterate+Index versus Iterate · Decision Problem, 16 test points across different datasets | running time: 10× | Helped |
| Increase the number of test points from 1 to 16 while using the index | Iterate+Index · Decision Problem, different datasets | running time | No clear effect |
| Increase the number of test points from 1 to 16 without using the index | AD and Iterate · Decision Problem, different datasets | running time | Hurt |
| Vary the missing rate from 20% to 80% while using the indexed decision algorithm | Iterate+Index · Decision Problem, different datasets | running time | No clear effect |
| Replace exact decision checking with sampling 100 possible worlds | Approximate Decision (AD) · Decision Problem, different datasets | correctness guarantee: 100 | Hurt |
| Use the optimal greedy poisoning algorithm instead of RP or SR | Greedy Search Poisoning (GS) · Single-point Data Poisoning Problem, most datasets | running time | Helped |
| Use the optimal greedy poisoning algorithm instead of RP or SR | Greedy Search Poisoning (GS) · Single-point Data Poisoning Problem, all evaluated datasets | poisoning rate | Helped |
| Use the optimal greedy poisoning algorithm instead of SR | Greedy Search Poisoning (GS) · Multiple-point Data Poisoning Problem, most datasets | effectiveness | Helped |
| Apply A1 and A2 in an optimal sequence rather than a random sequence | Greedy Search Poisoning (GS) versus Smarter Random Poisoning (SR) · Multiple-point Data Poisoning Problem, different datasets | poisoning rate | Helped |
Surprising findings
- Certifiable robustness for NBC is cheap to decide, with no asymptotic overhead over training and classification.
Limitations
- Results only hold for Naive Bayes classifiers, not more complex models.
- Multi-point poisoning is NP-complete, so only a heuristic is provided.
- Features must be discretized into finite domains; experiments use only categorical data.
Experimental setup
Datasets: heart fitness-club fetal-health employee winequalityN Company-Bankruptcy Mushroom bodyPerformance star-classification creditcard
Benchmarks: heart fitness-club fetal-health employee winequalityN Company-Bankruptcy Mushroom bodyPerformance star-classification creditcard
Metrics: running time poisoning rate number of poisoned cells
Baselines: Approximate Decision (AD) Iterate Random Poisoning (RP) Smarter Random Poisoning (SR)
Builds on: CPClean Naive Bayes Classifier
Closest papers by meaning
- On Robustness of Linear Classifiers to Targeted Data Poisoning (AAAI 2026 · similarity 0.86)
- Optimal Binary Classification Beyond Accuracy (NeurIPS 2022 · similarity 0.85)
- Learning Fair Naive Bayes Classifiers by Discovering and Eliminating Discrimination Patterns (AAAI 2020 · similarity 0.84)
- Improved Certified Defenses against Data Poisoning with (Deterministic) Finite Aggregation (ICML 2022 · similarity 0.84)
- Corruptions of Supervised Learning Problems: Typology and Mitigations (NeurIPS 2026 · similarity 0.83)
- Robust Conformal Outlier Detection under Contaminated Reference Data (ICML 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.