Exponentiell mekanism

Den exponentiella mekanismen är en teknik för att utforma differentiellt privata algoritmer. Den utvecklades av Frank McSherry och Kunal Talwar 2007. Deras arbete erkändes som en medvinnare av 2009 års PET Award for Outstanding Research in Privacy Enhancing Technologies.

Det mesta av den initiala forskningen inom området differentiell integritet kretsade kring verkligt värderade funktioner som har relativt låg känslighet för förändringar i en enskild individs data och vars användbarhet inte hämmas av små additiva störningar. En naturlig fråga är vad som händer i situationen när man vill bevara mer generella uppsättningar av fastigheter. Den exponentiella mekanismen hjälper till att utvidga begreppet differentiell integritet för att ta itu med dessa problem. Dessutom beskriver den en klass av mekanismer som inkluderar alla möjliga differentiellt privata mekanismer.

Mekanismen

Algoritm

I mycket allmänna termer mappar en sekretessmekanism en uppsättning av $n\,\!$ indata från domän ${\mathcal {D}}\,\!$ till ett intervall ${\ mathcal {R}}\,\!$ . Kartan kan vara randomiserad, i vilket fall varje element i domänen ${\mathcal {D}}\,\!$ motsvarar en sannolikhetsfördelning över intervallet ${\mathcal {R}}\ ,\!$ . Sekretessmekanismen gör inga antaganden om karaktären av ${\mathcal {D}}\,\!$ och ${\mathcal {R}}\,\!$ förutom ett basmått ${ \displaystyle \mu \,\!}$ på ${\mathcal {R}}\,\!$ . Låt oss definiera en funktion $q:{\mathcal {D}}^{n}\times {\mathcal {R}}\rightarrow \mathbb {R} \,\!$ . Intuitivt tilldelar denna funktion en poäng till paret $(d,r)\,\!$ , där $d\in {\mathcal {D}}^{n} \,\!$ och $r\in {\mathcal {R}}\,\!$ . Poängen återspeglar attraktionen hos paret $(d,r)\,\!$ , dvs ju högre poäng desto mer tilltalande är paret. Givet ingången ${\displaystyle d\in {\mathcal {D}}^{n}\,\!} ,$ är mekanismens mål att returnera en $r\in {\mathcal { R}}\,\!$ så att funktionen $q(d,r)\,\!$ är ungefär maximerad. För att uppnå detta, ställ in mekanismen ${\mathcal {E}}_{q}^{\varepsilon }(d)\,\!$ enligt följande: Definition: För valfri funktion ${\displaystyle q:({\mathcal {D}}^{n}\times {\mathcal {R}})\rightarrow \mathbb {R} \,\!} ,$ och ett basmått $\mu \,\!$ över ${\mathcal {R}}\,\!$ , definiera:

${\mathcal {E}}_{q}^{\varepsilon }(d):=\,\!$ Välj $r\,\!$ med sannolikhet proportionell mot ${\displaystyle e^{\varepsilon q(d,r)}\ gånger \mu (r)\,\!} ,$ där $d\in {\mathcal {D}}^{n},r\in {\mathcal {R}}\,\!$ .

Denna definition innebär att sannolikheten för att returnera en $r\,\!$ ökar exponentiellt med ökningen av värdet på $q(d,r)\,\!$ . Om man ignorerar basmåttet $\mu \,\!$ och sedan värdet $r\,\!$ som maximerar $q(d,r)\,\!$ har störst sannolikhet. Dessutom är denna mekanism differentiellt privat. Bevis för detta påstående kommer att följa. En teknisk detalj som bör komma ihåg är att för att korrekt definiera ${\displaystyle {\mathcal {E}}_{q}^{\varepsilon }(d)\,\!$${\displaystyle \int _{r}e^{\varepsilon q(d,r)}\times \mu (r)\,\!} ska vara$ ∫ ändlig .

Sats (differentiell integritet): ${\mathcal {E}}_{q}^{\varepsilon }(d)\,\!$ ger $( 2\varepsilon \Delta q)\,\!$ -differentiell integritet.

Bevis: Sannolikhetstätheten för ${\mathcal {E}}_{q}^{\varepsilon }(d)\,\!$ vid $r\,\!$ lika

${\frac {e^{\varepsilon q(d,r)}\mu (r)}{\int e^{\varepsilon q(d,r)}\mu (r)\,dr}} .\,\!$

Om nu en enda ändring i $d\,\!$ ändrar $q\,\!$ med högst $\Delta q\,\!$ så kan täljaren ändras vid mest med faktorn $e^{\varepsilon \Delta q}\,\!$ och nämnaren minimum med faktorn $e^{-\varepsilon \Delta q}\,\!$ . Således är förhållandet mellan den nya sannolikhetstätheten (dvs. med ny $d\,\!$ ) och den tidigare som mest $\exp(2\varepsilon \Delta q)\,\!$ .

Noggrannhet

Vi skulle helst vilja ha slumpmässiga dragningar av $r\,\!$ från mekanismen ${\mathcal {E}}_{q}^{\varepsilon }(d)\ ,\!$ för att nästan maximera $q(d,r)\,\!$ . Om vi ​​anser att $\max _{r}q(d,r)\,\!$ är $OPT\,\!$ så kan vi visa att sannolikheten för att mekanismen avviker från ${\displaystyle OPT\,\!} är låg$ så länge det finns en tillräcklig massa (i termer av $\mu$ ) av värdena $r\ ,\!$ med värdet $q\,\!$ nära optimum.

Lemma: Låt $S_{t}=\{r:q(d,r)>OPT-t\}\,\!$ och ${\displaystyle {\bar {S}}_{2t}=\{r:q(d,r)$ , vi har $p({\bar {S}}_{2t})\,\!$ är som mest $\exp(-\varepsilon t)/\mu (S_{t})\,\!$ . Sannolikheten tas över ${\mathcal {R}}\,\!$ .

Bevis: Sannolikheten $p({\bar {S}}_{2t})\,\!$ är högst ${ \displaystyle p({\bar {S}}_{2t})/p(S_{t})\,\!} ,$ eftersom nämnaren högst kan vara en. Eftersom båda sannolikheterna har samma normaliserande term så,

${\frac {p({\bar {S}}_{2t})}{p(S_{t})}}={\frac {\int _{{\bar {S}}_{ 2t}}\exp(\varepsilon q(d,r))\mu (r)\,dr}{\int _{S_{t}}\exp(\varepsilon q(d,r))\mu (r )\,dr}}\leq \exp(-\varepsilon t){\frac {\mu ({\bar {S}}_{2t})}{\mu (S_{t})}}.$

Värdet på $\mu ({\bar {S}}_{2t})\,\!$ är högst ett, så denna gräns innebär lemmasatsen.

Sats (noggrannhet): För dessa värden på $t\geq \ln \left({\frac {OPT}{t\mu (S_{ t})}}\right)/\varepsilon \,\!$ , vi har $E[q(d,{ \mathcal {E}}_{q}^{\varepsilon }(d))]\geq OPT-3t\,\!$ .

Bevis: Det följer av föregående lemma att sannolikheten för att poängen är minst $OPT-2t\,\!$ är $1-\exp(-\varepsilon t)/\mu (S_{t})\,\!$ . Enligt hypotesen, $t\geq \ln \left({\frac {OPT}{t\mu (S_{t})}}\ höger)/\varepsilon \,\!$ . Genom att ersätta värdet på $t\,\!$ får vi denna sannolikhet att vara minst $1-t/OPT\,\!$ . Multiplicering med $OPT-2t\,\!$ önskade gränsen.

Vi kan anta att $\mu (A)\,\!$ för $A\subseteq {\mathcal {R}}\,\!$ är mindre än eller lika med ett i alla beräkningar, eftersom vi alltid kan normalisera med $\mu ({\mathcal {R}})\,\!$ .

Exempelapplikation

Innan vi går in på detaljerna i exemplet, låt oss definiera några termer som vi kommer att använda i stor utsträckning under vår diskussion.

Definition (global känslighet): Den globala känsligheten för en fråga $Q\,\!$ är dess maximala skillnad när den utvärderas på två angränsande datauppsättningar $D_{1}, D_{ 2}\in {\mathcal {D}}^{n}\,\!$ :

$GS_{Q}=\max _{D_{1},D_{2}:d(D_{1},D_{2})=1}|(Q(D_{1})-Q(D_ {2}))|.\,\!$

Definition: En predikatfråga $Q_{\varphi }\,\!$ för varje predikat $\varphi \,\!$ definieras som

$Q_{\varphi }={\frac {|\{x\in D:\varphi (x)\}|}{|D|}}.\,\!$

Observera att $GS_{Q_{\varphi }}\leq 1/n\,\!$ för alla predikat $\varphi \,\!$ .

Frigöringsmekanism

Följande är tack vare Avrim Blum , Katrina Ligett och Aaron Roth .

Definition (Användbarhet): En mekanism ${\mathcal {A}}\,\!$ är $(\alpha ,\delta )\,\!$ - användbar för frågor i klass $H\,\!$ med sannolikhet ${\displaystyle 1-\delta \,\!} ,$ om $\forall h\in H\,\ !$ och varje dataset $D\,\!$ , för ${\widehat {D}}={\mathcal {A}}(D)\,\!$ , $|Q_{h}({\widehat {D}})-Q_{h}(D)|\leq \alpha \,\!$ .

Informellt betyder det att frågan ${\displaystyle Q_{h}\,\!} med stor sannolikhet$ kommer att bete sig på liknande sätt på den ursprungliga datamängden $D\,\!$ och på den syntetiska dataset ${\widehat {D}}\,\!$ . Tänk på ett vanligt problem i Data Mining. Antag att det finns en databas $D\,\!$ med $n\,\!$ poster. Varje post består av $k\,\!$ -tupler av formen $(x_{1},x_{2},\dots ,x_{ k})\,\!$ där $x_{i}\i \{0,1\}\,\!$ . Nu vill en användare lära sig ett linjärt halvsteg av formen $\pi _{1}x_{1}+ \pi _{2}x_{2}+\cdots +\pi _{k-1}x_{k-1}\geq x_{k}\,\!$ . I huvudsak vill användaren ta reda på värdena för $\pi _{1},\pi _{2},\dots ,\pi _{k-1 }\,\!$ så att maximalt antal tuplar i databasen uppfyller olikheten. Algoritmen vi beskriver nedan kan generera en syntetisk databas ${\widehat {D}}\,\!$ som gör det möjligt för användaren att lära sig (ungefär) samma linjära halvrum medan han frågar i denna syntetiska databas. Motivet för en sådan algoritm är att den nya databasen kommer att genereras på ett differentiellt privat sätt och därmed säkerställa integritet till de individuella posterna i databasen $D\,\!$ .

I det här avsnittet visar vi att det är möjligt att släppa en datauppsättning som är användbar för begrepp från en polynomisk VC-Dimension- klass och samtidigt följa $\varepsilon \,\!$ -differentiell integritet så länge som storleken på den ursprungliga datamängden är åtminstone polynom på VC-dimensionen av konceptklassen. För att formellt säga:

Sats: För vilken klass av funktioner som helst $H\,\!$ och vilken datauppsättning som helst $D\subset \{0,1\}^{k}\,\!$ såsom den där

$|D|\geq O\left({\frac {k\cdot \operatörsnamn {VCDim} (H)\log(1/\alpha )}{\alpha ^{3}\varepsilon }}+{\frac {\log(1/\delta )}{\alpha \varepsilon }}\ höger)\,\!$

vi kan mata ut en $(\alpha ,\delta )\,\!$ -användbar datauppsättning ${\widehat {D}}\,\!$ som bevarar $\varepsilon \,\!$ -differentiell integritet. Som vi nämnde tidigare behöver algoritmen inte vara effektiv.

Ett intressant faktum är att algoritmen som vi ska utveckla genererar en syntetisk datauppsättning vars storlek är oberoende av den ursprungliga datauppsättningen; i själva verket beror det bara på VC-dimensionen för begreppsklassen och parametern $\alpha \,\!$ . Algoritmen matar ut en datauppsättning av storleken ${\tilde {O}}(\operatörsnamn {VCDim} (H)/\alpha ^{2})\,\!$

Vi lånar Uniform Convergence Theorem från kombinatoriken och anger en följd av den som är anpassad till vårt behov.

Lemma: Givet varje datauppsättning $D\,\!$ finns det en datauppsättning ${\widehat {D}}\,\!$ med storlek ${\displaystyle =O(\operatörsnamn {VCDim} (H)\log(1/\alpha ))/\alpha ^{2}\,\!} så$ att $\max _{h\in H}|Q_{h}(D)-Q_{h}({\widehat {D}})|\leq \alpha /2\,\!$ .

Bevis:

Vi vet från den enhetliga konvergenssatsen att

${\begin{aligned}&\Pr \left[\ ,\left|Q_{h}(D)-Q_{h}({\widehat {D}})\right|\geq {\frac {\alpha }{2}}{\text{ för några }}h \in H\right]\\[5pt]\leq {}&2\left({\frac {em}{\operatörsnamn {VCDim} (H)}}\right)^{\operatörsnamn {VCDim} (H)} \cdot e^{-\alpha ^{2}m/8},\end{aligned}}$

där sannolikheten är över fördelningen av datamängden. Om RHS är mindre än ett så vet vi med säkerhet att datamängden ${\widehat {D}}\,\!$ existerar. För att binda RHS till mindre än en behöver vi ${\displaystyle m\geq \lambda (\operatörsnamn {VCDim} (H) )\log(m/\operatörsnamn {VCDim} (H))/\alpha ^{2})\,\!} ,$ där $\lambda \,\!$ är någon positiv konstant. Eftersom vi angav tidigare att vi kommer att mata ut en datauppsättning av storleken ${\tilde {O}}(\operatörsnamn {VCDim} (H)/\alpha ^{2} )\,\!$ , så genom att använda denna bunden på $m\,\!$ får vi $m\geq \lambda (\operatörsnamn {VCDim} (H)\log(1/\alpha )/\alpha ^{2})\,\!$ . Därav lemma.

Nu åberopar vi den exponentiella mekanismen.

Definition: För alla funktioner ${\displaystyle q:((\{0,1\}^{k})^{n }\times (\{0,1\}^{k})^{m})\rightarrow \mathbb {R} \,\!} och indatadataset D {\displaystyle$ D $,\!}$ , exponentialmekanismen matar ut varje dataset ${\widehat {D}}\,\!$ med sannolikhet proportionell mot $e^{q(D,{\widehat { D}})\varepsilon n/2}\,\!$ .

Från den exponentiella mekanismen vet vi att detta bevarar $(\varepsilon nGS_{q})\,\!$ -differentiell integritet. Låt oss gå tillbaka till beviset för satsen.

Vi definierar $(q(D),q({\widehat {D}}))=-\max _{h\in H}|Q_{h}(D)-Q_{h}({\widehat {D }})|\,\!$ .

För att visa att mekanismen uppfyller $(\alpha ,\delta )\,\!$ -användbarheten, bör vi visa att den matar ut något dataset ${\widehat {D}} \,\!$ med $q(D,{\widehat {D}})\geq -\alpha \,\!$ med sannolikhet $1 -\delta \,\!$ . Det finns som mest $2^{km}\,\!$ utdatauppsättningar och sannolikheten att $q(D,{\widehat {D}} )\leq -\alpha \,\!$ är högst proportionell mot $e^{-\varepsilon \alpha n/2}\,\!$ . Genom unionsbunden är alltså sannolikheten för att mata ut en sådan datauppsättning ${\widehat {D}}\,\!$ högst proportionell mot $2^{ km}e^{-\varepsilon \alpha n/2}\,\!$ . Återigen, vi vet att det finns någon datauppsättning ${\widehat {D}}\in (\{0,1\}^{k})^{m}\ ,\!$ för vilken $q(D,{\widehat {D}})\geq -\alpha /2\,\!$ . Därför matas en sådan datauppsättning ut med sannolikhet åtminstone proportionell mot $e^{-\alpha \varepsilon n/4}\,\!$ .

Låt $A:=\,\!$ händelsen att exponentialmekanismen matar ut något dataset ${\widehat {D}}\,\!$ så att $q(D,{\widehat {D}})\geq -\alpha /2\,\!$ .

$B:=\,\!$ händelsen att exponentialmekanismen matar ut något dataset ${\widehat {D}}\,\!$ så att $q(D,{\widehat {D}})\leq -\alpha \,\!$ .

$\därför {\frac {\Pr[A]}{\Pr[B]}}\geq {\frac {e^{-\alpha \varepsilon n/4}}{2^{km}e^ {-\alpha \varepsilon n/2}}}={\frac {e^{\alpha \varepsilon n/4}}{2^{km}}}.\,\!$

Om vi ​​nu ställer in denna kvantitet till att vara minst $1/\delta \geq (1-\delta )/\delta \,\!$ finner vi att det räcker med att ha

$n\geq {\frac {4}{\varepsilon \alpha }}\left(km+\ln {\frac {1}{\delta }}\right)\geq O\left({\frac {d \cdot \operatörsnamn {VCDim} (H)\log(1/\alpha )}{\alpha ^{3}\varepsilon }}+{\frac {\log(1/\delta )}{\alpha \varepsilon } }\höger).\,\!$

Och därför bevisar vi satsen.

Applikationer inom andra domäner

I exemplet ovan på användningen av exponentiell mekanism kan man mata ut en syntetisk datauppsättning på ett differentiellt privat sätt och kan använda datauppsättningen för att svara på frågor med god noggrannhet. Andra privata mekanismer, såsom posterior sampling, som returnerar parametrar snarare än datauppsättningar, kan göras likvärdiga med den exponentiella.

Förutom inställningen av integritet har den exponentiella mekanismen också studerats i samband med auktionsteori och klassificeringsalgoritmer . När det gäller auktioner hjälper den exponentiella mekanismen till att uppnå en sann auktionsinställning.

externa länkar

• The Algorithmic Foundations of Differential Privacy av Cynthia Dwork och Aaron Roth, 2014.