2. Crowdsourcing for Datafication

Tutorial slides are found at

http://goo.gl/Amif93
1

KYOTO UNIVERSITY

Obtaining “Human Judgment”:
Crowdsourcing Markets or Embedded Tasks
 Two approaches to asking people to make judgments:
1. Direct Approach: Using a crowdsourcing market• Asking workers to answer questions with monetary
rewards
2. Indirect Approach: Task embedding

2• Task enforcement：embedding a target task into anothertask users cannot evade: ex) reCAPTCHA• Gamification：Game playing activities for fun are designedto become completing tasks for a different purpose*Passive Approach: Extracting human judgments from existing
resources such as social media
KYOTO UNIVERSITY

Gamification: A Useful Design Pattern forCrowdsourcing
 Players activities for enjoying a game are actually completingtasks for a different purpose– Game With A Purpose; GWAP
– If successful, cost to complete tasks
will become almost zero

fold.it Ex: Foldit: a game to find folding configurations of proteins– Gamification of a hard optimization problem– Hundreds of thousands of registered workers– Outperforming automatic prediction algorithms– A successful example of human computation leading toKYOTO UNIVERSITY
3
important scientific discoveriesFramework for Gamification:
Output Agreement and Input Agreement
 The key to successful gamification is how cleverly we canembed the task into a game
– It is not obvious how to make a game fun– There is no established methodology for successfulgamification
 Several patterns used in gamification:– Output agreement– Input agreement

4

KYOTO UNIVERSITYExample of Output Agreement
ESP Game: A Game for Image Tagging
 A “cooperative” game by two players on the Web Two players see the same image and independently givewords to describe the image. If a common word is enteredby the both players, points are given to themEnter a word
describing thepicture

5KYOTO UNIVERSITY

Output Agreement:
Encouraging workers to agree on their outputs
 The hidden purpose behind the ESP game:– Collecting ``typical’’ keywords for describing images– Avoiding too general or too specific keywords
 Output agreement– Rewards are given to the players if they can reach agreementon their outputs– Each player guesses keywords her partner will come up with– This leads to find a typical keyword for representing theimage
6KYOTO UNIVERSITY

Input Agreement：
Overcoming the Difficulty in Output Agreement
 Difficulty in output agreement: Workers’ outputs rarely
coincide when the set of possible outputs is large (It assumes
that workers outputs coincide with a certain probability) Input agreement:– Each of two players receives an input (The two inputs canbe the same or different)– The goal of the players is guess if they have received thesame input after communicating to each other– If the communication is successful, they will guess correctly(and we can extract useful information from thecommunication)
7

KYOTO UNIVERSITYExample of Input Agreement:
Tag‐A‐Tune: Game for Tagging Music Each of two players receives an audio clip
– Audio clips they receive can be the same or different
 The goal of the players: Guessing whether the audio clips
they have been given are the same or not– Before answering the question, players exchange keywords
that represent the music, such “dynamic” or “peaceful”– Players receive points if their answers are correct– Note the system knows the true answer (whether the two
audio clips are the same) but the goal is collecting keywords
entered by the players
8KYOTO UNIVERSITY

Problem in Crowdsourcing Markets
Variance in Quality among Workers
 In a crowdsourcing market, not all workers do not haveability and dedication to complete the task
– Spam workers: work insincerely only to obtain a reward Quality control mechanisms in using a crowdsourcing market– Filtering workers based on the number of tasks they havecompleted or approval rates of their results– Qualification tests (hard to prepare for each kind of tasks)– Gold standard (not always available)

9

KYOTO UNIVERSITY

Quality Control: Introducing Redundancy andUsing Statistical Inference Assigning the same task to multiple workers
 Aggregating workers’ answers to estimate the true answer
Tasks

Check ifelectronicappliances

1Workers’ answers（Binary）

1Workers

1000
True answers
10?

?

1?

Unobserved trueanswers（We have toestimate them）?
KYOTO UNIVERSITY

Obtaining High Quality Answers fromRedundant Answers
 Aggregating answers using statistical inference• Majority voting, averaging
 Assuming different workers have the same ability to givecorrect answers– Every worker has the same power to vote
– However, their abilities are different actually If we know workers’ abilities (probabilities of giving truelabels), we can use them to weight their votes

11

KYOTO UNIVERSITY

Joint Estimation of Workers’ Abilities and True Labels
Usually we know neither workers’ abilities nor true labels
Mutual dependency between abilities and true labels

Workers withhigh abilities
give true labels

Workers giving
true labels havehigh abilities

Dawid&Skene (1979) proposed the latent class model to alternatingly
estimate true labels and workers’ abilities using the EM algorithm

12

KYOTO UNIVERSITY

Statistical Modeling Approach: Generative
Model with True Answers as Latent Variables
 Probability model to represent the generative process ofworkers’ answers from the true answer, depending on worker
specific parameters
 Statistical estimation of the unobserved true answer fromobservable answers
Workerʼs
TrueanswerWorkerʼs
answerability

Generative model
Unobservable world
Estimation
13

Observable
world
KYOTO UNIVERSITY

Latent Class Model:
A Basic Model to Represent Workers’ Abilities
 A basic model for quality control:– Proposed in 1979 for the purpose of medical diagnosis– Introducing worker’s ability (probability of giving the correct
Workersʼ answers
Workersanswer) ※Trueanswer
１
Unobservable１

０Workersʼ probabilities ofgiving correct answers(unknown)

14

１Observableanswers※More precisely,
probability of mistaking label k for label j
Dawid&Skene. Maximum Likelihood Estimation of Observer Error‐rated
KYOTO UNIVERSITY
Using the EM Algorithm. Applied Statistics, 28(1), pp.20‐28, 1979

Formal Problem Setting for the Latent Class ModelN questions, J workers
A worker does not necessarily answer all questions
Ji ⊆ {1, . . . ,J}: Set of workers who answered question iti ∈ {0, 1} (i ∈ {1, . . . , N}): true answer for question iyij ∈ {0, 1} (j ∈ Ji): answer for question i given by worker jOur goal is to infer {ti} given {yij}Workers
1Questions

101?
1?

0?

10
oWorkers’ answers

15?
True answers

KYOTO UNIVERSITY

Modeling Worker’s Ability Worker’s confusion matrix
Worker’sanswer
10

True answer
10

a1(j)
1-a1(j)a0(j)1-a0(j)t( j):probability that worker j gives answer 1
when the true answer is t
 Each element represents the probability of workers’ answer given
the true answer
 A worker who has large diagonal elements is considered to have ahigh ability16KYOTO UNIVERSITYThe Graphical Representation of the Latent Class ModeltipJ (j)

17N

 Prior probability of true answer tip(ti )  p (1  p)ti(1ti ) Conditional probability of worker’sanswer given the true answer
Jiyij

KYOTO UNIVERSITY

Using the EM algorithm to Alternatingly Estimate
Workers’ Abilities and True Answers
The model contains hidden variables (true answers)⇒Use the EM algorithm to alternatingly infer hidden variables andmodel parameters
1. Initialization：Estimate the expected values of {ti} using majority
votes
2. M‐step： Estimate parameters (j)} by using the current
expectations of {ti}3. E‐step：Estimate the expected values of hidden variables {ti} byusing the current estimation of (j)}4. Repeat steps 2 and 3 until convergence

19KYOTO UNIVERSITY

Filtering Workers based on their Abilities Workers’ confusion matrices contain information on their abilities Workers who always give wrong answers are actually “good” workers
 Using worker’s expected label to calculate the ability of the worker[Ipeirotis 2010]
p(ti  1 | yij  1) p( yij  1 | yi  1) p ( yi  1)
p ( yij  1)

1( j ) p
 ( j)
1 p   0( j ) (1  p)

 Spam workers give their answers independent of true answers, that isa1( j )  a0( j ) Spammer score [Raykar 2011]

S ( j )  (a1( j )  a0( j ) ) 2

20

KYOTO UNIVERSITY

Extension of the Latent Class Model:
Introducing Task Difficulties
 Introducing task difficulties as well as worker abilities
 Modelling the probability of worker j correctly answeringquestion j

Worker ability

Task easiness– When ability=0, probability of correct answer=0.5. Whenability and easiness are large, the probability of correct
answer is close to 1
– Estimation is made by the EM algorithm
21Whitehill et al. Whose Vote Should Count More: Optimal Integration of Labelsfrom Labelers of Unknown Expertise. NIPS 2009.

KYOTO UNIVERSITY

Further Extension of the Latent Class Model:
Modeling Annotators’ Different “Areas of Strength”
 In the models discussed so far:– Higher ability leads to higher probability of correctness– A harder task leads to lower probability of correctness
 Modeling “affinity” between a worker
and a task
Workerʼs
characteristics

Task
characteristics

Workerʼs
characteristics
Task
characteristics

When w j  x i  Thresholdthe worker answers 1
22Welinder et al. The Multidimensional Wisdom of Crowds. NIPS 2010.

KYOTO UNIVERSITY

Further Extension of the Latent Class Model:
Introducing Workers’ Confidence Asking workers about confidence in their answers as well
– In general, if a worker is more confidence about her answer, it is moreprobably correct Overconfident/underconfident workers
 A probabilistic model that considers the differences among workers in theiraccuracy of confidence judgments
Workers Confidence Answer
Is thisa bird?

Requester

70%

Yes

60%

Yes

100%

No

et al. Utilizing Workers' Self‐reported Confidence to Integrate
23 Oyama
Multiple Crowdsourced Labels. IJCAI 2013

KYOTO UNIVERSITY

Sensing by Crowdsourcing:
A Human as a Sensor
 Crowd sensing/participatory sensing– Data collection framework considering a human as a sensor– Data collection involves human judgment•

Simply collecting data from a sensor attached to a human without
any human intervention is not called crowd sensing Example of crowd sensing:– CreekWatch (IBM)：Monitoring water pollution using cell phones– CarTel (MIT)：Monitoring traffic jams using data collected from cars
– Noricell (MS)：Monitoring traffic noise and road surface using cellphones
24

KYOTO UNIVERSITYExample of Crowdsourcing for Datafication:
Turning Legacy Open Data Machine‐Readable
 Published data that are not always readily reusable Data charts are often designed to be understood by people, notby computers

Embedded chart in animage format

25

KYOTO UNIVERSITYExample of Crowdsourcing for Datafication:
Extracting Data from Chart Image Ask workers to visually reproduce a chart image
in a spreadsheet
Hidden purpose:
extract data from image

Apparent purpose:
reproduce chart in aspreadsheet

26

KYOTO UNIVERSITY

Using Data Labeled by Crowdsourcing in Supervised
Machine Learning Supervised learning requires training data
– Input‐output (gold answer) pairs
 Using crowdsourcing to collect training data
• NLP: Web page categorization, information extraction• Image processing: Image tagging for retrieval, object
recognition
TokyoTower

27

http://en.wikipedia.org/wiki/Tokyo_Tower
http://en.wikipedia.org/wiki/Eiffel Tower

EiffelTower

KYOTO UNIVERSITY

Supervised Learning: Learning a Prediction Modelfrom Input‐Output Pairs
 Training data are given as input-output pairs{(xi, yi)}i=1,...,N Estimate the modelyi ≒ f (xi)that explains the input-output relation

28

KYOTO UNIVERSITY

Learning from Crowdsourced Data:
Using Estimated True Answers
 Obtain (possibly incorrect) answers from multipleworkers{ (xi, yi,j) }i=1,...,N j=1,...,M(i)– j：worker id
1. Estimate the true answers from workersʼ
answers by using a quality control method suchas the Latent Class model
2. Learn a prediction model by using estimatedanswers as the true answers
29

KYOTO UNIVERSITY

Leaning from Crowdsourced Labels:Learning aPrediction Model Directly from Worker Labels
 Difference from quality control：Main objective is obtaining aprediction model rather than true answers
 Answers, worker models, and the prediction model are
estimated by using the EM algorithm
Prediction
modelTrueanswer
Input fx

yDifference fromquality control

Worker models

1
2
3

Workerʼs answers

１１０
Observedanswers

Workerʼs probability ofanswering correctly
Raykar et al. Learning from Crowds. JMLR, 2010
KYOTO
30 Kajino, Tsuboi, Kashima. Convex Formulations of Learning from Crowds. AAAI,
2012 UNIVERSITY

Summary: Crowdsourcing for Datafication
 Gamification– Output agreement, input agreement
 Quality control by introducing redundancy– Latent class model– Extension to utilize problem difficulty, worker expertize, confidence Examples of datafication– Crowd sensing– Digitizing legacy data Learning a prediction model from crowds

31

KYOTO UNIVERSITY