What is Machine Unlearning? Pt.1
Before privacy became a mainstream consideration, we rarely considered what companies did with our data. Personally, I didn’t care how companies like Facebook or Google were using my data until the famous Facebook-Cambridge Analytica scandal of 2018 [1]. These and other instances of data misuse emphasized the importance of strong privacy regulation, such as the ‘right to be forgotten’ [2] and the ‘General Data Protection Regulation’. Their intent is evident: we, as users and data contributors, have the right to withhold our data.
These regulations were a huge step forward because they gave us the right and power to protect our data. But, they also present huge challenges for machine learning services because models are often eagerly trained on (user) data before their accurate predictions are statically served. In particular, unlearning requests could have a huge impact on the accuracy and training time of machine learning models that need unlearning. In this blog post, I will cover some key points from one of my research papers, written in collaboration with the CleverHans lab. Machine Unlearning will be appearing in the IEEE SSP 21' conference and is available on my website or arXiv [3]. This blog post is broken up into three parts:
- Part 1 — defining machine unlearning (or simply, unlearning),
- Part 2 — comparing the different unlearning methods with our approach: SISA, which guarantees total erasure of unlearned data.
- Part 3 — deep-diving into SISA, including our evaluation methodologies and an implementation tutorial for arbitrary ML models.
Overview of Machine Learning (ML)
This goal of this section is to give a high level, intuitive understanding of the relevant concepts in ML. If you don’t need this overview, feel free to skip to the next section.
For the purposes of this blog post, we focus specifically on supervised learning, where we aim to learn the best possible mapping from each input to its associated label. For example, we may need to identify if a given image is of a chair, desk, or lamp. In this case, the inputs would be the pixels of an image and the output would be a prediction of either ‘chair’, ‘desk’, or ‘lamp’. The mapping may learn that short, four-legged contours correspond to chairs, wider four-legged contours correspond to desks, and long, cylindrical contours correspond to lamps.
The model learns this mapping by ensuring the best possible correspondence across all (input, label) pairs in our dataset. In the example above, we ensure that approximately all images of chairs are correctly classified as chairs, desks as desks, and so on. The input-output mapping that achieves this goal ‘best’ solves our image classification task for the set {desk, chair, lamp}. In general, many such mappings could be learned, where some are better and/or more likely than others. For example, we expect mappings that predict four-legged objects as chairs to be more likely (and better) than mappings that predict two-legged objects as chairs. Thus, there is a distribution of possible ML models that each solve the task to varying degrees of success.
A large area of machine learning research focuses on deep learning and neural networks, which is one class of mapping parametrizations. Many recent machine learning advancements train deep neural networks on large amounts of data to learn reliable and effective mappings for many different tasks (e.g. detecting hate speech, transcribing audio or video, etc.), in a computationally expensive process. Later, these trained models are used to efficiently predict the labels for new inputs (e.g., images). Models that are expensively trained before being served later are known as ‘eager learners’, unlike ‘lazy learners’, which perform the bulk of the computation at prediction time. Simply put, eager learners precompute a mapping using the dataset, whereas lazy learners compute this mapping on-the-fly uniquely for each prediction,. Eager learners more efficient when accepting many queries, but also more challenging for unlearning.
What is Machine Unlearning?
Machine unlearning is the problem of forgetting a data point’s contributions to a machine learning model’s input-output map. Users should reasonably expect that when they request their data to be removed, any contributions from their data in downstream models should be removed too. In this way, the user’s privacy is protected from adversaries who may attempt to breach it by inferring sensitive user-specific information that was used to train the model. But, what does it mean to remove a data points contributions’?
The ideal case is that the model was never trained on this data, which can be naively accomplished by retraining the model from scratch without the unlearned data — a computationally expensive process. Before diving deeper, let’s first define a few key terms: D is a dataset of user-contributed data where dᵤ is the data point to be unlearned. Mᵒʳⁱᵍⁱᶰᵃˡ is a model eagerly trained on all our data (D + dᵤ) — it is our machine learning service or product prior to receiving an unlearning request. We focus on eagerly trained models because training them makes the unlearning process nontrivial, unlike lazy models where we can just remove dᵤ from the dataset. Our goal is to develop an unlearning algorithm that can output a new model, Mᵘᶰˡᵉᵃʳᶰᵉᵈ, in a manner that is computationally cheaper than retraining from scratch (Mᶰᵃⁱᵛᵉ), while still preserving the privacy of dᵤ.
So we have two possible solutions to our problem. Naively, we can discard Mᵒʳⁱᵍⁱᶰᵃˡ, delete the data dᵤ, and retrain a new model on just D, giving us Mᶰᵃⁱᵛᵉ; or, we can try to efficiently convert the model trained on dᵤ, Mᵒʳⁱᵍⁱᶰᵃˡ, into our unlearned model Mᵘᶰˡᵉᵃʳᶰᵉᵈ.
To ensure the privacy of dᵤ, we require that Mᵘᶰˡᵉᵃʳᶰᵉᵈ=Mᶰᵃⁱᵛᵉ, or more accurately, that the distribution of possible models from our unlearning algorithm exactly matches that of models trained on D. If not, the model retains some contribution from dᵤ after the unlearning process, which could enable an adversary to infer sensitive user information. Much of this new area of research is focused on probabilistic unlearning and showing that Mᵘᶰˡᵉᵃʳᶰᵉᵈ≃Mᶰᵃⁱᵛᵉ, which does not entirely protect the privacy of user data.
These formulations cannot entirely unlearn dᵤ without destroying all our model’s inference utility, meaning we will always have Mᵘᶰˡᵉᵃʳᶰᵉᵈ≠Mᶰᵃⁱᵛᵉ using probabilistic unlearning. Hence, there will always be some non-zero contribution from dᵤ that an adversary can infer. However, this relaxed definition of unlearning is powerful for enabling tradeoffs between the privacy of user data and the efficiency of creating Mᵘᶰˡᵉᵃʳᶰᵉᵈ.
Thus, we focus on guaranteeing that Mᵘᶰˡᵉᵃʳᶰᵉᵈ=Mᶰᵃⁱᵛᵉ, which is our strict and deterministic definition of unlearning. This definition ensures that user’s privacy is (100%) protected because any resulting model, after unlearning dᵤ, is exactly equivalent to retraining without it. Compared with the naive approach, we achieve unlearning in a computationally efficient manner.
In part 2, we will compare probabilistic methods with our approach, SISA: elaborating on why achieving Mᵘᶰˡᵉᵃʳᶰᵉᵈ=Mᶰᵃⁱᵛᵉ is so difficult in a probabilistic setting and go over how our approach achieves this guarantee.
References
[1]A. Forrest, “Facebook fined $5bn for ‘inappropriate’ sharing of personal data”, The Independent, 2019. [Online]. Available: https://www.independent.co.uk/news/world/americas/facebook-data-privacy-scandal-settlement-cambridge-analytica-court-a9003106.html.
[2]”Announcement: Privacy Commissioner seeks Federal Court determination on key issue for Canadians’ online reputation — Office of the Privacy Commissioner of Canada”, Priv.gc.ca, 2020. [Online]. Available: https://www.priv.gc.ca/en/opc-news/news-and-announcements/2018/an_181010/.
[3] Bourtoule, L., Chandrasekaran, V., Choquette-Choo, C., Jia, H., Travers, A., Zhang, B., Lie, D., and Papernot, N. Machine unlearning. arXiv preprint arXiv:1912.03817, 2019.
