-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On 09/12/14 20:20, A. Johnson wrote:
This indeed seems plausible under the powerful assumption that the underlying stat is constant.
Actually it applies to any known relative pattern, for example, that the number increases by 1 each time.
Still a very powerful assumption given the stats we're gathering.
where the additive noise is applied to the center of the first bin?
Yes, you can look at it like that.
I can see how this is better, since the underlying value gets immediately smoothed by binning. However, it does give me a weird hacky feeling...
Is this construction something that has been used before?
Well, the output here is a bin, not a number, and the “exponential mechanism” is the generalization of the Laplace mechanism to handle arbitrary output spaces (kunaltalwar.org/papers/expmech.pdf). In this case, I believe that adding Laplace noise to a bin center and then re-binning is a way to select according to the distribution that the exponential mechanism would prescribe.
I see the value in switching algorithms and doing the binning step before adding noise.
But I don't see the value of binning the result once more. In a sense, we're already binning signal + noise by cutting off the float part. I don't see what we gain by reducing resolution even more. It seems just unnecessary.
Example:
- We observe 123 things. - We round up to the next multiple of 8, so to 128. - We add Laplace noise -12.3456, obtain 110.6544, round down to 110. - Why would we round up to the next multiple of 8 again, to 112?
It should be equally hard to infer the 128 value from 110 with bin size 1 or 112 with bin size 8. Unless I'm wrong. Please prove me wrong? :)
For now, I'm going to switch algorithm order in the code and not add a second binning step.
All the best, Karsten