目錄摘要 [5]保持相同為0.2，在OPPM算法中，價格變化最小值取值為0.01。3.3.2 算法的收益對比分析這一節(jié)主要介紹不同算法的收益的對比，任務(wù)拍賣算法的目的是最大化請求者的收益，因此算法的收益是衡量一個算法的性能的重要因素。在本小節(jié)的實驗中，不斷增加請求者的預(yù)算，根據(jù)不同算法的收益繪制出效益隨著預(yù)算的變化圖，從而對比不同算法產(chǎn)生的效益，結(jié)果如下圖所示：圖3.2實驗1的效益圖3.3實驗2的效益圖3.4實驗3的效益從不同算法的效益之間的關(guān)系中我們可以看出，在所有的實驗中除BP-MaxTasks算法外的所有算法產(chǎn)生的效益基本上呈現(xiàn)出隨預(yù)算的增加而線性上升的趨勢，而BP-MaxTasks算法的效益雖然整體上也呈現(xiàn)出上升的趨勢，但是偶爾會出現(xiàn)效益的下降，說明BP-MaxTasks算法不是特別穩(wěn)定，波動性較大。進一步對各種算法產(chǎn)生的效益進行對比我們可以看出OPPM算法和BP-DGreeedy算法的性能相當(dāng)，均接近最優(yōu)離線算法OPT-FIX所產(chǎn)生的效益。BP-UCB算法相對于OPPM來說效果稍差，但是相對于BP-MaxTasks算法，性能也提高40%左右，從圖示的算法對比結(jié)果來看，雖然基于定價機制的拍賣算法并沒有工人的花費信息，但是其產(chǎn)生的效益仍然能夠接近甚至達到最優(yōu)離線算法的效果，使得請求者達到了最優(yōu)收益，說明設(shè)計完善的基于定價機制的任務(wù)拍賣算法也能夠充分的預(yù)測得到工人的花費曲線，因此基于定價機制的任務(wù)拍賣算法由于交流負(fù)擔(dān)小，解決了用戶需要自己估計花費信息等問題，具有明顯的優(yōu)勢。3.3.3 算法的遺憾對比分析遺憾是一個算法產(chǎn)生的效益和最優(yōu)算法之間的差值，是評估一個算法性能的重要因素，一個算法的無遺憾性是指隨著預(yù)算的增加，算法的遺憾和預(yù)算的比值逐漸趨于0的性質(zhì)，是一個優(yōu)秀的拍賣算法應(yīng)具有的性質(zhì)，這一節(jié)我們實驗不同算法的遺憾隨著預(yù)算的變化關(guān)系，結(jié)果如下圖所示：圖3.5實驗1的效益圖3.6實驗2的效益圖3.7實驗3的遺憾從遺憾與預(yù)算的變化關(guān)系中我們可以看出，在所有的實驗中，算法的遺憾隨預(yù)算變化的總體趨勢為隨著預(yù)算的增加而逐漸增加。從圖中的結(jié)果我們可以看出，OPT-FIX算法、BP-Greedy算法、BP-UCB算法和OPPM算法的遺憾在所有的實驗中雖然有增加的趨勢，但是增加的趨勢逐漸變緩并傾向呈現(xiàn)出水平的趨勢，說明在所有的工人的花費分布下，這些算法的單位價格的遺憾逐步減少，并幾乎趨近于0，表明這些算法無遺憾的性質(zhì)。從圖中我們還可以看出BP-MaxTasks算法的遺憾隨價格的變化趨勢忽高忽低，呈現(xiàn)出不穩(wěn)定的趨勢，說明該算法在實際的實現(xiàn)中波動性較大，不是和應(yīng)用在具體的眾包系統(tǒng)中。此外，在實驗2中，BP-Greedy算法的變化曲線幾乎和x軸重合，說明BP-Greedy算法對于均勻分布的花費效果更加準(zhǔn)確。在所有的變化圖中OPPM算法的變化曲線一般都在BP-UCB算法的下方，說明OPPM算法的遺憾相對于BP-UCB算法來說更小，也表明了該算法具有更優(yōu)的效益。3.3.4 價格選擇情況對比分析眾包系統(tǒng)中的任務(wù)拍賣算法的核心是做到探索最優(yōu)價格與利用當(dāng)前最優(yōu)價格的均衡，這一節(jié)主要探討不同拍賣算法之間選定的價格的分布情況，如圖5.4所示。圖3.8價格被選擇的概率在圖5.4中x軸代表價格，y軸代表價格被選擇的概率，紅色的虛線代表最優(yōu)的價格，從上圖中我們可以觀察到BP-MaxTasks算法在局部最優(yōu)價格停留的時間過長，這是對局部最優(yōu)價格的過度利用照成的，而BP-UCB算法則收斂較慢，一直在進行價格的探索，這是由于探索過度導(dǎo)致的，但是OPPM算法在進行了數(shù)次的探索之后立刻收斂到了最優(yōu)價格的附近從而較好的做到了探索和開發(fā)的均衡，有著不錯的效果。3.4 總結(jié)從上面的實驗中我們可以看出，基于定價機制的任務(wù)拍賣算法在不知道工人信息的前提下準(zhǔn)確的估計出了工人的花費曲線，并且其中的OPPM取得了和最優(yōu)離線算法相近的結(jié)果，很好的做到了探索和開發(fā)的均衡，減少了眾包系統(tǒng)的交流負(fù)擔(dān)和應(yīng)用難度，在眾包系統(tǒng)有著廣闊的應(yīng)用場景。

第4章 考慮任務(wù)質(zhì)量的任務(wù)拍賣算法在第3章中介紹的算法中，都假設(shè)每一個任務(wù)都具有單位價值，沒有考慮任務(wù)的質(zhì)量問題，因此本文基于此背景，從理論上提出了OPPMQuality算法，使得其在分配任務(wù)的同時考慮任務(wù)的質(zhì)量問題，并具有近似與最優(yōu)離線算法的性能。4.1 考慮任務(wù)質(zhì)量的任務(wù)拍賣算法的基本模型在考慮任務(wù)質(zhì)量的任務(wù)拍賣算法中，算法給工人提供價格，工人完成任務(wù)后，請求者獲得的效益不再是單位價值而是0~1之間的某個數(shù)，該工人完成任務(wù)的價值與其花費相關(guān)，相同花費的工人完成任務(wù)的價值是獨立同分布的。如果工人接受任務(wù)，則請求者付出報酬為，獲得的收益為，如果工人拒絕任務(wù)，則請求者的花費為0，獲得的收益為，算法的目的是最大化請求者的效益。在本文中，只考慮工人完成的任務(wù)時立即可觀測的情況，為了解決上面提出的考慮任務(wù)質(zhì)量的拍賣問題，我們根據(jù)OPPM算法提出了一種改進的方案，使得其能夠用于工人的工作質(zhì)量不一致的場景中，我們在下面介紹改進后的OPPMQuality算法。4.2 任務(wù)質(zhì)量對選擇最優(yōu)價格的影響為了獲取任務(wù)質(zhì)量不一致情況下的最優(yōu)價格，我們首先引入下面的符號。令代表價格的價值的均值，如果預(yù)算足夠，則選擇價格可以獲得的價值為，但是由于預(yù)算限制的存在使得提供價格時，可以雇傭的工人的數(shù)目只有，因此價格可以獲得效益的估計值為，最優(yōu)的價格相應(yīng)的變更為，也就是使得接受價格的效益取得最大時的價格。此外，由于引入價格的質(zhì)量后，使得3.2.3節(jié)介紹的眾包系統(tǒng)中的拍賣算法的特征不在適用，因此需要設(shè)計新的價格選擇策略。4.3 OPPMQuality算法在OPPM算法中，忽略了工人工作質(zhì)量的不一致性，我們在下面解決工人工作質(zhì)量不一致的問題，并改進OPPM算法得到含有質(zhì)量控制的OPPMQuality算法。4.3.1 考慮任務(wù)質(zhì)量的價格選擇算法為了獲取最優(yōu)的價格，我們需要設(shè)計新的價格選擇策略。同樣地，我們令代表用戶是否接受任務(wù)，代表我們選擇價格可以獲得的效益，其中，。在真實的眾包平臺中，由于價格是離散的，所以最優(yōu)價格不一定可以取得。我們同樣的引入最優(yōu)可能價格POPs的概念，并且對其進行一定的改進，首先我們根據(jù)下面的定義引入可能的最優(yōu)價格:如果最優(yōu)價格滿足,則記為POP-1。如果價格滿足則記為POP-2.在這里我們使用代表價格對應(yīng)任務(wù)的價值的估計值，，為了完整性我們約定,如果有多個價格滿足，則取價格最低的那一個價格作為POP。根據(jù)上面的定義，我們首先提出最優(yōu)可能價格搜索算法POPSearcher用于搜索可能的最優(yōu)價格。在POPSearcher算法中，根據(jù)不同價格的效益選擇可能最優(yōu)的價格，在找到可能最優(yōu)的價格之后，為了增加算法的探索能力，我們提出MABQuality根據(jù)不同價格的效益和能夠產(chǎn)生價值的置信區(qū)間上限選擇當(dāng)前應(yīng)該提供給工人的價格。MABQuality算法如下：在OA-MABQuality算法中，我們使用代表價格對應(yīng)的任務(wù)能夠產(chǎn)生的價值在時刻的估計值，算法在開始時首先對初始化為1,代表價格被接受的次數(shù)初始化為0，代表價格的接受概率的估計值初始化為1，代表價格被提供的次數(shù)初始化為0,其余的符號和它們在OA-MAB算法中的定義相同。MABQuality算法在尋找提供給工人的價格時，首先根據(jù)時每一個價格能夠產(chǎn)生價值的估計值選擇能夠帶來最大效益的價格，然后如果價格產(chǎn)生的效益的估計值最大的POPs屬于POP2，且存在花費更少的價格的產(chǎn)生價值的置信區(qū)間上限超過了當(dāng)前POP帶來的效益,則算法有一半的幾率進行一次探索選擇花費更少而收益卻可能更大的，充分體現(xiàn)除了算法的探索性，如果價格產(chǎn)生的效益的估計值最大的POPs屬于POP1，則算法不在探索可能更好的價格，而是利用當(dāng)前能夠產(chǎn)生最優(yōu)價格的當(dāng)前最優(yōu)價格，充分利用當(dāng)前最優(yōu)價格。4.3.2 OPPMQuality算法實現(xiàn)在選擇了能夠獲取最大化效益的價格之后，我們利用OPPMQuality算法向工人提供最優(yōu)的價格，然后根據(jù)工人是否接受任務(wù)以及工人完成任務(wù)的質(zhì)量更新每一個價格的接受概率和每一個價格能夠獲取的平均價值，詳細的算法偽代碼如下所示:在上述的算法中，代表眾包平臺允許的最小價格變化，用于算法運行過程中價格的離散化和生成。在算法開始運行時首先使用和運算B生成所有可行的價格，對價格進行離散化。為了保證算法的預(yù)算可行性，每次在生成可行價格時使用剩余預(yù)算除以獲取所有可能的價格。在OPPMQuality算法中，根據(jù)價格的接受概率和對應(yīng)任務(wù)價值的估計值，調(diào)用MABQuality算法在價格集合S中搜索獲得最優(yōu)價格，將對應(yīng)的價格提供給工人，然后根據(jù)工人的接受或者拒絕信息更新任務(wù)計數(shù)、剩余預(yù)算以及價格接受概率和對應(yīng)任務(wù)價值的估計值等信息。4.4 實驗對比分析4.4.1 實驗背景這一小節(jié)，我們設(shè)計實驗評估OPPMQuality算法的效益，本節(jié)的實驗中，保證相同花費的工人完成任務(wù)的質(zhì)量是獨立同分布的，為了結(jié)果的準(zhǔn)確性，我們分別采用了不同的分布模擬工人的花費分布和任務(wù)價值的分布，具體的信息如表4.1所示。表4.1：實驗中采用的工人的花費分布實驗編號價格分布完成任務(wù)的價值1302303304.4.2 實驗結(jié)果在實驗中，我們保持的恒定，取價格變化最小值取值為0.01，為了對算法的性能進行評估，我們選擇擁有工人全部信息的最優(yōu)離線算法OPT-FIXQuality作為對比，對OPPMQuality算法效益進行評估，實驗的結(jié)果如下。圖4.1質(zhì)量控制算法的效益，實驗1圖4.2質(zhì)量控制算法的效益，實驗2’圖4.3質(zhì)量控制算法的效益，實驗3從效益與預(yù)算的途中我們可以看出OPPMQuality算法產(chǎn)生的效益達到了最優(yōu)離線算法的90%左右，其中從實驗2中可以看出OPPMQuality算法在均勻分布下能夠達到更好的效果，產(chǎn)生的效益和最優(yōu)離線算法十分接近。但是從實驗1和實驗3的結(jié)果來看，OPPMQuality算法對于正態(tài)分布的工人的花費更加敏感，產(chǎn)生的效益波動性較大，有較大的不穩(wěn)定性，還有一定的優(yōu)化空間。4.5 總結(jié)從4.4節(jié)的實驗結(jié)果可以看出，本文提出的OPPMQuality算法的效益平均達到了最有離線算法90%左右的性能，能夠在工人完成質(zhì)量不一致的背景下使得請求者的收益仍然保持在較高的水平。當(dāng)時OPPMQuality算法還有一些缺點，首先就是OPPMQuality算法需要在每個到達時線性搜索最好的價格，然后再搜索每一個價格的價值置信區(qū)間上限，導(dǎo)致算法的運行效率低下，從而時間效率太低。其次，算法產(chǎn)生的效益仍然有一定的波動性，還有很廣闊的優(yōu)化空間。

第5章 眾包中拍賣算法的實現(xiàn)本章主要簡單介紹一些算法的實現(xiàn)。本章首先介紹文中沒有給出代碼的算法的實現(xiàn)，然后提出一種三分搜索的算法用于提高BP-UCB算法、OPPM算法的運行效率。5.1 OPT-FIX算法的實現(xiàn)OPT-FIX時離線最優(yōu)算法，并且用來作為算法性能對比時的基準(zhǔn)，是眾包中的任務(wù)拍賣算法能夠獲得的最優(yōu)性能的上屆，并且所有算法的遺憾是根據(jù)OPT-FIX算法計算得到的，因此OPT-FIX算法實現(xiàn)的是否有效率極大的影響著整個實驗的性能，但是在很多的文獻中都只是給出了該算法的介紹，并沒有給出具體的實現(xiàn)，因此本文基于計算報價花費的概率密度函數(shù)實現(xiàn)OPT-FIX算法。下面介紹OPT-FIX算法的實現(xiàn)。5.1.1 計算報價接受概率因為OPT-FIX是離線算法，所以可以利用工人的所有信息，然后根據(jù)這些信息選擇一個最優(yōu)的固定價格提供給到來的每一個工人直到預(yù)算耗盡，在OPT-FIX算法中，最優(yōu)的價格肯定存在于工人的報價中，因此也不需要對價格進行離散化，本文中的實現(xiàn)首先統(tǒng)計每一個價格被接受的概率，然后選擇能夠使達到最大的價格，首先計算每一個價格被接受的概率，偽代碼如下所示。在CalculateCdf算法中，為了快速的計算出價格的接受概率，首先對花費進行排序，則價格的接受概率為。5.1.2 計算最優(yōu)效益在獲得價格接受概率之后，根據(jù)最優(yōu)價格固定價格的定義，我們遍歷每一個花費使得取得最大值得價格就是最優(yōu)固定價格，然后給每一個到來的工人均提供該價格就能夠獲取最優(yōu)的效益。5.2 改進BP-UCB算法和OPPM算法的運行效率這一小節(jié)我們首先觀測BP-UCB算法和OPPM算法中效益函數(shù)的特征，然后根據(jù)其特征提出一種三分搜索的策略加速算法的運行過程。5.2.1 BP-UCB算法和OPPM算法的效益函數(shù)在BP-UCB算法和OPPM算法中最優(yōu)價格根據(jù)下面的公式得到：（4）在公式4中，隨著價格p的增加而單調(diào)增加，而則隨著價格p的增加而單調(diào)減少，我們記，則是一個單極值函數(shù)，如圖5.1所示，紅色的線代表,藍色的線代表，綠色的線代表兩者的較小值，也就是。而搜索效益最高的價格的位置就是尋找取得最大值時的自變量的值，因此，我們可以使用三分查找快速查找最優(yōu)價格的位置。圖5.1效益函數(shù)圖5.2.2 三分查找算法如圖5.1所示，我們分別使用和代表搜索的區(qū)間，代表為區(qū)間的中點，為代表右部分區(qū)間的中點，則我們可以根據(jù)和的值判斷出離最大值更遠的區(qū)間，并且可以確定函數(shù)的最大值不在此區(qū)間內(nèi)，所以可以舍去，詳細的算法的偽代碼如下圖所示：在三分查找算法中，由于是單峰函數(shù)，因此可以直接舍棄三段中距離極值較遠的一段而不會失去最大值，因此該算法能夠很快的找到最優(yōu)價格的位置，使得搜索最優(yōu)價格的效率由降至級別，算法的總運行效率由降至級別，能夠極大的提高BP-UCB算法和OPPM算法的運行效率。

第6章 總結(jié)與展望6.1 本文總結(jié)在本文中，首先我們從理論上對比了多種基于報價機制的任務(wù)拍賣算法和基于定價機制的任務(wù)拍賣算法，然后實現(xiàn)多種任務(wù)拍賣算法并設(shè)計實驗驗證不同算法的性能，并設(shè)計實驗研究造成這些算法的性能差異的原因，根據(jù)實驗結(jié)論我們可以知道基于定價機制的算法需要更少的用戶信息，但是其效益仍然能夠達到和報價機制的任務(wù)拍賣算法相同的效果，尤其是OPPM算法不僅在理論上達到了最優(yōu)而且通過實驗可以驗證其很好的做到了探索與開發(fā)的均衡，在眾包中的任務(wù)拍賣算法中有著不錯的應(yīng)用前景。其次通過研究BP-UCB算法和OPPM算法的效益函數(shù)，本文還使用三分查找算法對BP-UCB算法和OPPM算法進行了改進，使得其擁有更高效的搜索效率。最后，本文提出了一種考慮任務(wù)質(zhì)量的任務(wù)拍賣算法OPPMQuality用于克服現(xiàn)有任務(wù)拍賣算法的缺陷，并且通過實驗驗證該算法具有不錯的性能。6.2 后續(xù)工作展望任務(wù)拍賣算法在眾包中有著廣闊的應(yīng)用場景，雖然OPPM算法實現(xiàn)簡單并且獲得了不錯的性能，但是算法在真實場景的應(yīng)用還有很長的路要走。首先OPPM算法只考慮到每一個工人只接受一件任務(wù)的場景，在眾包系統(tǒng)中，一名工人完成數(shù)件任務(wù)的案例屢見不鮮，因此是算法更加實用的一個方向就是考慮每名工人可以接受更多用戶的場景。此外，由于在眾包系統(tǒng)中工人的工作質(zhì)量參吃不齊，而OPPM算法沒有采取有效的質(zhì)量控制策略，因此算法中工人的工作質(zhì)量控制問題是另外一個可以考慮的方向，想要控制工人的工作質(zhì)量，本文提出的OPPMQuality方法是一個可行的方案，但是由于算法的效率地下以及波動性較大等原因，距離實用性算法仍然有很遙遠的距離，因此還有很大的改進空間。

參考文獻VonAL,MaurerB,McmillenC,etal.reCAPTCHA:human-basedcharacterrecognitionviaWebsecuritymeasures[J].Science,2008,321(5895):1465-1468.GaoY,ChenY,LiuKJR.OnCost-EffectiveIncentiveMechanismsinMicrotaskCrowdsourcing[J].IEEETransactionsonComputationalIntelligence&AiinGames,2015,7(1):3-15.SimpsonED,VenanziM,ReeceS,etal.LanguageUnderstandingintheWild:CombiningCrowdsourcingandMachineLearning[C]//InternationalConferenceonWorldWideWeb.ACM,2015:992-1002.SingerY,MittalM.Pricingmechanismsforcrowdsourcingmarkets[C]//InternationalConferenceonWorldWideWeb.ACM,2013:1157-1166.SinglaA,KrauseA.Truthfulincentivesincrowdsourcingtasksusingregretminimizationmechanisms[C]//InternationalConferenceonWorldWideWeb.ACM,2013:1167-1178.HuZ,ZhangJ.OptimalPosted-PriceMechanisminMicrotaskCrowdsourcing[C]//Twenty-SixthInternationalJointConferenceonArtificialIntelligence.2017:228-234.LaiTL,RobbinsH.Asymptoticallyefficientadaptiveallocationrules[J].AdvancesinAppliedMathematics,1985,6(1):4-22.NowakS.Howreliableareannotationsviacrowdsourcing:astudyaboutinter-annotatoragreementformulti-labelimageannotation[C]//InternationalConferenceonMultimediaInformationRetrieval.ACM,2010:557-566.Callison-BurchC.Fast,cheap,andcreative:evaluatingtranslationqualityusingAmazon'sMechanicalTurk[C]//ConferenceonEmpiricalMethodsinNaturalLanguageProcessing:Volume.AssociationforComputationalLinguistics,2009:286-295.AlonsoO,MizzaroS.CanwegetridofTRECassessors?UsingMechanicalTurkforrelevanceassessment[J].SigirWorkshopontheFutureofIrEvaluation,2009.BadanidiyuruA,KleinbergR,SingerY.Learningonabudget:postedpricemechanismsforonlineprocurement[C]//ACMConfe