四、带相关误差的线性查询

隐私数据分析中最基本的原语之一就是能够回答对数据集的数值查询。在上一章中，我们开始看到可以通过向查询答案中添加独立的噪声来实现此目的的工具。 在本章中，我们将继续进行这项研究，并发现通过添加相关的噪声的方法代替以前添加独立噪声的方法，我们可以获得更高精确度回答更为大量查询的能力。在这里，我们看到了解决此问题的两种特定机制，我们将在下一节中对其进行概括。

在本节中，我们考虑的算法比简单使用拉普拉斯机制合成的算法能更精确地解决查询发布问题。这种改进是可能的，因为查询集是作为一个整体来处理的（即使在在线设置中也是如此），所以允许将各个查询的噪音关联起来。要立即发现符合这些思路的某些内容，请考虑第1章中描述的差异攻击中的一对查询。“数据库中有多少人具有镰状细胞特征？”和“除了 X 以外，数据库中有多少人具有镰状细胞特征？” 假设有一种机制使用拉普拉斯机制回答了第一个问题，然后在提出第二个问题时回答“您已经知道了近似答案，因为您刚刚问过我几乎相似的问题。”对这两个问题的协调响应不会比单独执行任何一个问题所引起的隐私损失更多，因此节省了（少量）隐私。

查询发布问题是很自然的：给定一类查询通过数据库 $\mathcal{Q}$，我们希望为每个查询 $f_i \in \mathcal{Q}$ 发布一些答案 $a_i$ ，使得误差 $\max_i|a_i-f_i(x)|$ 尽可能小，而仍然保留着差分隐私 $\ ^[1]$。回想一下，对于任何低敏感性查询，我们可以应用拉普拉斯机制向这些查询的每个答案添加不同的，独立的噪声。不幸的是，在固定的隐私级别上，比如 $(\varepsilon,0)$-隐私保证，我们必须向答案添加一定大小的噪声，这些噪声是由尺度参数为 $|\mathcal{Q}|$ 的拉普拉斯机制产生的。添加这样大小的噪声是因为这是组合查询的敏感度可能增长的速率。同样，对于 $(\varepsilon,\delta)$ 隐私保证来说，噪声尺度参数为 $\sqrt{|\mathcal{Q}|\ln(1/\delta)}$。例如，假设我们的查询类别 $\mathcal{Q}$ 仅包含同一查询的许多副本：$f_i=f^*$。如果我们使用拉普拉斯机制来释放答案，它将添加独立的噪声，因此每个 $a_i$ 将是均值为 $f^*(x)$ 的独立随机变量。显然，在这种情况下，噪声速率必须以 $|\mathcal{Q}|$ 增长。因为否则 $a_i$ 的平均值将收敛到真实值 $f^*(x)$，这将违反隐私要求的。但是，在这种情况下，因为对于所有 $i$ 来说 $f_i = f^*$，所以仅对 $f^*$ 近似一次（$a^* \approx f^*(X)$），并为所有 $i$ 释放 $a_i=a^*$ 更有意义。在这种情况下，噪声尺度将不必再按 $|\mathcal{Q}|$ 。在本章中，我们旨在通过添加非独立噪声作为查询集的函数来设计比 Laplace 机制更精确的算法（误差范围为 $\log |\mathcal{Q}|$）。

（原文注[1] 正是隐私限制使问题变得有趣。如果没有这个约束，查询发布问题只需为每个查询输出精确的答案，就可以轻松而优化地解决。）

回想一下，我们的数据全体是 $\mathcal{X}=\{\chi_1,\chi_2,...,\chi_{|\mathcal{X}|}\}$，数据库用 $\mathbb{N}^{|\mathcal{X}|}$ 直方图表示。线性查询类似于计数查询，但归一化为取区间 $[0,1]$ 中的值，而不仅仅是布尔值。具体地说，线性查询 $f$ 采用 $f:\mathcal{X}\to[0,1]$ 的形式，并应用于数据库 $x$，返回数据库上查询的总和或平均值（我们将考虑两者，具体取决于哪个更便于分析）。当我们认为线性查询是返回平均值时，我们将它们称为标准化线性查询，并且其函数值为：

$$f(x) = \frac{1}{\Vert x\Vert _1}\sum_{i=1}^{|\mathcal{X}|}x_i\cdot f(\chi_i)$$

当我们认为线性查询返回求和值时，我们将它们称为非标准化的线性查询，并且其函数值为：

$$f(x)=\sum_{i=1}^{|\mathcal{X}|}x_i\cdot f(\chi_i)$$

【补充： 该部分约定的符号所代表的含义可以参考2.3节中内容。其中 $\mathcal{X}=\{\chi_1,\chi_2,...,\chi_{|\mathcal{X}|}\}$ 表示数据全体， $\chi_i$ 表示不同类别的数据集。$x_i$ 表示 $\chi_i$ 的记录数量。$\Vert x\Vert _1$ 代表 $\ell_1$ 距离概念，$\Vert x\Vert _1$ 表示数据库 $x$ 的记录数。$|\mathcal{X}|$ 表示数据全体中所有的类别总数。又有 $f(\chi_i)\to [0,1]$】

无论何时我们声明一个界限，都应该从上下文中清楚地知道我们所说的是标准化查询还是非标准化查询，因为它们接受的值在非常不同的范围内。注意，标准化线性查询采用 $[0,1]$ 中的值，而非标准化查询采用$[0,\Vert x\Vert _1]$ 中的值。

注意，根据该定义，线性查询的灵敏度 $\Delta f\leq 1$ 。后面的章节将讨论任意的低敏感度查询。

我们将介绍两种技术，分别用于离线和在线案例。令人惊讶的是，离线技术是指数机制的一个即时应用，它使用了来自学习理论的采样边界！该算法简单应用指数机制，该指数机制的范围等于所有小型数据库 $y$ ，并且质量函数 $u(x,y)$ ：

$$u(x,y) = -\max_{f\in \mathcal{Q}} |f(x)-f(y)| \qquad \qquad \quad(4.1)$$

采样边界（见下面的引理4.3）告诉我们，$x$ 的 $\ln|\mathcal{Q}/\alpha^2|$ 个元素的随机子集很可能给我们所有 $f(x)$ 的一个很好的近似（具体地，加性误差由 $\alpha$ 限制），因此我们知道将可能的输出集合限制到小的数据库是足够的。我们实际上并不关心潜在输出数据库是小的，只关心它们别太多：它们的数量在效用证明中起作用，这是指数机制效用定理（定理3.11）的直接应用。更具体地说，如果潜在输出的总数不是太多（特别是，低效用输出的总数不是太多），则坏输出与好输出的比率不是太大。

在线机制虽然事先不知道整个查询集，但其精度与离线机制相同，是稀疏向量技术的直接应用。因此，隐私是能保证，但效用性将需要证明。关键在于，即使对于一组非常大的计数查询，也很少有查询是“重要的”；也就是说，重要的查询将是“稀疏的”。与稀疏向量算法一样，我们可以根据有效查询的数量缩放噪声，而不依赖于查询的总数。

在我们继续介绍这些机制之前，我们只给出一个有用的线性查询类的示例。

示例 4.1 假设数据库的元素由 $d$ 个布尔特征表示。例如，第一特征可以表示个人是否是男性或女性，第二特征可以表示他们是否是大学毕业生，第三特征可以表示他们是否是公民等等。我们的数据全体为 $\mathcal{X}=\{0,1\}^d$。给定这些属性的子集 $S \subseteq \{1,...,d\}$ ，我们可能想知道数据集中有多少人具有这些属性。（例如，“肺癌家族史的男性大学毕业生占数据集的多少？”）这自然定义了一个查询，称为 单调关联查询。由属性 $S$ 的子集进行参数化，并定义为：$f_S(z)=\prod_{i\in S}z_i$，其中 $z\in \mathcal{X}$。所有此类查询为 $\mathcal{Q}=\{f_S:S \subseteq \{1,...,d\}\}$ ，并且大小为 $|\mathcal{Q}|=2^d$。回答的集合有时称为列联表或边际表，是发布有关数据集的统计信息的常用方法。通常，我们可能对所有答案的关联都不感兴趣，而只是对那些询问特征集 $S$ 中固定大小（$|S|=k$）的子集的答案感兴趣。这一类的查询 $\mathcal{Q}_k=\{f_S:S \subseteq \{1,...,d\},|S|=k\}$ 大小为：$(_k^d)$ （排列组合公式 $C_d^k$）

这类查询只是本节中给出的算法可以准确回答的一个示例。（请注意，如果我们也希望允许询问否定属性的（非单调）关联，我们也可以做到这一点——只需将特征空间从 $d$ 翻倍到 $2d$，并为所有 $i$ 设置 $z_{d+i}=1-z_i$，其中所有 $i \in \{1,...,d\}$。）

【补充个人理解例4.1：数据库的元素由 $d$ 个布尔特征表示，可以知道，数据总体 $\mathcal{X}$ 有 $d$ 个特征求其笛卡尔乘积表示：$\mathcal{X}=\{\underbrace{\{0,1\}\times,...,\{0,1\}}_{\text{d}}\}=\{0,1\}^d$。存在对这些特征进行查询，并列查询特征个数从 $1$ 个到 $d$ 个。同时，我们想知道关于符合这些特征的人数占总人数的多少，会自然而然使用：$f_S(z)=\prod_{i\in S}z_i$ 这个公式。这个公式中 $z_i$ 为拥有 $i$ 特征的人数在总人数的占比，显然总的占比为各个特征占比的乘积。对特征的查询集合（不限特征个数）即为文中的 $\mathcal{Q}=\{f_S:S \subseteq \{1,...,d\}\}$，由集合的子集总数公式可得：$|\mathcal{Q}|=2^d$。

之后，对于去非条件的查询，需要对特征进行拓展，如最后一段所属。举例来说即： “肺癌家族史的男性非大学毕业生占数据集的多少？” 】