PROBABILISTIC INFERENCE IN DIFFERENTIALLY PRIVATE SYSTEMS

• US 20110238611A1
• Filed: 03/23/2010
• Published: 09/29/2011
• Est. Priority Date: 03/23/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Williams, Oliver M. C., McSherry, Frank D.
• Granted Patent: US 8,639,649 B2
• Time in Patent Office: Days
• US Class Current: 706/52
• CPC Class Codes: G06N 5/04 Inference or reasoning models

Abstract

Given that a differentially private mechanism has a known conditional distribution, probabilistic inference techniques may be used along with the known conditional distribution, and generated results from previously computed queries on private data, to generate a posterior distribution for the differentially private mechanism used by the system. The generated posterior distribution may be used to describe the probability of every possible result being the correct result. The probability may then be used to qualify conclusions or calculations that may depend on the returned result.

Claims

1. A method comprising:

generating a result using a differentially private computation from a private data set by a computing device;

retrieving a posterior distribution for the differentially private computation by the computing device; and

providing the posterior distribution by the computing device.

2. The method of claim 1, further comprising providing the result.

3. The method of claim 1, further comprising:

determining a conditional distribution of the differentially private computation; and

inferring the posterior distribution using the conditional distribution.

4. The method of claim 3, wherein inferring the posterior distribution using the conditional distribution comprises:

retrieving a plurality of results from previous executions of the differentially private computation; and

inferring the posterior distribution using the conditional distribution and the plurality of results using probabilistic inference.

5. The method of claim 4, wherein using probabilistic inference comprises using Markov Chain Monte Carlo methods.

6. The method of claim 3, wherein the conditional distribution is one of a Laplacian distribution or a Gaussian distribution.

7. The method of claim 1, wherein the differentially private computation is an exponential mechanism.

8. The method of claim 1, wherein the private data set comprises census data.

9. The method of claim 1, wherein the private data set comprises medical data.

10. A method comprising:

receiving a first result at a computing device through a network, wherein the first result is generated from a second result of a private data set using a differentially private computation;

determining a conditional distribution of the differentially private computation by the computing device;

retrieving a plurality of results from previous executions of the differentially private computation;

probabilistically inferring a posterior distribution of the differentially private computation using the conditional distribution and the plurality of results by the computing device; and

providing the posterior distribution by the computing device through the network.

11. The method of claim 10, further comprising providing the first result through the network.

12. The method of claim 10, wherein the differentially private computation comprises an exponential mechanism.

13. The method of claim 10, wherein probabilistically inferring the posterior distribution comprises probabilistically inferring the posterior distribution using Markov Chain Monte Carlo methods.

14. The method of claim 10, wherein the conditional distribution is one of a Laplacian distribution or a Gaussian distribution.

15. The method of claim 10, wherein the private data set comprises census data.

16. The method of claim 10, wherein the private data set comprises medical data.

17. A system comprising:

a computing device;

a privacy integrated platform that generates a first result from a second result using a differentially private computation; and

an inference engine that;

generates a posterior distribution for the differentially private computation;

receives the generated first result; and

provides the generated first result and the generated posterior distribution.

18. The system of claim 17, wherein the differentially private computation is an exponential mechanism.

19. The system of claim 17, wherein the inference engine further determines a conditional distribution of the differentially private computation, and generates the posterior distribution for the differentially private computation using the determined conditional distribution.

20. The system of claim 19, wherein the conditional distribution is one of a Laplacian distribution or a Gaussian distribution.