Tue, Apr 25, 2023 @ 10:00 AM - 12:00 PM
Thomas Lord Department of Computer Science
PhD Thesis Defense - Yannan Li
Title: Formal Analysis of the Data Poisoning Robustness of K-Nearest Neighbors
Committee members(Lexicographic order): Pierluigi Nuzzo, Mukund Raghothaman, Chao Wang (chair)
Abstract: Data poisoning, which aims to corrupt a machine learning model and change its inference results by changing data elements in its training set, poses a significant threat to machine learning based software systems. However, formally certifying data poisoning robustness is a challenging task. I designed and implemented a set of formal methods for deciding, both efficiently and accurately, the data-poisoning robustness of the k-nearest neighbors (KNN) algorithm, which is a widely-used supervised machine learning technique. First, I developed a method for certifying the data-poisoning robustness of KNN by soundly overapproximating both the learning and inference phases of the KNN algorithm. Second, I developed a method for falsifying data-poisoning robustness, by quickly detecting the truly-non-robust cases using search space pruning and sampling. Finally, I extended these methods to other attack models and fairness certification, thus allowing for a more comprehensive analysis of the robustness of KNN.
Audiences: Everyone Is Invited
Contact: Melissa Ochoa