2
$\begingroup$

Imagine I'm conducting an ongoing poll asking people's favourite animal out of a list of animals, [cat, dog, penguin, chimpanzee, ...] etc.

I want to provide an interface that lets people query this poll data to see the relative popularity of each animal by different demographics. For example, querying the general population might reveal the plurality of respondents (36%) prefer penguins, but querying the 18-25 age-bracket might the plurality of respondents in that cohort (41%) prefer cats.

It's desirable to preserve the privacy of my respondents' animal preferences as much as possible. However, an attacker may be able to use prior knowledge of a given respondent to deduce their response by asking a specific enough series of queries.

I wish to limit an attacker's ability to do this by noisifying the data presented to those querying the data. As such, I want a procedure that pseudorandomly adds or removes a fraction of a percentage point from each category, but preserves their relative ordering. I also wish this procedure to be deterministic over the same set of data (though this can easily be achieved by using a fixed seed in the pseudorandom procedure).

Formally, I want

$$f : \mathbb R_{>0}^n \rightarrow \mathbb R_{>0}^n;\;\; f(\mathbf{x}) = \mathbf{y}; \;\; |\mathbf{x}| = |\mathbf{y}| = 1$$

where $\mathbf{x}$ is the vector of proportions of each category.

One naive way of going about this would be to simply add a pseudorandom Gaussian noise vector to the original vector and then renormalise. This poses at least two problems:

1) the "zero problem": if a cohort has zero people who like cats, how should the noisification procedure treat this? I'm inclined to say it should maintain the value at zero, but I can't think of a principled way of achieving this

2) the variance of the noise should ideally be the same for all elements in the vector, but any obvious procedure for forcing positivity would all typically result in smaller variance of noise for smaller values, so the noisification would end up making large values larger and small values smaller after renormalisation.

I feel like this should be a problem people have encountered before, but I can't find it in the literature.

$\endgroup$
4
  • 1
    $\begingroup$ Maybe this could help: stats.stackexchange.com/questions/144410/… $\endgroup$ – Eskapp Dec 21 '16 at 15:13
  • 1
    $\begingroup$ About the "0-problem", as you are working on a poll, it's a sample supposed to represent a larger population. So having a 0 doesn't mean that the proportion in the larger population is 0. The same way that having 50% in the poll doesn't mean it is exactly 50% in the larger population. It makes no sense to me to allow noise on all proportions values but 0... $\endgroup$ – Eskapp Dec 21 '16 at 22:34
  • 1
    $\begingroup$ @Eskapp - I think you're right in the general case. It makes more sense to not allow noise on zero values for my specific use-case, which I haven't elaborated upon, as I anticipate each sample to be highly representative of the base population. $\endgroup$ – R Hill Dec 22 '16 at 16:14
  • 1
    $\begingroup$ As an example of where else it might make sense to not add noise to zero-valued categories: if the question were "which of the following categories of goods do you purchase most frequently?" and it included the category "feminine hygiene products", breaking this down by gender and noisifying it would show some completely artificial proportion of men who frequently buy feminine hygiene products. $\endgroup$ – R Hill Dec 24 '16 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.