《中國人工智能學會通訊》——12.29 任務配置設定算法

下面介紹如何将合适的工作配置設定給正在請求任務的勞工 W。采用的思路是首先對每一個任務，都考慮如果将 W 中的某些勞工安排給它，它的準确率會有多少提升；然後選擇為每個勞工選擇最優的 h個任務，以最大化地提升準确率。

準确率估算 : 在推斷模型中，P(z t,k ) 被用來推斷 l t,k 的真實結果。如果 l t,k 的真實結果是 1，那麼推斷的準确率就是 P(z t,k =1)；如果真實結果是 0，那麼推斷的準确率就是 P(z t,k =0)。是以，需就真實結果是 1 或者 0 兩種情況考慮準确率。但兩者相似，為簡化描述，統一由 Acc t,k 來表示準确率。在任務配置設定過程中，如果任務 t 被安排給一組新的勞工集合，記為 W(t) W，由于 t 的答案改變了，Acc t,k 就會産生改變。記 Acc t,k (W(t)) 為考慮加入勞工 W(t)的答案後的改變的 t 準确率。 通過推斷模型的公式演算，可以證明 W(t) 中任務被安排給勞工的不同順序對準确率不會産生影響，并且 Acc t,k (W(t)) 可以線上性時間内計算獲得。

最優任務配置設定 : 對正在請求任務的勞工集合 W，目标是尋找一個配置設定方法來最大化期望準确率的提升。即尋找配置設定以最大化 ∆Acc t,k (W(t))。可以證明這一最大化問題是 NP-hard 的，由此，采用貪心算法來進行任務配置設定。貪心的過程是每次選擇能夠最大化期望準确率的〈勞工，任務〉，将任務安排給該勞工，不停選擇直到為每個勞工配置設定 h 個任務。