學術產出-Theses
Article View/Open
Publication Export
-
題名 霍奇排名之理論分析
Theoretic Aspect of HodgeRank作者 陳名秀
Chen, Ming Hsiu貢獻者 蔡炎龍
Tsai, Yen Lung
陳名秀
Chen, Ming Hsiu關鍵詞 霍奇理論
霍奇排名
組合霍奇理論
HodgeRank
Combinatorial Hodge theorem
Ombinatorial Hodge decomposition日期 2016 上傳時間 5-Apr-2017 15:36:35 (UTC+8) 摘要 霍奇排名是在近幾年才運用在排名的一種方法。在大多數現在的資料庫 中,資料庫很龐大,有些甚至會需要網路連結,而且很多會有資料不完整或 是資料不平衡的狀況。我們選擇用霍奇排名這種排名方法來處理可能會遇到 的這些困擾。這篇論文主要目的是想用運用基本的線性代數來研究霍奇排名和推導組合霍奇理論。
HodgeRank is a method of ranking that is new in recent years. In most of modern datasets, the amount of data is very large, some also need the internet connection, and plenty of them have the feature that incomplete or imbalanced. We use the method of HodgeRank to deal with these difficulties.This thesis is primary using elementary linear algebra to survey HodgeRank and deduce the combinatorial Hodge Theorem.參考文獻 [1] Kenneth J. Arrow. A difficulty in the concept of social welfare. Journal of Political Economy, 58(4):328–346, 1950.[2] Ralph Allan Bradley and Milton E. Terry. Rank analysis of incomplete block designs. I. The method of paired comparisons. Biometrika, 39:324–345, 1952.[3] Corinna Cortes, Mehryar Mohri, and Ashish Rastogi. Magnitude-preserving ranking algo- rithms. In Proceedings of the 24th International Conference on Machine Learning, ICML ’07, pages 169–176, New York, NY, USA, 2007. ACM.[4] H. A. David. The method of paired comparisons, volume 41 of Griffin’s Statistical Mono- graphs & Courses. Charles Griffin & Co., Ltd., London; The Clarendon Press, Oxford University Press, New York, second edition, 1988.[5] Dorit S. Hochbaum and Asaf Levin. Methodologies and algorithms for group-rankings decision. Manage. Sci., 52(9):1394–1408, September 2006.[6] Xiaoye Jiang, Lek-Heng Lim, Yuan Yao, and Yinyu Ye. Statistical ranking and combina- torial Hodge theory. Math. Program., 127(1, Ser. B):203–244, 2011.[7]M.G.KendallandB.BabingtonSmith.Onthemethodofpairedcomparisons.Biometrika, 31:324–345, 1940.[8] George Miller. The magical number seven, plus or minus two: Some limits on our capacity for processing information, 1956. One of the 100 most influential papers in cognitive science: http://cogsci.umn.edu/millennium/final.html[9] Frederick Mosteller. Remarks on the method of paired comparisons: I. the least squares solution assuming equal standard deviations and equal correlations. Psychometrika, 16(1): 3–9, 1951.[10] Frederick Mosteller. Remarks on the method of paired comparisons: Ii. the effect of an aberrant standard deviation when equal standard deviations and equal correlations are as- sumed. Psychometrika, 16(2):203–206, 1951.[11] Frederick Mosteller. Remarks on the method of paired comparisons: Iii. a test of signif- icance for paired comparisons when equal standard deviations and equal correlations are assumed. Psychometrika, 16(2):207–218, 1951.[12] Gottfried E. Noether. Remarks about a paired comparison model. Psychometrika, 25:357– 367, 1960.[13] Donald G. Saari and Vincent R. Merlin. A geometric examination of Kemeny’s rule. Soc. Choice Welf., 17(3):403–438, 2000.[14] Thomas L. Saaty. A scaling method for priorities in hierarchical structures. J. Mathemat- ical Psychology, 15(3):234–281, 1977.[15] Claire Voisin. Hodge theory and complex algebraic geometry. I, volume 76 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, english edi- tion, 2007. Translated from the French by Leila Schneps.[16]ClaireVoisin.Hodgetheoryandcomplexalgebraicgeometry.II,volume77ofCambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, english edi- tion, 2007. Translated from the French by Leila Schneps.[17] Douglas B. West. Introduction to graph theory. Prentice Hall, Inc., Upper Saddle River, NJ, 1996. 描述 碩士
國立政治大學
應用數學系
103751005資料來源 http://thesis.lib.nccu.edu.tw/record/#G0103751005 資料類型 thesis dc.contributor.advisor 蔡炎龍 zh_TW dc.contributor.advisor Tsai, Yen Lung en_US dc.contributor.author (Authors) 陳名秀 zh_TW dc.contributor.author (Authors) Chen, Ming Hsiu en_US dc.creator (作者) 陳名秀 zh_TW dc.creator (作者) Chen, Ming Hsiu en_US dc.date (日期) 2016 en_US dc.date.accessioned 5-Apr-2017 15:36:35 (UTC+8) - dc.date.available 5-Apr-2017 15:36:35 (UTC+8) - dc.date.issued (上傳時間) 5-Apr-2017 15:36:35 (UTC+8) - dc.identifier (Other Identifiers) G0103751005 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/108118 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 應用數學系 zh_TW dc.description (描述) 103751005 zh_TW dc.description.abstract (摘要) 霍奇排名是在近幾年才運用在排名的一種方法。在大多數現在的資料庫 中,資料庫很龐大,有些甚至會需要網路連結,而且很多會有資料不完整或 是資料不平衡的狀況。我們選擇用霍奇排名這種排名方法來處理可能會遇到 的這些困擾。這篇論文主要目的是想用運用基本的線性代數來研究霍奇排名和推導組合霍奇理論。 zh_TW dc.description.abstract (摘要) HodgeRank is a method of ranking that is new in recent years. In most of modern datasets, the amount of data is very large, some also need the internet connection, and plenty of them have the feature that incomplete or imbalanced. We use the method of HodgeRank to deal with these difficulties.This thesis is primary using elementary linear algebra to survey HodgeRank and deduce the combinatorial Hodge Theorem. en_US dc.description.tableofcontents 1 Introduction......................................... 12 Pairwise Ranking .................................... 42.1 PairwiseRankingProblems............................ 42.2 IntroductiontoHodgeRank............................ 42.3 PossibleApplicationsofPairwiseRankings ............ 62.3.1 RankingStudentsinaClass ......................... 62.3.2 MovieRecommendationSystems ...................... 7 2.3.3 RankingSportsTeam................................ 72.4 PairwiseRankingfromVoting ......................... 82.5 ProblemsofPairwiseRanking ......................... 83 Background .......................................... 93.1 SomeSimpleFactsinLinearAlgebra .................... 9 3.2 TheFirstIsomorphismTheorem ....................... 134 Combinatorial Hodge Theory ......................... 164.1 CochainComplex.................................... 16 4.2 CombinatorialHodgeTheory.......................... 17 4.3 Application ...................................... 205 Combinatorial Hodge Theory on Graphs ............... 225.1 GraphsandFunctionsonGraphs........................ 22 5.2 Matrices.......................................... 32 5.3 InnerProduct ..................................... 33 5.4 FindtheGlobalRanking ............................. 35 5.5 ApplyingCombinatorialHodgeTheory ................. 35 5.6 PracticalExample.................................. 366 Conclusion ......................................... 40Bibliography.......................................... 41 zh_TW dc.format.extent 384611 bytes - dc.format.mimetype application/pdf - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0103751005 en_US dc.subject (關鍵詞) 霍奇理論 zh_TW dc.subject (關鍵詞) 霍奇排名 zh_TW dc.subject (關鍵詞) 組合霍奇理論 zh_TW dc.subject (關鍵詞) HodgeRank en_US dc.subject (關鍵詞) Combinatorial Hodge theorem en_US dc.subject (關鍵詞) Ombinatorial Hodge decomposition en_US dc.title (題名) 霍奇排名之理論分析 zh_TW dc.title (題名) Theoretic Aspect of HodgeRank en_US dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) [1] Kenneth J. Arrow. A difficulty in the concept of social welfare. Journal of Political Economy, 58(4):328–346, 1950.[2] Ralph Allan Bradley and Milton E. Terry. Rank analysis of incomplete block designs. I. The method of paired comparisons. Biometrika, 39:324–345, 1952.[3] Corinna Cortes, Mehryar Mohri, and Ashish Rastogi. Magnitude-preserving ranking algo- rithms. In Proceedings of the 24th International Conference on Machine Learning, ICML ’07, pages 169–176, New York, NY, USA, 2007. ACM.[4] H. A. David. The method of paired comparisons, volume 41 of Griffin’s Statistical Mono- graphs & Courses. Charles Griffin & Co., Ltd., London; The Clarendon Press, Oxford University Press, New York, second edition, 1988.[5] Dorit S. Hochbaum and Asaf Levin. Methodologies and algorithms for group-rankings decision. Manage. Sci., 52(9):1394–1408, September 2006.[6] Xiaoye Jiang, Lek-Heng Lim, Yuan Yao, and Yinyu Ye. Statistical ranking and combina- torial Hodge theory. Math. Program., 127(1, Ser. B):203–244, 2011.[7]M.G.KendallandB.BabingtonSmith.Onthemethodofpairedcomparisons.Biometrika, 31:324–345, 1940.[8] George Miller. The magical number seven, plus or minus two: Some limits on our capacity for processing information, 1956. One of the 100 most influential papers in cognitive science: http://cogsci.umn.edu/millennium/final.html[9] Frederick Mosteller. Remarks on the method of paired comparisons: I. the least squares solution assuming equal standard deviations and equal correlations. Psychometrika, 16(1): 3–9, 1951.[10] Frederick Mosteller. Remarks on the method of paired comparisons: Ii. the effect of an aberrant standard deviation when equal standard deviations and equal correlations are as- sumed. Psychometrika, 16(2):203–206, 1951.[11] Frederick Mosteller. Remarks on the method of paired comparisons: Iii. a test of signif- icance for paired comparisons when equal standard deviations and equal correlations are assumed. Psychometrika, 16(2):207–218, 1951.[12] Gottfried E. Noether. Remarks about a paired comparison model. Psychometrika, 25:357– 367, 1960.[13] Donald G. Saari and Vincent R. Merlin. A geometric examination of Kemeny’s rule. Soc. Choice Welf., 17(3):403–438, 2000.[14] Thomas L. Saaty. A scaling method for priorities in hierarchical structures. J. Mathemat- ical Psychology, 15(3):234–281, 1977.[15] Claire Voisin. Hodge theory and complex algebraic geometry. I, volume 76 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, english edi- tion, 2007. Translated from the French by Leila Schneps.[16]ClaireVoisin.Hodgetheoryandcomplexalgebraicgeometry.II,volume77ofCambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, english edi- tion, 2007. Translated from the French by Leila Schneps.[17] Douglas B. West. Introduction to graph theory. Prentice Hall, Inc., Upper Saddle River, NJ, 1996. zh_TW
