Reversing the Data?

Over on Reddit's machine learning subreddit, a user posed this question (paraphrasing):

For my basketball predictor, I could double the number of training examples by creating new examples with the Home and Away teams swapped.  Would it make sense to do that?

That's an interesting thought.

The first concern is that you can't just swap Home and Away.  No one is entirely sure why, but home teams play differently (and better) than away teams.  In NCAA basketball, the Home Court Advantage (HCA) is between 4 and 5 points.  What's more, all of a team's statistics are typically different for their home games.  There's sometimes even a home court effect for neutral site games.  In particular, the "home" team in NCAA Tournament games does better than you would expect -- even when you adjust for them being the better team.  (In the Tournament, the better-seeded team in the matchup is the home team.)  If you just blindly swap Home and Away, the newly created games are going to be bad training examples because they won't reflect what would happen in a real game with a swapped matchup.

But let's assume that there is no difference between Home and Away.  In that case would it be valuable to swap Home and Away to create new training examples?

Let's look at a simple case.  Suppose that our training examples consist of a strength rating for each team (S1, S2) and the margin of victory (MOV).  Here's our very small training set:

S1, S2, MOV 
20, 18, 2
14, 28, -14

Based upon this training data, we'll build a (perfect) model that predicts MOV = S1 - S2.

Now let's augment the training set by adding new games where S1 and S2 are swapped and MOV is negated.

S1, S2, MOV 
20, 18, 2
14, 28, -14
18, 20, -2
28, 14, 14

Based upon the new training data, we'll build the exact same model!

That happens because we didn't add any new information to our training set.  We added new examples, but they didn't contain any new information. They just repeated existing information transformed in a way that was irrelevant to our model.

I suspect this will always happen if (1) the data transformation is perfect, and (2) the machine learning model can "see through" the transformation.

An example of modifying the training set where the data transformation is not perfect is boosting.  In boosting, we duplicate SOME of the training examples, and that leads to a different model.  If we duplicate all of the training examples, the transformation is perfect and there's no change to the learned model.  It's only duplicating some of the examples that is key to boosting.

A situation where the machine learning model cannot "see through" the transformation is using non-linear transformations with a linear model.  For example, if we have a data set where the data is arranged in a circle, a linear regression will not model the data well because it always produces a straight line.  However, if we apply a polar coordinate transformation on the data the circle will become a line, and the linear regression will be more effective.

My guess is that swapping Home & Away to create new training examples isn't an effective technique for NCAA Basketball.  However, I encouraged the original poster to go ahead and give it a try.  It's a fairly easy experiment, and who knows, my intuitions may be wrong!

(And if they are, I'm totally stealing the technique.)

Top Twenty (1/5)

I had email today asking about my Top Twenty.  I've been lax about doing that this year, but here's the ratings as of today:

Position	AP	Team	Rating
1	1	Kentucky	31.70
2	22	Ohio State	30.72
3	2	Duke	30.62
4	3	Virginia	30.18
5	4	Wisconsin	30.00
6	18	North Carolina	29.80
7	13	Notre Dame	29.78
8	5	Louisville	29.61
9	6	Gonzaga	29.51
10	9	Utah	29.24
11	10	Texas	29.23
12	8	Villanova	29.06
13	14	West Virginia	29.05
14	NR	Butler	28.62
15	7	Arizona	28.61
16	16	Oklahoma	28.60
17	NR	Illinois	28.45
18	NR	Michigan State	28.42
19	NR	Baylor	28.40
20	11	Maryland	28.30

I've included the AP rankings for comparison.  Kentucky is very strong -- as much stronger than the #2 than the #2 is of #7.  The PM likes Ohio State, North Carolina and Notre Dame much more than the poll.  Conversely, it doesn't think as much of Arizona, Villanova or Maryland.  Butler is probably the biggest darkhorse in this list, although they did receive votes in the AP poll.

The Effect of Additional Data on Performance

I've been wondering whether having more training data (i.e., additional seasons of games) would further improve my predictor.  This is problematic, because I already have data back to when the 3 point shot was introduced in the 2009-2010 season, so I can't actually get any more usable data.  But the question persisted, so I did a quick and dirty experiment to try to characterize how much improvement I'll see with additional data.

I trained a model on differing amounts of training data and tested it on the entire training set.  Ideally, I'd do this as some sort of cross-fold validation, picking different slices of the data for training, but I didn't want to spend the time that would require, so I just did each trial once.  So there's necessarily a lot of fuzziness in these results, but I still think the result is instructive.  The plot of error versus amount of training data looks like this:

That's error along the Y axis and number of training examples along the X.  You can see that error falls fairly steeply for the first 10K or so training examples and then begins to level off.  (Although it continues to slowly decrease.)  Eyeballing this chart suggests that additional data isn't likely to provide any big improvement.

If you're building your own predictor, this suggests that you should try to get at least 15K games for training data.  Depending upon how many games you throw out from the early season, that's around 3 full seasons of games.

This also shows the folly of trying to build a Tournament predictor based upon past Tournament games.  At 63 games a year, you'd need about 238 years of Tournament results to get a decent error rate :-).

The Prediction Tracker

This is just a quick note to say that this season I've been submitting predictions to The Prediction Tracker.  This site tracks the performance of a number of rating / prediction sites.  Current standings as of today look like this:

                                                                  Mean        Straight    Against
                           Straight  Against    Mean     Mean     Square        Up        Spread
                              Up     Spread     Error    Bias     Error       W     L     W     L

  Opening Line               0.77321  0.52652  8.82583 -0.12012  150.521    1016  298    268   241
  Dokter Entropy             0.76173  0.52541  8.79621 -0.15383  126.594    1055  330    703   635
  Line                       0.76170   .       8.63633 -0.07785  121.524    1042  326      .     .
  Ashby AccuRatings          0.74982  0.50901  8.86946  0.51996  127.529    1034  345    650   627
  StatFox                    0.74982  0.50000  9.15083  0.18088  135.416    1034  345    629   629
  System Average             0.74946  0.49440  8.92108  0.07232  128.329    1038  347    662   677
  Sonny Moore                0.74764  0.51311  9.30695  1.43590  139.909    1031  348    685   650
  NetProphet                 0.74661  0.53379  8.92028 -0.17446  126.397     551  187    387   338
  Sagarin Rating             0.74619  0.49625  9.16057 -0.02549  134.504    1029  350    661   671
  DRatings.com               0.74566  0.49234  9.43660 -1.43057  147.705     988  337    611   630
  Sagarin Predictor          0.74547  0.49737  9.11497  0.02793  133.947    1028  351    663   670
  ComPughter Ratings         0.74032  0.51709  9.53151  0.20241  148.497     841  295    575   537
  Sagarin Golden Mean        0.72806  0.49512  9.81426  0.07640  154.552    1004  375    659   672
  Sagarin Elo Score          0.71501  0.50113  10.2929  0.17347  169.295     986  393    668   665

I optimize my predictor on RMSE, so I'm pleased to see that I have the best performance in that metric of the tracked predictors.  I'm also doing the best of the predictors against the spread, although that performance is a little higher than I'd expect from my own testing so I won't be surprised if that trends down.  It's interesting to note that my predictor is about middle-of-the-pack for predicting the winner straight up and also not very good on Mean Error.

I only submit picks once a week on Monday, so that hurts my performance a little bit.  The predictions for the Saturday games are five or six days stale, which probably costs me 0.1 or so in RMSE.  (But for all I know the other predictors have the same problem.)

Some Miscellany

A few miscellaneous things I've experimented with recently.

At some point over the past few years I snagged a dataset which had the locations (latitude and longitude) of many of the Division 1 arenas.  I filled out the dataset and added in the date the arenas were constructed.  I also started grabbing the attendance numbers for games.  With the locations of all the team arenas, I can calculate the travel distance for Away teams.  (For Neutral site games, I just use a generic 500 mile travel distance for both teams.)  I was then able to feed all this data into the predictor.

There's a small correlation between travel distance and performance; teams that travel further generally perform more poorly.  But the effect is small, and the impact upon prediction accuracy is not significant.

Attendance numbers correlate positively with performance -- teams that get lots of fans tend to do well.  Cause and effect are probably reversed here -- fans turn out to see good teams.  Again, there's little benefit to prediction accuracy from the attendance numbers, probably because that information is already captured in the other statistics that describe how good the team is.  (If attendance was a good predictor it would be problematic, because we don't usually know the attendance numbers until the game is over!)

There's also a weak positive correlation between the date an arena was built and how well the team performs.  This is probably because good teams get new arenas.  For example, after winning the National Championship, the Maryland basketball team moved out of the rickety on-campus gym and into a shiny new arena. 

On a different note, I also started calculating the variance for team statistics and using them for prediction.  Variance tells us how much a variable is changing.  Imagine two teams that both average 10 offensive rebounds per game.  Team A has gotten exactly ten offensive rebounds in every game.  Team B has gotten 0 offensive rebounds in half their games, and twenty in the other half.  Their averages are the same, but Team B has a much higher variance.

One of the obvious ways to use variance is to quantify "confidence".  We might be much more confident in our prediction about a team that has very little variance (i.e., performs very consistently) than our prediction about a team that has a lot of variance.  I've had some success with this (particularly for predicting upsets in the NCAA tournament) but it's not an area where I've yet done a lot of experimentation.

But interestingly enough, it turns out that variance has some value as a direct predictor of performance.  In some cases, variance is a good thing -- a team with high variance in some statistic does better than a team with low variance.  In other cases, it's the opposite.  I've notice this in the past with some statistics (like Trueskill) that produce a variance as part of their calculation, but I decided to calculate variance consistently for all the statistics and test it for predictive value.

The results were mixed.  Some of the variance calculations were statistically significant and were selected by the model.  On the other hand, they didn't significantly improve accuracy.  I ended up keeping a number of the variance statistics because they represent a different aspect of the data, and I hope that means they'll make the model more consistent overall.

Other Approaches to Boosting

In my previous post I talked about boosting.  Boosting tries to improve the accuracy of a model by increasing the importance ("boosting") the training examples where the model has the most error.  Most machine learning toolkits include some form of boosting (often AdaBoost).  If you're not using a toolkit, it's pretty easy to manually implement a simple form of boosting.

To do this, train your classifier and then run it on all the examples of your training set.  You now have a training set with predicted outcomes and actual outcomes.  You can use this information to find the training examples with the most error.  If you're predicted the margin of victory (MOV) of a college basketball game, those are the training examples where the prediction is most different from the actual outcome.

(As an aside, this is most straightforwardly measured as the absolute value (or square) of the difference between the prediction and the actual outcome.  But you might also consider measuring this as a percentage error, if you think that being off by 1 point when you predict a 1 point victory is worse than being off 1 point when you predict a 20 point victory.)

Now you can take the worst predictions and duplicate them in the training set (so that they effectively count double) or even use them as the training set for a new predictor.  (Some machine learning models allow you to explicitly assign a weight to each training example.  In that case you can make them worth (say) 150%.) 

For my predictor, I have about 28,000 games in the training set.  I did an experiment where I took the worst 5600 (~20%) predictions and duplicated them in my training data.  Then I trained a new predictor on this "boosted" data and checked its accuracy.  I found a very small improvement in accuracy.

Why doesn't this approach boost accuracy for this problem?  I speculate that most of the games with large errors are games where "luck" skewed strongly towards one team.  Maybe one team shot 70% on their three-pointers, and the other team missed all their free throws.  Or one team just had a slightly bad night all-around and the other team had a slightly good night all-around.  By definition these sorts of events are unpredictable, so it doesn't benefit our model to try harder to predict them.  There's nothing useful in that data for the model to learn.

This insight suggests another approach.  If the worst predictions are in fact unpredictable, it might benefit us not to skew our training by trying to predict them.  We can do this by removing them from our training set (or de-weighting them if our model permits that).  I've never seen this approach suggested in the literature, so I don't have a name for it, but I'll call this "Deboosting."

We can create a deboosted training set in much the same way as a boosted set, except deleting rather than duplicating the worst predictions.  I did this and checked its accuracy.  Again, this shows only a slight improvement in accuracy.

So why doesn't this approach improve accuracy?  I suspect the answer is that the errors in the worst predictions are essentially random -- some in one direction, some in another.  So the games are unpredictable, but there's little net effect on the model when we train with these examples, because they tend to cancel each other out.  So removing them doesn't have as much impact as we might naively expect.

You can also consider doing similar things with the best predictions.  Removing the best predictions is a form of boosting (because it effectively increases the weight of the worst predictions) and duplicating the best predictions is likewise a form of deboosting.  You can also experiment with combinations, such as removing the worst examples and duplicating the best examples.

Finally, you can experiment with boosting approaches that make use of your knowledge of the problem domain and/or of attribute values to select the examples to boost.  As a simple example, maybe accuracy is improved by boosting the value of all non-conference road games.  Or by boosting examples where one team is much stronger than the other team (or conversely, where teams are very evenly matched).  There's a lot of room for creative speculation!

Other Meta-Classifier Approaches

In previous posts, I've talked about hyper-parameter tuning and ensemble learning.  The appeal of these techniques is to get something for nothing.  Without any real effort, they can (in theory) turn your inaccurate models into more accurate models.  Hyper-parameter tuning and ensemble learning aren't the only approaches to improve the accuracy of a base classifier.  Another commonly used approach is called "boosting."

Imagine that you have a model that predicts the final margin of victory (MOV) of a college basketball game.  If you ran this model on a bunch of training examples, you could calculate the error for each example (the actual MOV minus the predicted MOV).  You could then try to train a second model to predict that error.  And if you could do that, your combined prediction (the predicted MOV from the first model + the predicted error from the second model) would be better than your first model.  This idea is known as gradient boosting (or additive regression).

However, to be useful, there has to be something that the gradient boosting can find in the errors from the first model.  To understand why this is important, consider using gradient boosting with linear regression.  The linear regression algorithm produces the best linear solution to the data.  There's no other solution which will yield smaller errors.  So if you try to fit a second linear regression to the errors that are left behind, you get no improvement over the original model.  (Because no improvement is possible.)

There are two ways to overcome this limitation.  The first is to use a weaker base model.  That may seem non-intuitive, but it has the nice property of automatically turning a weak model into a stronger one.  (And in fact gradient boosting is usually applied to tree models for just this reason.)  The second approach is to use a different type of model for the second model.  For example, we could build a linear regression in the first step, and then a tree model in the second step.  The tree model could pick up some non-linear information in the errors that the linear regression would miss.

Gradient boosting is just one form of boosting.  In general, "boosting" methods try to improve accuracy by boosting the importance of training examples that have errors.  One approach is to weight the training examples, create a base classifier, find the training examples where the base classifier is wrong, increase the weight of those examples and create a new classifier.  The idea is that by forcing the base classifier to pay more attention to the incorrect examples, it will become more accurate on those examples.  A popular version of this approach is called adaptive boosting or AdaBoost and has proven to be very effective for a wide range of problems.

Machine learning toolkits like WEKA and RapidMiner have various forms of boosting built in, including both adaptive regression and AdaBoost, but the idea is straightforward enough that it's not difficult to implement yourself if you need more control over the approach.  In the case of the Pain Machine, I haven't found a boosting approach that improves the accuracy of the base linear regression, but I have found that some tree approaches can be boosted to an accuracy close to that of the linear regression.  I suspect that boosting is less useful for problem domains with large amounts of noisy data, or for models that are already close to the best possible performance, but that's just speculation on my part.