WaKA: Data Attribution using K-Nearest Neighbors and Membership Privacy Principles

Patrick Mesana, Clément Bénesse, Hadrien Lautraite, Gilles Caporossi, Sébastien Gambs · 2024

Read WaKA: Data Attribution using K-Nearest Neighbors and Membership Privacy Principles by Patrick Mesana, Clément Bénesse, Hadrien Lautraite, Gilles Caporossi, Sébastien Gambs (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-01357.txt.

Description

Abstract . In this paper, we introduce WaKA ( Wasserstein K-nearest neighbors Attribution ), a novel attribution method that leverages principles from the LiRA ( Likelihood Ratio Attack ) framework and k k -nearest neighbors classifiers ( k k -NN).

Catalog record

CREATORPatrick Mesana, Clément Bénesse, Hadrien Lautraite, Gilles Caporossi, Sébastien Gambs
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE83 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2411-01357

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

WaKA: Data Attribution using K-Nearest Neighbors and Membership Privacy Principles Patrick Mesana, Clément Bénesse, Hadrien Lautraite, Gilles Caporossi, Sébastien Gambs Abstract . In this paper, we introduce WaKA ( Wasserstein K-nearest neighbors Attribution ), a novel attribution method that leverages principles from the LiRA ( Likelihood Ratio Attack ) framework and k k -nearest neighbors classifiers ( k k -NN). WaKA efficiently measures the contribution of individual data points to the model’s loss distribution, analyzing every possible k k -NN that can be constructed using the training set, without requiring to sample subsets of the training set. WaKA is versatile and can be used a posteriori as a membership inference attack (MIA) to assess privacy risks or a priori for privacy influence measurement and data valuation. Thus, WaKA can be seen as bridging the gap between data attribution and membership inference attack (MIA) by providing a unified framework to distinguish between a data point’s value and its privacy risk. For instance, we have shown that self-attribution values are more strongly correlated with the attack success rate than the contribution of a point to the model generalization. WaKA’s different usages were also evaluated across diverse real-world datasets, demonstrating performance very close to LiRA when used as an MIA on k k -NN classifiers, but with greater computational efficiency. Additionally, WaKA shows greater robustness than Shapley Values for data minimization tasks (removal or addition) on imbalanced datasets. Volume: YYYY X DOI: XXXXXXX.XXXXXXX CCS: Security and privacy Privacy-preserving technologies 1. Introduction Data attribution methods have been developed originally to measure the contribution of individual data points in a training set to a model’s output. These methods can serve different purposes depending on the context. One key application is data valuation, in which the objective is to quantify the “value” of each data point with respect to its impact on the model’s ability to generalize. For example, Data Shapley Value (DSV), introduced in ( Ghorbani and Zou, 2019 ) and ( Jia et al., 2019 ) , is grounded in the game-theoretic Shapley Value framework and is often used for tasks such as data minimization via summarization, in which the objective is to remove a large fraction of data points while ensuring a high generalization performance of the model This approach aligns well with Article 5 of the General Data Protection Regulation (GDPR) ( European Parliament and Council, 2016 ) , which emphasizes that personal data should be “adequate, relevant, and limited to what is necessary” in relation to the purposes for which they are processed. As a motivating scenario, consider for instance an organization that collects a dataset and then trains a machine learning model over it, exposing its functionality via an API to monetize the access to the predictions of the model ( e.g. , for classifying movie reviews or categorizing images). Data attribution can be used by this organization from two perspectives: data valuation and privacy with Figure 1 illustrating both viewpoints. On one hand, data valuation can help estimate the contribution of each data point to the model, guiding decisions on redistributing a share of the model’s value to individuals who provided data points. This valuation, which aligns with Shapley value, also helps the organization determine which data points bring no value or even negative value, potentially avoiding unnecessary costs by not acquiring these data points. Figure 1. Illustration of data attribution in a movie review classification scenario, highlighting the dual perspectives of data valuation (estimating data point value) and data privacy (measuring potential information leakage). On the other hand, from the privacy perspective, the organization might be concerned with how much information about data points could potentially be leaked through the API, which is akin to measuring the privacy risk of data leakage. This is closely related to membership inference attacks (MIAs), in which an attacker aims to determine whether a particular data point was part of the model’s training set. While data valuation and privacy concerns are often related, they are usually addressed through very different methods. To solve this issue, we introduce WaKA (for 1-Wasserstein k -NN Attribution), which provides a unified framework for addressing both aspects using k -nearest neighbors ( k -NN) models. While being simple in their design, k -NN models offer a clear and intuitive way to perform data attribution. In particular, they are recognized as an instance-based explainable method ( Molnar, 2020 ) , meaning its predictions are directly influenced by the training data without an explicit model abstraction. However, a well-known limitation is that they do not perform well on high-dimensional data such as textual documents or images due to the curse of dimensionality. In such cases, the distance between points becomes nearly identical, making the identification of neighbors ineffective ( Friedman, 1997 ) . To overcome this challenge and apply them to datasets like images and textual data, we first employ a neural network to learn embeddings suitable for k -NN classification. These learned embeddings capture meaningful representations of the data, making k -NN effective even in high-dimensional settings. This approach is also commonly used in the data valuation literature in which case it is usually referred to as “surrogate models” ( Jia et al., 2021 ) . Additionally, while the majority of research on data attribution and membership inference attacks has been centered on neural networks, k -NN-based studies are highly relevant in practice. In particular, in industrial applications, such as retrieval-augmented generation (RAG) pipelines, k -NN with embeddings is widely adopted as the use of learned representations mitigates the high-dimensionality challenges typically associated with nearest neighbor search. Moreover, ( Yadav and Chaudhuri, 2021 ) demonstrated that interpretations of k -NN models using embeddings are comparable to a softmax layer in neural networks, reinforcing their relevance to modern machine learning workflows. The term “value” in data valuation is semantically charged, as it suggests an intrinsic worth of data points. In this context, the term is grounded in the Shapley Value axioms, which provide a unique way of attributing the contribution of each data point to the model’s generalization performance. Data valuation methods such as DSV seek to uncover the intrinsic properties of data in relation to the category of model being used, whether it be a type of neural network, a k -NN classifier or another machine learning model. In contrast, membership inference ( Shokri et al., 2017 ; Yeom et al., 2018 ) aims at determining whether a given data point was part of a specific model’s training dataset. For instance, LiRA ( Carlini et al., 2022a ) is a state-of-the-art approach for performing membership inference attacks (MIAs), which is based on the Likelihood Ratio Test (LRT), a statistical test that compares the likelihood of a model’s prediction for a given data point when trained with and without this point. To realize this, LiRA requires the training of shadow models via sampling and provides a membership score for each point in the training set, facilitating a more detailed attribution analysis. Similarly to LiRA, WaKA assumes that the adversary has access to the underlying data distribution, enabling probability mass function (PMF) computation. This assumption is fundamental to our framework but also to LiRA. Related work. More recently, the intersection

Read the complete text