Partioning-based mechanisms unde

1,ITRODUCTION

简单的介绍了在推荐系统实际应用当中当中一下，对个人隐私预算的需求。，在本文中，提出了两种基于分区的机制，即基于隐私和基于实用的分区，用于在数据集中处理每个个体的个性化差异隐私参数，同时最大化不同私有计算的效用。文章从【1】论文当中的两个机制，即minnum机制和threshould机制引出本文要介绍的两种分区机制，隐私意识和基于效用的分区机制（privacy-aware and utility-based partitioning）。
本文研究了实现PDP的两种新的分区机制，同时充分利用了不同个体的隐私预算，并最大化了目标DP计算的效用：隐私意识和基于实用的分区。给定任何DP聚合计算M，我们的分区机制组将各种隐私预算记录到k个分区中，使用其最小的隐私预算在每个分区上应用M，然后从k分区中综合计算得到最终输出。为了最大限度地利用所有剩余的隐私预算（即在分区当中被阈值掩盖的隐私预算），我们还开发了一个t轮分区，并从理论上证明了它的收敛性。隐私保护机制将所有隐私预算视为一种直方图，并将具有类似价值的直方图箱作为最小化隐私浪费的方法。基于实用的机制将所有的隐私参数划分为目标计算M的最大效用，特别地，我们发现基于实用的机制在许多重要的DP聚合分析中具有更好的性能，如计数查询、逻辑回归和支持向量机。这是因为它考虑了隐私预算浪费和每个分区的记录数量，这对目标DP聚合机制的效用有很大的影响。广泛的实验证明了我们的方法的一般适用性和优越的性能。

2,Related Work

相关工作主要介绍了一下Dwork拉普拉斯机制考虑全体隐私的机制和【1】中提出的两种个人差分隐私机制PDP1，基于简单抽样的机制和改进的指数机制（The Sample Mechanism PE Mechanism）本次实验结果将和抽样机制进行对比。

3，Preliminaries(预赛，原理，机制)

Definition 1 （£-Differential Privacy）

Definition 2 （Persionalized Differential Privacy)

4 Partitioning mechanisms(分区机制)

在本节中，我们提出了两个分区机制，以充分利用个人的隐私预算，并最大化目标DP计算的效用。
一般的分区机制，就是通过隐私预算将数据集D分成组,D₁，，，，，，D_k，然后计算出每个带噪音输出的查询结果q₁，，，，，，q_k。然后合成q。

Definition 3 (The General Partitioning Mechanism)

The General Partitioning Mechanism.png

分区机制没有隐私风险，信息是直接从记录里面读取出来的，其中每一个Privacy Budget都说每一个小组里面最小的隐私预算。

4.1 Privacy-aware partitioning mechanism

开发具有隐私意识的分区机制，目标是将具有类似隐私预算的记录分组，尽能力减小因为分区而浪费的隐私预算。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
制定了一个分区的隐私预算浪费W={W₁，，，，，，W_k},
我们定义隐私感知分区算法如下:

Definition 4 (Privacy-aware partitioning)

Privacy-aware partitioning
算法就是将隐私预算排队，然后进行分组，使隐私分区浪费最少，也就是将下面式最小化。然后得到相应的k个分组。 隐私意识分区方法目标.jpg

Define 5(Untilily-based partitioning)

开发效用最大的分区算法，使用最大效用函数，使得每一个分区的最后的效用之和最大。
最优化函数最大。

效用函数.jpg
在拉普拉斯机制当中，由于隐私预算与全局敏感度和数量有关，所以可以设置最大效用函数为：U(n_i; 笔记大概整理

【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