\Large Crowdsourced Task Routing via Matrix Factorization
Hyun Joon Jung and Matthew Lease\thanks{School of Information
We describe methods to predict a crowd worker's accuracy on new tasks based on his accuracy on past tasks. Such prediction provides a foundation for identifying the best workers to route work to in order to maximize accuracy on the new task. Our key insight is to model similarity of past tasks to the target task such that past task accuracies can be optimally integrated to predict target task accuracy. We describe two matrix factorization (MF) approaches from collaborative filtering which not only exploit such task similarity, but are known to be robust to sparse data. Experiments on synthetic and real-world datasets provide feasibility assessment and comparative evaluation of MF approaches vs.\ two baseline methods. Across a range of data scales and task similarity conditions, we evaluate: 1) prediction error over all workers; and 2) how well each method predicts the best workers to use for each task. Results show the benefit of task routing over random assignment, the strength of probabilistic MF over baseline methods, and the robustness of methods under different conditions.
jung_sdm14.tex
\documentclass[twoside,leqno,twocolumn]{article}  
\usepackage{ltexpprt} 
\usepackage{epsfig}
\usepackage{algorithm}
%\usepackage{algorithmic}
\usepackage{algpseudocode}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{ifpdf}
\usepackage{url}
%\usepackage{pseudocode}
%\usepackage{fancybox}

\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}
\renewcommand{\algorithmicforall}{\textbf{for each}}
\algnotext{EndFor}
\algnotext{EndWhile}
\algnotext{EndIf}
\algnotext{EndFunction}

\newcommand{\ma}{{MA$_k$}}

\begin{document}

%\setcounter{chapter}{2} % If you are doing your chapter as chapter one,
%\setcounter{section}{3} % comment these two lines out.

\title{\Large Crowdsourced Task Routing via Matrix Factorization}
\author{Hyun Joon Jung and Matthew Lease\thanks{School of Information, University of Texas at Austin. Correspondence: \texttt{hyunJoon@utexas.edu}, \texttt{ml@ischool.utexas.edu}.}}

\date{}

\maketitle

 
%\pagenumbering{arabic}
%\setcounter{page}{1}%Leave this line commented out.

\begin{abstract}
We describe methods to predict a crowd worker's accuracy on new tasks based on his accuracy on past  tasks. Such prediction provides a foundation for identifying the best workers to route work to in order to maximize accuracy on the new task. Our key insight is to model similarity of past tasks to the target task such that past task accuracies can be optimally integrated to predict target task accuracy. We describe two matrix factorization (MF) approaches from collaborative filtering which not only exploit such task similarity, but are known to be robust to sparse data. Experiments on synthetic and real-world datasets provide feasibility assessment and comparative evaluation of MF approaches vs.\ two baseline methods. Across a range of data scales and task similarity conditions, we evaluate: 1) prediction error over all workers; and 2) how well each method predicts the best workers to use for each task. Results show the benefit of task routing over random assignment, the strength of probabilistic MF over baseline methods, and the robustness of methods under different conditions. 
\end{abstract}

 {\bf Keywords}: \textit{crowdsourcing, task routing, matrix factorization, task recommendation}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
\label{sec:intro}

\begin{figure*} [t]
\centering
\ifpdf
\includegraphics[height=32mm]{mf_process3.pdf}
\fi
\vspace{-10pt}
\caption{Matrix factorization (MF) prediction of crowd workers' accuracies using a worker-task matrix. (Left) A worker-example matrix contains labels from workers for each task. (Center) From the worker-example matrices, we measure each worker's accuracy vs.\ a ground truth sample, then merge all workers' accuracies into a single worker-task matrix. (Right) Unobserved workers' accuracies are predicted by MF (shown in red), and these predictions allow us to tailor individual work assignments to workers predicted to perform well for a given task.}
\label{fig:mf_process}
\vspace{-10pt}
\end{figure*}

Crowdsourcing is quickly changing data collection practices in both industry and data-driven research areas such as natural language processing~\cite{Snow2008}, computer vision~\cite{Vijayanarasimhan2011}, and information retrieval~\cite{Law2011a}. However, quality concerns persist, especially with rudimentary crowdsourcing platforms like Amazon's Mechanical Turk (MTurk) where factors such as anonymity, piece-work pay, and limited worker interaction can contribute to poor quality crowd work.  Various statistical approaches have been proposed for mitigating these issues, such as by aggregating inputs from multiple workers~\cite{Snow2008} or filtering out inaccurate workers~\cite{ramesh2012identifying}. %or iterative worker management~\cite{Dow2012}. 
%Notwithstanding this effort, current crowdsourcing platforms, such as Amazon Mechanical Turk (MTurk), %\footnote{\url{www.mturk.com}}, 
%predominantly rely upon random task matching between a task requester and a crowd worker, which does not leverage the crowd members' varying skill levels and familiarity for different tasks. Little work to date has investigated effective matching of workers and tasks as another aspect of ensuring quality.

MTurk's default use case assumes workers self-select tasks.  In principle, this is often a good idea. For example, using an in-house labor platform, Law et al.\ found higher quality work when workers were allowed to self-select work rather than be assigned it arbitrarily.  However, an important assumption here is that workers are able to effectively search and find tasks of interest. In fact, prior work has shown that limited task search capabilities on MTurk in practice often lead to task selection being more random than one might otherwise expect~\cite{Chilton2010}. Moreover, lack of support for task routing in MTurk's default setup has led to a dearth of research in this area. Nonetheless, %As such, MTurk today can be to some degree viewed as making random task assignments, which may be poor quality. 
like spam filtering, the promise of work filtering / tailored work assignments is to better match workers to work for which they are best suited, with potential to increase work quality and satisfaction and reduce inefficiency of task selection. 

We  describe methods to predict a crowd worker's accuracy on new tasks based on his accuracy on past tasks. Such prediction provides a foundation for identifying the best workers to route work to in order to maximize accuracy on the new task. Note our methods do {\em not} require example feature representations and so are broadly applicable across crowdsourcing tasks. Our key insight, based on preliminary analysis on our MTurk data (Section~\ref{sec:real_data}), suggests cross-task worker accuracies being correlated based on task similarity. Intuitively, more similar tasks should yield more similar worker accuracy across tasks. Of course, ``spammers'' may still perform uncorrelated, inaccurate work across tasks. By modeling similarity to past tasks, work history can be better integrated to predict new task accuracy. 

Critically, note that such prediction cannot be done for one-shot or small scale data collection, where there is no work history, or where workers completely little work before leaving and never returning. While many academic studies have tended to report low rates of worker retention across tasks and within-task completion, we posit this may reflect community sampling bias of one-off, infrequent academic studies. In contrast, commercial crowd work offers large volume and repetition that allows workers to amortize time to spent learning a task, returning to tasks for which they are already familiar for greater retention and completion rates. %While the MTurk data used here is relatively small (Section~\ref{sec:real_data}), it is drawn from such a use case where we see significant worker retention across tasks.

We describe two approaches to predict worker accuracies based on matrix factorization (MF), widely used in collaborative filtering problems to predict missing values in a matrix using low-rank feature vectors~\cite{Koren2009}. To predict unobserved workers' performance on a new task, we construct a worker-task matrix, where entries reflect a worker's observed accuracy on past tasks, evaluated against some sample of ground truth data (Figure~\ref{fig:mf_process}). We investigate two well-known MF models: Singular Value Decomposition (SVD) and Probabilistic Matrix Factorization (PMF)~\cite{Ruslan2008}. Prior work~\cite{Lee2012_CF} describes the two MF's tradeoffs for general recommendation systems. We revisit such questions by investigating these issues in our setting of crowd worker accuracy prediction.

%Accumulated crowdsourced data sets may have different characteristics as compared to a typical recommendation data sets. Thus, for realistic experiments, we conduct a 

Experiments on synthetic and real-world datasets provide feasibility assessment and comparative evaluation of MF approaches vs.\ two baseline methods. Across a range of data scales and task similarity conditions, we evaluate methods in two ways: RMSE prediction error over all workers, and average accuracy of the top \textit{k} ranked workers according to each prediction method.

%This study begins from an analysis on accumulated crowdsourced data sets. While a typical crowdsourcing is conducted by a task requester at one time, crowdsourcing has been recently used repeatedly over time in order to improve the quality of data sets or obtain various types of data sets at scale. Unlike one-shot and relatively small-scale crowdsourcing, repeated crowdsourcing enable us accumulate the information about crowd workers' performance over time. Human task routing problems comes from the accumulated workers' performance information which is composed of a set of workers in a column and a set of tasks in a row. In this setting, task routing means how to allocate a particular task to a crowd worker whose past performance (accuracy) on a task is highly reliable. Our model is agnostic of the semantics of the numerical entries, and one might alternatively use the same model on worker affinities (preferences) in lieu of performance metrics. However, as in behavior-based recommendation systems, sparse observations make this challenging in practice. For example, most crowd workers perform a small subset of tasks. Moreover, to predict future performance we must have reasonable estimates of past performance, which may also be difficult (i.e., a worker may complete only a few examples on a given task).

%We fundamentally aims at effectively routing human tasks and finally improving the quality of crowdsourced data sets. To find strong candidate crowd workers for a specific task, we propose a matrix-factorization (MF)-based task routing model. MF is widely used in collaborative filtering problems since it is able to predict missing values in a matrix using low-rank feature vectors given by matrix factorizing~\cite{Koren2009}. To predict unobserved workers' performance in a particular task, we approach the worker-task matrix from a similar collaborative filtering viewpoint. We assume that task categories are predefined, and that the performance of each crowd worker is measured by task accuracy with respect to ground truth. 

%We consider each worker's accuracy for a particular task in a worker-task matrix (akin to a user rating for a specific item in a user-item matrix in collaborative filtering). To predict an unobserved worker's accuracy in the worker-task matrix, we investigate two well-known matrix factorization models: Singular Value Decomposition (SVD) and Probabilistic Matrix Factorization (PMF). In addition, we compare the performance and its benefits of MF-based task routing with non-MF based task routing baselines. For the validation of our study, 

%Primary research questions for this work include:
\begin{description}
\item[RQ1: MF-based Prediction Accuracy]{\em How does MF prediction performance vary as a function of task similarity, matrix size, and matrix density for predicting worker accuracies across tasks? How feasible and robust is it to challenging conditions?}
\item[RQ2: Finding Top Workers]{\em Does task routing to predicted top $k$ workers outperform random assignment? If so, by what degree, and how do proposed MF methods (PMF and SVD) compare vs.\ simpler baseline methods (average and weighted average)?}
\item[RQ3: The Effect of Spammers]{How robust is MF-based task routing to the existence of spammers?}
\end{description}
Results show the benefit of task routing over random assignment, the strength of probabilistic MF over baselines, and robustness of methods to different conditions. 

%To investigate these questions, we study the effect of task similarity, the size of a worker-task matrix, and the density of a worker-task matrix using synthetic data sets which reflects characteristics of real crowdsourced data sets. Furthermore, we study the performance of the proposed models' prediction with a real world crowdsourcing data set. These experiments demonstrate that MF-based models effectively predict unobserved workers' accuracies, enabling routing of tasks to effective workers without observing any past performance of the workers on these tasks. Furthermore, MF-based models effectively find strong candidates for a particular task which will be critical in terms of maintaining a pool of reliable workers.
%even though the workers had not participate in the task in the past. 

%{\bf Contributions.} We demonstrate that MF-based task routing is able to predict unobserved workers' accuracy in various scenarios. Crucially, we show our approach does not merely identify strong workers in general, but particularly benefits from correlating worker accuracy to ask similarity. Secondly, we demonstrate practical feasibility of automatically selecting strong candidates for a particular task. % by adopting matrix factorization models.  



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Related Work}

%\newcommand{\namecite}[1]{\citeauthor{#1}~\shortcite{#1}}

%While numerous studies have focused on label aggregation~\cite{Snow2008}, task design~\cite{Kulkarni2012}, and workflow design~\cite{Dai2011,Weld2011} in order to ameliorate quality concerns in crowdsourcing, 

MTurk's standard method of task self-selection has led to relatively few studies on task routing to better match workers to tasks, though work considered task assignment in other venues, such as Wikipedia~\cite{cosley2007suggestbot}. 
%\cite{Law2011a} investigated the performance effects of letting workers choose tasks (in a more flexible way than MTurk task search) vs.\ assigning them tasks. 
%task routing by choice in terms of crowdsourcing relevance judgments. 
Others have studied the cooperative refinement and task routing among on-line agents with regard to prediction tasks~\cite{KamarEce;HackerSeverin;Horovitz2012}. Bernstein at al.~\cite{Bernstein2012} investigate task routing in terms of real-time crowdsourcing. Though informative, these studies do not address finding strong candidates for a particular task from a task requester's viewpoint. Other work on task markets chains together of different worker competencies for problem solving~\cite{shahaf2010generalized}.

Karger et al.~\cite{Karger2011a} present a task assignment model based on random graph generation and a message-passing inference algorithm, in order to route tasks to crowd workers under homogeneous labeling tasks. Ho et al.~\cite{Ho2013} attempt to generalize this model to allow heterogeneous tasks by applying on-line primal-dual techniques. However, neither study answers the question of how to predict the unobserved workers' performance, which is critical to task routing in practice. Zhang et al.~\cite{zhang2012task} consider a related task routing task that seeks to engage people or automated agents to both contribute solutions and route tasks onward. 

%In this paper, we pursue matrix factorization (MF) algorithms to infer unobserved workers' performance, and prior work on these methods will be discussed subsequently. In regard to human computation applications, 
Jung and Lease~\cite{Jung2012-hcomp} study MF methods to improve the quality of crowdsourced labels, using a PMF model to infer unobserved labels in order to reduce the bias of the existing labels. They do not consider task routing. Yi et al.\ investigate matrix completion for crowdclustering, and more recently inferring user preferences~\cite{yi2012crowdclustering,Yi13}. Yuen et al.~\cite{Yuen2012} consider workers' task selection preferences and propose a task recommendation model based on PMF. However, they motivated their approach on conceptual grounds and did not evaluate it. Most recently, Kolobov et al.~\cite{Kolobov13} investigate task routing of multiple tasks across a common pool of workers.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section{Motivation}
%\label{sec:anal_cdata}

%This study begins from a preliminary analysis on accumulated crowdsourced data sets. An assumption behind the analysis is that an accumulated crowdsourced data set has its unique characteristics which may be critical to quality improvement of the data set.
%
%\subsection{Worker-Task Matrix Construction}
%A typical result from crowdsourcing is a set of tuples $S$ = $\{w, e, l\}$ which is composed of a crowd worker $w$, an example $e$, and a label $l$ generated by a worker on the task. However, a set of tuples is inappropriate for finding the implicit relations between workers and examples. Thus, we construct a worker-example table $E$ as shown in Figure~\ref{fig:mf_process} (b). Jung and Lease~\cite{Jung2012-hcomp} made use of this table in order to predict unobserved worker's labels in the matrix. We extend this idea to a worker-task relational model which consists of a set of workers and a set of tasks. In order to construct a worker-task matrix $R$, we first measure each worker's performance by predefined tasks. We assume that there exist $n$ different tasks and we have enough ground truth labels that will be used to measure workers' performance in terms of a metric. For simplicity, we use accuracy as a metric of workers' performance; however, it is possible to use any other metric that may be more expressive and powerful. 
%
%Once workers' accuracies by task are measured, we construct a worker-task relational model $R$ by merging the measured accuracy of workers into the table, as shown in Figure~\ref{fig:mf_process}(b). 
%
%% ML: leave this out
%%During the process, we discard the accuracy of a worker whose number of labels by a particular task is less than a threshold $\alpha$ in order to assure the confidence of accuracy. 
%
%\subsection{A Preliminary Analysis on a Worker-Task Matrix}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Worker-Task Matrix Factorization}
\label{sec:mf_model}

%As introduced in the Figure~\ref{fig:mf_process} (a) and (b), we obtain a worker-task matrix from a real crowdsourced data set collected by a well-known company. From this matrix, we observe three interesting issues: (1) a distribution of workers' accuracies in a particular task follows a normal distribution as shown in Figure~\ref{fig:real_turk_histogram}, (2) task similarity (correlation between two distributions of workers' accuracies), matrix size (number of workers \& tasks), and matrix density (sparseness) may influence on the prediction performance of MF, and (3) correlation analysis between two tasks suggests that highly accurate workers show consistent performance while low quality workers show random and noisy performance as shown in Figure~\ref{fig:scatter_tasks}. Unlike our initial expectation, a mixture of two tasks' accuracy distribution does not show a multivariate normal distribution. One of the plausible assumption is that there exist random workers who shows random performance irrespective of task similarity. Interestingly, our preliminary study shows that the frequency of random workers increase in proportion to the decrease of accuracy. In other words, the less accurate workers may show the more random patterns.
%
%These observations lead us to design comprehensive synthetic experiments in order to find an answer to our research questions RQ1-3 from Section~\ref{sec:intro}. 

%Given the partially observed worker-task matrix, we finally aim at predicting unobserved workers' %accuracies in order to route a particular task to strong candidates who are likely to perform the task accurately. As shown in Figure~\ref{fig:mf_process} (c), we finally obtain the full matrix via matrix factorization and use it for task routing. The details of MF-based methods is introduced subsequently. 

Matrix factorization (MF) has been studied for effectively recommending an item for a user in an online marketplace and advertisement. Our intuition is that finding strong candidates for a specific task is very similar to the recommendation of items for a specific user in collaborative filtering~\cite{Jung2012-hcomp}. In addition, latent features should capture how a worker successfully makes a label for a specific task. For example, two workers would achieve high accuracy for a task type if they both have similar amounts of domain knowledge for this task type. If we can discover these latent features, we should be able to predict workers' accuracies by task. Given a partially observed worker-task matrix, we aim to predict unobserved workers' accuracies (e.g., on new tasks) so that we might route work optimally, or recruit or exclude particular workers for a given new task.

%in order to route a particular task to strong candidates who are likely to perform the task accurately

%\subsection{ Singular Value Decomposition (SVD)}
{\bf Singular Value Decomposition (SVD)} %To infer unobserved accuracy in a worker-task matrix $R$, we consider two types of matrix approximation algorithms in this study. One of the popular ways to infer unobserved values in matrix is using Singular Value Decomposition (SVD) which 
%is a low-rank approximation based on minimizing sum-squared distance. SVD 
seeks an approximation matrix $\hat{R} = W^{T} T$ of the given rank which minimizes the sum-squared distance between the original matrix $R$ and $\hat{R}$. It has a critical drawback: it is %dependent only on the observed elements in $R$ and is 
undefined for incomplete matrices. Thus, it does not solve the problem of sparseness in the given $R$.

%\subsection{Probabilistic Matrix Factorization (PMF)}
{\bf Probabilistic Matrix Factorization (PMF)} 
%For the more advanced matrix factorization method, we consider probabilistic matrix factorization, which 
was introduced by Ruslan~\cite{Ruslan2008} and has demonstrated excellent performance in the Netflix challenge. We have {\it M} crowd workers, {\it N} tasks, and a worker-task matrix $R$ in which $R_{ij}$ indicates the accuracy of worker $i$ for task $j$. Let $W \in \mathbb{R}^{D*M}$ and $T\in \mathbb{R}^{D*N}$ be latent feature matrices for workers and tasks, with column vectors $W_i$ and $T_j$ representing $D$-dimensional crowd worker-specific and task-specific latent feature vectors, respectively. The conditional probability distribution over the observed cells $R \in \mathbb{R}^{M *N}$ is given by Equation 2. Indicator $I_{ij}$ equals 1 {\em iff} worker {\it i}'s accuracy is measured over task {\it j}. We place zero-mean spherical Gaussian priors on worker and task feature vectors.
%\begin{eqnarray} 
%p(R|W,T,\sigma^2) = \prod_{i=1}^{M} \prod_{j=1}^{N}[\mathcal{N}(R_{ij} | W_{i}^{T} T_{j},\sigma^{2})]^{{I}_{ij}}\\
%p(W|\sigma^2_{W}) = \prod_{i=1}^{M} [\mathcal{N}(W_{i} | 0,\sigma_{W}^{2} \mbox{I})]\\
%p(T|\sigma^2_{T}) = \prod_{j=1}^{N} [\mathcal{N}(T_{j} | 0,\sigma_{T}^{2} \mbox{I})] 
%\end{eqnarray}
To estimate model parameters, we maximize the log-posterior over example and worker features with fixed hyper-parameters. Maximizing the posterior with respect to {\it W} and {\it T} is equivalent to minimizing squared error with L2 regularization:
\vspace{-10pt}
\begin{multline}
E = \frac{1}{2}\sum_{i=1}^{M} \sum_{j=1}^{N} I_{ij}(R_{ij} - W_{i}^{T}T_{j})^{2} \\
+\frac{\lambda_{W}}{2}\sum_{i=1}^{M}\Vert W_{i} \Vert^{2}_{Fro} +\frac{\lambda_{T}}{2}\sum_{j=1}^{N}\Vert T_{j} \Vert^{2}_{Fro}
\end{multline}
where $\lambda_{W} = \sigma_{W} / \sigma, \lambda_{T} = \sigma_{T} / \sigma$, and $\Vert\centerdot \Vert_{Fro}^{2}$ denotes the Frobenius Norm. We use gradient descent to find a local minimum of the objective for $W$ and $T$. Finally, we infer unobserved workers' accuracies in the worker-task matrix $R$ by the scalar product of {\it W} and {\it T}. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Experiments}
\label{sec:Experiments}

\begin{figure} [t]
\centering
\ifpdf
\includegraphics[height=31mm]{real_turk_normal_distribution_new.pdf}
\fi
\vspace{-10pt}
\caption{Histograms of Workers' Accuracy in three different tasks. All these three histograms show that workers' accuracy distribution follow a normal distribution.}
\label{fig:real_turk_histogram}
\vspace{-10pt}
\end{figure} 

\begin{figure} [t]
\centering
\ifpdf
\includegraphics[height=40mm]{data_generation_new3.pdf}
\fi
\vspace{-10pt}
\caption{Scatter plots of accuracies across two tasks in (a) MTurk data and (b) synthetic data.}
\label{fig:scatter_tasks}
\vspace{-10pt}
\end{figure} 

%This section presents empirical answers to research questions RQ1-3 from Section~\ref{sec:intro}. We describe our experimental setup in Section~\ref{sec:exp_setting}, then proceed to present results on synthetic data (Section~\ref{sec:eval_results}) and real MTurk data (Section~\ref{sec:real_exp}).
 
%This section aims to empirically validate our hypothesis introduced in section 1. %as follows: 1) To what extent task similarity influences the performance of MF-based prediction of crowd worker's accuracy. 2) Does the increase of worker-task matrix size lower in the performance of matrix factorization based crowd worker's accuracy prediction? 3) To what extent does the density of worker-matrix matrix influence the performance of MF-based prediction of crowd worker's accuracy? 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\subsection{Experimental Setup}
%\label{sec:exp_setting}

%For the validation of our hypotheses, we evaluate the effectiveness of MF-based worker accuracy prediction under two conditions: synthetic data sets and a real-world data set. Synthetic data sets are generated in order to simulate various settings in a worker-task relational model. 
Our first set of experiments use synthetic data, letting us carefully control a variety of experimental variables for detailed analysis.  Following this, we describe additional experiments with real crowd data to assess performance of methods for a specific case of actual operating conditions. We begin by describing these datasets.

Our generative model for synthetic data is based up the the MTurk dataset consisting of three tasks (Section~\ref{sec:real_data}). Figure~\ref{fig:real_turk_histogram} plots histograms showing the number of workers achieving various levels of accuracy in each of three MTurk tasks. These histograms show a strong normal tendency, which we quantify later via a Shapiro-Wilk test~\cite{Shapiro1965} (Table~\ref{table:summary_real_data}). In addition, Figure~\ref{fig:scatter_tasks} (left) plots average worker accuracy for task 1 vs.\ task2 and shows strong correlation at high accuracies (similar plots for task 1 vs.\ task 3 and task 2 vs.\ task 3 are not shown). In other words, the best workers appear to be fairly accurate across tasks, whereas other workers show less correlation across tasks, perhaps tending toward uncorrelated accuracies as average accuracy across tasks decreases (e.g., the increasing prevalence of ``spammers'' as we consider lower average accuracies). These observations suggest correlated worker accuracies across tasks, which might be reasonably well-fit by a multivariate normal distribution with appropriate covariance. We further develop this idea below.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Synthetic Data.}
\label{sec:data_gen}

%-------------------------------------
\begin{algorithm}
\caption{Generative model for synthetic data}
\label{alg:data_gen}
\begin{algorithmic}[1]
\Require $taskSimilarity,numWorkers,numTasks$
\State $\sigma = matrix(taskSimilarity,numTasks,numTasks)$
\State $m = multivarNormal(numWorkers,\mu = 0.5,\sigma)$
\ForAll {$t \in [1:numTasks]$}
	\State $accuracy[1:numWorkers] = m[t]$
	\ForAll {$j \in [0:0.8]$ by $0.1$}
		\State $strata = [j, j+0.1]$
		\State  $workers = findWorkers(accuracy,strata)$
		%\State $\alpha = strata*0.1$
		\State $\alpha = (0.8-j)*10$ \Comment $\alpha \in \{80,70,\ldots,0\}$
		\State $subset = getRandomSample(workers,\alpha\%)$
		\ForAll {$worker \in subset$} 
			\State $max = $0.9/(9-j*10) \Comment $max \in \frac{0.9}{[9,8,7,\ldots,1]}$
			\State $accuracy[worker] = uniform[0,max]$
		\EndFor
	\EndFor
\EndFor
\Ensure $m$
\end{algorithmic}
\end{algorithm}

Our model of worker behavior makes three key assumptions. Firstly, we model workers' accuracies as following a normal distribution N($\mu$, $\sigma$), based on our real crowd accuracy histograms (Figure~\ref{fig:real_turk_histogram}) and supported by a Shapiro-Wilk test~\cite{Shapiro1965} confirming high normality (Table~\ref{table:summary_real_data}). Secondly, we assume worker accuracy is correlated across tasks in proportion to task similarity. In addition to knowing people naturally exhibit varying expertise/skill across tasks, we also observe this in our real crowd data (correlation in Figure~\ref{fig:scatter_tasks}'s left plot). Thirdly, we posit the existence of ``spammers'' who exhibit low accuracy, uncorrelated across tasks, due to any number of factors, such as fatigue, low language competency, negligence, etc. Because better workers are less likely to be spammers (by definition), we expect fewer spammers when average worker accuracy is high, and the ratio increasingly shifting toward more spammers at lower accuracies.

Our generative model for synthetic data (Algorithm~\ref{alg:data_gen}) takes three parameters as input which we vary as experimental variables: task similarity $s$, number of tasks $t$, and number of workers $w$. We sample a multivariate normal distribution of accuracies (per-task average accuracy), providing correlation across tasks by specifying covariance matrix $\sigma$ filled with $s$ ({\tt rmvnorm} function from {\tt mvtnorm} library in $R$). This ``optimistic'' distribution is free of spammers and reflects an idealized model of correlated accuracies. Next, we introduce spammers to produce an alternative ``pessimistic'' distribution by transforming a percentage of the idealized workers into spammers. To accomplish this, we first group workers by distributional strata over average accuracy across tasks (using a sliding window of size $0.1$). We then randomly sample a percentage of diligent workers from each strata and transform them into spammers by replacing their idealized per-task accuracy on each task with an accuracy sampled uniformly at random. 

Note that as a function of strata, we must decide (a) what percentage of workers to transform, and (b) the maximum accuracy of the interval from which to sample spammer accuracies. While our choice of functions here for (a) and (b) are relatively ad hoc, they enforce our principle above of finding fewer spammers as worker accuracy increases. We argue strengths of this model include: (i) its full description for reproducibility by others~\cite{paritosh2012human}; (ii) its implementation of over-arching modeling assumptions in some reasonable way; and (iii) an explicit discussion of how more accurate simulation might be achieved by further analysis and characterization of real crowd data properties. 

% This is both intuitive (e.g., an English major taking a comparative literature class vs.\ a calculus class), and partially evidenced by empirical data in Figure~\ref{fig:scatter_tasks}. 

\begin{table}
\centering
\begin{tabular}[h]{|c| c| c|c |}
\hline
{\bf \!\!Tasks} & {\bf Workers} &{\bf Accuracy} & {\bf Normality Test\!\!}\\ 
\hline
{\bf \!\!Task1} &206 & 0.676 & 0.9471 *\\ 
{\bf \!\!Task2} &384 & 0.599 & 0.99 *\\ 
{\bf \!\!Task3} &167 & 0.491 & 0.90 *\\ 
\hline
{\bf \!\!All} &443 & 0.596 & \\ 
\hline
\end{tabular}
\caption{Attributes of MTurk data with three tasks. Task similarity $s$ ranges from [0.545:0.719]. For all tasks, distribution of per-task worker accuracies follow a normal distribution with high statistical significance ($p<0.01$) under the Shapiro-Wilk test~\cite{Shapiro1965}.}
\label{table:summary_real_data}
\vspace{-20pt}
\end{table}

\subsection{MTurk Data.}
\label{sec:real_data}

We experiment with a commercial MTurk dataset which includes three different text processing tasks. Only workers with high approval ratings were allowed to perform work. While we cannot further describe the tasks or their similarity, we will show task similarity can be inferred automatically and varies. Moreover, asking a person to articulate a similarity score for two tasks is not a natural activity and expected to be difficult anyway, without experience or guidelines. As such, the ability to automatically infer task similarities without any reliance on manual tweaking is a strength of our approach.  

We also note ours is a retrospective study: workers self-selected what work to perform during actual data collection, and we simulate task assignment now after the fact. While such retrospective assignment methodology represents a common study design in active learning and community question answering research, we nonetheless method the usual limitations of such a study design.  In practice, we would have to contend with workers not performing tasks assigned to them, or that accuracy could diminish when people are assigned work instead of self-selecting that which most interests them.

Because a central goal of our work is to identify strong workers to whom work could be usefully assigned, there is little value in modeling workers who only briefly try out a task without completing much work. Consequently, we exclude workers who completed fewer than ten examples per task (37.4\% of workers retained for Task1, 43.2\% for Task2, and 30.8\% for Task 3). While modeling these other workers could be interesting in multiple respects (e.g., to study these ``flighty'' workers, or estimating worker accuracies from extremely sparse observations), we leave this for future work. 
%For the confidence of workers' accuracy, we exclude workers labeling fewer than 10 examples by each task ($\alpha$=10). 
%In practice, we do not know a worker's idealized average accuracy, but rather must estimate it from some combination of prior knowledge and/or observed labels vs. ground truth (i.e., gold) labels or labels from other workers. In this work, we assume a supervised context in which we have gold labels for some set of examples which we can use to estimate worker accuracy by simple relative frequency. 

Table~\ref{table:summary_real_data} characterizes remaining data for each task. 443 workers completed at least 10 examples on all 3 tasks, and 43\% of the (443 x 3) worker-task matrix observed. While prior crowdsourcing studies have tended to report lower rates of worker retention across tasks and within-task completion, the difference seen in our data may be indicative of a sampling bias between what is observed in one-off, infrequent academic studies vs.\ what is seen in commercial crowd work, where volume and repetition of familiar tasks lead to greater worker retention and completion rates. Greater study of commercial crowd data to assess such potential bias will be another interesting direction for future work.

%Figure~\ref{fig:real_turk_histogram} provided visual evidence of workers' per-task average accuracies following an approximately normal distribution. 
%Regarding the normality of the probabilistic distribution of workers' accuracies by task in the synthetic data sets, we verify the normality of our real-world data set by running a Shapiro-Wilk test~\cite{Shapiro1965}. As shown in the Table~\ref{table:summary_real_data}, the probabilistic distribution of each task follows a Normal distribution, and all tasks show correlation. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Metrics.}
\label{sec:metrics}

We report root-mean squared error (RMSE) and the mean accuracy of the top \textit{k} workers (\ma) according to some ranking function:
\vspace{-5pt}
\begin{equation*}
RMSE =\sqrt{\frac{\sum_{i,j} {(\hat{a}_{i,j} - a_{i,j})^{2}}}{n}}~~,~~ 
MA_k = \frac{1}{k}{\sum_{i=1}^{k}}{a_{i,j}}
\end{equation*}
%
%\vspace{-10pt}
%\begin{equation}
%MA = \frac{1}{k}{\sum_{i=1}^{k}}{a_{i,j}}
%\end{equation}
where $\hat{a}_{i,j}$ and ${a}_{i,j}$ respectively denote the predicted vs.\ observed worker accuracy for worker $i$ on task $j$. 

% The RMSE is intentionally selected over the other metrics, such as the mean squared error (MSE) or the mean absolute error (MAE). The RMSE is measured in the same units as the data, rather than in squared units, and is representative of the size of a typical error. Moreover,  the RMSE considers the larger error as more critical while the MAE only considers all the errors equally. Thus, we report all the prediction accuracy of the experiments based on the RMSE. 

While task similarity $s$ could be operationalized in many ways, in this study we adopt Pearson's correlation coefficient $r$ (i.e., $s=r$ in our study, but we preserve distinct notation of $s$ for generality). Following standard practice~\cite{Cohen1988}, we distinguish four specific levels of correlation in our experiments: weak ($r$=0.1), medium ($r$=0.4), strong ($r$=0.7), and very strong ($r$=0.9).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{PMF Model Parameters.}

MF infers unobserved, low dimensional factors (feature vectors) to explain observed workers' accuracies. We want to find an optimal dimensionality $D$ for these latent feature vectors. While larger $D$ is expected to yield more accurate prediction, it comes at a computational cost. Thus, it is common to optimize $D$ on development data. This development data is also used to optimize PMF regularization parameters $\lambda_{w}$ and $\lambda_{t}$ and learning rate $\epsilon$. Unlike our PMF formulation, SVD is parameter-free.

$\lambda_{w}$ and $\lambda_{t}$ are selected via 5-fold cross-validation, using {\bf only} 20\% of data for training and leaving 80\% for testing. 
%###????????????) for finding the parameters for a PMF model except the investigation on the effect of matrix density). 
For simplicity, we try only three settings each for $\lambda_{w}$ and $\lambda_{t} \in \{10^{-1}, 10^{-2}, 10^{-3}\}$, ultimately selecting $\lambda_{w} = \lambda_{t} = 0.01$. We use $\epsilon=0.005$ without tuning.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Baselines.}

One goal of our work is to assess the potential benefit of task routing at all (i.e., any approach) vs.\ just assigning tasks arbitrarily (i.e., random task assignment). While random assignment represents a very simplified model of how MTurk workers self-select tasks today, prior work has shown that MTurk's limited task search capabilities lead to task selection often being more random than one might expect otherwise~\cite{Chilton2010}. Thus for task routing experiments, random assignment provides our simplest, uninformed baseline.

A related but distinct goal of our work is to assess relative improvement of specific approaches proposed in Section~\ref{sec:mf_model} (SVD and PMF) vs.\ alternative, simpler but reasonable baseline methods one might utilize for automatic task assignment. 

Our first such informed baseline is to simply predict a worker's accuracy on a new task by his average accuracy on other tasks. A limitation of this baseline, however, is that it completely ignores task similarity. Moreover, since our generative model for synthetic data explicitly generates worker accuracies correlated across tasks by similarity (Section~\ref{sec:data_gen}), we expect a baseline exploiting this additional information should perform better. Our second informed baseline therefore computes an expectation (weighted average) across tasks based on task similarity rather than a simple average. 

% 10/14/13 ### -- this is important but out of space so cut, sadly
%Note that this weighted average baseline is unrealistically strong since it is provided knowledge of the true task similarities for weighted averaging. Firstly, this information is not provided MF methods (which implicitly infer correlation through matrix completion). Secondly, it is given true task accuracies, not estimated accuracies (i.e., computed Pearson correlation over workers doing both tasks). Thirdly, whereas such estimation is possible retrospectively, it is not possible at run-time since our task routing formulation intentionally does not provide any training data for the target task, only past tasks. The weighted average baseline thus represents an idealized, aggressive baseline, and not a practical one. 


\begin{figure*} [t]
\centering
\ifpdf
\includegraphics[width=170mm]{RMSE_matrix_density_dimension_new.pdf}
\fi
\vspace{-10pt}
\caption{(a) Matrix dimension vs.\ prediction accuracy and (b) Matrix Density (Training \%) vs.\ prediction accuracy. In (a), the x-axis shows the increase of task similarity ranging from 0.1 to 0.9 by 0.1. In order to investigate the effect of matrix dimension, we evaluate the prediction accuracy by increasing the number of tasks ($t$) and the dimensionality of feature vectors ($d = t-1$). Matrix density is fixed as 20\%. In (b), the x-axis shows the increase of matrix density from 10\% to 90\% by 10\%. In addition, we increase task similarity from 0.1 to 0.9 while fixing matrix dimension as 20 by 2,000 and the dimensionality of feature vectors ($d = 19$). %The mean of observed workers' accuracy in a worker-task matrix is used as a baseline for the comparison of the performance of prediction accuracy. %For training and testing, 20\% of cells in the matrix are considered as observed (used for training the models) and the remaining 80\% of cells are treated as unobserved (used for testing the performance of the models). 
}
\label{fig:task_similarity}
\vspace{-10pt}
\end{figure*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Synthetic Dataset Experiments}
\label{sec:eval_results}
%For the comprehensive investigation of the performance of the proposed models, we simulate various synthetic but realistic data sets. Experiments seek to answer several questions we raised earlier: MF-based Prediction Accuracy (RQ1), Finding top \textit{K} candidates (RQ2), and the effect of random workers in using the proposed model (RQ3). 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Experiment 1 (RQ1): MF-based Prediction Accuracy.}

%\subsubsection{Experimental Variables.}
%
%We vary $D \in \{5,10,15,20,25,30\}$ as an experimental variable, described later in the context of each experiment. Task similarity $s$ is set by varying Pearson's correlation $r$ between 0.1-0.9 (by 0.1). For the investigation of the effect of worker-matrix size, we vary the number of tasks from 5 to 30 (by 5) and the number of workers from 100 to 3000 (by 500). 

%The first question to be investigated is 
{\em To what extent do task similarity, matrix size, and matrix density influence MF-based prediction of crowd worker accuracies for varying task similarity?} We first measure RMSE of PMF and SVD methods vs.\ baseline methods for task similarity $s$ (Pearson's correlation $r$) $\in \{0.1,0.2,\ldots,0.9\}$, averaging 1,000 simulation trials for each setting of $s$. Results in Figure~\ref{fig:task_similarity} (a) and (b) show the RMSE achieved along the y-axis.

Our first set of experiments (Figure~\ref{fig:task_similarity}(a)) evaluate our ability to effectively predict worker accuracies across varying task similarity $s$, number of tasks, and number of workers. We vary the number of tasks from 5 to 30 (by 5) and the number of workers from 100 to 3000 (by 500). Four configurations of varying number of tasks $t$ vs.\ number of workers are shown: (5,500), (10,1000), (20, 2000), and (30,3000). Task similarity $s$ is varied along the x-axis. Matrix density is fixed at 20\% and dimensionality $D$ is set by $D=t-1$. 

Our second set of experiments (Figure~\ref{fig:task_similarity}(b)) evaluate our ability to effectively predict worker accuracies under varying task similarity $s$ and matrix density. Each of the four plots corresponds to a different task similarity $s \in \{0.1, 0.4, 0.7, 0.9\}$, matching the levels of Pearson correlation $r$ from {\em weak} to {\em very strong} as defined in Section~\ref{sec:metrics}. Matrix density varies along the x-axis (from 10-90\%). We fix the number of tasks ($t=20$), dimensionality ($D=t-1$), and the number of workers (2000). 

\begin{figure*} [t]
\centering
\ifpdf
\includegraphics[width=170mm]{MA_sim_topK3.pdf}
\fi
\vspace{-10pt}
\caption{(a) Matrix dimension vs.\ top \textit{10} workers' MA$_{10}$. The x-axis shows the increase of task similarity [0.1:0.9] and matrix dimension is increased across plots. (b) Task similarity vs.\ top \textit{k} workers' mean accuracy {\ma}. The x-axis shows the increase of top \textit{k} workers from 1 to 20. We evaluate {\ma} across increasing task similarity (0.1, 0.4, 0.7, 0.9). 15 tasks and 1,500 workers are used. Both (a) and (b) fix matrix density at 20\%.}
\label{fig:ma_exp}
\vspace{-15pt}
\end{figure*}

{\bf Task Similarity.} 
%Task similarity indicates to what extent crowdsourced tasks are similar to each other. The intuition behind this experiment is that the increase of task similarity will lead to improvement of prediction accuracy. 
{\em How similar do tasks need to be before we can make effective predictions?  How much do predictions improve with greater task similarity?} With only weak similarity $s=0.1$ (left-most point in all 4 plots in (a), left-most plot in (b)), RMSE of 0.21-0.23 can still be achieved, though this is far below the best RMSE$<$0.13 observed with very high task similarity.  Baselines seem sufficient, without need for MF methods.

As task similarity increases (across x-axis in (a) plots, and across plots in (b)), it tends to enable better prediction of worker accuracies across tasks, as expected. Moreover, we see PMF predictions improve by exploiting greater task similarity: both as the number of tasks and workers increase (a), or as matrix density increases (b). In contrast, SVD performs comparably to baselines in all four of the plots in (a); it does not benefit from increased task similarity even as the matrix size grows. While in (b) plots we do see SVD perform much better as $s$ increases with greater density, PMF still outperforms SVM by a wide margin.  

{\bf Matrix Size.} {\em How effectively can we predict worker accuracies when only small worker-task matrices (relatively few workers or tasks) are observed?  At what point (if any) does accuracy prediction break due as the matrix becomes too small?  How much does prediction improve with larger matrix size?}

Figure~\ref{fig:task_similarity}(a) shows that in the smallest case of 5 tasks and 500 workers, RMSE of 0.21-0.23 can still be achieved. Moreover, baseline methods seem sufficient in this case (comparable to MF methods). However, this is far below the sub-0.15 RMSE achieved by PMF with larger matrix sizes. As noted above, we see PMF capitalize on increasing task similarity $s$ with larger matrices while SVD does not. 

%In practice, a worker-task matrix may be initially very small, but the size of the matrix will increase as new workers and tasks are added to the matrix. For this situation, we investigate whether {\em the increase of worker-task matrix size lowers the performance of MF-based prediction of crowd workers' accuracy}? In this experiment, we aim to answer to the above question by understanding the effect of the change of the size of task-worker matrix on prediction performance. The size of the matrix is changed by two effects: the increase of task size or worker size. %The increase of the number of tasks and the increase of the number of workers may be equally considered for a MF process. However, the number of tasks is treated differently, since it is related to the dimensionality of feature vectors for training MF models, while the number of workers is irrelevant to feature vectors. It is common to choose the smaller of column size and row size as the dimensionality of feature vectors for MF.

%For the experiment of task size, we increase the number of tasks from 5 to 30 under the four different cases of task similarity (Pearson's correlation $r$=0.1, 0.4, 0.7, and 0.9). Figure~\ref{fig:task_similarity} (a) shows the effect of the number of tasks on prediction performance. The increase of task size leads to the improvement of prediction performance under medium or strong task similarity while there is no effect of task size under non-correlated tasks. Note that PMF outperforms the other models except the case of non-correlated tasks ($r$=0.1). The performance gap between SVD and the baseline increases as the correlation between tasks increases. In numerical terms, the prediction accuracy of the PMF model is highly accurate under strong correlation, which indicates that the error of a task routing based on the PMF model is expected to be small. 

%-----------------------------

{\bf The Effect of Matrix Density/Sparseness.} Prior crowdsourcing studies often report workers are often transient and rarely complete all tasks available. {\em What matrix density is needed to support effective worker accuracy predictions across tasks? How does prediction accuracy improve with increasing density?} 

%A typical worker-task matrix created from a raw crowdsourcing data is likely to be sparse or at least not fully dense since a crowd worker tends to participate in only a subset of tasks. This raises a question of {\em what extent the density of a worker-task matrix influences the performance of MF-based prediction of crowd workers' accuracy}? A basic assumption behind this experiment is that the denser a worker-task matrix, the more accurate prediction performance will be.

Figure~\ref{fig:task_similarity}(b) shows across plots, RMSE lies in [0.19-0.21] when density is only 10\%. As before, baseline methods seem sufficient when density is so low, with no improvement from MF methods. However, as noted above, both SVD and PMF improves dramatically vs. baselines with greater density, with PMF consistently dominating SVD across (b) plots. The best case RMSE$<$0.13 is observed under ideal settings of an extremely dense matrix and large worker-task matrix.

%For the experiment, we increase the density of a worker-task matrix by changing the number of observed cells in the matrix from 10\% to 90\% by 10\%. The effect of matrix density on prediction performance is also evaluated under the four different cases of task similarity as done in the previous experiments. Figure~\ref{fig:task_similarity} (b) shows the relationship between matrix density vs. prediction accuracy. No improvement of prediction accuracy is observed under very low task similarity (correlation $r$=0.1). However, the effect of matrix density on prediction accuracy increases as task similarity increases. In particular, PMF shows very accurate performance compared with the other models when the density of a worker-task matrix is greater than 30\%. The SVD model shows significant improvement as the density of the matrix increases, as expected from prior work~\cite{Lee2012_CF}. While this shows the suitability of using SVD under dense matrix conditions, it still under performs PMF. Moreover, the lower density matrix case is both more realistic and motivating for use.

{\bf RQ1 Summary.} Under worst case conditions, results show worker accuracies can be predicted with RMSE$\in[0.19-0.23]$, and that even simple averaging suffices is comparable to MF methods. However, as tasks exhibit even medium task similarity ($s=0.4$) significant gains are possible, and especially with steep with high correlation ($s=0.7$). Similar wins occur as matrix size increases, and with steep RMSE decreases beginning with matrix densities around only 30\%.  PMF consistently outperforms SVD in all cases where sufficient data exists to outperform baselines.

\subsubsection{Experiment 2 (RQ2): Finding Top Workers.}

RQ1 investigated our ability to predict worker accuracies across tasks in terms of RMSE.  For task routing, however, what we would really like to do is identify the top $k$ workers for a given task and route work to them; we do not care about specific accuracies, nor do we care about workers below this top $k$. We would like to know if routing work to some top $k$ workers (via any method) outperforms random assignment by some margin. If so, we would like to evaluate the relative benefit of proposed MF methods (PMF and SVD) vs.\ the simpler baseline methods (average and weighted average).

To answer these questions, we use some method (informed or random) to identify a set of $k$ workers, and we measure the average accuracy of these $k$ workers to compute {\ma} for each method. As in earlier experiments, informed methods use limited training set knowledge (20\%) of a worker's accuracy on $t-1$ other tasks to predict the worker's accuracy on held out task $t$, and we perform this prediction in round-robin fashion across tasks, with each task held out in turn and accuracy of workers on it predicted from the other tasks. In experiments here, after computing the average worker across $k$ workers for each task, we then average this average accuracy across tasks to arrive at {\ma} for each method.  We vary $k$ in these experiments.

%The previous section empirically validates that the MF-based task routing models show better performance in terms of predicting workers' accuracies. However, we are still wonder the benefits of MF-based task routing with regard to finding strong candidates for a specific task. The goal of task routing is not just to predict missing workers' accuracies in the matrix but assure the quality of predicted workers for the quality of crowdsourced data sets. In this experiment, we investigate our second question: {\em to what extent MF-based task routing brings the benefits with respect to finding strong candidates in comparison to non-MF based task routing?} We first measure the mean accuracy (MA) of top \textit{k} workers predicted by two MF models (PMF and SVD) and three baselines by increasing the number of top \textit{k} workers. 

As in Figure~\ref{fig:task_similarity}, Figure~\ref{fig:ma_exp} shows two sets of experiments (a) and (b) of four plots each. The first figure (a) shows matrix dimension vs.\ top \textit{10} workers' MA$_{10}$. The x-axis shows increasing task similarity [0.1:0.9]; matrix dimension is increased across plots. The figure (b) shows task similarity vs.\ top \textit{k} workers' mean accuracy {\ma}. The x-axis shows increasing $k\in[1:20]$ of top \textit{k} workers. We evaluate {\ma} across increasing task similarity (0.1, 0.4, 0.7, 0.9). 15 tasks and 1,500 workers are used. Both (a) and (b) fix matrix density at 20\%.

Results here are simpler and easier to understand than those in RQ1: informed assignment methods consistently outperform random assignment, MF methods outperform baselines, and PMF outperforms SVD. Overall, increase in task similarity brings increase in MA$_{10}$ (Figure~\ref{fig:task_similarity} (a)). Increase in matrix dimension also leads to a better performance in terms of finding strong candidates. When matrix dimension is very small (5,500), we see some fluctuations due to spammers.  %The only exception to these trends are with low density (20\%) and matrix size (5,500), where random assignment slightly outperforms simple average assignment, and SVD slightly outperforms PMF.

%Figure~\ref{fig:ma_exp} (a) shows task similarity vs.\ top \textit{k} workers' mean accuracy and matrix dimension, vs.\ (b) top \textit{k} workers' mean accuracy. As we expected, MF-based models (PMF\& SVD) outperform all three baselines in all the cases. It suggests that MF-based task routing effectively assures the quality of top \textit{k} workers since it is able to predict missing workers' accuracies unlike non-MF models. The weighted avg. baseline shows a better performance when task similarity is strong (\textit{s} $\ge$ 0.7); however, it still underperforms the MF-based models since it does not effectively predict strong candidates under the condition of matrix sparsity and the existence of random workers. The second experiment (b) also validates the advantage of MF-based task routing under the condition of fixed \textit{k = 10}. The PMF model is predominant in all the cases except a very small matrix, which the effect of random workers is expected to be greater than others.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Prediction With or Without Spammers.}
\label{sec:eval_random_workers}

\begin{figure} [t]
\centering
\ifpdf
\includegraphics[width=87mm]{random_worker_effects_new.pdf}
\fi
\vspace{-20pt}
\caption{Prediction of worker accuracies when spammers are absent or present (optimistic or pessimistic controlled synthetic data experiment), measuring the top-$k$ workers' mean accuracy {\ma} (left plot, bigger is better) and RMSE over all workers (right plot, lower is better). Task similarity is varied along the x-axis. We compare PMF vs.\ the weighted average baseline.}
\label{fig:random_effect}
\vspace{-20pt}
\end{figure}

%One of interesting characteristics in crowdsourced data sets are the existence of random workers. 
As discussed in Section~\ref{sec:data_gen}, spammers can be expected to degrade predictions of worker accuracies across tasks since such workers' accuracies across tasks are uncorrelated (by definition). {\em How robust are cross-task accuracy prediction methods to the presence of spammers?}

% ### ML 10/13/13: for MA, shouldn't we also look at a random assignment baseline for MA, to see whether task routing is really better?  Shouldn't we also try varying the degree of spammers in some way to assess under their varying presence (e.g., how many spammers, how their accuracy degrades). --> (HJ) That's good points. At this point, I don't have any numbers about the effect of varying the ratio of spammers. Need some more codings for it. 

Figure~\ref{fig:random_effect} compares the PMF vs.\ the best informed baseline (weighted average) in the presence or absence of spammers. For the experiment, we use the fixed number of workers (1,500) and tasks(5). In regard to {\ma} (left plot), PMF vs.\ baseline results are basically equivalent with or without spammers, with PMF dominating weighted average as both trend slightly up with greater task similarity. As for RMSE (right plot), we also see PMF dominate the baseline across task similarity settings, with or without spammers. However, for RMSE we see that with or without spammers, baseline performance is flat (no error reduction from increasing task similarity), whereas PMF prediction error decreases with greater task similarity. Trend lines for each method are remarkably parallel with or without spammers, with an offset of about 0.05 RMSE absolute. % for each method.

We understand these findings as follows. To predict the top-$k$ workers for a given task, we focus on only the most accurate workers, which are easy to distinguish from spammers on the basis of higher accuracies on observed tasks (training data). Top-$k$ prediction therefore seems intuitively robust to spammers.  RMSE, on the other hand, is trying to predict accuracies of all workers, thus is inherently sensitive to spammers.  Nevertheless, we see PMF is still able to achieve increasing RMSE reductions with greater task similarity, whereas average accuracy is not, as well as PMF dominating average accuracy for {\ma} prediction as well. 

\subsection{MTurk Data Experiments.}
\label{sec:real_exp}

Whereas our experiments with synthetic data allowed us to carefully control a variety of experimental variables for detailed analysis, we also want to evaluate methods with real crowd data reflecting a specific case of actual operating conditions in which methods could be applied. With three tasks, we fix dimensionality $D=3$.  

We first consider the incomplete matrix of 443 workers who worked on all three tasks (Table~\ref{table:summary_real_data}). Due to sparsity, we do not always have training data on two other tasks to predict the third, so we cannot compute average and weighted average baselines. We see PMF, SVD, and random assignment achieve 0.170, 0.170, and .317 RMSE, respectively.  For MA$_{10}$, they achieve 0.773, 0.609, and 0.381, respectively. We see random assignment perform much worse, and PMF outperforming SVD for MA$_{10}$, but not for RMSE.

\begin{table}
\resizebox{\columnwidth}{!}{%
\centering
\begin{tabular}[bp]{|c |c| c| c || c| c| c| c| }
\hline
	    &\multicolumn{3}{c||}{RMSE}  & \multicolumn{4}{c|}{MA$_{10}$} \\
\hline
{\bf Tasks} &{\bf PMF} &{\bf WAvg} &{\bf Avg} & {\bf PMF} & {\bf WAvg} & {\bf Avg} & {\bf Rand} \\ 
\hline
{\bf task1} & 0.227 & 0.278 & 0.289 & 0.901 & 0.834 & 0.825 & 0.684\\ 
{\bf task2} &0.209  & 0.266 & 0.273 & 0.932 & 0.834 & 0.821 & 0.688\\ 
{\bf task3} &0.197 & 0.257 & 0.267 & 0.946 & 0.712 & 0.712 & 0.687\\ 
\hline
{\bf All} &0.211 &0.267 &0.276 & 0.926 & 0.793 & 0.786 & 0.686\\ 
\hline
\end{tabular}
} % resize box
\caption{Performance on MTurk data. The RMSE and mean accuracy {\ma} of the top $k=10$ workers are shown for PMF vs.\ the three baselines: weighted average, average, and random assignment.}
\label{table:summary_real_turkdata}
\vspace{-10pt}
\end{table}

\begin{figure} [t]
\centering
\ifpdf
\includegraphics[width=65mm]{rTurk_final_MA_2.pdf}
\fi
\caption{Mean accuracy {\ma} of the top $k=10$ workers (averaged across tasks) as predicted by PMF, weighted average, and average, vs.\ random assignment.}
\label{fig:real_turk_ma}
\vspace{-20pt}
\end{figure}

%From the synthetic experiments, we confirmed that PMF outperforms the other models due to its probabilistic approach such as Gaussian priors. In this experiment, we run a PMF-based prediction model and measure the RMSE of prediction accuracy for the validation of the effectiveness of MF-based task routing. A raw matrix created from raw data is not a full matrix, and thus we only use a full matrix (3 tasks 54 workers) extracted from the original matrix. 

Next we consider a smaller, denser matrix of the 54 workers who completed all examples for all tasks, allowing us to compute average and weighted average baselines. Figure~\ref{fig:real_turk_ma} shows {\ma} achieved (averaged across tasks) by different methods (informed PMF, weighted average, and average, vs.\ uninformed random assignment) for increasing $k \in \{1,3,5,10,15,20\}$. Average task similarity across each pair of tasks is estimated as $s=0.65$. Table~\ref{table:summary_real_turkdata} shows per task RMSE and {\ma} achieved by the same set of methods for fixed $k=10$.  

Overall, PMF is seen to dominate other methods except with $k=1$, where both informed baselines perform comparably. Interestingly, we do not see the weighted average offering benefit over the simple average here. We also observe that PMF and informed baselines all outperform uninformed random assignment by a wide margin, across settings. This supports our hypothesis of informed task assignment (by any means) being valuable over random assignment, and it is consistent with earlier findings on synthetic data. 

Task-averaged PMF RMSE in Table~\ref{table:summary_real_turkdata} of 0.21 appears consistent with synthetic experiments with 5 tasks, 500 workers, and $s=0.65$ (Figure~\ref{fig:task_similarity} (a)), where PMF achieved RMSE 0.23. Similarly, the trend of PMF {\ma} degradation with increasing $k$ in Figure~\ref{fig:real_turk_ma} (from roughly 0.98 to 0.86) appears consistent with Figure~\ref{fig:ma_exp} ($s=0.7$ plot) where {\ma} is seen to decrease comparably (from roughly 0.92 to 0.80).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vspace{-5pt}
\section{Conclusion}

%In this study, we demonstrate that MF-based prediction of workers' accuracy makes it possible to selectively route human computation tasks to strong candidates. Throughout the experiments with synthetic and real-world data sets, we confirm that the accuracy of MF-based task routing tends to increase if task similarity get stronger, the size of worker-task matrix get bigger, and the matrix get denser.

%Some issues in MF-based task routing still require further research. First, latent similarity of tasks is critical to the success of the proposed method. In addition, if workers' accuracy across tasks somehow did show any correlation unlike what we see in Figure~\ref{fig:cor_pred_real}, this model may fail to identify strong candidates. Therefore, we recommend to check the correlation of worker's accuracy across tasks prior to running an MF-based prediction. Second, our synthetic experiment assumed that the probability of workers' accuracy follows a Normal distribution and verified it in our MTurk data set. %citation
% However, the distribution may follow other types of probabilistic distribution; thus, it is important to check the normality of the distribution. Accordingly, it is desirable to adopt an appropriate probabilistic distribution in MF-based prediction model. Thirdly, 

%we assumed workers' accuracy as an element in the matrix; however, it may be difficult to measure workers' accuracy over across tasks since obtaining ground truth is challenging. In practice, we recommend to use pseudo-ground truth generated by label aggregation methods in the absence of ground truth. Finally, MF-based task routing does not work well for a new worker since a system has not yet gathered sufficient information about the worker. It is called {\em cold-start} problem in collaborative filtering. We believe that this problem may be resolved by adopting a hybrid approach between MF-based task routing and task-similarity based workers' mean accuracy.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section{Conclusion}
Task routing represents a relatively little explored and increasingly important area for future quality improvements in crowdsourcing. Many interesting questions remain open, such as modeling time-varying worker accuracies, due to fatigue or training effects, in determining appropriate task routing. Better ways to tackle sparse worker history data and longer term longitudinal worker studies could also be incredibly informative.
%in terms of quality assurance in crowdsourcing. For this problem, we presented the matrix factorization (MF)-based task routing model based on the worker-task relational model. Further, we demonstrated the effectiveness of the model through both the synthetic and real-world experiments. 
%some findings in this study merit more attention and scrutiny. 

%require further investigations with regard to MF-based task routing: a study on the correlation of workers' performance across a large number of tasks will be a topic for our future work. In addition, task routing according to the variation of workers' performance over time will be another interesting topic to expand this research to a tensor-factorization model. 

%~\\
{\small {\bf Acknowledgments.} We thank the anonymous reviewers for their time and feedback. This work is supported in part by DARPA YFA Award N66001-12-1-4256, IMLS Early Career grant RE-04-13-0042-13, and NSF CAREER grant 1253413. Any opinions, findings, and conclusions or recommendations expressed by the authors do not express the views of any of the supporting funding agencies.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section*{Acknowledgments}
%We thank the reviewers for their time reviewing this work. 

\vspace{-5pt}
\bibliographystyle{siam}
{\small
\bibliography{jung_sdm14}
}
\end{document}

jung_sdm14.bbl
\begin{thebibliography}{10}

\bibitem{Bernstein2012}
{\sc M.~S. Bernstein, D.~R. Karger, R.~C. Miller, and J.~Brandt}, {\em
  {Analytic methods for optimizing realtime crowdsourcing}}, in Collective
  Intelligence, 2012.

\bibitem{Chilton2010}
{\sc L.~B. Chilton, J.~J. Horton, R.~C. Miller, and S.~Azenkot}, {\em Task
  search in a human computation market}, in {ACM SIGKDD Workshop on Human
  Computation}, HCOMP '10, 2010, pp.~1--9.

\bibitem{Cohen1988}
{\sc J.~Cohen}, {\em {Statistical power analysis for the behavioral sciences}},
  Lawrence Erlbaum Assoc., 2nd~ed., 1988.

\bibitem{cosley2007suggestbot}
{\sc D.~Cosley, D.~Frankowski, L.~Terveen, and J.~Riedl}, {\em Suggestbot:
  using intelligent task routing to help people find work in wikipedia}, in
  12th ACM conference on Intelligent user interfaces, 2007, pp.~32--41.

\bibitem{Ho2013}
{\sc C.~Ho, S.~Jabbari, and J.~W. Vaughan}, {\em Adaptive task assignment for
  crowdsourced classification}, in Proceedings of the 30th International
  Conference on Machine Learning (ICML), 2013, pp.~534--542.

\bibitem{Jung2012-hcomp}
{\sc H.~J. Jung and M.~Lease}, {\em {Improving Quality of Crowdsourced Labels
  via Probabilistic Matrix Factorization}}, in {Proceedings of the 4th Human
  Computation Workshop (HCOMP) at AAAI}, 2012, pp.~101--106.

\bibitem{KamarEce;HackerSeverin;Horovitz2012}
{\sc E.~Kamar, S.~Hacker, and E.~Horovitz}, {\em {Combining human and machine
  intelligence in large-scale crowdsourcing}}, in {Proceedings of the 11th
  International Conference on Autonomous Agents and Multiagent Systems
  (AAMAS)}, 2012, pp.~467--474.

\bibitem{Karger2011a}
{\sc D.~R. Karger, S.~Oh, and D.~Shah}, {\em Iterative learning for reliable
  crowdsourcing systems}, in Proceedings of the 24th Advances in Neural
  Information Processing Systems (NIPS), 2011, pp.~1953--1961.

\bibitem{Kolobov13}
{\sc A.~Kolobov, Mausam, and D.~S. Weld}, {\em {Joint Crowdsourcing of Multiple
  Tasks}}, in {1st AAAI Conference on Human Computation (HCOMP)}, 2013.

\bibitem{Koren2009}
{\sc Y.~Koren, R.~Bell, and C.~Volinsky}, {\em Matrix factorization techniques
  for recommender systems}, IEEE Computer, 42 (2009), pp.~30--37.

\bibitem{Law2011a}
{\sc E.~Law, P.~Bennett, and E.~Horvitz}, {\em {The effects of choice in
  routing relevance judgments}}, in {Proceedings of the 34th ACM SIGIR
  conference on Research and development in Information}, 2011, pp.~7--8.

\bibitem{Lee2012_CF}
{\sc J.~Lee, M.~Sun, and G.~Lebanon}, {\em A comparative study of collaborative
  filtering algorithms}, CoRR, abs/1205.3193 (2012).

\bibitem{paritosh2012human}
{\sc P.~Paritosh}, {\em Human computation must be reproducible}, in
  CrowdSearch: WWW Workshop on Crowdsourcing Web Search, 2012, pp.~20--25.

\bibitem{ramesh2012identifying}
{\sc A.~Ramesh, A.~Parameswaran, H.~Garcia-Molina, and N.~Polyzotis}, {\em
  Identifying reliable workers swiftly}, tech. report, Stanford InfoLab, 2012.

\bibitem{Ruslan2008}
{\sc R.~Salakhutdinov and A.~Mnih}, {\em Probabilistic matrix factorization},
  in {Adv.\ in Neural Information Processing Systems (NIPS)}, 2008.

\bibitem{shahaf2010generalized}
{\sc D.~Shahaf and E.~Horvitz}, {\em Generalized task markets for human and
  machine computation}, in Proceedings of the Twenty-Fourth AAAI Conference on
  Artificial Intelligence, 2010, pp.~986--993.

\bibitem{Shapiro1965}
{\sc S.~Shapiro and M.~Wilk}, {\em {An analysis of variance test for normality
  (complete samples)}}, Biometrika, 3 (1965).

\bibitem{Snow2008}
{\sc R.~Snow, B.~O'Connor, D.~Jurafsky, and A.~Ng}, {\em {Cheap and fast -- but
  is it good?: evaluating non-expert annotations for natural language tasks}},
  in {Proceedings of the Conference on Empirical Methods in Natural Language
  Processing (EMNLP)}, 2008, pp.~254--263.

\bibitem{Vijayanarasimhan2011}
{\sc S.~Vijayanarasimhan and K.~Grauman}, {\em {Large-scale live active
  learning: Training object detectors with crawled data and crowds}}, in
  {Proc.\ IEEE Computer Vision and Pattern Recognition}, 2011.

\bibitem{yi2012crowdclustering}
{\sc J.~Yi, R.~Jin, A.~K. Jain, and S.~Jain}, {\em Crowdclustering with sparse
  pairwise labels: A matrix completion approach}, in Proceedings of the 4th
  Workshop on Human Computation at AAAI, 2012, pp.~47--53.

\bibitem{Yi13}
{\sc J.~Yi, R.~Jin, S.~Jain, and A.~K. Jain}, {\em {Inferring Users�
  Preferences from Crowdsourced Pairwise Comparisons: A Matrix Completion
  Approach}}, in {1st AAAI Conference on Human Computation (HCOMP)}, 2013.

\bibitem{Yuen2012}
{\sc M.~Yuen, I.~King, and K.-S. Leung}, {\em Task recommendation in
  crowdsourcing systems}, in Proceedings of the First International Workshop on
  Crowdsourcing and Data Mining, CrowdKDD '12, 2012, pp.~22--26.

\bibitem{zhang2012task}
{\sc H.~Zhang, E.~Horvitz, Y.~Chen, and D.~C. Parkes}, {\em Task routing for
  prediction tasks}, in Proc.\ of the 11th International Conference on
  Autonomous Agents and Multiagent Systems (AAMAS), 2012, pp.~889--896.

\end{thebibliography}
