The Algorithmic Foundations of Differential Privacy （五）
写在前面的话
有一段时间没更新这个系列了，今天组会完晚上休息一下，再看看这本书。纯属个人笔记，如有问题请看原文或者留下评论。
Laplace versus Gauss
什么是先验分布？后验分布？似然估计？
x: 观察得到的数据（结果）
y : 决定数据分布的参数（原因）
先验分布（因）：Pr(y）
后验分布（先果后因：贝叶斯公式）：Pr(y|x)
似然估计（先因后果）：Pr(x|y)
举个例子：我有一个图像分类模型，有很多数据，每个数据有自己的特征。同时我设定了一些类别。这个时候我拿一个数据问你，这个数据属于哪一类？
Pr(类别｜特征)＝Pr(类别)×｛Pr(特征｜类别)／Pr(特征)｝
Pr(类别｜特征)表示后验，在该特征下属于这个类别的概率。
Pr(类别)表示先验，样本中该类别的概率。
Pr(特征｜类别)表示似然，该类别下，是该特征的概率。
Pr(特征｜类别)／Pr(特征)越大则偏向这个类别，越小则不是这个类别。
Pr(特征)表示全概率公式计算。
Ps.先验是非常重要的，特别对于机器学习来说，先验就是优化的开始, 可以在较小的数据集中有良好的泛化性能，从信息论的角度看，向系统加入了正确先验这个信息会提高系统的性能。
为什么拉普拉斯对应L1，高斯对应L2
原因是L1和L2正则先验分别是服从拉普拉斯分布和高斯分布的。至于先验分布是什么前面有解释。即先验分布是拉普拉斯分布时，正则化项为L1范数；当先验分布是高斯分布时，正则化项为L2范数。关于这两者的深入理解可以看看这篇博客。
1、拉普拉斯分布在参数w=0点的概率最高，因此L1正则化相比于L2正则化更容易使参数为0。
2、高斯分布在零附近的概率较大，因此L2正则化相比于L1正则化更容易使参数分布在一个很小的范围内。
回到书上
这一段应该比较好理解，我就不赘述了。就是高斯也行，只是用的L2。只是算敏感度的时候要遵循L2范数。并且定理3.22提到了高斯机制伴随着 δ。
高斯优点
1、添加的噪声与其他噪声源具有相同的类型
2、两个高斯的和是高斯的，因此隐私机制对统计分析的影响可能更容易理解和修正。
这两种机制在组合下产生相同的累积损失，因此即使对于每个单独合成来说,隐私保证较弱，但在许多计算中的累积影响是可比较的。此外，如果 δ 足够小（例如，亚多项式），在实践中，我们将永远不会遇到差分隐私保证的不足之处。
也就是说，相对于拉普拉斯噪声，高斯噪声在理论上是有缺点的。考虑 Report Noisy Max（带有拉普拉斯噪声）算法下，每个候选输出在数据库 x 上的效用得分与其在相邻数据集 y 上的效用分数相同。该机制产生 (ε,0)-差分隐私，与候选输出的数量无关。如果我们使用高斯噪声并报告最大值，并且如果候选值的数量比 1/δ 大，那么我们将精确地选择发生概率小于 δ 的具有大高斯噪声的事件。当我们远离高斯分布的尾时，我们不再能保证在 x,y 数据库的观测概率的差别在e±ε因子内。