算法设计练习#

需要考虑的问题#

  • 一共需要多少次问询,以及我们可以使用何种组合定理?

    • 可以使用并行组合性吗?

    • 我们应该使用串行组合性,高级组合性,还是差分隐私变体?

  • 我们可以使用稀疏向量技术吗?

  • 我们可以使用指数机制吗?

  • 我们应该如何分配隐私预算?

  • 如果敏感度无上界,该如何限制敏感度的上界?

  • 使用合成数据会带来帮助吗?

  • 后处理性有助于”降噪”吗?

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}\)

思想

均值

  1. 使用稀疏向量技术找到裁剪边界的上界和下界

  2. 计算噪声求和值与噪声计数值,再应用后处理性得到均值

方差

  1. 将方差问询拆分为一个计数问询(并计算得到\(\frac{1}{n}\),我们可以从计算均值问询的过程中得到计数问询的结果)与一个求和问询

  2. \(\sum_{i=1}^n (x_i - \mu)^2\)的敏感度是什么?我们可以裁剪并计算\(\sum_{i=1}^n (x_i - \mu)^2\),然后根据后处理性与(1)得到的结果相乘

标准差

  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部分,使用稀疏向量技术

使用稀疏向量技术:对于问询流中的每个问询,查看真实数据回复结果与合成数据回复结果之间的差值。如果差值较大,则问询一次真实数据,得到(应用并行组合性,得到直方图形式的)回复结果,并更新合成数据。否则,给出直接返回合成数据回复结果。这样一来,只有当需要更新合成数据时,我们才需要消耗隐私预算。