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

3418 软件学报 2025 年第 36 卷第 7 期

对待求解变量求偏导可得:

 ∂L

2
 = 2σ w a1 +λ

 1

∂w a1



 ∂L

 2
 = 2σ w a2 +λ

 2

 ∂w a2 (37)


 .

 .

 .




 ∂L



 = λ

∂w aM

 ∂L

2
 = 2σ w b1 +µ

 1

∂w b1



 ∂L

 2

 = 2σ w b2 +µ
 2

 ∂w b2
(38)


 .

 .
 .






 ∂L

 2
 = 2σ w bM−1 +µ
 M−1
∂w bM−1
将公式 (37) 和公式 (38) 左右两边分别相加可得:

M−1 M−1
∂L ∂L 2
M ∑ ∑ ∑
+ = 2 σ (w ai −w bi )+ Mλ+(M −1)µ (39)
i
∂w ai ∂w bi
i=1 i=1 i=1
M−1
∂L ∂L
M ∑ ∑
根据拉格朗日乘子法, 需要 + = 0, 则要求让尽可能多的项为 0, 那么使得 Mλ+(M −1)µ = 0.根
∂w ai ∂w bi
i=1 i=1
M−1 M−1
∑ ∑
M ∑
据前两个约束条件可得 w ai − w bi = 0, 进而有 (w ai −w bi ) = −w aM . 显然如果

i=1 i=1 i=1
M−1 M−1
∑ ( )∑
2
2 σ (w ai −w bi ) ⩾ 2min σ 2 i (w ai −w bi ) → 0 (40)
i
i=1 i=1
便可证得结论.
M−1
∑
2
由于 w M → 0, 需要使得 −2 σ w aM 尽可能靠近 0.
i
i=1
2
−1
2
σ = σ = σ = ... = σ 2 2 L ⩾ L 2 .
2
显然当 1 2 3 M−1 = minσ 时满足约束条件, 也就是 1
i
即证得 L 1 > L 2 . 因此剪枝很有必要.
定理 8. NATURE 引入的总误差较小.
证明: 根据分析算法总的误差为:

 ∑ M 1 
 
  √  
2 
1 N ∑   d 2n −d 1n 2 s=1 w 
s 
MAE ≈    +    (41)
N    ε π M   
n=1    
通过公式 (41) 可以看出, 在变量中, 由于 0 ⩽ w s ⩽ 1 且 M ∈ {1,2,3,...}, 因此 MAE 和某个工人的质量 w s 和用户
数量 M 负相关. 在 NATURE 中, 本文剪枝掉了低信息量的工人和任务值, 因此会得到较高的数据效用.
此外, 从引理 1 中达到最小误差的约束条件可以看出, 当最终数据的质量尽可能相等时误差最小. 本文通过对
工人效用感知地进行剪枝, 可以保证留下的都是高质量的工人, 这些工人的质量接近, 因此总误差也会较小.

4.1.3 复杂度分析
本节将分析 NATURE 算法的通信复杂度和计算复杂度.
(1) 通信复杂度
通信仅发生在算法的第 1 阶段, 也就是每个工人上传自身加噪数据给服务器. 共需交换 O(MN). 显然该复杂