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

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

8) Until 达到迭代次数或者满足迭代阈值 τ;
,
9) Return w s y n 和 ;
∗
ˆ x
n
在算法 1 中, 首先工人本地加噪并上传所做任务的值 (第 1, 2 行), 然后服务器迭代更新工人质量、任务重要
性以及任务的“真值” (第 3–8 行), 最后返回相关值 (第 9 行). 其中用计算所有任务前后两次“真值”差距的平均值是
否小于 τ 来判断是否满足迭代阈值 τ. 具体地讲, τ 的计算方式如公式 (21) 所示:

N ∑

∗ ∗
ˆx − ˆx
n,k n,k+1
t=1
τ = (21)
N
其中, ˆ x ∗ 和 ˆ x ∗ 分别表示第 n 个任务的第 k 次和第 k+1 次得到的“真值”.
n,k n,k+1
通过算法 1 可以得到每个工人的质量和任务重要性. 除此之外, 还可以得到每个任务的初始“真值”以备最终
真值发现使用. 现有研究表明真值发现容易受到初始值的影响, 因此, 经过 NWIE 后处理后的 NATURE 能得到较
好的噪音“真值”精度.

3.3 效用感知的自适应剪枝
在得到工人的质量和任务的重要性后, 需要在满足 LDP 的约束下, 同时考虑 LDP 下真值发现的总体误差裁
减掉部分值, 从而提高最终的数据质量. 为此, 首先给出本文需要的剪枝问题的形式化定义并形式化优化问题. 接
着, 本文在分析 LDP 下总体误差的基础上设计具有多项式时间复杂度的求解算法.
假设有 M 个工人和 N 个任务形成的大小为 M × N 的稀疏矩阵. 已知每个工人的质量 w s 和任务的重要性 ,
y n
本文剪枝得到一个子集, 该子集要能够同时保证工人的质量最高、任务的重要性最大以及保证所有任务都有值被
留下.
一种可能的做法是按照工人质量或者任务的重要性贪心地裁剪值, 不过这种做法可能降低最终数据集的质
量, 甚至是导致真值发现失败.
(1) 从剪枝掉的数据量来说, 若剪枝少的话, 则无法起到剪枝的效果, 剪枝太多可能导致剩下数据的信息量不
够. 显然, 无论哪种情况, 都会降低最终得到的“真值”精度.
(2) 从剪枝掉的工人来说, 其可能是高质量的工人, 这显然会浪费信息.
(3) 从剪枝掉的任务值来说可能导致某些任务没有值. 某些任务可能被工人做的次数较少, 有可能这些值都会
被剪枝掉, 将会导致无法得到相关任务的“真值”.
为此, 本文提出效用感知的自适应剪枝方法 (utility-aware adaptive pruning, UAP). 该方法的主要思想是根据工
人质量和任务的重要性效用感知且自适应地剪枝掉一些值. 下面首先给出本文形式化的剪枝问题 (公式 (22)), 并
证明该剪枝问题是 NP-hard 的, 接着设计了具有多项式时间复杂度的求解算法并分析复杂度, 最后给出算法流程.
(1) 问题形式化及 NP-hard 证明

 ∑
argmax (w s +y n )



 ˜ I

 ˜ I sn =1


 ∑
 M
 (22)
  ˜ I sn ⩾ 1, ∀n = 1,2,...,N
 
 
  s=1


s.t. ∑
  N
 
  ˜ I sn ⩾ 0, ∀s = 1,2,..., M
 
n=1
其中, ˜ I 表示剪枝后工人所做任务的指示矩阵, 如果剪枝后第 s 个工人做了第 n 个任务, 那么 ˜ I sn = 1, 否则 ˜ I sn = 0. 目
标函数表示需要剪枝后的矩阵中工人的质量和任务的重要性最大, 以期获得较好的表示. 第 1 个约束条件表示
每个任务至少要有一个工人的提交值, 第 2 个约束条件表示某个工人的所有值可能完全被剪枝掉, 也可能完全被
保留.
定理 4. 公式 (22) 所示的剪枝问题是 NP-hard 的.
证明: 本文将公式 (22) 所示的剪枝问题规约为已知的加权集合覆盖问题 (weighted set cover problem, WSCP).