Page 488 - 《软件学报》2025年第7期

张朋飞 等: 基于自适应剪枝的满足本地差分隐私的真值发现算法 3409

LDP, 在此基础上基于拍卖方法设计了满足个体理性等激励要求的真值发现新方法. 为了严格满足 LDP, Zhang 等
人 [26] 结合采样与推断提出了一种针对高维场景的严格满足 LDP 的新方法. 进一步地, 他们 [27] 结合概率化估计与
聚合来提升现有方案的精度.
综上, 现有研究要么针对离散值所设计, 要么对于连续值不严格满足 LDP. 同时现有研究均潜在假设数据是
纯净的或者是能在非隐私下被预先处理的. 然而实际中工人出于隐私泄露的担心, 群智感知服务器无法在非隐私
下预先处理数据. 为此, 本文针对连续值提出基于自适应剪枝的新方法 NATURE.

2 预备知识

2.1 真值发现
[7]
真值发现的典型算法是 CRH (conflict resolution on heterogeneous data) . 其遵循真值发现的一般原则, 即给予
数据更接近“真值”的工人更高的权重, 通过对来自不同质量工人提供的数据进行加权聚合来得到最终的“真值”.
通过交替迭代“真值估计” (公式 (1)) 和“权重更新” (公式 (2)) 直至收敛.

M N s
∑ ∑
w s · x n
s=1
n=1
∗
x = ∑ M ∑ N (1)
n
w s
s=1 n=1

 ∑ N ( ) 
s
 d x , x ∗ 
 
 n n 
  n=1  
w s = −log  ∑   (2)
 M ∑ N
s
 ( ) 
 d x , x ∗  
s=1 n=1 n n
s
其中, M、N 分别是工人数和任务数. w s 是第 s 个工人的权重, x 是第 s 个工人提交给第 t 个任务的值. x 是第 t 个
∗
t t
任务计算得到的真值, d(·) 往往采用欧氏距离来估算工人提交值和估算真值的差距.

2.2 本地差分隐私
本地差分隐私 (LDP) 的形式化定义如下.
定义 1. LDP. 假设有一个随机算法 M, 其定义域为 Dom(M), 值域为 Ran(M), 如果对于任意两条数据记录
′ ∗
t、t ∈ Dom(M), 以及任意一个输出 t ∈ Ran(M), 有下列不等式成立:

ε
Pr[M(t) = t ] ⩽ e ·Pr[M(t ) = t ],
∗
∗
′
则算法 M 满足 ε-LDP, 其中 ε 为隐私保护参数.
对于有些复杂的隐私保护问题, 通常需要多次应用 LDP 算法, 此时需要将隐私预算进行合理分配.
定理 1. 串行组合定理. 假设有满足 LDP 的随机算法 M 1 ,M 2 ,...,M n , 其对应的隐私参数分别为 ε 1 ,ε 2 ,...,ε n ,
(∑ n )
当在同一数据集上使用这些随机算法时, 它们构成的算法提供 ε i -LDP.
i=1
定理 2. 并行组合定理. 假设有满足 LDP 的随机算法 M 1 ,M 2 ,...,M n , 其对应的隐私参数分别为 ε 1 ,ε 2 ,...,ε n ,
当这些随机算法作用于不相交的数据集 D 1 ,D 2 ,...,D n 时, 它们构成的算法对这些数据集提供 max(ε i )-LDP.
定理 3. 后处理定理. 假设有满足 LDP 的随机算法 M A 和工作在 M A 输出上的任意算法 M B , 那么算法 M B 也
满足同级别隐私保护强度的 LDP.
一种典型的方法是采用 Laplace 机制, 在该机制中向数据中的每一维注入服从均值为 0 的 Laplace 分布的噪音
1 |x| ∆f
f (x) = e − λ . 其中 λ = , ∆f 是查询函数的敏感度. 比如如果查询某个值, 该值的范围为 [d 1 ,d 2 ], 那么 ∆f = d 2 −d 1 .
2λ ε

2.3 问题陈述
如图 1 所示, 假设有 N 个任务 T = {t 1 ,t 2 ,...,t N } 需要进行真值发现, 共有 M 个工人 U = {u 1 ,u 2 ,...,u M } 参与到
LDP 的真值发现中来. 工人 s 做了 |M s | 个任务. 每个工人的隐私预算为 ε. 本文的目标是在严格满足 LDP 的条件下
x , 求得各个任务的真值 .
s
∗
ˆ x
保护各个工人的值 t n
如表 1 所示是本文可能用到的主要符号说明.