林智仁臺灣大學：資訊工程學研究所黃子國Huang, Tzu-KuoTzu-KuoHuang2007-11-262018-07-052007-11-262018-07-052006http://ntur.lib.ntu.edu.tw//handle/246246/53797本論文探討的主題為如何從團體競爭之結果得到個體排名。 這個問題見於多處， 例如， 團體運動競賽中運動員的排名。 而在機器學習領域裡， 這個問題和多類別之分類及類別機率估測 有密切的關聯。 競賽結果通常有兩種型態：僅為勝負或 勝負及分數。根據這兩種競賽結果，我們提出新的模型來估計 個體之能力，從而獲得個體排名，並發展了簡單而有效 的估計演算法。為了驗證這些模型的效用，我們將其 用於分析橋牌比賽之結果以及多類別之分類問題。實驗結果 顯示，這些模型的確能得到好的估計。This thesis studies the problem of ranking individuals from their group competition results. Many real-world problems are of this type. For example, ranking players from team games is important in some sports. In machine learning, this is closely related to multi-class classification and probability estimates. Competition results are usually in two types: wins/losses only or wins/losses with scores. Based on the two types of results, we propose new models for estimating individuals' abilities, and hence rankings of individuals. We develope easy and effective solution procedures. Experiments on real bridge records and multi-class classification demonstrate the viability of the proposed models.TABLE OF CONTENTS ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii LIST OF FIGURES. . . . vi LIST OF TABLES. . . . . . . . . . . . . vii CHAPTER I. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 II. Binary Comparison Models . . . . . . . . . . . . . . . . . . . . . . 4 2.1 A Generalized Bradley-Terry model . . . . . . . . . . . . . . . 4 2.1.1 A Simple Procedure to Maximize the Likelihood (GBT) ...5 2.1.2 Other Methods to Maximize the Likelihood . . . . . . 6 2.1.3 Convergence of Algorithm 2 . . . . . . . . . . . . . . 7 2.2 An Exponential Model . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.1 Regularized Least Square (RLS) . . . . . . . . . . . . 11 2.2.2 Maximum A Posteriori (MAPB) . . . . . . . . . . . . 12 III. Scored Comparison Models . . . . . . . . . . . . . . . . . . . . . . 16 3.1 A Normal Model (NM) . . . . . . . . . . . . . . . . . . . . . . 16 3.2 The Exponential Model (2.12)(MAPS) . . . . . . . . . . . . . 17 IV. Multi-class Classification and Probability Estimates . . . . . . 20 4.1 Properties of the “One-against-the rest” Approach . . . . . . . 21 4.2 An Earlier Approach . . . . . . . . . . . . . . . . . . . . . . . . 23 4.3 Experiments: Simulated Examples . . . . . . . . . . . . . . . . 23 4.3.1 Data Generation . . . . . . . . . . . . . . . . . . . . . 24 4.3.2 Results of Various ECOC Settings . . . . . . . . . . . 24 4.4 Experiments: Real Data . . . . . . . . . . . . . . . . . . . . . . 28 4.4.1 Data and Experimental Settings . . . . . . . . . . . . 28 4.4.2 Evaluation Criteria and Results . . . . . . . . . . . . 29 V. Ranking Partnerships from Real Bridge Records . . . . . . . . 33 5.1 Experimental Settings . . . . . . . . . . . . . . . . . . . . . . . 34 5.2 Results and Analysis . . . . . . . . . . . . . . . . . . . . . . . . 36 VI. Extensions of the Generalized Bradley-Terry Model . . . . . . 43 6.1 Weighted Individual Skill . . . . . . . . . . . . . . . . . . . . . 43 6.2 Home-field Advantage . . . . . . . . . . . . . . . . . . . . . . . 44 6.3 Ties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 6.4 Multiple Team Comparisons . . . . . . . . . . . . . . . . . . . . 45 VII. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 APPENDICES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60569878 bytesapplication/pdfen-US排名團體比較rankinggroup comparisonsthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53797/1/ntu-95-R93922002-1.pdf