Building a RAPPOR with the Unknown: Privacy-Preserving Learning of Associations and Data Dictionaries

Giulia Fanti; Vasyl Pihur; Úlfar Erlingsson

Source-linked AI summary

Building a RAPPOR with the Unknown: Privacy-Preserving Learning of Associations and Data Dictionaries

Giulia Fanti, Vasyl Pihur, Úlfar Erlingsson

arXiv:1503.01214v1Mar 4, 2015cs.CR

TL;DR

The paper addresses RAPPOR’s need for known dictionaries and its inability to learn associations among multiple reported variables. It introduces joint-distribution and unknown-dictionary decoding methods, with simulations and real-world examples demonstrating practical efficacy. The approach can learn associations and frequent unknown string values while preserving local differential privacy, but joint estimation imposes substantial computational costs.

Problem
RAPPOR originally requires a known string dictionary and focuses on marginal distributions, limiting analysis when dictionaries or relationships among variables are unknown.
Method
The paper augments RAPPOR with joint-distribution estimation and substring-based decoding to learn frequent unknown strings.
Results
The methods estimate joint distributions and learn data dictionaries of frequent unknown values, with efficacy demonstrated through simulations and real-world examples.
Takeaways & Limitations
Privacy-preserving statistical learning can address multiple levels of unknowns for discrete, string-valued variables collected through locally differentially private systems.
Takeaways & Limitations
Joint estimation is computationally costly because EM iterations depend on previous iterations and the entire dataset, creating memory and computational loads at large scale.

Abstract

from arXiv · show

Techniques based on randomized response enable the collection of potentially sensitive data from clients in a privacy-preserving manner with strong local differential privacy guarantees. One of the latest such technologies, RAPPOR, allows the marginal frequencies of an arbitrary set of strings to be estimated via privacy-preserving crowdsourcing. However, this original estimation process requires a known set of possible strings; in practice, this dictionary can often be extremely large and sometimes completely unknown. In this paper, we propose a novel decoding algorithm for the RAPPOR mechanism that enables the estimation of "unknown unknowns," i.e., strings we do not even know we should be estimating. To enable learning without explicit knowledge of the dictionary, we develop methodology for estimating the joint distribution of two or more variables collected with RAPPOR. This is a critical step towards understanding relationships between multiple variables collected in a privacy-preserving manner.

I. INTRODUCTION

RAPPOR provides local differential privacy for collecting population statistics, but its original design assumes single-variable analysis and a known string dictionary. This paper addresses both limitations with joint-distribution tools and an algorithm for discovering frequent unknown strings.

Background: RAPPOR uses randomized response to protect individual reports while allowing aggregators to estimate population distributions.Users hash strings into Bloom filters, apply permanent randomized response, and generate instantaneous randomized responses for collection over time.
Limitations of original RAPPOR: The original RAPPOR workflow assumes that aggregators analyze one variable and know possible string values in advance.These assumptions limit applicability when relationships among attributes matter or when client-side strings are unknown.
Contributions: The paper introduces statistical tools for estimating joint distributions, variances, and independence between multiple RAPPOR-reported variables.The joint-distribution toolbox includes an expectation-maximization-based inference algorithm.
Contributions: The paper introduces an algorithm that estimates string distributions without knowing the possible values beforehand.It reports noisy representations of multiple substrings and uses joint distributions to learn the dictionary of frequent underlying strings.
Evaluation and scope: The methods are demonstrated through simulation and real-world examples and can extend beyond the RAPPOR encoding and decoding algorithms.The authors state that the methods apply to locally differentially private systems learning discrete, string-valued distributions.

III. ESTIMATING JOINT DISTRIBUTIONS

Single-variable estimation can be insufficient when associations among privacy-preserving reports matter. The paper therefore develops a general approach for estimating joint distributions from two or more RAPPOR-collected variables.

Motivation: Estimating only one variable may be insufficient when aggregators need associations between multiple privacy-preserving variables.The paper motivates this need with relationships between advertisements and recently installed software.
Approach: The proposed approach estimates the joint distribution of two or more variables collected through RAPPOR.These techniques are also used later to estimate distributions over unknown dictionaries.
Approach: Inference uses the expectation-maximization algorithm to produce unbiased estimates of joint probabilities.The algorithm is suited to settings where true values are unavailable and only noisy representations are collected.

A. Estimating Joint Distributions with the EM Algorithm

The EM procedure estimates unknown joint probabilities from pairs of noisy RAPPOR reports. It uses Bayes-based posterior assignments and iteratively updates the joint distribution until convergence.

Setup: The method estimates the joint distribution of two variables from noisy report pairs collected from independent clients.The Basic RAPPOR presentation uses observed representations X′ and Y′ for underlying variables X and Y.
Posterior estimation: Bayes’ theorem combines current joint-probability estimates with the likelihood of observing each pair of noisy reports.Conditional independence of the noisy reports given the true values factorizes the likelihood into separate RAPPOR probabilities.
Iteration: EM initializes a uniform joint distribution, repeatedly updates its cell estimates, and stops when successive estimates differ by less than a threshold.The update is performed until convergence under the stated maximum-change criterion.
Guarantee: The algorithm converges to maximum-likelihood estimates of the joint probabilities that are asymptotically unbiased.This establishes the statistical target and asymptotic property of the procedure.

B. Handling the “Other” category

When only top marginal categories are detected, undiscovered values must be represented explicitly as “Other” categories. The paper estimates their report distributions so EM can retain unbiased joint-distribution estimates.

Problem: Marginal decoding identifies top categories, but the remaining “Other” categories may contain substantial probability mass and cannot be omitted.Omitting them produces badly biased joint-distribution estimates.
Problem: The difficulty is estimating the probability of a report generated by any category outside the selected top categories.The resulting joint table includes an additional row and column for the two “Other” categories.
Estimation: The method estimates “Other” report probabilities from the known top categories, their frequencies, and expected bit counts.The calculation uses observed bit-setting counts and Bloom-filter representations.
Result: Including “Other” categories in EM yields unbiased estimates of the joint distribution.The paper applies the resulting procedure to the augmented contingency table.

C. Estimating the Variance-Covariance matrix

The paper derives variance estimates for RAPPOR-based joint-distribution estimates and uses them to construct confidence intervals and test independence. Because RAPPOR provides estimated cell frequencies rather than exact counts, it replaces the standard χ2 statistic with a variance-aware quadratic form.

The asymptotic distribution of the maximum-likelihood estimates is Gaussian with covariance determined by the information matrix.The covariance estimate quantifies uncertainty in the estimated joint proportions.
The covariance estimate enables 95% confidence intervals, tests for proportions differing from zero, and an overall association test.These procedures use the uncertainty captured by the variance-covariance matrix.
The observed information matrix is obtained from second derivatives of the observed-data log-likelihood evaluated at the maximum-likelihood estimates.Its inverse supplies the estimated variance-covariance matrix.
The diagonal entries of the estimated covariance matrix provide variance estimates for individual joint-proportion estimates.These variances support uncertainty assessment for each estimated cell.
The standard χ2 test is inappropriate because RAPPOR yields estimated means and covariance matrices rather than exact co-occurrence counts.The paper therefore develops a different statistic for testing independence.
The proposed statistic compares estimated joint proportions with products of estimated marginals using the estimated covariance matrix.Under no association, it follows a χ2 distribution with (m−1)(n−1) degrees of freedom.
The independence procedure estimates the joint distribution and covariance matrix with EM, then compares its statistic T with a χ2 critical quantile.The null is rejected when T exceeds q1−α.

E. Simulation Results

The simulation evaluates RAPPOR joint-distribution estimation on two variables with many categories. Ignoring the residual “Other” categories produces biased estimates, whereas modeling them yields unbiased joint and conditional estimates.

The simulation uses variables X and Y with 100 unique categories and discretized Zipfian marginal distributions.The truncated joint distribution is specified in Table I.
With 100,000 reports, the method estimated the frequencies of 15 top categories for each variable on average.The association analysis then selected the top five categories from each variable.
Ignoring “Other” categories produced poor estimates for both true joint frequencies and conditional frequencies.The conditional estimates regressed toward the mean: high values were underestimated and low values overestimated.
Accounting for “Other” categories produced unbiased estimates of the true joint frequencies.The estimated joint distribution becomes a 6×6 table.
Accounting for “Other” categories also produced 25 unbiased estimates of conditional frequencies.This corrects the regression-to-the-mean pattern observed when residual categories were omitted.

F. Real-World Example: Google Play Store Apps

The paper applies its RAPPOR association analysis to mobile-app category and payment data. It estimates a 30×2 contingency table, obtains confidence intervals with proper coverage, and detects significant differences in paid rates across categories.

The real-world example uses public metadata for 200,000 Google Play Store apps, recording 30 app categories and whether each app is free or paid.These variables form a 30×2 contingency table.
The analysis generates simulated Basic RAPPOR reports using 30-bit category reports and 1-bit payment-model reports.The resulting reports are used to estimate the joint contingency table.
The estimated 30×2 cell frequencies have 95% confidence intervals with proper coverage in all cases.The plotted cells distinguish free and paid items by category.
The estimated paid-rate ratio follows the true rates closely for most app categories, although it is less stable than joint-frequency estimates.The ratio is the category-specific paid proportion divided by the overall category proportion.
T = 107.093 and p = 6.9523e−11, indicating statistically significant differences in paid rates between app categories.The observed category rates range from 30% to 4%.
Unknown dictionary: Unknown-string analysis collects noisy reports for the full string and randomly selected n-grams, then uses n-gram co-occurrences to construct candidate strings.After learning a candidate dictionary, regular marginal RAPPOR analysis estimates full-string frequencies.
Unknown dictionary: The unknown-dictionary procedure allocates one-third of the privacy budget to the full-string report and the remaining two-thirds equally across two n-grams.The n-grams are sampled at distinct random positions.
Unknown dictionary: Truncating strings longer than M permanently loses information in their tails, while collecting more n-grams reduces per-n-gram privacy and increases co-occurrence complexity.These design trade-offs constrain unknown-dictionary estimation.

A. Building the Candidate Set

The candidate-set pipeline decodes frequent n-grams, estimates their pairwise joint distributions, and uses a k-partite graph to assemble full-string candidates. Thresholding and clique finding identify plausible strings, while semantic filtering can remove invalid candidates.

A. Building the Candidate Set: The aggregator first builds an n-gram dictionary, separates reports by position, and decodes common n-grams with marginal RAPPOR analysis.The n-gram dictionary contains D^n possible n-grams when the alphabet has D elements.
A. Building the Candidate Set: Pairwise joint analyses select n-gram pairs whose estimated frequency exceeds a threshold δ.The joint analyses use significant n-grams discovered during marginal decoding.
A. Building the Candidate Set: The threshold δ is chosen so uncorrelated n-gram pairs usually fall below it while reducing false negatives relative to a higher noise-discrimination threshold.The passage states that 1.64δ is the threshold expected to distinguish strings from noise, while a slightly lower threshold is used deliberately.
A. Building the Candidate Set: The aggregator constructs a k-partite graph whose edges connect valid n-gram pairs from different positions, then searches for fully connected k-cliques.Each clique corresponds to a full-string candidate, and k = M/n.
A. Building the Candidate Set: Naive clique finding can create a storage and computation bottleneck because the candidate count may grow exponentially with the number of collected bigrams.An approach developed for k-cliques in k-partite graphs is described as outperforming traditional branch-and-bound algorithms.
A. Building the Candidate Set: Candidate strings can also be filtered using semantics or prior knowledge, such as removing strings that violate strict URL encoding restrictions.The example removes candidates containing spaces in the middle of URLs.

B. Testing Candidate Strings

After constructing a candidate dictionary, the method applies marginal RAPPOR inference to full-string reports, removing low-frequency false positives. This stage trades broader privacy protection for incomplete recovery, especially on long-tailed distributions.

B. Testing Candidate Strings: Marginal inference uses full-string reports and the candidate dictionary C to estimate string frequencies as in the original RAPPOR analysis.False-positive candidates are removed when decoding shows negligible frequency.
B. Testing Candidate Strings: Full-string reports use privacy parameter ϵ/3 instead of ϵ, providing stronger privacy guarantees but generally imposing a substantial penalty for collecting two additional n-grams.The effect on final results depends on the true distribution.
B. Testing Candidate Strings: The estimated candidate set usually includes the most frequent candidates but can miss less frequent strings because privacy noise obscures them.For long-tailed distributions, a significant portion of distribution mass may fall below the noise floor.
B. Testing Candidate Strings: Many false-positive candidates may remain, forcing more conservative statistical testing when the number of tests is large.The resulting output is estimated marginal weights for the most common dictionary strings.

V. RESULTS

The paper evaluates unknown-dictionary RAPPOR decoding through simulations, measuring distribution accuracy, false negatives, computational cost, and threshold selection. Results show that larger n-grams improve estimates, while candidate-graph thresholds trade accuracy against computational complexity.

Efficiency: The EM phase has complexity O(N|D|nr), and increasing sample sizes can create memory and runtime constraints despite opportunities for parallelization.
100,000 simulated strings were drawn from a discretized Zipfian distribution and encoded as 128-bit RAPPOR reports for evaluation.
Hellinger distance measures recovered-distribution error, including cases where estimated and true distributions have different supports.
Accuracy and n-gram length: Larger n-grams produced better dictionary estimates for fixed string lengths because each report captures a larger fraction of the string.
Accuracy and n-gram length: False negatives caused the observed distribution discrepancies, with no false positives in the Figure 8 trials.
Accuracy vs. computational costs: Larger graph thresholds reduce candidate edges and computational load but increase the number of missed strings.
Accuracy vs. computational costs: The analytically computed threshold based on randomized-response noise appeared close to the simulated optimum.

D. Estimating the Dictionary in Real-World Settings

A URL experiment tests dictionary recovery under progressively less prior knowledge and a split privacy budget. The method recovers only the most frequent strings without a dictionary, while stronger prior knowledge recovers more strings; the broader accuracy discussion emphasizes substantial detection limits.

The real-world-style experiment sampled 1,000,000 clients from a distribution over 100 URLs and decoded reports with varying dictionary knowledge.
The experiment used full-string reports and two randomly chosen bigrams, with overall privacy parameter ϵ = 4.39 and per-report collection at ϵ/3 = 1.46.
With perfect dictionary knowledge and ϵ = 4.39, original RAPPOR detected and estimated frequencies for 75 unique strings.
Without prior dictionary knowledge, final marginal analysis discovered the top five strings and estimated their frequencies quite accurately, with one false positive.
Using trigrams produced 185 candidate strings, after which final marginal analysis found only two strings with no false positives.
The method does not detect many population strings, and unknown-dictionary estimation can require roughly 300 million samples for six-letter words in the worst case.

VI. RELATED WORK

The paper extends RAPPOR beyond its original practical assumptions by addressing unknown dictionaries and multivariate associations while preserving its local privacy guarantees. It also identifies decoding cost and privacy-budget allocation as remaining deployment challenges.

Prior work largely studied continuous variables, whereas this paper addresses discrete string distributions and their practical estimation challenges.
The proposed methods learn unknown client-side strings and their frequency distributions without requiring the dictionary in advance.
The enhancements address RAPPOR’s inability to learn associations and its requirement for a known string dictionary without changing its fundamental mechanism or weakening local differential privacy.
Joint estimation is the main decoding bottleneck because EM iterations depend on previous iterations and the entire dataset, increasing memory and computational loads for very large user populations.
The experiments allocate one-third of the privacy budget to each full-string and two n-gram reports, although this allocation is not necessarily optimal for estimation accuracy.

APPENDIX A TESTING FOR ASSOCIATION: VALIDATION

The appendix validates the proposed independence statistic under a constructed null distribution and examines decoding under geometric and stepwise string distributions. The test behaves as expected, while stepwise distributions produce less accurate estimates because mass falls below the noise threshold.

Testing for Association: The validation generates 100 RAPPOR trials from independent variables, each with K = 10,000 data points, then jointly decodes reports to compute the proposed statistic.
Testing for Association: The independence test’s observed and expected quantiles align with a linear fit of slope 1 and intercept 0, supporting its desired null-test behavior.
Different Distributions: The simulations use N = 100,000 reports over 100 categories with p = 0.25, q = 0.75, f = 0, and 128-bit Bloom filters.
Different Distributions: For a truncated geometric distribution with p = 0.3, estimate accuracy differs little from the Zipfian distribution used elsewhere in the simulations.
Different Distributions: For the stepwise distribution, estimates are less accurate because substantial probability mass lies below the noise threshold and accumulates in the “Other” category.