Active learning holds promise of significantly reducing data annotation costs while maintaining reasonable model performance. However, it requires sending data to annotators for labeling. This presents a possible privacy leak when the training set includes sensitive user data. In this paper, we describe an approach for carrying out privacy preserving active learning with quantifiable guarantees. We evaluate our approach by showing the tradeoff between privacy, utility and annotation budget on a binary classification task in a active learning setting.
Preserving data privacy is an essential tenet required to maintain the bond of trust between consumers and corporations. Consumers expect their data to remain secure while being used to design better services for them without compromising their identities – especially while carrying out sensitive transactions and interactions. We define these potentially compromising and personally identifiable data as sensitive data. Annotated data drives the machine learning economy and sensitive data holds the key to building richer experiences for users interacting with modern AI interfaces. However, in a bid to get annotations, sensitive data in the wrong hands could lead to irreparable damage in terms of reputation and trust between data holders and their users.
This potential data transfer deserves greater monitoring in
the era of human powered crowdsourcing and active learning.
As niche classification tasks arise to power new applications,
they often lack an abundance of pre-annotated datasets. With
active learning, the learner can select a subset of the available
data points to be annotated. This can exponentially reduce
In this paper, we argue that, for non-public datasets, the cost of learning the true labels should also factor in the privacy of the information contributed by the data owners to the data custodians. As a result, the active learning condition (beyond simply selecting the best examples) becomes
In this section, we present an introduction to active learning and the privacy challenge of outsourcing queries to the crowd. We then describe k-anonymity, its shortcoming in providing an adequate privacy model for active learning and how this can be improved with differential privacy.
The central premise of active learning is that a model is able
to perform as well with less data, if a learner can select the
training examples that provide the highest information
Various strategies have been proposed to implement an
active learner. One is uncertainty sampling
The main privacy issue with active learning stems from the
need to scale the annotation process by crowdsourcing the
labels via an open call
To achieve k-anonymity when the size of the frequency set is less than a desired k, the attributes are anonymized by either generalizing or suppressing the information. For example, marital status attributes listed as married, divorced or widowed are generalized as once married, while the ethnicity is redacted as *****.
Despite its promise, k-anonymity has fundamental
challenges, some of which are exacerbated by our unstructured
data domain. First,
Therefore, by ‘hiding in the crowd’ of k, a user has received some assurance from k-anonymity that their sensitive query will not be outsourced from the active learning model unless it passes a meaningful threshold. However, stronger formal privacy guarantees are required to demonstrate that given the user’s query, an attacker cannot decide where it came from with certainty. With k-anonymity, we are unable to directly quantify a privacy loss value, nor state the bounds of the guarantee of this loss. These two quantities are obtainable from a differential privacy model which we now describe.
Differential Privacy To motivate our discourse on why
we need stronger privacy guarantees than what k-anonymity
provides, we consider a hypothetical scenario: Would a user
be comfortable asking an AI agent a sensitive question, with
the knowledge that the question will be possibly used to
further train agent’s learning model? We denote the training
data available to the model before the user submission as D,
and the data after the user question as D0. These are adjacent
datasets differing on only one record. We posit that a user c
will be comfortable if (1) Q(D) = Q(D0) where Q is a query
over the dataset; and (2) P (S(c)|D0) = P (S(c)) where S
is a user secret. These 2 points are articulated in Dalenius’s
Desideratum
Anything that can be learned about a respondent from the statistical database should be learnable without access to the database However, we can’t make these exact guarantees because datasets are meant to convey information and they will have no utility if these points were true.
What Differential Privacy
With this, we state that, a randomized algorithm M : NX ! C that receives as input a dataset D with records from a universe X and outputs an element from C is (", )differentially private if for every pair of databases D and D0 differing in one record and every possible set of outputs C ✓ C we have
Pr[M(D) 2 C] e"Pr[M(D0) 2 C] + (1)
The parameter accounts for a < 1/||D||1 relaxed chance of the ✏ guarantee not holding – otherwise, it will be equivalent to just selecting a random sample on the order of the size of the dataset. One benefit of the differential privacy model is that it has a quantifiable, non binary value for privacy loss which helps in deciding to comparatively select one algorithm over the other. We observe an output of the random algorithm C ⇠ M (D) where we believe that C was more likely produced by D and not D0, then the privacy loss from the query that yields C on an auxiliary input x is: L(C; M, x, D, D0) d=ef ln(
P r[M(D) = C] P r[M(D0) = C] ) (2)
So we surmise that differential privacy promises to prevent a user from sustaining additional damage by including their data in a dataset; and the privacy loss obtained is ✏ with probability 1 .
A common method for making the results of a statistical
query differentially private involves adding Laplacian noise
proportional to either the query’s global sensitivity
Research has however shown that apart from providing
reasonable and well understood protection from inadvertent
exposure
This section introduces our proposed framework for carrying out active learning with privacy guarantees on queries that are sent to an external oracle. It presents the task we try our approach on, highlights the considerations that drive our choices and lays out a high level pseudo-code of our approach.
Our task consists of a very large dataset of user queries
U = {u1, ..., un} that represent the user intent (we map
the queries to the intent and do not extract specific
quasiidentifiers in order to prevent leakages from un-captured
sensitive attributes). Our pipeline consists of an active
learning model which learns a binary classifier, predicting if a
user intent belongs to a specified class or not. The model
is bootstrapped with a golden set of user queries and their
associated intents. Subsequent queries from a fixed pool are
added to a RANKEDEXAMPLEPOOL where they are ordered
by confidence/uncertainty
To train the model, it first draws on the golden set, then we make a next example call to draw an uncertain query from the pool with the criteria that knowing the accurate intent of this query gives the best performance increase to the model while preserving privacy. The query is then outsourced to external annotators and the annotated labels are re-incorporated into the model training process.
Given the size and projected scale of our dataset (⇡ 109 queries), we decide to employ randomized probabilistic algorithms in estimating if a query satisfies k-anonymity. Compute and memory resources are thus freed up for training and retraining the model rather than maintaining the frequency and cardinality of incoming queries. Each algorithm (detailed below) is adjusted to prevent over-estimations which could erode the privacy guarantees. Furthermore, after a query is presumed to satisfy k-anonymity, only 1 of the k queries is sent to n external annotators to prevent an aggregation of privacy losses.
In this paper, we adopt the differential privacy algorithm
from
We take a two-stepped approach to extend k-anonymity
to yield a quantifiable differentially private active learning
model taking a cue from how
◆! 1) ; 2 = 2 1 1 (3)
Therefore, k-anonymity on our full dataset (i.e., 1 = 1)
can instead be preceded by a mechanism that samples each
row of its input with probability 2, with k-anonymity then
applied to the resulting sub-sample to yield ✏2, 2-differential
privacy for ✏2 = ln(1 + ( 2(e✏1 1))) within the bounds
2 = 2 1. Thus the effect of sampling serves to amplify
pre-existing privacy guarantees
Furthermore, we harden our k-anonymity to offer ‘safe’
k-anonymization by aggregating the queries by frequency
rather than using a distance based measure
The next sections describe: how we carry out our sampling to ensure we select useful candidates in an efficient manner, and how we estimate k-anonymity using the queries.
Given a multiset of query sets M = {U1, ..., Us} with repetitions where a given Ui is a tuple hui, ..., uki, and a sampling rate , our objective is to return a sub-sample from which to Algorithm 1: Privacy-preserving Active Learning 1 Let be the sampling rate // = 2 from (3) 2 Let k be the anonymity parameter 3 Let l be number of samples for variance calculation Data: Input multiset of samples x with unknown labels y as: U = {x1, y1}, ..., {xn, yn}
Result: U 0 filtered private multiset 4 5 Bootstrap AL probablistic model P✓ with labeled utterances L 6 Retrieve random sub-sample U 0 of size n 7 Pool creation: to add queries to the
RANKEDEXAMPLEPOOL 8 for {x, y} 2 U 0 do 9 retrieve freq(x); 10 if freq(x) k then 11 retrieve variance x = var(P✓ (yˆ|x) : 1..l) on u; // computed using l draws add hx, xi to RANKEDEXAMPLEPOOL; 12 13 else 14 remove {x, y} from U 0; 15 end 16 end 17 18 Acquire labels for top examples sorted by x descending as {yˆ1, ..., yˆnˆ} 19 Set U 0 to be (x1, yˆ1), ..., (xnˆ, yˆnˆ) 20 Update model: draw the next training example from U 0 over x 21 get xˆ = argmaxu 1 P✓ (yˆ|x); - # sample we are least confident of
retrain learning model using {xˆ, yˆ} 22 23 24 return U 0 carry out k-anonymization before training our active learner. Let n be the number of distinct query sets —{U1, ..., Us}— with elements {e1, ..., en}. For a very large dataset size s, we seek to estimate nˆ using only m registers where m << n. The number of distinct queries in our sample set therefore become nˆ.
To estimate the cardinality nˆ, we utlize the
HYPERLOGLOG algorithm by
For each incoming Ui : hui, ..., uki, a hash h(Ui) is computed and converted to base 2. The b least significant bits are used to identify the register location to modify, where 2b = m or log2 m. With the remaining bits w, a count p(w) is made of the number of running 0s up to the leftmost 1. For a very large, uniformly distributed multiset of random numbers, 2 raised to the maximum value of p(w) gives a wide approx1Values taken for the Redis implementation of HYPERLOGLOG - http://antirez.com/news/75 imate of the cardinality. To correct this, HYPERLOGLOG breaks the multiset into subsets and uses the harmonic mean of the subsets.
After determining our sample size, the next step is to draw a random set of unique samples without replacement up to nˆ. We keep each element in the dataset with probability . The ensuing sub-sample represents the new dataset in our RANKEDEXAMPLEPOOL from which we will carry out our k-anonymization.
frequency
Given a multiset of query sets M = {U1, ..., Us} with
repetitions such that the frequency of Ui is fUi and Ui is a
tuple hui, ..., uki. For a very large dataset size s, we seek to
ˆ
estimate fUi using sub-linear space. To estimate the query
frequency, we use the COUNT-MEAN-MIN with conservative
update
Therefore after initial pre-sampling step, we select only queries which occur at least k times. These queries are then added to the RANKEDEXAMPLEPOOL where the next example is drawn based on the element with the highest uncertainty measure. The benefit of using the frequency to satisfy k-anonymity rather than using partitioning, clustering and recoding, or distance based algorithms, is to prevent attacks that rise from an attackers a-priori knowledge of a dataset. For example, a cluster of k with one sensitive or extreme outlier (e.g., a cluster of incomes within zip code with one UHNW outlier becomes easily identifiable by an attacker even though the aggregation was based on nearest neighbors).
Our work seeks to demonstrate quantifiable privacy preserving guarantees in an active learning setting by taking a presampling approach before carrying out k-anonymization. We evaluate our approach on an internal dataset used for intent classification on voice devices.
The Intent Classifier dataset consists of a subset of queries from February 2018. The dataset is used to train a model which determines a binary intent for a user. The dataset consists of 2.5M queries comprising 58K distinct data points. Each record contains a user query and a label indicating if it is categorized as a POSITIVE or NEGATIVE intent query. Part of the dataset has also been previously discussed and described by (Yang et al. 2018). Figures 1c and 1d show the nature of the dataset with a histogram and plot of the frequency distribution of the queries. As expected with textual data, there is a long tail of queries which were observed just once (making up ⇡ 60% of the dataset). The dataset consists of 63% of queries labelled as POSITIVE intents vs 27% being NEGATIVE.
The experiment task was binary intent classification in an active learning setting. We created a new baseline model which predicts POSITIVE and NEGATIVE intents. For the experiments, the model was initially bootstrapped with 1, 000 labeled examples. The active learner then queries a data pool to get a batch of additional training examples to improve the model. The active learning strategy was uncertainty sampling based on confidence scores.
The confidence and uncertainty scores for the active learning model were obtained from a Bayesian deep learning model described in (Yang et al. 2018) where model uncertainty, quantified by Shannon entropy is U (x) =
Pc( T1 Pt pˆc) log( T1 Pt pˆc) and T1 Pt pˆc is the averaged predicted probability of class c for x, sampled T times by Monte Carlo dropout. A histogram of the confidence and uncertainty scores can be seen in Figures 1a and 1b.
We simulated the probability of the crowd annotators returning the correct answers to the requested queries by drawing from a normal distribution with mean centered at 0.65 and standard deviation 0.01 (see (Yang et al. 2018)’s Figure 2(a) for more).
To evaluate our results, we compared the annotation accuracy between the baseline model, and the models trained with active learning and our privacy preserving model. We vary the sub-sampling parameter and the anonymization factor k while training our model and recording its accuracy. We set the evaluation data at 5, 000 samples (i.e., about 10% of the dataset). We also provide privacy guarantee values from numerical computations of ✏ and and highlight in the appendix, what values of k and provide those levels of guarantees.
Baseline condition train standard classification model. Sub-sampling parameter = 1, anonymization factor k = 1 i.e., using the entire dataset Experiment conditions train classification model using privacy preserving active learning. Sub-sampling parameter varied at = {0.1, 0.3, 0.6, 0.9}, anonymization factor varied at k = {1, 20, 100, 200, 500}
The results of our experiments are presented in Figures 2, 3 and 4. Our findings provide insight to the tradeoffs between privacy, utility and our annotation budget. (a) Distribution of confidence (b) Distribution of uncertainty scores for each unique query scores for each unique query (c) Histogram of frequency dis- (d) Log frequency distribution of tribution queries
Figure 2 highlights the privacy–utility tradeoff which occurs as a result of varying and k. As expected, as the value of k, gets smaller, i.e., by selecting more items in the tail of the dataset, we are able to improve the accuracy of our model. This however has the effect of degrading our privacy guarantees. Similarly, by providing privacy amplification by subsampling, the utility of our model suffers. Figure 2 paints a wholistic picture of this by showing how by tuning the values of and k, we can arrive at the same values of accuracy. Figure 3 describes how our annotation budget changes for different privacy settings. With a stronger privacy model, we incur less cost as a function of less annotation requests. By reading across the graph, we also discover that the same budget can be realized from different privacy configurations: e.g., by subsampling with = 0.1 and selecting k = 20, we incur the same budget as = 0.3 and k = 100 and therefore, the same accuracy (from Figure 2 above). We established from Figure 2 and Figure 3, the relationship between privacy and accuracy, and between privacy and our annotation budget. Since we can obtain the same level of accuracy and budget requirements from different parameter values, Figure 4 highlights how an increase in budget affects our overall model accuracy. Increasing the budget initially accelerates the improvement of our model, however, the utility gains quickly slow down. For example, after 30, 000 labels, we do not see any significant increase in model accuracy.
These results can serve as a guideline in selecting appropriate privacy parameters for different annotation budgets in a way that is more representative of the dataset. For example, for a fixed annotation budget, you can reduce to select more data points from the tail of the dataset (i.e., a smaller k). This variation can also be done by starting with a target accuracy score and varying and k. The results also demonstrate that by sacrificing some utility gains, we can make stronger privacy guarantees and reduce our annotation budget when carrying out active learning.
We now briefly revisit our results in the light of our hypothesis. We also discuss the limitations of our process, its implication to the broader discourse on privacy and machine learning and conclude with future work.
We apply the approach from
Our results show that by taking a small performance hit, we can achieve similar accuracy scores with a smaller annotation budget and stronger privacy guarantee. One limitation however is that we have only reported results on a binary classification task. We are currently expanding our approach by designing a new algorithm for differential privacy on text. We show that the accuracy loss increases as task complexity increases. Therefore, if we were to apply the approach in this work to other NLP tasks, e.g. multi-class classification or question answering, we will expect the accuracy loss to be greater.
Another limitation of our approach and potentially other
k parameter based approaches (
We believe that this is an area worthy of further research in order to further quantify the true cost of privacy in crowdsourcing and machine learning. We have already begun further work to address two of the limitations reported in this current paper.
Table 1 lays out a grid of ✏, scores and the corresponding sampling parameter and anonymization factor k required to satisfy that level of (✏, )-differential privacy. The shaded region presents a ⇥ k high level view of how to achieve a desired level of privacy.
A few insights can be gleaned from the results, the most obvious being that strong privacy requirements, (indicated by small ✏ and scores as we traverse the table towards the bottom left corner), require a higher anonymization factor k and smaller sampling rate . This is also observed by the fact that lowering the k factor only preserves privacy at the highest displayed ✏ value of 1.0 and = 1 ⇥ 10 6 (at the top right corner of the table).
Observing individually, we also note that, when k and ✏ are at fixed values, as decreases, i.e., to obtain stronger privacy guarantees, we need to lower the sampling rate . This indicates as decreases, privacy guarantees increase. Similarly, observing k by fixing the values of and ✏, demonstrates that increasing k improves our privacy guarantees. [Soria-Comas et al. 2014] Soria-Comas, J.; Domingo-Ferrer, J.; Sa´nchez, D.; and Mart´ınez, S. 2014. Enhancing data utility in differential privacy via microaggregation-based kanonymity. The VLDB Journal 23(5):771–794. [Sweeney 2002] Sweeney, L. 2002. k-anonymity: A model for protecting privacy. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 10(05):557–570. [Yang et al. 2018] Yang, J.; Drake, T.; Damianou, A.; and Maarek, Y. 2018. Leveraging crowdsourcing data for deep active learning an application: Learning intents in Alexa. In Proceedings of the 2018 World Wide Web Conference on World Wide Web, 23–32. International World Wide Web Conferences Steering Committee. [Zhang et al. 2016] Zhang, S.; Yang, G. H.; Singh, L.; and Xiong, L. 2016. Safelog: Supporting web search and mining by differentially-private query logs. In 2016 AAAI Fall Symposium Series. INTRODUCTION RESULTS