Tuesday, June 7, 2011
Google's Prediction API
Anyone out there up for trying out Google's Prediction API on NCAA basketball?
From the Maker's Faire
Peter Tu of GE Global Research was at the San Francisco Maker's Faire this weekend and mentions a talk by the guys who did the viral Coke & Mentos video:
Their method follows the 1-10-100 principle. It takes one experiment to spark a concept. By experiment 10 one should have fleshed things out and have defined a direction. By experiment 100 one hopes to have found something that is sublime… The four rules that they espouse are: 1) seek variation – explore the possibilities. 2) be obsessive – keep focused until one finds something special. 3) be stubborn – don’t give up until you work through the problems. 4) set limits and work within them – unconstrained innovation meanders and wonders, only by setting limits does it force one to dive into the depths of a concept. Their thoughts are somewhat reminiscent of “Zen and the Art of Motorcycle Maintenance”, where the key idea is to have an obsession with quality and to always have a good pot of coffee close at hand.This reminded me of someone... Although I doubt that I'm going to end up with a viral YouTube video :-)
Monday, June 6, 2011
A Note on Pace
Just a quick note to explain the slow pace of posting... Some of the iterative rating systems recalculate after every game, and can take upwards of two hours to prepare the test data set (which contains ~10K games). So when I hit an interesting system and am experimenting with different variants, it can take quite a while (what with real life interfering :-) to put together an assessment. I could post results piecemeal, but I think it makes more sense to wait until I have a complete assessment.
Wednesday, June 1, 2011
Logistic Regression/Markov Chain (LRMC)
The next MOV-based algorithm we'll look at is the Logistic Regression/Markov Chain (LRMC) model. LRMC was developed by Joel Sokol and Paul Kvam at Georgia Tech. It has gotten some press for being the best predictor of NCAA Tournament success over the past few years. In 2010 it got 51/63 games correct, better than any other predictor. (ISOV, a version of Iterative Strength Rating that uses MOV, was second.)
Sokol and Kvam have written several papers describing the LRMC model (one is available here). The basic notion is similar to the Random Walkers model. Each team has a certain number of votes, and in each iteration we move some of those votes to other teams, based upon that team's past performance. In the Random Walkers model, we move votes based upon whether a team won or lost a game. In LRMC, we move votes based upon the margin of victory.
In [Sokol 2006], the authors derive the following function to estimate the probability that Team A will beat Team B on a neutral site given that A beat B by "x" points on A’s court:
If we realize that "Team A will beat Team B on a neutral site" means the same thing as "Team A is better than Team B", then RH(x) gives us the probability that A is really better than B. We then use this probability to move "votes" between the two teams.
Of course, few NCAA basketball games take place on a neutral court, so we have to adjust our calculation to account for the HCA. [Sokol 2006] calculates the HCA at 10.5 points (a large value not in line with other analysts; we'll return to this in a moment), so we have to take away the HCA when calculating the RH(x) for the home team. If A beat B by 15 points at home, then RH(15-10.5) = 0.530, and A gets 53% of the "votes" that ride on this game.
If we plug RH(x) into our Random Walkers model, we get this performance:
This performance in on par with standard RPI. One concern with this approach is that even if the home team wins by 40 points, it can only garner about 70% of the "votes" because the exponential function tails off very slowly. Most college basketball fans would probably consider a win by 40 points near-certain proof that Team A was better than Team B. So rather than give the away team a floor of 30%, we can split the remaining 30%, or even assign it all to the home team. These approaches produce this performance:
Neither of these proves to be an improvement.
[Sokol 2010] experimented with replacing the "RH" function derived by logistic regression with other models, and found that an empirical Bayes model was better. (Technically, that makes the name LRMC no longer appropriate.) Part of the motivation for this change was that the 10.5 point home advantage found in the logistic regression model was considerably different than the estimates of HCA by everyone else. With the empirical Bayes model, the HCA is determined to be in the range 2-4, in line with other estimates. The RH function for the new model is:
This does prove to be an advantage over the original RH(x) function, but still not competitive with our best non-MOV predictor.
Sokol and Kvam have written several papers describing the LRMC model (one is available here). The basic notion is similar to the Random Walkers model. Each team has a certain number of votes, and in each iteration we move some of those votes to other teams, based upon that team's past performance. In the Random Walkers model, we move votes based upon whether a team won or lost a game. In LRMC, we move votes based upon the margin of victory.
In [Sokol 2006], the authors derive the following function to estimate the probability that Team A will beat Team B on a neutral site given that A beat B by "x" points on A’s court:
(The numeric factors in this equation were derived from analyzing home vs. home matchups using a logistic regression -- the details appear in the paper.)RH(x) = exp(0.292x-0.6228) / (1 + exp(0.292x-0.6228)
If we realize that "Team A will beat Team B on a neutral site" means the same thing as "Team A is better than Team B", then RH(x) gives us the probability that A is really better than B. We then use this probability to move "votes" between the two teams.
Of course, few NCAA basketball games take place on a neutral court, so we have to adjust our calculation to account for the HCA. [Sokol 2006] calculates the HCA at 10.5 points (a large value not in line with other analysts; we'll return to this in a moment), so we have to take away the HCA when calculating the RH(x) for the home team. If A beat B by 15 points at home, then RH(15-10.5) = 0.530, and A gets 53% of the "votes" that ride on this game.
If we plug RH(x) into our Random Walkers model, we get this performance:
| Predictor | % Correct | MOV Error |
|---|---|---|
| TrueSkill + iRPI | 72.9% | 11.01 |
| LRMC [2006] | 71.3% | 11.65 |
This performance in on par with standard RPI. One concern with this approach is that even if the home team wins by 40 points, it can only garner about 70% of the "votes" because the exponential function tails off very slowly. Most college basketball fans would probably consider a win by 40 points near-certain proof that Team A was better than Team B. So rather than give the away team a floor of 30%, we can split the remaining 30%, or even assign it all to the home team. These approaches produce this performance:
| Predictor | % Correct | MOV Error |
|---|---|---|
| TrueSkill + iRPI | 72.9% | 11.01 |
| LRMC [2006] | 71.3% | 11.65 |
| LRMC [2006] +15% to home | 70.5% | 11.62 |
| LRMC [2006] +30% to home | 66.8% | 12.57 |
Neither of these proves to be an improvement.
[Sokol 2010] experimented with replacing the "RH" function derived by logistic regression with other models, and found that an empirical Bayes model was better. (Technically, that makes the name LRMC no longer appropriate.) Part of the motivation for this change was that the 10.5 point home advantage found in the logistic regression model was considerably different than the estimates of HCA by everyone else. With the empirical Bayes model, the HCA is determined to be in the range 2-4, in line with other estimates. The RH function for the new model is:
RH(x) = phi(0.0189x-0.0756)Plugging this into our Random Walkers model gives this performance:
| Predictor | % Correct | MOV Error |
|---|---|---|
| TrueSkill + iRPI | 72.9% | 11.01 |
| LRMC [2006] | 71.3% | 11.65 |
| LRMC [2010] | 71.8% | 11.40 |
This does prove to be an advantage over the original RH(x) function, but still not competitive with our best non-MOV predictor.
Friday, May 27, 2011
The Offense-Defense Model & Probabilistic Matrix Model (PMM)
The first two MOV-based models will look at are similar: they both calculate an "Offense" and a "Defense" for each team. The "Offense" number represents a teams offensive capability and the "Defense" the defensive capability. When Duke plays UNC, Duke's predicted score is Duke's "Offense" times UNC's "Defense." Generally speaking, these numbers are calculated by initializing all teams to some baseline numbers (e.g., so that the expected score OxD = 65) and then iteratively adjusting the values so that they more closely match actual game outcomes. If Arizona State University consistently scores few points, it's "Offense" value will drop (and at the same time it's opponents' "Defense" value will also drop). After some number of iterations adjusting the numbers, the total error (across all games) will be minimized.
The Offense-Defense model is a version of this I first implemented for the 2010 March Madness Predictive Analytics Challenge. It's a fairly simple model. For each team, for each game, it predicts a score based upon the current Offense and Defense ratings. It then determines the error between the prediction and the actual game result, and adjusts the appropriate Offense and Defense ratings to remove 75% of the error. It then iterates this across all the games for a fixed number of iterations. (This algorithm isn't guaranteed to converge, although in practice it usually does.)
Testing this algorithm with our usual methodology gives these results (for comparison, I show the best non-MOV predictor as well):
This performance (with some adjustments) was enough to win the 2010 Challenge, but seems disappointing in comparison to the TrueSkill + iRPI performance. In particular, we might expect ratings based upon MOV to have lower MOV error rates, but that is not the case here. I also implemented a version of the Dick Vitale methodology, where I calculated separate home and away ratings for all teams. In this case, our predicted score is the home team's home Offense times the away team's away Defense (and vice versa). Here's how that performs:
Surprisingly (at least to me) this is significantly worse than the undifferentiated ratings. Perhaps this is additional evidence that teams don't play differently at home than away; the home court advantage would then be due primarily to the referees -- a conclusion shared by Sports Illustrated.
The second model I tested is the "Probabilistic Matrix Model" (PMM). This model is based upon the code Danny Tarlow released for his tournament predictor, which he discusses here. This is similar in spirit to the Offense-Defense model, if much more sophisticated mathematically. (You can tell this because the code has variables like s_hat_i in it.) Testing PMM gives these results:
The PMM does better than my naive Offense-Defense model (apparently there's something to all that math stuff) but still does not approach the performance of TrueSkill + iRPI. I did not implement separate home & away ratings, but there's no reason to think they would provide improved performance.
The Offense-Defense model is a version of this I first implemented for the 2010 March Madness Predictive Analytics Challenge. It's a fairly simple model. For each team, for each game, it predicts a score based upon the current Offense and Defense ratings. It then determines the error between the prediction and the actual game result, and adjusts the appropriate Offense and Defense ratings to remove 75% of the error. It then iterates this across all the games for a fixed number of iterations. (This algorithm isn't guaranteed to converge, although in practice it usually does.)
Testing this algorithm with our usual methodology gives these results (for comparison, I show the best non-MOV predictor as well):
| Predictor | % Correct | MOV Error |
|---|---|---|
| TrueSkill + iRPI | 72.9% | 11.01 |
| Offense-Defense | 69.6% | 11.84 |
This performance (with some adjustments) was enough to win the 2010 Challenge, but seems disappointing in comparison to the TrueSkill + iRPI performance. In particular, we might expect ratings based upon MOV to have lower MOV error rates, but that is not the case here. I also implemented a version of the Dick Vitale methodology, where I calculated separate home and away ratings for all teams. In this case, our predicted score is the home team's home Offense times the away team's away Defense (and vice versa). Here's how that performs:
| Predictor | % Correct | MOV Error |
|---|---|---|
| TrueSkill + iRPI | 72.9% | 11.01 |
| Offense-Defense (home & away) | 68.2% | 12.26 |
Surprisingly (at least to me) this is significantly worse than the undifferentiated ratings. Perhaps this is additional evidence that teams don't play differently at home than away; the home court advantage would then be due primarily to the referees -- a conclusion shared by Sports Illustrated.
The second model I tested is the "Probabilistic Matrix Model" (PMM). This model is based upon the code Danny Tarlow released for his tournament predictor, which he discusses here. This is similar in spirit to the Offense-Defense model, if much more sophisticated mathematically. (You can tell this because the code has variables like s_hat_i in it.) Testing PMM gives these results:
| Predictor | % Correct | MOV Error |
|---|---|---|
| TrueSkill + iRPI | 72.9% | 11.01 |
| Offense-Defense | 69.6% | 11.84 |
| PMM | 71.7% | 11.23 |
The PMM does better than my naive Offense-Defense model (apparently there's something to all that math stuff) but still does not approach the performance of TrueSkill + iRPI. I did not implement separate home & away ratings, but there's no reason to think they would provide improved performance.
Combinations & Other Models
Before we move on to MOV-based rating systems, it may be instructive to look at combining the various "RPI-like" rating systems to see if using them together can improve our prediction performance. For these experiments, I'll be looking at our three best RPI-like ratings: TrueSkill, Improved RPI (iRPI) and the Iterative Strength Rating (ISR).
The first experiment we can try is to use more than one rating as an input to our linear regression. The following table shows the performance using various combinations of the three ratings:
The combination of TrueSkill and the Improved RPI improves performance modestly. Adding in the Iterative Strength Rating does little (and in fact, the home team's ISR gets optimized out of the linear regression).
Another experiment we can try is to do a separate linear regression for each rating and then average their predictions (for regression tasks, this is done with the Vote operator in RapidMiner). Here are some averaging results:
Averaging provides worse performance than using a single linear regression.
We can also try using a more sophisticated prediction model than a linear regression. For cases where we're only using a single rating value for each team, we wouldn't expect this to provide significantly better performance than the linear regression. Here are the performances of some alternative models for the TrueSkill ratings:
As expected, there is no improvement over a simple linear regression. The alternate models also provide no benefit when we are using multiple ratings:
SVNs do the best here, but still not an improvement over the linear regression.
So combining TrueSkill & Improved RPI into a single regression is an improvement, but generally more sophisticated models don't provide any value. It's interesting to note that this performance is already as good as the best models reported in the literature.
Unless I get further distracted, I'll be moving on next to assessing ratings/models which make use of the margin of victory (MOV) next. I have a small collection of ratings/models to assess, but I'm always looking for inputs, so if you have a favorite ranking that you'd like to see included, please let me know!
The first experiment we can try is to use more than one rating as an input to our linear regression. The following table shows the performance using various combinations of the three ratings:
| Predictor | % Correct | MOV Error |
|---|---|---|
| TrueSkill | 72.8% | 11.07 |
| TrueSkill + Improved RPI | 72.9% | 11.01 |
| TrueSkill + Iterative Strength Rating | 72.7% | 11.05 |
| TrueSkill + Improved RPI + Iterative Strength Rating | 73.0% | 11.01 |
| Improved RPI + Iterative Strength Rating | 71.9% | 11.31 |
The combination of TrueSkill and the Improved RPI improves performance modestly. Adding in the Iterative Strength Rating does little (and in fact, the home team's ISR gets optimized out of the linear regression).
Another experiment we can try is to do a separate linear regression for each rating and then average their predictions (for regression tasks, this is done with the Vote operator in RapidMiner). Here are some averaging results:
| Predictor | % Correct | MOV Error |
|---|---|---|
| TrueSkill + Improved RPI (combined regression) | 72.9% | 11.01 |
| TrueSkill + Improved RPI (averaged) | 72.9% | 11.04 |
| TrueSkill + Iterative Strength Rating (averaged) | 72.8% | 11.17 |
| TrueSkill + Improved RPI + Iterative Strength Rating (averaged) | 73.0% | 11.16 |
Averaging provides worse performance than using a single linear regression.
We can also try using a more sophisticated prediction model than a linear regression. For cases where we're only using a single rating value for each team, we wouldn't expect this to provide significantly better performance than the linear regression. Here are the performances of some alternative models for the TrueSkill ratings:
| Predictor | % Correct | MOV Error |
|---|---|---|
| TrueSkill (neural network) | 72.8% | 11.07 |
| TrueSkill (support vector machine) | 72.7% | 11.08 |
| TrueSkill (k-NN, k=96) | 72.7% | 11.13 |
As expected, there is no improvement over a simple linear regression. The alternate models also provide no benefit when we are using multiple ratings:
| Predictor | % Correct | MOV Error |
|---|---|---|
| TrueSkill + Improved RPI (neural network) | 68.8% | 12.24 |
| TrueSkill + Improved RPI (support vector machine) | 72.9% | 11.02 |
| TrueSkill + Improved RPI (k-NN, k=96) | 72.8% | 11.13 |
SVNs do the best here, but still not an improvement over the linear regression.
So combining TrueSkill & Improved RPI into a single regression is an improvement, but generally more sophisticated models don't provide any value. It's interesting to note that this performance is already as good as the best models reported in the literature.
Unless I get further distracted, I'll be moving on next to assessing ratings/models which make use of the margin of victory (MOV) next. I have a small collection of ratings/models to assess, but I'm always looking for inputs, so if you have a favorite ranking that you'd like to see included, please let me know!
Tuesday, May 24, 2011
RPI-Like Summary
I've re-implemented the incorrect algorithms and results are below. But before summarizing the results so far, I'll briefly mention a few others that I did not implement.
Glicko
The Glicko Rating system was developed by Mark Glickman (chairman of the US Chess Federation (USCF) ratings committee) as an improvement upon ELO. The Glicko Rating system is very similar to Microsoft's TrueSkill rating system. Both are based on Bayesian reasoning and provide both a rating and an uncertainty. For two player games that don't produce ties (i.e., basketball) the only significant difference is that Glicko uses a logistic distribution of performance ratings rather than the Gaussian distribution used by TrueSkill. It seems unlikely that this small difference would result in a significant difference in predictive performance. (The Glicko-2 system adds a "volatility" factor, and this might be worth investigating at some point.)
Jon Dokter
The Prediction Tracker tracks the accuracy of various NCAA basketball rating systems both for won-loss and against the Las Vegas line. The highest rated system as of the end of the 2010-2011 season belonged to Jon Dokter. Dokter's ratings are intended to be predictive (he sells wagering advice for $10.99/week) but are not well-explained. This page provides a general overview of his methods, but there is not enough detail to replicate his rating system for testing.
Bethel Rank
Roy Bethel proposed a ranking system based upon "Maximum Likelihood Estimation" specifically to address the problem of sports with unequal strength of schedules, i.e., where teams do not play a complete round-robin. (His paper is available in the papers archive.) While Bethel's rating system appears interesting, it cannot handle winless or lossless teams. Since both happen with some regularity in college basketball (and are certain to occur for a significant portion of the season) using this rating is problematic.
NCAA Tournament-Specific Ratings
A number of people have created rating systems specific to predicting the NCAA tournament, e.g., Bradley West and Nate Silver. Most of these rely on seeding, human polls or other information that exists only for the tournament, and makes them unsuitable for predicting regular season games.
Other Systems
I'm interested in any pointers to other rating systems that I should investigate, particularly if they have a fundamentally different approach than the ones I've covered already. Send me an email (srt19170@gmail.com) or leave a comment.
Summary of Results
In total, I tested about 110 algorithm variants. (Some multiple times as I uncovered errors in my code!) The following table summarizes the best performances for each algorithm:
There are a couple of interesting points to be gathered from this.
First, the best performer (TrueSkill) represents about a 15% improvement over always picking the home team, but only about a 2% improvement over the standard RPI. On MOV Error, it fares somewhat better, being a 22% improvement over picking the home team, and about 5% over RPI. But given the complexity of TrueSkill compared to the 1-Bit algorithm (or even standard RPI), that isn't as much improvement as we might have hoped to see.
Second, we note that the performance of our implementation of ELO is very close to the tracked performance of Sagarin ELO at Prediction Tracker. That gives us some confidence in these results. (On the MOV Error side, there seems to be about a 1.5 point bias in MOV Error between my measurements and those on Prediction Tracker. I don't know why that would be.)
Third, if we compare TrueSkill to the rating systems tracked at Prediction Tracker, we see it would have beaten all systems except Jon Doktor -- and his system makes use of MOV. So even without making use of MOV, we have a system that is competitive with the best systems available.
Glicko
The Glicko Rating system was developed by Mark Glickman (chairman of the US Chess Federation (USCF) ratings committee) as an improvement upon ELO. The Glicko Rating system is very similar to Microsoft's TrueSkill rating system. Both are based on Bayesian reasoning and provide both a rating and an uncertainty. For two player games that don't produce ties (i.e., basketball) the only significant difference is that Glicko uses a logistic distribution of performance ratings rather than the Gaussian distribution used by TrueSkill. It seems unlikely that this small difference would result in a significant difference in predictive performance. (The Glicko-2 system adds a "volatility" factor, and this might be worth investigating at some point.)
Jon Dokter
The Prediction Tracker tracks the accuracy of various NCAA basketball rating systems both for won-loss and against the Las Vegas line. The highest rated system as of the end of the 2010-2011 season belonged to Jon Dokter. Dokter's ratings are intended to be predictive (he sells wagering advice for $10.99/week) but are not well-explained. This page provides a general overview of his methods, but there is not enough detail to replicate his rating system for testing.
Bethel Rank
Roy Bethel proposed a ranking system based upon "Maximum Likelihood Estimation" specifically to address the problem of sports with unequal strength of schedules, i.e., where teams do not play a complete round-robin. (His paper is available in the papers archive.) While Bethel's rating system appears interesting, it cannot handle winless or lossless teams. Since both happen with some regularity in college basketball (and are certain to occur for a significant portion of the season) using this rating is problematic.
NCAA Tournament-Specific Ratings
A number of people have created rating systems specific to predicting the NCAA tournament, e.g., Bradley West and Nate Silver. Most of these rely on seeding, human polls or other information that exists only for the tournament, and makes them unsuitable for predicting regular season games.
Other Systems
I'm interested in any pointers to other rating systems that I should investigate, particularly if they have a fundamentally different approach than the ones I've covered already. Send me an email (srt19170@gmail.com) or leave a comment.
Summary of Results
In total, I tested about 110 algorithm variants. (Some multiple times as I uncovered errors in my code!) The following table summarizes the best performances for each algorithm:
| Predictor | % Correct | MOV Error |
|---|---|---|
| Naïve | 50.0% | 14.50 |
| 1-Bit | 62.6% | 14.17 |
| Random Walkers | 71.0% | 11.72 |
| RPI | 71.2% | 11.62 |
| ELO | 71.8% | 11.59 |
| KRACH | 71.5% | 11.50 |
| Colley | 71.8% | 11.33 |
| Wilson | 71.9% | 11.32 |
| ISR | 71.9% | 11.32 |
| Improved RPI | 72.1% | 11.30 |
| TrueSkill | 72.8% | 11.09 |
There are a couple of interesting points to be gathered from this.
First, the best performer (TrueSkill) represents about a 15% improvement over always picking the home team, but only about a 2% improvement over the standard RPI. On MOV Error, it fares somewhat better, being a 22% improvement over picking the home team, and about 5% over RPI. But given the complexity of TrueSkill compared to the 1-Bit algorithm (or even standard RPI), that isn't as much improvement as we might have hoped to see.
Second, we note that the performance of our implementation of ELO is very close to the tracked performance of Sagarin ELO at Prediction Tracker. That gives us some confidence in these results. (On the MOV Error side, there seems to be about a 1.5 point bias in MOV Error between my measurements and those on Prediction Tracker. I don't know why that would be.)
Third, if we compare TrueSkill to the rating systems tracked at Prediction Tracker, we see it would have beaten all systems except Jon Doktor -- and his system makes use of MOV. So even without making use of MOV, we have a system that is competitive with the best systems available.
Subscribe to:
Posts (Atom)