# PUMA: Performance Unchanged Model Augmentation for Training Data Removal

Ga Wu, Masoud Hashemi, Christopher Srinivasa

###### Abstract

Preserving the performance of a trained model while removing unique
characteristics of marked training data points is challenging. Recent research
usually suggests retraining a model from scratch with remaining training data
or refining the model by reverting the model optimization on the marked data
points. Unfortunately, aside from their computational inefficiency, those
approaches inevitably hurt the resulting model’s generalization ability since
they remove not only unique characteristics but also discard shared (and
possibly contributive) information. To address the performance degradation
problem, this paper presents a novel approach called Performance Unchanged
Model Augmentation (PUMA). The proposed PUMA framework explicitly models the
influence of each training data point on the model’s generalization ability
with respect to various performance criteria. It then complements the negative
impact of removing marked data by reweighting the remaining data optimally. To
demonstrate the effectiveness of the PUMA framework, we compared it with
multiple state-of-the-art data removal techniques in the experiments, where we
show the PUMA can effectively and efficiently remove the unique
characteristics of marked training data without retraining the model that can
1) fool a membership attack, and 2) resist performance degradation. In
addition, as PUMA estimates the data importance during its operation, we show
it could serve to debug mislabelled data points more efficiently than existing
approaches.

## Introduction

As many countries and territories become increasingly concerned with personal
data protection, the corresponding protection regulations111CCPA in
California, GDPR in Europe, PIPEDA in Canada, LGPD in Brazil, and NDBS in
Australia. entitle individuals to revoke their authorization of using their
data for data analysis and machine learning (ML) model training. While
retraining ML models by removing marked data points is a feasible solution,
frequent data removal requests inevitably put enormous computational pressure
on the infrastructures responsible for real-time ML services. Furthermore,
cumulative data loss results in quick performance degradation. Hence,
effectively eliminating data’s unique characteristics while preserving model
performance is a critical and challenging research question.

In the literature, a few initial works attempted to address the data removal
challenge. For example, (Ginart et al. 2019) devised a general notion of
removal efficiency and proposed two model-specific data removal algorithms
(for k-means clustering models). Similarly, (Guo et al. 2020) introduced a
notion of Certified Removal and verified the effectiveness of their data
removal approach on linear classifiers. However, those methods usually focus
on specific ML algorithms and are hard to generalize to deep neural networks
that dominate the latest ML research and applications. (Bourtoule et al.
2019), alternatively, proposed a data removal-friendly model by ensembling
multiple ML models trained on disjoint data partitions. As such, the data
removal operation would only involve a sub-model. (Graves, Nagisetty, and
Ganesh 2020) proposed a more generalized single-model solution by explicitly
estimating the contribution (gradients) of each training data point as an
additive function. Unfortunately, such approaches require high costs;
maintaining many sub-models and tracking the model training process are barely
feasible for real-world applications. In addition, existing data removal works
merely pay attention to the performance degradation problem when removing
marked data points. While (Ginart et al. 2019)’s criterion includes a
constraint such as performance of the resulting model should not be worse than
that of a model trained from scratch with remaining data, it does not intend
to preserve the performance of the original model.

In this paper, we propose a novel approach, Performance Unchanged Model
Augmentation (PUMA), to efficiently erase the unique characteristics of marked
data points from a trained model without causing performance degradation. In
particular, the proposed PUMA framework explicitly models the influence of
each training data point on the model with respect to various performance
criteria (that are not necessarily the model training objectives). It then
complements the negative impact of removing marked data by reweighting the
remaining data points sparsely and optimally through a constrained
optimization. Consequently, PUMA can preserve model performance by linearly
patching the original model via reweighting operation while eliminating unique
characteristics of marked data points. In the experiments, we compare PUMA
with existing data removal approaches and show that PUMA has two desired
properties: 1) It can successfully fool a membership attack (Shokri et al.
2017), 2) It can resist performance degradation.

## Preliminary and Related Works

Before proceeding, we review existing related data removal approaches which
inspired this work. We also briefly describe the influence function to
facilitate our description in the main content. Finally, we list several
information leaking attack approaches that can be used to test the
effectiveness of data removal in the existing literature.

### Data Removal Approaches

Removing training data from models has a long research history that can be
tracked back to the era of support vector machines. (Cauwenberghs and Poggio
2000) proposed a decremented unlearning approach, called Leave-One-Out (LOO),
to gradually remove marked training data points from trained SVM model. By
examining the margin of the data points, LOO could significantly reduce the
computational effort of data removal. Later, (Karasuyama and Takeuchi 2009)
extended the decremental unlearning approach to support simultaneous addition
and/or removal of multiple data points through multi-parametric programming.
Following the same line of research, (Tsai, Lin, and Lin 2014) proposed a
warm-up based unlearning approach that is effective on multiple linear machine
learning models. Lastly, (Ginart et al. 2019) payed attention to unsupervised
learning tasks where it presented two model-specific data removal algorithms
for k-means clustering models.

Recent research (Graves, Nagisetty, and Ganesh 2020) stated that the
previously mentioned approaches are not suitable to work on deep network
models where the contribution of individual training data points are
intractable to compute exactly and analytically. To mitigate the computational
cost of retraining a new model from scratch, (Bourtoule et al. 2019) suggested
training multiple models on disjoint data partitions so that retraining is
limited to small groups of sub-models. Alternatively, (Graves, Nagisetty, and
Ganesh 2020) presented Amnesiac training which tracks contribution of each
training batch (a set of data points) during the model training. When a batch
is marked as to be removed, the operation is simply a subtraction between
model parameters and data contribution.

While the existing approaches show remarkable achievement on improving
efficiency of removing data points from a trained model, we note that they
underestimated two critical criteria of data removal tasks: 1) The data
removal approach should maintain model stability and protect against
performance degradation. 2) The data removal approach should minimize the
overall computational cost instead of only looking at the cost of the data
removal operation. More specifically, training multiple models or tracking
gradients of every training epoch is undesired in practice. All of the above
observations motivated our work on proposing Performance Unchanged Model
Augmentation (PUMA) in this paper.

### Influence Function for Prediction Explanation

An influence function is a limit equation which estimates the prediction
changes of a model when its inputs are perturbed. In statistics, the influence
function is similar to the Gâteaux derivative, but it can exist even when the
Gâteaux derivative does not exist for a particular model.

Recently, the influence function was used to explain the prediction of complex
machine learning models as it can reveal the impact of training data point
$(\mathbf{x}_{k},y_{k})$ on the test example $(\mathbf{x}_{j},y_{j})$’s
predictions (Koh and Liang 2017) such that

$\displaystyle\mathcal{I}_{\textit{up},\textit{loss}}\left((\mathbf{x}_{k},y_{k}),(\mathbf{x}_{j},y_{j})\right)\stackrel{{\scriptstyle\text{def}}}{{=}}\frac{d\mathcal{L}(\mathbf{x}_{j},y_{j},\theta)}{d\epsilon}\Bigr{|}_{\epsilon=0}$
(1)
$\displaystyle=\\!-\nabla_{\theta}\mathcal{L}(\mathbf{x}_{j},\\!y_{j},\\!\theta)\\!\left(\frac{1}{m}\\!\sum_{i=1}^{m}\\!\nabla_{\theta}^{2}\mathcal{L}(\mathbf{x}_{i},\\!y_{i},\\!\theta)\right)^{\\!-1}\\!\\!\\!\\!\\!\nabla_{\theta}\mathcal{L}(\mathbf{x}_{k},\\!y_{k},\\!\theta),$

where $\mathcal{L}$ denotes the loss function for the individual data point,
and $\epsilon$ denotes the degree of perturbation on the data $k$. By
computing Equation 1 for all training data points $k$, we can summarize a
training data importance rank for a particular test sample $j$.

Naturally, if we can explain the model prediction based on its training data
points, we can also refine the model prediction by perturbing those data
points. Based on this idea, (Guo et al. 2020) proposed a data removal approach
that leverages the Newton method and influence function. However, their
solution is defined for a linear model, making it hard to verify its
performance on complex models.

In this work, we will also leverage the influence function. The critical
difference between our work and (Guo et al. 2020) is two-folds: First, our
objective is to let the modified model preserve the original model’s
performance after data removal rather than passively monitoring whether the
modified model can produce near identical predictions against a model trained
on the remaining data from scratch. When a huge number of data points are
requested to remove, the difference between these two objectives is
significant; training new model from scratch with insufficient data points may
not reach a desirable performance. Second, the proposed approach modifies all
trainable parameters of the model while (Guo et al. 2020) only adjusts the
linear decision making layer which does not eliminate unique characteristics
of the removed data points (since the representations are learned with the
knowledge of the removed data points).

### Data Privacy Protection and Membership Attacks

In terms of evaluating the effectiveness of data removal approaches, previous
research (Graves, Nagisetty, and Ganesh 2020) suggested leveraging information
leaking attacks (Homer et al. 2008; Dwork et al. 2015; Fredrikson, Jha, and
Ristenpart 2015a; Yeom et al. 2018) to check if the data characteristics are
indeed removed from a trained model. Specifically, it is suggested that the
membership attack (Homer et al. 2008) could reveal whether a particular data
point is present in training a model, which is an ideal reference to see the
difference of attacks before and after the data removal operation. In the
literature, there are various membership attack algorithms (Shokri et al.
2017; Nasr, Shokri, and Houmansadr 2018; Yeom et al. 2018) since the concept
was introduced by (Homer et al. 2008).

In this paper, we will follow the track of previous works and conduct
membership attack experiments to show the effectiveness of our model in the
experiments.

## Performance Unchanged Model Augmentation

Given a machine learning model $f_{\theta_{\textit{org}}}$ learned on training
data set $D_{\textit{tn}}$, we aim to remove the unique characteristics of
marked data points $D_{\textit{mk}}\subset D_{\textit{tn}}$ from the model by
updating model parameters
$\theta_{\textit{org}}\rightarrow\theta_{\textit{mod}}$ without seriously
hurting its prediction performance with respect to various performance
criteria $\mathcal{C}$ (or $\mathcal{L}_{\textit{c}}$ for an individual
sample) such that

$\Bigr{\lvert}\underbrace{\frac{1}{|D_{\textit{tn}}|}\\!\sum_{i=1}^{|D_{\textit{tn}}|}\\!\mathcal{L}_{\textit{c}}(\mathbf{x}_{i},y_{i},\theta_{\textit{mod}})}_{\mathcal{C}(\theta_{\textit{mod}})}\\!-\\!\underbrace{\frac{1}{|D_{\textit{tn}}|}\\!\sum_{i=1}^{|D_{\textit{tn}}|}\\!\mathcal{L}_{\textit{c}}(\mathbf{x}_{i},y_{i},\theta_{\textit{org}})}_{\mathcal{C}(\theta_{\textit{org}})}\Bigr{\rvert}\\!\leq\\!\delta,$
(2)

where $\delta$ is a small change in performance. In particular, we are
interested in preserving overall performance rather than being concerned with
a shift in an individual prediction.

### Influence of Training Data

To tackle the data removal task defined above, we first need to reveal the
underlining causal relation between training data perturbation and model
performance variation. Specifically, in this section, we clarify two aspects
of this connection: 1) How the training data changes would impact model
parameters, and 2) How the parameter changes would impact the model
performance with respect to specific criteria $\mathcal{C}$.

#### Parameter as Linear Function of Data Contributions

We start by analyzing how perturbing the training dataset would impact the
model parameter changes via the influence function.

Let us assume the model parameter $\theta_{\textit{org}}$ is the optimal
solution of the (original) training objective $\mathcal{J}_{\textit{org}}$

$\displaystyle\theta_{\textit{org}}=\underset{\theta}{\operatorname{\arg\\!\min}}~{}\mathcal{J}_{\textit{org}}(\theta)=\underset{\theta}{\operatorname{\arg\\!\min}}\frac{1}{|D_{\textit{tn}}|}\\!\sum_{i=1}^{|D_{\textit{tn}}|}\\!\mathcal{L}_{\textit{t}}(\mathbf{x}_{i},y_{i},\theta)$
(3)

and $\theta_{\textit{mod}}$ is the optimal solution of a modified objective
$\mathcal{J}_{\textit{mod}}$

$\displaystyle\theta_{\textit{mod}}=\underset{\theta}{\operatorname{\arg\\!\min}}~{}\mathcal{J}_{\textit{mod}}(\theta)=$
(4)
$\displaystyle\\!\underset{\theta}{\operatorname{\arg\\!\min}}\underbrace{\frac{1}{|D_{\textit{tn}}|}\\!\sum_{i=1}^{|D_{\textit{tn}}|}\\!\mathcal{L}_{\textit{t}}(\mathbf{x}_{i},y_{i},\theta)}_{\mathcal{J}_{\textit{org}}(\theta)}\\!+\\!\underbrace{\frac{1}{|D_{\textit{up}}|}\\!\sum_{j=1}^{|D_{\textit{up}}|}\\!\lambda_{j}\mathcal{L}_{\textit{t}}(\mathbf{x}_{j},y_{j},\theta)}_{\mathcal{J}_{\textit{add}}(\theta)}$

that optimizes an additional weighted objective $\mathcal{J}_{\textit{add}}$
on a subset of training data points $D_{\textit{up}}\subseteq
D_{\textit{tn}}$, where $\mathcal{L}_{\textit{t}}$ denotes individual
prediction loss222Training loss $\mathcal{L}_{\textit{t}}$ is not necessarily
identical to the performance criterion loss $\mathcal{L}_{\textit{c}}$ defined
in Equation 2. and $\bm{\lambda}\in{\rm I\\!R}^{|D_{\textit{up}}|}$ denotes
the weight vector of upweighted data points.

When the values of weights $\bm{\lambda}$ are negligibly small, the derivative
of the modified objective $\mathcal{J}_{\textit{mod}}$ with respect to its
optimal parameters $\theta_{\textit{mod}}$ could be Taylor expanded at the
local anchor $\theta_{\textit{org}}$ such that

$\displaystyle\underbrace{\nabla\mathcal{J}_{mod}(\theta_{\textit{mod}})}_{\approx
0}\\!\approx\\!\nabla\mathcal{J}_{mod}(\theta_{\textit{org}})+\nabla^{2}\mathcal{J}_{mod}(\theta_{\textit{org}})(\theta_{\textit{mod}}\\!-\\!\theta_{\textit{org}})$
(5)
$\displaystyle\approx\\!\underbrace{\nabla\mathcal{J}_{\textit{org}}(\theta_{\textit{org}})}_{\approx
0}+\nabla\mathcal{J}_{add}(\theta_{\textit{org}})+\nabla^{2}\mathcal{J}_{mod}(\theta_{\textit{org}})(\theta_{\textit{mod}}\\!-\\!\theta_{\textit{org}}).$

Since the both $\theta_{\textit{mod}}$ and $\theta_{\textit{org}}$ are optimal
solutions with respect to their corresponding objective functions
$\nabla\mathcal{J}_{mod}(\theta)$ and $\nabla\mathcal{J}_{org}(\theta)$ (whose
derivatives are $0$s), the Equation 5 yields a difference between the two
optimal solution $\theta_{\textit{mod}}$ and $\theta_{\textit{org}}$ such that

$\theta_{\textit{mod}}-\theta_{\textit{org}}\mathrel{\overset{\makebox[0.0pt]{\mbox{def}}}{=}}-\left(\nabla^{2}\mathcal{J}_{\textit{org}}(\theta_{\textit{org}})\right)^{-1}\nabla\mathcal{J}_{\textit{add}}(\theta_{\textit{org}}),$
(6)

where we relaxed the Hessian matrix
$\nabla^{2}\mathcal{J}_{mod}(\theta_{\textit{org}})$ to
$\nabla^{2}\mathcal{J}_{org}(\theta_{\textit{org}})$. There are multiple
justifications for such relaxation. First, since the $\bm{\lambda}$s are set
to be small values, such a setting makes the difference of these second order
derivatives insignificant. Second, in practice, computing the Hessian matrix
(or Hessian Vector Product described later) is usually an iterative and
stochastic process which introduces larger noise than the relaxation we
introduced here. It is worth to mention that the expression in Equation 6
aligns with previous influence function work (Koh and Liang 2017) when
$\bm{\lambda}$ is restricted as a one-hot vector (that only upweights a single
data point). In our implementation, we compute HVP approximation in the same
way as described in (Koh and Liang 2017).

By expanding the derivative of the additive perturbation term
$\nabla\mathcal{J}_{add}(\theta_{\textit{org}})$, we can convert the Equation
6 to a linear function of the perturbation weight $\bm{\lambda}$ as follows:

$\theta_{\textit{mod}}\\!-\\!\theta_{\textit{org}}=-\\!\sum_{j=1}^{|D_{\textit{up}}|}\\!\lambda_{j}\\!\left(\nabla^{2}\mathcal{J}_{\textit{org}}(\theta_{\textit{org}})\right)^{\\!-\\!1}\nabla\mathcal{L}_{\textit{t}}(\mathbf{x}_{j},\\!y_{j},\\!\theta_{\textit{org}}).$
(7)

Indeed, with trained model whose parameter $\theta_{\textit{org}}$ is fixed,
both the Hessian matrix
$\nabla^{2}\mathcal{J}_{\textit{org}}(\theta_{\textit{org}})$ and gradient
vector $\nabla\mathcal{L}(\mathbf{x}_{j},y_{j},\theta_{\textit{org}})$ are
constant for the fixed set of upweighted data points $D_{\textit{up}}$.

(a) Before Removal

(b) Naive Influence Removal

(c) PUMA

Figure 1: Projection Direction Comparison between Naive Influence Removal and
PUMA. (a) The projection direction of each data point (green arrow as shown
Equation 12). Blue arrow shows the one marked to remove. (b) The overall
projection direction (red arrow) is toward high loss area after naive data
contribution removal. (c) The overall projection direction (red arrow) is
toward low loss area after PUMA data removal. Orange contour plot shows the
loss surface of training objective $\mathcal{J}$. Purple contour plot shows
the loss surface of performance criterion $\mathcal{C}$. For both contour
plots, lighter color shows lower loss.

#### Performance Gap as Taylor Approximation of Parameter Changes

When the difference between two sets of parameters is reasonably small, the
performance gap between the two corresponding models could be approximated
through Taylor expansion such that

$\displaystyle\mathcal{C}(\theta_{\textit{mod}})-\mathcal{C}(\theta_{\textit{org}})=\nabla\mathcal{C}(\theta_{\textit{org}})(\theta_{\textit{mod}}-\theta_{\textit{org}})+\epsilon$
(8)
$\displaystyle\approx-\sum_{j=1}^{|D_{\textit{up}}|}\lambda_{j}\nabla\mathcal{C}(\theta_{\textit{org}})\left(\nabla^{2}\mathcal{J}_{\textit{org}}(\theta_{\textit{org}})\right)^{-1}\nabla\mathcal{L}(\mathbf{x}_{j},y_{j},\theta_{\textit{org}}),$

which is a linear function of the additive data perturbation $\bm{\lambda}$,
where $\epsilon$ represents the higher order Taylor expansion that is
exponentially smaller than the first term. Intuitively, term

$\psi(\mathbf{x}_{j},y_{j})=\underbrace{\nabla\mathcal{C}(\theta_{\textit{org}})\left(\nabla^{2}\mathcal{J}_{\textit{org}}(\theta_{\textit{org}})\right)^{-1}}_{\text{Hessian
Vector
Product~{}(HVP)}}\nabla\mathcal{L}(\mathbf{x}_{j},y_{j},\theta_{\textit{org}})$
(9)

is a scalar that serves as the individual contribution score of data
$(\mathbf{x}_{j},y_{j})$ to the performance degradation. By adjusting the
weights $\bm{\lambda}$, one can control the performance gap effortlessly.
Hence, at this point, we established the causal relation between data
perturbation and model performance changes.

### Performance Preserved Data Removal through Gradient Re-weighting

By combining Equation 2 and Equation 8, we note they form an implicit
constraint on the data up-scaling factors $\bm{\lambda}$ such that any changes
on a subset factor $\lambda_{\textbf{j}}$ would encourage the changes of
remaining $\bm{\lambda}_{/\textbf{j}}$ as complement to maintain the
performance gap smaller than $\delta$.

Based the above notion, we describe how we remove the influence of some marked
data points $D_{\textit{mk}}\subseteq D_{\textit{up}}$ from a target model
$f_{\theta_{\textit{org}}}$ without hurting the model performance.

According to the Equation 4, removing the contribution of a marked data point
$(\mathbf{x}_{k},y_{k})$ is equivalent to setting its perturbation factor
$\lambda_{k}$ to $-1$. Correspondingly, to maintain the model performance
while removing data points $D_{\textit{mk}}$, we propose optimizing the
assignment of the perturbation factor $\bm{\lambda}$ for the remaining
training data points (or randomly sampled subset
$D_{\textit{up}\backslash\textit{mk}}$) to complement model criterion
degradation. Concretely, we propose solving the following linear optimization
task

$\underset{\bm{\lambda}}{\operatorname{\arg\\!\min}}\left\lVert\sum_{j\not\in
D_{\textit{mk}}}^{|D_{\textit{up}}|}\lambda_{j}\psi(\mathbf{x}_{j},y_{j})-\sum_{k=1}^{|D_{\textit{mk}}|}\psi(\mathbf{x}_{k},y_{k})\right\rVert^{2}\\!+\\!\Omega(\bm{\lambda}),$
(10)

where $\Omega$ denotes the regularization term which encourages both sparsity
($l_{1}$ norm) and small changes of $\bm{\lambda}$ ($l_{2}$ norm). In terms of
computational efficiency, since the $\psi(\mathbf{x},y)$s are scalar values,
the optimization is simple convex optimization. While estimating individual
contribution $\psi(\mathbf{x}_{j},y_{j})$ looks expensive, the estimation is
no more than a dot product between individual gradient and pre-cached Hessian
Vector Product (HVP) term.

With the optimized contribution factor $\bm{\lambda}^{*}$, we can then update
the model parameters by a simple patching such that

$\theta_{\textit{mod}}=\theta_{\textit{org}}+\eta\left[\sum_{k=1}^{|D_{\textit{mk}}|}\phi(\mathbf{x}_{k},y_{k})-\sum_{j\not\in
D_{\textit{mk}}}^{|D_{\textit{up}}|}\lambda_{j}^{*}\phi(\mathbf{x}_{j},y_{j})\right],$
(11)

where the individual projection of each data point is

$\phi(\mathbf{x},y)=\left(\nabla^{2}\mathcal{J}_{\textit{org}}(\theta_{\textit{org}})\right)^{-1}\nabla\mathcal{L}(\mathbf{x},y,\theta_{\textit{org}})$
(12)

and projection rate $\eta\ll 1$ is a hyper-parameter which keeps patching
effective while holding our previous assumptions such that data upweighting is
reasonably small.

Figure 1 shows a simple example of PUMA data removal. When a data point is
marked for removal (blue arrow), PUMA optimizes Equation 10 and applies the
optimal factor $\bm{\lambda}$ to the projection formula (Equation 12) to
adjust model parameters such that model performance with respect to the
performance criterion (purple contour) is preserved. In contrast, if we
naively remove the local influence of the marked data point, the model would
result in performance degradation. In this particular example, performance
criterion is measured through Expected Calibration Error (ECE) (Guo et al.
2017). The example model is a linear model with two parameters trained on a
binary classification task.

## Experiments and Evaluations

In this section, we conduct various experiments to answer the following
research questions:

  * •

RQ1: Is the proposed approach able to preserve model performance while
removing data points?

  * •

RQ2: Is the removal successful in terms of causing membership attack failure?

  * •

RQ3: How efficient is the proposed approach compared to other state-of-the-art
candidates?

  * •

RQ4: How sensitive is PUMA with respect to its hyper-parameters?

  * •

RQ5: Can the proposed approach conduct mislabeling debugging as it estimates
the influence of training data point?

### Experimental Settings

Candidate Data Removal Algorithms  In data removal experiments, we compare
PUMA against the following state-of-the-art data removal approaches.

  * •

Retrain Model: Retrain model from scratch with remaining data points after
picking out marked data points.

  * •

Retrain Sub-model: Retrain sub-model that is trained on marked data points.
This is also called Sharded, Isolated, Sliced, and Aggregated training (SISA).

  * •

Amnesiac Machine Learning:  Track gradient information of each training batch
during training phase. Subtract the gradients when the batch is marked for
removal.

Mislabelling Debugging Algorithms  In mislabelled data debugging experiments,
we compare PUMA against the following well-known debugging approaches
including Influence Function (Koh and Liang 2017), Representor Point Selection
(Yeh et al. 2018), and Data Sharply Value (Ghorbani and Zou 2019).

Datasets We conducted our experiments on two synthetic datasets, two tabular
datasets from UCI data group (Dua and Graff 2017), and the MNIST dataset
(LeCun and Cortes 2010). Full description of the data used in this paper is
given in Appendix A.

(a) Before Removal

(b) After Removal

Figure 2: Removing the training points marked by crosses from the model. As
demonstrated in the right plot, PUMA successfully removed the information of
all marked points. ‘x’ in the plot shows the data intended to remove. Colors
show the class labels. Table 1: Comparison of Model Performance Preservation
among Candidate Removal Approaches. Value shows accuracy. Higher is better
after data removal. We omit to present statistics in the main paper for
clearness. The full table with statistics is presented in Appendix D for
further reference.

Data Group | Dataset | Ordered | Random
---|---|---|---
Original | Approach | 20% | 40% | 60% | 80% | Original | Approach | 20% | 40% | 60% | 80%
Synthetic | Radial | 95.04 | Retrain Model | 93.64 | 91.60 | 84.15 | 66.24 | 95.89 | Retrain Model | 93.97 | 90.94 | 82.58 | 66.51
80.88 | SISA | 67.35 | 63.57 | 61.93 | 51.91 | 75.62 | SISA | 64.71 | 64.35 | 54.80 | 54.77
95.04 | Amnesiac ML | 56.38 | 54.75 | 53.53 | 50.54 | 95.88 | Amnesiac ML | 49.08 | 48.95 | 48.95 | 48.95
94.97 | PUMA | 68.97 | 69.60 | 67.99 | 70.77 | 95.82 | PUMA | 72.44 | 73.22 | 71.82 | 76.02
Rectangular | 62.00 | Retrain Model | 61.20 | 60.35 | 55.80 | 54.25 | 65.00 | Retrain Model | 64.70 | 64.50 | 62.30 | 58.65
55.60 | SISA | 55.90 | 48.30 | 30.10 | 29.55 | 56.50 | SISA | 56.50 | 56.50 | 56.55 | 56.90
| 62.00 | Amnesiac ML | 46.60 | 43.85 | 43.45 | 39.15 | 65.00 | Amnesiac ML | 35.40 | 35.40 | 35.40 | 35.40
| 61.85 | PUMA | 55.25 | 56.30 | 53.85 | 61.70 | 64.95 | PUMA | 59.90 | 62.05 | 62.55 | 64.80
Tabular (UCI) | German | 71.52 | Retrain Model | 70.56 | 70.12 | 70.11 | 70.00 | 75.16 | Retrain Model | 74.88 | 73.24 | 72.47 | 70.00
70.00 | SISA | 70.00 | 70.00 | 68.96 | 66.16 | 70.00 | SISA | 70.00 | 70.00 | 70.00 | 70.00
71.52 | Amnesiac ML | 68.52 | 64.40 | 66.24 | 64.03 | 75.16 | Amnesiac ML | 36.24 | 36.28 | 35.72 | 35.72
71.47 | PUMA | 69.08 | 70.72 | 70.64 | 70.72 | 75.12 | PUMA | 70.96 | 73.24 | 74.44 | 74.28
Breast Cancer | 96.45 | Retrain Model | 96.62 | 96.11 | 96.00 | 94.85 | 96.00 | Retrain Model | 95.82 | 95.54 | 95.65 | 95.20
91.31 | SISA | 89.20 | 88.91 | 80.68 | 52.62 | 92.28 | SISA | 91.60 | 88.05 | 88.22 | 87.88
| 96.45 | Amnesiac ML | 96.05 | 95.82 | 95.25 | 82.28 | 96.00 | Amnesiac ML | 35.20 | 30.51 | 30.51 | 30.51
| 96.39 | PUMA | 96.17 | 95.88 | 96.22 | 96.62 | 96.00 | PUMA | 95.08 | 94.91 | 95.25 | 95.54
Image | MNIST | 97.58 | Retrain Model | 97.28 | 96.72 | 95.76 | 93.48 | 97.99 | Retrain Model | 97.72 | 97.16 | 96.60 | 93.98
95.89 | SISA | 95.80 | 95.67 | 94.78 | 89.86 | 95.66 | SISA | 93.47 | 90.63 | 78.06 | 59.83
97.44 | Amnesiac ML | 9.44 | 9.84 | 9.56 | 9.36 | 98.06 | Amnesiac ML | 10.39 | 10.39 | 10.39 | 10.39
| 97.60 | PUMA | 96.70 | 96.66 | 97.17 | 97.16 | 97.97 | PUMA | 97.42 | 97.58 | 97.60 | 97.61

Table 2: Comparison of Membership Attack after Data Removal Operation. Value
shows percentage of removed data that is identified as training data. Lower
values in the table show better performance of removal.

Data Group | Dataset | Ordered | Random
---|---|---|---
Retrain Model | SISA | Amnesiac ML | PUMA | Retrain Model | SISA | Amnesiac ML | PUMA
Before | After | Before | After | Before | After | Before | After | Before | After | Before | After | Before | After | Before | After
Synthetic | Radial | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 0.00 | 100.00 | 5.31 | 100.00 | 52.36 | 100.00 | 37.00 | 100.00 | 50.00 | 100.00 | 1.18
Rectangular | 100.00 | 91.65 | 83.18 | 83.18 | 100.00 | 33.33 | 100.00 | 36.66 | 100.00 | 67.07 | 98.50 | 94.00 | 100.00 | 86.20 | 100.00 | 20.00
Tabular | German | 100.00 | 77.12 | 100.00 | 100.00 | 100.00 | 0.00 | 100.00 | 3.42 | 94.44 | 84.44 | 100.00 | 98.81 | 94.44 | 93.33 | 85.18 | 2.22
Breast Cancer | 100.00 | 100.00 | 87.50 | 87.50 | 100.00 | 100.00 | 100.00 | 56.25 | 100.00 | 100.00 | 90.00 | 73.75 | 100.00 | 87.50 | 100.00 | 71.25
Image | MNIST | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 0.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 100.00 | 72.00

### Dessert: Preliminary Data Removal Check

Before starting quantitative evaluation, we first run a preliminary check on a
simple binary classification task to show the effect of PUMA data removal.
Specifically, we first train a classifier on a synthetic dataset that contains
three observation clusters for each class as shown in Figure 2 (a). The
trained classifier is a perfect estimator of data distribution (with $100\%$
prediction accuracy). We then mark all data in one cluster for removal
(denoted by ‘x’ in the plots). Intuitively, if the marked data points are
never used for training the classifier, we can imagine that their predictions
should align with the predictions of data points surrounding them. Indeed, the
model obtained after the PUMA data removal operation reflects our intuition as
shown in Figure 2 (b), where all removed data points are now predicted as
members of the orange class.

### Effectiveness of Preserving Model Performance

In this section, we quantitatively evaluate how the data removal approaches
preserve model performance after data removal. In particular, we gradually
remove training data points with percentages $[20\%,40\%,60\%,80\%]$ and aim
to show the performance degradation after data removal. To simplify the
experimental setting, here we assume the training objective $\mathcal{J}$ and
performance criterion $\mathcal{C}$ are identical (both of them are cross
entropy loss of prediction). Considering that both Amnesiac ML and SISA models
may show better performance when the data marked to be removed belong to same
training batch, we conduct experiments in two scenarios. In the first scenario
(Ordered), we intentionally group all data points marked to be removed into
small set of training batches such that the removal operation would not impact
other training batches (and sub-models for SISA). In the second scenario
(Random), we simulate a more realistic setting where removal may apply to any
data points irrespective of training batches.

Table 1 shows performance preservation comparison between our proposed
approach (PUMA) and various baselines. In the table, we make the following
observations:

  * •

Among all candidate data removal approaches, PUMA shows the best performance
preservation ability. And, in some cases, the model obtained after the PUMA
operation even shows better performance than the original model.

  * •

Amnesiac ML often completely destroys the model with its data removal
operation when the removal is applied to more than 20% of training data. This
observation aligns with the original results described in the Amnesiac ML
paper (Graves, Nagisetty, and Ganesh 2020) where refined training is required
after the removal operation.

  * •

While Amnesiac ML and SISA show reasonably satisfactory performance
preservation ability in one of the two scenarios, they tend to fail in another
scenario. Amnesiac ML fails in the setting where data may be required to be
removed from random batches. In contrast, SISA does not perform well when the
number of sub-models is reduced, as a consequence of removing all training
data points of the sub-models.

(a) UCI German Credit

(b) MNIST

Figure 3: Execution time comparison among the data removal approaches.
Statistics come from 50 times run, and error bar shows the standard deviation.
Lower is better.

### Effectiveness of Data Removal

Now, we show how well the proposed approach works in removing the influence of
data points from the model. To quantitatively evaluate the performance, we
conduct a membership attack on the model after data removal. Ideally, if the
influence of a data point is successfully removed, then the membership attack
would predict that the given data point does not belong to the training data
set. Hence, a lower value for data removal shows better removal effectiveness.

Table 2 shows a comparison of the effectiveness of the data removal
approaches. In the table, we observe follows:

  * •

In most cases, PUMA shows better data removal performance compared to the
other baseline models. While Amnesiac ML occasionally outperforms PUMA, we
realize that it could be due to a complete model degradation, as previously
observed in Table 1.

  * •

In multiple experiments, we observed that the data removal operations could
not reduce the success rate of membership attack to zero. This is due to the
existence of similar training examples to the marked data points that are not
marked for removal. Since well-train ML models can generalize well on
previously unseen data points, these remaining data points can also fool the
membership attack classifier when the prediction confidence is high enough.

Figure 4: Mislabelling debugging comparison between PUMA and state-of-the-art
debugging algorithms. We corrupted datasets by randomly flipping 10% of the
data labels. The goal of the candidate approaches is to identify and correct
the mislabelled data as early as possible. PUMA shows significant advantage
when only 20% of data are processed during debugging.

(a) Synthetic Radial

(b) UCI German Credit

Figure 5: Effects of hyper-parameter tuning. Large projection rate $\eta$
shows better resistant to the membership attack while suffers from severe
performance degradation.

### Efficiency of Data Removal

As efficiency is the one of most important reason of running the data removal
operation, we compare the execution time of different data removal approaches
in the previously described experimental settings. Here, we only show the two
most representative plots as the general trendy is similar.

Figure 3 shows the execution time comparison on UCI German Credit and MNIST
datasets. Specifically:

  * •

PUMA shows the best efficiency compared to the other candidates when the data
removal happens to be random (i.e. the more practical scenario).

  * •

SISA’s efficiency depends on how many sub-models are involved in retraining.
In the ordered data removal setting, SISA shows competitive efficiency.
However, when the data removal happens to involve more sub-models, its
efficiency is dramatically reduced.

  * •

In general, data removal approaches are more efficient than training a model
from scratch. However, for the small dataset (UCI-German Credit), there is no
significant advantage of using a data removal operation. In particular, the
Amnesiac ML approach does not show better efficiency compared to retraining a
model from scratch.

### Insight of Hyper-parameter Tuning

As introduced in Equation 11, PUMA has one important hyper-parameter $\eta$
which controls the projection step of parameter augmentation. Indeed, a huge
projection step $\eta$ would seriously violate the Taylor approximation
assumption that PUMA approach relies on. Hence, in this experiment, we aim to
demonstrate the importance of tuning this hyper-parameter.

Figure 5 shows the trend of tuning $\eta$ on two representative datasets (UCI
German Credit and MNIST (LeCun and Cortes 2010)). Overall, there is a trade-
off between the effectiveness of removing data and the ability of preserving
model generalization. Keeping the projection rate in the range of
$\eta\in[10^{-2},10^{-1}]$ often show satisfactory removal performance while
maintaining the model’s generalization ability.

### Corrupted Sample Discovery

As PUMA explicitly states the contribution of individual data points to the
performance criterion (see Equation 9), a side functionality of PUMA is to
debug mislabelled data in the same fashion as Influence Function (Koh and
Liang 2017), Representer Point Selection (Yeh et al. 2018), and Data Shapley
(Ghorbani and Zou 2019). We also have included a simplified version of the
Influence function by removing the inverse Hessian matrix from the influence
function formulation to accelerate the computation, denoted by Neural Tangent
Kernel (NTK), due to its similarity to the NTK formulation (Jacot, Gabriel,
and Hongler 2018). Figure 4 shows the overall performance of mislabel
debugging. In this experiment, we randomly flip the label of 10% of the
training data samples and calculate the data values using the aforementioned
algorithms. PUMA outperforms other algorithms by discovering more corrupted
training data points while reviewing fewer data fractions. Tabel 3 shows the
corresponding execution time for the debugging test, where we observe that
PUMA is significantly more efficient than the other approaches.

Table 3: Comparison of Running Time (in Seconds). Lower values in the table
show better performance to the mislabelled data debugging. We omit the
statistic in this table for saving space. Please refer to Appendix D for
statistics.

Data | Approach
---|---
GShapley | NTK | SelfInfluence | RSP | PUMA
Two Moons | $90.37$ | $22.65$ | $1562.93$ | $17.14$ | $\bm{7.61}$
Spiral | $78.47$ | $19.91$ | $1464.01$ | $16.51$ | $\bm{7.44}$
Radial | $82.99$ | $21.60$ | $1563.53$ | $17.76$ | $\bm{7.76}$
Rectangulars | $78.04$ | $20.23$ | $1480.12$ | $16.81$ | $\bm{7.29}$

## Conclusion

This paper presents a novel data removal approach, PUMA, which removes unique
characteristics of marked training data points from a trained ML model while
preserving the model’s performance with respect to certain performance
criterion. Compared to existing approaches which require access to the model
training process, PUMA shows a significant advantage as it does not restrict
how the model is trained. From various experiments, we note PUMA also
demonstrates better performance compared to the baseline approaches in
multiple aspects, including effectiveness, efficiency and performance
preservation ability.

## References

  * Ateniese et al. (2015) Ateniese, G.; Mancini, L. V.; Spognardi, A.; Villani, A.; Vitali, D.; and Felici, G. 2015.  Hacking smart machines with smarter ones: How to extract meaningful data from machine learning classifiers.  _International Journal of Security and Networks_ , 10(3): 137–150.
  * Bourtoule et al. (2019) Bourtoule, L.; Chandrasekaran, V.; Choquette-Choo, C. A.; Jia, H.; Travers, A.; Zhang, B.; Lie, D.; and Papernot, N. 2019.  Machine Unlearning.  _CoRR_ , abs/1912.03817.
  * Cauwenberghs and Poggio (2000) Cauwenberghs, G.; and Poggio, T. A. 2000.  Incremental and Decremental Support Vector Machine Learning.  In Leen, T. K.; Dietterich, T. G.; and Tresp, V., eds., _Advances in Neural Information Processing Systems 13, Papers from Neural Information Processing Systems (NIPS) 2000, Denver, CO, USA_ , 409–415. MIT Press.
  * Dua and Graff (2017) Dua, D.; and Graff, C. 2017.  UCI Machine Learning Repository.
  * Dwork et al. (2015) Dwork, C.; Smith, A. D.; Steinke, T.; Ullman, J. R.; and Vadhan, S. P. 2015.  Robust Traceability from Trace Amounts.  In Guruswami, V., ed., _IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015_ , 650–669. IEEE Computer Society.
  * Fredrikson, Jha, and Ristenpart (2015a) Fredrikson, M.; Jha, S.; and Ristenpart, T. 2015a.  Model Inversion Attacks that Exploit Confidence Information and Basic Countermeasures.  In Ray, I.; Li, N.; and Kruegel, C., eds., _Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA, October 12-16, 2015_ , 1322–1333. ACM.
  * Fredrikson, Jha, and Ristenpart (2015b) Fredrikson, M.; Jha, S.; and Ristenpart, T. 2015b.  Model inversion attacks that exploit confidence information and basic countermeasures.  In _Proceedings of the 22nd ACM SIGSAC conference on computer and communications security_ , 1322–1333.
  * Ghorbani and Zou (2019) Ghorbani, A.; and Zou, J. 2019.  Data shapley: Equitable valuation of data for machine learning.  In _International Conference on Machine Learning_ , 2242–2251. PMLR.
  * Ginart et al. (2019) Ginart, A.; Guan, M. Y.; Valiant, G.; and Zou, J. 2019.  Making AI Forget You: Data Deletion in Machine Learning.  In Wallach, H. M.; Larochelle, H.; Beygelzimer, A.; d’Alché-Buc, F.; Fox, E. B.; and Garnett, R., eds., _Advances in Neural Information Processing Systems 32, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , 3513–3526.
  * Graves, Nagisetty, and Ganesh (2020) Graves, L.; Nagisetty, V.; and Ganesh, V. 2020.  Amnesiac Machine Learning.  _CoRR_ , abs/2010.10981.
  * Guo et al. (2020) Guo, C.; Goldstein, T.; Hannun, A. Y.; and van der Maaten, L. 2020.  Certified Data Removal from Machine Learning Models.  In _Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event_ , volume 119 of _Proceedings of Machine Learning Research_ , 3832–3842. PMLR.
  * Guo et al. (2017) Guo, C.; Pleiss, G.; Sun, Y.; and Weinberger, K. Q. 2017.  On calibration of modern neural networks.  In _International Conference on Machine Learning_ , 1321–1330. PMLR.
  * Hitaj, Ateniese, and Perez-Cruz (2017) Hitaj, B.; Ateniese, G.; and Perez-Cruz, F. 2017.  Deep models under the GAN: information leakage from collaborative deep learning.  In _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_ , 603–618.
  * Homer et al. (2008) Homer, N.; Szelinger, S.; Redman, M.; Duggan, D.; Tembe, W.; Muehling, J.; Pearson, J. V.; Stephan, D. A.; Nelson, S. F.; and Craig, D. W. 2008.  Resolving individuals contributing trace amounts of DNA to highly complex mixtures using high-density SNP genotyping microarrays.  _PLoS Genet_ , 4(8): e1000167.
  * Huang et al. (2017) Huang, G.; Liu, Z.; Van Der Maaten, L.; and Weinberger, K. Q. 2017.  Densely connected convolutional networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 4700–4708.
  * Jacot, Gabriel, and Hongler (2018) Jacot, A.; Gabriel, F.; and Hongler, C. 2018.  Neural tangent kernel: Convergence and generalization in neural networks.  _arXiv preprint arXiv:1806.07572_.
  * Karasuyama and Takeuchi (2009) Karasuyama, M.; and Takeuchi, I. 2009.  Multiple incremental decremental learning of support vector machines.  _Advances in neural information processing systems_ , 22: 907–915.
  * Koh and Liang (2017) Koh, P. W.; and Liang, P. 2017.  Understanding Black-box Predictions via Influence Functions.  In Precup, D.; and Teh, Y. W., eds., _Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017_ , volume 70 of _Proceedings of Machine Learning Research_ , 1885–1894. PMLR.
  * LeCun and Cortes (2010) LeCun, Y.; and Cortes, C. 2010.  MNIST handwritten digit database.
  * Lyu and Chen (2021) Lyu, L.; and Chen, C. 2021.  A Novel Attribute Reconstruction Attack in Federated Learning.  _arXiv preprint arXiv:2108.06910_.
  * Nasr, Shokri, and Houmansadr (2018) Nasr, M.; Shokri, R.; and Houmansadr, A. 2018.  Comprehensive Privacy Analysis of Deep Learning: Stand-alone and Federated Learning under Passive and Active White-box Inference Attacks.  _CoRR_ , abs/1812.00910.
  * Shokri et al. (2017) Shokri, R.; Stronati, M.; Song, C.; and Shmatikov, V. 2017.  Membership inference attacks against machine learning models.  In _2017 IEEE Symposium on Security and Privacy (SP)_ , 3–18. IEEE.
  * Tsai, Lin, and Lin (2014) Tsai, C.; Lin, C.; and Lin, C. 2014.  Incremental and decremental training for linear classification.  In Macskassy, S. A.; Perlich, C.; Leskovec, J.; Wang, W.; and Ghani, R., eds., _The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’14, New York, NY, USA - August 24 - 27, 2014_ , 343–352. ACM.
  * Yang et al. (2021) Yang, F.; Zhong, Z.; Liu, H.; Wang, Z.; Luo, Z.; Li, S.; Sebe, N.; and Satoh, S. 2021.  Learning to Attack Real-World Models for Person Re-identification via Virtual-Guided Meta-Learning.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, 3128–3135.
  * Yeh et al. (2018) Yeh, C.-K.; Kim, J. S.; Yen, I. E.; and Ravikumar, P. 2018.  Representer point selection for explaining deep neural networks.  _arXiv preprint arXiv:1811.09720_.
  * Yeom et al. (2018) Yeom, S.; Giacomelli, I.; Fredrikson, M.; and Jha, S. 2018.  Privacy Risk in Machine Learning: Analyzing the Connection to Overfitting.  In _31st IEEE Computer Security Foundations Symposium, CSF 2018, Oxford, United Kingdom, July 9-12, 2018_ , 268–282. IEEE Computer Society.

## Appendix A: Detailed Experiment Setup

### Dataset

The experiments in this paper involves three groups of data sources, including
synthetically generated data, UCI data (Dua and Graff 2017), and the MNIST
dataset (LeCun and Cortes 2010). Table 4 summarizes the datasets used in this
paper.

Table 4: Dataset used in the experiments.

Dataset | Size | Num of Features | Num of Labels | Model Architecture
---|---|---|---|---
Radial | 600 | 2 | 2 | 2-layer FCN
Rectangular | 800 | 2 | 3 | 2-layer FCN
Breast Cancer | 699 | 9 | 2 | 2-layer FCN
German Credit | 1000 | 20 | 2 | 2-layer FCN
MNIST | 70000 | 784 | 10 | DenseNet

#### Synthetic Data

We used multiple synthetic datasets to conduct the proof of concept
experiments in the paper as the results are easy to visualize and interpret.
Figure 6 shows the synthetic data we produced for our experiments.

(a) Radial

(b) Rectangular

Figure 6: Synthetic data used in our experiments. Radial dataset has 2 classes
with 6 clusters, while rectangular dataset has 3 classes with 16 clusters.

#### UCI datasets

The UCI data is a group of classic tabular datasets well suited to justify the
quantitative performance of a ML model in the literature. Among the hundreds
of datasets, we chose to use German Credit and Breast Cancer dataset in our
experiments since both of the datasets are closely related to two important
machine learning application fields: finance and medicine.

#### MNIST

We include the MNIST dataset along with the Convolution Network (DenseNet)
architecture in our experiments to show that the proposed approach can work on
more complex model architectures than simple Fully Connected Networks (FNC).
In addition to the quantitative evaluations of the main paper, we also use it
to visualize the effects of data removal in Appendix C.

### Predictive Models

In the experiments, we train the classifiers with two neural network
architectures. Specifically, for the synthetic and the tabular (UCI) data, we
train fully connected neural networks that have two hidden layers with
dimension of 64 and 32 respectively. For the MNIST dataset, we train a
DenseNet model (Huang et al. 2017) to reach a better prediction performance.

The following pytorch code shows the actual architecture we used in the
experiments.

⬇

1class FlexibleFCN(nn.Module):

2 def __init__(self, neurons, activation):

3 super(FlexibleFCN, self).__init__()

4 self.layers = nn.ModuleList()

5 for i in range(len(neurons) - 1):

6 self.layers.append(torch.nn.Linear(neurons[i], neurons[i + 1]))

7 if activation == ”relu”:

8 self.activation = torch.nn.ReLU()

9 else:

10 self.activation = torch.nn.Sigmoid()

11

12 def forward(self, x):

13 for i in range(len(self.layers) - 1):

14 x = self.layers[i](x)

15 x = self.activation(x)

16 x = self.layers[-1](x)

17 return x

Listing 1: Fully Connect Network

⬇

1class DenseNet(nn.Module):

2 def __init__(

3 self,

4 block,

5 nblocks,

6 growth_rate=12,

7 reduction=0.5,

8 num_classes=10,

9 channel=3,

10 last_pool_size=4,

11 ):

12 super(DenseNet, self).__init__()

13 self.growth_rate = growth_rate

14

15 num_planes = 2 * growth_rate

16 self.conv1 = nn.Conv2d(

17 channel, num_planes, kernel_size=3,

18 padding=1, bias=False

19 )

20

21 self.dense1 = self._make_dense_layers(block,

22 num_planes,

23 nblocks[0])

24 num_planes += nblocks[0] * growth_rate

25 out_planes = int(math.floor(num_planes * reduction))

26 self.trans1 = Transition(num_planes, out_planes)

27 num_planes = out_planes

28

29 self.dense2 = self._make_dense_layers(block,

30 num_planes,

31 nblocks[1])

32 num_planes += nblocks[1] * growth_rate

33 out_planes = int(math.floor(num_planes * reduction))

34 self.trans2 = Transition(num_planes, out_planes)

35 num_planes = out_planes

36

37 self.dense3 = self._make_dense_layers(block,

38 num_planes,

39 nblocks[2])

40 num_planes += nblocks[2] * growth_rate

41 out_planes = int(math.floor(num_planes * reduction))

42 self.trans3 = Transition(num_planes, out_planes)

43 num_planes = out_planes

44

45 self.dense4 = self._make_dense_layers(block,

46 num_planes,

47 nblocks[3])

48 num_planes += nblocks[3] * growth_rate

49

50 self.bn = nn.BatchNorm2d(num_planes)

51 self.linear = nn.Linear(num_planes, num_classes)

52 self.softmax = torch.nn.Softmax(dim=1)

53 self.num_classes = num_classes

54

55 self.last_pool_size = last_pool_size

56

57 def _make_dense_layers(self, block, in_planes, nblock):

58 layers = []

59 for i in range(nblock):

60 layers.append(block(in_planes, self.growth_rate))

61 in_planes += self.growth_rate

62 return nn.Sequential(*layers)

63

64 def forward(self, x):

65 out = self.conv1(x)

66 out = self.trans1(self.dense1(out))

67 out = self.trans2(self.dense2(out))

68 out = self.trans3(self.dense3(out))

69 out = self.dense4(out)

70 out = F.avg_pool2d(F.relu(self.bn(out)),

71 self.last_pool_size)

72 out = out.view(out.size(0), -1)

73 out = self.linear(out)

74 return out

Listing 2: CNN DenseNet

### Membership Attack Setup

We implemented the attack model based on the description in the original
membership attack paper (Shokri et al. 2017). Since, in our experimental
setting, the training data is fully observable, we use the training data to
train the shadow models. Here, the shadow models hold the same architecture as
the predictive models described previously.

We train a membership attack model for each of the datasets using five shadow
models, where each shadow model is trained on a subset of data points (less
than 10% of training set) randomly sampled from the training set. The number
of training epochs for the shadow models is set to 50.

After training the shadow models, a neural network based binary classifier is
trained on the output of the shadow models to predict whether a data point has
been a member of the training set or not. The architecture of this classifier
is a two-hidden layer neural network with latent dimensions of 128 and 64.
This architecture aligns with the description in the previous data removal
literature (Graves, Nagisetty, and Ganesh 2020). The binary classifier is then
used to attack the predictive models before and after data removal to
demonstrate the effectiveness of the data removal algorithms.

### Data Marking for Removal Experiment

As mentioned in the main paper, when many similar data points exist in a
dataset, removing one or a small set of them does not help to demonstrate the
data removal performance (via membership attack) since the ML model would
generalize to the removed data points with high prediction confidence.

Hence, we mark the data through a clustering based approach. Specifically, we
conduct the following steps to mark the data for removal experiments:

  1. 1.

For each class $y$ in the training set, run a k-means clustering algorithm on
the features $\mathbf{X}$.

  2. 2.

Choose all data points in a cluster from the k-means clusters as the marked
data points.

  3. 3.

Run step 1-2 for all classes.

The following python code shows how we did it in our implementation.

⬇

1@staticmethod

2def mark_data(data_loader, label_interested, clustering=True):

3 with torch.no_grad():

4 tensor_X, tensor_y = data_loader.dataset.tensors

5 label_index = torch.where(tensor_y == label_interested)[0].cpu().numpy()

6 if not clustering:

7 data_index_to_remove = label_index

8 else:

9 x = tensor_X.cpu().numpy()[label_index]

10 kmeans = KMeans(n_clusters=8, random_state=0).fit(

11 np.array(x).reshape(len(x), -1)

12 )

13 values, counts = np.unique(kmeans.labels_, return_counts=True)

14 value_pri = values[counts.argsort()[0]]

15 data_index_to_remove = label_index[np.where(kmeans.labels_ == value_pri)]

16 return data_index_to_remove

Listing 3: Mark Data to Remove

### How does Amnesiac ML and SISA Handle Single/Batch Data Removal?

Amnesiac ML does not support single data removal operation since it requires
storing the gradient information for each point, which is barely possible in
practice. Hence, to remove contribution of a single data point, we need to
remove the entire training batch containing the point in question.

Indeed, in the Experiment and Evaluation section, we mentioned that we have
two experiment scenarios, namely Ordered and Random. In the Ordered scenario,
we assume all data points that are marked to be removed belong to the same
data batch. In this particular setting, Amnesiac ML could work as it was
presented in its original paper (Graves, Nagisetty, and Ganesh 2020). We
introduce this scenario for the purpose of fair comparison. For a more
realistic scenario (Random), since the marked data points may be spread across
many batches, we have no choice but to remove the batches that contain the
marked data points. Hence, the updated model could face severe performance
degradation, as shown in Table 1.

SISA naturally supports removing single a data point since it retrains the
sub-model that has been trained on the marked data point. However, SISA faces
a computational challenge when we remove multiple data points requiring to
retrain multiple involved sub-models simultaneously. Hence, SISA’s efficiency
depends on the distribution of marked data points in the sub-model training
datasets. This intuition could be justified in our experiment results (Figure
3), where we show SISA’s run time varies when we switch scenarios (Random vs.
Ordered).

## Appendix B: Algorithm Implementation

In this section, we present the implementation details of the PUMA algorithm
in the form of pseudo-code.

### PUMA Removal Pseudo Code

Algorithm 1 shows the pseudo-code of the PUMA data removal procedure. Here, we
use $D_{\textit{up}}$ instead of $D_{\textit{up}/\textit{mk}}$ to represent
the reweight data points for simplicity.

Algorithm 1 PUMA Data Characteristics Removal

Original model $\theta_{\textit{org}}$, Training objective
$\mathcal{J}_{\textit{org}}$, Performance criterion $\mathcal{C}$, Data marked
to remove $D_{\textit{mk}}$, Whole training set $D_{\textit{tn}}$, Learning
rate $\eta$

Optional: Upweight data $D_{\textit{up}}$

$\mathcal{C}$ is differentiable, $D_{\textit{mk}}\subset D_{\textit{tn}}$

$\nabla\mathcal{C}\leftarrow\textit{Gradient}(\mathcal{C},D_{\textit{tn}},\theta_{\textit{org}})$

$\nabla\mathcal{C}\left(\nabla^{2}\mathcal{J}_{\textit{org}}\right)^{-1}\\!\\!\leftarrow\textit{HVP}(\mathcal{J}_{\textit{org}},D_{\textit{tn}},\theta_{\textit{org}},\nabla\mathcal{C})$
$\triangleright$ Cache

$D_{\textit{up}}\leftarrow\textit{Sample}(D_{\textit{tn}},\textit{excluding}=D_{\textit{mk}})$
$\triangleright$ Optional

for $(\mathbf{x}_{k},y_{k})\in D_{\textit{mk}}$ do $\triangleright$ Get Data
Influence

$\psi(\mathbf{x}_{k},y_{k})\\!\leftarrow\\!\nabla\mathcal{C}\\!\left(\nabla^{2}\mathcal{J}_{\textit{org}}\right)^{\\!-1}\\!\nabla\mathcal{L}(\mathbf{x}_{k},y_{k},\theta_{\textit{org}})$

for $(\mathbf{x}_{j},y_{j})\in D_{\textit{up}}$ do $\triangleright$ Get Data
Influence

$\psi(\mathbf{x}_{j},y_{j})\\!\leftarrow\\!\underbrace{\nabla\mathcal{C}\\!\left(\nabla^{2}\mathcal{J}_{\textit{org}}\right)^{\\!-1}}_{\textit{Cached}}\\!\nabla\mathcal{L}(\mathbf{x}_{j},y_{j},\theta_{\textit{org}})$

$\bm{\lambda}^{*}\\!\leftarrow\\!\underset{\bm{\lambda}}{\operatorname{\arg\\!\min}}\left\lVert\sum_{j}\lambda_{j}\psi(\mathbf{x}_{j},y_{j})\\!-\\!\sum_{k}\psi(\mathbf{x}_{k},y_{k})\right\rVert^{2}\\!+\\!\Omega(\bm{\lambda})$
$\triangleright$ SLSQP Constraint Optimization

$V_{\textit{mk}}\leftarrow 0$ $\triangleright$ Get Parameter Projection
Direction

for $(\mathbf{x}_{k},y_{k})\in D_{\textit{mk}}$ do

$V_{\textit{mk}}\leftarrow
V_{\textit{mk}}+\nabla\mathcal{L}(\mathbf{x}_{k},y_{k},\theta_{\textit{org}})$

$\Phi_{\textit{mk}}\leftarrow\textit{HVP}(\mathcal{J}_{\textit{org}},D_{\textit{tn}},\theta_{\textit{org}},V_{\textit{mk}})$

$V_{\textit{up}}\leftarrow 0$ $\triangleright$ Get Parameter Projection
Direction

for $(\mathbf{x}_{j},y_{j})\in D_{\textit{mk}}$ do

$V_{\textit{up}}\leftarrow
V_{\textit{up}}+\lambda_{j}\nabla\mathcal{L}(\mathbf{x}_{j},y_{j},\theta_{\textit{org}})$

$\Phi_{\textit{up}}\leftarrow\textit{HVP}(\mathcal{J}_{\textit{org}},D_{\textit{tn}},\theta_{\textit{org}},V_{\textit{up}})$

$\theta_{\textit{mod}}\leftarrow\theta_{\textit{org}}+\eta\left[\Phi_{\textit{mk}}-\Phi_{\textit{up}}\right]$
$\triangleright$ Update Model

Overall, there are five fundamental steps in the procedure.

  1. 1.

Compute and cache the Hessian Vector Product
$\nabla\mathcal{C}\left(\nabla^{2}\mathcal{J}_{\textit{org}}\right)^{-1}$ for
both the training objective $\mathcal{J}$ and performance criterion
$\mathcal{C}$ on training data $D_{\textit{tn}}$.

  2. 2.

Estimate the influence value of the data points marked for removal
$D_{\textit{mk}}$ and the reweighted data points $D_{\textit{up}}$.

  3. 3.

Optimize the reweighting weights $\bm{\lambda}$ with constrained optimization
algorithms. E.g. SLSQP or L-BFGS.

  4. 4.

Estimate the weighted parameter projection directions for both
$D_{\textit{mk}}$ and $D_{\textit{up}}$

  5. 5.

Update the model parameters with learning rate $\eta$

While computing the inverse of the Hessian matrix is possible for simple
linear models, it is generally infeasible for more complicated setups, since
there is no guarantee on the Hessian matrix to be positive definite, as
noticed in the previous literature (Koh and Liang 2017). Hence, in our
implementation, we directly compute the Hessian Vector Product approximation
to avoid the potential numerical issue.

### PUMA Data Debugging Pesudo Code

While PUMA was originally not designed for debugging mislabeled data, we note
it shows reasonably good performance (with significant advantage in
efficiency) compared with the state-of-the-art approaches.

As mentioned in the main paper, since PUMA computes the influence of each data
point on the overall model performance (see Equation 9), we can use this
information to rank the data points and identify the mislabelled data points
that usually have large negative influences. In addition, since the data
points close to the decision boundary are often noisy, we filter the candidate
data points with this condition to avoid large false positive predictions.
Algorithm 2 shows the algorithm for debugging mislabelled data.

Algorithm 2 PUMA Problematic Data Debugging

Original model $\theta_{\textit{org}}$, Training objective
$\mathcal{J}_{\textit{org}}$, Performance criterion $\mathcal{C}$, Whole
training set $D_{\textit{tn}}$, Number of problematic data to return $k$

$\mathcal{C}$ is differentiable

$\nabla\mathcal{C}\leftarrow\textit{Gradient}(\mathcal{C},D_{\textit{tn}},\theta_{\textit{org}})$

$\nabla\mathcal{C}\left(\nabla^{2}\mathcal{J}_{\textit{org}}\right)^{-1}\\!\\!\leftarrow\textit{HVP}(\mathcal{J}_{\textit{org}},D_{\textit{tn}},\theta_{\textit{org}},\nabla\mathcal{C})$
$\triangleright$ Cache

$\textit{Confidence}\leftarrow\textit{EmptyList}()$

$\textit{Influence}\leftarrow\textit{EmptyList}()$

for $(\mathbf{x}_{i},y_{i})\in D_{\textit{tn}}$ do

$\textit{Confidence}[i]\leftarrow
p(y_{i}|\mathbf{x}_{i};\theta_{\textit{org}})$ $\triangleright$ Prediction

$\textit{Influence}[i]\leftarrow\underbrace{\nabla\mathcal{C}\\!\left(\nabla^{2}\mathcal{J}_{\textit{org}}\right)^{\\!-1}}_{\textit{Cached}}\\!\nabla\mathcal{L}(\mathbf{x}_{i},y_{i},\theta_{\textit{org}})$

$L_{\textit{if}}\leftarrow\textit{argsort}(\textit{Influence},\textit{top}=k)$
$\triangleright$ Top low influences

$L_{\textit{cf}}\leftarrow\textit{argsort}(\textit{Confidence},\textit{top}=k)$

$H_{\textit{cf}}\leftarrow\textit{argsort}(\textit{Confidence},\textit{bottom}=k)$

$S\leftarrow L_{\textit{if}}\setminus(L_{\textit{cf}}\cup H_{\textit{cf}})$
$\triangleright$ Candidate mislabelled data

if
$\textit{mean}(\textit{Influence},S)\\!>\\!\textit{mean}(\textit{Influence},L_{\textit{if}}\cap
L_{\textit{cf}})$ then

$S\leftarrow\emptyset$

return S

Compared to the self-influence method (Koh and Liang 2017), our proposed
approach does not require computing the Hessian Vector Product (HVP) for each
training data. Instead, it caches the HVP for the entire training set and
computes individual data point influence through simple gradient estimation
and dot-product (with the cached HVP). While using the entire training data’s
HVP may hurt our approach’s debugging performance, we empirically show that
the performance degradation is negligible.

(a) Data

(b) Model prediction before removal

(c) Model prediction after removal

Figure 7: Removing the training points marked by crosses from the model. As
demonstrated in the right plot, PUMA successfully removed the information of
all marked points. ‘x’ in the plot shows the data intended to remove. Colors
show the class labels.

(a) Data marked to remove
(Predictions of original model)

(b) Data marked to remove
(Predictions of augmented model)

(c) Other data in the same class
(Predictions of augmented model)

(d) Randomly sampled data
(Predictions of augmented model)

Figure 8: Removing marked data points that belong to a particular style of
digit 4. On top of each digit image, we show the ground truth label (denoted
as T), predicted label (denoted as P), and the prediction confidence (denoted
as Prob).

## Appendix C: More Demo Cases

In this section, we show two demonstrative examples which visualize the data
removal effect of PUMA.

Figure 7(a) shows a binary classification task, where data points are
distributed as moon shapes. Since there is no noise introduced in the data
generation process, the model can make perfect predictions as shown in Figure
7(b). When we remove the data points marked as ‘x’ from the train model (see
Figure 7(c)), the top four data points are classified as belonging to the
orange class and the bottom one is still classified as the green class. More
importantly, the predictions for the other data points remain unchanged. This
observation reflects our intuition, where PUMA would leverage remaining data
points to stabilize the model’s generalization ability by complementing the
loss of the removed data points.

Figure 8 shows a more complex removal case, where we try to remove some data
points belonging to digit 4 with a certain writing style. Figure 8 (a) shows
that, before the removal operation, the model predicts the marked data points
quite well; all of the predictions are correct with high confidence ($=1.0$).
After the removal operation, we note the marked data points are misclassified
with various prediction confidences, as shown in Figure 8 (b). In contrast,
the predictions on other data points of the same class are not seriously
affected by the removal operation as their predictions are still correct, as
shown in Figure 8 (c). This demonstrates that the PUMA data removal operation
does not false-fully generalize to the other data points in the same class,
even if they look similar. Finally, Figure 8 (d) shows that the removal
operation also preserved the prediction accuracy for other inputs.

Table 5: Comparison of Model Performance Preservation among Candidate Removal
Approaches with Statistics. Value shows accuracy. Higher is better after data
removal. Results are collected from 20 times independent experiments.

Data Group | Dataset | Ordered
---|---|---
Original | Approach | 20% | 40% | 60% | 80%
Synthetic | Radial | $95.04\pm 0.59$ | Retrain Model | $\bm{93.64\pm 0.87}$ | $\bm{91.60\pm 1.22}$ | $\bm{84.15\pm 3.00}$ | $66.24\pm 6.42$
$80.88\pm 3.62$ | SISA | $67.35\pm 8.16$ | $61.93\pm 7.86$ | $63.57\pm 9.53$ | $51.91\pm 4.57$
$95.04\pm 0.59$ | Amnesiac ML | $56.38\pm 4.85$ | $54.75\pm 4.46$ | $53.53\pm 4.68$ | $50.54\pm 1.60$
$94.97\pm 0.64$ | PUMA | $68.97\pm 9.47$ | $69.60\pm 4.88$ | $67.99\pm 5.62$ | $\bm{70.77\pm 7.61}$
Rectangular | $62.00\pm 0.81$ | Retrain Model | $\bm{61.20\pm 1.08}$ | $\bm{60.35\pm 1.10}$ | $\bm{55.80\pm 3.75}$ | $54.25\pm 3.86$
$55.60\pm 5.04$ | SISA | $55.90\pm 4.97$ | $48.30\pm 12.39$ | $30.10\pm 7.78$ | $29.55\pm 5.71$
| $62.00\pm 0.81$ | Amnesiac ML | $46.60\pm 9.34$ | $43.85\pm 8.37$ | $43.45\pm 9.73$ | $39.15\pm 4.29$
| $61.85\pm 0.74$ | PUMA | $55.25\pm 8.28$ | $56.30\pm 6.11$ | $53.85\pm 9.64$ | $\bm{61.70\pm 6.80}$
Tabular (UCI) | German | $71.52\pm 0.49$ | Retrain Model | $\bm{70.56\pm 0.86}$ | $70.12\pm 0.80$ | $70.11\pm 0.73$ | $70.00\pm 0.00$
$70.00\pm 0.00$ | SISA | $70.00\pm 0.00$ | $70.00\pm 0.00$ | $68.96\pm 3.28$ | $66.16\pm 5.23$
$71.52\pm 0.49$ | Amnesiac ML | $68.52\pm 5.26$ | $64.40\pm 10.80$ | $66.24\pm 8.60$ | $64.03\pm 12.27$
$71.47\pm 0.50$ | PUMA | $69.08\pm 3.19$ | $\bm{70.72\pm 0.77}$ | $\bm{70.64\pm 0.73}$ | $\bm{70.72\pm 1.07}$
Breast Cancer | $96.45\pm 0.45$ | Retrain Model | $\bm{96.62\pm 0.42}$ | $\bm{96.11\pm 0.59}$ | $96.00\pm 0.54$ | $94.85\pm 1.92$
$91.31\pm 1.84$ | SISA | $89.20\pm 1.67$ | $88.91\pm 5.61$ | $80.68\pm 12.00$ | $52.62\pm 26.43$
| $96.45\pm 0.45$ | Amnesiac ML | $96.05\pm 1.71$ | $95.82\pm 1.54$ | $95.25\pm 2.85$ | $82.28\pm 11.89$
| $96.39\pm 0.47$ | PUMA | $96.17\pm 1.42$ | $95.88\pm 1.67$ | $\bm{96.22\pm 0.61}$ | $\bm{96.62\pm 0.62}$
Image | MNIST | $97.58\pm 0.48$ | Retrain Model | $\bm{97.28\pm 0.16}$ | $\bm{96.72\pm 0.56}$ | $95.76\pm 0.73$ | $93.48\pm 0.47$
$95.89\pm 0.24$ | SISA | $95.80\pm 0.36$ | $95.67\pm 0.57$ | $94.78\pm 0.46$ | $89.86\pm 0.39$
$97.44\pm 0.43$ | Amnesiac ML | $9.44\pm 1.12$ | $9.84\pm 1.42$ | $9.56\pm 1.25$ | $9.36\pm 1.24$
| $97.60\pm 0.37$ | PUMA | $96.70\pm 0.99$ | $96.66\pm 0.48$ | $\bm{97.17\pm 0.33}$ | $\bm{97.16\pm 0.26}$

Data Group | Dataset | Random
---|---|---
Original | Approach | 20% | 40% | 60% | 80%
Synthetic | Radial | $95.89\pm 0.88$ | Retrain Model | $\bm{93.97\pm 1.01}$ | $\bm{90.94\pm 1.25}$ | $\bm{82.58\pm 4.87}$ | $66.51\pm 6.61$
$75.62\pm 5.55$ | SISA | $64.71\pm 7.29$ | $64.35\pm 8.78$ | $54.80\pm 3.65$ | $54.77\pm 5.70$
$95.88\pm 0.88$ | Amnesiac ML | $49.08\pm 2.31$ | $48.95\pm 2.20$ | $48.95\pm 2.20$ | $48.95\pm 2.20$
$95.82\pm 0.86$ | PUMA | $72.44\pm 7.05$ | $73.22\pm 7.82$ | $71.82\pm 7.39$ | $\bm{76.02\pm 8.43}$
Rectangular | $65.00\pm 0.23$ | Retrain Model | $\bm{64.70\pm 1.00}$ | $\bm{64.50\pm 1.54}$ | $62.30\pm 2.49$ | $58.65\pm 3.55$
$56.50\pm 0.00$ | SISA | $56.50\pm 0.00$ | $56.50\pm 0.00$ | $56.55\pm 0.15$ | $56.90\pm 1.44$
| $65.00\pm 0.23$ | Amnesiac ML | $35.40\pm 19.08$ | $35.40\pm 19.08$ | $35.40\pm 19.08$ | $35.40\pm 19.08$
| $64.95\pm 0.15$ | PUMA | $59.90\pm 4.53$ | $62.05\pm 2.74$ | $\bm{62.55\pm 2.49}$ | $\bm{64.80\pm 1.60}$
Tabular (UCI) | German | $75.16\pm 0.66$ | Retrain Model | $\bm{74.88\pm 0.95}$ | $\bm{73.24\pm 0.66}$ | $72.47\pm 0.88$ | $70.00\pm 0.18$
$70.00\pm 0.00$ | SISA | $70.00\pm 0.00$ | $70.00\pm 0.00$ | $70.00\pm 0.00$ | $70.00\pm 0.00$
$75.16\pm 0.66$ | Amnesiac ML | $36.24\pm 7.50$ | $36.28\pm 7.46$ | $35.72\pm 7.69$ | $35.72\pm 7.69$
$75.12\pm 0.61$ | PUMA | $70.96\pm 3.62$ | $\bm{73.24\pm 1.39}$ | $\bm{74.44\pm 0.66}$ | $\bm{74.28\pm 1.29}$
Breast Cancer | $96.00\pm 0.00$ | Retrain Model | $\bm{95.82\pm 0.27}$ | $\bm{95.54\pm 0.36}$ | $\bm{95.65\pm 0.39}$ | $95.20\pm 0.67$
$92.28\pm 2.24$ | SISA | $91.60\pm 2.95$ | $88.05\pm 4.57$ | $88.22\pm 4.20$ | $87.88\pm 5.23$
| $96.00\pm 0.00$ | Amnesiac ML | $35.20\pm 20.33$ | $30.51\pm 18.97$ | $30.51\pm 18.97$ | $30.51\pm 18.97$
| $96.00\pm 0.00$ | PUMA | $95.08\pm 1.94$ | $94.91\pm 2.29$ | $95.25\pm 1.76$ | $\bm{95.54\pm 0.24}$
Image | MNIST | $97.99\pm 0.36$ | Retrain Model | $\bm{97.72\pm 0.29}$ | $97.16\pm 0.42$ | $96.60\pm 0.74$ | $93.98\pm 0.72$
$95.66\pm 0.41$ | SISA | $93.47\pm 0.68$ | $90.63\pm 1.51$ | $78.06\pm 3.28$ | $59.83\pm 10.02$
$98.06\pm 0.37$ | Amnesiac ML | $10.39\pm 1.32$ | $10.39\pm 1.32$ | $10.39\pm 1.32$ | $10.39\pm 1.32$
| $97.97\pm 0.34$ | PUMA | $97.42\pm 0.66$ | $\bm{97.58\pm 0.36}$ | $\bm{97.60\pm 0.58}$ | $\bm{97.61\pm 0.44}$

## Appendix D: Results with Statistics

Here we show the full table of our experiment results with statistics that
were omitted in the main paper.

### Performance Preservation with Statistics

Table 5 shows the performance preservation table. The mean values are exactly
the same as presented in the main paper. Statistics show standard deviation of
10 runs. Here, we note that Amnesiac ML often shows a large variance compared
to the other approaches, even when the marked data points are intentionally
organized into a small number of batches (see results in Ordered scenario). In
addition, we also observe that, on the small datasets, training multiple sub-
models (as SISA does) often results in bad performance compared with single
model approaches (Retrain, Amnesiac ML, and PUMA).

Table 6: Comparison of Membership Attack after Data Removal Operation. Value
shows percentage of removed data that is identified as training data. Lower
values in the table show better performance of removal.

Data Group | Dataset | Ordered
---|---|---
Retrain Model | SISA | Amnesiac ML | PUMA
Before | After | Before | After | Before | After | Before | After
Synthetic | Radial | $100.00\pm 0.00$ | $100.00\pm 0.00$ | $100.00\pm 0.00$ | $100.00\pm 0.00$ | $100.00\pm 0.00$ | $\bm{0.00\pm 0.00}$ | $100.00\pm 0.00$ | $5.31\pm 10.38$
Rectangular | $100.00\pm 0.00$ | $91.65\pm 6.20$ | $83.18\pm 19.76$ | $83.18\pm 19.76$ | $100.00\pm 0.00$ | $\bm{33.33\pm 0.00}$ | $100.00\pm 0.00$ | $36.66\pm 29.18$
Tabular | German | $100.00\pm 0.00$ | $77.12\pm 1.38$ | $100.00\pm 0.00$ | $100.00\pm 0.00$ | $100.00\pm 0.00$ | $0.00\pm 0.00$ | $100.00\pm 0.00$ | $\bm{3.42\pm 6.90}$
Breast Cancer | $100.00\pm 0.00$ | $100.00\pm 0.00$ | $87.50\pm 8.83$ | $87.50\pm 8.83$ | $100.00\pm 0.00$ | $100.00\pm 0.00$ | $100.00\pm 0.00$ | $\bm{56.25\pm 13.50}$
Image | MNIST | $100.00\pm 0.00$ | $100.00\pm 0.00$ | $100.00\pm 0.00$ | $100.00\pm 0.00$ | $100.00\pm 0.00$ | $100.00\pm 0.00$ | $100.00\pm 0.00$ | $\bm{0.00\pm 0.00}$

Data Group | Dataset | Random
---|---|---
Retrain Model | SISA | Amnesiac ML | PUMA
Before | After | Before | After | Before | After | Before | After
Synthetic | Radial | $100.00\pm 0.00$ | $52.36\pm 3.86$ | $100.00\pm 0.00$ | $37.00\pm 17.88$ | $100.00\pm 0.00$ | $50.00\pm 0.00$ | $100.00\pm 0.00$ | $\bm{1.18\pm 1.96}$
Rectangular | $100.00\pm 0.00$ | $67.07\pm 5.29$ | $98.50\pm 3.37$ | $94.00\pm 12.86$ | $100.00\pm 0.00$ | $86.20\pm 0.00$ | $100.00\pm 0.00$ | $\bm{20.00\pm 23.30}$
Tabular | German | $94.44\pm 0.00$ | $84.44\pm 2.34$ | $100.00\pm 0.00$ | $98.81\pm 8.38$ | $94.44\pm 0.00$ | $93.33\pm 3.51$ | $85.18\pm 2.22$ | $\bm{2.22\pm 7.13}$
Breast Cancer | $100.00\pm 0.00$ | $100.00\pm 0.00$ | $90.00\pm 7.90$ | $73.75\pm 27.29$ | $100.00\pm 0.00$ | $87.50\pm 0.00$ | $100.00\pm 0.00$ | $\bm{71.25\pm 25.71}$
Image | MNIST | $100.00\pm 0.00$ | $100.00\pm 0.00$ | $100.00\pm 0.00$ | $100.00\pm 0.00$ | $100.00\pm 0.00$ | $100.00\pm 0.00$ | $100.00\pm 0.00$ | $\bm{72.00\pm 13.03}$

Table 7: Comparison of Running Time (in Seconds). Lower values in the table
show better performance to the mislabelled data debugging. We omit the
statistic in this table for saving space. Please refer to appendix for
statistics.

Data | Approach
---|---
GShapley | NTK | SelfInfluence | RSP | PUMA
Two Moons | $90.37\pm 2.50$ | $22.65\pm 0.62$ | $1562.93\pm 113.78$ | $17.14\pm 0.17$ | $\bm{7.61\pm 0.08}$
Spiral | $78.47\pm 0.62$ | $19.91\pm 0.23$ | $1464.01\pm 5.32$ | $16.51\pm 0.13$ | $\bm{7.44\pm 0.11}$
Radial | $82.99\pm 0.29$ | $21.60\pm 0.42$ | $1563.53\pm 2.54$ | $17.76\pm 0.27$ | $\bm{7.76\pm 0.07}$
Rectangulars | $78.04\pm 0.79$ | $20.23\pm 0.38$ | $1480.12\pm 9.33$ | $16.81\pm 0.26$ | $\bm{7.29\pm 0.08}$

### Removal Performance with Statistics

Table 6 shows the data removal performance table with statistics. As the data
points marked to be removed are randomly selected in each experiment, we
observe large variances in the table. However, since the mean values reported
in the table are dramatically different, we don’t observe an overlap among the
statistics of the results.

### Execution Time for Debugging

Table 7 shows the execution time for mislabelled data debugging with
statistics.

## Appendix E: Model Calibration Application

As described in the main paper, PUMA preserves model performance while
removing and reweighting the contributions of the training data points. The
performance can be measured by any differentiable performance criterion
$\mathcal{C}$. In this example, we define the performance criterion
$\mathcal{C}$ as an Expected Calibration Error (ECE) (Guo et al. 2017).

In the following context, we first use PUMA’s data debugging ability to
identify the problematic data points causing mis-calibration. We then use
PUMA’s data removal functionality to update the model parameters to get a
better calibrated model.

### Identifying Problematic Data Points

To identify the problematic data points causing mis-calibration, we need to
modify the PUMA debugging algorithm to filter the problematic data points into
three categories, namely over-confidence, over-uncertain, and other-noise.
Specifically, we make the following adjustment on the Algorithm 2 to meet the
requirement.

Algorithm 3 PUMA Problematic Data Debugging

Original model $\theta_{\textit{org}}$, Training objective
$\mathcal{J}_{\textit{org}}$, Performance criterion $\mathcal{C}$, Whole
training set $D_{\textit{tn}}$, Number of problematic data to return $k$

$\mathcal{C}$ is differentiable

$\cdots$

$L_{\textit{if}}\leftarrow\textit{argsort}(\textit{Influence},\textit{top}=k)$
$\triangleright$ Top low influences

$L_{\textit{cf}}\leftarrow\textit{argsort}(\textit{Confidence},\textit{top}=k)$

$H_{\textit{cf}}\leftarrow\textit{argsort}(\textit{Confidence},\textit{bottom}=k)$

$S_{1}\leftarrow L_{\textit{if}}\cap H_{\textit{cf}}$ $\triangleright$ Over-
confident

$S_{2}\leftarrow L_{\textit{if}}\cap L_{\textit{cf}}$ $\triangleright$ Over-
uncertain

$S_{3}\leftarrow L_{\textit{if}}\setminus(L_{\textit{cf}}\cup
H_{\textit{cf}})$ $\triangleright$ Other-noise

return $S_{1}$, $S_{2}$, $S_{3}$

When the performance criterion is ECE, running the above algorithm, we can
identify the three categories of data which negatively influence the
predictive uncertainty estimation of the model (increasing ECE).

Figure 9 shows our experiment results on the synthetic data. The data is
heavily corrupted two-moon synthetic data with 5000 data points. Among the
data points, 100 data points’ labels are randomly flipped. We run PUMA with
ECE loss as the performance metric $\mathcal{C}$ to debug the trained model on
the corrupted data. Results show that PUMA can fairly accurately identify the
various problems in the model (i.e. the three data categories). Note, unlike
the mislabelled data points, the identified over-confident and over-uncertain
predictions are part of the model problems, not a training data quality issue.
Hence, in Figure 9(b), the over-confident predictions are not symmetric in the
two classes for this particular model.

(a) Noisy Data

(b) Problem Highlight

Figure 9: Problematic data points discovered by PUMA. The problems are
categorized into three categories. For the prediction of mislabelled data
points, we show the prediction’s True Positive (TP), False Positive (FP), and
False Negative (FN).

(a) ECE Before Patching

(b) ECE After Patching

Figure 10: Expected Calibration Error (ECE) before and after PUMA model
patching/augmentation. For most of prediction confidence bins, we observe the
better calibration after PUMA model augmentation.

### Model Patching with PUMA

Now, if we set
$D_{\textit{mk}}\stackrel{{\scriptstyle\text{def}}}{{=}}S_{1}\cup S_{3}$ and
$D_{\textit{up}}\stackrel{{\scriptstyle\text{def}}}{{=}}S_{2}$ and run the
PUMA data removal algorithm (see Algorithm 1) with small learning rate $\eta$
(E.g. $\eta\leq 1e-4$), we expect to see that the ECE loss of the model is
reduced after updating the model with PUMA.

Figure 10 shows the model augmentation results. The results reflect our
expectation, since the ECE loss of the updated model is dramatically reduced.

## Appendix F: Discussion

### Purging Data vs. Data Characteristic Removal

Complete removal of data points from a trained model is barely possible since
the model training procedure is usually complex and it mixes information from
all training data points with mutual dependence. In particular, training
process of the modern deep learning often uses momentum-enabled optimization
algorithms to avoid getting stuck in a local minimum. This makes the
decomposition of the contribution of each training data point in learned model
parameters hard. In addition, approaches such as batch normalization and
weight decay could make the data contribution estimation even more
intractable. Hence, in this paper, we do not intend to completely purge the
effects of the training data points. Indeed, the only possible solution for
removing data from a model is probably retraining the model from scratch with
the remaining data points.

The main goal of this work is to remove the identifiable characteristics of
the marked data points such that 1) their negative impact on the model can be
mitigated and 2) the marked data points cannot be retrieved or identified by
the adversaries. The fundamental difference between our goal and
removing/purging data is that we want to keep the general properties of all
data points (including the marked ones) that are positively influential to the
model such that the model’s performance is preserved. This technique is
particularly useful when the models under service are required to respond
quickly to data removal requests, so that a full model retraining can be
conducted offline within certain period of time. Indeed, the immediate
response to data removal requests in online service is increasingly important.

### Privacy Protection vs Data Characteristic Removal

Privacy protection is a very important research field with many well defined
criteria. However, PUMA is not designed to satisfy those criteria (e.g.
information leakage (Hitaj, Ateniese, and Perez-Cruz 2017; Ateniese et al.
2015), re-identification attack (Yang et al. 2021), reconstruction attack (Lyu
and Chen 2021), tracing attack (Homer et al. 2008), model inversion
(Fredrikson, Jha, and Ristenpart 2015b)). Indeed, this paper does not aim to
solve privacy preservation problems. While we use the performance of the
membership attack as a metric in the paper, it is meant to show the
effectiveness of removing data characteristics only.

Actually, we note that PUMA could be used in various application scenarios
such as improving the prediction calibration of a model. As shown in previous
examples in Appendix E, by removing data which causes over-confidence and
upweighting over-uncertain data points optimally, PUMA can adjust a model’s
prediction uncertainty to fit calibration requirements in certain
applications. This application does not involve privacy protection but is very
useful for cascade models or multi-stage models, where outputs of upstream
models are expected to be well calibrated.


# Explainability in CNN Models by Means of Z-scores

###### Abstract

This paper explores the similarities of output layers in Neural Networks (NNs)
with logistic regression to explain importance of inputs by Z-scores. The
network analyzed, a network for fusion of Synthetic Aperture Radar (SAR) and
Microwave Radiometry (MWR) data, is applied to prediction of arctic sea ice.
With the analysis the importance of MWR relative to SAR is found to favor MWR
components. Further, as the model represents image features at different
scales, the relative importance of these are as well analyzed. The suggested
methodology offers a simple and easy framework for analyzing output layer
components and can reduce the number of components for further analysis with
e.g. common NN visualization methods.

Index Terms—  Convolutional Neural Networks, Z-scores, Logistic Regression,
Explainability

##  1 Introduction

Explainability of non-linear complex machine learning models such as Deep
Neural Networks remains a challenging time-consuming tasks with increasing
importance. As the use of these models spreads into new areas, explainability
becomes important to obtain new knowledge about scientific problems or to
understand ethical dilemmas that may arise when trusting the outcome without
understanding how it was reached.

In this work we study how to interpret a Convolutional Neural Network (CNN)
designed for Satellite Sensor Fusion. The aim is to exploit the statistical
similarities an output layer of a CNN shares with the corresponding linear
model from common statistical practices. The network in our experiments was
designed for prediction of sea ice in the Arctic. Currently, mapping of sea
ice is a manual discipline where ice analysts draw polygons on top of
Synthetic Aperture Radar (SAR) images and assign these polygons average ice
concentration intervals. The potential improvements for automating the time
consuming manual process of drawing these polygons, i.e. Ice Charts, lie in
larger and more frequent coverage, and increased consistency with less manual
labour. Automating the process on SAR data alone is challenging. SAR images
show patterns related to ice formations but back-scatter intensities can be
ambiguous between ice and open water. The model in this study tackles the
challenges by fusing SAR data from Sentinel-1 with Microwave Radiometer (MWR)
data from AMSR2 to exploit the advantages of each instrument. While SAR data
has ambiguities it has a very high resolution, where MWR data has good
contrast between open water and ice, the resolution is too poor for many
applications of sea ice mapping.

In the last layer of a CNN, several features are concatenated in the image
domain before a product-sum of a set of coefficients is passed through a
Sigmoid function to form probabilities of ice in a pixel in the image. This
process is similar to a logistic regression except for the CNN being optimized
by stochastic gradient descent in an end-to-end manner. Convolutional filters
that extract image features from the SAR data are learned simultaneously with
the coefficients in the mixing layer that combines the information with MWR
data. Interpreting these coefficients provides information on how the CNN
weights the importance of the inputs, which is exploited in this paper. This
methodology is further explained in Section 3.

##  2 Related Work

Interpretation and visualization of features and filters in CNNs were
pioneered by [1]. Since their work on analyzing which pixels in a given image
are important for the decision of a CNN, several improvements and new methods
have followed [2, 3, 4]. One of the biggest remaining challenges with CNNs and
Deep Learning is the lack of explainability and interpretation, as adressed in
[5]. In remote sensing less work has been done with model interpretation than
in general computer vision, and regarding fusion networks hardly any papers
have touched upon this subject. In [6], they mention this problem as to easily
be impressed by empirical improvements of Pan Sharpening and multi-spectral
fusion networks without any notion to the correctness of the spectral
information of the fused product. The authors in [6] propose a method to
control which information from the Panchromatic image band is used in the
fusion network.

As opposed to previous work in the field, this paper focuses on the
interpretability of the last layer in a satellite sensor fusion network. In
many CNN model architectures the last layer’s inputs consist of semantic
feature representations learned by the model. By knowing which inputs are
important one can deal with fewer nodes to interpret.

##  3 Model and Experiments

The model presented here extracts image features from the SAR images at four
different scales by means of an Atrous Spatial Pyramid Pooling, [7]. In the
networks last layer a linear mixing of feature inputs with MWR components
allows for a direct interpretation of what information is important in order
to predict sea ice.

As the SAR images and MWR data have very different resolutions, the model
applies a series of convolutions on the SAR data independently. In the second
to last layer a set of different features at different scales are extracted by
using different dilation rates in the convolutional filters. These are then
concatenated with upsampled AMSR2 brightness temperature measurements in order
to perform a pixel-wise linear combination that is passed through a sigmoid
function, see Figure 1.

Fig. 1: Model architecture of the sensor fusion model analyzed in this work.
The different scales are controlled by dilation rates i.e. scale 2 is dilation
rate equal 2. Before applying dilation filters the input is smoothed with a
average operation in a $dxd$ window with $d$ equal to the dilation rate.

Due to the resolution difference between AMSR2 and Sentinel-1 data of up to a
factor 268,000 (for 6.93GHz ASMR2 band wrt. area of footprint), it is
computationally unwise to perform equally many convolutions on the two input
sources. Therefore, this CNN processes the SAR input separately and merges it
with the coarser MWR at a later stage. The image feature scales are not
achieved by sub-sampling schemes but by the use of dilated convolutions with
four different dilation rates. One set of image features is extracted by skip-
connection from the output of the second convolution layer and is referred to
as Scale-0. This scale has also skipped all batch-normalization operations and
therefore retains a linear relationship to the original back-scatter values in
the Sentinel-1 image. Scales 2-16 have been processed by six convolutional
layers pair-wise interleaved with ReLU activations, Batch Normalization and
Dropout Regularization. This means the distribution of activation intensities
are normalized over batches of data inside the network.

The interesting property of this CNN architecture is that all inputs to the
last layer represent different information about the problem at hand. It is
relevant to know if Scale-0 is more important to the problem than Scale-16
which might have an insufficient resolution to capture edge information in the
ice charts. Another question, is what effect the MWR data has? MWR instruments
measure with far coarser resolution but have high contrast between open water
and ice, almost independent of wind and ocean current conditions.

As the output size of a convolution layer is an adjustable parameter, one can
also study what effect it has on the importance of a feature scale to increase
the size. This will be explored by two model variants, one with increased
sizes of output nodes in the feature Scales 2-16. Table 1 shows the sizes of
the inputs to the last CNN layer for the two model variants studied here.

Table 1: Input size of each input type for the two model variants. Inp. Type | Small | Large
---|---|---
Scale-0 | 14 | 14
Scale-2 | 14 | 28
Scale-4 | 14 | 28
Scale-8 | 14 | 28
Scale-16 | 14 | 28
AMSR2 | 14 | 14

Section 5 elaborates on the effect of the increased size of scale-feature
layers in the CNN on the balance between Sentinel-1 and between Sentinel-1 and
AMSR2 components.

##  4 Statistical Properties of Neural Networks

The last layer of a Neural Network trained with categorical cross-entropy,
i.e. image classification or per-pixel classification, resembles a logistic
regression since it is a linear combination of preceding layer’s outputs
parsed through a sigmoid function. In our case the last layer processes a
concatenation of ASMR2 channels with features extracted from the SAR image.
This allows for a straight forward comparison between the importance of the
two data sources. As typically done in logistic regression, coefficients can
be corrected with input standard deviation to provide Z-scores,

$Z_{i}=\frac{c_{i}}{\sigma_{i}/\sqrt{n}}$ (1)

where $c_{i}$ is the $i^{\prime}th$ coefficient and $\sigma_{i}$ the standard
deviation of the corresponding input that is multiplied with $c_{i}$. In
traditional statistical analysis one would correct for degrees of freedom by
the square root of the number of independent samples, $n$. In image analysis,
when considering pixels as samples one has to be careful not confusing the
number of pixels entering the analysis with independent samples. Pixels are
inherently spatially correlated to high extent. In our studies millions of
pixels has entered the analysis which would yield almost any coefficient
significant if considered independent samples. We therefore leave out the
correction for degrees of freedom and reduce Eq. 1 to,

$Z_{i}=\frac{c_{i}}{\sigma_{i}}$ (2)

This leaves out the study of significance while we can consider relative
importance of the different inputs instead.

##  5 Results

The coefficients studied in Figure 2(a) are from a model with 14 components in
each input group of the mixing layer. By input group we mean the six different
input groups, Scale-0, Scale-2, Scale-4, Scale-8, Scale-16 and AMSR2
brightness temperatures (b_temp) as shown in Figure 1. When the output layer
size, i.e. the number of components in each group of Scale-2 to Scale-16, is
increased we see a redistribution of relative importance only among the image
features, Figure 2(b).

(a) Small model.

(b) Large model.

Fig. 2: First 14 Z-scores in descending order of importance.

Generally, the relative importance of the AMSR2 brightness temperatures does
not change with change of the model size on the image feature side. Only very
few input channels change their order of importance and only slightly.

(a) Small model.

(b) Large model.

Fig. 3: Z-scores summed over input groups, i.e. MWR (btemp), scale-0, scale-2,
etc.

In Figure 3 Z-scores within each group are summed to show the overall
importance of each group.

##  6 Conclusion

For the task of sea ice prediction, it seems that the relative importance of
inputs favor the MWR data. This is not surprising as the ice charts that
represent the ground truth, to a large extent consists of homogeneous areas,
i.e. the edge pixels are relatively few compared to the total amount.

The size of the network had a small effect only on the relationship between
Z-scores associated with the image features and not on the relative importance
between image features and MWR inputs. The relationship between the different
image feature scales change slightly, see Figures 3(a) and 3(b), but the
single most important image feature remains to be from Scale-0. This is
interesting because it is likely to mean that the CNN uses coarse scale data
from MWR to predict overall homogeneous areas. Thereby, the image features
from the second CNN layer only provides edge and other higher resolution
information.

It was found during the experiments that the activation function on the mixing
layer affects the variance and thereby the estimation of Z-scores. The
commonly used Rectified Linear Unit function lead to ”dead” nodes in the Large
model, i.e. the variances of the respective output were zero. Instead a linear
activation function was used for these studies. It should also be noted that
the standard deviation of AMSR2 data should be calculated prior to the
upsampling, as it otherwise leads to extremely low estimates, i.e. very high
z-scores. Here, the AMSR2 inputs where normalized to zero mean and unit
variance prior to the model training and evaluation.

##  7 Acknowledgements

The authors would like thank our collaborators, at the Danish Meteorological
institute, Matilde Brandt Kreiner, Jørgen Buus-Hinkler, and from the Technical
Univeristy of Denmark Henning Skriver, Roberto Saldo and from Harnvig Arctic &
Maritime, Klaus Harnvig. Together in the danish research project ASIP
(Automated Sea Ice Products) we have prepared the dataset and developed the
models that were used for the statistical analysis of coefficients presented
here. The authors would also like to thank the Innovation Fund Denmark for the
financial support, Grant:7049-00008B, and the support of NVIDIA Corporation
with the donation of the GPU used for this research.

## References

  * [1] Matthew D Zeiler and Rob Fergus,  “Visualizing and understanding convolutional networks,”  in European conference on computer vision. Springer, 2014, pp. 818–833.
  * [2] Sebastian Bach, Alexander Binder, Grégoire Montavon, Frederick Klauschen, Klaus-Robert Müller, and Wojciech Samek,  “On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation,”  PloS one, vol. 10, no. 7, pp. e0130140, 2015.
  * [3] Bolei Zhou, Aditya Khosla, Aude Oliva, and Antonio Torralba,  “Object detectors emerge in deep scene CNNs,”  2015\.
  * [4] Bolei Zhou, David Bau, Aude Oliva, and Antonio Torralba,  “Interpreting deep visual representations via network dissection,”  IEEE transactions on pattern analysis and machine intelligence, 2018\.
  * [5] Yonina C Eldar, Alfred O Hero III, Li Deng, Jeff Fessler, Jelena Kovacevic, H Vincent Poor, and Steve Young,  “Challenges and open problems in signal processing: Panel discussion summary from ICASSP 2017 [panel and forum],”  IEEE Signal Processing Magazine, vol. 34, no. 6, pp. 8–23, 2017\.
  * [6] Tayeb Benzenati, Yousri Kessentini, Abdelaziz Kallel, and Hind Hallabia,  “Generalized laplacian pyramid pan-sharpening gain injection prediction based on cnn,”  IEEE Geoscience and Remote Sensing Letters, 2019.
  * [7] Liang-Chieh Chen, George Papandreou, Florian Schroff, and Hartwig Adam,  “Rethinking atrous convolution for semantic image segmentation,”  arXiv preprint arXiv:1706.05587, 2017.