Laplace函数

$f(x|μ,b)=\frac{1}{2b}e^{\frac{-|x-μ|}{b}}$f(x∣μ,b)=2b1​eb−∣x−μ∣​
其图像为：

​ 其中$μ$μ表示期望，图像上表示对称轴，$x$x代表变量，$b$b代表参数。

​ 对于该函数，其期望为$μ$μ，方差为$2b^2$2b2，这里的证明，比较简单，略。

​ 在差分隐私中通常，令$μ$μ等于0，$b$b等于$\frac{\Delta f}{\varepsilon}$εΔf​，此时函数Laplace函数记为：
$Lap(\frac{\Delta f}{\varepsilon})=\frac{1}{(\frac{2\Delta f}{\varepsilon})}e^{\frac{-|x|}{(\frac{\Delta f}{\varepsilon})}}$Lap(εΔf​)=(ε2Δf​)1​e(εΔf​)−∣x∣​
​ 化简为：
$Lap(\frac{\Delta f}{\varepsilon})=\frac{\varepsilon}{2\Delta f}e^{\frac{-\varepsilon|x|}{\Delta f}}$Lap(εΔf​)=2Δfε​eΔf−ε∣x∣​

Laplace噪声满足$\varepsilon$ε-差分隐私定义

差分隐私定义：

​ 对于相邻的数据集$D$D和$D’$D’，他们两者之多相差一条数据。然后给定一个映射函数$f:D\rightarrow R^d$f:D→Rd。它表示一个数据集$D$D到一个$d$d维空间的映射关系。对于所得的函数$f(D)=(x_1,x_2,\dots,x_d)^T$f(D)=(x1​,x2​,…,xd​)T上加入Laplace噪声，得到输出函数$M(D)$M(D)。

​ 可记为：
$M(D)=f(D)+(Lap_1(\frac{\Delta f}{\varepsilon}),\dots,Lap_d(\frac{\Delta f}{\varepsilon}))^T$M(D)=f(D)+(Lap1​(εΔf​),…,Lapd​(εΔf​))T
​ 如果横着看不习惯，可以竖着看（看成列向量）。

​ 关键点：

​ $\Delta f=\max \limits_{D,D'}||f(D)-f(D')||_p$Δf=D,D′max​∣∣f(D)−f(D′)∣∣p​，其中$p$p一般取值为1，即一范数。

​ 算法$M$M满足差分隐私定义条件是：
$Pr[M(D)\in S]\leqslant e^\varepsilon * Pr[M(D')\in S]$Pr[M(D)∈S]⩽eε∗Pr[M(D′)∈S]
​ $S$S表示为一组观察到的所有序列组合。类比于函数的值域。

证明

​ 首先，得出$\Delta f$Δf的表示具体表示形式。

​ 设，$f(D)=(x_1,\dots,x_d)^T$f(D)=(x1​,…,xd​)T，$f(D')=(x'_1,\dots,x'_d)^T=(x_1+\Delta x_1,\dots,x_d+\Delta x_d)^T$f(D′)=(x1′​,…,xd′​)T=(x1​+Δx1​,…,xd​+Δxd​)T，

则：

​ $\Delta f=\max \limits_{D,D'}(\displaystyle \sum_{i=1}^n(|x_i-x'_i|)) = \max \limits_{D,D'}(\displaystyle \sum_{i=1}^n|\Delta x_i|)$Δf=D,D′max​(i=1∑n​(∣xi​−xi′​∣))=D,D′max​(i=1∑n​∣Δxi​∣)

​ 为了简化，假定所有的$x_i$xi​均为0，那么$f(D)=(0,\dots,0)^T$f(D)=(0,…,0)T，$f(D')=(\Delta x_1,\dots,\Delta x_d)^T$f(D′)=(Δx1​,…,Δxd​)T

​ 记一个输出序列（向量）$S=(y_1,\dots,y_d)^T$S=(y1​,…,yd​)T。

​ 证明技巧：化为分式比较

​ $Pr[M(D)\in S]=\displaystyle\prod_{i=1}^d\frac{\varepsilon}{2\Delta f}e^{-\frac{\varepsilon}{\Delta f}|y_i|}$Pr[M(D)∈S]=i=1∏d​2Δfε​e−Δfε​∣yi​∣，累乘号，是因为$x_i$xi​独立同分布

​ $Pr[M(D')\in S]=\displaystyle\prod_{i=1}^d\frac{\varepsilon}{2\Delta f}e^{-\frac{\varepsilon}{\Delta f}|y_i-\Delta x_i|}$Pr[M(D′)∈S]=i=1∏d​2Δfε​e−Δfε​∣yi​−Δxi​∣

​ 二者相比：
$\frac{Pr[M(D)\in S]}{Pr[M(D')\in S]}=\frac{\displaystyle\prod_{i=1}^d\frac{\varepsilon}{2\Delta f}e^{-\frac{\varepsilon}{\Delta f}|y_i|}}{\displaystyle\prod_{i=1}^d\frac{\varepsilon}{2\Delta f}e^{-\frac{\varepsilon}{\Delta f}|\Delta x_i-y_i|}}=\displaystyle \prod_{i=1}^d e^{-\frac{\varepsilon}{2\Delta f}(|y_i|-|y_i-\Delta x_i|)}=e^{\frac{\varepsilon}{\Delta f} \displaystyle \sum_{i=1}^d(|y_i-\Delta x_i|-|y_i|)}$Pr[M(D′)∈S]Pr[M(D)∈S]​=i=1∏d​2Δfε​e−Δfε​∣Δxi​−yi​∣i=1∏d​2Δfε​e−Δfε​∣yi​∣​=i=1∏d​e−2Δfε​(∣yi​∣−∣yi​−Δxi​∣)=eΔfε​i=1∑d​(∣yi​−Δxi​∣−∣yi​∣)
​ 由基本不等式知：
$|y_i-\Delta x_i|-|y_i| \leq |y_i -\Delta x_i -y_i|=|\Delta x_i|$∣yi​−Δxi​∣−∣yi​∣≤∣yi​−Δxi​−yi​∣=∣Δxi​∣
​ 故上式：
$\sum_{i=1}^d(|y_i-\Delta x_i|-|y_i|) \leq \sum_{i=1}^n|\Delta x_i| \leq \max \limits_{D,D'}(\sum_{i=1}^n|\Delta x_i|)=\Delta f$i=1∑d​(∣yi​−Δxi​∣−∣yi​∣)≤i=1∑n​∣Δxi​∣≤D,D′max​(i=1∑n​∣Δxi​∣)=Δf
​ 于是有：

​
$\frac{Pr[M(D)\in S]}{Pr[M(D')\in S]} \leqslant e^{\varepsilon}$Pr[M(D′)∈S]Pr[M(D)∈S]​⩽eε
​ 得证。即${Pr[M(D)\in S]} \leqslant e^{\varepsilon} * {Pr[M(D')\in S]}$Pr[M(D)∈S]⩽eε∗Pr[M(D′)∈S]

​ 再由对称性知，${Pr[M(D')\in S]} \leqslant e^{\varepsilon} * {Pr[M(D)\in S]}$Pr[M(D′)∈S]⩽eε∗Pr[M(D)∈S]

其他问题

我们已经知道，噪声是符合Laplace机制的，这样是符合差分隐私的定义的。问题是：

1. $M(D)=f(D)+(Lap_1(\frac{\Delta f}{\varepsilon}),\dots,Lap_d(\frac{\Delta f}{\varepsilon}))^T$M(D)=f(D)+(Lap1​(εΔf​),…,Lapd​(εΔf​))T，这个“加法”是普通的加法就好了吗？对于数据集$D$D的分布有什么要求吗？还是说任意数据都可以呢？
2. 在累乘时，我们默认是独立同分布的，那么非独立同分布数据也可以这样算吗？
3. 在$\Delta f$Δf的定义时，我们假定是用一范数的，用其他范数来度量可以吗？答案是否定的，不可以。具体分析可以参考这篇文章。

4. 根据范数的定义可知道，$||\vec x||_p$∣∣x∣∣p​是一个随着$p$p增大而不断减小的递减函数。这个结论是明显的，但是证明，现在我还不会。对于这题而言，这个范数的证明，是无关紧要的。但是这个结论是需要记住的。

参考自MathThinker

数学公式的排版好费时间呀，得多敲！排版公式的语法总结，后面写多了再做。