# Learning to Limit Data Collection via Scaling Laws: A Computational
Interpretation for the Legal Principle of Data Minimization

Divya Shanmugam<EMAIL_ADDRESS>Massachusetts Institute of
TechnologyCambridgeMAUSA02139 ,  Samira Shabanian
<EMAIL_ADDRESS>Microsoft ResearchMontrealCanada ,  Fernando
Diaz<EMAIL_ADDRESS>Microsoft ResearchMontrealCanada ,  Michèle Finck
<EMAIL_ADDRESS>University of TübingenGermany and  Asia J. Biega
<EMAIL_ADDRESS>Max Planck Institute for Security and
PrivacyBochumGermany

(2022)

###### Abstract.

Modern machine learning systems are increasingly characterized by extensive
personal data collection, despite the diminishing returns and increasing
societal costs of such practices. Yet, data minimisation is one of the core
data protection principles enshrined in the European Union’s General Data
Protection Regulation (’GDPR’) and requires that only personal data that is
adequate, relevant and limited to what is necessary is processed. However, the
principle has seen limited adoption due to the lack of technical
interpretation.

In this work, we build on literature in machine learning and law to propose
FIDO, a Framework for Inhibiting Data Overcollection. FIDO learns to limit
data collection based on an interpretation of data minimization tied to system
performance. Concretely, FIDO provides a data collection stopping criterion by
iteratively updating an estimate of the _performance curve_ , or the
relationship between dataset size and performance, as data is acquired. FIDO
estimates the performance curve via a piecewise power law technique that
models distinct phases of an algorithm’s performance throughout data
collection _separately_. Empirical experiments show that the framework
produces accurate performance curves and data collection stopping criteria
across datasets and feature acquisition algorithms. We further demonstrate
that many other families of curves systematically _overestimate_ the return on
additional data. Results and analysis from our investigation offer deeper
insights into the relevant considerations when designing a data minimization
framework, including the impacts of active feature acquisition on individual
users and the feasability of user-specific data minimization. We conclude with
practical recommendations for the implementation of data minimization.

††journalyear: 2022††copyright: rightsretained††conference: 2022 ACM
Conference on Fairness, Accountability, and Transparency; June 21–24, 2022;
Seoul, Republic of Korea††booktitle: 2022 ACM Conference on Fairness,
Accountability, and Transparency (FAccT ’22), June 21–24, 2022, Seoul,
Republic of Korea††doi: 10.1145/3531146.3533148††isbn:
978-1-4503-9352-2/22/06††ccs: Social and professional topics Governmental
regulations††ccs: Applied computing Law††ccs: Computing methodologies Feature
selection††ccs: Computing methodologies Online learning settings

##  1\. Introduction

Data minimisation is a core principle of the European Union’s Data Protection
Regulation (GDPR, 2016), as well as data protection laws in other
jurisdictions:

> ”Personal data shall be: […] adequate, relevant and limited to what is
> necessary in relation to the purposes for which they are processed (data
> minimisation)”

The requirement serves as a guideline for respectfully processing data. Recent
empirical research has shown that it is possible to replicate the performance
of data-driven systems with significantly less data (Biega et al., 2020; Chow
et al., 2013; Vincent et al., 2019; Wen et al., 2018). These findings are a
consequence of the diminishing returns that data collection exhibits across
applications and domains (Hestness et al., 2017; Krause and Horvitz, 2010; Tae
and Whang, 2020). Recognizing that limiting data is possible, legal guidelines
point to algorithmic techniques that could be incorporated into minimization
pipelines, including feature selection (Binns and Gallo, 2019) or examination
of learning curves (Datatilsynet, 2018).

Yet, despite the existence of numerous algorithmic techniques that could be
adapted to comply with the minimization requirement, the data minimisation
principle has received little attention from the computer science community to
date. As noted by scholars reviving discussion about the principle, a dearth
of concrete mathematical definitions and guidelines is one of the main factors
inhibiting adoption (Biega and Finck, 2021). Indeed, qualitative research has
shown a lack of consistent data minimization standards or an understanding of
the principle among software developers (Senarath and Arachchilage, 2018).

Recent interpretations of data minimization propose to tie the data collection
purpose in data-driven systems to performance metrics, an interpretation
termed _performance-based data minimization_ (Biega and Finck, 2021; Biega et
al., 2020). Our work follows this interpretation, addressing the question of
_how to proactively satisfy the performance-based data minimization principle
in machine learning with personal data_.

Contributions. In this work, we propose FIDO, a Framework for Inhibiting Data
Overcollection, and demonstrate how ongoing personal data collection could be
approached in the context of data minimization.

FIDO’s key conceptual proposal is to _adaptively learn an algorithm’s
performance curve_ so that an _appropriate data collection stopping point_ can
be determined accurately. By modeling the performance curve directly, the
framework remains flexible to different underlying feature acquisition
algorithms and definitions of performance. Experiments involving multiple
datasets in the recommender systems domain validate this flexibility and
demonstrate FIDO’s ability to estimate algorithm performance given additional
data accurately _without_ collecting more data.

The core technical insight FIDO contributes lies in its performance curve
estimation procedure, which builds on recent work in machine learning
literature that identifies three distinct phases in the performance curves of
learning algorithms: the small data phase, the power law phase, and the
diminishing returns phase (Hestness et al., 2017). We demonstrate that these
performance phases can be observed in the context of user data collection and
provide a technique to model the data collection phases directly by adaptively
learning a piecewise power law curve. Empirical experiments show that other
approaches to estimate performance curves systematically _overestimate_ the
return on additional data. Modeling each phase directly allows FIDO to not
only learn the performance curve more accurately as data is acquired but also
satisfy practical constraints of data minimization.

Finally, we examine issues related to user-level data minimization. We
demonstrate the impacts that algorithmic components such as active feature
acquisition (a technique to intelligently select which feature values to
acquire) might have on minimization outcomes. We find that active feature
acquisition can lead to unequal, concentrated data collection from a small set
of users, in addition to decreased minimization performance for evolving user
communities or when sensitive features are excluded from initial data
collection. We also find that user-specific performance curves are highly
variable, where the collection of more data can often result in a _decrease_
in user-specific performance.

This paper seeks to offer a computational perspective on the GDPR’s principle
of data minimization, contributing insights to the ongoing discussions about
the technical implementation of this core data protection principle, and to
provide recommendations to practitioners and scholars moving forward.

##  2\. Legal Background

Data minimization is one of the core principles of European data protection
law. In recent years, many have questioned its suitability in face of
technical advances based on the repurposing of large quantities of data(Koops,
[n.d.]). Some indeed fear that adherence to the principle ‘would sacrifice
considerable social benefit’ as it may limit the innovative potential of
machine learning (MacCarthy, 2018). Even so, data minimization remains one of
the principles that ought to be respected regardless of the specific context
of personal data processing. Controversies around the principle will continue
as the adoption of the draft Data Governance and Data Acts would force
discussions as to how to reconcile related legislative incentives to process
more (personal) data with data minimization. In this paper, we discuss whether
it is at all possible to reconcile data minimization with machine learning.

Article 5(1)(c) GDPR provides that data shall be ‘adequate, relevant and
limited to what is necessary in relation to the purposes for which they are
processed’. Article 25(2) GDPR reiterates that controllers only process
personal data ‘necessary for each specific purpose of the processing’. First,
the data processed must be ‘relevant’, meaning that only pertinent data ought
to be processed. This is designed to safeguard against the accumulation of
data for the sake of gathering more data for undisclosed ends and stands in
tension with the contemporary operation of ML systems, which often re-purpose
data. Second, data can only be processed where it is adequate. Although this
requirement is closely intertwined with relevance, adequacy is different in
that it may sometimes require that more, not less, data is processed, such as
where existing data is inadequate to draw inferences about demographic groups
underrepresented in a dataset. Third, only necessary data ought to be
processed, meaning that data controllers need to identify the minimum amount
of data necessary to fulfill the purpose (Biega and Finck, 2021). Beyond,
there remain unresolved questions regarding the interpretation of data
minimization, such as whether data minimization also requires the
pseudonymisation of personal data and whether it implies that preference
should be given to ordinary personal data over sensitive data (Biega and
Finck, 2021). Either way, it is worth pointing out that compliance with data
minimization can also enhance the quality of ML as there is less need to clean
the data and less risk of inaccuracy (Datatilsynet, 2018).

Data minimization in data-driven systems has been hindered by the lack of
concrete computational formalizations, as the principle has received less
academic attention in the computing community compared to fairness or
transparency. While legal requirements leave room for interpretation,
regulatory bodies then issue more specific guidelines to help translate these
requirements into practice (guidelines for the implementation of data
minimization in Machine Learning and Artificial Intelligence have been issued
by the data protection authorities in the UK (Binns and Gallo, 2019; ICO,
2018b, a) or Norway (Datatilsynet, 2018)). Often, these guidelines mention
potential techniques or implementation directions but are still not concrete
enough to offer specific mathematical definitions or algorithms (which may
lead to vastly varying implementations in practice (Senarath and Arachchilage,
2018)). The paper addresses this gap, exploring the feasibility of an
interpretation based on algorithmic performance curves.

##  3\. Related Work

Ideas related to the legal concept of data minimization exist across fields in
machine learning. We discuss past work on data minimization and performance
curves below, and expand on intersections with the literature on sample
complexity and active feature acquisition in the supplementary material.

###  3.1. Perspectives on Data Minimization.

Our work follows a number of recent efforts to formalize the principle of data
minimization. Biega et al. (2020) propose an interpretation of data
minimization that ties data collection purpose to system performance and
discuss the feasability of data minimization in recommendation systems. Our
work deepens this interpretation, noting that past work on privacy by design
highlights data collection as a key area to implement data minimization. More
specifically, we propose a learning-based framework to enforce a data
collection stopping criterion, in addition to novel definitions of stopping
criteria related to the returns on additional data, rather than absolute model
performance.

Existing guidelines distinguish between _breadth-based_ data minimization and
_depth-based data minimization_ (Authority, 2018). In the former, one aims to
minimize the number of features, while the latter concerns minimizing the
overall amount of data collected for one data modality. Rastegarpanah et al.
(2021) study breadth-based data minimization and propose an audit method that
uses feature imputation to identify whether the features used for a given
model are necessary to preserve predictive performance to a pre-specified
degree. Goldsteen et al. (2021) also address breadth-based data minimization
by identifying how to best generalize features during inference, using ideas
from knowledge distillation and data anonymization. In contrast, FIDO is a
depth-based data minimization framework meant to guide data collection during
model training.

While it has been shown empirically that data can be minimized through various
domain- and algorithm-specific heuristics (Biega et al., 2020), a question
remains of how to automatically learn when to stop data collection for various
personalization systems and feature acquisition strategies; the remainder of
this paper focuses on this problem. For a thorough treatment of the harms data
minimization protects against, we refer the interested reader to Biega and
Finck (2021).

###  3.2. Performance Curves.

Our approach is closely related to empirical research on performance curve
estimation, which examines the relationship between dataset size and model
performance. The literature considers many metrics, including sensitivity
(Hajian-Tilaki, 2014), error rates (Gürses et al., 2015), accuracy (Cho et
al., 2015; Kolachina et al., 2012), and confidence (Dobbin et al., 2008;
Kalayeh and Landgrebe, 1983). While these works typically assume a power law
relationship, alternatives have been considered and shown to be comparable in
accuracy (Domhan et al., 2015; Kolachina et al., 2012).

Tae and Whang (2020) propose a data collection framework most closely related
to ours. They use performance curves to identify classes which require more
data to achieve equitable error rates. Tae and Whang (2020) assume a power law
relationship throughout the data collection process. In contrast, we model
regions of the performance curve separately, and most importantly, use the
performance curve to _identify a data collection stopping point_.

Literature on learning curves—the relationship between training epochs and
model performance—is related to our own, but aims to learn curves that are
generalizable across model configurations or hyperparameter sets. Thus, the
methods assume access to hundreds of architectures (Baker et al., 2017) or
multiple datasets (Wistuba and Pedapati, 2020) and depart from our setting. We
include a nonparametric baseline inspired by this work in the supplementary
material and find that the resulting performance curves are insufficient for
achieving data minimization criteria.

##  4\. Problem Formalization

The key proposal in this paper is to maximally limit data collection given a
target performance using _performance curves_. We plot the true performance
curves for the GoogleLocal-L dataset (Pasricha and McAuley, 2018) and
MovieLens-20M dataset (Harper and Konstan, 2015) and contrast these to the
three phases of data collection identified by Hestness et al. (2017) (Fig. 1
left, courtesy of Hestness et al. (2017)). The phases are:

  1. (1)

_The small data region_ , where the collected data is insufficiently
representative and model performance is poor.

  2. (2)

_The power-law region_ , where there is a direct trade-off between the amount
of data collected and performance.

  3. (3)

_The irreducible error/diminishing returns region_ , where the collection of
more data does not lead to model improvement.

Figure 1. Model performance over the course of data collection. On the left, a
figure from Hestness et al. (2017) plots the phases of data collection. On the
right, we plot model performance over data collection from GoogleLocal and
MovieLens-20M. Note the change in slope over the course of data collection; we
see for both GoogleLocal and MovieLens-20M, the return on additional data
decreases, in line with current understanding of the diminishing returns
region. Preprocessing details for each dataset can be found in the
supplementary material.

The figure is a three panel figure, where the first panel represents the
theoretical relationship between dataset size and performance, and the other
panels are validation of this relationship on two popular recommendation
datasets. On the left, the curve is flat at the beginning, steep in the
middle, and flat again at the end. These phases of the performance curve
correspond to different stages of data collection, labeled as the “small data
region”, the “power-law region” and the “irreducible error region. On the
right, we see each of these phases occur over the course of data collection on
MovieLens (middle) and GoogleLocal (right).

We can make two observations from Figure 1. The first is that the phases of
data collection identified by Hestness et al. (2017) in machine translation
exist for recommendation datasets. This is true for both GoogleLocal and
MovieLens. The second observation is that a mere 10% of the dataset lands data
collection outside of the small data region. A majority of data collection
occurs between the power law region and the diminishing returns region. This
has important implications for modeling the performance curve: modeling the
entire region using one power law curve produces underestimates of the
predicted generalization error given additional data. In later sections, we
show that modeling each phase separately mitigates this effect.

From a practical perspective, the data collection phases could be used to
decide when collecting more data is necessary for reliable model performance
(the small data region), when a user should opt to trade more data for better
performance (the power-law region), and when data collection should stop (the
irreducible error, or diminishing returns region).

The distinction of these phases is also pertinent from a legal perspective. In
particular, the application of data minimization’s necessity criterion would
indicate that continued collection of personal data in the third phase would
be hard to justify as it is not “necessary” to improve the model and meet its
underlying purpose. We formalize these implications into a formal stopping
criterion based on an empirical derivative of the the learned performance
curve.

###  4.1. Formal Interpretation.

We follow a recent interpretation that ties data collection to _model
performance metrics_ (Biega et al., 2020). However, operationalizing this
interpretation remains unclear. We propose a formalization based on the
returns in performance from additional data.

####  4.1.1. Scenario and Notation.

We assume a scenario where a data processor operates a service (a model $M$,
such as a recommender system) and collects data from a pool of queryable data
$\mathcal{P}$ (consisting of user-feature-value triples) generated by a
population of users $\mathcal{U}$. We define $M$ as the collection of
parameters learned using personal data, including hyperparameters.

The acquired data is used to train $M$ and make predictions for each user
$u\in\mathcal{U}$. We further assume that, when data collection begins, the
data processor has access to some initial data: $\mathcal{I}$ for training the
model and $\mathcal{V}$ set aside to validate model performance predictions.
Such initial data would include any data that is historical, purchased, or
collected in different markets.

During data collection, the processor applies a feature acquisition policy
$H(\mathcal{P},n)$ which queries $n$ feature values from $\mathcal{P}$.
Queries equate to the collection of a specific user-feature-value for
inclusion in the training set for model $M$. We refer to the union of initial
and acquired data as $\mathcal{A}$ and let $|\cdot|$ denote the cardinality of
a set. Let $\sigma_{M}$ represent the true performance curve for $M$, which
maps a domain of training dataset sizes to a range of model performances as
measured by a performance metric $\sigma$. User-specific performance curves
for $M$ are termed $\sigma_{M}^{u}$ for a given user $u$. The objective used
to train $M$ translates to the processing purpose.

The processor can use the resulting predicted performance curve to adhere to a
concrete data minimization objective. In the main text, we propose and
validate one such objective, detailed below: _returns-based_ data
minimization. Experiments in the supplementary material furthermore engage an
alternate formalization of data minimization, where the stopping criterion is
determined by the _relative model performance_ achieved rather than the
performance returns, providing further evidence of FIDO’s flexibility.

####  4.1.2. Minimizing by Returns in Performance.

We minimize in reference to a threshold on the return in model performance of
additional data. One could select an appropriate threshold by assessing user
preferences or selecting a sufficiently small threshold such that user
experience is not affected. Formally, a data collector would cease data
collection once the slope of the performance curve drops below threshold $t$:

(1) $\frac{d\sigma_{M}}{dn}(|\mathcal{A}|)\leq t$

Producing an accurate approximation of $\sigma_{M}$ is thus central to any
performance-based data minimization objective. Our experiments show that
existing approaches produce performance curves that are insufficient for the
stated objectives. We compensate for these shortcomings by providing an
accurate parametric model to approximate $\sigma_{M}$.

##  5\. FIDO: Framework for Inhibiting Data Overcollection

The framework accepts three parameters: feature acquisition algorithm $H$,
model $M$, and performance metric $\sigma$. There are three steps: (1) $H$
acquires a portion of the available data (_Data Collection_), (2) the
performance curve is fit to the new data (_Curve Fitting_), and (3) Steps 1
and 2 repeat until the conditions of Step 3 (_Stopping Criterion Evaluation_)
are met.

###  5.1. Step 1: Collect Data.

In this step, a feature acquisition algorithm $H$ collects $q$ observations
from the pool of available observations $\mathcal{P}$. Smaller $q$ translate
to more conservative data collection processes and to more accurate estimates
of the stopping criterion at the expense of decreased efficiency (smaller $q$
mean that Steps 2 and 3 are executed more frequently). One might choose to set
a larger $q$ early on during data processing, and decrease it as the data
processing continues.

###  5.2. Step 2: Fit the Performance Curve.

The key idea underpinning this step is to model the phases of data collection
separately via a piecewise power law curve. The piecewise power law curve is
the piece-wise combination of three power law curves, which we will refer to
as $f_{0}$, $f_{1}$, and $f_{2}$:

(2) $f(x)=\begin{cases}f_{0}(x)=a_{0}x^{-b_{0}}&0\leq x\leq t_{0}\\\
f_{1}(x)=a_{1}x^{-b_{1}}&t_{0}<x\leq t_{1}\\\
f_{2}(x)=a_{2}x^{-b_{2}}&t_{1}<x\\\ \end{cases}$

where $f(x)$ accepts as input a training set size $x$. We fit the piecewise
power law curve to subsamples of $\mathcal{A}$ of different sizes. More
specifically, given the query size parameter $q$, we generate
$|\mathcal{A}|/q$ samples such that the size of each consecutive sample
increases by $q$. We train the model on each sample and evaluate model
performance on $\mathcal{V}$. The resulting pairs of values (sample size and
performance on the validation set) are then used to fit $f(x)$. We fit the
parameters for $f_{0}$, $f_{1}$, and $f_{2}$ using weighted non-linear least
squares; details can be found in the supplementary material.

Finally, we optimize thresholds $t_{0}$ and $t_{1}$ using coordinate descent,
such that the _slopes_ of each consecutive pair of power laws maximally
differ. This translates to an iterative approach that first estimates $t_{0}$
while $t_{1}$ is left fixed, and then estimates $t_{1}$ while $t_{0}$ is
fixed, until convergence. More formally, we alternate optimization between the
following objectives:

(3) $\displaystyle\max_{t_{0}}\quad|b_{0}-b_{1}|\quad$ $\displaystyle s.t.$
$\displaystyle\quad 0<t_{0}<t_{1}$ (4)
$\displaystyle\max_{t_{1}}\quad|b_{1}-b_{2}|\quad$ $\displaystyle s.t.$
$\displaystyle\quad t_{0}<t_{1}<|\mathcal{A}|$

While $t_{0}$ and $t_{1}$ do not appear directly in the optimization
objective, they impact the estimates of $b_{0}$, $b_{1}$, and $b_{2}$ by
delimiting which sample size and model performance pairs are used to estimate
each decay parameter (as described in Equation (2)). Assuming the underlying
function is a piecewise power law curve, Equations (3) and (4) are convex
optimizations and converge to the correct thresholds.

This follows our intuition regarding the each region: namely, that the phases
are distinguished by the differing _return_ in additional data. Note that in
this paper we assume that model performance increases as we collect more data.
This is a common assumption in the performance curve literature (Kolachina et
al., 2012; Hestness et al., 2017), but there are cases in which additional
data may hurt model performance. We discuss one such case in Section 6.3.2. In
these settings, a different family of parametric curves should be used and
FIDO remains flexible to alternate performance curve estimation procedures.

In theory, one could compute a stopping criterion directly from the subsamples
of $\mathcal{A}$, without fitting the performance curve. This has two
undesirable consequences. The first is the instability of the resulting
stopping criteria, due to the noise inherent to performance measurements from
individual subsamples, as we will see in later experiments. Second, learning a
performance curve allows the data minimizer to reason about performance given
additional data, _without collecting that data_. This affords the framework
flexibility to a range of data minimization objectives, including those that
cease data collection based on absolute model performance rather than
performance increase rate (relevant experiments are in the supplement).

###  5.3. Step 3: Evaluate Stopping Criterion.

In this step, the resulting performance curve is used to accomplish a specific
data minimization objective. Note that these are not the only reasonable data
minimization objectives and the framework can adapt to different formulations.

Minimizing by returns requires the data collector to specify a threshold for
return after which data collection should stop, $t\in\mathbb{R}$. We can use
the performance curves to estimate this quantity by taking the derivative at a
given sample size:

(5) $\hat{s}=\begin{cases}-b_{0}a_{0}x^{-b_{0}-1}&0\leq x\leq t_{0}\\\
-b_{1}a_{1}x^{-b_{1}-1}&t_{0}<x\leq t_{1}\\\
-b_{2}a_{1}x^{-b_{2}-1}&t_{1}<x\\\ \end{cases}$

Once $\hat{s}$ falls below $t$, data collection stops. Implementation details
are in the supplementary material.

##  6\. Experiments

Dataset | # Users | # Items | Item type | Sparsity
---|---|---|---|---
MovieLens-L | 5000 | 17400 | movie | 1.7%
MovieLens-S | 1000 | 11529 | movie | 2.6%
GoogleLocal-L | 1500 | 265807 | business | 0.1%
GoogleLocal-S | 500 | 104766 | business | 0.3%

Table 1. Dataset statistics.

####  6.0.1. Datasets.

We perform experiments on two datasets in the recommender system domain:
MovieLens-20M (Harper and Konstan, 2015) and GoogleLocal (He et al., 2017;
Pasricha and McAuley, 2018). The datasets contain user ratings for movies and
businesses, respectively. For each, the task is to predict user ratings for
unseen items. We sample each dataset at two sizes to examine how results
generalize across user numbers and sparsity levels. Dataset statistics can be
found in Table 1 and preprocessing pipelines can be found in the supplementary
material.

Each dataset is subject to the same initial, validation, and test splits,
where each split is 10% of the total ratings and stratified across users. The
remaining 70% of the data is the queryable rating set $\mathcal{P}$. We
produce 5 random splits of each dataset according to these divisions. All
results are reported over the 5 splits. We assume random feature acquisition
unless otherwise stated.

####  6.0.2. Alternate Curve Models.

Methods relating dataset size to performance commonly assume a power law model
(Hestness et al., 2017; Tae and Whang, 2020). We benchmark FIDO’s piecewise
power law technique against alternate approaches in the literature. We include
2P-PL-Initial to determine the benefit of updating the curve as data is
acquired, and a two-parameter power law method 2P-PL to represent the most
common approach to fitting performance curves (Tae and Whang, 2020; Figueroa
et al., 2012). The remaining baselines represent variations of the power law
curve that capture the notion of diminishing returns. The first (3P-PL) models
the irreducible error directly and the second (3P-PL-Exp) models an additional
exponential decay. The parameter fitting approach is the same for our method
and described in the supplementary material.

  * •

2P-PL-Initial: Fits two-parameter power law ($f(x)=ax^{b}$) to subsamples of
$\mathcal{I}$.

  * •

2P-PL: Fits two-parameter power law ($f(x)=ax^{b}$) to subsamples of
$\mathcal{A}$.

  * •

3P-PL: Fits three-parameter power law ($f(x)=ax^{b}+c$) to subsamples of
$\mathcal{A}$.

  * •

3P-PL-Exp: Fits three-parameter power law with an exponential cutoff
($f(x)=x^{a}e^{bx}+c$) to subsamples of $\mathcal{A}$.

  * •

Naive: Estimates slope of the performance curve empirically via last two
subsamples of $\mathcal{A}$.

  * •

Oracle: Estimates slope via a discrete approximation using _all_ sample size
and performance pairs. Exact implementation is in the supplementary material.

We include comparisons to two additional baselines—a variant of the proposed
curve model with two pieces (for the power law curve stage and diminishing
returns stage) rather than three, and a nonparametric regression model—in the
supplementary material.

####  6.0.3. Hyperparameters.

We assume that $M$ is a FunkSVD (Funk, 2006) recommendation system. We use the
same hyperparameters for the number of latent features $r$ and query size $q$
across all experiments: $r$ is set to be 30, and $q$ is set to be 2% of the
number of queryable entries.

####  6.0.4. Metrics.

We measure performance via mean-squared error (MSE), a standard recommendation
evaluation metric. Methods are compared based on (1) return given additional
data (change in MSE per additional feature-value observation) and (2) the
amount of data collected for a given threshold $t$ (reported over 5 dataset
splits). We compute statistical significance via a paired $t$-test with a
Bonferroni correction.

###  6.1. Evaluation of Data Minimization Objective.

We compare the amount of data collected by FIDO using a suite of performance
curve models, including the piecewise power law technique described in Section
5.2, to the amount of data collected by an oracle with access to _all_ sample
size and performance pairs. For a variety of thresholds, FIDO paired with the
piecewise power law technique halts data collection significantly closer to a
criterion with access to all sample size and performance estimates (Table 2,
$p$ ¡ 1e-5). Due to the noise of the performance measurements, _Naive_
produces stopping criteria that are both noisier and further from the true
stopping point. Later experiments show that _Naive_ fails to generalize to
different feature acquisition algorithms and cannot accommodate alternate
performance-based data minimization objectives.

The slope estimates drawn from the performance curve in FIDO are more accurate
than those of the curve-fitting baselines across the stages of data collection
(Figure 2 (A)). _3P-PL-Exp_ consistently underestimates the return on
additional data over the course of data collection, and subsequently halts
data collection too early. In contrast, _2P-PL-Initial_ , _2P-PL_ , and
_3P-PL_ overestimate the return on additional data and frequently halt data
collection later than the empirically derived stopping point. These results
suggest that the use of _3P-PL-Exp_ would produce a conservative data
minimization approach in that such a data minimization method would be
unlikely to over-collect data. The reverse is true for the remaining baselines
– such a data minimization approach would likely collect more data than is
required.

This is a direct result of each curve model’s ability to model the last stage
of data collection accurately. Examine the accuracy of each curve model’s
estimate of performance given the entire dataset (Figure 2 (B)). Each method
converges to the true value for model performance (red) over the course of
data collection. The power law baselines (_2P-PL-Initial_ , _2P-PL_ , _3P-PL_)
underestimate error given $\mathcal{P}$. This confirms results from prior work
in machine translation (Kolachina et al., 2012), and is a consequence of
extrapolation from the power law region into the diminishing returns region.
_3P-PL-Exp_ instead overestimates test error because the $e^{-bx}$ term
produces a curve too flat to describe the true relationship; illustrative
plots for the performance curve fits are included in the supplementary
material.

The halting points for GoogleLocal-S and MovieLens-S exhibit more noise than
their larger counterparts. This suggests that producing reliable estimates of
the return on additional data is more challenging for smaller datasets.

Figure 2. Evaluation of performance curves over the course of data collection.
Our method outperforms baselines in estimating _return_ on additional data,
where return is defined as the reduction in model error given an additional
feature-value observation (A). Supporting plots for GoogleLocal-S and
MovieLens-S are in the supplementary material. For each dataset, we plot
predicted performance, $\sigma_{M}{(|\mathcal{I}\cup\mathcal{P}|)}$, over the
course of data collection using different curve-fitting methods (B). Our
method (dark green) matches the true performance (red) most closely at all
stages.

The figure has four panels, where the left two panels plot the relationship
between dataset size and estimated return on additional data and the two
panels on the right plot estimated performance given additional data. The
baselines are plotted in different colors on each graph. Over both estimation
tasks, FIDO combined with a piecewise power law curve achieves the highest
accuracy.

Dataset | Threshold | 2P-PL-Initial | 2P-PL | 3P-PL | 3P-PL-Exp | Naive | FIDO | Oracle
---|---|---|---|---|---|---|---|---
GoogleLocal-L | -5.0e-07 | $0.32\pm 0.00$ | $0.32\pm 0.01$ | $0.32\pm 0.01$ | $0.16\pm 0.00$ | $\mathbf{0.27\pm 0.02}$ | $\mathbf{0.29\pm 0.02}$ | $0.27\pm 0.01$
GoogleLocal-L | -2.0e-07 | $0.73\pm 0.01$ | $0.61\pm 0.01$ | $0.53\pm 0.01$ | $0.25\pm 0.01$ | $0.36\pm 0.04$ | $\mathbf{0.42\pm 0.03}$ | $0.41\pm 0.02$
GoogleLocal-L | -5.0e-08 | $1.00\pm 0.00$ | $1.00\pm 0.00$ | $1.00\pm 0.00$ | $0.40\pm 0.02$ | $0.52\pm 0.08$ | $\mathbf{0.68\pm 0.05}$ | $0.68\pm 0.05$
GoogleLocal-S | -5.0e-07 | $0.88\pm 0.01$ | $0.71\pm 0.01$ | $0.60\pm 0.01$ | $0.28\pm 0.01$ | $0.37\pm 0.07$ | $\mathbf{0.42\pm 0.06}$ | $0.47\pm 0.03$
GoogleLocal-S | -2.0e-07 | $1.00\pm 0.00$ | $1.00\pm 0.00$ | $0.91\pm 0.03$ | $0.39\pm 0.01$ | $0.44\pm 0.08$ | $\mathbf{0.51\pm 0.14}$ | $0.58\pm 0.06$
GoogleLocal-S | -5.0e-08 | $1.00\pm 0.00$ | $1.00\pm 0.00$ | $1.00\pm 0.00$ | $\mathbf{0.55\pm 0.01}$ | $0.46\pm 0.09$ | $\mathbf{0.59\pm 0.08}$ | $0.64\pm 0.10$
MovieLens-L | -5.0e-07 | $0.13\pm 0.00$ | $0.13\pm 0.00$ | $0.13\pm 0.00$ | $0.13\pm 0.00$ | $\mathbf{0.14\pm 0.01}$ | $\mathbf{0.13\pm 0.00}$ | $0.13\pm 0.00$
MovieLens-L | -2.0e-07 | $0.29\pm 0.00$ | $0.27\pm 0.00$ | $0.26\pm 0.00$ | $0.13\pm 0.00$ | $\mathbf{0.25\pm 0.01}$ | $\mathbf{0.25\pm 0.02}$ | $0.23\pm 0.01$
MovieLens-L | -5.0e-08 | $1.00\pm 0.00$ | $0.76\pm 0.01$ | $0.62\pm 0.01$ | $0.24\pm 0.01$ | $0.43\pm 0.08$ | $\mathbf{0.53\pm 0.05}$ | $0.53\pm 0.02$
MovieLens-S | -5.0e-07 | $0.50\pm 0.02$ | $0.53\pm 0.01$ | $0.51\pm 0.01$ | $0.23\pm 0.01$ | $\mathbf{0.37\pm 0.04}$ | $\mathbf{0.46\pm 0.05}$ | $0.45\pm 0.03$
MovieLens-S | -2.0e-07 | $1.00\pm 0.00$ | $1.00\pm 0.00$ | $0.97\pm 0.02$ | $0.36\pm 0.01$ | $0.51\pm 0.08$ | $\mathbf{0.68\pm 0.14}$ | $0.79\pm 0.08$
MovieLens-S | -5.0e-08 | $1.00\pm 0.00$ | $1.00\pm 0.00$ | $1.00\pm 0.00$ | $0.64\pm 0.02$ | $0.66\pm 0.22$ | $\mathbf{0.99\pm 0.03}$ | $1.00\pm 0.00$

Table 2. Performance over diminishing returns criterion. Each value is the
fraction of data collected using a given method while adhering to the
diminishing returns stopping criterion, averaged over 5 runs. Our method halts
collection closest to the true stopping point across thresholds (p-value
3e-6). Bolded entries are closest to the true stopping point, within a
standard deviation.

###  6.2. Robustness to Query Size.

In the previous experiments we used a query size of 2%. Here, we investigate
the robustness of FIDO’s predictions to different query size values
$q\in[0.005,0.01,0.02,0.03,0.04,0.05,0.06,0.07]$. Large $q$ simulate a setting
in which large batches of data are acquired at one time, while smaller $q$
simulate the continuous arrival of new user data.

Table 3 reports that FIDO provides the closest estimation of the true model
performance across different query sizes. While FIDO produces the most
faithful estimates of the true stopping point across query sizes _it is more
sensitive to small query sizes_ compared to baselines using a single power law
curve. Lower query sizes require models to be retrained more frequently to
produce data to fit the performance curve. Thus, for models with
computationally intensive training procedures, it is optimal to choose the
largest query size that maintains accuracy. On the other hand, smaller queries
will lead to more accurate stopping decisions and less data overcollection. It
is up to a practitioner to select the query size based on their domain
knowledge, and our results suggest that the set of query sizes producing
accurate estimates is quite large.

###  6.3. Robustness to Feature Acquisition Algorithms.

Thus far, we have considered data collection where observations are queried
randomly from $\mathcal{Q}$. AFA methods improve upon this approach by instead
querying feature values based on their uncertainty (Huang et al., 2018; Freund
et al., 1997; Chakraborty et al., 2013) or contribution to a downstream task
(Melville et al., 2005; Vu et al., 2007). Successful AFA methods collect less
data than random feature acquisition and deliver equivalent performance.
Recent work has shown that this success is often dependent on initialization
conditions (Munjal et al., 2020).

We consider two popular AFA methods: Stability and Query-by-Committee (_QBC_).
QBC (Chakraborty et al., 2013) employs three matrix imputation approaches
($k$-NN, EM, and SVD) to predict missing feature values. _Stability_ takes a
similar approach and predicts missing feature-values using SVD given different
ranks. Each feature-value’s uncertainty corresponds to the variance in
predicted values. Both algorithms request the highest variance feature-values.
For Stability, we follow the approach of (Huang et al., 2018) and set the
ranks to be $[1,2,3,4,5]$.

####  6.3.1. FIDO is robust to different AFA algorithms.

Across both AFA algorithms and multiple thresholds, FIDO halts data collection
closest to the true stopping point ($p$ ¡1e-3). Table 4 reports these results
for GoogleLocal-L. Expectedly, we see that for the same stopping criterion
(e.g., a threshold of -5.0e-7), AFA algorithms collect less data than random
feature acquisition algorithms. Existing curve-fitting approaches are more
competitive in the AFA setting, which can be attributed to an expanded power
law region (illustrative performance curves can be found in the supplementary
material.

In general, trends for each baseline hold in this setting: the curve models
which use a single power law (_2P-PL-Initial_ , _2P-PL_ , _3P-PL_) stop
collecting data too late on average, while _3P-PL-Exp_ stops collecting data
too early. _Naive_ is naturally affected by the noisier performance curves and
performs significantly worse than the other methods.

####  6.3.2. AFA algorithm performance depends on initial system data

In Figure 3(A) we examine the dependence of AFA algorithm performance on (1)
the type of initialized data and (2) the feature acquisition algorithm
employed. We consider two additional types of initialization; user-subset
(initialized randomly across a subset of users) and item-subset (initialized
randomly across subset of items). In each of these cases, the test set is
formed from a random sample that includes ratings from all users. In agreement
with Munjal et al. (2020), we observe that the performance depends on data
initialization conditions. When the initialization data is a random sample
across users and items, AFA algorithms perform similarly. However, when the
initialization data contains only a subset of users, or only a subset of
items, AFA begins to decrease in performance. This is consequential in cases
where (i) the population of data subjects is evolving (initialization data
does not contain users who join at a later time), and (ii) the data processor
is not initially allowed to collect certain feature values because of external
constraints (e.g., feature sensitivity).

Query Size | Threshold | 2P-PL-Initial | 2P-PL | 3P-PL | 3P-PL-Exp | Naive | FIDO | Oracle
---|---|---|---|---|---|---|---|---
0.005 | -2.0e-07 | $0.70\pm 0.01$ | $0.62\pm 0.01$ | $0.55\pm 0.01$ | $0.21\pm 0.00$ | $0.24\pm 0.04$ | $0.30\pm 0.04$ | $0.35\pm 0.01$
0.010 | -2.0e-07 | $0.71\pm 0.01$ | $0.62\pm 0.01$ | $0.55\pm 0.01$ | $0.22\pm 0.00$ | $0.32\pm 0.05$ | $0.36\pm 0.02$ | $0.39\pm 0.03$
0.020 | -2.0e-07 | $0.73\pm 0.01$ | $0.62\pm 0.01$ | $0.53\pm 0.01$ | $0.25\pm 0.00$ | $0.39\pm 0.03$ | $0.41\pm 0.03$ | $0.42\pm 0.02$
0.030 | -2.0e-07 | $0.75\pm 0.02$ | $0.63\pm 0.02$ | $0.53\pm 0.02$ | $0.27\pm 0.01$ | $0.43\pm 0.02$ | $0.46\pm 0.02$ | $0.43\pm 0.01$
0.040 | -2.0e-07 | $0.79\pm 0.03$ | $0.64\pm 0.02$ | $0.53\pm 0.02$ | $0.29\pm 0.00$ | $0.44\pm 0.02$ | $0.46\pm 0.02$ | $0.44\pm 0.02$
0.050 | -2.0e-07 | $0.81\pm 0.04$ | $0.65\pm 0.02$ | $0.54\pm 0.02$ | $0.32\pm 0.00$ | $0.45\pm 0.05$ | $0.49\pm 0.02$ | $0.46\pm 0.02$
0.060 | -2.0e-07 | $0.78\pm 0.02$ | $0.63\pm 0.00$ | $0.52\pm 0.02$ | $0.32\pm 0.00$ | $0.45\pm 0.03$ | $0.47\pm 0.00$ | $0.45\pm 0.03$
0.070 | -2.0e-07 | $0.84\pm 0.03$ | $0.64\pm 0.03$ | $0.50\pm 0.00$ | $0.35\pm 0.03$ | $0.49\pm 0.03$ | $0.50\pm 0.00$ | $0.47\pm 0.03$

Table 3. Robustness to Query Size. Applied to GoogleLocal-L, each method’s
robustness to different query sizes sheds light on the tradeoffs involved in
query size selection. The proposed method and Naive are competitive in their
accuracy in estimating the true stopping point, while 2P-PL and 3P-PL produce
the most consistent stopping criteria over threshold sizes.

AFA Alg | Threshold | 2P-PL-Initial | 2P-PL | 3P-PL | 3P-PL-Exp | Naive | FIDO | Oracle
---|---|---|---|---|---|---|---|---
Stability | -5.0e-07 | $0.30\pm 0.00$ | $0.31\pm 0.03$ | $0.31\pm 0.06$ | $0.16\pm 0.00$ | $0.24\pm 0.03$ | $0.26\pm 0.06$ | $0.22\pm 0.06$
Stability | -2.0e-07 | $0.71\pm 0.02$ | $0.64\pm 0.06$ | $0.57\pm 0.11$ | $0.24\pm 0.03$ | $0.27\pm 0.09$ | $0.47\pm 0.11$ | $0.42\pm 0.09$
Stability | -1.0e-07 | $1.00\pm 0.00$ | $1.00\pm 0.00$ | $0.96\pm 0.06$ | $0.29\pm 0.06$ | $0.29\pm 0.14$ | $0.70\pm 0.21$ | $0.75\pm 0.15$
QBC | -5.0e-07 | $0.32\pm 0.02$ | $0.33\pm 0.00$ | $0.33\pm 0.00$ | $0.19\pm 0.02$ | $0.23\pm 0.00$ | $0.24\pm 0.02$ | $0.21\pm 0.02$
QBC | -2.0e-07 | $0.73\pm 0.02$ | $0.67\pm 0.02$ | $0.58\pm 0.02$ | $0.24\pm 0.02$ | $0.23\pm 0.00$ | $0.38\pm 0.03$ | $0.36\pm 0.03$
QBC | -1.0e-07 | $1.00\pm 0.00$ | $1.00\pm 0.00$ | $1.00\pm 0.00$ | $0.31\pm 0.02$ | $0.23\pm 0.00$ | $0.88\pm 0.27$ | $0.96\pm 0.00$

Table 4. Robustness to AFA Algorithm. The proposed method adheres most closely
to the true stopping point across AFA algorithms applied to data collection
from GoogleLocal-L.

##  7\. User-specific Impact Analyses

Previous sections discuss minimized data collection in terms of diminishing
return across all users. In this section, we examine FIDO’s effect on per-user
metrics. We discuss how user performance-based data minimization departs from
traditional assumptions for performance curves and recommend areas for further
research.

###  7.1. Evaluation of User-Specific Data Minimization.

Figure 3. (A) We show that the performance achieved during data collection
depends on both the AFA algorithm employed and the initialization conditions.
Error bars are reported over 5 random initializations. (B) User-specific
performance metrics when minimized data collection learns one curve for all
users (left) and a curve for each user (right). Unsurprisingly, we see that
the mode of user-specific performance increases as $t$ increases. This is also
the case when learning user-specific performance curves, but there is a large
spread of true returns on additional data. This suggests future areas of work
for learning accurate user-specific performance curves. (C) We also show that
a small portion of users bear the majority of the data collection burden in a
histogram of the quantity of features acquired per user by Stability from
MovieLens-S halfway through data collection.

We analyze the performance of the framework on user-specific performance
metrics in two cases. In the first, we replicate the setting discussed in
previous sections and learn a performance curve for the entire dataset. In the
second, FIDO learns a performance curve _per user_ and applies a stopping
criterion based on goal $t$ to each curve. We use the same procedure to
estimate $t_{u}$ as $t$ earlier, except we use a user-specific performance
curve rather than a global performance curve. The user-specific performance
curve is learned by replacing a global performance metric (MSE over all users)
with a user-specific performance metric (MSE over a set of items specific to
one user). Estimating $t_{u}$ from $\sigma_{M}^{u}$ produces a $t_{u}$ for
each user.

In Figure 3(B), we plot the distribution of user returns in performance given
a global threshold $t$ (left). As $t$ increases, the distribution mode shifts
up and the variance in user fractions of performance decreases. Note that the
x-axis for each histogram extends beyond $1$. This is because more data does
not necessarily translate to increased _per-user_ performance. Two factors are
responsible: 1) The small validation set size for each user produces noisy
performance estimates and 2) the collection of additional data can still hurt
user performance if this data is not representative. The assumption of
monotonically increasing performance over data collection does not hold, and
accordingly, the framework does not perform as well. A key takeaway from this
experiment is that the return in performance may not be an appropriate metric
for data minimization on a per user level.

###  7.2. Lessons on User-Specific Data Minimization.

Methods designed to address user-specific data minimization should consider:

####  7.2.1. Tensions between AFA and fairness

While AFA is a natural choice for limited data collection, we find that it
introduces disparate data collection burden across users by collecting a
different number of features from different users. Figure 3(C), plots a
histogram of the quantity of collected data over users for AFA algorithm
Stability, for dataset MovieLens-S (similar trends exist for other datasets).
AFA algorithms ”exploit” a small number of users by collecting a large number
of feature-values from them. Yet, our experiments also show that increased
data collection significantly correlates with better performance for
individual users. It is likely that certain users would choose to bear the
burden of excess data collection in exchange for better performance. Thus,
data minimization given an AFA approach raises questions of both user fairness
and user agency.

####  7.2.2. More complex curve models.

It is worth exploring a family of parametric curves that describe the
phenomenon of a user whose model performance degrades with the collection of
additional data. Approximately 20% of users in each of the four datasets
exhibit this property, suggesting that monotonic curve models are not the
right choice for modeling user-specific performance curves. Moreover, user-
specific performance curves are noisier and as a result, may benefit from
drawing multiple samples at each subsample size.

##  8\. Putting It All Together

Thus far, we have put forth a framework to guide data collection by learning
the an algorithm’s performance curve as data arrives. Subsequent experiments
validated the resulting performance curve on a returns-based data minimization
objective. These experiments deliver a number of takeaways for the data
minimization practitioner. Here, we summarize the implications of our results
on specific design choices:

  1. (1)

Choosing a Feature Acquisition Algorithm. Based on our experiments, we
recommend random feature acquisition to guide data minimization. We base this
recommendation on three reasons: 1) random feature acquisition produces a
smoother performance curve, and thus, more accurate performance estimates, 2)
our work confirms recent findings that demonstrate how the success of
intelligent data collection depends upon initialization conditions (Munjal et
al., 2020), and 3) AFA algorithms can place excess data collection burden on
specific users, as our user-specific impact analyses show.

  2. (2)

Choosing a Performance Curve Model. The piecewise power law curve model is
best fit to describe the relationship between dataset size and performance in
the datasets we consider. We see that this choice may not be consequential
when the diminishing returns region is small, as we see with MovieLens-S.

  3. (3)

Creating a Representative Validation Set. This framework hinges on the
creation of a representative validation set. As is the case with many systems
that operate on continuously collected data, a representative validation set
may need to be updated to account for data drift over time.

  4. (4)

Identifying a Relevant Objective. While the framework we propose is flexible
to many objectives, it is worth considering when one objective may be more
desirable than another. We provide a case study of an alternate objective,
based on relative performance in the supplement. One can consider its _ease of
definition_ : how well does the selected objective reflect user preferences?
Gauging user preferences in terms of relative performance may be easier to
survey for than diminishing returns. One could also consider the objective’s
_specificity_. Our experiments show that minimizing by diminishing returns is
more accurate earlier on during data collection compared to minimization by
relative performance. Dataset size plays a role too, as our experiments show
that both the prediction of returns and relative performance are noisier in
smaller datasets.

  5. (5)

Performing User-Specific Impact Analyses. Data minimization may
disproportionately affect marginalized populations. Recent work (Tae and
Whang, 2020; Chen et al., 2018) has shown that in some instances, it is
necessary to collect _more_ data to ensure the equitable performance. As a
result, it is imperative to perform per-user analyses when studying and
proposing methods for data minimization.

##  9\. Limitations

FIDO is not without limitations. First, the framework relies on access to a
validation set large enough to approximate performance on the test set.
Experiments on MovieLens-S and GoogleLocal-S show that smaller validation set
sizes translate to higher variance in data minimization performance. One could
mitigate this variation in performance by intelligently constructing the
validation set, rather than randomly. Such an approach could be useful in
settings where concept drift is common, and the validation set must be updated
to remain representative of the test set.

Moreover, this work considers data acquisition where feature-values are
roughly homogeneous in terms of sensitivity, since each is an item rating.
Data minimization concerns not only whether data is collected, but also what
type of data is collected. This includes the identifiability or pseudonymity
of the collected data. Intersections between FIDO and recent work on breadth-
based data minimization (Rastegarpanah et al., 2021; Goldsteen et al., 2021)
can address feature-specific data minimization concerns.

Finally, FIDO is only one way to implement data minimization and represents
one facet of a comprehensive approach to data minimization. In practice, a
data processor would deploy multiple techniques that work in concert to
minimize data across stages of a system’s life cycle, including data
collection, storage, and inference.

##  10\. Discussion

This work aims to bridge the gap between the legal principle of data
minimization and its practical realization. Data-driven systems often operate
under the assumption that more data is unequivocally better, for all parties
involved. This might not the case when the identifiability, sensitivity,
liability, and storage costs of collected data are acknowledged and
appropriately balanced. We intend our work to be a step towards respectful
data collection.

Towards this end, we propose FIDO, a Framework for Inhibiting Data
Overcollection. FIDO takes an idea established across domains in machine
learning—the ubiquity of scaling laws in data driven systems—and uses it to
provide a performance-based stopping criterion. FIDO accomplishes this by
acquiring data in small batches, refitting an estimate of the performance
curve, and applying a performance-based stopping criterion. FIDO uses a
piecewise power law technique grounded in different phases of data collection
to produce an accurate estimate of the performance curve.

Our empirical investigation of FIDO revealed findings with practical
implications for the implementation of data minimization. Specifically,
certain performance curve families (e.g., the three-parameter power law)
systematically overcollect data by not modeling each data collection phase
separately. We also demonstrate how active feature acquisition—a technique
which might be thought of as a go-to tool for data minimization—can be
undesirable in the context of personal data protection. We found that AFA can
place excess data collection burden on a small set of users, and that the
technique’s performance depends on data initialization conditions, with
degrading performance in simulations of evolving user communities or
restricted feature sets

In light of these complexities, we believe that data minimization compliance
in machine learning models will require similar efforts as the principle of
fairness has garnered. Definitions, formal implementations and caveats will
depend on the application domain, the underlying model (e.g., recommendation,
classification). The piecewise power law may not be appropriate for all
domains, including user-specific data minimization. Moreover, adversarial
approaches are possible: a data processor acting in bad faith may choose a
model class that requires a large amount of personal data. Further research is
necessary to ensure data minimization occurs despite malicious data collection
practices.

###### Acknowledgements.

We thank John Guttag, Hansa Srinivasan, and Hal Daumè III for helpful
comments.

## References

  * (1)
  * Authority (2018) Datatilsynet: The Norwegian Data Protection Authority. 2018.  Artificial Intelligence and Privacy.  https://www.datatilsynet.no/globalassets/global/english/ai-and-privacy.pdf
  * Baker et al. (2017) Bowen Baker, Otkrist Gupta, Ramesh Raskar, and Nikhil Naik. 2017.  Accelerating neural architecture search using performance prediction.  _arXiv preprint arXiv:1705.10823_ (2017).
  * Biega and Finck (2021) Asia J. Biega and Michèle Finck. 2021.  Reviving Purpose Limitation and Data Minimisation in Data-Driven Systems.  _Technology and Regulation_ (2021).
  * Biega et al. (2020) Asia J. Biega, Peter Potash, Hal Daumé, Fernando Diaz, and Michèle Finck. 2020.  Operationalizing the Legal Principle of Data Minimization for Personalization. In _ACM(43) SIGIR ’20_. 399–408.
  * Binns and Gallo (2019) Reuben Binns and Valeria Gallo. 2019.  _Data minimisation and privacy-preserving techniques in AI systems_.  https://ico.org.uk/about-the-ico/news-and-events/ai-blog-data-minimisation-and-privacy-preserving-techniques-in-ai-systems/
  * Chakraborty et al. (2013) Shayok Chakraborty, Jiayu Zhou, Vineeth Balasubramanian, Sethuraman Panchanathan, Ian Davidson, and Jieping Ye. 2013.  Active Matrix Completion.  _ICDM_.
  * Chen et al. (2018) Irene Chen, Fredrik D Johansson, and David Sontag. 2018\.  Why is my classifier discriminatory?. In _NeurIPS_. 3539–3550.
  * Cho et al. (2015) Junghwan Cho, Kyewook Lee, Ellie Shin, Garry Choy, and Synho Do. 2015.  Medical Image Deep Learning with Hospital PACS Dataset.  _CoRR_ (2015).
  * Chow et al. (2013) Richard Chow, Hongxia Jin, Bart Knijnenburg, and Gokay Saldamli. 2013.  Differential data analysis for recommender systems. In _ACM7-RecSys_. 323–326.
  * Datatilsynet (2018) Norwegian Data Protection Authority Datatilsynet. 2018.  _Artificial Intelligence and Privacy_.  https://www.datatilsynet.no/en/regulations-and-tools/reports-on-specific-subjects/ai-and-privacy/
  * Dobbin et al. (2008) Kevin K. Dobbin, Yingdong Zhao, and Richard M. Simon. 2008\.  How Large a Training Set is Needed to Develop a Classifier for Microarray Data?  _Clinical Cancer Research_ 14, 1 (2008), 108–114.
  * Domhan et al. (2015) Tobias Domhan, Jost Tobias Springenberg, and Frank Hutter. 2015\.  Speeding up automatic hyperparameter optimization of deep neural networks by extrapolation of learning curves. In _IJCAI-24_.
  * Figueroa et al. (2012) Rosa L Figueroa, Qing Zeng-Treitler, Sasikiran Kandula, and Long H Ngo. 2012.  Predicting sample size required for classification performance.  _BMC Medical Informatics and Decision Making_ 12, 1 (2012).
  * Freund et al. (1997) Yoav Freund, H Sebastian Seung, Eli Shamir, and Naftali Tishby. 1997.  Selective sampling using the query by committee algorithm.  _Machine learning_ 28 (1997).
  * Funk (2006) Simon Funk. 2006\.  Netflix update: Try this at home.  _https://sifter.org/ simon/journal/20061211.html_ (2006).
  * GDPR (2016) GDPR. 2016.  Regulation (EU) 2016/679 of the European Parliament and of the Council.  _Official Journal of the European Union_ (2016).
  * Goldsteen et al. (2021) Abigail Goldsteen, Gilad Ezov, Ron Shmelkin, Micha Moffie, and Ariel Farkash. 2021.  Data minimization for GDPR Compliance in machine learning models.  _AI and Ethics_ (2021), 1–15.
  * Gürses et al. (2015) Seda Gürses, Carmela Troncoso, and Claudia Diaz. 2015\.  Engineering privacy by design reloaded. In _Amsterdam Privacy Conference_. 1–21.
  * Hajian-Tilaki (2014) Karimollah Hajian-Tilaki. 2014\.  Sample size estimation in diagnostic test studies of biomedical informatics.  _Journal of Biomedical Informatics_ 48 (2014), 193 – 204.
  * Harper and Konstan (2015) F Maxwell Harper and Joseph A Konstan. 2015.  The movielens datasets: History and context.  _Acm-TiiS_ 5, 4 (2015), 1–19.
  * He et al. (2017) Ruining He, Wang-Cheng Kang, and Julian McAuley. 2017\.  Translation-based recommendation. In _ACM11-RecSys_. 161–169.
  * Hestness et al. (2017) J Hestness, S Narang, N Ardalani, G Diamos, H Jun, H Kianinejad, M Patwary, Y Yang, and Y Zhou. 2017\.  Deep Learning Scaling is Predictable, Empirically.  _arXiv preprint arXiv:1712.00409_ (2017).
  * Huang et al. (2018) Sheng-Jun Huang, Miao Xu, Ming-Kun Xie, Masashi Sugiyama, Gang Niu, and Songcan Chen. 2018\.  Active feature acquisition with supervised matrix completion. In _ACM24-SIGKDD_. 1571–1579.
  * ICO (2018a) UK Information Commisioner’s Office: ICO. 2018a.  _Guide to Data Protection. Some basic concepts_.  Retrieved Jan 22, 2020 from https://ico.org.uk/for-organisations/guide-to-data-protection/introduction-to-data-protection/some-basic-concepts/
  * ICO (2018b) UK Information Commisioner’s Office: ICO. 2018b.  _Guide to the General Data Protection Regulation (GDPR). Principle (c): Data minimisation._ Retrieved Jan 22, 2020 from https://ico.org.uk/for-organisations/guide-to-data-protection/guide-to-the-general-data-protection-regulation-gdpr/principles/data-minimisation/
  * Kalayeh and Landgrebe (1983) HM Kalayeh and David A Landgrebe. 1983.  Predicting the required number of training samples.  _IEEE-TPAMI_ 6 (1983), 664–667.
  * Kolachina et al. (2012) Prasanth Kolachina, Nicola Cancedda, Marc Dymetman, and Sriram Venkatapathy. 2012.  Prediction of learning curves in machine translation. In _ACL ’12_.
  * Koops ([n.d.]) Bert-Jaap Koops. [n.d.].  The trouble with European data protection law’(2014).  _International Data Privacy Law_ 4 ([n. d.]), 250.
  * Krause and Horvitz (2010) Andreas Krause and Eric Horvitz. 2010.  A utility-theoretic approach to privacy in online services.  _Journal of Artificial Intelligence Research_ 39 (2010), 633–662.
  * MacCarthy (2018) Mark MacCarthy. 2018\.  In Defense of Big Data Analytics.  _The Cambridge Handbook of Consumer Privacy_ (2018), 47–78.
  * Melville et al. (2005) Prem Melville, Maytal Saar-Tsechansky, Foster Provost, and Raymond Mooney. 2005.  An expected utility approach to active feature-value acquisition. In _ICDM_.
  * Munjal et al. (2020) Prateek Munjal, Nasir Hayat, Munawar Hayat, Jamshid Sourati, and Shadab Khan. 2020.  Towards Robust and Reproducible Active Learning Using Neural Networks.  _arXiv_ (2020), arXiv–2002.
  * Pasricha and McAuley (2018) Rajiv Pasricha and Julian McAuley. 2018.  Translation-based factorization machines for sequential recommendation. In _ACM-12-RecSys_. 63–71.
  * Rastegarpanah et al. (2021) Bashir Rastegarpanah, Krishna Gummadi, and Mark Crovella. 2021\.  Auditing Black-Box Prediction Models for Data Minimization Compliance.  _Advances in Neural Information Processing Systems_ 34 (2021).
  * Senarath and Arachchilage (2018) Awanthika Senarath and Nalin Asanka Gamagedara Arachchilage. 2018\.  Understanding Software Developers’ Approach towards Implementing Data Minimization.  _arXiv preprint arXiv:1808.01479_ (2018).
  * Tae and Whang (2020) Ki Hyun Tae and Steven Euijong Whang. 2020.  Slice Tuner: A Selective Data Collection Framework for Accurate and Fair Machine Learning Models.  (2020).
  * Vincent et al. (2019) Nicholas Vincent, Brent Hecht, and Shilad Sen. 2019.  “Data Strikes”: Evaluating the Effectiveness of a New Form of Collective Action Against Technology Companies. In _The World Wide Web Conference_. ACM.
  * Vu et al. (2007) Duy Vu, Mikhail Bilenko, Maytal Saar-tsechansky, and Prem Melville. 2007.  Intelligent Information Acquisition for Improved Clustering.
  * Wen et al. (2018) Hongyi Wen, Longqi Yang, Michael Sobolev, and Deborah Estrin. 2018\.  Exploring recommendations under user-controlled data filtering. In _ACM12 RecSys_. 72–76.
  * Wistuba and Pedapati (2020) Martin Wistuba and Tejaswini Pedapati. 2020.  Learning to Rank Learning Curves. In _International Conference on Machine Learning_. PMLR, 10303–10312.


070018 2015 R. Dickman M. Hutter, Australian National University, Canberra,
Australia. 070018

In this paper, a Bayesian method for piecewise regression is adapted to handle
counting processes data distributed as Poisson. A numerical code in
_Mathematica_ is developed and tested analyzing simulated data. The resulting
method is valuable for detecting breaking points in the count rate of time
series for Poisson processes.

# Bayesian regression of piecewise homogeneous Poisson processes

Diego J. R. Sevilla[inst1] E-mail<EMAIL_ADDRESS>
(2 November 2015; 27 November 2015)

††volume: 7

99 inst1 Departamento de Física y Química, Escuela de Formación Básica.
Facultad de Ciencias Exactas, Ingeniería y Agrimensura. Universidad Nacional
de Rosario, Av. Pellegrini 250, S2000BTP Rosario, Argentina.

##  1 Introduction

Bayesian statistics have revolutionized data analysis [1]. Techniques like the
Generalized Lomb-Scargle Periodogram [2] allow us to obtain oscillation
frequencies of time series with unprecedented accuracy. The Gregory and Loredo
method [3] goes further allowing us to find and characterize periodic signals
of any period and shape.

To detect non-periodical variations, the _Exact Bayesian Regression of
Piecewise Constant Functions_ by Marcus Hutter (hereafter Hutter’s method) [4]
is valuable. It permits to estimate the most probable partition of a data set
in segments of constant signals, determining the number of segments and their
borders, and in-segments means and variances. Hutter’s method works with two
continuous distributions: Normal, and Cauchy-Lorentz. The latter —the
canonical example of a pathological distribution with undefined moments—, is
also suitable to analyze data with other symmetric probability distributions,
especially with heavy tails.

In the case of counting processes, especially for low rates, when data consist
in non-negative small integers, methods specially designed to discrete
probability distributions are necessary. Some regression methods, specially
for non-homogeneous Poisson processes [5], were developed.

In this paper, Hutter’s method is adapted for analyzing data distributed as
Poisson. The results are summarized in a code in _Mathematica_ [6]. It can be
used to analyze data of several physical processes which follow the Poisson
distribution (e.g., detection of photons in X-ray Astronomy, particles in
nuclear disintegration, etc.), if sudden changes in detection rates are
suspected.

##  2 Method

Hutter’s method is summarized in Table 1 of Ref. [4] in a pseudo C code which
is divided in two blocks. The first one calculates moments $A^{k}_{ij}$ with
$k=0,1,2$ of the PDF of the statistical models for segments of data
$D_{ij}:=\\{n_{i+1},\ldots,n_{j}\\}$. The second one performs the regression
from moments $A^{k}_{ij}$. The code developed in this work is divided in three
blocks.

As the members of the Poisson distributions family are identified by one
parameter -the mean rate $r$ of the Poisson process-, the PDF of the models
for a segment $D_{ij}$ is [1]

$P(r|D_{ij},I)=\frac{P(r|I)\,P(D_{ij}|r)}{P(D_{ij})},$ (1)

where $P(r|I)$ is the prior of parameter $r$, $P(D_{ij}|r)$ is the likelihood
of segment $D_{ij}$ for a given $r$, $P(D_{ij})$ is the global likelihood of
the family, and $I$ represents a prior information.

Usually, the prior information consists of global quantities calculated from
$D:=D_{0N}$, _i.e._ , from all the data set. For Poisson processes, only one
quantity is necessary: the mean rate $\hat{r}$. Considering the conjugate
prior of the Poisson distribution [7], the prior results

$P(r|\hat{r})=\frac{r^{\hat{r}-1}\,e^{-r}}{\Gamma(\hat{r})}.$ (2)

For a Poisson process with rate $r$, the likelihood of a segment $D_{ij}$ is

$P(D_{ij}|r)=\prod_{t=i+1}^{j}\frac{r^{n_{t}}\,e^{-r}}{n_{t}!}.$ (3)

So, the moments of the posterior can be expressed in an analytical form

$A^{k}_{ij}=\frac{\Gamma(k+\hat{r}+\sum_{t=i+1}^{j}n_{t})\,\prod_{t=i+1}^{j}\frac{1}{n_{t}!}}{\Gamma(\hat{r})\,(j-i+1)^{k+\hat{r}+\sum_{t=i+1}^{j}n_{t}}}.$
(4)

Code block 1 calculates $A^{k}_{ij}$. It needs as input the time series to be
analyzed (list data). The output are functions A0[i,j], A1[i,j] and A2[i,j]
and integer n, which is the length of data.

Code block 1: _Mathematica_ code to calculate $A^{k}_{ij}$.

⬇

n=Length[data];

r=Mean[data];

Do[

Do[

d=j-i; m=r+Sum[data[[t]],{t,i+1,j}];

A0[i,j]=(m-1)!/(Gamma[r]*(d+1)^m)*

Product[1/data[[t]]!,{t,i+1,j}];

A1[i,j]=m*A0[i,j]/(d+1);

A2[i,j]=(m+1)*A1[i,j]/(d+1);

,{j,i+1,n}];

,{i,0,n}];

As the second block of Hutter’s code only needs the moments $A^{k}_{ij}$ as
inputs, it could work properly with no changes. It computes the evidence, the
probability for $k$ segments and its MAP estimation $\hat{k}$, the probability
of boundaries locations and the MAP locations of the $\hat{k}$ boundaries, the
first and second in-segment moments, and an interesting regression curve that
smooths the final result.

Nevertheless, for our specific problem, once the segments boundaries are
obtained, we can estimate their means and variances straightforwardly, so we
only use a part of Hutter’s second block, which is shown in code block 2. The
logical of the algorithm is explained in Ref. [4]. Code block 2 needs as
inputs A0[i,j], A1[i,j], A2[i,j] and n, all calculated in code block 1, and
integer kmax, which is the maximum number of segments to be considered. The
outputs are the evidence (e), the probability for $k$ segments (c[k]), its MAP
(khat), the probability of boundaries locations (B[i]), and their MAP
(that[p]).

Code block 2: _Mathematica_ code to calculate breaking points.

⬇

Do[

L[0,i]=KroneckerDelta[i,0];

R[0,i]=KroneckerDelta[i,n];

,{i,0,n}];

Do[

Do[

L[k+1,i]=Sum[L[k,h]*A0[h,i],{h,k,i-1}];

R[k+1,i]=Sum[R[k,h]*A0[i,h],{h,i+1,n-k}];

,{i,0,n}]

,{k,0,kmax-1}];

e=1/kmax*Sum[L[k,n]/Binomial[n-1,k-1],{k,1,kmax}];

Do[

c[k]=L[k,n]/(Binomial[n-1,k-1]*kmax*e)

,{k,1,kmax}];

khat=1;

Do[If[c[khat]<c[k],khat=k];,{k,0,kmax}];

Do[B[i]=

Sum[L[p,i]*R[khat-p,i]/L[khat,n],{p,0,khat}];

,{i,0,n}];

Do[

that[p]=0;

dummy=L[p,0]*R[khat-p,0];

Do[

If[dummy<L[p,h]*R[khat-p,h],

that[p]=h;

dummy=L[p,h]*R[khat-p,h];

];

,{h,1,n}];

,{p,0,khat}];

Finally, we calculate the in-segments means and estimate their statistical
errors. If one segment of $m$ elements has $n$ counts, its mean rate is $n/m$,
and its variance is approximately $n/m^{2}$.

To determine the accuracy of the fit, it is also useful to estimate the
uncertainties of the boundaries locations. A reasonable estimation of the
uncertainties can be obtained from the second moments of the probability
distributions of boundaries locations in the neighborhoods of the breaking
points. If the probabilities of the boundaries locations are given by function
$B(k)$, the uncertainties approximately result

$\epsilon_{\hat{k}}=\sqrt{\frac{\sum_{k=\hat{k}-a+1}^{\hat{k}+a}B(k)\,(k-\hat{k})^{2}}{\sum_{k=\hat{k}-a+1}^{\hat{k}-a}B(k)}},$
(5)

where $a$ is large enough to consider all the width of the peak corresponding
to boundary $\hat{k}$, but small enough to avoid including peaks of other
boundaries. In practice, if $\hat{\j}$, $\hat{k}$ and $\hat{l}$ are the
positions of consecutive boundaries, a good value for $a$ is the minimum of
$(\hat{k}-\hat{\j})/2$ and $(\hat{l}-\hat{k})/2$.

Code block 3 uses these approaches to calculate the constant piecewise
regression of data, and to estimate its statistical errors. The inputs are
c[k], khat, B[i] and that. The outputs are list reg, which represents the best
fit, and lists re1 and re2, which represent the minimum and maximum
estimations considering the statistical errors of reg.

Code block 3: _Mathematica_ code to calculate regression.

⬇

TBP=DeleteDuplicates[Table[that[k],{k,0,khat}]];

NBP=Length[TBP]-1;

Do[BP[k]=TBP[[k+1]];,{k,0,NBP}];

ethat[0]=0;ethat[NBP]=0;

Do[

l1=IntegerPart[(BP[k-1]+BP[k])/2]+1;

l2=IntegerPart[(BP[k+1]+BP[k])/2];

ethat[k]=

Round[Sqrt[Sum[(j-BP[k])^2*B[j],{j,l1,l2}]/

Sum[B[j],{j,l1,l2}]]];

,{k,1,NBP-1}];

Do[

mm[k]=BP[k]-BP[k-1];

nn[k]=Sum[data[[i]],{i,BP[k-1]+1,BP[k]}];

,{k,1,NBP}];

reg=Flatten[Table[Table[nn[k]/mm[k]

,{BP[k]-BP[k-1]}],{k,1,NBP}]];

BP1[0]=BP2[0]=BP[0];BP1[NBP]=BP2[NBP]=BP[NBP];

Do[

s=If[reg[[BP[k]+1]]>reg[[BP[k]]],1,-1];

BP1[k]=BP[k]+s*ethat[k];

BP2[k]=BP[k]-s*ethat[k];

,{k,1,NBP-1}];

re1=Flatten[Table[Table[(nn[k]-Sqrt[nn[k]])/mm[k]

,{BP1[k]-BP1[k-1]}],{k,1,NBP}]];

re2=Flatten[Table[Table[(nn[k]+Sqrt[nn[k]])/mm[k]

,{BP2[k]-BP2[k-1]}],{k,1,NBP}]];

##  3 Applications and Discussion

Figure 1 (top) shows, in blue dots, data simulated using _Mathematica_. Data
consist of 150 Poisson distributed elements, the first 50 with rate $1.5$, the
second 50 with rate $0.5$, and the last 50 with rate $1.0$. Applying the first
2 blocks of code on data, we can see that the probability of having 2 breaking
points is very high. Figure 1 (top) also shows, in red line, the probability
for the boundaries locations. Applying code block 3, we obtain the regression
[Fig. 1 (bottom), black dashed curve] and its error estimation [Fig. 1
(bottom), gray zone]. The continuous blue line in Fig. 1 (bottom) indicates
the rates used in simulation.

Figure 1:  Top: Simulated data (blue dots) and boundaries location probability
(red line). Bottom: Regression curve and its error estimation (black dashed
line and gray zone), and the rate curve used in simulation (blue line).

The regression in the example above fits very well with the rate curve used in
simulation. But sometimes regressions result qualitatively different to the
rate curve, showing more or less breaking points, even for data simulated in
the same conditions. This effect is due to chance. To show this issue, 2000
simulations with the same conditions were performed. In 992 of them, two
breaking points were found. In the others, there were found zero (44), one
(208), three (419), four (155), five (73), six (41), and seven or more (68)
breaking points. For cases in which two breaking points were found, statistics
of the most likely boundaries locations and in-segment mean rates were
calculated. Figure 2 shows histograms of those statistics.

Figure 2:  Top: Histogram of the boundaries locations. Bottom: Histogram of
the in-segment mean rates. Both figures were calculated for a set of 2000
simulations similar to that shown in Fig. 1.

Figure 2 (top) shows histograms for boundaries locations. It is clear that the
bigger the step, the smaller the uncertainty on its location. Figure 2
(bottom) shows histograms of in-segment rates. It is clear that the greater
the rate, the smaller its relative statistical error.

Figure 3 shows data and boundaries location probabilities for a simulation
similar to the previous ones, but now with rates 3.0, 1.0 and 2.0. Comparing
Fig. 1 (top) and Fig. 3 (top), we can see that in the latter one the
boundaries locations are found more accurately.

Figure 3:  Top: Simulated data (blue dots) and boundaries location probability
(red line). Bottom: Regression curve and its error estimation (black dashed
line and gray zone), and the rate curve used in simulation (blue line).

Again, 2000 simulations with the same conditions were performed. In 1159 of
them, two breaking points were found, while in the others, there were found
zero (1), one (33), three (499), four (167), five (75), six (32), and seven or
more (34) breaking points. Figure 4 shows histograms of the statistics of the
most likely boundaries locations and in-segment rates for the simulations with
two breaking points found. Comparing with Fig. 2, we can see that the
histograms are now narrower. These results confirm what was stated above.

Figure 4:  Top: Histogram of the boundaries locations. Bottom: Histogram of
the in-segment rates. Both figures were calculated for a set of 2000
simulations similar to that shown in Fig. 3.

It is important to note that the probability for the _real curve_ to be
_completely_ inside the region defined by the error estimations of the
regression is significantly less than one. It is easy to see why: if the
errors were independent and equal to the standard error, the probability of
satisfying $n$ error conditions simultaneously would be $0.68^{n}$. But even
the actual probability could be lower, since it is clear that the errors must
be dependent. Nevertheless, the error estimations presented here are useful to
get an idea of the accuracy of the regression.

Finally, the capability to detect a breaking point with this code was tested
for different count rates. To do this, simulated data sets of a single step in
the count rate were used. Data sets consist in 100 Poisson distributed
elements, the first 50 for a rate $r_{1}$ and the last 50 for a rate $r_{2}$.
1000 simulations were done for each pair $(r_{1},r_{2})$. Statistics of
successful detections are presented in Table 1. A successful detection is
considered when only one breaking point between elements 40 and 60 is
detected.

Table 1 shows that the smaller is the mean rate difference and the smaller are
the mean rates, the more difficult is the detection of the step. This result
is expected because in a Poisson distribution the variance is equal to the
mean.

Table 1: Statistics of successful detections for a single step. $r_{1}$\$\,r_{2}$ | 3.0 | 2.0 | 1.6 | 1.2 | 0.8
---|---|---|---|---|---
0.4 | 0.86 | 0.74 | 0.70 | 0.63 | 0.46
0.8 | 0.77 | 0.70 | 0.60 | 0.36 |
1.2 | 0.69 | 0.61 | 0.30 |  |
1.6 | 0.65 | 0.28 |  |  |
2.0 | 0.60 |  |  |  |

##  4 Conclusions

In this work, a code for Bayesian regression of piecewise constant functions
was adapted to handle data from Poisson processes. For this purpose, equations
for calculating the moments of the posteriors of segments of data were found
through Bayes theorem, considering the conjugate prior of the Poisson
distribution as prior. These results, as well as part of Hutter’s method, were
used to calculate the most probable number of segments and their boundaries.
Procedures for calculating in-segments mean rates and the uncertainties of
mean rates and boundaries locations are also provided. The resulting method is
summarized in a code in _Mathematica_.

The code was applied to simulated data. Firstly, two examples with tree
segments were analyzed. The code performed well in both cases considering the
dispersion of data, and the results improved in the case of higher mean rates
and mean rates differences. This occurs because of the statistical dispersion
of Poisson distributed data, which is greater than the mean rate if the mean
rate is lower than one.

Finally, simulations of data of a single step were analyzed for different
rates, and statistics of the regressions with only one breaking point are
presented in a table. This table shows the effect of the rates and rate
differences in the regression accuracy, and, together with the errors
estimations provided by the code, can serve as an indicator of the reliability
of the method.

Supplementary material including the source code for the algorithms can be
found at the journal website [8].

###### Acknowledgements.

This work was partially supported by the National University of Rosario.

## References

  * [1] P C Gregory, Bayesian logical data analysis for the physical sciences, Cambridge University Press, Cambridge, UK (2004).
  * [2] G L Bretthorst, Lecture notes in statistics, Springer, Berlin (1988).
  * [3] P C Gregory, T J Loredo, A new method for the detection of a periodic signal of unknown shape and period, Astrophys. J. 398, 146 (1992).
  * [4] M Hutter, Exact Bayesian regression of piecewise constant functions, Bayesian Analysis 2, 635 (2007).
  * [5] J F Lawless, Regression methods for Poisson process data, J. Am. Stat. Assoc. 82, 399 (1987).

  * [6] Wolfram Research Inc., _Mathematica_ version 9.0, Wolfram Research, Inc., Champaign, Illinois (2012).
  * [7] A Gelman, J B Carlin, H S Stern, D B Rubin, Bayesian data analysis, Taylor & Francis, UK (2014).
  * [8] _Mathematica_ codes and examples by the author can be found at `http://www.papersinphysics.org`.


# Zero-shot Active Learning Using Self Supervised Learning

##  1 Introduction

Deep learning algorithms are often said to be data hungry. The performance of
such algorithms generally improve as more and more annotated data is fed into
the model. While collecting unlabelled data is easier (as they can be scraped
easily from the internet), annotating them is a tedious and expensive task.
Given a fixed budget available for data annotation, Active Learning helps
selecting the best subset of data for annotation, such that the deep learning
model when trained over that subset will have maximum generalization
performance under this budget.

A common theme in active learning is to start with a random subset of labelled
data and then use different strategies to iteratively add new datapoints. We
believe that there are three limitations of the current active learning
approaches.

  * •

For the current approaches examples are added iteratively in batches, which
can make this process difficult to scale. If an orgnization uses a third party
system to do data annotation process, then back and forth iterative
communication between them can make the process tedious and difficult to use.

  * •

Active learning approaches are not model agnostic. It means that for any new
model, another round of Active learning will have to be run to get the best
subset of data given the budget constraints.

  * •

The current approaches start with a random subset of data. Thus the initial
data that is collected for labelling is not an optimal subset.

In this work, we aim to propose a new Active Learning approach which is model
agnostic as well as one doesn’t require an iterative process. We aim to
leverage self-supervised learnt features for the task of Active Learning. The
benefit of self-supervised learning, is that one can get useful feature
representation of the input data, without having any annotation.

##  2 Related Work

###  2.1 Active Learning

Two popular directions for Active Learning are -

  * •

Uncertainty Estimation - [6, 18, 11] Select datapoints for which the model is
most uncertain about. The idea here is that adding such uncertain data points
will help the model better learn about the data, which in turn help it to
generalize well.

  * •

Diversity - [15, 8, 16] \- Select datapoints such that the diversity of
labelled set is increased. [15, 17] uses core-set/k-centre greedy approach to
iteratively sample new datapoints, using features extracted from the model
that has been trained over the current pool of labelled data. We will base our
algorithm over this approach.

###  2.2 Self-Supervised Learning

Self-supervised learning [2, 3, 10], is another area of research which aims to
do away with the expensive data annotation process. The idea here is to learn
good features from the data, which can then be used for other downstream
tasks.

#### Momentum Contrastive Learning [1, 14].

Momentum Contrast (MoCo) trains a visual representation encoder by matching an
encoded query $q$ to a dictionary of encoded keys using a contrastive loss.
The dictionary keys $\\{k_{0},k_{1},k_{2},...\\}$ are defined on-the-fly by a
set of data samples. The dictionary is built as a queue, with the current
mini-batch enqueued and the oldest mini-batch dequeued, decoupling it from the
mini-batch size. The keys are encoded by a slowly progressing encoder, driven
by a momentum update with the query encoder. The learned representations are
then evaluated by training a linear classifier using labeled training data and
evaluating on a test data. This method enables a large and consistent
dictionary for learning visual representations. Figure 1 shows a schematic
overview of MoCo.

Figure 1: Schematic Overview of Momentum Contrastive Learning Method

##  3 Datasets

We will be performing our experiments over CIFAR-10 dataset [9, 7]. The
CIFAR-10 dataset consists of 60000 32x32 colour images in 10 classes, with
6000 images per class. There are 50000 training images and 10000 test images.
The dataset is publicly available.

##  4 Method

We aim to use self-supervised for the task of active learning. Since the
features can be extracted without any annotation, these features are agnostic
to the model as well as the task which will be used for a given dataset.
Further, since these features are pre-computed once, and do not change as a
downstream task is performed for the dataset, we can get an ordering in which
the data needs to be annotated from before without going into an iterative
process. Specifically, our approach consists of the following steps -

  * •

Train a self-supervised model over the CIFAR-10 dataset, or use an existsing
self-supervised model trained over the ImageNet dataset [4].

  * •

Get features for all the images in the CIFAR-10 dataset.

  * •

Apply k-centre greedy algorithm to get the ordering in which the dataset needs
to be labelled [15, 13].

  * •

Given the budget constraint select the top ordered data-points, annotate them
and then train a model for this subset.

In the k-centre greedy approach we start with $k$ randomly selected datapoints
as cluster centres. Given a fixed budget $B$ we iteratively add $B$ datapoints
by selecting the one which is farthest away from the cluster centres. Once a
datapoint is selected, it is also added as a new cluster centre. This is a
diversity based Active Learning approach, as we want the selected data-points
to be as diverse as possible

##  5 Experiment Details

We perform our experiments over the CIFAR-10 dataset, and the task is
classification. We choose Wide ResNet [19] as the model for this task. We
further use CutOut [5] augmentation to improve the generalization ability.

We evaluate our approach for different budget constraints, where the budget is
defined by the number of annotated/labelled data-points. We show results for
budgets of 5k to 25k with an interval of 2500. Thus if the budget is $B$, we
select $B$ data-points, annotate them, train our Wide ResNet using the $B$
data-points and then report the test accuracy of this model.

###  5.1 Baselines

We choose the following two baseline approaches for comparison -

  * •

Random \- For each of the budget contraint, randomly select those number of
datapoints from the dataset.

  * •

Core-Set [15] \- Same as our approach, except that it uses a supervised model
instead of self-supervised model. Thus, given a subset of annotated datapoints
till now, it trains a supervised model over it, and then uses the pre-final
layer embeddings as the features of an input. The features are used to perform
k-centre greedy approach and then select the new data-points. Since, for any
selected subset we need to train a model to get the features, thus the
features will be dynamically updated for every iteration of Active learning.
This is in contrast to us, where our features are fixed throughout the Active
Learning process [13].

###  5.2 Active Learning Using Self-Supervised Features (Our Approach)

We use MoCo-v2 [3] and SimCLR [1, 12] to perform self-supervised learning over
the CIFAR-10 dataset. We use the following data-augmentation strategies for
MoCo-v2 training -

  * •

Random Grayscale \- Images are randomly converted to grayscale with a
probability of 0.2

  * •

Random Resize Crop \- A crop of scale randomly chosen between 0.08 to 1.0 is
made, before resizing the crop again to size 32*32.

  * •

Random Horzintal Flip \- The image is randomly flipped horizontally with a
probability pf 0.5.

  * •

Random Color jitter \- The brightness, hue and saturation are randomly changed
with a proabibility of 0.8.

To test the efficacy of the self supervised learning, we use the linear
evaluation protocol [3, 1] where the network is frozen, and only a linear
layer is learnt over the labelled trainset. On the linear evaluation protocol,
MoCo-v2 achieves a test accuracy of 91.2% whereas SimCLR achieves a test
accuracy of 93.6%

###  5.3 Evaluation

As mentioned above we train different WideResNet models for each of the budget
constraints, and then compare the test accuracies of the different algorithms
for each budget.

###  5.4 Results

Figure 2 shows the results for the two baselines as well as our approach over
different data splits. As can be seen from the figure, Our approach performs
better than the random baseline, but performs slighly worse the Core-Set
baseline when the number of labelled samples are less than 20k. For data split
sizes of 20k and more, our approach is comparable to the Core-Set baseline.

Our approach although performs comparable or slightly worse than the Core-Set
baseline, it has the advantage that the method is non-iterative based and also
is model agnostic. Thus, even if instead of Wide ResNet we used any other
model for classification, the same sampled data-points could have been used
for labelling.

Figure 2: Performance of different approaches

##  6 Discussion

(a) Random

(b) Core-Set

Figure 3: Frequency of classes in the 20k data points selected for labelling
for the Baselines

(a) Our (MoCo-v2)

(b) Our (SimCLR)

Figure 4: Frequency of classes in the 20k data points selected for labelling
for the Baselines

We plot the frequency of each of the classes amongst the 20k data points
selected for labelling in Figures 3 and 4.

As can be seen in Figure 3(a) random selection uniformly selects each of the
10 classes. However, the core-set baseline selects examples from cat class
more than other as seen in Figure 3(b). A similar trend exists for our
approaches too in Figures 4(a) and 4(b) where the cat class is selected more.

##  7 Conclusion and Future Work

In this work we proposed a non-iterative and model agnostic method for
performing Active Learning using self-supervised features. While being non-
iterative our approach is still comparable/slightly worse to the existing
state-of-the art approaches. We showed via frequency histogram, the different
classes selected in the labelled dataset, and find similar behaviour as to the
state-of-the=art approaches.

In the future we will like to explore other datasets such as CIFAR-100 and
ImageNet [4] and also try to further improve our performance with possibly
better self-supervised features.

##  8 Contributions

Abhishek implemented the baselines and did experiments with the MoCo-v2
approach. Shreya did experiments with the SimCLR approach. The project was
also advised by Jiaming Song.

## References

  * [1] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In International conference on machine learning, pages 1597–1607. PMLR, 2020.
  * [2] Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey Hinton.  Big self-supervised models are strong semi-supervised learners.  arXiv preprint arXiv:2006.10029, 2020.
  * [3] Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He.  Improved baselines with momentum contrastive learning.  arXiv preprint arXiv:2003.04297, 2020.
  * [4] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee, 2009.
  * [5] Terrance DeVries and Graham W Taylor.  Improved regularization of convolutional neural networks with cutout.  arXiv preprint arXiv:1708.04552, 2017.
  * [6] Yarin Gal, Riashat Islam, and Zoubin Ghahramani.  Deep bayesian active learning with image data.  In International Conference on Machine Learning, pages 1183–1192. PMLR, 2017.
  * [7] Akshat Jindal, Shreya Singh, and Soham Gadgil.  Classification for everyone: Building geography agnostic models for fairer recognition.  arXiv preprint arXiv:2312.02957, 2023.
  * [8] Andreas Kirsch, Joost Van Amersfoort, and Yarin Gal.  Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning.  arXiv preprint arXiv:1906.08158, 2019.
  * [9] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * [10] SDGV Akanksha Kumari and Shreya Singh.  Parallelization of alphabeta pruning algorithm for enhancing the two player games.  Int. J. Advances Electronics Comput. Sci, 4:74–81, 2017.
  * [11] G Mohammed Abdulla, Shreya Singh, and Sumit Borar.  Shop your right size: A system for recommending sizes for fashion products.  In Companion Proceedings of The 2019 World Wide Web Conference, WWW 1́9, page 327–334, New York, NY, USA, 2019. Association for Computing Machinery.
  * [12] Charles Rajan, Nishit Asnani, and Shreya Singh.  Shaping political discourse using multi-source news summarization.  arXiv preprint arXiv:2312.11703, 2023.
  * [13] Chetanya Rastogi, Prabhat Agarwal, and Shreya Singh.  Exploring graph based approaches for author name disambiguation.  arXiv preprint arXiv:2312.08388, 2023.
  * [14] Abraham Gerard Sebastian, Shreya Singh, P. B. T. Manikanta, T. S. Ashwin, and G. Ram Mohana Reddy.  Multimodal group activity state detection for classroom response system using convolutional neural networks.  In Pankaj Kumar Sa, Sambit Bakshi, Ioannis K. Hatzilygeroudis, and Manmath Narayan Sahoo, editors, Recent Findings in Intelligent Computing Techniques, pages 245–251, Singapore, 2019. Springer Singapore.
  * [15] Ozan Sener and Silvio Savarese.  Active learning for convolutional neural networks: A core-set approach.  arXiv preprint arXiv:1708.00489, 2017.
  * [16] Loveperteek Singh, Shreya Singh, Sagar Arora, and Sumit Borar.  One embedding to do them all.  arXiv preprint arXiv:1906.12120, 2019.
  * [17] Shreya Singh, G Mohammed Abdulla, Sumit Borar, and Sagar Arora.  Footwear size recommendation system.  arXiv preprint arXiv:1806.11423, 2018.
  * [18] Donggeun Yoo and In So Kweon.  Learning loss for active learning.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 93–102, 2019.
  * [19] Sergey Zagoruyko and Nikos Komodakis.  Wide residual networks.  arXiv preprint arXiv:1605.07146, 2016.