Rating Systems Vs Machine Learning on the context of

Report
Rating Systems Vs Machine
Learning on the context of
sports
George Kyriakides, Kyriacos Talattinis, George Stefanides
Department of Applied Informatics,
University Of Macedonia
Aim of the paper
• Study the performance of linear algebra rating systems and machine
learning methods.
• Evaluate the accuracy of each method.
• Evaluate the quality of the predictions.
Structure of the presentation
• Clarify what is rating and ranking.
• Explain linear algebra rating systems used in this paper.
• Explain machine learning methods used in this paper.
• Compare the rating systems and machine learning methods by
predicting soccer games (English Premier League).
• Conclusions.
• Possible future work.
Related research
• Nivard van Wijk uses a Pseudo Least-Squares Estimator to predict soccer
matches.
• Paul Kvam and Joel S. Sokol use logistic regression and markov chains to
predict basketball matches.
• Keeneth Massey uses linear algebra to rank basketball and football teams.
• Search engines use machine learning to rank search results.
• No comparison between machine learning and linear algebra has been
made.
• Studies on accuracy have been conducted for machine learning and linear
algebra independently, but never for profitability of the methods.
Rating
• The evaluation of an object, based on some desirable criteria. For
example, a car may have a 1 to 5 stars NCAP safety rating.
Ranking
• A relationship between a set of objects, such that for any two items,
one is ranked higher than the other and is consequently better,
assuming that the object ranked highest is the best.
• Rating can be used to rank a set of objects. Sorting a vector
containing ratings we are effectively ranking the elements.
Ranking
Rating Systems
• Many systems have been proposed:
•
•
•
•
•
•
•
Massey
Colley
Markov
Keener
Google Page Rank
mHITS
Elo
Methods used in this paper
• Massey
• Colley
• mHITS
Massey Method
• Proposed by Kenneth Massey in 1997 to rank NCAA (National
Collegiate Athletic Association) teams.
• It uses a linear least squares regression to solve a system of linear
equations.
• A rating vector is calculated, where each entry corresponds to the
rating of the team.
• Massey Method (2)
• First, the matrix M is generated , where Mij is the number of games teams i
and j played, multiplied by -1 and Mii is the total number of games team i
has played.
• The second step is to calculate the vector p, where pi is the total number of
points scored by team i, minus the points that were scored against the
team.
• The final step is to solve the system of equations:
Mr= p
where r is the vector of the ratings, so if ri > rj team i is better than team j.
Colley Method
• Proposed by astrophysicist Dr.Wesley Colley in 2001.
• Variation of a simple method used to rank teams, which calculated
the win ratio of each team (wins divided by total games).
• A system of linear equations is solved in order to find a rating vector.
Colley Method (2)
• First the matrix C is computed as follows:
2 +  ,  = 
 = − ,
≠

Where nij is the total number of games played between teams i and j.
• Second, the vector b is computed:
1
 = 1 + ( - )
2
Where wi are the total wins of team i and li are the total losses of team i.
• Finally, the system of equations
Cr=b
is solved, where r is the vector with the rating for each team.
mHITS(Offence-Defense model)
• It was proposed by Anjela Govan in 2009.
• Generalization of HITS algorithm for ranking web pages.
• It uses the offensive and defensive strength of the teams to calculate
their overall rating.
• The method calculates the rating of a team:
 =


Where ri is the rating of the team, oi is its offensive strength and di is
its defensive strength.
mHITS(Offence-Defense model) (2)
• Initialize vector d(0)=[d1 d2....dn] as a vector of ones.
• Compute the matrix A, where aij is the score that team j generated against
team i (0 if they did not play each other).
• The third step of the initialization is to calculate
1
(0)

 =

• Continue to refine o and d, by continuously computing
1
()

 =  (−1)

1
()

 =  ()

• High o values signify strong offence and low d values signify strong defense
Machine Learning
Methods used in this paper
• Decision Trees
• Artificial Neural Networks
• Random Forests
Artificial Neural Networks
• Networks of nodes which accept inputs and produce an output based
on an activation function.
• Nodes’ connections are weighted.
• Usually organized in layers .
• Each layer is a group of nodes not connected to any node of the same
group.
• Input data is presented to the input layer, “hidden” layers process the
data and the presentation layer outputs the results.
Artificial Neural Networks
• Multilayer Perceptron, which uses back propagation was used in the
paper.
• Learning rate:0.3
• Momentum:0.2
• Hidden layers:3
• Epochs:500
• 10-Fold Cross-Validation
Decision Tree Learning
• Uses a decision tree to classify/predict.
• Also known as classification/regression trees.
• Leaves represent class labels.
• Branches split the data into appropriate sets.
• Different algorithms use different criteria to split the data.
C4.5
• Uses Information Gain to measure the quality of the split.
• Confidence factor: 0.7
• Unpruned
• 10-Fold Cross-Validation
Random Forest
• A multitude of decision trees is generated
• Each tree is trained independently, using a different subset of the
data
• Input data is presented to all trees
• The class that the highest percentage of trees produce is the output
Soccer
Soccer
• Ternary Result
Season 2009-2010
Draw
Away
Home
Predictions
• Hindsight
• Foresight
• Betting
Implementation
• Weka
•
•
•
•
Open-source GNU GPL
Data mining software
Implemented in Java
Association rules, Classification, Clustering
• Custom Java code
• mHits
• Colley
• Massey
• Jamma
• Numerical linear algebra library
Hindsight Accuracy
Method Neural
Trees
Forest
MHITS
Colley
Massey
Season
2008 /2009
52.63%
71.32%
97.11%
51.37%
53.62%
38.90%
2009 / 2010
56.32%
72.11%
94.74%
55.20%
56.54%
48.67%
2010 /2011
51.32%
60.79%
94.74%
45.07%
47.05%
42.18%
2011 /2012
50.53%
58.42%
96.32%
54.95%
55.46%
47.68%
2012 /2013
45.79%
55.00%
95.79%
50.88%
51.88%
42.95%
Hindsight (2)
120.00%
100.00%
80.00%
60.00%
40.00%
20.00%
0.00%
2008 /2009
2009 / 2010
2010 /2011
2011 /2012
2012 /2013
Confusion Matrices
• Confusion matrices allow the visualization of the performance of an
algorithm
• It indicates the quality of the predictions
• 95% Accuracy:
Class A
B
Actual
A
95 5
B
0
0
Confusion Matrices (Hindsight)
Random Forest
94.74%
Class
Loss
Win
Decision Tree
72.11%
Draw
Actual
Class
Loss
Win
ANN
56.32%
Draw
Actual
Class
Loss
Win
Draw
Actual
Loss
87
2
2
Loss
65
21
5
Loss
18
46
27
Win
5
186
2
Win
11
178
4
Win
8
167
18
Draw
1
8
87
Draw
13
52
31
Draw
11
56
29
Foresight Accuracy
Method Neural
Trees
Forest
MHITS
Colley
Massey
Season
2008 /2009
56.84%
49.47%
50.00%
56.97%
48.78%
36.25%
2009 / 2010
50.00%
52.63%
38.42%
53.05%
48.17%
42.10%
2010 /2011
46.32%
46.32%
41.58%
46.63%
42.78%
41.06%
2011 /2012
46.84%
46.84%
37.89%
53.35%
46.90%
45.83%
2012 /2013
50.53%
48.74%
48.42%
52.40%
47.70%
40.54%
Foresight (2)
60.00%
50.00%
40.00%
30.00%
20.00%
10.00%
0.00%
2008 /2009
2009 / 2010
2010 /2011
2011 /2012
2012 /2013
Confusion Matrices (Foresight)
Random Forest
37.89%
Class
Loss
Draw
Decision Tree
46.84%
Win
Class
Loss
Draw
ANN
46.84%
Win
Actual
Actual
Class
Loss
Draw
Win
Actual
Loss
21
15
17
Loss
17
11
25
Loss
16
4
33
Draw
18
12
13
Draw
13
6
24
Draw
19
0
24
Win
31
24
39
Win
15
13
66
Win
21
0
73
Making a profit
Quantity
VS
Quality
Making a profit
• Quantity.
• 90% Accuracy – 1.05 average booking odds
•
•
•
•
In 100 games, betting 1 unit each time:
Win 90*0.05 = 4.5
Lose 10
Net profit = 10-4.5 = -5.5
Making a profit
• Quality
• 60% Accuracy – 2.5 average booking odds
•
•
•
•
In 100 games, betting 1 unit each time:
Win 60*1.5 = 90
Lose 40
Net profit = 90 - 40 = 50
Betting
• The average odds of the 5 biggest online booking companies.
• 1000 money units starting capital.
• 50 units betted each time.
• Each method chose the outcome it thought would occur.
Foresight Betting Money Sum
Method Neural
Season
Trees
Forest
MHITS
Colley
Massey
2008 /2009
1368
1422
1157
1802
510
-690
2009 / 2010
816
-918
54
480
157
-722
2010 /2011
1387
366
1899
132
-707
-351
2011 /2012
541
-55
99
1629
839
2252
2012 /2013
2010
1815
1635
1133
993
551
Foresight Betting Net Profits sum
1500
1000
500
0
-500
-1000
-1500
2008/2009
-2000
-2500
2009 / 2010
2010 /2011
2011 /2012
2012 /2013
Conclusions
• Machine learning proved to be superior in hindsight predictions and
prediction quality.
• Draws are the most difficult to predict.
• mHITS is the best in foresight prediction accuracy, but not in quality.
• Neural Networks are the most profitable of all.
• Random Forests constructed the best hindsight models.
Future Work
• Other Machine Learning Methods
• Portfolio management for betting section
• Other sports, where a draw is much less likely to be the outcome
Thank you very much for your attention!

similar documents