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!

Govan Ratings

The next system will take a look at is based on [Govan 2009].  Govan calls this the "Offense-Defense Rating" but to avoid confusion with my own Offense-Defense Rating, I will refer to this system as the "Govan Rating."

The idea behind the Govan Rating is to generate an Offense and a Defense rating for every team based upon scoring.  Assuming that "Score_ij" represents the points scored by Team j against Team i, then the Offense rating for Team j is given by the formula:

Offense_j = (Score_1j/Defense₁) + ... + (Score_nj/Defense_n)

That is, Offense of Team J is the sum over all the teams of the points scored by Team J divided by the Defense rating of the opposing team.  When the opposing team is a good defender (i.e., has a low Defense rating), then Team J gets a relatively higher Offense rating.  When the opposing team is a poor defender (i.e., has a high Defense rating), then Team J gets a relatively lower Offense rating.

The formula for calculating the Defense rating for Team I is the reverse:

Defense_i = (Score_i1/Offense₁) + ... + (Score_in/Offense_n)

Again, you are rewarded for holding down the scoring of teams with potent offenses, and penalized for giving up points to teams with weak offenses.

Since Offense and Defense are interdependent, they must be iteratively approximated.  The method varies slightly from what we've seen before.  In this case, we will estimate the (k)th iteration of Offense using the (k-1)th iteration values for Defense, and then the (k)th iteration of Defense using the (k)th iteration values for Offense that we just calculated (not the (k-1)th values as you might have expected).

Not unsurprisingly, this can be expressed as matrix calculations.  See the paper for details.

One significant problem with this system is that the ratings do not (necessarily) converge if every team doesn't play every other team.  We can solve this by adding a phantom tie game between every pair of teams. 

There are a couple of interesting features of this system.  First, this system doesn't consider Won-Loss records at all; you get rewarded equally regardless of whether you score 80 points in a loss or in a win.  Second, this rating system rewards teams that play more games.  A team that plays 30 games is going to have a higher Offense rating than one that plays only 22.

So how does Govan perform?

Predictor	% Correct	MOV Error
TrueSkill + iRPI	72.9%	11.01
IMOV	72.7%	11.05
Govan (baseline)	71.8%	11.44

The baseline performs about as well as the improved LRMC.  One potential problem here is that the linear regression can only combine the Offense and Defense terms additively.  Given how they are defined, we might guess that Offense/Defense would be a better predictive rating than Offense + Defense.  If we define a combined rating Combined = Offense/Defense and add that to the model we get a slight improvement:

Predictor	% Correct	MOV Error
TrueSkill + iRPI	72.9%	11.01
IMOV	72.7%	11.05
Govan (baseline)	71.8%	11.44
Govan (w/ Combined)	71.8%	11.43

For the model above, I had set the phantom tie game to a score of 68-68.  (68 is the average score in NCAA basketball, so I reasoned this would perturb the ratings the least.)  [Govan 2009] uses small numbers for this tie game, so as an experiment, I set the score of the phantom tie game to 1-1, and then to 0.1-0.1:

Predictor	% Correct	MOV Error
TrueSkill + iRPI	72.9%	11.01
IMOV	72.7%	11.05
Govan (baseline)	71.8%	11.44
Govan (w/ Combined)	71.8%	11.43
Govan (w/ Combined; 1-1)	72.2%	11.26
Govan (w/ Combined; 0.1-0.1)	72.6%	11.21

This provides a significant performance improvement, although not yet competitive with the best of breed.

As mentioned above, one of the odd features of this system is that it rewards playing more games.  We can try to address that by dividing the Offense and Defense ratings by the number of games played:

Offense_j = (1/N_j)* [(Score_1j/Defense₁) + ... + (Score_nj/Defense_n)]
Defense_i = (1/N_j)* [(Score_i1/Offense₁) + ... + (Score_in/Offense_n)]

This will hopefully remove any reward for playing more games while still permitting the solution to converge:

Predictor	% Correct	MOV Error
TrueSkill + iRPI	72.9%	11.01
IMOV	72.7%	11.05
Govan (w/ Combined; 0.1-0.1)	72.6%	11.21
Govan (w/ Combined; 0.1-0.1, normalized)	73.5%	10.80

And so it does, providing a big boost to performance -- making this version of Govan the best performing rating so far!

Tweaks like eliminating close games or blowouts don't really apply to this rating, because the rating is based solely on points scored, and not the game outcome.  Nonetheless, it's worth a quick experiment to see if ignoring close games has a positive effect:

Predictor	% Correct	MOV Error
TrueSkill + iRPI	72.9%	11.01
Govan (best)	73.5%	10.80
Govan (mov-cutoff=2)	73.5%	10.82

Answer: no.

We'll stop for now with tweaking this rating.  One thing we'll want to look at in the future is combining this with other ratings.  Because Govan does not use the Won-Loss record, it may capture information not captured by ratings like TrueSkill that don't consider scores at all, and so properly combining the two might improve the overall performance.  Or not -- that's an experiment for another day!