算法设计练习#
需要考虑的问题#
一共需要多少次问询，以及我们可以使用何种组合定理？
可以使用并行组合性吗？
我们应该使用串行组合性，高级组合性，还是差分隐私变体？
我们可以使用稀疏向量技术吗？
我们可以使用指数机制吗？
我们应该如何分配隐私预算？
如果敏感度无上界，该如何限制敏感度的上界？
使用合成数据会带来帮助吗？
后处理性有助于”降噪”吗？
1. 更普适的”采样-聚合”算法#
设计一个变种”采样-聚合”算法，使其不需要分析者指定问询函数\(f\)的输出范围。
思想：首先，使用稀疏向量技术找到适用于整个数据集的\(f(x)\)上界和下界。由于\(clip(f(x), lower, upper)\)是一个敏感度有上界的问询，我们可以在此问询上应用稀疏向量技术。随后，基于得到的上界和下界使用”采样-聚合”算法。
2. 汇总统计#
设计一种算法来生成满足差分隐私的下述统计数据：
均值：\(\mu = \frac{1}{n} \sum_{i=1}^n x_i\)
方差：\(var = \frac{1}{n} \sum_{i=1}^n (x_i - \mu)^2\)
标准差：\(\sigma = \sqrt{\frac{1}{n} \sum_{i=1}^n (x_i - \mu)^2}\)
思想：
均值
使用稀疏向量技术找到裁剪边界的上界和下界
计算噪声求和值与噪声计数值，再应用后处理性得到均值
方差
将方差问询拆分为一个计数问询（并计算得到\(\frac{1}{n}\)，我们可以从计算均值问询的过程中得到计数问询的结果）与一个求和问询
\(\sum_{i=1}^n (x_i - \mu)^2\)的敏感度是什么？我们可以裁剪并计算\(\sum_{i=1}^n (x_i - \mu)^2\)，然后根据后处理性与（1）得到的结果相乘
标准差
只需计算方差的平方根
涉及到的全部问询：
裁剪下界（稀疏向量技术）
裁剪上界（稀疏向量技术）
噪声求和（均值）
噪声计数
噪声求和（方差）
3. 频繁项#
谷歌的RAPPOR系统[15]用于统计谷歌浏览器用户最常设置的主页是什么。请设计下述算法：
给定基于流量统计得到的10,000个最受欢迎的网页列表，
从这10,000个最受欢迎的网页中确定前10个最受欢迎的主页
思想：使用并行组合性，获取加噪后排名前10的主页
4.分层查询#
设计一种为美国人口普查信息生成汇总统计结果的算法。算法应该能按下述从低到高的层次输出相应的人口统计结果：
人口普查区
城市 / 乡镇
邮编
国家
洲
美国
思想：
思想1：使用并行组合性，只计算最低层次（人口普查区）的人口统计结果。将所有区域的计数结果相加，得到各个城市的人口统计结果，以此类推，得到所有统计结果。优势：隐私预算低。
思想2：计算所有层次的计数结果，分别对每一层使用并行组合性，根据真实数据调整预算分配。优势：对于较低层，我们可以得到更准确的统计结果。
思想3：和（2）一样，但应用后处理性，基于更高层的计数结果重新缩放较低层的计数结果，将缩放后的（浮点数）结果截断为整数；将负数设置为0。
5. 一系列范围问询#
设计一种算法来准确回答一系列范围问询。这些范围问询都是针对某一个数据表的问询：”有多少行数据的值在\(a\)和\(b\)之间？”（即特定取值范围的数据行数）。
第1部分#
这一系列范围问询是已经预先确定的、数量有限的、形式为： \(\{(a_1, b_1), \dots, (a_k, b_k)\}\)的问询序列。
第2部分#
这一系列范围问询序列的长度\(k\)是预先确定的，但是问询以流方式执行，每一个问询必须在执行时就给出回复。
第3部分#
范围问询序列可能是无限长的。
思想：
根据串行组合性，依次执行每一个问询
对于第1部分，我们可以引入\(L2\)敏感度，从而引入高斯机制。当\(k\)很大时，高斯噪声的应用效果会更好。
或者，我们可以构造合成数据：
为每个问询范围\((i, i+1)\)计算一个计数值（这样就可以应用并行组合性了）。这就是所谓的合成数据表示法！我们可以将直方图中落在指定问询区间内的所有分段计数结果相加，从而回答无穷多的范围问询。
对于第2部分，使用稀疏向量技术
使用稀疏向量技术：对于问询流中的每个问询，查看真实数据回复结果与合成数据回复结果之间的差值。如果差值较大，则问询一次真实数据，得到（应用并行组合性，得到直方图形式的）回复结果，并更新合成数据。否则，给出直接返回合成数据回复结果。这样一来，只有当需要更新合成数据时，我们才需要消耗隐私预算。