六、查询增强

在前面的小节中，我们重点讨论了私有查询发布的问题，在这个问题中，我们坚持将最坏情况的错误限制在所有查询上。 如果我们只要求较低的平均误差，给定查询的一些分布，我们的问题会更容易吗？ 在本节中，我们看到答案是否定的：给定一种能够以低平均误差解决查询发布问题的机制，给定查询的任何分布，我们可以将其“提升（boost）”为解决查询发布问题的机制最坏情况错误。这既揭示了私有查询发布的复杂性，又为我们设计私有查询发布算法提供了新的工具。

Boosting是一种通用且广泛使用的提高学习算法准确性的方法。给出一组标记的训练示例

$$\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\},$$

其中每一个$x_i$都是从一个域$\mathcal{U}$上的一个基础分布$\mathcal{D}$上提取的，并且每个$y_i\in\{+1,-1\}$，一个学习算法产生假设$h\space:\space\mathcal{U}\to\{+1,-1\}$。理想情况下，$h$不仅仅会“描述”给定样品上的标记， 而且还将归纳概括，提供一个合理准确的方法来分类从底层分布的其他元素。boosting的目标是将弱基学习器转化为强基学习器，强基学习器产生的假设可能比随机猜测好一些，通过强基学习器，它可以根据$\mathcal{D}$为样本绘制一个非常精确的预测器。许多boosting算法共享以下基本结构。 首先，在样本集上施加一个初始的（通常是均匀的）概率分布。 然后以轮次进行计算。 在每一轮$t$：

1. 基本学习器运行在当前分布上，表示为$\mathcal{D}_t$，产生分类假设$h_t$； 然后

2. 假设$h_1,...,h_t$对样本进行重新加权，定义一个新的分布$\mathcal{D}_{t+1}$。

在预定的轮数之后，或者当假设的适当组合被确定为非常准确时，该过程停止。 因此，给定一个基本学习器，一个boosting算法的设计决策是：（1）如何修改一轮到下一轮的概率分布；（2）如何组合假设$\{h_t\}_{t=1,...,T}$以形成最终的输出假设。

在本节中，我们将对查询使用Boosting——也就是说，出于Boosting算法的目的，域$\mathcal{U}$是一组查询$\mathcal{Q}$——去获得一种用于回答大量任意低灵敏度查询的离线算法。与中值机制相比，该算法需要更少的空间，并且根据基础学习器的不同，它还可能具有更高的时间效率。

算法围绕着一个有点神奇的事实展开（引理6.5）：如果我们能找到一个大纲，它能为几个选定的问题提供准确的答案，那么实际上这个大纲就能为大多数问题提供准确的答案！我们将这一事实应用于基础学习器，基础学习器从$\mathcal{Q}$上的分布中采样，并产生一个“弱”大纲作为输出，该大纲为$\mathcal{Q}$中的大多数权重产生“好”答案，以差分私有的方式boosting，以获得对所有Q都好的大纲。

虽然boosting是在查询上执行的，但隐私仍然是针对数据库的行。Boosting查询的隐私挑战来自这样一个事实，即数据库中的每一行都会影响全部查询的回答。这将体现在查询的重新加权中：相邻的数据库可能导致完全不同的重新加权，这将在生成的$h_t$中观察到，这些$h_t$将共同形成大纲。

boosting过程的运行时间与查询数$|\mathcal{Q}|$和基本大纲生成器的运行时间呈准线性关系，与数据域大小$|\mathcal{X}|$无关。这为构建有效且准确的隐私保护机制提供了一条新途径，类似于机器学习文献中的Boosting方法：算法设计者可以处理构建弱隐私保护基本大纲生成器的任务（可能容易得多），并自动获得更强的机制。