# 六、查询增强

在前面的小节中，我们重点讨论了私有查询发布的问题，在这个问题中，我们坚持将最坏情况的错误限制在所有查询上。 如果我们只要求较低的平均误差，给定查询的一些分布，我们的问题会更容易吗？ 在本节中，我们看到答案是否定的：给定一种能够以低平均误差解决查询发布问题的机制，给定查询的任何分布，我们可以将其“提升（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](https://github.com/doubleheiker/algorithmic-foundation-of-dp-zh-cn/blob/master/6-Boosting-for-Queries/Base-synopsis-generators/A-generalization-bound.html)）：如果我们能找到一个大纲，它能为几个选定的问题提供准确的答案，那么实际上这个大纲就能为大多数问题提供准确的答案！我们将这一事实应用于基础学习器，基础学习器从$$\mathcal{Q}$$上的分布中采样，并产生一个“弱”大纲作为输出，该大纲为$$\mathcal{Q}$$中的大多数权重产生“好”答案，以差分私有的方式boosting，以获得对所有Q都好的大纲。

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

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