摘要：给定 Omega 域上定义的一个元组集合 D，我们研究了在 Omega 上构建直方图（histogram）以逼近 D 中的元组分布的差分隐私算法（differentially private algorithms）。对于该问题现有的解决方案大多数都采用了一种分层分解方法（hierarchical decomposition approach），其递归式地将 Omega 分成子区域并计算每个子区域的有噪声元组数，直到所有的噪声数都低于一个特定的阈值。但是，这种方法需要我们

(i) 在 Omega 的分割中的递归深度上施加一个限制 h；

(ii) 设置每个计数中的噪声，使之与 h 成比例。

h 的选择是一个非常严重的难题：h 太小会导致直方图粒度太粗糙，h 太大则会导致当在确定一个子区域是否应该被分割时在元组计数中出现太多的噪声。此外，h 不能直接基于 D 而进行调制；否则，h 自身的选择就会暴露隐私信息和违反差分隐私。为了弥补现有方法的不足，我们提出了一种直方图构建算法 PrivTree，该算法采用了分层分解（hierarchical decomposition），但完全消除了对预定义的 h 的需求。PrivTree 的核心是一种全新的机制，其可以

(i) 在拉普拉斯分布（Laplace distribution）上利用一种新分析；

(ii) 让我们可以在决定应该分割哪个子区域时仅使用常量的噪声，而无需担心分割的递归深度（recursion depth）。我们在建模空间数据上演示了 PrivTree 的应用，结果表明其可以被扩展到能处理序列数据（其中子区域中的决策并不是基于元组数，而是一个更复杂的度量）。我们在许多不同的真实数据集上的实验表明 PrivTree 在数据效用方面显著超越了当前最佳水平。

©本文为机器之心编译，转载请联系本公众号获得授权。

　　?------------------------------------------------

加入机器之心（全职记者/实习生）：[email protected]

投稿或寻求报道：[email protected]

广告&商务合作：[email protected]