So Who Won: Dynamic Max Discovery with the Crowd
展开查看详情
1. So Who Won: Dynamic Max Discovery with the Crowd Assma Boughoula
2. Mo=va=on Which ki?en is cutest? Which dog is largest?
3. Problem Statement • Set O of n objects {o1, …, on} • Each oi has quality ci • π : permuta=on or ranking of O • If π(i) < π(j) then oi is ranked higher than oj and ci>cj • W : n x n matrix of votes from workers • Assump=ons: – ci ≠ cj for all i ≠ j – Workers can only compare a pair of objects • Goal: arrive at the correct permuta=on π quickly and efficiently
4. Framework • Two sub-problems Es-mate Max Which pairs with current to compare informa-on next?
5. Framework Es-mate Max Which pairs with current to compare informa-on next? Judgment Problem Next Votes Problem
6. Outline • Judgment Problem • Next Votes Problem – Maximum Likelihood – Maximum Likelihood (ML) baseline (ML) baseline – Heuris=c Strategies – Heuris=c Vote • Indegree Selec=on Strategies • Local • Paired • PageRank • Max • Itera=ve • Greedy • Round Robin
7.Judgment Problem A B C D A B C D
8. Judgment Problem Maximum Likelihood • Average worker accuracy p is known • Calculate P(πd|W) for each permuta=on πd • Choose most probable permuta=on In example: (D, C, B, A) (C, D, B, A) • There are n! possible permuta=ons!!! Exhaus=ve, inefficient
9. Judgment Problem Kemeny permuta-on: • Minimizes number of edges i-j that don’t respect ranking. • (D, C, B, A)
10. Judgment Problem Indegree Strategy • For each node i, look at all neighbors j: • Calculate score: s(i)= P(i<j |wij,wji) • Choose max s(i) Only considers neighbors, not whole W
11. Judgment Problem Local Strategy • Considers “neighbors of neighbors” • wins(i) = Σjwji losses(i) = Σjwij • s(i) = wins(i) – losses(i) + Σj:ci>cjwins(j) - Σj:ci<cjlosses(j) Reward Penalty
12. Judgment Problem PageRank Strategy • Considers whole graph • S(i) = PageRank(i) • Prt+1(i) =Σjwji prt(j)/outdeg(j) • Pr0(i) = 1/n
13. Judgment Problem Itera-ve Strategy • dif(i) = wins(i)– losses(i) • Eliminate lower half of objects according to dif(i) scores • Repeat with remaining objects
14. Judgment Problem Itera-ve Strategy Iter1: dif(A)=-2, dif(B)=-4, dif(C)=1, dif(D)=3 Iter2: dif(C)=0, dif(C)=0
15. Judgment Problem p=0.75 p=0.95
16. Framework Es-mate Max Which pairs with current to compare informa-on next? Judgment Problem Next Votes Problem
17. Next Votes Problem Some Nota=on… • Budget b = # votes to be requested • Poten=al vote {oi, oj} • Q = {{oi, oj},…} possible mul=set of b votes • Answer tuple ({oi, oj}, ox) • Answer mul=set a={({oi, oj}, ox),…} • 2b possible answer mul=sets for each Q !!! • a∧W : updated W matrix
18. Next Votes Problem Maximum Likelihood • Look for Q such that a∧W increases our confidence when es=ma=ng the max the most. • Choose Q that maximizes: ΣamaxiP(i is max, a∧W ) • Assumes average worker accuracy p known
19. Next Votes Problem Paired Vote Selec-on • Order objects by score s(i) from judgment problem b = 2 Q = (A,B), (E,D) (A, B, E, D, C, F)
20. Next Votes Problem Max Vote Selec-on • Compare with current max b = 2 Q = (A,B), (A,E) (A, B, E, D, C, F)
21. Next Votes Problem Greedy Vote Selec-on • Sort objects by s(i) • s(i) x s(j) for each pair (i,j) • Select b pairs with highest s(i) x s(j) (A, B, E, D, C, F) S=(1,1,0,0,-1,-1) ((A,B),(A,E),(A,D),(B,E)…)
22. Next Votes Problem Complete (Round Robin) Vote Selec-on • K = size of tournament b=6 K=3 (A, B, E, D, C, F) S=(1,1,0,0,-1,-1) ((A,B),(A,E),(B,E),(A,D),(B,D),(E,D))
23.Next Votes Problem
24. Recap Es-mate Max Which pairs with current to compare informa-on next? Judgment Problem Next Votes Problem
25. Recap • Judgment Problem • Next Votes Problem – Maximum Likelihood – Maximum Likelihood (ML) baseline (ML) baseline – Heuris=c Strategies – Heuris=c Vote • Indegree Selec=on Strategies • Local • Paired • PageRank • Max • Itera-ve • Greedy • Round Robin