跳到主要內容

臺灣博碩士論文加值系統

(44.220.44.148) 您好!臺灣時間:2024/06/21 14:43
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:黃子國
研究生(外文):Tzu-Kuo Huang
論文名稱:由團體比較做個體排名
論文名稱(外文):Ranking Individuals by Group Comparisons
指導教授:林智仁林智仁引用關係
指導教授(外文):Chih-Jen Lin
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:資訊工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:英文
論文頁數:62
中文關鍵詞:排名團體比較
外文關鍵詞:rankinggroup comparisons
相關次數:
  • 被引用被引用:0
  • 點閱點閱:118
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本論文探討的主題為如何從團體競爭之結果得到個體排名。
這個問題見於多處,
例如,
團體運動競賽中運動員的排名。
而在機器學習領域裡,
這個問題和多類別之分類及類別機率估測
有密切的關聯。
競賽結果通常有兩種型態:僅為勝負或
勝負及分數。根據這兩種競賽結果,我們提出新的模型來估計
個體之能力,從而獲得個體排名,並發展了簡單而有效
的估計演算法。為了驗證這些模型的效用,我們將其
用於分析橋牌比賽之結果以及多類別之分類問題。實驗結果
顯示,這些模型的確能得到好的估計。
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
A. Agresti. Categorical Data Analysis. Wiley, New York, 1990.
E. L. Allwein, R. E. Schapire, and Y. Singer. Reducing multiclass to binary: a unifying approach for margin classifiers. Journal of Machine Learning Research, 1:113–141, 2001. ISSN 1533-7928.
C. L. Blake and C. J. Merz. UCI repository of machine learn-ing databases. Technical report, University of California, Department of Information and Computer Science, Irvine, CA, 1998. Available at http://www.ics.uci.edu/~mlearn/MLRepository.html.
B. Boser, I. Guyon, and V. Vapnik. A training algorithm for optimal margin clas-sifiers. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, pages 144–152. ACM Press, 1992.
R. A. Bradley and M. Terry. The rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39:324–345, 1952.
G. W. Brier. Verification of forecasts expressed in probabilities. Monthly Weather Review, 78:1–3, 1950.
C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/∼cjlin/libsvm.
C. Cortes and V. Vapnik. Support-vector network. Machine Learning, 20:273– 297, 1995.
J. Darroch and D. Ratchli. Generalized iterative scaling for log-linear models. The Annals of Mathematical Statistics, 43(5):1470–1480, 1972.
H. A. David. The method of paired comparisons. Oxford University Press, second edition, 1988.
R. R. Davidson and P. H. Farquhar. A bibliography on the method of paired comparisons. Biometrics, 32:241–252, 1976.
T. G. Dietterich and G. Bakiri. Solving multiclass learning problems via error-correcting output codes. Journal of Artificial Intelligence Research, 2:263–286, 1995. URL citeseer.ist.psu.edu/dietterich95solving.html.
L. R. J. Ford. Solution of a ranking problem from binary comparisons. American Mathematical Monthly, 64(8):28–33, 1957.
M. E. Glickman. Paired comparison models with time-varying parameters. PhD thesis, Department of Statistics, Harvard University, 1993.
J. Goodman. Sequential conditional generalized iterative scaling. In ACL, pages 9–16, 2002.
T. Hastie and R. Tibshirani. Classification by pairwise coupling. The Annals of Statistics, 26(1):451–471, 1998.
T.-K. Huang, R. C. Weng, and C.-J. Lin. A generalized Bradley-Terry model: From group competition to individual skill. In Advances in Neural Information Processing Systems 17. MIT Press, Cambridge, MA, 2005.
T.-K. Huang, C.-J. Lin, and R. C. Weng. Ranking individuals by group compar-isons. In Proceedings of the Twenty Third International Conference on Machine Learning (ICML), 2006a.
T.-K. Huang, R. C. Weng, and C.-J. Lin. Generalized Bradley-Terry models and multi-class probability estimates. Journal of Machine Learning Research, 7:85– 115, 2006b. URL http://www.csie.ntu.edu.tw/∼cjlin/papers/generalBT. pdf.
J. J. Hull. A database for handwritten text recognition research. IEEE Transac-tions on Pattern Analysis and Machine Intelligence, 16(5):550–554, May 1994.
D. R. Hunter. MM algorithms for generalized Bradley-Terry models. The Annals of Statistics, 32:386–408, 2004.
Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324, November 1998. MNIST database available at http://yann.lecun.com/exdb/mnist/.
H.-T. Lin, C.-J. Lin, and R. C. Weng. A note on Platt’s probabilistic outputs for support vector machines. Technical report, Department of Computer Science, National Taiwan University, 2003. URL http://www.csie.ntu.edu.tw/∼cjlin/ papers/plattprob.ps.
P. McCullagh and J. A. Nelder. Generalized Linear Models. CRC Press, 2nd edition, 1990.
D. Michie, D. J. Spiegelhalter, and C. C. Taylor. Machine Learning, Neural and Statistical Classification. Prentice Hall, Englewood Cliffs, N.J., 1994. Data available at http://www.ncc.up.pt/liacc/ML/statlog/datasets.html.
R. N. Pendergrass and R. A. Bradley. Ranking in triple comparisons. In I. Olkin, editor, Contributions to Probability and Statistics. Stanford University Press, Stanford, CA, 1960.

S. D. Pietra, V. D. Pietra, and J. Lafferty. Inducing features of random fields. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(4):380–393, 1997.
R. L. Placket. The analysis of permutations. Applied Statistics, 24:193–202, 1975.
J. Platt. Probabilistic outputs for supportvector machines and comparison to reg-ularized likelihood methods. In A. Smola, P. Bartlett, B. Sch¨olkopf, and D. Schu-urmans, editors, Advances in Large Margin Classifiers, Cambridge, MA, 2000. MIT Press. URL citeseer.nj.nec.com/platt99probabilistic.html.
P. V. Rao andL. L. Kupper. Ties in paired-comparison experiments: Ageneraliza-tion of the Bradley-Terry model. Journal of the American Statistical Association, 62:194–204, 1967. [Corrigendum J. Amer. Statist. Assoc. 63 1550-1551].
G. Simons and Y.-C. Yao. Asymptotics when the number of parameters tends to infinity in the Bradley-Terry model for paired comparisons. The Annals of Statistics, 27(3):1041–1060, 1999.
T.-F. Wu, C.-J. Lin, and R. C. Weng. Probability estimates for multi-class classi-fication bypairwise coupling. Journal of Machine Learning Research, 5:975–1005, 2004. URL http://www.csie.ntu.edu.tw/∼cjlin/papers/svmprob/svmprob. pdf.
B. Zadrozny. Reducing multiclass to binary by coupling probability estimates. In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems 14, pages 1041–1048. MIT Press, Cambridge, MA, 2002.
E. Zermelo. Die Berechnungder Turnier-Ergebnisse als ein Maximumproblem der Wahrscheinlichkeitsrechnung. Mathematische Zeitschrift, 29:436–460, 1929.
T. Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 32(1):56–134, 2004.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top