Private Counterfactual Retrieval With Immutable Features
This addresses the need for secure and practical counterfactual explanations in classification tasks, particularly for users with immutable features, though it is incremental as it extends prior work on private counterfactual retrieval.
The paper tackles the problem of privately retrieving the closest counterfactual explanation from a database while ensuring certain input features remain unchanged, proposing two schemes based on private information retrieval and analyzing their communication costs and information leakage.
In a classification task, counterfactual explanations provide the minimum change needed for an input to be classified into a favorable class. We consider the problem of privately retrieving the exact closest counterfactual from a database of accepted samples while enforcing that certain features of the input sample cannot be changed, i.e., they are \emph{immutable}. An applicant (user) whose feature vector is rejected by a machine learning model wants to retrieve the sample closest to them in the database without altering a private subset of their features, which constitutes the immutable set. While doing this, the user should keep their feature vector, immutable set and the resulting counterfactual index information-theoretically private from the institution. We refer to this as immutable private counterfactual retrieval (I-PCR) problem which generalizes PCR to a more practical setting. In this paper, we propose two I-PCR schemes by leveraging techniques from private information retrieval (PIR) and characterize their communication costs. Further, we quantify the information that the user learns about the database and compare it for the proposed schemes.