京东-优惠雷达
新人页面
精选商品
首月0月租体验,领12个月京东PLUS
自营热卖

利用本地差分隐私技术收集和分析多维数据(一)

庸人自扰梦 1年前   阅读数 272 0

       最近看了一篇论文《Collecting and Analyzing Multidimensional Data with Local Differential Privacy》,其中最关键的就是本地化差分隐私技术(以下简称LDP)在收集分析数据时的各种实现机制

一、拉普拉斯机制

       1、假设每个用户u_{i}的数据记录t_{i}包含一个数值属性,其值位于范围[-1,1]内;

       2、定义一个输出扰动记录的随机函数:t_{i}^{*}=t_{i}+Lap(\frac{2}{\epsilon }),其中Lap(\lambda )表示遵循尺度\lambda的拉普拉斯分布的随机变量,其具有以下概率密度函数:pdf(x)=\frac{1}{2\lambda }exp(-\frac{|x|}{\lambda })期望为0、方差为2\lambda ^{2}的Laplace分布的概率密度函数);

       3、显然,该估计t_{i}^{*}是无偏的,因为在每个t_{i}^{*}中注入的拉普拉斯噪声Lap(\frac{2}{\epsilon })具有零均值(即期望为0)t_{i}^{*}的方差是\frac{8}{\epsilon ^{2}}即方差为2\lambda ^{2}

       4、一旦数据采集者接收到所有被扰动的元组,它就只计算它们的平均值\frac{1}{n}\sum_{i=1}^{n}t_{i}^{*}作为误差等级为O(\frac{1}{\epsilon \sqrt{n}})(不知道怎么得出来的~)的均值估计值。

       简而言之,用户将数据添加一个拉普拉斯噪声Lap(\frac{2}{\epsilon })后发送给数据收集者,数据收集者对得到的数据元组先求平均值后再对外发布。

二、拉普拉斯机制变体

       SCDF由Soria-Comas和Domingo-Ferrer提出,可以获得多维数据的改进结果精度;Stairease mechanism由Geng 等人提出,实现了无界输入值的最佳性能。具体而言,对于单个数值t_{i},两种方法都注入随机噪声n_{i},该随机噪声n_{i}来自以下分段恒定概率分布:

                            

       在SCDF中,;在Stairease mechanism中,m=\frac{2}{1+e^{\epsilon /2}}。 

       注意:Stairease mechanism中的最优性结果不适用于有界输入的情况(有界输入是指输入集合数据分布是有上界或者下界的,即均大于或者均小于某个值)。

       这两种方法就是改变了噪声的注入方式。

三、Duchi等人的解决方法

       杜奇等人提出了一种在LDP下扰动多维数据元组的方法。 以下算法说明了Duchi等人对于一维案例的解决方案:

                            

       特别的是,给定一个元组t_{i}\in[-1,1],算法返回一个扰动的元组t_{i}^{*},它等于\frac{e^{\epsilon }+1}{e^{\epsilon }-1}-\frac{e^{\epsilon }+1}{e^{\epsilon }-1},具有以下概率:

                            

       注意:a.以上两概率之和为1;

                 b.当\epsilon趋近于0时,两概率趋近于相等,为\frac{1}{2}

                 c.当\epsilon不趋近0时,x=\frac{e^{\epsilon }+1}{e^{\epsilon }-1}的概率大于x=-\frac{e^{\epsilon }+1}{e^{\epsilon }-1}的概率。

       杜奇等人证明t_{i}^{*}是输入值t_{i}的无偏估计。 另外,t_{i}^{*}的方差是:

                            

                            

        因此,当t_{i} = 0时,t_{i}^{*}取最坏(最大)方差,等于(\frac{e^{\epsilon }+1}{e^{\epsilon }-1})^{2}。 在接收到该算法输出的扰动元组时,收集者简单地计算所有用户的属性的平均值以获得估计的平均值。

        以上解决方案的缺点:下图说明了拉普拉斯机制和Duchi等人的解决方案在变化时返回的噪声值最坏(最大)方差。当\epsilon \leq 2时,Duchi等人的解决方案比拉普拉斯机制提供的方差小得多,但是当\epsilon > 2时,后者明显优于后者。

                            

        回想一下,Duchi等人的解决方案总返回 t_{i}^{*}=\frac{e^{\epsilon }+1}{e^{\epsilon }-1}或 t_{i}^{*}=-\frac{e^{\epsilon }+1}{e^{\epsilon }-1}。因此,该解决方案输出的噪声值t_{i}^{*}总是具有绝对值|\frac{e^{\epsilon }+1}{e^{\epsilon }-1}|> 1,因此无论隐私预算有多大,t_{i} = 0时t_{i}^{*}的方差总是大于1。相反,拉普拉斯机制产生\frac{8}{\epsilon ^{2}}的噪声方差,其随着增加而呈二次方减小,由此在\epsilon大的时候是优选的。然而,当\epsilon小时,分母\epsilon ^{2}会导致很大的噪声方差,而Duchi等人的解决方案不会遇到这个问题,因为它的方差被确定在相对较小的范围内[-\frac{e^{\epsilon }+1}{e^{\epsilon }-1},\frac{e^{\epsilon }+1}{e^{\epsilon }-1}]

       噪声方差的大小会直接影响扰动数据的方差大小,扰动数据方差越小说明数据之间的相似度越高,即差分隐私保护越成功,所以各种实现机制以方差趋小为目的。

        下一篇讲一下改进后的实现机制。

 

 

 


注意:本文归作者所有,未经作者允许,不得转载

全部评论: 0

    我有话说: