Halftime Scores

Suppose that Maryland plays Duke in Cameron.  Maryland is ahead by 8 points at halftime, but ends up losing by 2 points.  The next week, Wake Forest plays Duke in Cameron.  They're down 1 point at halftime, and also end up losing by 2 points.

On the basis of those games, which is the better team, Maryland or Wake Forest?

There are reasonable arguments for several viewpoints.  Certainly you might argue that there's no reason to think either is better -- they both ended up at the same place and the halftime score is immaterial.  You could also argue that Maryland is better -- they outplayed Duke, at least for a half, which is more than Wake Forest managed.  Or you could argue that Wake Forest is better -- they were within a small margin of error of beating Duke in both halves, which is more than Maryland can say.

Or consider the case where Maryland wins the first half by 8 and loses the second by 10, while Wake Forest loses the first half by 10 and wins the second half by 8.  Is that evidence that either team is better?

In reading papers on rating systems over the past few years, I've noticed that many authors devise a rating system to reflect their personal belief on questions like this one.  I wouldn't be surprised at all to read a paper that said (in effect) "Based upon the halftime score, Maryland is clearly the better team, and here's a rating system that reflects that."  So we have rating systems that discount blowouts, and rating systems that emphasize non-conference road wins, and so on.

As long-time readers of this blog know, my own outlook is different.  What I believe is important or unimportant isn't, well, important.  What counts is whether something improves predictive performance.  So when I started collecting scoring by halves, my purpose was to see how that could be best used to improve prediction.

The first thing I did was to create some baseline statistics based on the scoring by halves, such as a team's average score in the first half, in the second half, average score of opponents in the first half, average MOV by half, and so on.  I didn't expect these statistics to have much predictive value.  For one thing, it seems clear that the strength of the opposing team is an important factor in understanding a team's performance, and none of these baseline statistics reflect that strength of schedule.

Still, I believe in testing over assumptions, and testing revealed at least one statistic that did have some predictive value: the ratio of a team's scoring in the first half to the scoring in the second half.  As I hinted here, there's some correlation between team strength and the ratio of scoring by halves.  Good teams generally have high ratios -- that is, they do more of their scoring in the first half than the average team does.  That's a pretty intriguing result.  Some work by Monte McNair shows that teams generally improve their offensive efficiency as the game progresses, so it may be that good teams play more efficiently from the start of the game.  There's probably more interesting results to be had by analyzing and understanding this result.

After testing the baseline statistics, I turned my attention to using the scoring by halves with strength measures like RPI, Trueskill and so on.  These measures try to assign a team a single numeric strength value based upon game outcomes.  I wanted to try to extend the measures to include the scoring by halves information and see whether that improved the predictive value of the measures.

There are several ways to go about this, but one straightforward approach is to treat each half like another separate game.  So in the case of Maryland above, we'd calculate our measure as if Maryland had played Duke three times -- winning once by 8, losing once by 10, and losing once by 2.  We can also try variants, such as using only the first halves of games.  So we can calculate all the variants and test to see which one has the best predictive value.

I've initially applied this approach to Trueskill.  To begin with, I measured the performance of the baseline Trueskill-MOV metric on my current test set.  This is currently the best single predictive measure in the Performance Machine's metrics.

Predictor	% Correct	MOV Error
Baseline Trueskill-MOV	72.7%	11.59

The first tests were to calculate the metric based on just the halves individually, and then using all three results.

Predictor	% Correct	MOV Error
Baseline Trueskill-MOV	73.6%	11.59
First Half Only	72.1%	11.97
Second Half Only	70.9%	12.69
All Three	73.4%	11.55

There are a couple of things to note here.  As you might guess, neither half by itself is better than using the game score.  More surprising is that performance in the first half is much better for prediction than performance in the second half.  (To go back to our second example above, this is reason to believe that Maryland is the better team than Wake Forest.)  And using all three together is marginally better (at least in MOV Error) than using just the final score.

So far this treated each half like a separate game.  But one could argue that a Margin of Victory of 4 in a half is the equivalent of an MOV of 8 in a whole game.  We can test this by applying various modifiers to the scores and how they are bonused in the algorithm.  The best results I could find were these:

Predictor	% Correct	MOV Error
Baseline Trueskill-MOV	73.6%	11.59
Best First Half Only	73.2%	11.78
Best Second Half Only	72.2%	12.25
All Three	73.4%	11.51

With tweaking all of the variants could be improved somewhat.  Using all three was about a 1/10 of a point improvement on the baseline.

Another possibility is to use the two half scores and ignore the game score.  With some tweaking to count the first half about twice as much as the second half, this turns out to be very effective:

Predictor	% Correct	MOV Error
Baseline Trueskill-MOV	73.6%	11.59
Only Half Scores	74.3%	11.46

I find this a pretty surprising result.  Getting a better strength metric by ignoring the game outcomes is non-intuitive (to say the least) and goes against the typical sports punditry about how winning is the only thing that matters.

This metric is the single best metric in the PM's arsenal, and was used to generate the PM's Top Twenty.

Correlation Between Predictors

Danny Tarlow was kind enough to give me some comments on a paper I'm writing about the work reported in this blog, and one of his suggestions was to look at whether the predictors I've tested are picking up on the same signals.  This is a significant question because if the predictors are picking up on different signals, then they can be combined into an ensemble predictor that will perform better than the individual predictors.  (Dietterich 2000) showed that

"...a necessary and sufficient condition for an ensemble of classifiers to be more accurate than any of its individual members is if the classifiers are accurate and diverse."

A classifier is accurate if is better than random guessing.  Two predictors are diverse if they make different errors.  Intuitively, an ensemble will perform better than the base predictors if the errors in the base predictors are uncorrelated and tend to cancel each other out.  Our predictors are all obviously accurate, but are they diverse?

To test this we can measure the correlation between the errors made by the different predictors.  If they are uncorrelated, then it is likely that we can construct an ensemble with improved performance.  I don't have the time and energy to test all combinations of the predictors I've implemented, but here are the correlations between the top two won-loss based predictors (Wilson, iRPI) and the top two MOV-based predictors (TrueSkill+MOV, Govan):

	Wilson	iRPI	TrueSkill + MOV
iRPI	0.99
Trueskill+MOV	0.93	0.93
Govan	0.95	0.95	0.98

Not unsurprisingly, the highest correlations are between the two won-loss predictors and the two MOV-based predictors.  But all of the predictors are highly correlated.  The least correlated (by a hair) are Wilson and TrueSkill+MOV.  Putting those two predictors into a combined linear regression or an averaging ensemble results in performance worse that TrueSkill+MOV alone.

On the other hand, perhaps using the best predictors is the wrong course.  Perhaps its more likely that the worst predictors are uncorrelated with the best predictors, and a combination of one of the worst with one of the best would be fruitful.

	Wilson	iRPI	TrueSkill + MOV	Govan
1-Bit	0.83	0.83	0.80	0.79
Winning Percentage	0.97	0.98	0.92	0.93

As this shows, even the 1-Bit predictor ("the home team wins by 4.5") is highly correlated with the better predictors, and using just the winning percentage shoots the correlation to 0.92+.  Adding these predictors to an ensemble with the better predictors also results in worse performance.

Of course, it's always possible that some combination of predictors will improve performance.  There's been some interesting work in this area -- see (Caruana 2004) in Papers.  But for right now I don't have the infrastructure to search all the possible combinations.

Experimenting with Recency

I wanted to take another look at the relative value of recent games, that is, whether prediction is more accurate if we base it upon only a team's recent performance instead of the entire season-to-date.  To do this, I calculated the Govan ratings for each team based upon the last "N" games, for various values of N.  Here are the results:

Predictor	N	MOV Error	% Correct
Govan	30	10.805	73.5%
Govan	25	10.963	73.1%
Govan	20	11.280	72.1%
Govan	15	11.980	70.2%

With N=30, this is essentially the same as using all the games to date.  Smaller values of N throw out the oldest games to use only N games.  The trend is clear; it seems that even the oldest games add useful information for prediction.

If using games from the very beginning of the season is useful in predicting games at the end of the season, perhaps using even older games would be useful.  Perhaps we should include (say) the previous season's games when predicting.   ("That's crazy talk!" I hear you say.  We shall see...)

It's fairly straightforward to modify my workflow so that it doesn't reset at the beginning of each new season.  I currently use games from the 2008-2009, 2009-2010 and 2010-2011 seasons.  If we run without resetting at the beginning of each new season (essentially treating the data as one long season), this is the comparative performance for our favorite two predictors:

Predictor	MOV Error	% Correct
Govan (normal)	10.80	73.5%
Govan (merged seasons)	11.04	73.4%
TrueSkill (normal)	10.88	73.3%
TrueSkill (merged seasons)	10.99	73.4%

Interestingly, performance does not suffer much from including previous seasons.  As you might expect, TrueSkill suffers less of a hit than Govan.   Since TrueSkill essentially updates a hypothesis with every game, it's better able to discard the contrary evidence from earlier games.

Now let's look at performance within a season, as I did in this post.  Here I've broken the season down into four quarters of ~1000 games each, and I show the performance both with and without using the previous season's games.  (This is really the last four quintiles of the season -- in both cases I throw away the first 1000 games of each season.)

Quarter of the Season	Govan (normal)	Govan (merged)	Improvement
1st	11.40	11.23	+1.5%
2nd	10.70	11.44	-6.9%
3rd	10.52	11.02	-4.8%
4th	10.05	10.89	-8.4%

Not unsurprisingly, using the previous season improves prediction during the first quarter of the season.  (TrueSkill shows the same pattern, improving by about 2.2% in the first quarter.)  Even though the previous season's performance isn't a good predictor, it is apparently better than starting everyone off with a clean slate.

This suggests that we should use the previous season's data until we have enough current season data to make good predictions.  We should be able to do this combining the recent games window and the merged seasons.  If we always predict using the (say) previous 30 games, and include the previous season, that should be close to what we want, although it might not throw away the previous season's games fast enough.  Sadly, I can't seem to get that to work (or rather, it works, but returns very bad results which make me think it's broken).

As an alternative, we can "prime" each season by including the last 1000 games of the previous season.  This has the disadvantage that the primer games impact the ratings for the whole season, but it's a simple approach and easy to implement:

Predictor	MOV Error	% Correct
Govan (normal)	10.80	73.5%
Govan (primed)	10.78	73.1%
TrueSkill (normal)	10.88	73.3%
TrueSkill (primed)	10.91	73.1%

Again if we look at the performance by quarters we see that performance in the first quarter games is much improved, but that's offset by poorer performance in the later quarters. That's a little trickier to implement. Generally speaking, it isn't always possible to "back out" a game from the ratings.  We can address that by "restarting" partway through the season without the primer games.  Here's what that yields:

Predictor	MOV Error	% Correct
Govan (normal)	10.80	73.5%
Govan (primed + restart)	10.74	70.7%
TrueSkill (normal)	10.88	73.3%
TrueSkill (primed)	10.94	70.5%

The result is a mixed bag.  MOV Error is improved by about 0.5% for Govan (which is really a 2% improvement in the first quarter games), but reduced by a similar amount with TrueSkill.  Meanwhile, % Correct drops rather dramatically for both ratings. 

In general, the evidence suggests that there is no benefit to limiting the number of current season games when calculating ratings, and there is mixed benefit in early season games from incorporating results from the previous season.

Conference Vs. Non-Conference

As a follow-on to this posting where I looked at how well the predictors worked over different periods of the season and noted some odd behaviors, I looked at conference versus non-conference games, to see if there was some difference in performance.  Here are the results:

Predictor	MOV Error	% Correct
TrueSkill -- Conference Games	10.689	72.10%
TrueSkill -- Non-Conference Games	11.539	76.39%
Govan -- Conference Games	10.583	72.17%
Govan -- Non-Conference Games	11.325	76.83%

This shows the same sort of split we see in early-season versus late-season predictions:  conference predictions are closer to the actual Margin of Victory, but more often on the wrong side of the contest.  Of course, most non-conference games are also early-season games, there's some interdependence in these results.  We can try to factor this out by looking at late-season non-conference games and early-season conference games:

Predictor	MOV Error	% Correct
TrueSkill -- Conference Games	10.689	72.10%
TrueSkill -- Early Conference Games	11.485	66.67%
TrueSkill -- Non-Conference Games	11.539	76.39%
TrueSkill -- Late Non-Conference Games	11.148	72.68%
Govan -- Conference Games	10.583	72.17%
Govan -- Early Conference Games	10.988	69.57%
Govan -- Non-Conference Games	11.325	76.83%
Govan -- Late Non-Conference Games	11.089	73.04%

This seems to show that it's really the early season versus late season that matters (and the predictors are particularly bad at early-season conference games).

One easy follow-up to this experiment is to train our predictor on only conference games (or only non-conference games) and see if this improves performance within the category.  I won't post the numbers, but there's no advantage in training on non-conference games when predicting non-conference games, etc.

None of this explains the oddity of MOV Error improving while % Correct simultaneously worsens, but at least there's some evidence that conference versus non-conference is probably not a big factor in prediction performance.

Another Experiment

I don't recall now what prompted me, but I recently decided to take a look at how the performance of the predictors works temporally.  The same way I broke the games down by mismatches as I did in this post, I would subdivide the games according to when they occurred in the season: early, middle, or late.

I have about 4000 games in the training data for each season (2009, 2010, 2011) so I actually broke those down into quarters to give me an even 1000 games in each portion of the season.  (I remind the reader that I remove the first 1000 games of the season from the training set because the ratings aren't yet reliable.  So when I talk about the first 1000 games in this posting, those are actually the second thousand games played in that season.)  I then tested the performance of the two best predictors: TrueSkill + mov adjustment, and the Govan ratings.  In this case, I think it's easier to look at a graph of the results rather than a table.  Let's start with the MOV Error by quarters of the season:

MOV Error By Quarter

As you might expect, the error goes down (performance improves) as the season progresses.  On average, the improvement is slightly more than 1 point.  (In 2009, both ratings perform slightly worse in the 4th quarter of the season, but the overall trend seems clear.)  Presumably more games leads to a more accurate rating and hence a more accurate prediction.

Now let's look at a similar chart for the percentage of correct predictions:

% Correct Predictions by Quarter

This chart is a complete curveball.  Performance at correctly picking the winner is by far best in the first quarter, drops dramatically through the third quarter, and then rebounds substantially in the fourth quarter.  This is completely unexpected, particularly in light of the MOV Error, which performs as we'd intuitively expect.

I can hazard some guesses as to what is going on, but none seem particularly explanatory.  More experiments would seem to be in order.

One question is whether the prediction performance is high in the first quarter because (1) the rating is only operating on a few games, or (2) the teams are playing differently (more predictably) in that quarter.  To test that hypothesis, I could restart the rating at the beginning of each quarter.  If (1) is true, then we'd expect to see similar performance in all four quarters.

Another thought is that teams play more non-conference games in the first quarter of the season.  To test this hypothesis, I could do a comparison of performance prediction on conference vs. non-conference games.

In any case, this is a very puzzling (and hopefully eventually enlightening) result!

An Idle Experiment

I exchanged an email with Dan Baker (aka Spartan Dan) in which we discussed how to measure performance for predictors.  He pointed me towards this posting where Ken Pomeroy looks at performance broken down into "bands" of predicted win percentages.  That's an interesting way of looking at the data, although it's only applicable to rating systems that predict a winning percentage (like Bradley-Terry).  I've done similar sorts of analysis in the past, and this spurred me to repeat some of those experiments.

I generated the usual test data for the TrueSkill rating system, but instead of testing against the whole data set, I filtered down to certain subsets.  (I also changed the parameters of the cross-validation slightly because some of the subsets are relatively small -- that's why the performance on the entire data set doesn't match the previous version.)  In the first experiment, I created subsets where the difference between the TrueSkill ratings for the home team and the away team was either greater than 40, less than -40, or in-between.  (This roughly corresponds to predicting a ten point win by the home team, a ten point win by the away team, or somewhere in-between.)  Here are the results for those subsets (as well as the results for the whole data set for comparison):

Predictor	% Correct	MOV Error
TrueSkill	73.4%	10.96
Delta TS > 40	95.7%	11.60
Delta TS < 40 && > -40	68.9%	10.85
Delta TS < -40	79.3%	10.71

There are a number of interesting results here.  First, home teams with a big ratings advantage rarely lose and we consequently have a very good winning percentage for those games.  However, our MOV Error is at its worst.  This might be because of blowouts, or more volatility in these games.  Second, our prediction rate in "close" games is very poor -- only slightly better than our naive 1-bit predictor (although it would presumably do worse on this subset).  However, our MOV Error is pretty good -- probably because it's an absolute measure, and close games are likely to have a tighter MOV spread.  Finally, we do a lot worse predicting games where the away team has the big advantage.  We (essentially) predict all wins by the away team, but in reality the home team manages to win more than 20% of those games.

Recall that we use linear regression to create an equation that predicts the MOV.  That equation looks something like this:

MOV = H_c * (Home Team's TrueSkill Rating) + A_c * (Away Team's TrueSkill Rating) + C

We can give some intuitive (if not perhaps completely correct) meanings to these coefficients.  C represents the "Home Court Advantage" -- it is the bonus (if positive) the home team gets for playing at home.  The ratio of H_c to A_c represents the relative advantage (or disadvantage) the home team has over the away team.

So let's compare the coefficients produced for each of the subsets:

Predictor	Hc	Ac	C
TrueSkill	0.249	-0.238	3.48
Delta TS > 40	0.249	-0.251	3.77
Delta TS < 40 && > -40	0.250	-0.235	3.29
Delta TS < -40	0.148	-0.164	-0.373

The first interesting thing that jumps out is the equation for big home underdogs, which is quite different from the other three.  In particular, if we think of C as the Home Court Advantage, it completely disappears when the home team is a big underdog.  Even worse for the home team, this is the subset where their relative advantage (H_c to A_c) is at its worst.  But somehow the home team manages to win 20% of these games! There's probably something interesting to be found in that anomaly...  Another interesting thing to note is that when home teams are big favorites, they actually slightly underplay their strength (relative to the away team) although this is somewhat compensated by a greater HCA.

This is far from a rigorous experiment, but it does illustrate that the overall performance of our model can obscure radically different performance on included subsets.  It also suggests that we might want to build our predictor to use different models (or entirely different approaches) for different subsets of the data.  (But interestingly, the "sum" of the three subset models actually slightly under-performs the single overall model.  So maybe this intuition is wrong!)  In particular, it might be worthwhile to start tracking the performance of our candidate models for "close games", since that's clearly the place where significant performance gains can be had.

An Experiment with TrueSkill

At the moment I'm looking at the TrueSkill rating system and thinking about how to incorporate margin of victory (MOV).  (In particular, I'm watching (and thinking about) Tom Minka's lectures from the Machine Learning Summer School 2009.  These lectures are a great resource, by the way, and well worth browsing.)  As the best of the ratings that don't use MOV, it seems reasonable that TrueSkill might be even better if it incorporated MOV.    I haven't yet formulated a mathematically sound way to add MOV to TrueSkill (I'm open to pointers) but that of course has not kept me from experimenting.

Recall that in TrueSkill we update the ratings for the two teams involved in a game by comparing the strengths.  If you win a game over a strong opponent, than that's good evidence that your rating ought to rise and your opponent's fall.  And if you win a game over a weak opponent, than that's not good evidence to change the ratings (because you were expected to win).

So how should we interpret MOV?  One reasonable approach is to say that a win by a large MOV is better evidence that your rating should rise than a win by a small MOV.  (For the moment we ignore "Running Up the Score" and similar problems with MOV.)  Referring back to how TrueSkill works, winning by a large MOV is therefore similar to beating a stronger team.  So perhaps we can incorporate MOV into the TrueSkill algorithm by adjusting our opponent's rating up or down based upon MOV (creating an "effective" rating) and then updating our own rating accordingly.

That turns out to be pretty straightforward to add to the algorithm, and gives these results:

Predictor	% Correct	MOV Error
TrueSkill + iRPI	72.9%	11.01
Govan (best)	73.5%	10.80
TrueSkill (w/ MOV)	73.3%	10.91

This turns out to work surprisingly well for a completely arbitrary hack.  Some playing around with the bonusing function shows that performance is slightly improved by using MOV*2 as the bonus:

Predictor	% Correct	MOV Error
TrueSkill + iRPI	72.9%	11.01
Govan (best)	73.5%	10.80
TrueSkill (w/ MOV)	73.3%	10.91
TrueSkill (w/ MOV*2)	73.3%	10.88

Other bonusing variants and tweaks don't show any improvement.  This performance is not quite as good as the Govan rating, but certainly shows some promise.

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:

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!

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:

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.

Trueskill

We'll now turn our attention to the first of the "RPI Alternatives" we will evaluate.  Like RPI, all of these approaches make use of only the won-loss record in rating teams.

The first approach is Microsoft's "Trueskill" rating system.  The Trueskill system was developed at Microsoft Research to rank players on XBox Live.  This has a number of unique challenges.  First, there are many players, so most players have not played against each other.  Second, many of the games on XBox Live are multiplayer or team games, and players may join or drop out of the game at different points in the game play.  Finally, Trueskill is in some sense intended to be a predictive system.  It's main use is to predict how competitive a game will be between two players.

As a rating system, Trueskill also has a couple of unique features.  For each player it calculates not only a rating, but also an explicit uncertainty in the rating.  After one game, Trueskill will provide a rating for the teams involved, but the uncertainty in the ratings will be high.  As more games are played, the uncertainties become less.

What happens when a player performs better or worse than expected?  Trueskill can either move the player's rating, or change the uncertainty, or some of both.  There is explicit provision in the Trueskill system to tune this tradeoff.

Finally, Trueskill also accommodates games that can end in a draw.

The Trueskill system is based upon Bayesian inferencing.  The fundamental ideas are not hard to grasp, but the details can be daunting.  Fortunately, Jeff Moser has provided a very clear tutorial on Trueskill, which you can find here.  Jeff also provides an implementation of Trueskill in C#, and was instrumental in helping me create the Trueskill implementation in Lisp, which you can download here.

College basketball is simpler than XBox Live in that we don't have to worry about multiplayer games or players dropping out before a game is finished.  So to test Trueskill for predicting college basketball games, I was able to implement the simplest Trueskill algorithm: one that deals with just two player games.

As mentioned above, Trueskill accommodates draws.  This is nice, since we showed earlier with RPI that it improved prediction accuracy to consider some games as draws.  It's worth noting that Trueskill treats draws somewhat differently than we did with RPI.  In the RPI tweak, we set an MOV cutoff and ignored games that fell below that cutoff.  In Trueskill, there is a similar cutoff that identifies drawn games, and these games are ignored when updating a team's rating.  However, Trueskill also uses the likelihood of a draw to control the impact a non-drawn game has on a team's ratings.  For example, if draws are very likely, then a non-drawn game has a big impact upon ratings.  This makes intuitive sense -- if it's very hard to get a decisive win, then that should be strong evidence that the winning team is better than the losing team.

To make use of draws, we need to tell Trueskill what point differential counts as a draw, as well as how likely draws are to occur.  I used the last three seasons of games to determine the likelihood that a game will be decided by "N" or fewer points:

Point Spread	Likelihood
1 Point	4.5%
2 Points	10.5%
3 Points	17.0%
4 Points	22.3%
5 Points	28.7%
6 Points	34.0%
7 Points	39.1%
8 Points	44.0%
9 Points	49.3%
10 Points	54.2%
11 Points	58.6%
12 Points	62.7%

We can then test with draws set at various levels to find the best performance.  We test here just as we did with RPI -- our main measure of performance is the error in predicted Margin of Victory (MOV):

Draw	Performance
2 Points	11.29
3 Points	11.24
4 Points	11.19
5 Points	11.16
6 Points	11.13
7 Points	11.13
8 Points	11.09
9 Points	11.10
10 Points	11.13

As this table shows, best performance is achieved with an amazingly high level of draws -- 8 points, which drops 44% of the played games from consideration.  The performance of the Trueskill algorithm at this setting is also signficantly better than our best RPI algorithm:

Predictor	% Correct	MOV Error
1-Bit	62.6%	14.17
RPI (infinite depth, mov-cutoff=1)	72.1%	11.30
Trueskill (draw=8 points)	72.8%	11.09

To this point, we've made no use of the uncertainty measure that the Trueskill algorithm provides.  And it isn't clear how to make use of it.  We're using the Trueskill ratings for each team as inputs to a linear regression, resulting in an equation that looks something like this:

MOV = 1.514*HTrueskill - 1.462*ATrueskill + 2.449

Adding the uncertainty measures to this regression doesn't seem like it will add any useful information for determining the MOV, and indeed, when they are added they get optimized out of the regression. Another approach is exemplified by the Microsoft's Leaderboard, which uses a "conservative" strength estimate calculated by subtracting three times the uncertainty measure from the rating.  Using this as the inputs to our predictor also fails to improve our predictive accuracy.  Similar experiments with adding the uncertainty to the home team and subtracting it from the away team, etc., all fail to provide any improvements.  So while the explicit uncertainty might prove to be useful for a more sophisticated predictor, it doesn't appear to provide any value for a simple linear regression.

Another area of tweaking we can look at for Trueskill is home court advantage (HCA).  As with RPI, the linear regression effectively adjusts for the home court advantage, but in this case manual adjusting might provide some additional benefits.  If we adjust for HCA by (say) subtracting points from the home team's score, it will affect which games are considered "draws" by the Trueskill algorithm, and this may lead to improved accuracy.  Here is the performance with the HCA set to various values, including the Dick Vitale Approach:

Predictor	% Correct	MOV Error
1-Bit	62.6%	14.17
Trueskill (draw=8 points)	72.8%	11.09
Trueskill (draw=8 points, HCA=2.5)	72.5%	11.13
Trueskill (draw=8 points, HCA=3.5)	72.4%	11.13
Trueskill (draw=1 point, Vitale)	70.0%	12.09
Trueskill (draw=8 points, Vitale)	70.8%	11.80

I could find no adjustment for HCA which improved the predictive performance.

The other tweaks we tried for RPI (such as weighting recent games more heavily) do not easily apply to the Trueskill algorithm.