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

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

3.2 噪音感知的权重和重要性估计

在得到工人上传的噪音值 x s ′ 之后, 为了对工人和任务剪枝提供必要的依据, 除了工人的权重之外, 本文引入
n
任务的重要性, 用于衡量工人提交的关于该任务的值对最终精度的影响. 考虑到数据中蕴含的表示工人质量的高
斯噪音 [6,7] 和为隐私保护注入的拉普拉斯噪音, 根据噪音数据求得“真值”的建模方法如下.
′ ∗ 2 α 是混合分布
在本文的模型中, 每个观测值 x 都是一个以真实值 x 为中心、协方差为 σ I N 的混合分布, 其中
i
的比例. 实际中受到主客观因素的影响, 每个工人不可能是一个完美的工人, 也就是说每个工人的可靠性存在上
界, 因此本文限制 σ i ⩾ σ 0 . 最大化以下似然函数:

M ∏[
]
2
2
∗
αN(x | x ,σ I N )+(1−α)L(x | x ,2σ I N )
′
∗
′
i i
i=1
 ( ) N [ ] ( ) N [ ]
M ∏ ′ ∗ 2 ′ ∗
 1 ∥x − x ∥ 1 ∥x − x ∥ 
=   α √ exp − i +(1−α) exp − i    (3)
 2σ 2 
i=1 2πσ i i 2σ i σ i
取负对数后展开得到:

   √ N [ ] 
∗ 2
∗ 2
∗
′
′
MN M ∑   ∥x − x ∥   1−α  2π   ∥x − x ∥ ∥x − x ∥ 
′

i
i
i


ln(2π)− Mlnα+  Nlnσ i + −ln  +    exp −  (4)
1




2  2σ 2  α  2  2σ 2 σ i 
i=1 i i
x
由于 ln(1+ x) ⩽ x 且 e ≈ 1+ x, 得到以下优化问题:

   √ N 
 ′ ∗ 2  
  ∥x − x ∥
  i 1−α  2π    

   Nlnσ i +    
  −    
 
 M ∑ 2    
 MN  2σ α 2  

 
   i  
min  ln(2π)− Mlnα+    , s.t. σ i ⩾ σ 0 (5)

x ∗ ,σ  2  ( ′ ∗ 2 ′ ∗ ) 



  ∥x − x ∥ ∥x − x ∥ 

 i=1  i i
  
  − +1 
2σ σ i
  
 2 
i
{ √ } √
′ ∗
由于 σ i = max σ 0 ,∥x − x ∥/ N , 同时根据方差公式并便于计算, 定义 σ 0 = 1/ N, 得到:
i
 
  √ 
 ′ ∗ 2 N ( ) 
 ∑  d∥x − x ∥ N √  ∑ 
  1−α  2π   ( )
  i   ′ ∗ 2 ′ ∗  ′ ∗ 
   N∥x − x ∥  + (6)
min    −     ∥x − x ∥ − i   Nln∥x − x ∥ 
i
i
x ∗  2 α 2 2  

 
∥x ′ −x ∗ ∥<1 ∥x ′ −x ∗ ∥⩾1
i i
′
∗
假设 ℓ = ∥x − x ∥, 最终的优化问题为:
i

 √ √  √
  N  N
 
  (1−α)  2π   2 d(1−α)  2π 
  2
 1    ℓ − 
          ℓ, 0 ⩽ ℓ < 1

  −
  α  2    dα  2  (7)





2lnℓ, ℓ ⩾ 1

分别用 w s 和 y n 表示第 s 个工人的质量和第 n 个任务的重要性. 为了同时得到工人质量和任务的重要性, 本文提
出噪音感知的权重和重要性估计算法 (noise-aware weight and importance estimation, NWIE). 该算法的主要思想是同
时考虑数据中蕴含的内源性的高斯噪音以及注入的外源性的 Laplace 噪音来推断工人的质量和任务的重要性.
在 NWIE 中, 根据公式 (7) 构建如公式 (8) 所示的约束优化问题. 其最小化工人上传噪音值 x n s′ 和待求解“真值”
∗
ˆ x 之间的加权距离. 同时, 考虑工人的质量和任务的重要性, 如果求得的“真值”偏离高质量的工人和重要的任务,
n
那么在目标函数中给予其更大的惩罚. 公式 (8) 中的两个约束条件分别用来约束权重和工人的质量分布取值在 0–1
之间.

 √ √  √
  N  N 
M ∑ N ∑
  
   2π   ( ∗ 2 2 N  2π  s′ ∗ 
 
)


 s′
s′

∗
 min w s y n 1−     x − ˆx −     x − ˆx +2lnx − ˆx  

 


      n n   n n n n  
 w s ,ˆx ∗ ,y n 2 N 2
 n
 s=1 n=1


 

 M
 ∑
 
 
 e −w s = 1 (8)

 
 
 
 
  s=1
s.t.


 
 
 
 N ∑
 
  −y n
  e = 1
 
 
 
n=1