1、學院(部)計算機科學與技術學院題 目面向眾包系統的拍賣算法對比研究II目 錄摘 要1Abstract2前 言3第1章緒 論41.1研究背景及意義41.2眾包中的任務拍賣算法概述51.3本文的主要工作和創新點61.4本文的組織結構7第2章眾包中拍賣算法的模型和評價標準82.1眾包中拍賣算法的基本概念和理論模型82.1.1請求者與工人82.1.2眾包中的任務拍賣算法的一般模型92.2眾包中的任務拍賣算法的分類92.2.1基于報價機制的任務拍賣算法92.2.2基于定價機制的任務拍賣算法102.3眾包中的任務拍賣算法的評估基準102.3.1最優離線算法102.3.2眾包中的任務拍賣算法的遺憾11第3章

2、眾包中的拍賣算法對比分析123.1基于報價機制的拍賣算法123.1.1BP-MaxTasks 算法133.1.2BP-DGreedy算法143.2基于定價機制的任務拍賣算法173.2.1BP-UCB算法183.2.2OPPM算法193.3實驗對比分析213.3.1實驗背景213.3.2算法的收益對比分析223.3.3算法的遺憾對比分析253.3.4價格選擇情況對比分析273.4總結28第4章考慮任務質量的任務拍賣算法294.1考慮任務質量的任務拍賣算法的基本模型294.2任務質量對選擇最優價格的影響294.3OPPMQuality算法304.3.1考慮任務質量的價格選擇算法304.3.2OPP

3、MQuality算法實現324.4 實驗對比分析344.4.1實驗背景344.4.2實驗結果344.5 總結36第5章眾包中拍賣算法的實現385.1OPT-FIX算法的實現385.1.1計算報價接受概率385.1.2計算最優效益395.2改進BP-UCB算法和OPPM算法的運行效率395.2.1BP-UCB算法和OPPM算法的效益函數395.2.2三分查找算法40第6章總結與展望426.1本文總結426.2后續工作展望42參考文獻43致謝4547摘 要眾包是一種新興的解決問題的方式，通常用于解決一些對于人類來說十分簡單但是對于機器來說求解起來較為困難甚至不可能的問題。近年來，隨著機器學習以及大

4、數據產業的興起，很多科技公司和學者都采用眾包進行機器學習訓練數據的收集以及整理，進而導致與眾包相關的理論研究得到迅速發展。在眾包系統中，任務分配機制有著舉足輕重的地位，任務分配機制的優劣極大的影響眾包系統的性能，因此在學術界提出了各種任務分配機制。拍賣算法作為任務分配機制中的核心算法，廣泛地使用在眾包系統中的任務分配機制中，這篇論文主要研究了眾包系統中的任務拍賣算法，首先從理論上對比了多種基于報價機制的任務拍賣算法和基于定價機制的任務拍賣算法，然后實現并設計實驗根據算法的遺憾評估不同算法性能。結果表明，雖然基于定價機制的算法需要更少的用戶信息，但是其效益仍然能夠達到和報價機制的任務拍賣算法相同

5、的效果。此外，本文還提出了一種含有質量控制策略的任務拍賣算法，并且通過實驗驗證其獲得了不錯的性能。關鍵詞：眾包；任務分配；拍賣算法；定價機制；報價機制；AbstractCrowdsourcing is a newly developing way to tackle the barriers that are usually very simple for an individual to perform but intricate or impossible to solve for machines. In recent years, with the rise of machine le

6、arning and the big data industry, many technology companies and scholars have used crowdsourcing to collect and clean training data, which has led to the rapid development of theoretical research related to crowdsourcing.Task allocation mechanism play a crucial role in crowdsourcing systems, which i

7、s of great impact on the performance of crowdsourcing system. There are various task allocation mechanisms have been put forward in academia, such as posted-price-based mechanisms and biding-based mechanisms. Auction algorithms are widely used in the task allocation mechanism of crowdsourcing system

8、, which are the core algorithms in task allocation mechanism. This dissertation mainly discusses the auction algorithms in the crowdsourcing system, and compares the performance of various auction algorithms in terms of the regret of algorithm theoretically and empirically. The experimental results

9、show that although the posted-price mechanism requires less user information, but it still achieve the same performance of biding mechanism. In additional, a task auction algorithm with quality control strategy is proposed in this dissertation, and the experimental results show that the algorithm ha

10、s a good performance.Keywords: Crowdsourcing; Task Allocation; Auction Mechanisms; Posted-Price; Biding;前 言雖然計算機技術在高速的發展，但是目前仍然有很多對于計算機來說難以解決甚至不能解決但是對于個人來說很容易解決的問題，因此眾包這一種利用人類的集體智慧解決問題的方案應運而生，并且很快成為一個解決一些簡單問題高效而又便利的方法。在眾包系統中，一個請求者（Requester）通常需要在給定的預算范圍內完成成百上千的任務，請求者把這些任務和他們的價格提交到眾包平臺中，工人（Worker）提交他

11、們的答案并且獲取指定的報酬。在眾包系統中，一個核心的挑戰就是如何決定每一個任務的價格。過高的定價導致預算很快耗盡，而過低的定價導致沒有足夠多的工人愿意參與到工作中，也會導致請求這的效益過低。因此設計一個高效的任務分配機制對于眾包系統來說至關重要。在學術研究中，拍賣算法被廣泛的應用在任務分配機制的設計中，因此任務拍賣算法有著重要的研究意義。本文主要以眾包系統為研究對象，研究眾包系統中的任務拍賣算法，對比分析了多種任務拍賣算法，并且設計和實現了相應的任務拍賣算法，然后設計實驗分析對比算法的性能差異，并且對現有的算法進行了一些改進，然后提出了一種考慮任務質量的任務拍賣算法。本文的主要工作在于：(1)

12、. 研究BP-MaxTasks算法、BP-DGreedy算法、BP-UCB算法和OPPM算法的原理，并從理論上對比各個算法的關系和差異。(2). 實現上述的眾包系統中的拍賣算法，并且設計實驗根據實驗結果分析算法的效益和遺憾，對比不同算法的性能差異。(3). 改進BP-UCB算法和OPPM算法，通過研究BP-UCB算法和OPPM算法的效益函數的特征，設計三分搜索算法快速檢索最優價格，從而提高BP-UCB算法和OPPM算法的運行效率，這是本文對于算法實現方式上的創新。(4). 從理論上提出帶有質量控制策略的OPPMQuality算法，并且實現該算法，設計實驗驗證其具有良好的性能，這是本文在理論上的

13、創新。第1章緒 論本章首先介紹眾包系統中的研究背景和理論意義，然后簡單介紹眾包中的任務拍賣算法，其次簡要介紹本文所做的主要工作和貢獻，最后介紹本篇論文的結構。1.1研究背景及意義互聯網的迅速發展也給眾包的發展帶來了大量的機遇，互聯網上如亞馬遜Mturk和Click Worker一般的微任務眾包平臺比比皆是。這些眾包系統作為聯系請求者和工人的橋梁而存在，在這些眾包平臺中，請求者發布各式各樣的被稱為HITs(Human Intelligence Tasks，人類智能任務)的任務給在線的工人，這些任務被在線的眾包平臺中的工人執行，然后把結果返回給眾包平臺并獲取他們應得的報酬。一般來說，提交到微任務眾

14、包平臺中的任務通常都是一些圖片識別1，問卷調查填寫2,自然語言文本理解3等微型的任務，完成這些任務通常不需要花費工人太多的時間，但是請求者需要完成很多類似的任務，請求者通過完成的任務能夠獲取一定的效益。此外，請求者一般還有一定的預算限制了其能夠在該任務上付出的報酬，因此請求者需要在預算受限的情況下最大化完成任務所獲得的效益。在這些眾包平臺中，請求者可以選擇哪些工人可以做他們的任務，并且決定每一個任務他們能夠給出的價格，而工人則根據自己完成任務的花費以及請求者提供的價格決定是否接受相應的任務。因此一個合適的任務分配機制在眾包系統的設計中不可或缺。確定合適的任務定價是任務分配機制的核心問題。對于請

15、求者來說，過低的定價導致愿意接受任務的工人寥寥無幾，從而獲取的效益過少，過高的定價會導致請求者的預算很快花完，導致預算的低效利用，因此任務分配機制必須要決定合適的價格，在高效的利用預算的同時也能夠吸足夠多的工人參與到任務之中，從而提高請求者的效益。雖然任務的定價算法在眾包系統中有著舉足輕重的地位，但是設計一個合適的定價方案仍然是一個十分具有挑戰性的問題。在眾包系統中的任務分配機制中，一般假設如果給予工人的報酬不低與用戶的花費，則該用戶會接受任務，并且用戶一旦接受任務就會完成任務，因此任務定價算法的核心就是確定用戶的花費曲線。在學術界中通常采用任務拍賣算法的形式設計任務分配機制，Singer Y

16、等人通過報價機制，確定價格的閾值，以把預算分段的方式最大化完成的任務數目4。Singla A等人通過遺憾最小化機制，依據報價機制通過離散化價格的方式近似工人的花費曲線，提出了BP-DGreedy算法，相比于Singer Y等人的方法是請求者的效益提高了進40%，并且使用置信區間上限代替價格的接受概率，把其推廣到定價機制，在減少了交流的負擔的同時能夠獲取接近的性能5。更近一步的，Hu Z等人通過任務拍賣算法和多臂賭博機之間的聯系，提出了基于定價機制的OPPM算法6，不再需要先驗的價格范圍，并且證明其遺憾匹配Lai-Robbins遺憾下限7。眾包在各個領域都有著廣泛的使用。在圖像識別領域Ahn L

17、V等人提出了reCAPTCHA項目，通過在驗證碼中嵌入書籍中的字符信息從而使用眾包技術識別圖像中的文字，完成紙質書籍的電子化1。Nowak S等人通過眾包中的投票機制過濾噪聲數據，提高圖像注解系統的準確率8。在自然語言處理領域中，Callison-Burch C等人采用眾包的形式對機器翻譯的結果進行質量評估，解決了手工評估緩慢且代價高昂的問題9。在網絡搜索領域，Alonso等人通過眾包分析搜索結果是否能夠提供用戶所需要的信息, 從而將眾包應用到Web搜索結果質量評估方面10。 此外眾包系統在人工智能領域也有著廣泛的應用。因此眾包系統有著深遠的研究意義，眾包系統中的任務分配算法的研究能夠對科學的

18、進步帶來極大的效益。1.2眾包中的任務拍賣算法概述在眾包系統的設計中，任務分配機制有著重要的地位，一般的任務分配算法都采取任務拍賣的方法把任務分給相應的工人，任務拍賣算法的主要任務是根據請求者的預算和工人們的歷史信息確定合適的任務定價。眾包系統中的定價機制通常假設如果請求者提供的價格比工人的花費高，則工人接受任務。由于沒有工人花費的先驗知識，一般的任務拍賣算法通過計數價格的接受頻率在線學習工人的花費分布。為了在不知道工人花費的情況下最大化請求者的收入，學術界中提出了不同的任務拍賣算法。Badanidiyuru A等人離散化工人的花費為一系列的幾何級數，然后使用啟發式算法從這些幾何級數中選擇價格

19、11。Singla A等人根據該方式提出了一個改進的策略，在預算限制下，這個改進的策略選擇能夠最大化預期收入的置信上限的價格5。Agrawal S和Badanidiyuru A等人采用線性規劃的方式選擇價格，這個線性規劃問題的定義與所有可能的價格的預期收入的置信上限有關Error! Picture switch must be first formatting switch.,Error! Picture switch must be first formatting switch.。作為總結，當一個工人到來時，任務拍賣算法通過學習到的工人的花費曲線估計所有可能價格的預期收入，進而選擇最優的價

20、格，作為定價提交給用戶，然后用戶選擇接受或者拒絕這個價格。1.3本文的主要工作和創新點本文主要以眾包系統為研究對象，研究了眾包系統中的任務拍賣算法，并且實現了相應的任務拍賣算法，提出了一種考慮任務質量的任務拍賣算法，改進了已有算法的性能，然后設計實驗分析對比算法的性能差異。本文的主要工作在于：(1). 研究BP-MaxTasks算法、BP-DGreedy算法、BP-UCB算法和OPPM算法，從原理上理解這些拍賣算法之間的聯系，進一步從理論上對比這些算法，得出算法之間的差異。 (2). 實現上述的眾包系統中的拍賣算法，并且實現最有離線算法OPT-FIX作為算法性能的評價標磚，然后設計實驗計算算法

21、的效益和遺憾，根據不同算法的效益和遺憾對比不同算法的性能差異，設計實驗獲取不同算法選擇不同價格的概率從而分析算法新能差異的原因。(3). 改進BP-UCB算法和OPPM算法，通過研究BP-UCB算法和OPPM算法的效益函數，得到其目標函數是單極值函數的特點，然后設計三分搜索算法快速檢索算法中的最優價格，從而提高BP-UCB算法和OPPM算法的運行效率。這是本文在算法的實現方式上進行的創新。(4). 提出帶有質量控制策略的OPPMQuality算法，并且實現該算法，然后設計實驗獲得算法的效益，并且和最優離線算法進行對比，從而從實驗上驗證其具有良好的性能。這是本文在理論上的創新。1.4本文的組織結

22、構本文共有六章組成，每個章節的內容安排如下：第一章：緒論。本章主要介紹了眾包系統以及眾包系統中的任務拍賣算法的研究背景以及意義，簡介眾包中的任務拍賣算法的基礎，本文的主要工作和貢獻，以及本文的組織結構。第二章：眾包中的拍賣算法的模型和評價標準。本章首先提出眾包中的任務分配機制中的一些基礎概念，然后給出眾包中的任務分配機制的理論模型，再簡單的介紹任務分配機制中的拍賣算法的兩種類別，最后給出眾包中任務拍賣算法的評價標準。第三章：眾包中的拍賣算法對比分析。本章主要介紹眾包中的任務拍賣算法，并設計實驗對比不同算法的性能。首先按照類別介紹不同的任務拍賣算法，然后從理論上對這些算法進行對比分析，最后設計實

23、驗從實驗上對比這些算法的性能，從不同算法選擇價格的分布來分析產生不同結果的原因。第四章：考慮任務質量的任務拍賣算法。本章提出了一種考慮任務質量的任務拍賣算法，首先從理論上介紹算法的原理，然后給出算法的偽代碼實現，最后設計實驗對比其和離線最優算法的性能差異以及分析OPPMQuality算法的不足。第五章：眾包中的拍賣算法的實現。本章主要介紹了算法實現過程中的難點，然后介紹了對BP-UCB算法和OPPM算法的改進。第六章：總結全文，提出未來工作的設想以及展望。第2章眾包中拍賣算法的模型和評價標準本章首先提出眾包中的任務分配機制中的一些基礎概念，然后給出眾包中的任務分配機制的理論模型，再簡單的介紹任

24、務分配機制中的拍賣算法的兩種類別，最后給出眾包中任務拍賣算法的評價標準。2.1眾包中拍賣算法的基本概念和理論模型眾包中的任務拍賣算法主要牽涉到請求者和工人，在這一小節主要介紹不同客戶之間的聯系，然后在介紹任務拍賣算法的一般理論模型。2.1.1請求者與工人請求者主要是指任務的提交者，請求者把他們需要解決的任務提交到眾包平臺，并且可以指定他們所具有的預算限制。對于一個任務來說，請求者可以選擇提供他愿意為任務所付出的最大價格，也可以要求工人提交必要的信息（如花費，能夠完成的任務數目等），更近一步來說，請求者可以根據歷史的工人信息決定把哪些任務以什么價格分配給哪些工人。一般來說，請求者通過任務的完成獲

25、取效益，在本文中把請求者的效益定為其能夠完成的任務的數目。工人主要是指完成任務的客戶。對于一個任務來說，每一個工人完成這些任務都有其自己的花費，不同的工人的花費是不同的，但是在任務分配機制中，一般假設所有工人的花費是獨立同分布。工人通過自己的花費決定是否接受一個具有指定價格的任務。在眾包系統中的任務拍賣算法中，一般假設如果給予工人的報酬高于其完成任務的花費，則其接受任務，并且認為其一旦接受任務就完成任務。2.1.2眾包中的任務拍賣算法的一般模型在眾包系統中，請求者提交任務，這些任務可以被隨后到來的工人執行，請求者的預算限制為，請求者的目的是在預算限制的情況下最大化其效益，在本文中假設每件任務具

26、有單位價值，也就是在預算限制下最大化完成任務的數目。在眾包平臺中，共有數目為的工人，使用代表，工人隨著時間的消耗逐漸到達。每一個工人有一個相關的私人花費，但所有工人的花費是獨立同分布的。此外工人有可能被要求提供他們的報價，一般來說，任務拍賣算法需要保證算法的誠實性(truthful)，也就是保證工人的報價時是其最優策略。在眾包系統中，一般假設工人的隨機到達，也就是工人到達的先后順序是隨機的，但是本文只關注每一個時間最多只有一個工人到達的情形。任務拍賣算法的主要任務就是當工人在時刻的到達，根據時刻之前的工人信息確定一個價格提供給工人,如果工人接受并完成任務，則請求者付出相應的報酬給工人并獲取相應

27、的效益。2.2眾包中的任務拍賣算法的分類眾包系統中通常有兩類任務拍賣算法，基于報價機制的任務拍賣算法和基于定價機制的任務拍賣算法，本小節簡要介紹這兩類任務拍賣算法。2.2.1基于報價機制的任務拍賣算法基于報價機制的任務拍賣算法在提供給工人價格之前，會讓工人報告他們的報價，基于報價機制的任務拍賣算法一般需要保證拍賣算法的誠實性，也就是工人提供他們的真實花費作為他們報價為他們的最優策略。為了保證拍賣算法的誠實性，基于報價機制的任務拍賣算法一般只會根據以及之前到來的工人信息決定時刻到來的工人的任務定價。2.2.2基于定價機制的任務拍賣算法由于基于報價機制的任務拍賣算法需要工人和請求者交流報價信息，但

28、是由于工人很難準確的確定其完成任務所需的花費和在微任務眾包系統中信息交流較為不便等原因，人們提出了基于定價機制的任務拍賣算法。在基于定價機制的任務拍賣算法中，請求者向工人提供任務的價格，工人只需要做出接受或者拒絕的決定，不再需要工人的其他信息，在實際應用中被廣泛的采用。2.3眾包中的任務拍賣算法的評估基準為了評估任務分配算法的性能，還需要算法的評估基準。這一節我們介紹算法的評估基準。2.3.1最優離線算法最有離線算法是指在知道工人所有信息的情況下的算法，通常用來做算法性能的基準，這一小節我們介紹兩種最優離線算法，然后介紹為什么選取OPT-FIX作為算法性能的基準。(1). 最優價格組合OPT-

29、VAR考慮一個知道所有工人信息的離線算法，請求者的最大效益可以通過按照工人的花費升序排列，然后給予每一個工人他們花費的報酬直到用盡預算得到，我們稱這種評價基準為最優價格組合OPT-VAR。(2). 最優固定價格 OPT-FIX類似地，通過提供能夠是請求者獲取最大效益的單一價格的離線算法所獲得的效益成為OPT-FIX，對應的成為相應的價格為最優固定價格，使用代表。使用代表工人的花費曲線，也就是代表工人接受價格的概率，則最優價格可以通過下面的公式得到： (1)在上面的公式中， 代表采取最優價格能夠得到的收益，最優價格通過公式(1)計算得到，代表拍賣算法可以得到的收益，使用他們的差值代表算法的遺憾，

30、因此最大化請求者的效益就相當于最小化拍賣算法的遺憾。需要注意的是上面說的最優價格都是在離線情況下也就是在知道所有工人的花費信息的情況下得到的，因此上述兩種算法一般用作在線任務拍賣算法的性能評估基準。Goldberg A等人的研究表明，OPT-FIX的性能十分接近OPT-VAR的性能14。更近一步地，最近Singer Y15和Badanidiyuru A16等人的研究表明OPT-FIX是任何誠實的在線算法可以達到的最佳性能，因此本文中采用OPT-FIX作為任務拍賣算法的性能度量標準。2.3.2眾包中的任務拍賣算法的遺憾在本文中，引入遺憾(Regret)評價一個在線任務拍賣算法的性能指標，一個拍賣

31、算法的遺憾定義為算法所能得到的效益和采取最優價格能夠得到的效益的差值，遺憾的定義如下面的公式所示： (2)在上面的公式中， 代表采取最優價格能夠得到的收益，最優價格通過公式(1)計算得到，代表拍賣算法可以得到的收益，使用他們的差值代表算法的遺憾，因此最大化請求者的效益就相當于最小化拍賣算法的遺憾。第3章眾包中的拍賣算法對比分析本章介紹眾包中的任務拍賣算法，首先按照類別介紹不同的任務拍賣算法，然后介紹各種算法的實現方式，其次實現算法并設計實驗分析算法的效益和遺憾，進一步分析不同算法產生不同效益的原因。3.1基于報價機制的拍賣算法在基于報價機制的任務拍賣算法中，當工人在時刻到達時，任務拍賣算法要求

32、工人提供其花費的報價，然后根據歷史的工人信息決定任務的定價,并將其提交給工人，如果工人接受任務，則請求者獲得效益,預算花費為，然后等待下一個工人的到來，如果工人不接受任務，則請求者獲得效益，預算花費為，然后等待下一個工人的到來。由于在基于報價機制的任務拍賣算法中，工人的花費是有他們自己提供的，為了保證工人報價的真實性，基于報價機制的任務拍賣算法需要滿足下面的要求：(1). 誠實性(truthful)在一個拍賣算法中，如果工人的報價是工人的最優策略則該拍賣算法是誠實的，即如果一個拍賣算法滿足，對均有則稱該算法具有誠實性，其中分別代表被分配任務的結果。在本文的任務拍賣算法中，需要具有誠實性的特征。

33、(2). 預算可行性(budget feasible)如果一個任務拍賣算法的總花費不會超過預算，即成立，其中與分別代表工人被分配的任務的結果與價格，則該拍賣算法是預算可行的。在本文的算法中均為預算可行的算法。3.1.1BP-MaxTasks 算法BP-MaxTasks算法是Singer Y等人提出的算法4，算法首先根據工人到達時間的比例分布獲取等分點的時間，如果工人在時間之前到達的概率是，則是工人到達時間的等分點。然后按照等分點的時間把任務拍賣過程分成不同的階段，然后估計某一等分點之前的離線最優價格作為下一個階段任務的報價。同時收集用戶的報價信息，首先我們介紹價格閾值的建立過程。(1) 建立價

34、格閾值GetThreshold過程用于建立價格閾值，其主要思想來源與Singer Y提出的比例共享機制(proportional share mechanism)15,算法根據歷史工人的報價信息獲取能夠最大化完成任務數目的價格，并提供這個價格作為下一階段的報價。在本文中，只研究每位工人只接受一件任務的情形，所以。算法的偽代碼如下：需要注意的是GetThreshold需要工人的報價信息，因此是一個離線算法，在BP-MaxTasks算法的等分點時間節點，根據GetThreshold獲取下一階段的價格信息。(2) 收集用戶報價BP-MaxTasks算法把任務拍賣過程分成不同的階段，然后根據前一階段的

35、工人的報價估計下一階段到來的工人，其偽代碼如下圖所示：在BP-MaxTasks算法中，代表工人到達時間的等分位點，其中，然后根據工人的歷史報價信息獲取下一階段提供的價格，并在接下來的階段中提供價格直到預算耗盡或者工人全部到達，在本文的實驗中，每個工人只能接受一個任務，因此取均為1，此外因為給予工人的報酬只與其之前的工人的報價相關，因此該算法是誠實性的算法。(3) 理論分析BP-MaxTasks算法把時間T分成1,2,4,8階段，使得每一個時間節點之前到達的工人數目等于下一個階段的工人數目，并在每一個節點使用之前所有工人的報價計算出一個離線的最優報價，根據該報價估計下一階段工人的花費，是一種樸素

36、的思想，實驗表明，BD-MaxTasks的算法的性能達到了OPT_FIX算法的60%左右。3.1.2BP-DGreedy算法BP-DGreedy算法是Singla A提出的任務拍賣算法5，BP-DGreedy算法首先根據一個乘法因子把價格離散化，然后根據用戶的報價維護不同價格的接受概率，進一步選擇能夠最大化收益的離散后的價格，這一節主要介紹BP-DGreedy算法。(1) 經典的多臂賭博機問題在經典的多臂賭博機背景中，有個互相獨立的選擇，稱為臂(arms),每一個臂和一個未知的獎勵分布相關聯。一個MAB算法能夠進行輪游戲，在每一輪次中拉一個臂并得到一個隨機的和該臂相關的獎勵，算法的目的是最大化

37、獲得的獎勵。MAB問題是一個探索(explore)和開發(exploit)均衡的一個典型問題，一個MAB算法需要探索不是最優的臂，從而得了解最優的臂的信息，同時，為了最大化獎勵，必須要利用(exploit)目前最優的臂，MAB算法的目的是通過快速收斂到最優的臂以最小化算法的遺憾。(2) 從價格的離散化到多臂賭博機問題在我們所描訴的任務拍賣算法中，一個主要挑戰就是工人的花費曲線是未知的。為了估計工人的花費曲線，我們首先把價格進行離散化，然后通過計數每一個價格的接受概率從而估計工人的花費曲線。因此我們采用與Kumar V等人17類似的乘法因子的方式把價格離散化為K個獨立的臂，其中是算法的一個參數。

38、但是預算限制打破了經典MAB問題的背景，因為除了時間界限(假設每一輪次到達一個工人)的限制外，我們還需要保證預算限制的滿足。每一個臂的接受概率隨價格的變化關系如圖3.1所示。在圖3.1中橫坐標代表離散化的價格，縱坐標代表能夠完成的任務的數目。我們使用代表價格被工人接受的概率，則代表預算所允許最多雇傭的工人。按照經典MAB問題的定義，我們每次都應該選擇最大的價格，但是卻導致完成任務數目的下降，因此我們需要根據預算限制調整算法。圖3.1 預算限制和價格接受概率的關系(3) 選擇具有最高收益的價格除了在第二章引入的一些符號之外，我們需要額外的介紹一些標記以介紹BP-DGreedy算法。令代表K個離散

39、價格之中最優價格的索引代表對應的最優價格，代表對應的價格的接受概率，則根據圖3.1我們可以得到： (3)此外，我們使用代表在時刻t剩余的預算，代表價格在時刻已經被提供的次數，代表是否接受的結果，使用代表在時刻的觀測值，然后我們得出下面的BP-DGreedy算法。(4) BP-DGreedy算法BP-DGreedy是基于報價機制的算法，該算法征求工人的報價，然后提供一個價格給工人，工人可以選擇接受或者拒絕這個定價。為了保證算法的誠實性，一個自然的方式是使提供給當前工人的價格和其報價無關。根據算法的誠實性，我們可以得到,這樣可以保證算法知道之前的所有工人信息。為了選擇臂使得選擇的價格和工人的報價無

40、關，我們基于估計的每一個價格接受的概率預測每一個臂的預期收益，然后提供具有最好預期收益的臂所對應價格。為了估計價格的接受概率，我們基于每一個報價維護每一個臂的平均接受率。對應的BP-DGreedy的偽代碼如下所示：BP-DGreedy算法通過將任務拍賣算法和多臂賭博機問題聯系起來，然后離散化價格并維護每一個價格的接受概率從而精確的估計工人的花費曲線，實驗表明BP-DGreedy的效益基本接近OPT-FIX的最優價格，相對于BD-MaxTasks算法使得用戶的效益提高了進40%，是一個近似最優的算法。3.2基于定價機制的任務拍賣算法在基于定價機制的任務拍賣算法中，當工人在時刻到達時，任務拍賣算法

41、直接根據歷史的工人的接受拒絕信息決定任務的定價,并將其提交給工人，如果工人接受任務，則請求者獲得效益,預算花費為，然后等待下一個工人的到來，如果工人不接受任務，則請求者獲得效益，預算花費為，然后等待下一個工人的到來。在基于定價機制的任務拍賣算法中，由于不再需要工人的報價信息，所以對算法的誠實性沒有要求，但是仍然要求算法是預算可行的。此外，由于在基于定價機制的任務拍賣算法沒有歷史工人的花費信息，所以想要準確的確定工人的花費曲線具有更大的挑戰。3.2.1BP-UCB算法這一小節主要介紹BP-UCB算法，BP-UCB算法是Singla A等人根據BP-DGreedy算法改進得到的算法5，在BP-UC

42、B算法中，算法不在根據工人的報價維護每一個臂的接受概率，而是根據多臂賭博機問題中的UCB算法18，維護每個臂的置信區間上限，并將該值作為每一個臂的接受概率的值。具體的算法如下所示：在BP-UCB算法中，代表價格被提供的次數，代表價格接受概率的置信區間上限。在中，代表價格被接收的概率，代表置信區間的大小，也就是說價格選擇的次數越多，其置信區間越窄也就是越接近真實的接受概率，因此使用代表BP-DGreedy算法中的價格接受概率，就得到了BP-UCB算法。BP-UCB算法運行前期，所有臂的置信區間都較寬寬，算法主要在做探索工作，隨著工人到來的數目增加，臂的置信區間逐漸變窄，接受概率的估計值逐步接近真

43、實值，算法傾向于利用接受概率足夠大而效益又高的臂，做到了開發與利用的均衡。雖然BP-UCB算法沒有工人的真實花費信息，但是其性能和BP-DGreedy算法接近，具體的實驗和對比討論詳見下面的實驗部分。3.2.2OPPM算法這一節我們介紹OPPM算法，該算法是由Hu Z等人提出的基于定價機制的任務拍賣算法6，該算法類似于BP-UCB算法，但是該算法基于眾包系統的獨特特征以及多臂賭博機問題，并且Hu Z通過證明其符合Lai Robbins遺憾下限從而證明了其最優性7。(1) 眾包系統中的拍賣算法的獨特特征（1） 更高的價格能夠吸引更多的工人，也就是接受概率函數單調增加。（2） 更高的價格可以雇傭的

44、工人數目逐漸下降，也就是預算限制的工人數目單調減少。（3） 最優的價格是當接受概率和預算限制可以雇傭的工人相等時的價格，也就是。(2) 等價的多臂賭博機問題設想我們需要重復性的在價格中選擇N次，在每次選擇后我們可以觀察到一個隨機變量服從于伯努利分布，其中的均值是，同時我們可以獲得選擇的獎勵是，其中，獎勵在后臺累計，也就是我們只有在選擇N次之后才能知道獲得了多少獎勵。基于（1）中介紹的3個獨特特征，我們引入接下來的兩類可能的最優價格(POPs):（1） 如果最優價格滿足,則記為POP-1。（2） 如果價格滿足則記為POP-2.下面我們介紹最優價格選擇算法OA-MAB算法：在這里，為了完整性我們約

45、定。代表價格已經被選擇的概率，代表價格的接受概率的估計值,算法開始時初始化,此外我們使用代表價格不僅是POP而且時POP2的次數，代表價格的置信區間上屆的度量，在這里我們采用KL散度計算概率的置信區間上界，的值由下面的式子得到： (3)在(3)中sup代表集合的上確界，代表兩個均值分別為x, y隨機變量的KL散度，通過求出集合的上確界獲取價格的置信區間上界將作為概率的估計值。(3) OPPM算法OPPM算法利用OA-MAB算法選擇最優的價格，然后根據用戶的接受拒絕信息更新每一個價格的接受概率，詳細的算法偽代碼如下所示：在上述的算法中，用于價格的離散化，代表眾包平臺允許的最小價格變化。在OPPM

46、算法中，根據價格的接受概率，調用OA-MAB算法在價格集合S中搜索獲得最優價格，將對應的價格提供給工人，然后根據工人的接受或者拒絕信息更新任務計數、剩余預算以及價格接受概率等信息。3.3實驗對比分析3.3.1實驗背景這一節的實驗部分，我們對比了BD-MaxTasks算法，BP-DGreedy算法，BP-UCB算法以及OPPM算法的性能。作為對照，我們還是用離線最優算法OPT-FIX作為性能的基準。工人的花費數據根據不同的價格分布隨機生成。在實驗中，工人們順序到來，任務拍賣算法根據歷史工人的信息為每一個工人提供一個價格，工人根據自己的花費選擇接受或者拒絕改價格，然后拍賣算法根據工人的決定更新提供

47、給下一個工人的算法，為了結果的準確性，我們分別采用了不同的分布模擬工人的花費分布，具體的信息如表5.1所示。表 3.1：實驗中采用的工人的花費分布實驗編號價格分布150250350在實驗中，所有的數值均以元為單位，在算法的效益和遺憾的對比中，我們保持的恒定，使得有足夠的工人能夠參與任務。為了測量結果的準確性，每種算法均取10次運行結果的平均值。在算法BP-DGreedy算法和BP-UCB算法中，值和Singla A等人的實驗5保持相同為0.2，在OPPM算法中，價格變化最小值取值為0.01。3.3.2算法的收益對比分析這一節主要介紹不同算法的收益的對比，任務拍賣算法的目的是最大化請求者的收益，

48、因此算法的收益是衡量一個算法的性能的重要因素。在本小節的實驗中，不斷增加請求者的預算，根據不同算法的收益繪制出效益隨著預算的變化圖，從而對比不同算法產生的效益，結果如下圖所示：圖 3.2 實驗1的效益圖3.3 實驗2的效益圖3.4 實驗3的效益從不同算法的效益之間的關系中我們可以看出，在所有的實驗中除BP-MaxTasks算法外的所有算法產生的效益基本上呈現出隨預算的增加而線性上升的趨勢，而BP-MaxTasks算法的效益雖然整體上也呈現出上升的趨勢，但是偶爾會出現效益的下降，說明BP-MaxTasks算法不是特別穩定，波動性較大。進一步對各種算法產生的效益進行對比我們可以看出OPPM算法和B

49、P-DGreeedy算法的性能相當，均接近最優離線算法OPT-FIX所產生的效益。BP-UCB算法相對于OPPM來說效果稍差，但是相對于BP-MaxTasks算法，性能也提高40%左右，從圖示的算法對比結果來看，雖然基于定價機制的拍賣算法并沒有工人的花費信息，但是其產生的效益仍然能夠接近甚至達到最優離線算法的效果，使得請求者達到了最優收益，說明設計完善的基于定價機制的任務拍賣算法也能夠充分的預測得到工人的花費曲線，因此基于定價機制的任務拍賣算法由于交流負擔小，解決了用戶需要自己估計花費信息等問題，具有明顯的優勢。3.3.3算法的遺憾對比分析遺憾是一個算法產生的效益和最優算法之間的差值，是評估一

50、個算法性能的重要因素，一個算法的無遺憾性是指隨著預算的增加，算法的遺憾和預算的比值逐漸趨于0的性質，是一個優秀的拍賣算法應具有的性質，這一節我們實驗不同算法的遺憾隨著預算的變化關系，結果如下圖所示：圖 3.5 實驗1的效益圖3.6 實驗2的效益圖3.7 實驗3的遺憾從遺憾與預算的變化關系中我們可以看出，在所有的實驗中，算法的遺憾隨預算變化的總體趨勢為隨著預算的增加而逐漸增加。從圖中的結果我們可以看出，OPT-FIX算法、BP-Greedy算法、BP-UCB算法和OPPM算法的遺憾在所有的實驗中雖然有增加的趨勢，但是增加的趨勢逐漸變緩并傾向呈現出水平的趨勢，說明在所有的工人的花費分布下，這些算法

51、的單位價格的遺憾逐步減少，并幾乎趨近于0，表明這些算法無遺憾的性質。從圖中我們還可以看出BP-MaxTasks算法的遺憾隨價格的變化趨勢忽高忽低，呈現出不穩定的趨勢，說明該算法在實際的實現中波動性較大，不是和應用在具體的眾包系統中。此外，在實驗2中，BP-Greedy算法的變化曲線幾乎和x軸重合，說明BP-Greedy算法對于均勻分布的花費效果更加準確。在所有的變化圖中OPPM算法的變化曲線一般都在BP-UCB算法的下方，說明OPPM算法的遺憾相對于BP-UCB算法來說更小，也表明了該算法具有更優的效益。3.3.4價格選擇情況對比分析眾包系統中的任務拍賣算法的核心是做到探索最優價格與利用當前最

52、優價格的均衡，這一節主要探討不同拍賣算法之間選定的價格的分布情況，如圖5.4所示。圖3.8 價格被選擇的概率在圖5.4中x軸代表價格，y軸代表價格被選擇的概率，紅色的虛線代表最優的價格，從上圖中我們可以觀察到BP-MaxTasks算法在局部最優價格停留的時間過長，這是對局部最優價格的過度利用照成的，而BP-UCB算法則收斂較慢，一直在進行價格的探索，這是由于探索過度導致的，但是OPPM算法在進行了數次的探索之后立刻收斂到了最優價格的附近從而較好的做到了探索和開發的均衡，有著不錯的效果。3.4總結從上面的實驗中我們可以看出，基于定價機制的任務拍賣算法在不知道工人信息的前提下準確的估計出了工人的花

53、費曲線，并且其中的OPPM取得了和最優離線算法相近的結果，很好的做到了探索和開發的均衡，減少了眾包系統的交流負擔和應用難度，在眾包系統有著廣闊的應用場景。第4章考慮任務質量的任務拍賣算法在第3章中介紹的算法中，都假設每一個任務都具有單位價值，沒有考慮任務的質量問題，因此本文基于此背景，從理論上提出了OPPMQuality算法，使得其在分配任務的同時考慮任務的質量問題，并具有近似與最優離線算法的性能。4.1考慮任務質量的任務拍賣算法的基本模型在考慮任務質量的任務拍賣算法中，算法給工人提供價格，工人完成任務后，請求者獲得的效益不再是單位價值而是01之間的某個數，該工人完成任務的價值與其花費相關，相

54、同花費的工人完成任務的價值是獨立同分布的。如果工人接受任務，則請求者付出報酬為，獲得的收益為，如果工人拒絕任務，則請求者的花費為0，獲得的收益為，算法的目的是最大化請求者的效益。在本文中，只考慮工人完成的任務時立即可觀測的情況，為了解決上面提出的考慮任務質量的拍賣問題，我們根據OPPM算法提出了一種改進的方案，使得其能夠用于工人的工作質量不一致的場景中，我們在下面介紹改進后的OPPMQuality算法。4.2任務質量對選擇最優價格的影響為了獲取任務質量不一致情況下的最優價格，我們首先引入下面的符號。令代表價格的價值的均值，如果預算足夠，則選擇價格可以獲得的價值為，但是由于預算限制的存在使得提供

55、價格時，可以雇傭的工人的數目只有，因此價格可以獲得效益的估計值為，最優的價格相應的變更為，也就是使得接受價格的效益取得最大時的價格。此外，由于引入價格的質量后，使得3.2.3節介紹的眾包系統中的拍賣算法的特征不在適用，因此需要設計新的價格選擇策略。4.3OPPMQuality算法在OPPM算法中，忽略了工人工作質量的不一致性，我們在下面解決工人工作質量不一致的問題，并改進OPPM算法得到含有質量控制的OPPMQuality算法。4.3.1考慮任務質量的價格選擇算法為了獲取最優的價格，我們需要設計新的價格選擇策略。同樣地，我們令代表用戶是否接受任務，代表我們選擇價格可以獲得的效益，其中，。在真實

56、的眾包平臺中，由于價格是離散的，所以最優價格不一定可以取得。我們同樣的引入最優可能價格POPs的概念，并且對其進行一定的改進，首先我們根據下面的定義引入可能的最優價格:（1） 如果最優價格滿足,則記為POP-1。（2） 如果價格滿足則記為POP-2.在這里我們使用代表價格對應任務的價值的估計值，為了完整性我們約定,如果有多個價格滿足，則取價格最低的那一個價格作為POP。根據上面的定義，我們首先提出最優可能價格搜索算法POPSearcher用于搜索可能的最優價格。在POPSearcher算法中，根據不同價格的效益選擇可能最優的價格，在找到可能最優的價格之后，為了增加算法的探索能力，我們提出MAB

57、Quality根據不同價格的效益和能夠產生價值的置信區間上限選擇當前應該提供給工人的價格。MABQuality算法如下：在OA-MABQuality算法中，我們使用代表價格對應的任務能夠產生的價值在時刻的估計值，算法在開始時首先對初始化為1,代表價格被接受的次數初始化為0，代表價格的接受概率的估計值初始化為1，代表價格被提供的次數初始化為0,其余的符號和它們在OA-MAB算法中的定義相同。MABQuality算法在尋找提供給工人的價格時，首先根據時每一個價格能夠產生價值的估計值選擇能夠帶來最大效益的價格，然后如果價格產生的效益的估計值最大的POPs屬于POP2，且存在花費更少的價格的產生價值的置信區間上限超過了當前POP帶來的效益,則算法有一半的幾率進行一次探索