Recommender Systems and Information Fusion in Spatial Crowdsourcing Pubblico

Abstract

Spatial Crowdsourcing (SC) refers to a series of data collection mechanisms where a set of users with a sensing or computing device are asked to perform a set of tasks at different locations and times. In this work, we explore some of the challenges that arise with SC and propose some solutions. These challenges concern a proper recommendation of tasks to users in such a way that they maximize their expected utility while at the same time maximizing the probability that all the tasks are performed. The utility for the users can be based on the tasks the expected reward they are planning to obtain, and the distance to the assignments. These aspects can be predicted through tensor-factorization techniques. A high-paying assignment might be far from a user, while a low paying assignment is nearby. Depending on the users’ preference, we seek to recommend a set of tasks that maximize the user’s utility. On the other hand, we also want to maximize the sum of probabilities that the tasks are performed, considering the interdependencies between users. We define the system utility as a convex linear combination of the user and the task utility and suggest approximation methods to recommend the tasks that yield the highest system utility.

We also deal with the problem of truth inference, which focuses on integrating the responses from a mobile crowdsourcing scenario and determining the true value. Many times, the answers from a mobile crowdsourcing scenario are noisy, contradicting, or have missing values. We developed a recursive Bayesian system that updates the reputation model of the users, the probability that the users were in the correct time and location, and the probability that the events are true. We further enhanced this algorithm using a Kalman filter that predicts the true state of the event at each time-stamp using a hidden event model and which is updated with the reports from the users. Our method was compared against the naive majority voting method as well as other state-of-the-art truth inference algorithms and our method shows a considerable improvement. 

Table of Contents

1 Introduction                                              1

1.1 Motivation.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  1

1.2 Recommender Systems in Spatial Crowdsourcing . . . . . . . . 4

1.2.1 CurrentChallenges . . . . . . . . . . . . . . . . . . . . .  4

1.2.2 ExistingSolutionsandLimitations . . . . . . . . . . . . . . . 5

1.2.3 Frameworkofproposedsolution . . . . . . . . . . . . . . . . . 6

1.3 TruthInferenceinSpatialCrowdsourcing. . . . . . . . . . . . . . . . . . 7

1.3.1 CurrentChallenges . . . . . . . . . . . . . . . . . . . . .  8

1.3.2 ExistingSolutionsandLimitations . . . . . . . . . . . . . . .  8

1.3.3 Frameworkofproposedsolution . . . . . . . . . . . . . . . . .  8

1.4 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2 Related Work                                             13

2.1 SpatialCrowdsourcing . . . . . . . . . . . . . . . . . . . . . . . . 13

   2.1.1 Classification of Tasks . . . . . . . . . . . . . . . . . . . . . 13

   2.1.2 Classification of Distribution Models . . . . . . . . . . . . . . . 16

2.2 Recommender Systems in Spatial Crowdsourcing . . . . . . . . 19

   2.2.1 Taskrecommendations . . . . . . . . . . . . . . . . . . . . .  20

   2.2.2 Taskprediction . . . . . . . . . . . . . . . . . . . . . . . . . .  21

2.3 TruthInferenceAlgorithms . . . . . . . . . . . . . . . . . . . . . . 22

        2.3.1 General Classification of Truth Inference Algorithms . . 22

        2.3.2 Truth Inference in Spatio-temporal Scenarios . . . . . . . . . 22

3 Recommender Systems in Spatial Crowdsourcing                 25

   3.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . .  25

     3.1.1 Users’pointofview . . . . . . . . . . . . . . . . . . . . . . . . . . 25

     3.1.2 Tasks’pointofview . . . . . . . . . . . . . . . . . . . . . . . . . . 26

     3.1.3 System’spointofview . . . . . . . . . . . . . . . . . . . . . . . .  27

   3.2 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

     3.2.1 IndividualUtilityFunction . . . . . . . . . . . . . . . . . . . . . . 29

     3.2.2 Independent probability of performing a task . . . . . . . . . . . 30

     3.2.3 Dependent probability of performing a task . . . . . . . . . . . . . 31

     3.2.4 Probability that a task is performed. . . . . . . . . . . . . . . . . . . . . 32

   3.3 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32

     3.3.1 Depth First Search Algorithm . . . . . . . . . . . . . . . . . . . . .32

     3.3.2 GreedyAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . .33

     3.3.3 ProgressiveAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 34

     3.3.4 HybridApproaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

   3.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

     3.4.1 Evaluation Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

     3.4.2 Simulation experiments . . . . . . . . . . . . . . . . . . . . . . .  42

     3.4.3 Case study. . .  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .43

   3.5 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  52

     3.5.1 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . .  52

     3.5.2 Case Study Results . . . . . . . . . . . . . . . . . . . . . . . . . . . .  53

4 Location and Time-aware Truth-Inference with Bayesian Filtering       63

   4.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

     4.1.1 Proposed Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

   4.2 Truth-Inference Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . .  70

     4.2.1 Bayesian Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

     4.2.2 Kalman Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

   4.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  80

     4.3.1 Compared Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

     4.3.2 Real-World Case Study. . . . . . . . . . . . . . . . . . . . . . . . . . . 82

     4.3.3 Evaluation metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  84

     4.3.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

     4.3.5 Simulation Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . .  85

5 Conclusion 93

   5.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  93

   5.2 Recommender Systems in Spatial Crowdsourcing . . . . . . . . . . . . . . . . 94

   5.3 Truth Inference in Spatial Crowdsourcing. . . . . . . . . . . . . . . . . . . . . . . . . 96

   5.4 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  97

Appendix                                                        100

   6.1 Tighter Bounds for User and TaskUtilities . . . . . . . . . . . . . . . . . . .  100

Bibliography                                                     102 

About this Dissertation

Rights statement

• Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.

School	Laney Graduate School
Department	Computer Science and Informatics
Degree	Ph.D.
Submission	Dissertation
Language	English
Research Field	Information Technology
Parola chiave	Crowdsourcing Recommender systems Truth inference
Committee Chair / Thesis Advisor	Sunderam, Vaidy, Emory University Xiong, Li, Emory University
Committee Members	Ho, Joyce, Emory University Jiang, Xiaoqian, University of California, San Diego

Ultima modifica

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Recommender Systems and Information Fusion in Spatial Crowdsourcing ()	2017-12-15 01:02:45 -0500	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions