Certifying the Fairness of KNN in the Presence of Dataset Bias
This addresses fairness certification for a widely used algorithm in machine learning, but it is incremental as it adapts existing techniques to KNN.
The paper tackles the problem of certifying fairness for k-nearest neighbors (KNN) classification when training data has historical bias, proposing a method based on abstract interpretation to reduce computational costs and showing effectiveness on six datasets with accurate certifications for many test inputs.
We propose a method for certifying the fairness of the classification result of a widely used supervised learning algorithm, the k-nearest neighbors (KNN), under the assumption that the training data may have historical bias caused by systematic mislabeling of samples from a protected minority group. To the best of our knowledge, this is the first certification method for KNN based on three variants of the fairness definition: individual fairness, $ε$-fairness, and label-flipping fairness. We first define the fairness certification problem for KNN and then propose sound approximations of the complex arithmetic computations used in the state-of-the-art KNN algorithm. This is meant to lift the computation results from the concrete domain to an abstract domain, to reduce the computational cost. We show effectiveness of this abstract interpretation based technique through experimental evaluation on six datasets widely used in the fairness research literature. We also show that the method is accurate enough to obtain fairness certifications for a large number of test inputs, despite the presence of historical bias in the datasets.