The forget-set identification problem

Machine Unlearning (MU) is the problem of removing the influence of user’s unwanted evidence from a trained machine-learning model. MU is typically formulated so that the input unwanted evidence corresponds to a subset of the training set utilized to train the model upstream, which is commonly referred to as the “forget set”. However, this requirement is often difficult to satisfy in real-world scenarios, as users may be unaware of the peculiarities of the training set or simply they do not have access to it. In a more realistic setting, users provide their unwanted evidence in a form that is more abstract than or anyway different from a precise subset of training data. In such cases, executing MU methods requires an essential and challenging preliminary step, which, to the best of our knowledge, has never been addressed so far: identifying the forget set based on user’s unwanted evidence. In this paper, we fill this important gap in the MU literature and introduce the Forget-Set Identification (ForSId) problem: given a trained machine-learning model, an “unwanted set” of samples (evidence to unlearn), and a “wanted set” of samples (evidence to retain), identify the forget set as a subset of the training set, such that the similarity in the predictions of the original model and the model retrained on the training data remaining after the removal of the forget set is: (i) low on the unwanted set, indicating that the unwanted samples have been effectively unlearned by the model, and (ii) high on the wanted set, to ensure that the model keeps its original performance on the data to be retained. We define ForSId as an optimization problem, prove its NP-hardness, and devise an algorithm based on a theoretical connection to Red-Blue Set Cover. Our ForSId is a novel complementary problem to MU. It serves as a foundational step to be performed before executing MU methods, allowing for extending the range of applicability of MU to all those settings where user’s unlearning evidence does not correspond to (or is too hard to be directly expressed in terms of) a forget set. We conduct extensive experiments based on the exact unlearning task (which is the most reliable one) on several real-world datasets and settings, involving nontrivial baselines. Results demonstrate high performance of our proposed algorithm and clear superiority over the baselines.