# Selecting Workers Wisely for Crowdsourcing When Copiers and Domain Experts Co-exist
## 5 Truth Discovery  
This section presents our truth discovery method. We observe that there are two relations between workers' credibility and tasks' truth: (i) given a task \(t_{j}\), if the worker's credibility for \(t_{j}\) is high, then his/her answer is likely to be the truth for \(t_{j}\); (ii) given a worker \(w_{i}\), if \(w_{i}\) often answers tasks correctly, then \(w_{i}\) has a high credibility. Therefore, truth and workers' credibility depend on each other. Based on these intuitions, we developed our approach, in which the truth computation step and the worker credibility estimation step are iteratively conducted until convergence. Next, we introduce these two steps in detail and analyze the time complexity of the truth discovery step.  
**Truth computation step:** In this step, workers' credibility is assumed to be fixed. Then, the estimated truth \(q_{j}\) can be inferred through weighted aggregation. In general, for each task, we obtain the estimated truth by the following formula.  
\[\bar{q_{j}}=\frac{\sum_{w_{i}\in\hat{W}_{ij}}q_{i}^{j}\cdot q_{i}^{j}}{\sum_{w_ {i}\in\hat{W}_{ij}}q_{i}^{j}} \tag{13}\]  
This follows the principle that answers from reliable workers are considered more in the aggregation.  
**Worker credibility estimation step:** In this step, workers' credibility is identified based on the current estimated truth. As \(q_{i}^{j}\) denotes worker \(w_{i}\)'s credibility for task \(t_{j}\), we decide whether to improve or reduce the credibility of \(w_{i}\) according to the difference \(e_{i}^{j}\) between \(a_{i}^{j}\) and \(\bar{a_{j}}\). We used the following principles to update the worker's credibility: (i) If \(e_{i}^{j}\) is less than the threshold \(\theta\), we think worker's answer is good and improve his/her credibility. (ii) If \(e_{i}^{j}\) is larger than \(\theta\), we believe that worker's answer is poor and his/her accuracy is reduced. We use the indicator function to represent this:  
\[F=\begin{cases}1,\ e_{i}^{j}\leqslant\theta\\ 0,\ e_{i}^{j}>\theta\end{cases} \tag{14}\]  
Then, we calculate the accuracy of the worker \(q_{i}^{j}\):  
\[q_{i}^{j}=(q_{i}^{j}+0.5\cdot(1-q_{i}^{j}))^{F}\cdot(q_{i}^{j}-0.5\cdot\frac{e _{i}^{j}}{|I|}\cdot q_{i}^{j})^{|F-1|} \tag{15}\]  
The above formula shows how to improve the credibility of reliable workers and reduce the credibility of unreliable workers.  
After we obtain the new credibility of workers, we can calculate the estimated truth again. We iteratively calculate these two values until they converge. The estimated truth obtained after convergence is the final estimated truth we need, that is the last round of \(q_{j}\). In the truth discovery, there is also the step of updating worker domain expertise, which we analyze in Section 6.1. The pseudo code of the whole truth discovery algorithm is shown in Algorithm 4.  
**Time complexity:** For each task, suppose it takes \(u\) iterations to converge, then the time complexity of obtaining the final \(\bar{T}_{j}\) is \(O(uk)\). The time complexity of updating worker domain expertise is \(O(|W||D|)\). Thus, the total time complexity is \(O(|T|(uk+|W||D|))\). In practice, \(u\leq 20\), the time complexity is linear.  
```
1:The set of answers \(\{<t,w,a>\}\)
2:truth \(\bar{a}\), updated worker domain quality
3:for\(j=1\) to \(|\operatorname{T}|\)do
4:repeat
5: compute \(\bar{a_{j}}\) by (13)
6:for each \(w_{i}\in\hat{W_{l_{j}}}\)do
7: compute \(q_{i}^{j}\) by (14,15)
8:endfor
9:until convergence
10:for each \(w_{i}\in\hat{W_{l_{j}}}\)do
11: compute \(v_{i}^{k}\) by (16)
12:endfor
13:endfor
14:return \(\bar{a}\), updated worker domain quality
```  
**Algorithm 4** Truth discovery.