Exponenciální mechanismus (rozdílné soukromí) - Exponential mechanism (differential privacy)

The exponenciální mechanismus je technika pro navrhování rozdílně soukromé algoritmy. Byl vyvinut společností Frank McSherry^[1] a Kunal Talwar^[2] v roce 2007. Jejich práce byla uznána jako spoluvlastník ceny PET za rok 2009 za vynikající výzkum v technologiích zvyšujících ochranu soukromí.^[3]

Většina počátečního výzkumu v oblasti diferenciálního soukromí se točila kolem skutečných funkcí, které mají relativně nízkou hodnotu citlivost ke změně údajů o jedinci, jehož užitečnost nebrání malé odchylky v aditivách. Přirozenou otázkou je, co se stane v situaci, kdy si chceme uchovat obecnější sady vlastností. Exponenciální mechanismus pomáhá při řešení těchto problémů rozšířit pojem rozdílového soukromí. Kromě toho popisuje třídu mechanismů, která zahrnuje všechny možné odlišně soukromé mechanismy.

Exponenciální mechanismus ^[4]

Algoritmus

Obecně řečeno, mechanismus ochrany soukromí mapuje soubor ${displaystyle n ,!}$ vstupy z domény ${displaystyle {mathcal {D}} ,!}$ do rozsahu ${displaystyle {mathcal {R}} ,!}$. Mapa může být náhodná, v takovém případě každý prvek domény ${displaystyle D ,!}$ odpovídá rozdělení pravděpodobnosti v celém rozsahu ${displaystyle R ,!}$. Mechanismus ochrany soukromí nepředpokládá povahu ${displaystyle {mathcal {D}} ,!}$ a ${displaystyle {mathcal {R}} ,!}$ kromě základny opatření ${displaystyle mu,!}$ na ${displaystyle {mathcal {R}} ,!}$. Pojďme definovat funkci ${displaystyle q: {mathcal {D}} ^ {n} imes {mathcal {R}} ightarrow mathbb {R},!}$. Tato funkce intuitivně přiřadí dvojici skóre ${displaystyle (d, r) ,!}$, kde ${displaystyle din {mathcal {D}} ^ {n} ,!}$ a ${displaystyle rin {mathcal {R}} ,!}$. Skóre odráží přitažlivost páru ${displaystyle (d, r) ,!}$, tj. čím vyšší je skóre, tím přitažlivější je dvojice. Vzhledem k vstupu ${displaystyle din {mathcal {D}} ^ {n} ,!}$, cílem mechanismu je vrátit ${displaystyle rin {mathcal {R}} ,!}$ taková, že funkce ${displaystyle q (d, r) ,!}$ je přibližně maximalizován. Chcete-li toho dosáhnout, nastavte mechanismus ${displaystyle {mathcal {E}} _ {q} ^ {varepsilon} (d) ,!}$ jak následuje:
Definice: Pro jakoukoli funkci ${displaystyle q: ({mathcal {D}} ^ {n} imes {mathcal {R}}) ightarrow mathbb {R},!}$a základní míra ${displaystyle mu,!}$ přes ${displaystyle {mathcal {R}} ,!}$, definovat:

${displaystyle {mathcal {E}} _ {q} ^ {varepsilon} (d): = ,!}$ Vybrat ${displaystyle r ,!}$ s pravděpodobností úměrnou ${displaystyle e ^ {varepsilon q (d, r)} imes mu (r) ,!}$, kde ${displaystyle din {mathcal {D}} ^ {n}, rin R ,!}$.

Tato definice implikuje skutečnost, že pravděpodobnost návratu ${displaystyle r ,!}$ roste exponenciálně se zvyšováním hodnoty ${displaystyle q (d, r) ,!}$. Ignorování základní míry ${displaystyle mu,!}$ pak hodnota ${displaystyle r ,!}$ který maximalizuje ${displaystyle q (d, r) ,!}$ má nejvyšší pravděpodobnost. Tento mechanismus je navíc odlišně soukromý. Následovat bude důkaz tohoto nároku. Jednou z technických věcí, které je třeba mít na paměti, je správná definice ${displaystyle {mathcal {E}} _ {q} ^ {varepsilon} (d) ,!}$ the ${displaystyle int _ {r} e ^ {varepsilon q (d, r)} imes mu (r) ,!}$ by měla být konečná.

Věta (rozdílné soukromí): ${displaystyle {mathcal {E}} _ {q} ^ {varepsilon} (d) ,!}$ dává ${displaystyle (2varepsilon Delta q) ,!}$-diferenciální soukromí.

Důkaz: Hustota pravděpodobnosti ${displaystyle {mathcal {E}} _ {q} ^ {varepsilon} (d) ,!}$ v ${displaystyle r ,!}$ rovná se

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

Nyní, pokud dojde k jediné změně ${displaystyle d ,!}$ Změny ${displaystyle q ,!}$ maximálně ${displaystyle Delta q ,!}$ pak se čitatel může změnit maximálně o faktor ${displaystyle e ^ {varepsilon Delta q} ,!}$ a jmenovatel minimálně o faktor ${displaystyle e ^ {- varepsilon Delta q} ,!}$. Poměr nové hustoty pravděpodobnosti (tj. S novou ${displaystyle d ,!}$) a ta starší je nanejvýš ${displaystyle exp (2varepsilon Delta q) ,!}$.

Přesnost

V ideálním případě bychom chtěli náhodné losování ${displaystyle r ,!}$ z mechanismu ${displaystyle {mathcal {E}} _ {q} ^ {varepsilon} (d) ,!}$ téměř maximalizovat ${displaystyle q (d, r) ,!}$. Pokud vezmeme v úvahu ${displaystyle max _ {r} q (d, r) ,!}$ být ${displaystyle OPT ,!}$ pak můžeme ukázat, že pravděpodobnost odchylky mechanismu ${displaystyle OPT ,!}$ je nízká, pokud je dostatečná hmotnost (ve smyslu ${displaystyle mu}$) hodnot ${displaystyle r ,!}$ s hodnotou ${displaystyle q ,!}$ blízko k optimálnímu.

Lemma: Nechat ${displaystyle S_ {t} = {r: q (d, r)> OPT-t} ,!}$ a ${displaystyle {ar {S}} _ {2t} = {r: q (d, r) leq OPT-2t} ,!}$, my máme ${displaystyle p ({ar {S}} _ {2t}) ,!}$ je nanejvýš ${displaystyle exp (-varepsilon t) / mu (S_ {t}) ,!}$. Pravděpodobnost je převzata ${displaystyle R ,!}$.

Důkaz: Pravděpodobnost ${displaystyle p ({ar {S}} _ {2t}) ,!}$ je nanejvýš ${displaystyle p ({ar {S}} _ {2t}) / p (S_ {t}) ,!}$, protože jmenovatel může být maximálně jeden. Protože obě pravděpodobnosti mají stejný normalizační člen,

${displaystyle {frac {p ({ar {S}} _ {2t})} {p (S_ {t})}} = {frac {int _ {{ar {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 ({ar {S}} _ {2t})} {mu (S_ {t})}}.}$

Hodnota ${displaystyle mu ({ar {S}} _ {2t}) ,!}$ je nanejvýš jeden, a proto tato vazba implikuje příkaz lemma.

Věta (přesnost): Pro tyto hodnoty ${displaystyle tgeq ln left ({frac {OPT} {tmu (S_ {t})}} ight) / varepsilon,!}$, my máme ${displaystyle E [q (d, {mathcal {E}} _ {q} ^ {varepsilon} (d))] geq OPT-3t ,!}$.

Důkaz: Z předchozího lemmatu vyplývá, že pravděpodobnost, že skóre bude alespoň ${displaystyle OPT-2t ,!}$ je ${displaystyle 1-exp (-varepsilon t) / mu (S_ {t}) ,!}$. Hypotézou, ${displaystyle tgeq ln left ({frac {OPT} {tmu (S_ {t})}} ight) / varepsilon,!}$. Nahrazení hodnoty ${displaystyle t ,!}$ dostaneme tuto pravděpodobnost alespoň ${displaystyle 1-t / OPT ,!}$. Násobení s ${displaystyle OPT-2t ,!}$ získá požadovanou vazbu.

Můžeme předpokládat ${displaystyle mu (A) ,!}$ pro ${displaystyle Asubseteq {mathcal {R}} ,!}$ být menší nebo roven jedné ve všech výpočtech, protože vždy můžeme normalizovat s ${displaystyle mu ({mathcal {R}}) ,!}$ .

Příklad použití exponenciálního mechanismu ^[5]

Než se dostaneme do podrobností příkladu, definujme některé pojmy, které budeme v naší diskusi značně používat.

Definice (globální citlivost): Globální citlivost dotazu ${displaystyle Q ,!}$ je jeho maximální rozdíl při hodnocení na dvou sousedních souborech dat ${displaystyle D_ {1}, D_ {2} in {mathcal {D}} ^ {n} ,!}$:

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

Definice: Predikátový dotaz ${displaystyle Q_ {varphi} ,!}$ pro jakýkoli predikát ${displaystyle varphi,!}$ je definován jako

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

Všimněte si, že ${displaystyle GS_ {Q_ {varphi}} leq 1 / n ,!}$ pro jakýkoli predikát ${displaystyle varphi,!}$.

Uvolňovací mechanismus

Toto je kvůli Avrim Blum, Katrina Ligett a Aaron Roth.

Definice (Užitečnost): A mechanismus^{[trvalý mrtvý odkaz ]} ${displaystyle {mathcal {A}} ,!}$ je ${displaystyle (alfa, delta) ,!}$-užitečné pro dotazy ve třídě ${displaystyle H ,!}$ s pravděpodobností ${displaystyle 1-delta,!}$, pokud ${displaystyle for all hin H ,!}$ a každý datový soubor ${displaystyle D ,!}$, pro ${displaystyle {widehat {D}} = {mathcal {A}} (D) ,!}$, ${displaystyle | Q_ {h} ({widehat {D}}) - Q_ {h} (D) | leq alpha,!}$.

Neformálně to znamená, že s vysokou pravděpodobností dotaz ${displaystyle Q_ {h} ,!}$ se bude chovat podobným způsobem na původní datové sadě ${displaystyle D ,!}$ a na syntetickém datovém souboru ${displaystyle {widehat {D}} ,!}$.
Zvažte běžný problém v dolování dat. Předpokládejme, že existuje databáze ${displaystyle D ,!}$ s ${displaystyle n ,!}$ záznamů. Každá položka se skládá z ${displaystyle k ,!}$- n-tice formuláře ${displaystyle (x_ {1}, x_ {2}, tečky, x_ {k}) ,!}$ kde ${displaystyle x_ {i} v {0,1} ,!}$. Nyní se uživatel chce naučit a lineární poloviční prostor formuláře ${displaystyle pi _ {1} x_ {1} + pi _ {2} x_ {2} + cdots + pi _ {k-1} x_ {k-1} geq x_ {k} ,!}$. V podstatě chce uživatel zjistit hodnoty ${displaystyle pi _ {1}, pi _ {2}, tečky, pi _ {k-1} ,!}$ tak, aby maximální počet n-tic v databázi uspokojil nerovnost. Algoritmus, který popisujeme níže, může generovat syntetickou databázi ${displaystyle {widehat {D}} ,!}$ což umožní uživateli naučit se (přibližně) stejný lineární poloprostor při dotazování na tuto syntetickou databázi. Motivací pro takový algoritmus je, že nová databáze bude generována odlišně soukromým způsobem, a tím zajistí soukromí jednotlivých záznamů v databázi ${displaystyle D ,!}$.

V této části ukážeme, že je možné uvolnit datovou sadu, která je užitečná pro koncepty z polynomu VC-Dimension třídy a zároveň dodržovat ${displaystyle varepsilon,!}$-diferenciální soukromí, pokud je velikost původní datové sady alespoň polynomiální na VC-Dimension třídy konceptu. Formálně uvést:

Teorém: Pro jakoukoli třídu funkcí ${displaystyle H ,!}$ a jakýkoli datový soubor ${displaystyle Dsubset {0,1} ^ {k} ,!}$ takhle

${displaystyle | D | geq Oleft ({frac {kcdot operatorname {VCDim} (H) log (1 / alpha)} {alpha ^ {3} varepsilon}} + {frac {log (1 / delta)} {alpha varepsilon} } no) ,!}$

můžeme vygenerovat ${displaystyle (alfa, delta) ,!}$- užitečná datová sada ${displaystyle {widehat {D}} ,!}$ který zachovává ${displaystyle varepsilon,!}$-diferenciální soukromí. Jak jsme již zmínili dříve, algoritmus nemusí být efektivní.

Jedním zajímavým faktem je, že algoritmus, který budeme vyvíjet, generuje syntetický datový soubor, jehož velikost je nezávislá na původním datovém souboru; ve skutečnosti to záleží jen na VC-rozměr pojmové třídy a parametru ${displaystyle alpha,!}$. Algoritmus vydává datovou sadu velikosti ${displaystyle {ilde {O}} (operatorname {VCDim} (H) / alpha ^ {2}) ,!}$

Půjčujeme si Věta o jednotné konvergenci z kombinatorika a uveďte z toho důsledek, který odpovídá naší potřebě.

Lemma: Vzhledem k jakékoli datové sadě ${displaystyle D ,!}$ existuje datová sada ${displaystyle {widehat {D}} ,!}$ velikosti ${displaystyle = O (operatorname {VCDim} (H) log (1 / alpha)) / alpha ^ {2} ,!}$ takhle ${displaystyle max _ {hin H} | Q_ {h} (D) -Q_ {h} ({widehat {D}}) | leq alpha / 2 ,!}$.

Důkaz:

Z věty o jednotné konvergenci víme, že

${displaystyle {egin {aligned} & Pr left [, left | Q_ {h} (D) -Q_ {h} ({widehat {D}}) ight | geq {frac {alpha} {2}} {ext {for some }} hin Hight] [5pt] leq {} & 2left ({frac {em} {operatorname {VCDim} (H)}} ight) ^ {operatorname {VCDim} (H)} cdot e ^ {- alfa ^ {2 } m / 8}, konec {zarovnáno}}}$

kde je pravděpodobnost nad distribucí datové sady. Pokud je tedy RHS menší než jedna, víme jistě, že soubor dat ${displaystyle {widehat {D}} ,!}$ existuje. Abychom mohli svázat RHS na méně než jednu, potřebujeme to ${displaystyle mgeq lambda (operatorname {VCDim} (H) log (m / operatorname {VCDim} (H)) / alpha ^ {2}) ,!}$, kde ${displaystyle lambda,!}$ je nějaká pozitivní konstanta. Vzhledem k tomu, že jsme již dříve uvedli, že vydáme datovou sadu velikosti ${displaystyle {ilde {O}} (operatorname {VCDim} (H) / alpha ^ {2}) ,!}$, takže pomocí tohoto vázán na ${displaystyle m ,!}$ dostaneme ${displaystyle mgeq lambda (operatorname {VCDim} (H) log (1 / alpha) / alpha ^ {2}) ,!}$. Proto lemma.

Nyní vyvoláme exponenciální mechanismus.

Definice: Pro jakoukoli funkci ${displaystyle q: (({0,1} ^ {k}) ^ {n} imes ({0,1} ^ {k}) ^ {m}) ightarrow mathbb {R},!}$ a vstupní datová sada ${displaystyle D ,!}$, exponenciální mechanismus vydává každou datovou sadu ${displaystyle {widehat {D}} ,!}$ s pravděpodobností úměrnou ${displaystyle e ^ {q (D, {widehat {D}}) varepsilon n / 2} ,!}$.

Z exponenciálního mechanismu víme, že to zachovává ${displaystyle (varepsilon nGS_ {q}) ,!}$-diferenciální soukromí. Vraťme se k důkazu Věty.

Definujeme ${displaystyle (q (D), q ({widehat {D}})) = - max _ {hin H} | Q_ {h} (D) -Q_ {h} ({widehat {D}}) | ,! }$.

Ukázat, že mechanismus splňuje požadavky ${displaystyle (alfa, delta) ,!}$-užitečnost, měli bychom ukázat, že vydává nějakou datovou sadu ${displaystyle {widehat {D}} ,!}$ s ${displaystyle q (D, {widehat {D}}) geq -alpha,!}$ s pravděpodobností ${displaystyle 1-delta,!}$. Existuje nanejvýš ${displaystyle 2 ^ {km} ,!}$ výstupní datové soubory a pravděpodobnost, že ${displaystyle q (D, {widehat {D}}) leq -alpha,!}$ je nanejvýš úměrná ${displaystyle e ^ {- varepsilon alfa n / 2} ,!}$. Tedy spojením odborů je pravděpodobnost výstupu jakékoli takové datové sady ${displaystyle {widehat {D}} ,!}$ je nanejvýš úměrná ${displaystyle 2 ^ {km} e ^ {- varepsilon alfa n / 2} ,!}$. Opět víme, že existuje nějaká datová sada ${displaystyle {widehat {D}} v ({0,1} ^ {k}) ^ {m} ,!}$ pro který ${displaystyle q (D, {widehat {D}}) geq -alpha / 2 ,!}$. Proto je takový datový soubor vydáván s pravděpodobností alespoň úměrnou ${displaystyle e ^ {- alfa varepsilon n / 4} ,!}$.

Nechat ${displaystyle A: = ,!}$ událost, že exponenciální mechanismus vydává nějakou datovou sadu ${displaystyle {widehat {D}} ,!}$ takhle ${displaystyle q (D, {widehat {D}}) geq -alpha / 2 ,!}$.

${displaystyle B: = ,!}$ událost, že exponenciální mechanismus vydává nějakou datovou sadu ${displaystyle {widehat {D}} ,!}$ takhle ${displaystyle q (D, {widehat {D}}) leq -alpha,!}$.

${displaystyle here {frac {Pr [A]} {Pr [B]}} geq {frac {e ^ {- alfa varepsilon n / 4}} {2 ^ {km} e ^ {- alfa varepsilon n / 2}} } = {frac {e ^ {alpha varepsilon n / 4}} {2 ^ {km}}}.,!}$

Nyní nastavte toto množství alespoň na ${displaystyle 1 / delta geq (1-delta) / delta,!}$, zjistíme, že stačí mít

${displaystyle ngeq {frac {4} {varepsilon alpha}} left (km + ln {frac {1} {delta}} ight) geq Oleft ({frac {dcdot operatorname {VCDim} (H) log (1 / alpha)} {alpha ^ {3} varepsilon}} + {frac {log (1 / delta)} {alpha varepsilon}} ight).,!}$

A proto dokazujeme větu.

Exponenciální mechanismus v jiných doménách

Ve výše uvedeném příkladu použití exponenciálního mechanismu je možné výstupovat syntetickou datovou sadu odlišně soukromým způsobem a pomocí datové sady odpovídat na dotazy s dobrou přesností. Jiné soukromé mechanismy, jako je zadní odběr vzorků,^[6] který vrací parametry spíše než datové sady, může být ekvivalentní exponenciálnímu.^[7]

Kromě nastavení soukromí byl exponenciální mechanismus studován také v kontextu teorie dražby a klasifikační algoritmy.^[8] V případě aukcí exponenciální mechanismus pomáhá dosáhnout a pravdivý nastavení aukce.

Reference

externí odkazy

• Algoritmické základy rozdílového soukromí autorky Cynthia Dwork a Aaron Roth, 2014.