[WIP 20151111]iCrowd: An Adaptive Crowdsourcing Framework 第二部分:算法

Fan, J., Li, G., Ooi, B. C., Tan, K. L., & Feng, J. (2015, May). iCrowd: An Adaptive Crowdsourcing Framework. InProceedings of the 2015 ACM SIGMOD International Conference on Management of Data (pp. 1015-1030). ACM.

转载本文请注明来自http://boweihe.me/?p=1661

翻论文翻到一篇新鲜的货,赶紧拿出来分享,如果不发帖我想是没有兴趣能精读啦~为了督促自己,所以就写了这篇东西。

目前来说应该是分三个部分:

  1. 基本思路及框架
  2. 算法(努力中, 本篇)
  3. 实验(努力中)

准确率估计(对应章节3)

基本思路是考虑微任务之间的“相似性”,因为文章第6章的实验结果表明,参与者在相似领域的准确率是有可比性的(尽管领域差距变大以后可比性变差)。藉此,如果我们观察到某个参与者w正确作答了某些问题,我们可推断她也能胜任相似领域的一些问题。

111 112

打个比方,给定一组已经全局完成的微任务,包括那些qualification microtasks(Fig4. t1, t2, t3)以及那些已经达成共识的任务(t6, 在任务数量k=3时);同时给定一参与者w1。那么所谓的准确率估计问题就是想计算出参与者w1对于那些待分配给他的问题(如t4, t7)的回答准确率。

基于图的估计模型(Graph-Based Estimation Model)

基于图的估计模型,其主要思路就是利用微任务在图中的相似度(边的权值)估计某些问题作答的准确度:如果对于某些已经全局完成的微任务能拿到观测的准确率qw,我们就能据此推测图中相连的其他微任务(节点)的准确率。以Fig.3为例,给定参与者w已回答问题的准确度,比如正确回答了t2,错误回答t3,那我们可以预测w在作答与t2相似的问题(如图中的t7, t8, t9)会有相对较高的准确率,而作答与t3类似问题(如t10, t11, t12)时准确率就会相对较低。

然而,照上述方法算出这么个估计值是不实际的,因为估计出的准确率pw既要保证每组相邻节点算出的准确度的局部相似性(local similarity),又要保证所属子图准确度的全局相似性(global similarity)。此外,pw还要和观察准确率qw有一致性:估计出来的值不能和观测值有很大偏差。下面给出问题的形式化描述方法,方便起见,113

114 115

引理1. 公式(2)的解为如下形式

20151111144848

引理2. 基于公式(4)的迭代算法能够算出公式(3)中的最优解p*

证明:见引文[35]

2015111114493320151111145807

算法1如下图:

iCrowd_algoritum1

 

iCrowd: An Adaptive Crowdsourcing Framework 第一部分:基本思路及框架

Fan, J., Li, G., Ooi, B. C., Tan, K. L., & Feng, J. (2015, May). iCrowd: An Adaptive Crowdsourcing Framework. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (pp. 1015-1030). ACM.

转载本文请注明来自http://boweihe.me/?p=1661

翻论文翻到一篇新鲜的货,赶紧拿出来分享,如果不发帖我想是没有兴趣能精读啦~为了督促自己,所以就写了这篇东西。

目前来说应该是分三个部分:

  1. 基本思路及框架(本篇)
  2. 算法(努力中)
  3. 实验(努力中)

一句话概括

iCrowd能实时地通过评估参与者完成任务的成绩来估计他作答的准确性,并且能够借此分析出他擅长作答的领域。

问题描述(对应章节2.1)

iCrowd_01

iCrowd_02

iCrowd框架(对应章节2.2)

iCrowd_03

Glickman 的ELO算法

Glickman的ELO算法被搬到众包中实现,可以参考这篇

Bashir, M., Anderton, J., Wu, J., Golbus, P. B., Pavlu, V., & Aslam, J. A. (2013). A Document Rating System for Preference Judgements. In Proceedings of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval (pp. 909–912). New York, NY, USA: ACM. http://doi.org/10.1145/2484028.2484170
但是文章里算法描述的部分似乎有写错的地方,可能是作者不小心,把公式(7)的分母部分写错了(原文中的字母j没有换成自己的B)~
Glickman的原文是:
Glickman, M. E. (1999). Parameter estimation in large dynamic paired comparison experiments. Journal of the Royal Statistical Society: Series C (Applied Statistics), 48(3), 377-394.
QQ截图20150622165240

其中m为对手个数, 为与对手B进行比赛的次数; 为本局比赛A的结果(1-胜,0-负)

F是一个常量,(Bashir et al. 2013)中F=200, (Glickman, 1998)中F=400.

 

The rating algorithm is implemented as follows.

(a) Collect game outcome data over a rating period.

(b) At the end of the period, update players’ rating distributions due to game outcomes from their preperiod (prior) rating distributions.

(c) Subsequently update players’ rating distributions due to the passage of time.

Crowd-BT算法模型 Part III [在线学习]

转载请注明来自http://boweihe.me/?p=1524

本文内容源自

Chen, X., Bennett, P. N., Collins-Thompson, K., & Horvitz, E. (2013, February). Pairwise ranking aggregation in a crowdsourced setting. InProceedings of the sixth ACM international conference on Web search and data mining (pp. 193-202). ACM.

第二部分还在努力学习,先把第三部分贴上来…有部分理解不全我就假装没看到了(捂脸)

在线学习:这个方法似乎是借鉴了Crowd-BT模型,但是最后参数更新的方法用了另外一套东西,可以独立于Crowd-BT的最优化而计算。

QQ截图20150517212359 QQ截图20150517212419 QQ截图20150517212505

Crowd-BT算法模型 Part I [Bradley-Terry的延伸-模型基础]

转载请注明来自http://boweihe.me/?p=1524

本文内容源自

Chen, X., Bennett, P. N., Collins-Thompson, K., & Horvitz, E. (2013, February). Pairwise ranking aggregation in a crowdsourced setting. InProceedings of the sixth ACM international conference on Web search and data mining (pp. 193-202). ACM.

第一部分是对Crowd-BT中采用的模型的中文翻译及理解,不涉及后面的主动学习算法(因为暂时没看懂,哈哈)。

因为没弄懂Wordpress的公式插件,所以暂时用Word文档的截图了..

QQ截图20150515100316

 

QQ截图20150515100340

QQ截图20150515100406