Naive Bayes Classifiers over Missing Data: Decision and Poisoning
This addresses robustness verification and security for machine learning models in real-world scenarios with incomplete data, representing an incremental advance in certifiable robustness methods.
The paper tackles the problem of certifiable robustness for Naive Bayes classifiers on datasets with missing values, showing that efficient algorithms exist to decide robustness for multiple test points and that data poisoning attacks are polynomial-time for single points but NP-complete for multiple points.
We study the certifiable robustness of ML classifiers on dirty datasets that could contain missing values. A test point is certifiably robust for an ML classifier if the classifier returns the same prediction for that test point, regardless of which cleaned version (among exponentially many) of the dirty dataset the classifier is trained on. In this paper, we show theoretically that for Naive Bayes Classifiers (NBC) over dirty datasets with missing values: (i) there exists an efficient polynomial time algorithm to decide whether multiple input test points are all certifiably robust over a dirty dataset; and (ii) the data poisoning attack, which aims to make all input test points certifiably non-robust by inserting missing cells to the clean dataset, is in polynomial time for single test points but NP-complete for multiple test points. Extensive experiments demonstrate that our algorithms are efficient and outperform existing baselines.