基于組合多臂賭博機的移動群智感知用戶招募算法

蔣偉進 陳萍萍 張婉清 孫永霞 陳君鵬

①(湖南工商大學計算機學院 長沙 410205)

②(武漢理工大學計算機學院 武漢 430073)

1 引言

隨著移動設備和無線通信技術的快速發(fā)展，催生了移動群智感知技術，智能終端設備都攜帶著不同類型的傳感器，比如全球定位系統(tǒng)、溫度傳感器、距離傳感器、麥克風等，這些都可以用來收集和人們密切相關的各類數(shù)據(jù)[1]，然后數(shù)據(jù)平臺實現(xiàn)對數(shù)據(jù)的加工(如清洗、評估、提取、聚合等操作)和向數(shù)據(jù)消費者輸出標準化的可用數(shù)據(jù)[2]，從而被運用于各大應用領域，如智能交通、公共服務、環(huán)境監(jiān)測、智能醫(yī)療等[3]。

在典型的群智感知系統(tǒng)中，由任務提供者、感知數(shù)據(jù)平臺、任務參與者3部分組成[4]。任務提供者向數(shù)據(jù)平臺提供發(fā)布的任務和相應報酬，感知數(shù)據(jù)平臺負責數(shù)據(jù)的接收、集成、清理、分析和交易等[5]，任務參與者接收平臺發(fā)布的任務信息，根據(jù)自身情況進行回應，同時上報完成感知任務的能力，比如感知質量或空間覆蓋[6]。數(shù)據(jù)平臺根據(jù)用戶的回應按照利益最大化的目標選擇一部分用戶來參與并支付一定的報酬，這個過程就稱為用戶招募[7]。被招募的用戶再執(zhí)行相應的感知任務和把結果返回到平臺。最后平臺會對用戶完成的感知質量進行評估和記錄，使下一輪選擇出更合適的用戶。

在現(xiàn)有工作中，移動群智感知系統(tǒng)很多是假設用戶的感知質量已知，并在此基礎上采用特定的優(yōu)化目標對用戶進行招募[8]。然而現(xiàn)實生活中，移動用戶的感知質量往往是未知的，不僅平臺未知，用戶也難以確定自身的感知質量，因為感知質量不僅與用戶的感知環(huán)境、綜合素質有關，還與用戶的感知設備以及參與興趣相關[9]。雖然用戶的完成任務的感知質量不一樣，但由于用戶擁有的感知設備是不變的，用戶習慣都不會發(fā)生明顯的變化，因此用戶的感知質量滿足一定的分布條件，完成的感知任務越多，感知質量的分布就越準確[10]。因此本文研究的是在平臺不知道用戶的感知質量或成本值的前提下，數(shù)據(jù)交易平臺如何建立合適的用戶招募機制，不僅需要在用戶執(zhí)行的過程學習其成本和感知質量值，還需要盡最大可能保證移動群智感知系統(tǒng)的高效性和利潤最大化[11]。 而用戶感知質量的未知給用戶招募造成了極大的挑戰(zhàn)，平臺是應該選取那些已經(jīng)被認為是高質量的用戶，還是選取其他可能具有更高質量的用戶。這就是強化學習中的經(jīng)典問題–“探索”和“利用”[12]。為解決該難題，本文將用戶選擇問題建模成有預算的多臂老虎機模型，并采用基于置信區(qū)間上限的用戶招募算法來招募合適的用戶。

本文所做的貢獻主要由以下3個方面：

(1)本文是招募用戶的感知質量未知的前提下，解決有限預算下的感知質量最大化用戶招募問題。一般而言，數(shù)據(jù)平臺總是希望選擇那些感知能力強的系統(tǒng)用戶，然而在實際場景中平臺并不能事先獲得用戶的成本和感知質量參數(shù)，因此本文采用組合多臂賭博機(Combination Multi-Armed Bandit,CMAB)來形式化用戶感知能力的學習過程，并提出在理想情況和缺乏用戶成本參數(shù)情況下的用戶招募機制。

(2)在上述兩種情況下的用戶招募機制下，分別擴展基本的置信區(qū)間上限 (Upper Confidence Bound, UCB)的公式，設計針對所有任務的感知質量函數(shù)，提出貪婪用戶招募策略，選擇最大化函數(shù)邊際值的移動用戶。

(3)在不同設定情況下的實驗結果表明提出的基于CMAB的用戶招募算法能夠有效地學習用戶的感知質量值。

2 相關工作

對于移動群智感知，當前學者所做的工作主要是用戶招募，在成本限制下選擇任務完成好即感知質量高的參與者，同時采用激勵機制鼓勵用戶分享數(shù)據(jù)。劉琰等人[13]研究移動群智感知的任務分發(fā)，使參與者參加多個感知任務，并提出多任務分配方法，在任務移動總距離最短和參與者人數(shù)最少的目標下選擇出最佳的參與者。周杰等人[14]選擇盡可能少的參與者來接受感知任務，達到對指定地點集合的時空覆蓋這一質量要求，定義了“t-時隙k-覆蓋”群智感知任務，以最小代價完成該類任務。Wang等人[15]重點關注具有預算約束的覆蓋均衡用戶選擇(Coverage-Balancing User Selection, CBUS)問題，選擇一個適當?shù)挠脩糇蛹?，使感知范圍盡可能大且平衡，同時又滿足移動群智感知活動指定的預算。蔣偉進等人[16]針對移動用戶追求高回報的貪婪特性會使得招募成本偏高的問題提出一種針對團體的群智感知招募激勵機制，解決了移動用戶對數(shù)據(jù)進行過高定價來提高利潤的問題。Song等人[17]研究了任務分配策略，針對受歡迎的任務被大家所選擇，不受歡迎的任務往往無法分配到合適用戶的情況提出一種面向覆蓋的任務分配(Coverage-Oriented Task Assignment, COTA)策略，通過學習和利用工人的任務偏好來實現(xiàn)覆蓋范圍的任務分配，將不受歡迎的任務遷移到一些合格的工人上。Zhang等人[18]通過優(yōu)化任務的可靠性和空間多樣性來選擇參與者， 建立了兩個優(yōu)化目標的激勵模型，再基于逆向拍賣設計兩個在線激勵機制。Chen等人[8]對如何選擇最合適的參與者提出一個均勻覆蓋和最大覆蓋的覆蓋評估，設計一個基于軌跡段的選擇方案。Xiao等人[19]針對用戶招募過程中每個用戶的感知質量和招募成本不透露給其他用戶或平臺的目標，使用秘密共享方案設計了兩個安全的用戶招募協(xié)議。上述學者大多數(shù)是在已知用戶的感知質量的基礎上優(yōu)化用戶人數(shù)和移動距離，減少平臺預算，但未考慮用戶收集的感知數(shù)據(jù)質量在實時變化的情況，這就需要我們對用戶的感知質量進行學習，得到最適合用戶的任務分配。因此本文提出基于CMAB的用戶招募算法，利用強化學習來對用戶的感知質量進行學習，實時與感知數(shù)據(jù)平臺交互，解決有限預算下任務感知質量最大化問題。

3 基于CMAB的用戶招募算法模型

3.1 基本定義

表1 本文主要符號和釋義

u(Pr)代表在r輪次中所有用戶的感知質量，每個任務完成的感知質量再乘以相應的權重。

定義2 有限預算下的感知任務的質量最大化問題(Maximum Quality and Limit Budget,MaxQLimitB)可定義為

在基于UCB感知質量公式上本文提出感知質量函數(shù)，如式(9)所示

3.2 基于CMAB的用戶已知成本招募算法

然而在每輪選擇中，總有一些用戶的成本超過了成本預算限制。所以本文提出一種新穎的貪婪修復算法(Greedy Repair Algorithm, GRA)，如表2所示。首先將所有預選的用戶都按感知質量與成本比率降序排列，存儲在數(shù)組Q[0,1,···,n]， 并采用標志布爾數(shù)組F[i]標識每個用戶的選擇狀態(tài)，若F[i]=1表示該用戶被選中，F(xiàn)[i]=0則未被選中。在算法貪婪修復算法中，感知質量成本比首先降序排列，依次選擇參與者，同時更改F[i]的狀態(tài)，并計算累計的成本值Cost，當累計成本大于預算時GRA并不會停止，它會從總成本減去當前的所選參與者的成本，并將該參與者的狀態(tài)標識為F[i]=0，接著重復上面的步驟，選擇盡可能多的參與者。

表2 貪婪修復算法(GRA)

3.3 基于CMAB的用戶未知成本招募算法

因此感知質量的函數(shù)值和招募成本的比率如式(13)所示

表3 基于CMAB 的用戶已知成本招募算法

該算法的基本思路是在初始化階段，選擇用戶的第1個選項來初始化相應的參數(shù)，在之后的用戶招募階段，結合貪婪修復算法，并在預算有限的前提下，每輪次選擇感知質量和成本最大比率的移動感知用戶，并更新用戶的成本參數(shù)，獲得新的用戶成本，該算法時間復雜度為O(APLY)，由于數(shù)組需要大小為 n 的臨時存儲空間，因此空間復雜度為O(n)。具體過程如表4所示。

表4 基于CMAB 的用戶未知成本招募算法

4 實驗結果與分析

本文的實驗是在預算有限的背景下，選擇感知質量未知的用戶過程，驗證基于CMAB的用戶招募算法學習用戶感知質量的能力，即能否選擇高質量的用戶。為了方便表述，在實驗結果圖中，將算法2命名為已知的組合多臂賭博機算法(Combined Multi-Arm Bandit algorithm with Known Cost,KC-CMAB)，將算法3命名為未知的組合多臂賭博機算法(Combined Multi-Arm Bandit algorithm with UnKnown Cost, UKC-CMAB)，為了驗證算法的高效性，分別采用ε-貪婪算法，基于預算的貪婪算法，基于質量的貪婪算法，α-最優(yōu)算法進行對比實驗，具體設置如下所示。

4.1 數(shù)據(jù)集設置

本文采用意大利羅馬地區(qū)320輛左右出租車的1個月以來真實數(shù)據(jù)集以及模擬數(shù)據(jù)集，羅馬數(shù)據(jù)集包括乘客上下車的日期和時間、出租車和乘客的位置、行程距離以及乘客人數(shù)。由于數(shù)據(jù)集過于龐大，計算的總成本過高，本文首次對數(shù)據(jù)集進行處理：(1)選擇10 km×10 km的矩形區(qū)域作為空間限制。(2)在區(qū)域中，選取了數(shù)據(jù)集中m個乘客位置作為模擬平臺發(fā)布的感知任務，取值范圍分別為[200,1000]。n輛出租車作為模擬的移動用戶，取值范圍為 [50 200]。在本次實驗中，m和n的默認值分別設置為800,150，每個移動用戶執(zhí)行任務的范圍為[6 15]。(3)每個感知任務采用圓盤覆蓋的方法，即以任務為中心，以250 m為半徑畫出圓盤，如果用戶在該圓盤范圍內(nèi)，則執(zhí)行相關的任務。對于感知質量的期望值qi表示用戶i訪問該位置的頻率。成本參數(shù)的期望值為范圍(0,1]的隨機生成數(shù)，并采用高斯分布和均勻分布來設置感知質量值和成本。模擬數(shù)據(jù)集是根據(jù)現(xiàn)有的方法生成模擬數(shù)據(jù)，假設感知任務和參與者的位置均勻分布在一個10 km×10 km的2D空間中，經(jīng)緯度則均勻地分布在(0,1)中，此外，每個參與者都有一個反映過去完成任務情況的成本值，為了簡便，用歐幾里得距離來量化感知任務位置與參與者所在位置的距離長短，將考慮不同規(guī)模的參與者和任務對選擇結果的影響，分別從{200,500,1000}和{50,100,150,200}中選擇n個參與者和m個感知任務。

4.2 算法的對比

為了突出KC-CMAB算法的高效性，結合現(xiàn)有工作，分別設計4個算法來進行對比實驗，第1個算法是 ε-貪婪算法(Epsilon-Greedy，簡稱epsilon-Grd)，該算法平衡利用和探索策略，以(1-ε)的概率選擇最大收益的參與者，以ε的概率隨機選擇1個參與者，實現(xiàn)探索策略，本實驗將ε設置為0.1。第2個算法是α-最優(yōu)算法，已知所有用戶的感知質量和成本參數(shù)，能夠選擇出最佳用戶。第3個算法是基于預算的貪婪算法 (Budget-Greedy, budget-Grd)，從預算角度下構建組合多臂賭博機招募機制，將預算平均分配到每輪，并貪心地選擇成本比值較小的用戶，直到預算耗盡。第4個算法是基于質量的貪婪算法 (Quality-Greedy，簡稱quality-Grd)從質量角度構建組合多臂賭博機招募機制，來選擇感知質量最大的用戶，不考慮用戶成本的大小，直至預算耗盡。

4.3 實驗過程分析

本實驗將采用總任務的感知質量值作為實驗測試結果指標，將從平臺每輪招募的人數(shù)Y、招募的用戶數(shù)量A、發(fā)布的任務數(shù)量P和預算的成本值B 4個指標來進行設定評估算法的性能。為了驗證上述各個指標從小到大增加，本算法是否有效性的問題。首先設定其中3個指標不變，另外一個指標將從小變大。參考前期實驗基礎，首先設置指標不變的數(shù)值：預算B為10000，每輪招募人數(shù)Y為80，用戶數(shù)量A為150，任務數(shù)量P為800。測試總感知質量分別隨著預算B、任務數(shù)量P、用戶數(shù)量A以及每輪招募人數(shù)Y的變化，驗證算法是否還有效，具體如圖1–圖4所示。

圖1 總感知質量與預算成本的關系

圖2 總感知質量與任務數(shù)量的關系

圖3 總感知質量與用戶數(shù)量的關系

圖4 總感知質量與每輪招募人數(shù)的關系

隨著預算成本值的增大，各個算法的總感知質量增大，但KC-CMAB和UKC-CMAB更接近α-Optimal算法，由圖1所示；因為隨著預算的增大，每個用戶獲得收益更多，能夠激勵認真地完成任務，獲得不錯的報酬，因此用戶感知質量與成本的比率就越精確，數(shù)據(jù)平臺就越有可能選擇排在前面的高質量的用戶。對于逐漸增大要完成的任務數(shù)量、整體算法先呈增大后減少的趨勢，如圖2所示；因為剛開始的預算充足，增加任務數(shù)量，能使每個人的任務數(shù)量增多，對于KC-CMAB和UKCCMAB算法來說，能更多次學習用戶的感知質量，從而提高用戶選擇的精度，但隨著任務數(shù)量越來越多，所得報酬大幅度減少，不能激勵用戶認真完成任務，從而降低了總任務的感知質量；隨著用戶數(shù)量的增多，對于數(shù)據(jù)平臺來說，擴大了用戶選擇范圍，能夠探索出更多的優(yōu)秀用戶，在一定范圍內(nèi)能大大增高任務總的感知質量，但由于預算有限，當用戶范圍超過臨界值時，任務的總感知質量將逐漸變小，如圖3所示；隨著每輪用戶招募人數(shù)的增多，能夠在每一輪次中積極探索高質量的用戶，但會使不同用戶執(zhí)行同樣的任務，會大大增加數(shù)據(jù)冗余度，當超過一定界限，總感知質量逐漸減少，如圖4所示。實驗結果證明：隨著預算，每輪招募人數(shù)、招募用戶數(shù)量和任務數(shù)量各個指標從小到大增加，KC-CMAB和UKC-CMAB都整體優(yōu)于其他3種算法，接近于α-Optimal最優(yōu)算法，具有良好的自適應性。

上述實驗是設定預算B為10000的情況，沒有具體驗證在不同預算下，每輪招募人數(shù)、招募用戶數(shù)量和任務數(shù)量對任務的總感知質量的影響。接下來在本文的實驗中設定不同預算值下的參數(shù)變量，第一為預算值B，范圍為5000～15000；第二為每輪招募人數(shù)Y，設置Y=50～120，間隔為10；第三為招募的用戶數(shù)量，設置A=60～200，間隔為20；第四為比較發(fā)布的任務數(shù)量，設置P=200～1000，間隔為200。設置的情況匯總如表5所示。

表5 算法2實驗情況設定

4.4 實驗結果分析

對于情況1～情況4，如圖5–圖7所示，在每輪招募人數(shù)為20～50時，5種算法的感知質量差距相差不大，但KC-CMAB整體好于UKC-CMAB,epsilon-Grd, bridge-Grd, quality-Grd，跟α-Optimal接近，因為平臺每輪招募的人數(shù)Y越多，總輪次越少，如圖8所示，這表示用戶的選擇性擴大，容易選中高質量的用戶，但隨著招募的人數(shù)大大提高，個人所獲得收益降低，用戶積極性很可能降低，參與度不高，所獲得感知質量降低，因此需要選擇合適的Y在有限成本下使感知質量最大化。而UKC-CMAB的算法比KC-CMAB效果要差，但比其他3種算法效果好，因為該算法不僅要學習成本，還要學習感知質量，使結果最優(yōu)化。

圖5 總感知質量和每輪招募用戶數(shù)量的關系(b=5000)

圖6 總感知質量和每輪招募用戶數(shù)量的關系(b=10000)

圖7 總感知質量和每輪招募用戶數(shù)量的關系(b=15000)

圖8 每輪次和每輪招募人數(shù)所占比率的關系

對于圖9–圖11所示，隨著招募用戶的增多，KC-CMAB和UKC-CMAB算法所獲得的感知質量明顯大于其他3種算法，而KC-CMAB更接近α-最優(yōu)算法，達到α-Optimal最優(yōu)算法的80%以上，這表示文中提出的算法能夠充分選擇利用策略，學習選擇高質量的用戶，而對于其他3種算法，容易陷入局部最優(yōu)化，未選擇最優(yōu)用戶。

圖9 感知質量和用戶數(shù)量的關系(b=5000)

圖10 感知質量和用戶數(shù)量的關系(b=10000)

圖11 感知質量和用戶數(shù)量的關系(b=15000)

如圖12，圖13，圖14所示，隨著任務數(shù)量的增多，KC-CMAB和UKC-CMAB的感知質量先增后降，在任務數(shù)1000達到感知質量最大值，因為任務數(shù)量越多，招募的用戶隨著增多，任務的成本降低，但會考慮到感知質量越高的用戶，其成本越高這種情況，算法會優(yōu)先選擇感知質量略差，但成本更低的用戶。

圖12 感知質量和任務數(shù)量的關系(b=5000)

圖13 感知質量和任務數(shù)量的關系(b=10000)

圖14 感知質量和任務數(shù)量的關系(b=15000)

5 結束語

本文針對有限預算下用戶成本已知和未知的條件下最大感知質量的用戶招募問題，在任務的感知質量不斷變化的情況下提出一種基于CMAB模型的用戶招募算法，使移動群智平臺能根據(jù)每輪用戶感知質量的反饋，動態(tài)調(diào)整自己的選擇，在下一輪選擇符合條件的高質量用戶，使用戶招募在長期的選擇中能夠獲得較好的平均感知質量。但在用戶招募過程中，未考慮用戶為了高收益而提供虛假結果的情況，后續(xù)將針對如解決用戶為獲得報酬而做虛假任務的問題進行大量研究。