1,ITRODUCTION

簡(jiǎn)單的介紹了在推薦系統(tǒng)實(shí)際應(yīng)用當(dāng)中當(dāng)中一下，對(duì)個(gè)人隱私預(yù)算的需求。，在本文中，提出了兩種基于分區(qū)的機(jī)制，即基于隱私和基于實(shí)用的分區(qū)，用于在數(shù)據(jù)集中處理每個(gè)個(gè)體的個(gè)性化差異隱私參數(shù)，同時(shí)最大化不同私有計(jì)算的效用。文章從【1】論文當(dāng)中的兩個(gè)機(jī)制，即minnum機(jī)制和threshould機(jī)制引出本文要介紹的兩種分區(qū)機(jī)制，隱私意識(shí)和基于效用的分區(qū)機(jī)制（privacy-aware and utility-based partitioning）。
本文研究了實(shí)現(xiàn)PDP的兩種新的分區(qū)機(jī)制，同時(shí)充分利用了不同個(gè)體的隱私預(yù)算，并最大化了目標(biāo)DP計(jì)算的效用：隱私意識(shí)和基于實(shí)用的分區(qū)。給定任何DP聚合計(jì)算M，我們的分區(qū)機(jī)制組將各種隱私預(yù)算記錄到k個(gè)分區(qū)中，使用其最小的隱私預(yù)算在每個(gè)分區(qū)上應(yīng)用M，然后從k分區(qū)中綜合計(jì)算得到最終輸出。為了最大限度地利用所有剩余的隱私預(yù)算（即在分區(qū)當(dāng)中被閾值掩蓋的隱私預(yù)算），我們還開(kāi)發(fā)了一個(gè)t輪分區(qū)，并從理論上證明了它的收斂性。隱私保護(hù)機(jī)制將所有隱私預(yù)算視為一種直方圖，并將具有類似價(jià)值的直方圖箱作為最小化隱私浪費(fèi)的方法?；趯?shí)用的機(jī)制將所有的隱私參數(shù)劃分為目標(biāo)計(jì)算M的最大效用，特別地，我們發(fā)現(xiàn)基于實(shí)用的機(jī)制在許多重要的DP聚合分析中具有更好的性能，如計(jì)數(shù)查詢、邏輯回歸和支持向量機(jī)。這是因?yàn)樗紤]了隱私預(yù)算浪費(fèi)和每個(gè)分區(qū)的記錄數(shù)量，這對(duì)目標(biāo)DP聚合機(jī)制的效用有很大的影響。廣泛的實(shí)驗(yàn)證明了我們的方法的一般適用性和優(yōu)越的性能。

2,Related Work

相關(guān)工作主要介紹了一下Dwork拉普拉斯機(jī)制考慮全體隱私的機(jī)制和【1】中提出的兩種個(gè)人差分隱私機(jī)制PDP1，基于簡(jiǎn)單抽樣的機(jī)制和改進(jìn)的指數(shù)機(jī)制（The Sample Mechanism PE Mechanism）本次實(shí)驗(yàn)結(jié)果將和抽樣機(jī)制進(jìn)行對(duì)比。

3，Preliminaries(預(yù)賽，原理，機(jī)制)

Definition 1 （￡-Differential Privacy）

Definition 2 （Persionalized Differential Privacy)

4 Partitioning mechanisms(分區(qū)機(jī)制)

在本節(jié)中，我們提出了兩個(gè)分區(qū)機(jī)制，以充分利用個(gè)人的隱私預(yù)算，并最大化目標(biāo)DP計(jì)算的效用。
一般的分區(qū)機(jī)制，就是通過(guò)隱私預(yù)算將數(shù)據(jù)集D分成組,D₁，，，，，，D_k，然后計(jì)算出每個(gè)帶噪音輸出的查詢結(jié)果q₁，，，，，，q_k。然后合成q。

Definition 3 (The General Partitioning Mechanism)

The General Partitioning Mechanism.png

分區(qū)機(jī)制沒(méi)有隱私風(fēng)險(xiǎn)，信息是直接從記錄里面讀取出來(lái)的，其中每一個(gè)Privacy Budget都說(shuō)每一個(gè)小組里面最小的隱私預(yù)算。

4.1 Privacy-aware partitioning mechanism

開(kāi)發(fā)具有隱私意識(shí)的分區(qū)機(jī)制，目標(biāo)是將具有類似隱私預(yù)算的記錄分組，盡能力減小因?yàn)榉謪^(qū)而浪費(fèi)的隱私預(yù)算。we formulate the privacy budget waste of a partition D_i as W_i = W(i,1, . . . , i,ni) = sum_{i=1}^n_i(i,j ?min(i,j ))², where ni is number of recordsin Di, _i,j is the privacy budget of jth-record of Di, and min(_i,j ) ensures _i-DP for Di
制定了一個(gè)分區(qū)的隱私預(yù)算浪費(fèi)W={W₁，，，，，，W_k},
我們定義隱私感知分區(qū)算法如下:

Definition 4 (Privacy-aware partitioning)

Privacy-aware partitioning

隱私意識(shí)分區(qū)方法目標(biāo).jpg

Define 5(Untilily-based partitioning)

開(kāi)發(fā)效用最大的分區(qū)算法，使用最大效用函數(shù)，使得每一個(gè)分區(qū)的最后的效用之和最大。
最優(yōu)化函數(shù)最大。

效用函數(shù).jpg

筆記大概整理

【1】Z. Jorgensen, T. Yu, and G. Cormode. Conservative or liberal? personalized differential
privacy. In 31st IEEE International Conference on Data Engineering
(ICDE), pages 1023–1034, 2015