基於多臂式吃角子老虎機之群眾分包系統動態任務分配

Abstract

群眾外包是個可以讓需求者外包工作給多個工作者的途徑。由於工作的多樣性以及工作者的能力會隨著工作的種類而有所不同，在眾包的系統中，有個主要的議題就是工作與工作者的配對問題，目的是透過適合的配對來盡可能得收集可靠的答案。 在這個論文中，我們先聚焦在同質且依序到來的任務分配問題。為了解決這個問題，我們提出了一個改良的演算法，CrowdMAB，我們利用了多臂吃角子老虎機演算法當做工作者選取的策略，同時使用最大期望演算法來估計工作者的信賴度以及彙總答案。此外，CrowdMAB 可以動態地收集答案，且需求者可以透過調整信賴度閾值及截斷參數來控制所消耗的預算。與當前最新演算法 CrowdSense相比之下，實驗顯示我們的演算法可以顯著地提昇工作的正確率，同時也可以降低總花費。接下來，我們考慮與現實貼近的設定：異質性群眾外包，也就是工作及工作者皆為異質性且批次到來。不同於同質性任務分配，難題在於如何在同個時間點有效地配對大量的工作及工作者以最大化所有工作的正確率。為了描述這樣的問題，我們制定了一個最佳化的問題，同時提出了兩步驟分配的策略來找到適當的分配值。在我們的設定下，模擬實驗顯示我們演算法的表現與最佳分配非常接近。

Crowdsourcing is a valuable approach where requesters can outsource a task to several workers. Due to the diversity of tasks and task-dependent reliability of workers, one of the major issues in such systems is the task-worker matching problem, which is aimed at collecting as many reliable answers as possible by matching the task with suitable workers. In this thesis, we first focus on the homogeneous sequential task assignment problem in crowdsourcing setting. To solve this problem, we proposed an improved algorithm, CrowdMAB, which uses multi-armed bandit algorithms as the worker selection strategy, and EM algorithm for reliability estimation of workers and answers aggregation. Moreover, CrowdMAB can dynamically collect answers for the task, and requester can control the labeling cost (time and money) by confidence threshold and truncation parameter. Our experiments on CrowdMAB and several baselines, include the state-of-the-art algorithm, CrowdSense, demonstrate that our algorithm has significantly improvement on task accuracy, also reduces the total label cost. Secondly, we consider a close-to-reality setting, heterogeneous crowdsourcing, where workers and tasks are heterogeneous and batch-coming. Different from the above assignment problem, the challenge is how to efficiently matching a lot of tasks and workers at the same time so that we can maximize the accuracy of total tasks. To characterize this problem, we formulate an optimization problem, and we propose a two-step assignment policy to efficiently find the solution. Under our settings, simulation experiments show that the performance of our algorithm is close to optimum.