# Iterative Learning for K-Approval Votes in Crowdsourcing Systems
## 4 Algorithms  
In this section, we explain the design of our algorithm and the process used to estimate the correct answers. To avoid confusion in notation, we use uppercase \(K\) to represent the  
Figure 3: An illustration of task–worker assignments. number of selections and lowercase \(k\) to represent the iteration number of our algorithm. In our setting, workers to which task \(i\) is assigned are allowed to vote for \(K_{i}\) alternatives. For each edge \((i,j)\), a response is denoted as:  
\[\vec{A}_{ij}\in\mathrm{A}=\left\{\sum_{s=1}^{K_{i}}\vec{e}_{s}\Big{|}\vec{e}_{s }\in U_{D_{i}}\right\}\]  
where \(\mathbb{U}_{D_{i}}=\{\vec{e}_{u}|u\in[1:D_{i}]\}\) comprises \(D_{i}\) dimensional unit vectors. To extract the correct answers from unreliable responses of workers, we propose an iterative algorithm for \(K\)-approval voting systems. Our algorithm takes advantage of two types of messages between a task node and a worker node. A task message is denoted as a \(D_{i}\) dimensional vector, \(\vec{x}_{i\to j}\). Each component of this vector corresponds to the likelihood, meaning the possibility of being the correct answer to task \(i\). A worker message, \(y_{j\to i}\), represents how reliable the worker \(j\) is. Since these worker messages are strongly correlated with the reliability \(p_{ij}\), our algorithm can assess relative reliability. We will empirically verify the correlation between \(\{y_{j\to i}\}\) and \(\{p_{ij}\}\) in Section 6. The initial messages of our iterative algorithm are sampled independently from the _Gaussian_ distribution with unit mean and variance, i.e., \(y_{j\to i}^{(0)}\sim\mathcal{N}(1,1)\). Unlike EM-based algorithms [10; 11], our approach is not sensitive to initial conditions as long as the consensus of the group of workers is positively biased. Now, we define the adjacent set of task \(i\) as \(\partial i\), and similarly, the adjacent set of worker \(j\) is defined as \(\partial j\). Then, at the \(k^{th}\) iteration, both messages are updated using the following rules: For \(\forall(i,j)\in E\),  
\[\vec{x}_{i\to j}^{(k)}=\sum_{j^{\prime}\in\partial i\setminus j}\frac{1}{K_{i }}\Big{(}\vec{A}_{ij^{\prime}}y_{j^{\prime}\to i}^{(k-1)}\Big{)}, \tag{1}\]  
\[y_{j\to i}^{(k)}=\sum_{i^{\prime}\in\partial j\setminus i}\frac{1}{K_{i^{ \prime}}}\Big{(}\vec{A}_{ij^{\prime}}-\Big{(}\frac{K_{i^{\prime}}}{D_{i^{ \prime}}}\Big{)}\vec{1}\Big{)}\cdot\vec{x}_{i^{\prime}\to j}^{(k-1)}. \tag{2}\]  
At the task message update process shown in (1), our algorithm gives a weight to the response according to the relative reliability of a worker. At the worker message update process shown in (2), it gives greater relative reliability to a worker who strongly follows the consensus of other workers. Figure 4 describes two vectors in the message vector space. As shown above, \(\frac{1}{K_{i^{\prime}}}\big{(}\vec{A}_{ij^{\prime}}-(\frac{K_{i^{\prime}}}{D _{i^{\prime}}})\vec{1}\big{)}\) represents the difference between the response of worker \(j\) solving task \(i^{\prime}\) and the expectation of a random response \(\big{(}\frac{K_{i^{\prime}}}{D_{i^{\prime}}}\big{)}\vec{1}\) with normalizing factor \(\frac{1}{K_{i^{\prime}}}\). Additionally, \(\vec{x}_{i^{\prime}\to j}^{(k-1)}\) is the weighted sum of responses of other workers who have solved the task \(i^{\prime}\). Thus, the inner product of these two vectors in (2) can assess the similarity between the response of worker \(j\) for the task \(i^{\prime}\) and sum of those of other workers who have solved the task \(i^{\prime}\). A larger positive similarity value of the two vectors means that worker \(j\) is more reliable, whereas a negative value means that the worker \(j\) does not follow the consensus of other workers, and our algorithm regards the worker \(j\) as unreliable. Specifically, when \(\vec{x}_{i^{\prime}\to j}^{(k-1)}\) and \(\frac{1}{K_{i^{\prime}}}\big{(}\vec{A}_{ij^{\prime}}-(\frac{K_{i^{\prime}}}{D _{i^{\prime}}})\vec{1}\big{)}\) are orthogonal for fixed task \(i^{\prime}\), the inner product of the two vectors is close to zero.