In statistics, the optimistic knowledge gradient is a smart decision-making strategy developed by Xi Chen, Qihang Lin and Dengyong Zhou in 2013 to help solve complex problems in crowdsourced data labeling (a form of optimal computing budget allocation problem). In crowdsourcing, multiple people are asked to label or classify data, but each labeling attempt comes with a cost. The main challenge is figuring out the most efficient way to allocate resources when you want to get the most accurate labels without spending too much money. Imagine you're running a project where you need to classify thousands of images, and each person you ask to label an image charges a fee. The optimistic knowledge gradient helps you determine the most cost-effective way to get the most reliable labels by strategically choosing which items to have labeled and by whom. This approach is particularly useful in machine learning and data science, where getting accurate labeled data is crucial but can be expensive. By using mathematical techniques, the method tries to maximize the information gained while minimizing the overall cost of labeling.
Motivation The optimal computing budget allocation problem is formulated as a Bayesian Markov decision process(MDP) and is solved by using the dynamic programming (DP) algorithm where the Optimistic knowledge gradient policy is used to solve the computationally intractable of the dynamic programming (DP) algorithm. Consider a budget allocation issue in crowdsourcing. The particular crowdsourcing problem we considering is crowd labeling. Crowd labeling is a large amount of labeling tasks which are hard to solve by machine, turn out to easy to solve by human beings, then we just outsourced to an unidentified group of random people in a distributed environment.
Methodology We want to finish this labeling tasks rely on the power of the crowd hopefully. For example, suppose we want to identify a picture according to the people in a picture is adult or not, this is a Bernoulli labeling problem, and all of us can do in one or two seconds, this is an easy task for human being. However, if we have tens of thousands picture like this, then this is no longer the easy task any more. That's why we need to rely on crowdsourcing framework to make this fast. Crowdsourcing framework of this consists of two steps. Step one, we just dynamically acquire from the crowd for items. On the other sides, this is dynamic procedure. We don't just send out this picture to everyone and we focus every response, instead, we do this in quantity. We are going to decide which picture we send it in the next, and which worker we are going to hire in the crowd in the next. According to his or her historical labeling results. And each picture can be sent to multiple workers and every worker can also work on different pictures. Then after we collect enough number of labels for different picture, we go to the second steps where we want to infer true label of each picture based on the collected labels. So there are multiple ways we can do inference. For instance, the simplest we can do this is just majority vote. The problem is that no free lunch, we have to pays for worker for each label he or she provides and we only have a limited project budget. So the question is how to spend the limited budget in a smart way.
Challenges Before showing the mathematic model, the paper mentions what kinds of challenges we are facing.
Challenge 1 First of all, the items have a different level of difficulty to compute the label, in a previous example, some picture are easy to classify. In this case, you will usually see very consistent labels from the crowd. However, if some pictures are ambiguous, people may disagree with each other resulting in highly inconsistent labelling. So we may allocate more resources on this ambiguous task.
Challenge 2 And another difficulty we often have is that the worker are not perfect, sometimes this worker are not responsible, they just provide the random label, therefore, of course, we would not spend our budget on this no reliable workers. Now the problem is both the difficulty of the pictures and the reliability of the worker we completely unknown at the beginning. We can only estimate them during the procedure. Therefore, we are naturally facing to exploration and exploitation, and our goal is to give a reasonable good policy to spend money to the right way–maximize the overall accuracy of final inferred labels.
… excerpt ends here. Continue reading the full article.
