Conservative or Liberal? Personalized Differential Privacy
保守或自由?個性化的微分隱私
Abstract-差異隱私被廣泛接受為為聚合數(shù)據(jù)分析提供強有力的正式隱私保證的強大框架。該模型的一個限制是，所有個人都享有同等程度的隱私保護。然而，數(shù)據(jù)主體對其數(shù)據(jù)的可接受的隱私水平有不同的期望，這是很常見的。因此，差別隱私可能會導(dǎo)致一些用戶的隱私保護不足，而過度保護其他用戶。我們認為，通過接受并非所有用戶都需要相同級別的隱私，通?？梢酝ㄟ^不向不想要隱私的用戶提供過多的隱私來獲得更高級別的實用價值。我們提出了一種新的隱私定義，稱為“個性化差異隱私”(P（personalized）DP)，這是一種對差異隱私的推廣，其中用戶為其數(shù)據(jù)指定了個人隱私需求。然后介紹了幾種實現(xiàn)PDP的新機制。我們的主要機制是一個通用機制，可以自動將任何現(xiàn)有的差異私有算法轉(zhuǎn)換成滿足PDP的算法。受著名的指數(shù)機制的啟發(fā)，我們還提出了一種更直接的實現(xiàn)PDP的方法。我們通過在真實和合成數(shù)據(jù)上的大量實驗來證明我們的框架。
INTRODUCTION
簡單的介紹了差分隱私最近幾年的發(fā)展，和現(xiàn)在發(fā)展的方向，還介紹了本文和其之間的
Contributions
在本文中，我們考慮了受信任的數(shù)據(jù)分析師希望從包含許多個人用戶個人數(shù)據(jù)的數(shù)據(jù)集中發(fā)布匯總統(tǒng)計數(shù)據(jù)的設(shè)置。每個用戶都可能對其數(shù)據(jù)有不同的隱私要求，分析人員希望發(fā)布關(guān)于數(shù)據(jù)的有用的聚合信息，同時滿足貢獻者的個人隱私要求。為此，我們提出了一種新的隱私框架，稱為個性化差異隱私(PDP)，這是一種對差異隱私的推廣，。我們還證明了差異隱私的組合屬性可以遺傳給PDP，允許從單個PDP組件構(gòu)建復(fù)雜的隱私保護算法。
A.這可以利用非統(tǒng)一的隱私要求，以達到更好的效用，而不是通過差別的隱私。我們的第一種機制是通用的，可以很容易地將任何現(xiàn)有的差異私有算法自動轉(zhuǎn)換為PDP算法。該機制是一個兩步過程，涉5及到在單個元組級別上的非統(tǒng)一采樣步驟，然后在采樣數(shù)據(jù)集上調(diào)用適當?shù)牟町愃接袡C制。在采樣步驟中，根據(jù)相應(yīng)用戶的個人隱私需求計算每個元組的包含概率。我們證明，這兩步程序引入的隨機性的兩個來源結(jié)合起來，產(chǎn)生了精確的個性化保證要求。我們的第二個機制是一種更直接的實現(xiàn)PDP的方法，。在第三節(jié)中，我們介紹了新的隱私定義，然后討論了如何滿足定義，在第四節(jié)中，第五節(jié)介紹了我們的實驗研究，第六節(jié)總結(jié)了
B. 第二節(jié)：PRELIMINARIES
主要介紹差分隱私的概念
Definition 1 (Dataset).：
Definition 2 (Neighboring datasets)：
Definition 3 (￡-Differential Privacy）：
Definition 4 (Global Sensitivity ).：
Theorem 1 (Laplace Mechanism )：
Theorem 2 (Exponential Mechanism）
[if !supportLists]C. [endif]Related Work
k-匿名的個性化隱私:要求一條數(shù)據(jù)至少和其他k-1條記錄不可分，這通常是通過泛化或抑制屬性值來實現(xiàn)的。在肖和陶的方法中，用戶通過在泛化層次中為他們的數(shù)據(jù)指定最小泛化級別來指定他們的隱私偏好。（抑制：就是用一個沒有意義的符號去代替某一個值，泛化：用不夠具體但在語義上一致）
后面主要說和最近的一些論文對比，本文的陳述和技術(shù)貢獻優(yōu)越性，本文提供的算法：PDP的主要機制沒有這樣的限制;它可以自動將任何不同的私有算法——無論是拉普拉斯機制的實例、指數(shù)機制，還是多個不同私有模塊的組合——轉(zhuǎn)換成滿足我們個性化隱私定義的算法，關(guān)于隱私拍賣的工作(在[2 1]中進行了調(diào)查)，表面上與目前的工作相似。這項工作主要是關(guān)于如何準確計算用戶群體的統(tǒng)計數(shù)據(jù)，這些用戶要求對其參與所造成的隱私損失進行經(jīng)濟補償。用戶對其隱私進行(可能是非統(tǒng)一的)評估，表示參與e- difference私有分析(作為e的函數(shù))所產(chǎn)生的隱私成本，以及如果使用其數(shù)據(jù)應(yīng)支付的賠償金額
Definition 5 (Privacy Specification)：隱私規(guī)范是將: U -+ R+從用戶映射到個人隱私好，其中較小的值表示較強的隱私偏好。Fleta"(0.01 , 1 .0)用來表示與用戶對應(yīng)的隱私偏好。
在實踐中，期望典型用戶選擇有意義的數(shù)字隱私設(shè)置可能是不合理的。相反，我們設(shè)想這樣一個場景:領(lǐng)域?qū)＜覍⑦m當?shù)闹蹬c用戶友好的描述符關(guān)聯(lián)起來(例如，低、中、高隱私)，用戶從中進行選擇。這是一種可能性;一般來說，為不同的私有系統(tǒng)選擇一個合適的隱私參數(shù)是一個開放的問題，在本文中我們沒有進一步考慮它。全局參數(shù)e，不能被個人影響，我們的模型假設(shè)隱私規(guī)范是公共知識。在傳統(tǒng)的微分隱私這反映了情況,全球隱私設(shè)置€被假定為一個公共參數(shù)。但是，這意味著用戶的隱私參數(shù)不能表示關(guān)于其敏感值的任何信息。我們認為這是一個合理的假設(shè)，因為隱私規(guī)范是在用戶級別定義的，而不是在元組級別定義的。也就是說，我們可以將隱私設(shè)置看作是擁有數(shù)據(jù)的用戶的函數(shù)，而不是數(shù)據(jù)的函數(shù)
Definition 6 (Personalized Differential Privacy (PDP))：
![]()
差分隱私定義
也就是將差分隱私里面的隱私預(yù)算換成了個人預(yù)算，從而保證個性化隱私
Theorem 3 (Differential Privacy Implies PDP)：M : V -> R，滿足￡-DP也滿足Fleta-PDP，with privacy specification = {(u,￡) u 屬于 U}.
Theorem 4 (Composition)：
證明過程大概就是討論著證明連個過程串行時數(shù)據(jù)集在進行組合時候的處理，討論兩個算法有對數(shù)據(jù)集合中重復(fù)部分進行預(yù)算時候，為兩個或多個算法隱私預(yù)算之和。若沒有重合的話那么就是其中算法算法的隱私預(yù)算
原始機制：
我們現(xiàn)在引入的樸素基線機制在技術(shù)上實現(xiàn)了PDP，但是沒有利用個性化的隱私偏來
福實用程序。在剩下的部分,我們將使用符號DP F€(D)來表示,計算輸入在數(shù)據(jù)集D上的函
數(shù)f（）并且滿足滿足傳統(tǒng)€-DP微分隱私的任何計算機制。DP F€(D)可以是用來實現(xiàn)指
機制或者laplace機制或者更復(fù)雜的組合。最簡單的就是直接應(yīng)用應(yīng)用原理3，我們找到
小的個人隱私用戶預(yù)算，然后將其作為該函數(shù)的隱私預(yù)算，達到最強的隱私保護作用，以
下就是最小化的的隱私預(yù)算，（講真，這種做法感覺繞圈子，從每個用戶上升到了全體來闡釋什么是差分隱私，不過這樣寫，也就是說，最小的，即這個就是最嚴格的，但這個超過了大多數(shù)人的需要，而且太強烈意味著要添加更多噪音，影響數(shù)據(jù)的使用）
Definition 7 (Minimum)：
![]()
最小最基本機制.png
定義和證明都很清楚，就不多做解釋了。
如果有一個數(shù)據(jù)集，里面較多的人不關(guān)注隱私，而一部分人關(guān)注隱私，一種做法就是對這個數(shù)據(jù)集進行分類，強的那一部分按照最嚴格的差分隱私方法執(zhí)行
Definition 8 (Threshold)：介紹了一個新的入門的機制
，也就是人為設(shè)置一個t，然后，用戶對隱私要求在這之下的元組將會被刪除，然后證明了這個滿足差分隱私D6.
實現(xiàn)PDP通過抽樣
我們現(xiàn)在為實現(xiàn)PDP提供了一種更智能的通用機制，在許多情況下，它能夠獲得比基線更高的實用級別。在計算中引入兩個獨立的隨機性來源：1，元組級別的非均勻隨機抽樣，其中元組的包含概率取決于相應(yīng)用戶的個人隱私偏好.2：通過在抽樣輸入上調(diào)用傳統(tǒng)的差異私有機制引入了額外的均勻隨機性，其中隱私參數(shù)f依賴于t。將這兩個隨機性源組合在一起,就產(chǎn)生了每個元組所需的精確隱私量。（簡單的說，就是先按個人隱私偏好進行隨機抽樣，然后對其進行個性化差分隱私處理。）
Definition 9 (The Sample Mechanism):
表示獨立隨機的選擇元組：
表示用戶對元組x的隱私偏好，t是介于最大和最小的隱私偏好之間的們可以等于，入門的機制介紹完了，現(xiàn)在再來介紹簡單機制，簡單機制定義如下
R，romove隨機選擇刪除
Theorem 5. The Sample mechanism Sf satisfies
-PDP
簡單的機制滿足
-PDP，以下是證明過程：
備注：說受一片論文影響隨機抽樣有隱私放大的效果，這在第二章B部分有介紹
討論：第一，可以把該機制看成黑盒子；第二：我們看到簡單機制有效的引入兩種隨機機制的同時也引入了兩種誤差，t越小，抽樣步驟丟棄的更少（抽樣誤差更低），但是會造成添加更多的噪音，t最小是就變成了最小線性機制，t最大的話就會變成給每個元組都提供了差分隱私保護，也就是很簡單，較為基本的隱私保護
這個可調(diào)閾值t很有用，t是用戶對自己數(shù)據(jù)集的隱私預(yù)算拼分，t很大時，提供完全E-DP機制的隱私保護，但有的人不需要，不一定達到最好的效果。通過較小的t，達到隱私預(yù)算，并且添加較小的噪音
由于抽樣造成的誤差不僅取決于隱私規(guī)范，而且還取決于數(shù)據(jù)的密度。因此，對于足夠大的數(shù)據(jù)集，設(shè)置一個較低的閾值(例如，可以極大地提高具有強烈隱私要求的用戶的樣本率，代價是略微增加噪音，但總誤差較低
下面有一個例子：
在總用戶為200中，開始t=1，err=150，而將t=0.2.err=50。
實際上，采用改方法可以避免一種情況，全局敏感度很高，但對于大多數(shù)元組和集合度，敏感度較低，對輸出的影響較小。
在實踐中，為任意f精確地優(yōu)化t可能不是件小事，因為盡管DP/可能在不了解數(shù)據(jù)集的情況下被量化，但抽樣的影響確實取決于輸入數(shù)據(jù)。因此，必須小心謹慎，以免通過調(diào)優(yōu)過程泄露隱私。在某些情況下，一種可能的選擇是使用不再敏感(或不那么敏感)的舊數(shù)據(jù)(來自類似的分布)，在不違反隱私的情況下近似地優(yōu)化閾值。在其他情況下，可以使用較保守用戶的部分隱私預(yù)算，并從數(shù)據(jù)子集估算所需的數(shù)量。我們推遲對閾值優(yōu)化策略的深入研究，以供今后工作參考。在第五節(jié)中，我們將演示對于許多函數(shù)，設(shè)置t = max
或t =1/|u|
”的簡單啟發(fā)法，通常會在真實數(shù)據(jù)和隱私問題上給出良好的結(jié)果。
兩步機制，通過采樣步驟實現(xiàn)PDP，然后是一個標準的差異私有機制,接下來將介紹一種高效直接的機制。
指數(shù)機制，這里介紹了打分函數(shù)
理解：r在F（D）中出現(xiàn)的次數(shù)，如果沒有的話就是負數(shù)，表示需要經(jīng)過多少次改變才能達到這個要求，鄰近數(shù)據(jù)集不同，那我們就需要對不同的進行區(qū)分，以最大化r。
通過修改指數(shù)機制的打分函數(shù)，構(gòu)成新的指數(shù)機制
Definition 10 (PE Mechanism)
函數(shù)F：D->R,數(shù)據(jù)集：D，隱私規(guī)范
Theorem 6. The PE mechanism satisfies -PDP：
證明過程在附錄，沒看懂，df（）表示什么意義？以下是大概想的：
表示D和D’相差幾個元組，大概據(jù)說當查詢函數(shù)為預(yù)定參數(shù)r是中用戶設(shè)置的最大隱私預(yù)算，帶蓋就是將打分函數(shù)換了以后，輸出到r的概率，原來是用指數(shù)機制（使其輸出o∈O 的概率正比于exp（E*q(D,r)）/2 dq，則說M 是滿足 ?-DP 的指數(shù)機制），現(xiàn)在改了打分函數(shù)，所以我們就需要重新證明：
接下來就是三個式列：
Count實例：
理解：
后面兩個中位數(shù)和最大數(shù)，差不多就是這個意思
D. [endif]EXPERIMENTAL STUDY實驗研究
接下來，我們將PDP機制應(yīng)用于兩個常見的聚合函數(shù)，count和中值，以及更復(fù)雜的多元線性回歸任務(wù)。雖然count和中值是相對簡單的函數(shù)，但它們是構(gòu)建更復(fù)雜算法]的重要基元。對于計數(shù)函數(shù)和中值函數(shù)，我們比較了簡單機制和類似指數(shù)的PE機制。對于線性回歸，我們使用抽樣機制來轉(zhuǎn)換由Zhang.[33]引入的一種最近的線性回歸差分私有方法，生成了algo的PDP版本算法。
本實驗要證明該算法提供可調(diào)度的隱私保證，通過原數(shù)據(jù)集（包含用戶對自己數(shù)據(jù)聚設(shè)置的隱私預(yù)算，沒有設(shè)置也可以用均值代替）和生成數(shù)據(jù)集之間均方根誤差來調(diào)節(jié)閾值t。
為了為我們的實驗生成隱私規(guī)范，我們將用戶(記錄)隨機分為三組:保守派，代表高度關(guān)注隱私的用戶;適中，代表中等關(guān)注的用戶;自由主義者，代表那些不太關(guān)心用戶的人。保守組和中度組的用戶比例由參數(shù)fc和fM決定;自由派用戶的比例是1.0 - (fe + fM)“在我們的實驗中使用的默認值是fc = 0.54和fM = 0.37。保守組和中等組的用戶的隱私偏好分別從[ce, CM]和[CM, CL]區(qū)間(舍入到最接近的百分位)均勻隨機繪制
下面是實驗當中的一些一些參數(shù)變化范圍：
實驗數(shù)據(jù)集大小
實驗數(shù)據(jù)集大小
計數(shù)當中出現(xiàn)1的次數(shù)
自由用戶隱私預(yù)算
中等用戶隱私預(yù)算
保守用戶隱私預(yù)算
中位數(shù)查詢當中的標準差
中位數(shù)查詢當中的均值
保守派的用戶比列
中等組的用戶比列
自由組的用戶比列
我們上面介紹了四種機制：最小數(shù)機制，入門機制，簡單機制，新指數(shù)機制然后按照上面寫的用數(shù)據(jù)集進行賦閑，里面可以說Laplace機制和指數(shù)機制或者他們的組合機制
