五、泛化

在本章中,我们泛化了上一节的查询发布算法。结果,我们得到了任意低灵敏度查询(不仅是线性查询)的界限,还有线性查询的新界限。这些泛化也为查询发布和机器学习之间的联系提供了一些启示。

第 4 章中的 SmallDB 离线查询发布机制是我们称之为 Net 机制的一个特例。我们发现,两种机制都产生了合成数据库,这为在隐私数据库上的任何查询 Q\mathcal{Q} 的返回值提供了一种方便的逼近方法:只评估合成数据库上的查询,并将结果作为有噪声的答案。更一般地说,一种机制可以产生任意形式的数据结构,与固定的、公共的算法(独立于数据库)一起提供一种近似查询值的方法。

Net 机制SmallDB 机制的一个简单泛化:首先,独立于实际数据库,定义一个数据结构的 α\alpha-Net,其独立于真实数据库,这样使得通过发布的数据结构对 Q\mathcal{Q} 中的任何查询进行求值,可以很好地(在加性α误差范围内)估计私有数据库上的查询值。下一步,对Q\mathcal{Q} 中的任何查询应用指数机制对 Net 中的元素进行选择,指数机制中的效用函数将 Net 中元素的最大错误最小化。

我们还对 在线可乘权重算法 进行了泛化,以便我们可以使用任何其他在线学习算法实例化该算法,以通过一组查询来学习数据库。我们注意到,这种机制可以在线运行,也可以离线运行,在这种情况下,这些向 “在线” 机制请求的查询集合是由 “隐私区分器” 来选择的,该隐私区分器识别当前假设与实际数据库大不相同的查询。这些查询将在在线算法中生成更新步骤。事实证明,“隐私区分器”等同于不可知论学习算法,该算法为有效的查询发布机制提供了一个明确的来源。

在下面各节中,我们将讨论查询集 Q\mathcal{Q} 类型的数据结构。

定义 5.1 一类查询 Q\mathcal{Q} 有一些数据结构类 D\mathcal{D},从这些数据结构类 D\mathcal{D} 中提取的数据结构 DD 被隐式地赋予了一个分析函数 Eval:D×QR\text{Eval:}\mathcal{D}\times\mathcal{Q} \to \mathbb{R},我们可以用它来分析 DD 上的任何查询。然而,为了避免被符号所困扰,当上下文中的含义清楚时,我们将简单地写 f(D)f(D) 来表示 Eval(D,f)\text{Eval}(D,f)

Copyright © GuoJohnny 2019 all right reserved,powered by Gitbook修订时间: 2020-01-02 13:11:41

results matching ""

    No results matching ""