高麗萍,孫明達,高 麗,陳慶奎

1(上海理工大學 光電信息與計算機工程學院,上海 200093)

2(復旦大學 上海數(shù)據(jù)科學重點實驗室,上海 200093)

3(上海理工大學 圖書館,上海 200093)

1 引 言

通信技術和移動智能終端的發(fā)展讓移動設備能夠采集到多種傳感數(shù)據(jù),這使得智能手機用戶能夠輕松發(fā)現(xiàn)并分享數(shù)據(jù).于是移動眾包(MCS)成為了一個熱門話題,其融合了智能手機和眾包的特點,利用廣大的移動用戶群體來分享信息,提高社會福利.同時,MCS可以結(jié)合云服務,物聯(lián)網(wǎng)等前沿技術,使其在物流運輸,環(huán)境監(jiān)控,社交網(wǎng)絡等各個領域被廣泛運用[1,2].

一個典型的移動眾包應用主要基于3類實體,任務請求者、任務參與者(簡稱工人)和眾包平臺.請求者將一些感知任務發(fā)布到平臺上,并設置一些要求(預算,截止時間等).對任務感興趣的工人向平臺提出執(zhí)行任務的請求,平臺收集到工人信息后合理地分配任務.最后根據(jù)工人的任務完成情況,平臺給予其一些回饋.由于眾包工人來源于互聯(lián)網(wǎng),存在較多不確定因素,工人持續(xù)提交低質(zhì)量感知數(shù)據(jù)會影響MCS平臺的可靠性和精確性,損害請求者的利益.如何有效地激勵工人參與任務并且得到高質(zhì)量的傳感數(shù)據(jù)成為MCS的核心問題.

因此,一個可靠的MCS平臺需要設計有效的激勵機制[3].許多激勵機制建立在金錢激勵上,即每個工人對任務有一個報價,表示他所消耗的物質(zhì)資源或所提供勞動力的貨幣價值,并期望自己的貢獻能夠獲得回報.如果沒有足夠的獎勵,工人就沒有動力參與任務.平臺根據(jù)報價和工人其余信息來決定任務的分配和報酬.在離線場景下,平臺先收集所有工人的信息后再進行調(diào)度分配,這使得平臺比較容易針對不同的目標(如最大化效用[3-6]、最大化社會福利[7-9]、最小化報酬[10,11]),配合一些限制條件選擇最優(yōu)的工人集.然而在現(xiàn)實中,工人是以隨機動態(tài)的方式到達或離開平臺.與離線場景相比,MCS平臺在在線場景中無法事先得知工人會在什么時間段參與任務.一旦工人上線,需要立即做抉擇,即是否接受或拒絕工人的請求,同時當任務分配給工人后,還需要根據(jù)已有的信息決定報酬.

此外,激勵機制的設計還需考慮質(zhì)量評估.MCS的任務大多以提交傳感數(shù)據(jù)為主,如監(jiān)測某個地區(qū)的噪聲、溫度、路面狀況等.由于傳感器和動態(tài)環(huán)境的不一致,移動用戶采集的傳感數(shù)據(jù)通常存在噪聲或不同程度的誤差.在無法準確了解每個工人的感知行為和任務地點的真實情況下,平臺很難去判斷傳感數(shù)據(jù)的質(zhì)量.同時在MCS應用中,獲取真實的樣本數(shù)據(jù)(Ground Truth)作為其它傳感數(shù)據(jù)的質(zhì)量標準是困難的,在很多情況下甚至是不現(xiàn)實的[4].這時候,平臺可以先發(fā)布一些任務,采集足夠多的歷史數(shù)據(jù)后判斷數(shù)據(jù)質(zhì)量,推測出每個工人的可靠程度.但是請求者有固定的預算,這限制了平臺不能無限次分配任務來獲取大量歷史數(shù)據(jù).所以MCS的激勵機制需要制定一個有效的質(zhì)量評估方式.

本文之前的工作[5]提出了一種長時間質(zhì)量感知的激勵機制策略(QAI),將眾包任務分配過程分成多個階段,同時把工人的質(zhì)量看作是隱變量,各個階段的請求者都會給工人提交的答案進行打分,平臺則根據(jù)這些分數(shù)運用隱馬爾可夫模型來預測下一階段的工人質(zhì)量.然而,QAI是一個離線場景下的激勵機制,同時假設了請求者可以直接評估工人的任務結(jié)果,無法解決前面提到的問題.因此,本文在QAI的基礎上進一步考慮在線工人選擇問題,提出一種多階段質(zhì)量感知的在線激勵機制(SQOI).具體的貢獻如下:

·本文考慮了預算與時間約束下的在線工人選擇問題,將眾包活動周期分成多個階段,設計了階段性的系統(tǒng)與質(zhì)量模型,通過靜態(tài)質(zhì)量和動態(tài)質(zhì)量來評定各個階段在線工人的服務質(zhì)量.

·根據(jù)模型,提出多階段質(zhì)量感知的在線激勵機制SQOI,設計了具體的框架,集成了階段性工人選擇、質(zhì)量預估和參數(shù)更新三個模塊.理論證明了SQOI具有預算可行性、個體合理性、真實性和計算效率.

·通過實驗測試了SQOI在不同參數(shù)下的性能,并且證明了SQOI在提升數(shù)據(jù)質(zhì)量上的有效性.

論文的其余部分組織如下:第2節(jié)對相關工作進行了介紹.第3節(jié)介紹了系統(tǒng)模型和效用計算.第4節(jié)給出了多階段質(zhì)量感知的在線激勵機制框架和相關算法設計.第5節(jié)對SQOI進行了仿真實驗.結(jié)論在最后一節(jié)中給出.

2 相關工作

2.1 激勵機制

如今,已有許多關于MCS的激勵機制研究.大多數(shù)的工作是針對離線場景下的激勵機制,即平臺在分配之前就得到了工人與任務的所有信息,如工人的能力,偏好,報價等.同時平臺會指定某一目標,這樣工人的選擇問題變?yōu)榱嗽谔囟s束下的規(guī)劃問題,需要設計算法求解該問題.如Yang等人[3]運用Stackelberg博弈思想設計激勵機制,最大化用戶的效用.Peng等人[6]從提高傳感數(shù)據(jù)質(zhì)量的角度上設計激勵機制,并運用信息論度量每個參與者的有效數(shù)據(jù)貢獻.Wen等人[7]提出一種基于質(zhì)量驅(qū)動的拍賣激勵機制,并提出一種概率方案來評估數(shù)據(jù)的準確性.Jin等人[8]則將用戶信息質(zhì)量作為激勵機制的一個重要指標,同時將任務分配問題看作一種集合覆蓋問題,設計了一種組合的反向拍賣模型來提高社會福利.以上研究都是基于離線場景下,不適用于工人實時到達的在線場景.

當前也有一些關于眾包的在線場景研究.Singer等人[10]提出了一種競價模型,從預算范圍內(nèi)最大化任務數(shù)量和最小化支付報酬兩種目標考慮激勵相容機制的實現(xiàn).Zhao 等人[12]基于在線競價模型,研究在指定預算下的服務價值最大化問題.同時在文獻[11]以最小化MCS的任務報酬為目標設計了節(jié)儉式的在線激勵機制.一些研究[9,13-15]將經(jīng)典的多臂賭博機模型用在移動眾包的在線任務分配中.其主要思想是以在線學習的方式權衡眾包環(huán)境下未知工人的探索與利用,在分配任務的過程,逐步對每個工人的能力和偏好有全面的認知.其中文獻[9,13]在工人選擇上進一步考慮其上下文信息,對工人的服務質(zhì)量進行建模,盡可能地選取高質(zhì)量工人.Han等人[14]提出BLISS框架來解決有限預算下的最大化傳感收益問題.Gao等人[15]則考慮預算和覆蓋限制下工人招募問題,從招募成本同質(zhì)和異質(zhì)兩種情況進行研究.然而以上的研究都假設了工人的數(shù)據(jù)質(zhì)量或貢獻可以直接得到.

2.2 數(shù)據(jù)質(zhì)量評估

由于在很多眾包場景下,任務請求者需要由第三方平臺為其判斷工人提交的數(shù)據(jù)質(zhì)量,甚至為每個任務集成一個可靠準確的答案,因此眾包的質(zhì)量評估成為了研究的熱點.Hung 等人[16]采用了多數(shù)投票算法,任務分配給多個工人獨立完成,平臺將收集的數(shù)據(jù)中的多數(shù)意見作為最終的正確結(jié)果.這個方法將所有工人的感知數(shù)據(jù)在質(zhì)量和貢獻上視為平等,沒有考慮工人的多樣性,最終的結(jié)果往往不準確.Zhang等人[17]則在標簽收集任務中,將工人執(zhí)行不同類別任務的可靠性作為權重,設置加權多數(shù)投票算法,得到每個任務的真實標簽.然而其考慮的任務是基于二進制標簽,不適用于連續(xù)性的移動傳感數(shù)據(jù).同樣Liu等人[18]采用MAB模型來提升數(shù)據(jù)集標記任務的質(zhì)量,其評估結(jié)果是離散的.Li 等人[19]進一步使用迭代式加權多數(shù)投票算法來減少標簽聚合的錯誤率.Liu等人[4]研究了感知上下文與數(shù)據(jù)質(zhì)量的關系,通過構(gòu)建一個上下文數(shù)據(jù)質(zhì)量分類器來實時估計工人數(shù)據(jù)質(zhì)量.Yang等人[20]通過無監(jiān)督學習的方式,將傳感數(shù)據(jù)聚類成多個中心,測量每個用戶的數(shù)據(jù)與中心的偏離值作為其質(zhì)量.

本文結(jié)合現(xiàn)有研究的優(yōu)缺點,針對移動傳感數(shù)據(jù)的特點來研究MCS在線場景下的激勵機制,設計了SQOI框架,旨在指定預算和時間限制下,為任務請求者選取能夠提供高質(zhì)量傳感數(shù)據(jù)的工人.

3 系統(tǒng)模型和效用計算

在本節(jié)中,我們將介紹系統(tǒng)模型和質(zhì)量模型,并且定義了本文所解決的問題.為了更清楚、更簡單地理解不同符號的含義,表1給出了文中出現(xiàn)的符號及其描述.

表1 符號說明

3.1 系統(tǒng)模型

首先,考慮一個在線MCS系統(tǒng),其中包含了一些用戶和一個中心化平臺.任務請求者向平臺發(fā)布了一系列傳感任務T={1,2,…,|T|},同時設置了預算B和活動周期D,前者規(guī)定了支付給工人的報酬上限,后者規(guī)定任務需要在指定時間內(nèi)完成.平臺擁有一些工人W={1,2,…,|W|},這些工人的移動設備上都安裝了MCS的應用程序.每個工人存在兩種狀態(tài):上線和離線.當工人設備上的MCS程序正在運行,其處于上線狀態(tài),準備參與任務；反之,當程序關閉后,其處于離線狀態(tài),無法參與任務.

由于涉及到金錢激勵,本文將任務與工人的匹配視作一個在線競價過程.圖1具體描述了整個在線MCS系統(tǒng)的執(zhí)行流程.首先MCS平臺對外發(fā)布這些傳感任務.當工人j上線后,決定是否參與任務,如果選擇參與,向平臺提交他的請求,包括報價bj、上線時間olj、離線時間ofj和執(zhí)行的任務集T(j).接著平臺根據(jù)工人的請求,在無法了解工人的情況下,決定是否聘用該工人.為了維護工人的權益,該決定是不可撤銷的.最后如果工人被選中,他需要執(zhí)行任務并提交自己的傳感數(shù)據(jù).平臺將賦予其一筆報酬pj.該過程將不斷重復,直到累計報酬超出預算或任務過期為止.

圖1 MCS的執(zhí)行流程

3.2 質(zhì)量模型

工人分配到傳感任務后,需要在規(guī)定時間內(nèi)提交傳感數(shù)據(jù).本文考慮一種普遍的場景,即請求者需要第三方平臺來判斷任務的結(jié)果和工人的表現(xiàn).如環(huán)境噪音、溫度檢測這類傳感任務,請求者需要采集一段時間內(nèi)不同地點的數(shù)據(jù),且事先無法得知標準值.在這種情況下,他需要MCS平臺發(fā)布任務收集數(shù)據(jù),并為每個任務預估出較為精確的結(jié)果.

(1)

(2)

3.3 效用計算

本文站在請求者的角度上研究問題,即在固定的活動周期內(nèi),工人以在線的形式請求執(zhí)行任務,平臺需要在有限的預算內(nèi)選擇能夠提供高質(zhì)量傳感數(shù)據(jù)的工人.用Ms表示第s階段平臺選擇的工人,于是請求者每個階段的效用為:

(3)

由于Bs是常量,所以目標函數(shù)可以轉(zhuǎn)變?yōu)?

(4)

(5)

平臺制定有效的激勵機制來盡可能地提升請求者的效用,同時需要滿足以下幾個性質(zhì):

1)預算可行性:累計的任務報酬不能超過預算限制,如公式(5)所示.

4)計算效率:提出的激勵機制可以在多項式時間內(nèi)計算.

4 多階段質(zhì)量感知的在線激勵機制框架設計

本節(jié)主要介紹SQOI的具體框架設計.在3.1節(jié),整個眾包活動周期被分成了多個階段,平臺需要在每個階段對上線的工人進行選擇、給予合適的報酬、評估數(shù)據(jù)質(zhì)量并更新相關參數(shù),為下一階段做參考.所以SQOI把每個階段又分為階段性工人選擇、質(zhì)量預估和參數(shù)更新3個模塊.由于各個階段的處理方式一致,為了簡化符號,下文統(tǒng)一將上標s忽略.

4.1 階段性工人選擇

在離線場景下,所有工人事先提交信息,平臺計算這些工人的服務質(zhì)量后,選取前k個質(zhì)量最高的工人即可最大化請求者的效用.而在線場景下,工人以隨機的形式一個接一個地上線,平臺無法獲得全局信息,這種情況類似于經(jīng)典的秘書問題.本文采用階段性工人選擇算法,每個階段輸入閾值θ作為工人的選擇標準.在當前階段結(jié)束后,統(tǒng)計該階段中所有在線工人的報價和預估的質(zhì)量,計算后更新θ,作為下一階段的輸入.首階段的閾值由平臺設定.

算法1.Phased Worker Selection

輸入:任務集T,預算B,活動周期D,閾值θ

輸出:分配結(jié)果M,支付報酬P

初始化M←φ,M′←φ,d←1

1.whiled≤Ddo

2.ifwjarriving at time stepdthen

5. end if

6.M′←M′∪{j}

7.end if

8.ifd=Dthen

9. obtain all the dataXworkers submit

10.tr,E←Quality_Estimate(M,X)

11.θ←Parameter_Update(tr,X,M,M′)

12.end if

13.t←t+1

14.end while

15.returnM,P,θ

4.2 質(zhì)量預估

在每個階段末,平臺收集完工人提交的數(shù)據(jù)后,如果事先得知每個任務的真實結(jié)果,那么可以判斷工人提交的傳感數(shù)據(jù)是否通過標準,從而評估工人的服務質(zhì)量.在本文的場景下,請求者無法給定每個任務的正確答案,即tri是一個隱藏變量,這導致了工人的效用矩陣無法直接獲取.因此平臺需要根據(jù)工人提交的傳感數(shù)據(jù)推測出最接近的答案.假設每個階段平臺能夠收集到大量的數(shù)據(jù),那么在參數(shù)未知的情況下,可以借助期望最大化(EM)算法的思想求得tri的最大似然估計,從而預估出真實數(shù)據(jù)所在的區(qū)間[6].

(6)

(7)

同時,可以得到每個區(qū)間的先驗估計:

(8)

(9)

即:

(10)

由于EM算法是一個迭代的方法,該模塊會重復計算每個工人的效用矩陣和每個任務的真實結(jié)果分布,直至參數(shù)收斂,最終得到一個準確的結(jié)果.

算法2.Quality Estimate

輸入:匹配集M,數(shù)據(jù)集X

輸出:任務真實結(jié)果分布tr,工人的效用矩陣E,

1.fori∈Tdo

2. form∈σdo

4. end for

5.end for

6.whiletr,Edid not converge do

7. for m∈σ

8. calculatetlmaccording to equation (8)

9. end for

10. for j ∈Mdo

12. form,n∈σdo

14. end for

15. end for

16. fori∈Tdo

18. form∈σdo

20. end for

21. end for

22.end while

23.returntr,E

4.3 參數(shù)更新

得到每個任務的真實區(qū)間概率和每個工人的效用矩陣后,平臺需要更新相關參數(shù).具體由算法3所示,主要分為兩部分,第1部分更新了工人的動態(tài)質(zhì)量和靜態(tài)質(zhì)量(1-11行).第2部分根據(jù)采樣集M′中工人質(zhì)量和報價計算出一個新的閾值θ(12-16行).其中參數(shù)δ由平臺設置,用來控制θ的大小,如果δ較小,θ變大,下一階段可以選擇的工人可能變少,導致階段任務分配率降低.反之δ較大,選擇工人的標準降低,可能造成數(shù)據(jù)質(zhì)量下降,浪費了預算.

算法3.Parameter Update

輸入:真實結(jié)果分布tr,數(shù)據(jù)集X,匹配集M,采樣集M′

輸出:下一個階段閾值θ

1. for(T(j),j)∈M,i∈T(j)do

2. get the intervalnofxi,j

4.αj←αj+1

5. else

6.βj←βj+1

7. end if

8. end for

9. forj∈Wdo

10. updatedqj,sqjfor next stage

11. end for

12.J←φ,sum←0,k←argmaxj∈M′(dqjsqj|T(j)|/bj)

13. while ∑j∈J∪{k}bj≤Bdo

14.J←J∪{k},sum←sum+dqksqk|T(k)|

15.k←argmaxj∈M′-J(dqjsqj|T(j)|/bj)

16.end while

17.returnsum/δB

4.4 理論證明

這一部分主要證明SQOI具備預算可行性、個體合理性、真實性以及計算效率.

定理1.SQOI具備預算可行性.

證明:SQOI將整個眾包活動周期分為多個階段.同時每個階段都包含有限的預算(2s-1B/2[log2D]).在算法1的第3行,當一個工人上線并提交他的報價后,平臺會比較當前階段剩余預算是否高于工人的預計報酬, 如果前者低于后者,即使工人滿足質(zhì)量標準也不會分配任務.因此框架滿足預算可行性.

定理2.SQOI具備個體合理性.

定理3.SQOI具備真實性.

所以在任何情況下,工人在虛假報價下的效用始終不會超過真實報價下的效用,即SQOI具備真實性.

定理4.SQOI具備計算效率.

證明:由于SQOI框架是在線運行的,所以需要考慮每個階段的復雜度.假設平臺的工人數(shù)為|W|,任務數(shù)為|T|.算法1的工人選擇階段最多需要執(zhí)行|W|次.在階段末,|σ|表示數(shù)據(jù)區(qū)間總數(shù),則運行質(zhì)量評估模塊(算法2)最多需要|W‖T‖σ|次迭代.|σ|由平臺設置,可以將其作為一個常量來對待,則復雜度為O(|W‖T|).在參數(shù)更新模塊(算法3),1-11行每個工人需要運行|T(j)|次,即最多需要O(|W‖T|).在12-16行的閾值計算部分,最多需要運行|W|log|W|次.因此,每個階段的時間復雜度為O(|W‖T|),SQOI具備計算效率.

5 實驗分析

本節(jié)通過實驗來驗證SQOI在不同參數(shù)下的表現(xiàn)和其在提升請求者效用上的有效性.

5.1 實驗設置

表2 實驗參數(shù)設置

本文設計了3個實驗.第1個實驗研究了SQOI在不同工人到達率下對效用的影響.第2個實驗研究了SQOI參數(shù)更新模塊的輸入?yún)?shù)δ對效用的影響.第3個實驗將階段離線算法(Offline)和在線隨機算法(Random)作為基線算法,同SQOI進行對比.在階段離線算法中,平臺能夠事先得到各個階段的工人上線時間、報價和服務質(zhì)量,然后選擇效用最高的k個工人.在線隨機算法則是在各個時刻隨機選擇上線的工人.

5.2 實驗結(jié)果

首先本文研究了在相同環(huán)境下,不同到達率對效用的影響.由圖2所示,當用戶到達率增加,整體效用增大.同時當?shù)竭_率在較高的區(qū)間內(nèi),高預算可以得到更大的效用值.因為工人參與任務的積極性一旦變高,平臺可以在初期階段收集充足的傳感數(shù)據(jù)和采樣集,對每個在線工人的質(zhì)量有更為準確的評估,所以算法1在后期階段可以選擇高質(zhì)量的工人集,提高請求者的效用.

圖2 工人到達率λ對效用的影響

接著本文針對算法3的輸入?yún)?shù)δ進行研究.固定預算為2000,比較到達率不同時,參數(shù)δ對算法性能的影響.由圖3所示,隨著δ的增長,整體效用在逐漸降低,同時λ越大時,效用下降的速率也越快.這是由于每個階段的篩選工人的閾值θ不斷下降,導致一些低質(zhì)量高報價工人可以被選中,最終總效用下降.可見在線場景中,工人參與度較高的情況下,增加δ會降低請求者的效用.

圖3 參數(shù)δ對效用的影響

最后本文將SQOI與階段離線算法和在線隨機算法進行比較.從圖4可以看出,隨著請求者預算的增加,離線算法由于在分配前事先獲取了所有工人的信息,其表現(xiàn)是最優(yōu)的.而SQOI的曲線始終位于離線算法和隨機算法之間,且遠高于后者.所以本文提出的方法比起在線隨機算法在提高請求者效用上有著顯著的優(yōu)勢.

圖4 不同算法的效用對比

6 總結(jié)與展望

本文考慮了預算與時間約束下的移動眾包在線激勵機制問題,提出了一種多階段質(zhì)量感知的在線激勵機制SQOI,通過增量學習的方式將整個眾包活動周期分為多個階段,每個階段集成了工人選擇、質(zhì)量評估和參數(shù)更新模塊.在缺少標準數(shù)據(jù)的情況下,為請求者盡可能地提供高質(zhì)量的傳感數(shù)據(jù).同時,本文證明了SQOI具有預算可行性,個體合理性,真實性和計算效率.最后通過實驗進一步說明該機制在提升數(shù)據(jù)質(zhì)量上的可行性.

然而,SQOI還存在著以下幾點問題.首先,本文考慮的是同質(zhì)任務,即任務類型相同,且所有任務由請求者同時發(fā)布,所以SQOI不適用于異質(zhì)任務的分配.其次,SQOI在工人低參與度的場景下,由于每個階段平臺收集的數(shù)據(jù)較少,會影響到算法的性能.在未來的工作中,我們會根據(jù)這些問題,進一步完善SQOI的模型和算法.