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.

Testing Methodology Redux

For the RPI experiments, I used a testing methodology that tried each RPI variant against the same set of approximately 10K training games and 500 test games.  This had the advantage of being fast and repeatable.  However, it has the disadvantage that performance on the 500 test games might not accurately estimate the general performance. That is, we might have a tweak that (for whatever reason) happens to perform very well (or very poorly) on that particular set of test games.  As we move forward into other ratings and more complex models, we'd like to avoid that problem.

To do that, we can test our algorithms on several different test sets.  The general approach is called cross-validation.  The basic idea is to split the input set into a large training set and a smaller test set, train the algorithm on the training set, test it on the test set, and then repeat for a new training & test set.  The more test sets we use, the closer we can come to accurately estimating the true performance of the algorithm.  The drawback is that testing becomes slower because of the repeated training-testing loop.

RapidMiner provides cross-validation as a standard operator.  This picture shows the top-level process flow I am using in testing:

The flow begins at the top left, where the entire set of game data is read in from a CSV (comma-separated values) file.  Each game has the date, home team, away team, scores, etc., as well as the computed ratings to be tested -- for example, we might have the basic RPI rating for each team.  (The computed ratings are produced by a Lisp program that must be run before the cross-validation.)

The game data is then subject to some preprocessing to get it ready for use in the predictive model.  The first step is to generate a unique ID for each game.  (This is useful if we split the data from a game into two parts and want to later re-join the parts.)  Next is a "Generate Attributes" operator, which takes the home team score and the away team score and creates a derived attribute called MOV (the Margin of Victory).  The "Set Role" operator then marks this new attribute as the "label" in our data -- the label is what we are trying to predict.  Finally, we use a "Select Attribute" operator to select only those attributes in the game data that we want to use as inputs to our predictive model.  For example, if we are testing RPI, we'd select only the home team's RPI and the away team's RPI (along with the label) as inputs to the model.

The yellow Validation operator encapsulates the cross-validation process.  It takes as inputs the preprocessed training data and outputs a model, the same training data, and some computed performance estimates.  In RapidMiner, we can drill down inside this operator to look at the cross-validation process:

This process is divided into two halves: Training and Testing.  RapidMiner takes care of splitting the data into a training set and a testing set.

The training set is fed into the Training side of the cross-validation as the input.  The Training side takes this input and produces a model.  In this case, we're using a Linear Regression operator that takes the training data and produces a linear regression that best fits the input attributes (Home RPI, Away RPI) to the label data (the Margin of Victory).  The model is then output from the Training side and passed over to the Testing side.

The Testing side of the cross-validation takes the model and the test data and outputs performance values.  In this case, we use the "Apply Model" operator to apply the model from the Training side to the test data.  This produces "labelled data" -- the test data with an added attribute called "Predicted(MOV)".

In this case, I want to keep track of two measures of performance: the number of correctly predicted games, and the root mean squared error in the MOV prediction.  To do this, a copy is made of the labelled data using the Multiply operator.  One copy is sent down to the yellow Performance operator at the bottom of the figure.  This is a built-in RapidMiner operator that calculates root mean squared error from the labelled data.  This result is then pushed out as a performance measure for this model.

The other copy of the labelled data is sent into the pink boxes at the top of the figure.  These boxes rename the "Prediction(MOV)" attribute, generate a new attribute which is 1 if the prediction was correct and 0 otherwise, and then aggregates (sums) the new attribute.  This number is then converted to a performance measure and pushed out as another performance measure for this model.

When this process is run, RapidMiner splits the data into training and test sets according to the parameters of the Cross-Validation operator (in this case, I'm doing 100 cross-validations), runs the Training/Testing process on each data set, and averages the performance measures across all the sets:

RapidMiner can also produce a variety of plots of attributes and results, such as this:

This can be handy for debugging or to visualize the data.

RPI Recap

I want to take a posting to recap the various approaches we've looked at over the past few weeks.  Although I've been applying them to the RPI algorithm, I believe they'll continue to be generally useful as we look at more complex prediction approaches.

(1) Measure

The initial insight was to have a clear notion of what we're trying to achieve and then select objective metrics to measure progress.  The importance of this was repeatedly evident as we looked at various RPI tweaks.  In many cases, "obvious" improvements to RPI turned out to be no improvement at all.  In another case, we corrected a math error in RPI that turned out not be an error at all (or at any rate didn't improve predictive performance). 

(2) Home Court Advantage

There is a proven and significant home court advantage in college basketball.  We looked at several ways to account for HCA, but in the end our predictive model captured it better than we could with an apriori solution.  For example, the linear regression for one of our RPI tweaks looked like this:

MOV = 85.414 * Hrpi - 80.508 * Arpi + 1.580

The different coefficients for the home team's RPI (85.414) and the away team's RPI (80.508), as well as the constant bias (1.580) combine to model the home court advantage.

The lesson here is that the HCA is important to accurate prediction, and we need to ensure that either our model accommodates it naturally (as in the case above) or that we otherwise account for it in our data.  For the latter case we looked at a number of possible tools: weighting the home record differently, applying a point bias to the home team, or splitting a team into a "home team" and "away team" component.

(3) Strength of Opponent

One of the paradoxical challenges of assessing a team's strength is that you need to know the strength of the teams it has played.  It's a classic Catch-22.

The RPI approach to breaking this death spiral is to base the strength metric on some other measure.  This is what RPI does -- RPI tells us how strong a team is, but RPI itself is eventually dependent on won-loss records.  By recursively finding the winning percentage for opponents, and opponents' opponents, RPI tries to estimate the true strength of a team.

One useful improvement we found on this technique is to carry out this recursion "infinitely" by using an iterative solution.  We can use another measure as an initial estimate of our strength metric, and then iteratively adjust the metric until we get the values that best match the actual performance so far.

(4) Data Filtering

Our prediction algorithms are based largely on past performance.  One approach we used with some success for RPI was to filter the past performance to eliminate games that reduced our prediction accuracy.  In the case of RPI, we found in it was useful to eliminate games where the MOV was 1 point.  In general, we may want to look at a variety of different filtering approaches (e.g., eliminate blow-out games, pre-season tournament games, etc.).

(5) Modeling Changing Performance

As we build predictive models, we have to consider whether a team's performance changes substantially over the course of a season.  (It clearly does so from season to season.)  If it does, then our predictive accuracy might be better if we discount older games when building our models.  Another intriguing possibility is whether we can identify specific events where a team's performance changed substantially, e.g., when we notice the minutes played by specific players changes signficantly due to an injury or other reason.

In the case of RPI, we weren't able to improve our accuracy by weighting recent games, but other methods or different approaches may yet prove valuable.

Next up we'll start taking a look at some alternative methods for rating teams that use only won-loss records.  There are a number of candidates, and we'll be looking to see if any of them  provide a significant advantage over our (tweaked) RPI.

The Recency (Non-)Effect

Our final RPI tweak (unless I'm lying again) will look at the impact of recent results on predictability.  It's reasonable to suppose that a team's level of performance might change during the season -- that is, it might get better or worse as the season goes along.  In this case,recent games might be a better predictor of future performance than older games

To test this notion, we can modify our RPI calculations so that they take into account only the last "N" games.  For some representative values of "N", that yields these results:

Predictor	N	% Correct	MOV Error
1-Bit		62.6%	14.17
RPI (nw, 15+15+70)		76.8%	11.46
RPI (nw, 15+15+70)	4	67.6%	12.52
RPI (nw, 15+15+70)	8	72.8%	11.89
RPI (nw, 15+15+70)	16	74.2%	11.47

Restricting the RPI calculations to the most recent games has a strong negative impact on predictive power.  Of course, this method is fairly drastic: it gives 100% value to the most recent games and 0% to anything older.  A more nuanced approach would count the most recent games more, but not discount entirely the older games.  Something like a weighted moving average would be ideal, but it isn't entirely obvious how to apply that to RPI.  Instead, we'll take the approach of counting the most recent games more than once.  That is, we'll treat each team as if it played it's most recent games multiple times (with the same results).  This will have the effect of weighting those games correspondingly more.

This table shows the impact of repeating some number of recent games some number of times (in addition to counting all games once):

Predictor	N	Repeats	% Correct	MOV Error
RPI (nw, 15+15+70)	4	1	72.8%	11.63
RPI (nw, 15+15+70)	8	1	74.2%	11.56
RPI (nw, 15+15+70)	16	1	74.6%	11.49
RPI (nw, 15+15+70)	4	1/3	73.6%	11.64
RPI (nw, 15+15+70)	8	1/3	75.4%	11.58
RPI (nw, 15+15+70)	16	1/3	75.2%	11.51
RPI (nw, 15+15+70)	2	2	70.6%	12.49
RPI (nw, 15+15+70)	1	2	66.2%	12.82

In no case that I could find did weighting recent games improve performance over the baseline.  Putting emphasis on a small number of recent games is particular bad; this suggests that if teams do change performance over the course of the season it is only slowly.

Next time (unless something shiny distracts me again), we'll sum up the various tweaks we've tried with RPI.

MOV Cutoff Filter

The next tweak we'll look at for RPI goes back to our previous discussion about the limits of prediction.  We noted there that the last possession of the game could swing the final game score by 6 points.  Even if it's hard to quantify exactly, there's a certain random component in final game scores.  That's particularly a concern for rating systems that rely only on won-loss records, because a swing of a few points in a close game could change a game from a win to a loss.  Intuitively at least, we might want to discount close games when calculating RPI, under the theory that they're not really good evidence that one team was better than the other.

The easiest way to do this is to filter out all games where the final MOV was less than some threshold when computing a team's RPI.  Making that change and applying it with various thresholds to our current best "% Correct" RPI variation gives these results:

Predictor	% Correct	MOV Error
1-Bit	62.6%	14.17
RPI (unw,15+15+70)	75.4%	11.49
RPI (nw, 15+15+70, mov-cutoff=1)	76.8%	11.46
RPI (nw, 15+15+70, mov-cutoff=3)	75.4%	11.56
RPI (nw, 15+15+70, mov-cutoff=8)	73.4%	11.62
RPI (nw, 15+15+70, mov-cutoff=12)	70.0%	11.98

Filtering out all games that were decided by 1 point provides a big improvement in "% Correct" and a small improvement in "MOV Error". It's also interesting to note how resilient RPI is to removing games. MOV cutoff = 12 removes more than 40% of the games and only introduces a few percent more error.

We can try the same technique with our current best "MOV Error" variation (the infinitely deep RPI):

Predictor	% Correct	MOV Error
1-Bit	62.6%	14.17
RPI (improved)	74.6%	11.33
RPI (improved, mov-cutoff=1)	74.2%	11.31
RPI (improved, mov-cutoff=3)	74.6%	11.43
RPI (improved, mov-cutoff=8)	73.4%	11.36
RPI (improved, mov-cutoff=12)	72.0%	11.79

Again, an MOV cutoff of 1 provides a (small) improvement in the MOV Error.

It turns out I lied in the last post when I said the MOV cutoff would be the last tweak we examined for RPI.  In the next posting, I'll take a quick look at calculating RPI using a rolling window that only counts the last "N" games, to see if there's a usable "recency" effect in teams' performances.

A Tale of Two Demons

We now turn our attention to one of the most vexing aspects of RPI, illustrated this season by the Tale of Two Demons:  the first being the DePaul Blue Demons and the second being the Northwestern State Demons.

DePaul University finished the season 7-24 and a miserable 1-18 in conference.  DePaul's wins included 4-25 Chicago St., 8-21 Northern Illinois and 9-21 Central Michigan.

In contrast, Northwestern St. finished the season 16-13 with a respectable 10-7 record in conference.  They split home-and-home with Southland East Division champion McNeese St. and came within 1 point of winning the conference tournament and advancing to the NCAAs.

Yet curiously, DePaul has an RPI of 0.4590 and Northwestern State an RPI of 0.4566!  How does this happen?

Recall the oft-cited formula for RPI: 

RPI = (WP * 0.25) + (OWP * 0.50) + (OOWP * 0.25)

The biggest factor in this equation is the Opponents' Winning Percentage.  But critically, the opponents' winning percentage is calculated from all of a team's opponents.  So DePaul University benefits more from their 18 losses to strong Big East opponents than Northwestern State does from it's winning record in the Southland Conference.

No doubt when the NCAA concocted this aspect of the RPI formula, they were thinking of the case where a team has run up a good record against a bunch of patsies.  In that case, the team's RPI gets docked because the OWP is low; and that makes sense because those are also (mostly) opponents the team has beaten.  (The NCAA might also have been intentionally motivating teams to play strong out-of-conference schedules.)  But it certainly seems counter-intuitive to give a team more credit for being beaten by good teams than for beating mediocre teams.  And surely it makes for worse predictability.

Doesn't it?

Well, time to roll out the code and test.  A reasonable first approach is to calculate OWP as the average of all the opponents a team actually beat, rather than all the opponents.  (A similar reasoning applies to OOWP.)  Let us try that approach using our current best RPI formula as well as the "Infinite Depth" RPI:

Predictor	% Correct	MOV Error
1-Bit	62.6%	14.17
RPI (unw,15+15+70)	75.4%	11.49
RPI (unw,15+15+70,winners)	72.0%	12.20
RPI (infinite)	74.6%	11.33
RPI (infinite,winners)	74.0%	11.97

In both cases, this change makes for a worse predictor!  That's hard to comprehend.  Essentially, this says that losing to good teams makes a team more likely to win future games.  While I can certainly come up with a rationalization for that (e.g., playing good teams makes you a better team, even if you lose), it's hard to put much faith in it.  Still, the numbers don't lie.

As a second approach, we can break out the OWP for both the opponents we've beaten as well as the opponents that beat us.  So we'll have a "Winners OWP" and a "Losers OWP".  Instead of completely dropping the OWPs of the teams that beat us, we can include them as a less-weighted factor. Weighting the beaten opponents by about 3x the "lost to" opponents does improve performance over just the beaten opponents (to 369/11.47 for the unweighted, 15+15+70 version of RPI) but not enough to make it better than the standard versions.  So (at least for this approach) we have to conclude that RPI may be right about the relative strengths of the DePaul Blue Demons and the Northwestern St. Demons.  Apparently playing good opponents, even if you lose to them, makes you a stronger team.

We've about beaten RPI to death at this point, but we'll take a look at one more tweak before moving on to look at some other ratings that also make use of only won-loss records.

Infinitely Deep RPI

In the previous posting, we looked at extending the "depth" of RPI to an additional level -- that is, including OOOWP in our RPI calculation.  In this posting, we'll look at extending RPI to "infinite" depth.

We can view the RPI for a team as having two components.  The first is a measure of the team's strength, and the second is a measure of it's opponent's strength:

RPI = (Team's Strength) + (Team's Opponents' Strengths)

The standard RPI formula estimates the first term with WP and the second term with OWP and OOWP.  But a better estimate of a team's strength is the RPI itself, so we could use that instead, at least for the opponents:

RPI = (Team's Strength) + (Average of Team's Opponents RPIs)

But now we have a weirdly self-referential equation:  Calculating Duke's RPI will involve calculating UNC's RPI which will involve calculating Duke's RPI, ad infinitum.

We can solve this sort of self-referential formula iteratively -- that is, we can calculate an initial RPI estimate for all the teams and then repeat that process using the latest RPI estimates at each step until we reach an answer.  There are two requirements for this to be successful.  First, we need "bootstrap" values to get ourselves started, and secondly, we need to structure our formula so that the answers converge.

Conveniently for us, Andrew Dolphin has already done the hard work of determining a formula that meets those criteria:

RPI = (WP-0.5) + (Average of Team's Opponents RPIs)

so all we have to do is calculate.  Plugging this formula into our framework and testing gives us:

Predictor	% Correct	MOV Error
1-Bit	62.6%	14.17
RPI (unw,15+15+70)	75.4%	11.49
RPI (infinite)	74.6%	11.33

This gives us slightly better performance (in MOV Error) than the RPI that stops at OOOWP, suggesting that the standard RPI formula depth (to OOWP) is probably sufficient for our purposes.

Next we'll look at one of the most perplexing oddities of RPI.