Vol.56 No (Mar. 2015) 1,a) 1 1 1, , Human Computation Quality Control 1 1 Nonnegative Matrix Factorization A Task A

Size: px

Start display at page:

Download "Vol.56 No (Mar. 2015) 1,a) 1 1 1, , Human Computation Quality Control 1 1 Nonnegative Matrix Factorization A Task A"

しおりまきい
5 years ago
Views:

1 1,a) 1 1 1, , Human Computation Quality Control 1 1 Nonnegative Matrix Factorization A Task Allocation Method to Human Computation Motohiro Makiguchi 1,a) Daichi Namikawa 1 Shozo Azuma 1 Michio Shimomura 1,2 Naoyoshi Kanamaru 1 Received: October 4, 2014, Accepted: November 10, 2014 Abstract: Establishing a quality control methodology for obtaining a data set consisting of the results of tasks performed by workers is one of the most important problems to solve in Human Computation (HC). Our research proposes a new quality control methodology based on efficient task allocation algorithm which selects suitable workers for a given task. In concrete, the algorithm classify the workers into group by Nonnegative Matrix Factorization (NMF) clustering of the workers based on the result of the tasks performed by the workers in the past, aiming to reduce the cost of worker-sectioning process and easily select a large number of workers without sacrificing the quality. We have shown that the newly proposed algorithm successfully reduced the cost of worker-sectioning process for a given task, and can select a large number of suitable workers maintaining quality. Keywords: human computation, crowdsourcing, task allocation, nonnegative matrix factorization (NMF) 1. Human Computation HC 1 NTT NTT Service Evolution Laboratories, Yokosuka, Kanagawa , Japan Chiba Institute of Technology, Narashino, Chiba , Japan a) makiguchi.motohiro@lab.ntt.co.jp [1] HC c 2015 Information Processing Society of Japan 1132

2 HC Amazon Mechanical Turk [2]AMT Crowdsourcing HC AMT [3] HC 1 HC 2 HC HC HC Quality Control [5] [8] c 2015 Information Processing Society of Japan 1133

3 [9] 2 50% [5] 2 [6] [7] [4] Private Crowdsourcing System [10] 1 [11] Donmez IEThresh [12] Gomes [14] c 2015 Information Processing Society of Japan 1134

1 2 3 1 2 4. 1 Table 1 The top hierarchy in the named entity. Person God Organizaton Location Facility Product Event Natural Object Disease Color Timex Periodx Numex Other 4.

4 Table 1 The top hierarchy in the named entity. Person God Organizaton Location Facility Product Event Natural Object Disease Color Timex Periodx Numex Other 4.1 HC Named Entity [15] Wikipedia [16] 14 1 Web 1 1 Fig. 1 The screen capture of the named entity task Nonnegative Matrix Factorization NMF [17] K-means NMF 1 NMF NMF I J X I K c 2015 Information Processing Society of Japan 1135

5 T K J V T V TV X D T V X NMF k {1,...,K} T V TV X D Kullback-Leibler divergence KL divergence D (X, TV) = I i=1 j=1 J d (x ij, x ij ) (1) d (x ij,t T i,v j )=x ij log x ij t T i v x ij + x ij (2) j x ij = t T i v j T V t ik v kj x ij j x t ik t ij v kj ik, (3) v kj v kj j v kj x ij x ij t ik i i t ik 4.3 NMF X i {0,...,I} j {0,...,J} [0, 1] 2 j i y j i i j i y j i =[1, 0, 0] X N = n < N 3. 2 n (4) 1 3 1, n 3 NMF NMF K k {1...K} m < N n PartialExperts (m K) n Majority n Random n 2 2 Table 2 The number of workers that requested test task. NMF m K PartialExperts m K Majority 0 Random 0 c 2015 Information Processing Society of Japan 1136

m 3 m =3 1 2 2 1 2 5. 5.1 1 331 0.61 SD 0.14 0.19 0.95 5.1.1 2 18 K =6 4 3 n =3 NMF 0.86 PartialExperts 0.80Majority 0.67 Random 0.61 5.1.2 3 18 NMF Random- Expert n 3 17 n 5.1.3 4 3 n =3 Experts 3 m 3 K 4 66 6 3 n 18 Fig.

6 m 3 m = SD K =6 4 3 n =3 NMF 0.86 PartialExperts 0.80Majority 0.67 Random NMF Random- Expert n 3 17 n n =3 Experts 3 m 3 K n 18 Fig. 3 The average accuracy rate increasing the extract worker number n Fig. 2 The accuracy rate in each method. 4 Fig. 4 The average accuracy rate increasing the number of test task workers. c 2015 Information Processing Society of Japan 1137

6. 5 0.7 Fig. 5 The accuracy rate of each method in the average accuracy rate 0.7 more. 6 0.

7 Fig. 5 The accuracy rate of each method in the average accuracy rate 0.7 more Fig. 6 The accuracy rate of each method in the average accuracy rate under /5 1/ Task High Task Low ,000 5 Task High 6 Task Low 5 Majority NMF Random NMF NMF NMF c 2015 Information Processing Society of Japan 1138

8 HC [1] von Ahn, L.: Human Computation, Doctoral Thesis, UMI Order Number: AAI , CMU (2005). [2] Amazon Mechanical Turk, available from amazon.com/jp/mturk (accessed ). [3] Bigham, J.P., Jayant, C., Ji, H., Little, G., Miller, A., Miller, R.C., Miller, R., Tatarowicz, A., White, B., White, S. and Yeh, T.: VizWiz: Nearly Real-time Answers to Visual Questions, UIST 2010 (2010). [4] PrivateCrowdSourcing 3M3-OS-07d-2 (2013). [5] Sheng, V.S., Provost, F.J. and Ipeirotis, P.G.: Get another label? improving data quality and data mining using multiple, noisy labelers, KDD 2008, pp (2008). [6] deim2013, pp.1 7 (2013). [7] Sakurai, Y., Okimoto, T., Oka, M., Shinoda, M., and Yokoo, M.: Quality-Control Mechanism utilizing Worker s Confidence for Crowdsourced Task, Proc. 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2013 ) (2013). [8] Dawid, A.P. and Skene, A.M.: Maximum Likelihood Estimation of Observer Wrror-Rates Using the EM Algorithm, Journal of the Royal Statistical Society, Series C, Vol.28, No.1, pp (1979). [9] Vol.28, No.3, pp (2013). [10] 2M5-OS-07b-2 (2013). [11] 2M5-OS-07b-1 (2013). [12] Donmez, P., Carbonell, J.G. and Schneider, J.: Efficiently learning the accuracy of labeling sources for selective sampling, Proc. 15th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (SIGKDD) (2009). [13] NTT com/service/qpolicy4.html/ [14] Gomes, R., Welinder, P., Krause, A. and Perona, P.: Crowdclustering, Advances in Neural Information Processing Systems (2011). [15] google.com/site/extendednamedentityhierarchy/ [16] Wikipedia, available from (accessed ). [17] NMF / signal/sawada/mypaper/ pdf/ c 2015 Information Processing Society of Japan 1139

9 NMF NTT ICT NTT NTT GIS NTT c 2015 Information Processing Society of Japan 1140

& Vol.5 No (Oct. 2015) TV 1,2,a) , Augmented TV TV AR Augmented Reality 3DCG TV Estimation of TV Screen Position and Ro

& Vol.5 No (Oct. 2015) TV 1,2,a) , Augmented TV TV AR Augmented Reality 3DCG TV Estimation of TV Screen Position and Ro TV 1,2,a) 1 2 2015 1 26, 2015 5 21 Augmented TV TV AR Augmented Reality 3DCG TV Estimation of TV Screen Position and Rotation Using Mobile Device Hiroyuki Kawakita 1,2,a) Toshio Nakagawa 1 Makoto Sato