Research On Bayesian Ranking Algorithms Based On Probabilistic Graphical Model

Estimating player’s skill and Ranking have played an important role in competitive sports. Bayesian skill estimation is a probabilistic problem that tries to use sport game results (such as win, draw, and lose) to estimate players’skills with linear ordering. The statistical methods to model sport game results are always objective and effective when a large number of participants can not be compared directly. TrueSkill is a typical algorithm that uses probabilistic graphical model to solve the problem, and TrueSkill-T is used to estimate the skill of participants on time series.This paper researches the professional Go player’s skill estimating from the aspects of game results, playing time, score, and first move advantage based on probabilistic graphical model. And then, the Bayesian rating algorithm based on graphical model is applied to recommender system. The main work and achievements discussed in this thesis are:(1) TrueSkill model is applied to the professional Go player’s skill estimating and a evaluation method of rating results is proposed. This paper compares and analyzes Elo algorithm, TrueSkill algorithm, and the existing grading system used in Go community. Experiments show that rankings generated by TrueSkill algorithm have good properties and it outperforms Elo in simulations by giving more sensible rankings.(2) TrueSkillGo-Year model is implemented by simplifying and modifying TrueSkill-T model according to the characteristics of Go matches. In order to explore the feasibility of TrueSkill-T on practical ranking applications, the adaptability of the data to this algorithm is investigated by data missing, error data based on real and simulated data of Go games. Experiments show that ranking meets domain knowledge and the algorithm is fit for practical use. (3) A method to model the first move advantage in the TrueSkill framework is proposed for the sport game results are usually influenced by first move advantage (or home play advantage), and this method can learn real skill of player and first move advantage automatically. Two real world datasets are used to compare the proposed method with three existing models, and the result shows that the proposed method can improve average estimation accuracy noticeably.(4) A recommender system based on probabilistic graphical model is proposed by combining content-based methods and user ratings. The structural information of user ratings is implicitly expressed by the topology of model and that is useful for reducing the input space. The curse of dimensionality caused by competition-based recommender system can also be solved by learning product quality and user preference. Experiments show that PGM-based recommender system has greatly improved the accuracy over the previous algorithm.