請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/50472完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 陳光禎(Kwang-Cheng Chen) | |
| dc.contributor.author | Hsiang Hsu | en |
| dc.contributor.author | 徐祥 | zh_TW |
| dc.date.accessioned | 2021-06-15T12:42:11Z | - |
| dc.date.available | 2018-08-02 | |
| dc.date.copyright | 2016-08-02 | |
| dc.date.issued | 2016 | |
| dc.date.submitted | 2016-07-27 | |
| dc.identifier.citation | [1] A. Stimson, “The longitude problem: The navigator’s story,” The Quest for Longitude, The Collection of Historical Scientific Instruments, 2nd ed., Harvard University, Cambridge, MA, pp. 72–84, 1998.
[2] J. Howe, “The rise of crowdsourcing,” Wired magazine, vol. 14, no. 6, pp. 1–4, 2006. [3] F. Khatib, F. DiMaio, S. Cooper, M. Kazmierczyk, M. Gilski, S. Krzywda, H. Zabranska, I. Pichova, J. Thompson, Z. Popović, et al., “Crystal structure of a monomeric retroviral protease solved by protein folding game players,” Nature structural & molecular biology, vol. 18, no. 10, pp. 1175–1177, 2011. [4] F.-Y. Wang, “Parallel control and management for intelligent transportation systems: Concepts, architectures, and applications,” vol. 11, no. 3, pp. 630–638, 2010. [5] Broad of Innovation, “List of open innovation crowdsourcing,” 2016. [6] A. Vempaty, L. R. Varshney, and P. K. Varshney, “Reliable crowdsourcing for multi-class labeling using coding theory,” vol. 8, no. 4, pp. 667–679, 2014. [7] D. R. Karger, S. Oh, and D. Shah, “Budget-optimal task allocation for reliable crowdsourcing systems,” Operations Research, vol. 62, no. 1, pp. 1–24, 2014. [8] D. Acemoglu, M. Mostagir, and A. Ozdaglar, “Managing innovation in a crowd,” tech. rep., National Bureau of Economic Research, 2014. [9] D. R. Karger, S. Oh, and D. Shah, “Iterative learning for reliable crowdsourcing systems,” in Proc. NIPS, pp. 1953–1961, 2011. [10] D. R. Karger, S. Oh, and D. Shah, “Efficient crowdsourcing for multi-class labeling,” in Proc. ACM SIGMETRICS Int. Conf. Meas. Model. Comput. Syst., pp. 81–92, Jun. 2013. [11] W. Wang and Y. Jiang, “Multiagent-based allocation of complex tasks in social networks,” vol. 3, no. 4, pp. 571–584, 2015. [12] V. C. Raykar, S. Yu, L. H. Zhao, G. H. Valadez, C. Florin, L. Bogoni, and L. Moy, “Learning from crowds,” J. Mach. Learn. Res., vol. 11, pp. 1297–1322, 2010. [13] D. DiPalantino, T. Karagiannis, and M. Vojnovic, “Individual and collective user behavior in crowdsourcing services,” tech. rep., Microsoft Research, Jun. 2011. [14] D. C. Brabham, “Crowdsourcing as a model for problem solving an introduction and cases,” Convergence: the international journal of research into new media technologies, vol. 14, no. 1, pp. 75–90, 2008. [15] Wikipedia, “Wikipedia:Good article statistics,” 2016. [16] H. Li, B. Yu, and D. Zhou, “Error rate bounds in crowdsourcing models,” arXiv preprint arXiv:1307.2674, 2013. [17] R. Elsässer and T. Sauerwald, “Tight bounds for the cover time of multiple random walks,” in Automata, Languages and Programming, pp. 415–426, Springer, 2009. [18] P. Winkler and D. Zuckerman, “Multiple cover time,” Random Structures Algorithms, vol. 9, no. 4, pp. 403–411, 1996. [19] F. R. Chung, Spectral graph theory, vol. 92. American Mathematical Soc., 1997. [20] A. K. Chandra, P. Raghavan, W. L. Ruzzo, R. Smolensky, and P. Tiwari, “The electrical resistance of a graph captures its commute and cover times,” Computational Complexity, vol. 6, no. 4, pp. 312–340, 1996. [21] A. Krause and D. Golovin, “Submodular function maximization,” Tractability: Practical Approaches to Hard Problems, vol. 3, p. 19, 2012. [22] C. Cooper and A. Frieze, “The cover time of random regular graphs,” SIAM Journal on Discrete Mathematics, vol. 18, no. 4, pp. 728–740, 2005. [23] C. Cooper and A. Frieze, “The cover time of sparse random graphs,” Random Structures & Algorithms, vol. 30, no. 1, pp. 1–16, 2007. [24] C. Cooper and A. Frieze, “The cover time of the giant component of a random graph,” Random Structures & Algorithms, vol. 32, no. 4, pp. 401–439, 2008. [25] C. Cooper and A. Frieze, “The cover time of the preferential attachment graph,” Journal of Combinatorial Theory, Series B, vol. 97, no. 2, pp. 269–290, 2007. [26] M. T. Barlow, J. Ding, A. Nachmias, and Y. Peres, “The evolution of the cover time,” Combinatorics, Probability and Computing, vol. 20, no. 03, pp. 331–345, 2011. [27] M. Chupeau, O. Bénichou, and R. Voituriez, “Cover times of random searches,” Nature Physics, 2015. [28] M. Chupeau, O. Bénichou, and R. Voituriez, “Mean cover time of one-dimensional persistent random walks,” Physical Review E, vol. 89, no. 6, p. 062129, 2014. [29] O. Bénichou, C. Loverdo, M. Moreau, and R. Voituriez, “Intermittent search strategies,” Reviews of Modern Physics, vol. 83, no. 1, p. 81, 2011. [30] C. Cooper, A. Frieze, and T. Radzik, “Multiple random walks in random regular graphs,” SIAM Journal on Discrete Mathematics, vol. 23, no. 4, pp. 1738–1761, 2009. [31] R. Elsässer and T. Sauerwald, “Tight bounds for the cover time of multiple random walks,” Theoretical Computer Science, vol. 412, no. 24, pp. 2623–2641, 2011. [32] J. Kahn, J. H. Kim, L. Lovasz, and V. H. Vu, “The cover time, the blanket time, and the matthews bound,” in Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on, pp. 467–475, IEEE, 2000. [33] A. Ghosh, S. Boyd, and A. Saberi, “Minimizing effective resistance of a graph,” SIAM review, vol. 50, no. 1, pp. 37–66, 2008. [34] S. M. Ross et al., Stochastic processes, vol. 2. John Wiley & Sons New York, 1996. [35] D. M. Cvetkovic, M. Doob, and H. Sachs, “Spectra of graphs. theory and application,” 1980. [36] L. Lovász, “Submodular functions and convexity,” in Mathematical Programming The State of the Art, pp. 235–257, Springer, 1983. [37] R. Kondor and J. Lafferty, “Diffusion kernels on graphs and other discrete structures,” in Proc. Int. Conf. on Machine Learning, pp. 315–322, 2002. [38] A. J. Smola and B. Schölkopf, Learning with kernels. Citeseer, 1998. [39] A. J. Smola and R. Kondor, “Kernels and regularization on graphs,” in Learning theory and kernel machines, pp. 144–158, Springer, 2003. [40] L. Lovász et al., “Random walks on graphs: A survey,” Combinatorics, Paul Erdos is Eighty, vol. 2, pp. 353–398, 1996. [41] M. Newman, Networks: an introduction. OUP Oxford, 2010. [42] J. Leskovec, D. P. Huttenlocher, and J. M. Kleinberg, “Governance in social media: A case study of the wikipedia promotion process.,” in Proc. International Conference on Web and Social Meida (ICWSM), 2010. [43] D. Aldous and J. Fill, “Reversible markov chains and random walks on graphs,” 2002. [44] U. Feige, “A tight upper bound on the cover time for random walks on graphs,” Random Structures & Algorithms, vol. 6, no. 1, pp. 51–54, 1995. [45] P. Matthews, “Covering problems for brownian motion on spheres,” The Annals of Probability, pp. 189–199, 1988. [46] S. Ermon, C. P. Gomes, A. Sabharwal, and B. Selman, “Taming the curse of dimensionality: Discrete integration by hashing and optimization,” arXiv preprint arXiv: 1302.6677, 2013. [47] S. Boyd and L. Vandenberghe, Convex optimization. Cambridge university press, 2004. [48] D. Kempe, J. Kleinberg, and É. Tardos, “Maximizing the spread of influence through a social network,” in Proc. ACM SIGKDD international conference on Knowledge discovery and data mining, 2003. [49] A. Krause, A. Singh, and C. Guestrin, “Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies,” Journal of Machine Learning Research, vol. 9, no. Feb, pp. 235–284, 2008. [50] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, “An analysis of approximations for maximizing submodular set functions—i,” Mathematical Programming, vol. 14, no. 1, pp. 265–294, 1978. [51] I. H. Dinwoodie et al., “A probability inequality for the occupation measure of a reversible markov chain,” The Annals of Applied Probability, vol. 5, no. 1, pp. 37–43, 1995. [52] M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey, “An analysis of approximations for maximizing submodular set functions—ii,” in Polyhedral combinatorics, pp. 73–87, Springer, 1978. [53] G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák, “Maximizing a submodular set function subject to a matroid constraint,” in International Conference on Integer Programming and Combinatorial Optimization, pp. 182–196, Springer, 2007. [54] R. Jain, D.-M. Chiu, and W. R. Hawe, A quantitative measure of fairness and discrimination for resource allocation in shared computer system, vol. 38. Eastern Research Laboratory, Digital Equipment Corporation Hudson, MA, 1984. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/50472 | - |
| dc.description.abstract | 群眾外包是社群與網路科學中新崛起的科技，然而現存的研究大多不考慮群眾工作者自由選擇想處理的子任務對一個群眾外包系統的效能與子任務品質的影響。本篇論文考慮這個社群網路中的基本現象，並將此概念抽象化成在圖上的隨機漫步，因此，群眾外包系統的效能就是圖的平均覆蓋時間 (mean cover time)，而子任務的品質則可由佔用測度 (occupation measure) 來描述。藉此，我們提出最佳子任務管理與推薦問題，也就是利用連結子任務，在滿足子任務品質與成本限制下最佳化系統的效率。這個最佳子任務管理與推薦問題也可被視為圖上的有效資源分配問題。利用光譜圖論 (Spectral graph theory) 與次模集合函數 (Submodular set function) 優化理論，我們提出了清晰簡潔且運算可行的方法論來解決這個問題，並利用數值模擬與真實數據驗證了它們的正確性與效率。這個方法論在其他眾多領域，如：網路中的搜尋與導航、資源獲取、感測器規畫問題等也具有廣泛的應用。 | zh_TW |
| dc.description.abstract | Crowdsourcing has been an emerging technology in social and network science. Existing researches, however, often neglect the underlying tasks selection process of crowd workers, and how it effects the efficiency and tasks quality of a crowdsourcing system. In this thesis, we consider and formulate this fundamental phenomenon as random walks over graphs; Hence, the efficiency and quality are connected to the mean cover time and occupation measure on graphs respectively. We propose the optimal tasks management and recommendation problem, which could be viewed as a resource allocation problem over graphs, and aim at reducing the mean cover time while satisfying some quality constraints {it via} adding edges efficiently among tasks. Exploiting graph spectrum and submodular set function optimization, elegant and computationally efficient methodologies are proposed to implement such systems, together with illustrative verification from numerical results and data of real crowdsourcing systems. This methodology could be applied to numerous applications in other fields, including network searching and navigation, resource harvesting, sensor distributing problems, etc.. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T12:42:11Z (GMT). No. of bitstreams: 1 ntu-105-R03942046-1.pdf: 3041563 bytes, checksum: 4585d799ef715c9ad225c36ed93879e9 (MD5) Previous issue date: 2016 | en |
| dc.description.tableofcontents | 1 Introduction 1
1.1 Crowdsourcing - Historical Background and Unsolved Problems . . . . . 1 1.2 Related Works on Cover Time . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Preliminaries 6 2.1 Markov Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Spectral Graph Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Submodularity and Submodular Function Maximization (SFM) . . . . . . 8 2.4 Graph Kernel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.4.1 Algebra on Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.4.2 Random Walk Graph Kernels . . . . . . . . . . . . . . . . . . . 11 v2.5 Limiting Behaviours of Cover Time . . . . . . . . . . . . . . . . . . . . 13 2.5.1 Complete Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.5.2 Erdぴos-R´enyi (ER) random graph and Regular Graphs . . . . . . . 14 3 Problem Formulation 18 3.1 Graphical Model for Micro-tasks . . . . . . . . . . . . . . . . . . . . . . 18 3.2 Unreliable Crowd Workers and Task Selection Process . . . . . . . . . . 19 3.3 Task Selection as Random Walks on Graphs . . . . . . . . . . . . . . . . 22 3.4 Spectral Graph Theory for Mean Hitting Time . . . . . . . . . . . . . . . 27 3.5 Efficiency Optimization Problem for (G, K, T, ‾p) Crowdsourcing Sys- tems Under Quality Constraints . . . . . . . . . . . . . . . . . . . . . . . 29 4 Optimal Tasks Management for Quality-Guaranteed Crowdsourcing Systems 33 4.1 Submodularity of Mean Cover Time . . . . . . . . . . . . . . . . . . . . 33 4.2 Worst-Case Quality-Guaranteed Crowdsourcing . . . . . . . . . . . . . . 38 4.3 Fair Quality-Guaranteed Crowdsourcing . . . . . . . . . . . . . . . . . . 39 5 Experiments 46 5.1 Some Properties of Mean Cover Time . . . . . . . . . . . . . . . . . . . 46 5.2 Worst-Case Quality-Guaranteed Crowdsourcing . . . . . . . . . . . . . . 51 5.3 Fair Quality-Guaranteed Crowdsourcing . . . . . . . . . . . . . . . . . . 53 5.4 Wikipedia Data Experiments . . . . . . . . . . . . . . . . . . . . . . . . 57 6 Conclusion and Future Works 62 References 64 | |
| dc.language.iso | en | |
| dc.subject | 群眾外包 | zh_TW |
| dc.subject | 光譜圖論 | zh_TW |
| dc.subject | 光譜圖論 | zh_TW |
| dc.subject | 次模集合函數 | zh_TW |
| dc.subject | 圖優化 | zh_TW |
| dc.subject | 次模集合函數 | zh_TW |
| dc.subject | 群眾外包 | zh_TW |
| dc.subject | 圖優化 | zh_TW |
| dc.subject | graph optimization | en |
| dc.subject | spectral graph theory | en |
| dc.subject | submodular set function | en |
| dc.subject | graph optimization | en |
| dc.subject | crowdsourcing | en |
| dc.subject | spectral graph theory | en |
| dc.subject | submodular set function | en |
| dc.subject | crowdsourcing | en |
| dc.title | 圖上的有效資源分配 - 群眾外包 | zh_TW |
| dc.title | Efficient Resource Allocation on Graphs - Crowdsourcing | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 104-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 楊谷章(Guu-Chang Yang),林守德(Shou-De Lin),林嘉慶(Jia-Chin Lin),鄭欣明(Shin-Ming Cheng) | |
| dc.subject.keyword | 群眾外包,圖優化,次模集合函數,光譜圖論, | zh_TW |
| dc.subject.keyword | crowdsourcing,graph optimization,submodular set function,spectral graph theory, | en |
| dc.relation.page | 68 | |
| dc.identifier.doi | 10.6342/NTU201601419 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2016-07-27 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電信工程學研究所 | zh_TW |
| 顯示於系所單位： | 電信工程學研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-105-1.pdf 未授權公開取用 | 2.97 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。