許永真臺灣大學：資訊工程學研究所何建儒Ho, Chien-JuChien-JuHo2007-11-262018-07-052007-11-262018-07-052007http://ntur.lib.ntu.edu.tw//handle/246246/54094儘管近幾十年來，電腦科學有相當長足的發展，還是有一些問題沒辦法用電腦有效的解決。像是圖形辨識(image recognition)或是常識推理(common sense reasoning)，這些對於人類來說相當容易的問題，目前為止卻沒有一個很好的方法可以用電腦自動的解決。這篇論文嘗試利用遊戲來向玩家收集資訊，並且進一步利用這些資訊來解決電腦難以處理的問題。 為了達成這個目的，我們設計了一個多人網路線上遊戲 PhotoSlap 來幫助我們將相同人的照片群聚(cluster)起來。利用 PhotoSlap 所產生出來的資訊，我們可以進一步達成照片標註(photo annotation)。過去也有一些研究利用遊戲來收集照片註解，這篇論文主要的不同點在於：利用賽局理論對遊戲設計進行了分析，並且證明了這樣的遊戲設計會符合subgame perfect equilibrium，也就是說只要是理性想得高分的玩家，便會貢獻出正確的資訊。最後我們請了四組焦點團體(focus group)來進行實驗，實驗結果驗證了遊戲設計的合理性，以及所獲得資料的正確性。Despite impressive advancement in computer technology, there are still limitations on the capabilities of computers. Tasks like image recognition or common sense reasoning are trival for humans, but present challenges on even the fastest computer today. This thesis aims to explore the power of human Computation and shows how human brain powers can be utilized to solve problems that are hard for computers. A multi-player online game, PhotoSlap, is designed to achieve the task of semantic clustering and therefore accomplishes photo annotation. This research extends human computation research in incentive analysis with a game theoretic approach. In particular, PhotoSlap can be shown to reach emph{subgame perfect equilibrium} with the target strategy when players are rational and not collusive. Experiments involving four focus groups have been conducted, and the preliminary results demonstrated the game design to be reasonable and therefore produce useful information.Acknowledgments ii Abstract iii List of Figures x List of Tables xii Chapter 1 Introduction 1 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Problem and Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4 Thesis Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Chapter 2 Related Work 5 2.1 Knowledge Collection . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.1 Expert Annotation . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.2 Mass Collaboration . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Human Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.1 The ESP Game . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.2 Peekaboom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.3 Other Applications . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Mechanism Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3.1 Basic Definitions of Game Theory . . . . . . . . . . . . . . . . . 10 2.3.2 Extensive Game . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3.3 Solution Concept . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Chapter 3 Semantic Clustering Algorithm 15 3.1 Semantic Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.1.1 Face Photo Clustering . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.3 Proposed Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.3.1 Human Algorithm: The PhotoSlap Game . . . . . . . . . . . . . 18 3.3.2 Strategy Analysis: A Game Theoretic Approach . . . . . . . . . 18 Chapter 4 Human Algorithm Design 19 4.1 A Productivity Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.2 Game Mechanism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.2.1 Game Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.2.2 Scoring Mechanism . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2.3 Intuition Behind the Game Rules . . . . . . . . . . . . . . . . . . 22 Chapter 5 Strategy Analysis 23 5.1 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 5.2 The Modeling of PhotoSlap . . . . . . . . . . . . . . . . . . . . . . . . . 24 5.3 Subgame Perfect Equilibrium . . . . . . . . . . . . . . . . . . . . . . . . 26 5.3.1 The subgame in which player 3 is the root . . . . . . . . . . . . . 26 5.3.2 The subgame in which player 2 is the root . . . . . . . . . . . . . 29 5.3.3 The subgame in which player 1 is the root . . . . . . . . . . . . . 30 5.4 Multiple Equilibria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Chapter 6 Evaluation 33 6.1 Experiment Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 6.2 How Good Is The Game Strategy . . . . . . . . . . . . . . . . . . . . . . 33 6.3 Is The Game Fun . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 6.4 Is The Game Productive . . . . . . . . . . . . . . . . . . . . . . . . . . 36 6.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 Chapter 7 Application: PhotoSlap Annotation System 37 7.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 7.2 PhotoSlap Annotation System . . . . . . . . . . . . . . . . . . . . . . . 38 7.2.1 Semi-automatic Face Detection . . . . . . . . . . . . . . . . . . 39 7.2.2 PhotoSlap Game . . . . . . . . . . . . . . . . . . . . . . . . . . 39 7.2.3 Bulk Annotation Tool . . . . . . . . . . . . . . . . . . . . . . . 42 Chapter 8 Conclusion 43 8.1 Summary of Contributions . . . . . . . . . . . . . . . . . . . . . . . . . 44 8.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Bibliography 471383968 bytesapplication/pdfen-US賽局理論人機協力演算法照片標註human algorithmgame theory,photo annotationthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/54094/1/ntu-96-R94922053-1.pdf