Thoughts on the Kaggle Contest

As mentioned in a previous post, Kaggle is sponsoring a March Madness contest.  After some false starts, I managed to figure out the rules, scoring, and submission format.  The first phase of the contest is scoring predictions for the past five tournaments.  I entered a submission based on the Prediction Machine's point spreads and placed in the Top Ten of the leaderboard.

Some random thoughts about the contest in no particular order.

(1) The "typical" March Madness contest awards full points for predicting a game correctly, and no points for predicting a game incorrectly.  Scoring is totally dependent upon the outcome of the game, so scoring for games between closely matched opponents is essentially random.  Consequently, winning these contests usually comes down to getting a few late round upset picks correct, a topic I've previously explored.

The Kaggle contest is using an interesting alternative scoring method, the log loss, also called the predictive binomial deviance.  Submissions give a likelihood from 0 to 1 for a particular outcome (e.g., Arizona will beat UNC Greensboro).  The more certain (closer to 1) the prediction, the higher the reward (penalty) for getting the game right (wrong).  For close games, you can predict an outcome around 0.50 and get a small reward if you are right but only a small penalty if you are wrong.  This scoring metric does a better job of rewarding contestants who accurately judge the relative strengths of the teams in each game rather than the outcome of that particular game (if that makes sense).

You can also think of this scoring method as a betting strategy.  When you place a high likelihood on a particular outcome, it's like betting a lot on the game.  When you place an even likelihood on a particular outcome, it's like betting only a small amount on the game.  The winner is the contestant who ends up with the most money at the end of the tournament.

(2)  The problem with predicting "likelihood" is that there's no way to measure the actual likelihood.  If we made the teams play a 100 games, we'd get a good approximation of the likelihood, but that's obviously not reasonable.  So there's really two parts to each submission:  (a) assessing the relative strength of the competing teams, and (b) translating that into a likelihood of victory for one of the teams. 

To see that these are two separate problems, imagine that every competitor had to base their entry on the RPI scores of the teams.  Every competitor would have the same relative strength assessment.  But they could translate that into a likelihood any way they wanted.  One competitor might use an exponential model with an exponent of 15, another an exponential model with an exponent of 22, another a logistic distribution, etc.  The winner in this case would be whomever happened to pick the best likelihood model for that year's tournament.

To my mind, it would be a better test of the predictors to have them predict the point spread of each game.  Point spread is directly measurable and is the best proxy we have for likelihood, so we'd eliminate that element of how well the competitors translated relative strength to likelihood.  But this is probably a minor point -- predicting likelihood with a log loss evaluation is overall a pretty good approach.

(3)  So what's the right strategy for this contest?  The default strategy is obviously to make your best possible predictions for the games and enter that.  But does it ever make sense to intentionally use something other than your best possible prediction?

In a traditionally-scored tournament pool, I believe it does make sense to pick against your best predictions.  The reason is that most good predictors are going to have similar outcomes for almost all the games.  In that situation, the best possible result for your best predictions might be to end up in a multi-way tie for first place.  But in any decent size pool, the most likely result is that you're going to lose to someone who got lucky and picked one or more of the inevitable upsets.  So if you want to win the pool, you need to pick upsets yourself, and hope to get lucky.

It isn't clear to me that the same reasoning applies with the log loss scoring method.  Since it rewards accurate assessment more than game outcome, it may be that the best strategy is to simply use your best possible predictions.

(4)  Phase One of this contest is essentially meaningless.  The outcomes of the last five tournaments are known, so it is trivial to craft a "perfect" submission.  No one has done that yet, but the top of the leaderboard is already filled with (what appear to be) unrealistic submissions.  These submissions are probably "cheating" or are heavily tuned to do well on the Phase One test data.

(5) So what's the best "realistic" score for this contest?  By this, I mean the score over a large number of tournament games.

On the point spread side, the best known predictor for college basketball game outcomes are the Vegas closing lines.  This isn't an absolute bound on performance, but it's a good starting point. As I pointed out above, converting point spreads to likelihoods isn't straightforward, but with one reasonable approach, the lines have a log loss score of around 0.52 for the past few seasons of regular season games.  So I'd be dubious of any approach that does significantly better than that.

(6) That said, it's important to remember that a single NCAA tournament is a very small set of data.  It's perfectly reasonable to expect an approach that would be terrible on average over a large number of tournaments to do very well on any particular tournament (or vice versa).  For example, my entry to Phase One had a score of about .54.  When I look at how that entry scored on each individual season, I see that in some seasons it scored around .51.   So the winner of Phase Two could easily be someone who just happened to get lucky with a good score this year.

It wouldn't be an entirely unreasonable approach to build a model to assess team strengths, an algorithm for translating that to likelihoods and then tune that to do particularly well on some past tournament (say, 2010).  That's probably not the best general approach, but it might get lucky and do very well this year.

Local Regression

The Prediction Machine uses a linear regression to form its predictions.  A linear regression works by calculating a straight line equation (hence "linear") that best fits the observed historical data.  That looks something like this picture:

Given a new X we use the blue line to predict a value for Y.  The Prediction Machine isn't two-dimensional like this illustration -- it has dozens of inputs rather than just one -- but this gives you the general idea of how it works.

It turns out that a linear regression works pretty well for the Prediction Machine.  But I've wondered whether there aren't "special cases" hidden in the data where the equation that best fits all the data doesn't work well for the special cases.  For example, you might think that teams that are very good at getting offensive rebounds could be predicted more accurately with a slightly different equation.  If you could pick out those cases and use a different linear regression, overall accuracy would improve.

There are a number of different approaches to doing this.  One is to use a more complex regression, so that the "blue line" can bend more flexibly in different regions of the prediction space.  For example, you can use a polynomial regression:

But a polynomial regression still bends "smoothly" and is limited in how many times it can bend.

Another approach is to predict a game's outcome based upon its nearest neighbors, as I talked about here.  The shortcoming with this is that the prediction is based upon the average of all the nearby neighbors -- which might not be the right estimation.  A more sophisticated model (such as a linear regression) might work better.

Local regression is a modeling technique that combines nearest neighbors with regression.  It works by finding the nearest neighbors to the example you want to predict, creates a linear regression using just those neighbors, and then predicts the example using the linear regression.  If your data really has "neighborhoods" that act differently, this should do a better job of prediction.

Local regression was recently added to RapidMiner so I took the opportunity to apply it to the Prediction Machine to see if it would improve performance.

The results were disappointing and/or enlightening, depending upon your perspective.  Performance of localized regression was much poorer than a linear regression for small numbers of neighbors.  It wasn't until the number of neighbors was greater than 2000 that its performance started to approach the performance of the linear regression.

This confirms earlier experiments suggesting that there aren't localized "neighborhoods" within the NCAA basketball data where we can improve performance by treating them differently.  The factors that predict performance seem to apply equally across the whole spectrum of college teams.

Data Cleansing

Generally I gather my data from ESPN and it's mostly consistent.  They do a pretty good job keeping the data clean.  But I've also gathered data from Yahoo and other sources (such as betting lines).  And any attempt to merge the data from different sources is an adventure in reconciliation.

There's no standard for reporting neutral site games, so sometimes one team is the home team, and sometimes the other team is the home team.

Team names are reported any which way.   Teams like "California State Fullerton Titans" are a nightmare -- CSU Fullerton, CSU-Fullerton, CSU Fullerton Titans, Cal State Fullerton, Cal St Fullerton, Cal St. Fullerton, Cal. State Fullerton, etc., etc.  Surprisingly, the only outright confusion is SDSU, which usually means South Dakota State University, but sometimes means San Diego State University.

Game times are typically reported in Eastern Time.  Which is fine except for Hawaii, whose scores are sometimes reported on the day the game started, and sometimes on the day it ended.  The Alaskan Shootout is a problem, too.  According to ESPN, Oral Roberts played both Loyola-Marymount and Charlotte on 11/22 this year.  Talk about a tough schedule -- fire the AD!

A couple of games were cancelled this year (notably the 11/9 weather games), but a game between BYU and Utah State was postponed when a Utah State player dropped dead on the court during practice.  Luckily the athletic trainer had a defibrillator and restarted the player's heart, saving his life.

The non-D1 teams schools find to play are endlessly fascinating.  Last week Houston Baptist played Ecclesia College, which is so small it barely has a Wikipedia page.  I can't even tell how many students are enrolled there from its website.  The most popular non-D1 opponents this year are San Diego Christian (8 games against D1 opponents, lost every one) and Rochester (6 games, won against Eastern Illinois).   MIT seems to be Harvard's opening opponent every year (?).  Le Tourneau College was founded by a guy who made his fortune inventing earthmoving equipment.

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.

How to Pick a Tournament Bracket, Part 2

In the previous post, I looked at a strategy for picking a Tournament bracket.  The basic idea is that to win a sizable Tournament challenge, you can't just pick the most likely outcome of each game.  You're going to have to pick at least some of the inevitable upsets correctly.  A reasonable way to do that is to decide how many points from upsets you think you'll need, and then pick some combination of upsets to reach that number.  It turns out the best way to do that is to pick late-round upsets between closely-matched teams.

However, there are some concerns with that approach.  One is that if you pick "likely" upsets (such as a #2 over a #1), it's reasonable to assume that many of your competitors might pick the same upset.  So although the upset might be both likely and high-scoring, it might not do much to separate you from your competitors.  That's an interesting problem, but one we'll leave for another day.

Another concern is that the strategy is "all or nothing."  We are assuming that we'll need (say) G = 16 points to win the Tournament challenge and make picks accordingly.  But in truth our chance of winning the Tournament challenge is more of an S-curve:

We have some guess at G that will give us a reasonable chance to win the challenge, but we might end up needing more or we might be able to win with less.  With G = 16 the strategy I've outlined so far leads us to pick a single 16 point upset in a semi-final game.  This is fine if the upset occurs.  But if it doesn't, losing 16 points moves us a sizable distance to the left on the S-curve and greatly reduces our chances of winning.  Something of this sort happened to my entry (the Pain Machine) in the last Machine Madness contest -- the PM predicted a Kansas-Kentucky upset that would have left it at G = 34.  But since Kentucky won, the PM ended up at G = 2 and lost the contest to a predictor at G = 7.  We'd really like a strategy that optimizes our chance to win under all possible scenarios.

Mathematically, this is the sum over all possible outcomes of the likelihood of the outcome times the likelihood of winning under that outcome.  If we pick a single 16 point upset, then there are two possible outcomes: the upset happens or it doesn't.  If L(n) is the likelihood of winning the challenge with n points, then expected value of that strategy is:

EV = L(0) * (1 - p(u,v)) + L(16) * p(u,v)

But if instead we picked two 8 point upsets, then there are four possible outcomes: neither of the upsets occur, the first upset occurs but the second doesn't, the first doesn't but the second does, or they both occur.  The expected value of this strategy is more complicated: 

EV = L(0) * (1 - p(u₁,v₁)) * (1 - p(u₂,v₂)) + 
         L(8) * p(u₁,v₁) *  (1 - p(u₂,v₂)) + 
         L(8) * (1 - p(u₁,v₁)) * p(u₂,v₂) + 
         L(16) * p(u₁,v₁) * p(u₂,v₂)

Depending upon the probability of the various outcomes and the likelihood of winning, the expected value of this strategy might be higher than picking a single 16 point upset, even though the chances of scoring the full 16 points are reduced.

Up until now, I've been implicitly assuming that the possible outcomes of an upset pick are either zero or n points.  But that's not really true.  The cost of an incorrect pick can be greater than just losing the points for that game. 

For example, last year the Pain Machine correctly predicted that #15 Lehigh would beat #2 Duke.  Given the rarity of 15-2 upsets, that was an amazing prediction.  But even if it was a very likely upset, it would have been a bad pick, because there was a potentially high cost if the upset didn't happen.  To see why, here is the bracket:

If the prediction is correct, the Pain Machine picks up 1 point for the correct first round prediction.  But if the prediction is incorrect, the Pain Machine is very likely to lose 2 points when Duke wins in round, 4 more points when they win in the third round, and so on. (Since as a #2 seed, we expect them to win until the round of eight.)

We can generalize this idea as a value formula for a win by U over V:

        V(u,v) = (p(u,v) * round_i ) - (p(v,i+1) * round_i+1 ) - (p(v,i+1)*p(v,i+2)* round_i+2 ) ...

Here, p(u,v) represents the probability that U defeats V, round_i represents the scoring value for the Ith round of the tournament, and p(v,i+1) represents the probability of V defeating their likely opponent in  round i+1 if they had not been upset by U.  To return to the Lehigh-Duke example, the value is the probability of Lehigh beating Duke times 1 (the value of that round) minus the probability of Duke beating Notre Dame (their expected opponent) times 2 (the value of that round), and so on.

To maximize V(u,v) we must maximize p(u,v) and minimize p(v,i+1).  And since round_i+1 = 2*round_i, it is twice as important to minimize p(v,i+1).  To translate this into plain English, we want to pick upsets where the team being upset has very little chance to win its next round game.  That's why the Lehigh upset was a poor pick -- because as a #2 seed Duke had a very good chance to win its second round game.

Instead, this formula will value upset picks like #10 Xavier over #7 Notre Dame.  (Which also happened!) To see why, look again at the bracket:
Whichever team wins the first round game -- Notre Dame or Xavier -- they are likely to lose the second round game to the stronger Duke team.  Thus the downside of the upset pick is minimized -- if Notre Dame wins and then loses to Duke as expected, you'll only have lost one point for the incorrect upset pick.

This insight is nothing new.  Canny pickers already look for upsets that are "firewalled" off in the next round by a strong opponent.  However, the value formula above gives us an objective measure for comparing between possible upset picks.  I suspect that most people incorrectly assess the p(u,v)  vs. p(v,?) tradeoff.  Because scoring doubles each round, it's much more important to consider the cutoff in the next round than the upset chance -- which most people probably find counter-intuitive.

Unfortunately, the strategy of "firewalling" upset picks runs counter to the strategy of picking high-scoring late round upsets, because (assuming most games are not upsets) the mismatches which make good firewalls primarily occur in the early rounds.  If the tournament runs mostly true to the seedings, the late round games are usually between closely-matched teams and do not make good firewalls.  An interesting exception is the Championship game itself.  If you pick an upset in the Championship game incorrectly, you're guaranteed not to lose any additional points. 

To summarize these thoughts about picking a tournament bracket:

1. A bracket consisting of chalk picks and true mis-seedings is not likely to win a sizable Tournament challenge.
2. Picking late-round upsets between highly-seeded teams has the advantages of (1) scoring a lot of points, and (2) being relatively likely to occur.
3. To maximize the overall chance of winning the challenge, it may be better to spread your upset picks rather than bet "all or nothing."
4. Upset picks which are firewalled in the next round reduce the downside risk of an incorrect pick.

How To Pick A Tournament Bracket, Part 1

Pre-season is probably not the best time to be pondering the Tournament, but I've been recently thinking a bit more about the challenge of predicting the Tournament with the goal of winning something like the ESPN Tournament Challenge or the Machine Madness contest.  These sorts of contests are a dilemma to a machine predictor, because most predictors try to determine who is most likely to win a particular matchup.  But of course, that's exactly how the Tournament is seeded.  So the machine predictors end up predicting almost entirely "chalk" outcomes.

The only time the machines don't predict a win for the higher seed is when they believe the teams have been mis-seeded -- that is, when the Committee has made a mistake in their assessment of the relative strengths of the teams.  In last year's Machine Madness contest, Texas over Cincy and Purdue over St. Mary's were consensus upset picks by five of the six predictors -- strong evidence (to my mind, anyway) that those teams were mis-seeded.  But, for all the grumbling by fans, the Committee does a pretty good job at seeding the Tournament, and you can't expect to find many true mis-seedings. 

Neither chalk picks or mis-seedings are likely to win a Tournament challenge against a sizable field.  That's because (1) a lot of your competitors will have made the same picks, (2) there will be a significant number of true upsets where a weaker team beats a stronger team (historically, 22% in the first round, and 15% for the Tournament overall), and (3) someone out there will have picked those upsets.  So to win a Tournament challenge, the machine is going to have to pick some actual upsets -- and then hope that it gets lucky and those upsets are the ones that happen.

Knowing the historical frequency of upsets, my strategy last year was to force my predictor to pick 6 upsets in the first round and 5 more in the rest of the tournament.  But is that the right way to pick upsets?  How can we pick upsets to maximize (in some sense) our chance to win the Tournament challenge?

The first problem in answering this question is knowing how many points will be sufficient to win the challenge, because that will drive the selection of upsets.  Obviously, it's impossible to know this number a priori.  However, we could look at previous Tournament challenges and see how many points the competitors in the top (say) 1% had scored off correctly predicting upsets.  That would provide a reasonable goal G for our upset calculations.

Sadly, ESPN, Yahoo, etc., seem to remove the Tournament challenge information from the Internets fairly quickly, so I can't actually research this.  (If someone has some info on this, please let me know!)  However, we do have the results of the last two Machine Madness contests.  Last year, the winning entry scored 127 points and the "chalk" (baseline) entry scored 120 points, for G = 7.  The year before, the winning entry scored 69 points and the chalk entry scored 57 points, for G = 12.  (There's undoubtedly a correlation between the size of the field and G.   G = 12 might be sufficient most years to win the Machine Madness contest, but probably wouldn't be enough to win the ESPN Tournament Challenge.)

If we adopt the notation that V(u,v) is the value of a victory of Team U over Team V, then we will want to pick upsets such that:

G < V(u₁,v₁) + V(u₂,v₂) + V(u₃,v₃) ...

Because of the way the tournament is structured, the value of V(u,v) is determined by the seeding of the two teams.  The following table has seedings down both axises and shows how many points an upset is worth:

For example, a #8 seed beating a #1 seed is worth 2 points, because that matchup will necessarily occur in the second round.

If we adopt the notation that p(u₁,v₁) is the probability of u₁ defeating v₁, then the probability of G is:

p(u₁,v₁) * p(u₂,v₂) * p(u₃,v₃)  ...

(because we must get all of our upset picks correct to score G points).

Now imagine that we are predicting the tournament and we know that most games have a 0% chance of an upset.  However, four of the third round games are very likely upsets -- 49%.  And one of the semi-final games has a slight chance of an upset -- about 6%.  If G = 16, which upsets should we pick?

The (possibly surprising) answer is that we should pick the very unlikely semi-final upset!  To get 16 points we have to pick either the semi-final game, or all four of the third round games, and:

       .06 > .49*.49*.49*.49

The joint probability equation combined with the typical Tournament challenge scoring means that it will almost always be better to pick unlikely late round upsets that score highly than multiple likely early round upsets that score poorly.  Knowing this, it's easy to see that my strategy in previous years to force a certain number of upsets into my bracket was very non-optimal.

So, given a goal G and upset probabilities p(u,v) we have an approach for selecting upsets from our bracket.  We've seen how to calculate V(u,v) and how to estimate G.  How can we estimate the upset probabilities?

Many predictors will produce something that can be used to estimate upset probabilities.  For example, in past years my predictor has used the predicted MOV to estimate upset probabilities -- the slimmer the predicted margin of victory, the more likely an upset.  But lacking any information of that sort, we could estimate the upset probabilities based upon historical performance of seeds within the tournament:

This table shows the upset percentage for each seeding matchup for the last ten years.  (I have left out matchups that have occurred 4 times or less.)  Each upset percentage is shaded to indicate the value of the matchup in typical Tournament challenge scoring.  For example, matchups between #1 seeds and #2 seeds have been won by the #2 seeds 52% of the time, and they are worth 8 points. With a few oddball exceptions (such as the 2-10 matchups), this table shows is that you should prefer to pick upsets of the #1 or #2 seeds by #2 or #3 seeds.  These matchups are worth the most points and -- because the teams are closely seeded -- are nearly tossups.

So if G = 16, filling out your bracket with all chalk picks and two #2 over #1 upsets would give you the best chance to win the Tournament challenge.

More thoughts to follow in Part 2 at some later date.

Recent Papers

I took some time out recently to read through some of the basketball prediction papers from this year's MIT Sloan Sports Analytic Conference.  Here are some thoughts...

Insights from the LRMC Method for NCAA Tournament Prediction
Mark Brown, Paul Kvam, George Nemhauser, Joel Sokol
MIT Sloan Sports Analytics Conference 2012

The latest paper from the LRMC researchers compares the performance of LRMC to over 100 other ranking systems as reported by Massey here.  The measure of performance used is correct prediction of the NCAA tournament games.  LRMC out-performs all of the other rankings, getting 75.5% correct over 9 years.  The next best predictor did 73.5%.  (I don't optimize my predictor on this metric, but it also gets about 73.5% correct.)

The LRMC work is always interesting and well done.  A couple of notes that pop to mind:

(1) The advantage LRMC has over the other models is not huge.  LRMC gets 75.5% correct; the 20th ranked model gets about 72% correct -- the difference is about 3 games per tournament.  That's certainly significant, but in a test set of only 600 games, it may not be that significant.  One very good year (or one very bad year) could move a rating significantly.  It would be interesting to see the year-to-year performance of the ratings, but the authors don't provide that information.

(2) The authors assume there is no home court advantage (HCA) in the NCAA tournament and simply predict that the higher-rated team will win.  In my testing, including an HCA for the higher-seeded team improves prediction performance.  For example, this paper reports the performance of RPI as about 70% in predicting tournament games.  In my testing, RPI with HCA predicted about 73% correctly.  So the results may be skewed depending upon how much effect HCA has on each prediction model.  (The authors don't use HCA for LRMC, so that model might do better as well.)

(3) In this paper, the authors test against all the matchups that actually occurred in the tournament -- that is, they do not "fill out a bracket" and commit to game predictions at the beginning of the tournament.  In 2011, LRMC was included in the March Madness Algorithm Challenge and finished quite poorly -- outscored by all but three of the other entrants.   (A similar result can be seen here.)  Taking a look at the LRMC bracket for 2012 (here), LRMC got 22 correct picks out of the initial 36 games -- and got only one of the three play-in games correct, missed all of the upsets, and predicted two upsets that did not occur.  Eight of the entries in the algorithm challenge picked more first-round games correctly.  In fact, LRMC's only correct predictions in the entire tournament were higher seeds over lower seeds.  And once again it would have lost the algorithms challenge.

(4) My own attempts to implement LRMC and use it to predict MOV (found here) have performed more poorly (around 72%) than the authors report in this paper.  It may be that my implementation of LRMC was faulty, or that LRMC happened to perform slightly worse on my test data than on the tournament games used in this paper.


Moving on from the performance of LRMC, there are a couple of other interesting results in this paper.  One is that  home court advantage does not vary substantially from team to team.  This confirms my own experiments.  (I don't think I've reported on those experiments -- perhaps I'll write them up.)  A second is that the natural variance in games is around 11 points, which matches closely what I've found.  The last is that the authors found that the cliche "good teams win close games" doesn't seem to have any validity.

Can Statistical Models Out-predict Human Judgment?: Comparing Statistical Models to the NCAA Selection Committee
Luke Stanke
MIT Sloan Sports Analytics Conference 2012

As with the LRMC paper, this paper looks at predicting tournament game outcomes. In this case, the author compares the NCAA committee seedings and RPI ratings to four different Bradley-Terry models.  For more on Bradley-Terry models, see here.

Stanke reports the results of testing these models against (approximately) the same games used in the LRMC paper:

The highest performing models are the Bradley-Terry models using only win/loss data. These two models correctly predicted approximately 89% of games in the NCAA tournament games from the past eight seasons. The next group of models is the Bradley-Terry Models using points a method for ranking teams. These models predicted over 82% of games correctly. The third group is the alternative models, the Committee Model, The RPI Model, and the Winning Percentage Model. These models range from 69.1% of games correctly picked to 72.9% of games correctly picked.

This is certainly an interesting result -- particularly in light of the claims of the LRMC paper.  According to the LRMC authors, LRMC's 75.5% success rate out-performed over 100 other rankings from Massey's page, and the Vegas line's success rate of ~77% is an upper-bound to performance. 

So what explains this disparity?  I didn't know -- so I sent off an email to the author.   Luke Stanke emailed me to say that the result was caused by a coding error, and that actual performance was around 72%.   (I know all about coding errors... :-)  So his results here are in line with the expected performance for Bradley-Terry type rating systems.  His conclusion remains unchanged -- that computer rating systems are better than the committee at selecting and seeding the tournament, and Bradley-Terry would be better than RPI.  I won't disagree with either conclusion! :-)

Using Cumulative Win Probabilities to Predict NCAA Basketball Performance
Mark Bashuk
MIT Sloan Sports Analytics Conference 2012

Bashuk lists his affiliation as "RaceTrac Petroleum" so like me he appears to be an interested amateur in game prediction.  In this paper he describes a system that uses play-by-play data to create "Cumulative Win Probabilities" for each team, and eventually, a rating.  He uses this rating to predict game outcomes, and for the 2011-2012 season correctly predicts 72.6%.  In comparison, Pomeroy predicts 77.7% correctly and the Vegas Opening Line 75.2%.

It is unclear to me after reading the paper exactly how CWP and the ratings are calculated.  However, unlike most authors, Bashuk has made his code available on the Web.  (URLs are provided in Appendix 1 of the paper.)  This is very welcome to anyone trying to reproduce his results.  Unfortunately for me, Bashuk's code is in SQL, which I don't understand well.  So poring through it and understanding his process may take some time.

A Detour into RapidMiner

A chunk of visitors to this blog find it looking for RapidMiner, so I thought I'd take a detour to explain the RapidMiner process I'm using to explore early season performance.  This RapidMiner process uses training data to build a model, applies the model to separate test data, and then measures performance.  This is something of a sequel to the post I did for Danny Tarlow over at his blog.  Hopefully it will be useful to some folks as an example of how to put together a more complex RapidMiner process, as well as how to apply a model to test data, which wasn't covered in the previous post.

(Reminder: RapidMiner is a free data-mining tool that you can download here.)

The (unreadable) graphic above illustrates the entire process.  There are four parts to this process.  In Process 1, the training data is read in and processed.  In Process 2, the test data is read in and processed.  In Process 3, the training data is used to build a linear regression and then the model from that regression is applied to the test data.  In Process 4, the results are processed and performance measures calculated.  I'll now go into each process in detail.

The graphic above shows Process 1 in more detail. It's a straightforward linear flow starting at the upper left and ending at the lower right.  The steps are:

1. Read CSV -- This operator reads in the training data, which is simply a large text file in comma-separated value (CSV) format, with one line for every game (record) in our training data set.
2. Generate ID -- This operator adds a unique ID attribute to every record in our training data set.  (We'll see later why it is useful to have a unique ID on every record in the data set.)
3. Rename by Replacing -- This operator is used to rename attributes in the data set.  In this case, I use it to replace every occurrence of a dash (-) with an underscore ( _ ).  Dashes in attribute names are problematic when you do arithmetic on the attributes, because they get mistaken for minus signs.
4. Generate Attributes -- This operator generates new attributes based on the existing attributes.  In this case, I calculate a new attribute called "mov" (Margin of Victory) by subtracting the visiting team's score from the home team's score.
5. Set Role -- Most attributes are "regular" but some have special roles.  For example, the ID attribute generated in step 2 has the "id" role.  Here I use the Set Role operator to set the role of the "mov" attribute to "label."  This role identifies the attribute that we are trying to predict.
6. Read Constructions -- You can use the Generate Attributes operator to generate new attributes, but that's not convenient if you want to generate a lot of new attributes, or if you want to generate new attributes based on some external inputs.  In my case, I have generated and tested many derived statistics, and entering them manually into "Generate Attributes" was not feasible.  The Read Constructions operator reads formulas to generate new attributes from a file and creates them in the data set.  Using this, I was able to have a Lisp program create a (long) list of derived statistics to test, write them to a file, and then have the RapidMiner process construct them automatically.
7. Replace Missing Values -- This is the first of several data cleanup operators.  There shouldn't be any missing values in my data sets, but if there is, this operator replaces the missing value with the average over the rest of the data.
8. Replace Infinite Values -- Some of the constructions in Step 6 can result in "infinite" values if (for example) they cause a divide by zero.  These two operators replace positive infinite values with 250 and negative infinite values with -250.
9. Select Attributes -- The last operator in this process removes some attributes from our data.  In particular, we don't want to leave the scores in the data -- because the predictive model will (rightfully) use those to predict the MOV.  (The MOV itself is not a problem, because it has the "label" role.)  We also remove a couple of other attributes (like the team names) that would cause other problems.

So at the end of this process, we have read in the training data, processed it to contain all the attributes we want and none that we don't want, and cleaned up any inconsistencies in the data.

Process 2 is exactly the same as Process 1, except it is applied to the test data.  It's important to ensure that both the training data and the test data are treated identically.  If they aren't, you'll get misleading results or cause an error later in the process.  (I should point out that RapidMiner can bundle up a process into a sub-process and reuse it in multiple places, and that's probably what I should do here.)

The graphic above shows Process 3.  I've left in the "Select Attributes" from the end of Process 1 and Process 2 for context.  Here are the steps in Process 3:

1. Linear Regression -- RapidMiner offers a wide variety of classification models that can be used for prediction.  In this case we're using a linear regression.  The input to this operator is the training data, and the output is a model.  This operator trains itself to predict the "label" attribute (MOV in our case) from the regular attributes.  The model it produces is a linear equation based upon the regular attributes.  In my process here, I'm training the model every time I run the process.  It's also possible to train the model once, save it, and re-use it every time you want to test or predict.  In my case, I tweak the data and/or process almost continuously, so it's easiest just to re-train every time.  There are about 15K records in the training data set, and the Linear Regression takes a couple of minutes on my laptop.  Other classification operators are much slower, and re-training each time is not feasible.
2. Apply Model -- This operator applies the model from step 1 to the testing data from Process 2 and "labels" it -- that is, it adds a "prediction(mov)" attribute that has a predicted Margin of Victory for the game.
3. Join -- This operator "joins" two data sets.  To do this, it finds records in the two data sets that have the same ID and then merges the attributes into a single record.  (Now we see why we need a unique ID!)  The two data sets being merged here are (1) the labeled data from the model, and (2) the original data from the Select Attributes operator.  Recall that the Select Attributes operator is used to remove unwanted attributes from the data, including the team names and scores.  So the labeled data coming out of the model does not have that information.  However, to evaluate our predictive performance we need the scores (so we can compare the actual outcome to the predicted outcome) and it would be nice to have team names and dates on the data as well.  So this Join operator puts those attributes back into our data.  In general, this is a useful technique for temporarily removing attributes from a data set.

At this point, we have a data set which consists of our test data with an added attribute "prediction(mov)"containing the predicted margin of victory for each game.  Next we want to see how well our model performed.

The graphic above shows Process 4.  I've left in the "Join" from Process 3 to make it clear where it connects.  Here are the steps to Process 4:

1. Rename -- The first step is to rename the "prediction(mov)" attribute to "pred".  The parentheses in this name can confuse some later processing, so it's best just to remove them.
2. Generate Attributes -- Next we generate a new attribute called "correct".  This attribute is 1 if we've correctly predicted the winner of the game, and 0 if not.  RapidMiner provides a powerful syntax for defining new attributes.  In this case, "correct" is defined as "if(sgn(mov)==sgn(pred),1,0)" -- if the sign of our predicted MOV is the same as the sign of the actual MOV, then we correctly predicted the winner.
3. Write Excel -- At this point, I save the results to an Excel spreadsheet for later reference and processing (e.g., to produce the graphs seen here).
4. Multiply -- I like to look at two different measures of performance, so I create two copies of the test data.  This isn't strictly necessary in this case (I could chain the two Performance operators) but this is another example of a useful general technique.
5. Performance -- RapidMiner provides a powerful operator for measuring performance that can assess many different measures of error and correlation.  In the top use of Performance in this process, I use the built-in "root mean squared error" measure and apply it to the predicted MOV to calculate the RMSE error.
6. Aggregate / Performance -- The second measure of performance I like to look at is how often I predicted the correct winner.  (I might prefer a model that predicts the correct winner more often even if it increases the RMSE of the predicted MOV.)  I want to know this number over the entire data set, so the first step is to Aggregate the "correct" attribute.  This produces a new attribute "sum(correct)" which is the number of correct predictions over the whole data set (and has the same value for every record in the data set).  This is then reported by the Performance operator as a performance measure.  The Performance operator isn't strictly necessary in this situation -- I could just report out the "sum(correct)" value -- but in general marking this as a measure of performance allows me to (for example) use the value to drive an optimization process (e.g., selecting a subset of attributes that maximizes the number of correct predictions).

And that's "all" there is to it.  One of the advantages of RapidMiner is that the graphical interface for building processes let's you quickly lay out a process, as well as easily modify it (such as switching the Linear Regression to an SVM, for example). 

Awakening From the Long Summer's Sleep

College basketball fans hibernate in the summer.

I'm slowly awakening from my March Madness-induced stupor and starting to prepare for the new season.

One of the first tasks is to look at conference realignments.  My predictors don't actually use conferences for anything -- I keep thinking that conference games will have more predictive power than non-conference games, or vice versa, but to date neither has proven to be true.  Nonetheless, I keep track of the conference affiliations of teams, so every Fall I have to update that data for the various conference movements.

I took my summary of the changes from the "Blogging the Bracket" here.  If there's any interest in the compiled data, please let me know.  I've noticed that there's been little interest in the data files I provided last year, so I won't bother unless someone expresses some interest.

The next task is to scrape the schedule of games for the season.  In past seasons, I've scraped the schedule from Yahoo Sports.  Unfortunately, it appears that they have "updated" their interface and broken everything.  No scheduled games appear at all, and the majority of the tournament games from last year are missing as well.

Sigh.

Hopefully this is just a temporary situation while Yahoo Sports gets their bugs fixed and the data loaded.  Alternate sources of this data are not easy to find.  ESPN and CBS are still showing last year's games.  The NCAA website started carrying game results (and box scores) last season, but doesn't seem to have the upcoming games.

In the meantime, I've been thinking about how to predict early season games.  These games are difficult to predict because we do not have any history of past performance for this year's teams.  So we're forced to base our predictions on other data -- or to not predict early season games (which is what I've done in past seasons).  Some alternate data is only available for some of the teams (e.g., the AP preseason rankings) or is entirely subjective, which makes it less useful from my viewpoint.

One source of objective data for all the teams is their previous season's performance.  One approach to predicting the early season games is to assume that teams will be just as strong this year as they were last year.  Another approach might be to assume that teams will migrate towards the mean -- the best teams from last year will get a little weaker and the worst teams will get a little stronger.  We could also look at team data such as the number of graduating seniors and use that information to modify the previous year's performance -- e.g., a team that lost most of its starting minutes would get weaker.  An intriguing idea is to see if we can predict the change in performance for a team from season to season (based upon what factors?) and then use that to modify the previous year's performance.

As time permits, I will set up to test some of these ideas and report my findings.

The Continued (Slow) Pursuit of Statistical Prediction (Part III)

As promised last time, we'll now look at a different type of derived statistic. We're going to look at statistics which are the ratio between the two teams of the same base statistic, e.g.,

(Ave # of offensive rebounds for the home team / Ave # of offensive rebounds for the away team)

The idea here is that it may be more predictive to look at the relative strengths of the teams rather than the absolute strengths. 

The first statistics I want to try this upon are the strength measures like TrueSkill and RPI. Suppose that Syracuse, with an RPI of 0.6823, plays Missouri, with an RPI of 0.6234, and the same night UCF, with an RPI of 0.5723 plays Oregon State with an RPI of 0.516.  Would we expect the same outcome in those games?  In both cases, the better team is about 0.06 better in RPI.  But Syracuse is about 10% better than Missouri, while UCF is about 12% better than OSU.  If it's the relative strength that matters, we would expect UCF to win (on average) by more than Syracuse.

To test this out, I generated the relative strengths for measures like TrueSkill and ran them through my testing setup.  In every case, the relative strengths had no predictive value above and beyond the value of the absolute strengths.  And when the relative strengths alone were used for prediction, they underperformed the absolutes used alone.

I then did the same thing for the statistical attributes like offensive rebounding and got the same result.  The relative strengths of the two teams provided no additional predictive accuracy.

I find this result fairly intriguing.  My strong intuition was that at least a portion of the game outcome would be better explained by the relative strengths of the two teams. It's hard to believe that Syracuse should win its game against Missouri by more points simply because they're both stronger teams than UCF and OSU.  But (as has often proven to be the case!) my intuition was just wrong, and relative strength is much less important than I would guess.

The Continued (Slow) Pursuit of Statistical Prediction (Part II)

Continuing on from last time, I had set up the infrastructure to allow me to easily test the value of derived variables in statistical prediction.  Before testing any of these derived variables, we need a baseline.  In this case, the baseline is the performance of a linear regression using all the base variables.  I don't know that I've ever documented the base variables, but they are basically all that can be created from the full game statistics available at Yahoo! Sports.  These are averaged by game, so for example one of the base statistics is "Average free throw attempts per game."  I also have the capability to average statistics by possession (e.g., "Average free throw attempts per possession" but unlike some other researchers, I've never found per possession averages to be any more useful than per game averages, so I generally don't produce them.

For most statistics, I also produce the average for the team's opponents.  So to continue the example above, I produce "Average free throws per game for this team's opponents."  I also produce a small number of simple derived statistics, such as "Average Margin of Victory (MOV)", and winning percentages at home and on the road.

When we get to predicting game outcomes, of course we have all of these statistics for both the home and the away team.  (And that home/road distinction is important, obviously.)  If we use all these base statistics to create a linear regression, we get the following performance:

Predictor	% Correct	MOV Error
Base Statistical Predictor	72.3%	11.10

This is the same performance I have reported earlier, and tracks fairly well with the best performance from the predictors based upon strength ratings.

Now we want to augment that predictor with derived statistics to see if they offer any performance improvement.  As mentioned last time, we have 1200 derived statistics, so we have to do some feature selection to thin that crop for testing. 

One possibility (as discussed here) is to build a decision tree, and use the features identified in the tree.  If we do that (and force the tree to be small), we identify these derived features as important:

1. The home team's average margin of victory per possession over the overall winning percentage
2. The away team's average number of field goals made by opponents over average score
3. The home team's average assists by opponents over the field goals made
4. The home teams average MOV per game over the home winning percentage

That is, you'd have to admit, quite a goulash of statistics.  I can probably come up with some rationale about some of those, but I won't bother.  All I really care about is whether they will improve my predictive accuracy.

To test that, I add those statistics to my base statistics and re-run the linear regression.  In this case, what I find is that while some of the derived statistics are identified as having high value by the linear regression, the overall performance does not improve.

There are other methods for feature selection, of course.  RapidMiner has an extension focused solely on feature extension.  This offers a variety of approaches, including selecting based on Maximum Relevance, Correlation-Based Feature Selection, and Recursive Conditional Correlation Weighting.  All of these methods identified "important" derived statistics, but none produced a set of features that out-performed the base set.

A final approach is a brute force approach called forward search.  In this approach, we start with the base set of statistics, add each of the derived statistics in turn, and test each combination.  If any of those combinations improve on the base set, we pick the best combination and repeat the process.  We continue this way until we can find no further improvement.

There are a couple of advantages to this approach.  First, there's no guessing about what features will be useful -- instead we're actually running a full test every time and determining whether a feature is useful or not.  Second, we're testing all combinations in our search space, so we know we'll find the best combination.  The caveat here is that we assume that improvement is monotonic with regards to adding features.  If the best feature set is "A, B, C" then we're assuming we can find that by adding A first (because it offers the most improvement at the first step), then B to that, and so on.  That isn't always true, but in this case it seems a reasonable assumption.

The big drawback of this approach is that it is very expensive.  We have to try lots of combinations of features, and we have to run a full test for each combination.  In this case, the forward search took about 54 hours to complete -- and since I had to run it several times because of errors or tweaks to the process in ended up taking about a solid week of computer time.

In the end, the forward search identified ten derived features, with this performance:

Predictor	% Correct	MOV Error
Base Statistical Predictor	72.3%	11.10
w/ Forward Search Features	74.0%	10.73

This is a fairly significant improvement.  The most important derived features in the resulting model were:

1. The away team's opponent scoring average over the away team's winning percentage.
2. The away team's offensive rebounding average over the away team's # of field goals attempted
3. The away team's scoring average over the away team's winning percentage
4. The away team's opponent treys attempted over the away team's rebounds

The ten statistics were actually evenly divided between home team statistics and away team statistics, but it turned out that the most significant five were all the away team statistics.

I'll leave it to the reader to contemplate the meaning of these statistics, but there are some interesting suggestions here.  The first and third statistics seem to be saying something about whether the away team is winning games through defense or offense.  The second and fourth statistics seem to be saying something about rebounding efficiency, and perhaps about whether the team is good at getting "long" rebounds.  (The statistics for the home team are completely different, by the way.)

Next time I'll begin looking at a different set of derived statistics.

The Continued (Slow) Pursuit of Statistical Prediction

When we last met on this topic, I was inspired by the Four Factors to look at derived statistics created from the ratio of two existing statistics, e.g.,

Offensive Balance = (# 3-Pt Attempts) / (# FG Attempts)

My previous work in this area has convinced me of the value of looking at all possibilities, no matter how non-intuitive, my approach was to look exhaustively at all the possible ratios between the ~35 base statistics.  That leads to some crazy statistics such as:

(Average # of fouls per possession by the home team's previous opponents) / 
    (Average offensive rebounds per game by the home team in previous games)

There turn out to be a number of difficulties with this approach.  (Perhaps not unsurprisingly, although crazy nonsensical statistics are not one of them.)

First, it's a lot of work just to generate the 1060 derived statistics.  (Only 1060 because I avoided inverse ratios, and avoided "cross-ratios" between the two teams.)  Initially I was generating a subset of these from within the Lisp code that pre-processes the game data.  That was painful to set up and slow to execute.  Eventually I discovered a way to generate the derived statistics within RapidMiner. I was able to drive this from a data file, so I wrote a small Lisp program to generate the data file that RapidMiner could use to construct all 1060 derived statistics.

Second, this amount of data tended to overwhelm my tools.  With the derived attributes, each game has about 1200 attributes total.  My training corpus has about 12K games.  The combination tended to break most of the data modeling features of RapidMiner, usually by overwhelming the memory capacity of Java.  Even when the software was capable of handling the data volume, operations like a linear regression might take hours (or days!) to complete, so testing and experimenting was laborious at best.

One way to reduce this problem is to thin the dataset, by testing on (say) a tenth of the full corpus.  But that introduced a new problem: overfitting.  If I used (say) a tenth of the data, I had about 1200 games in my test set -- just about the same number of test games as attributes.  The result of that is almost invariably a very specific model that does extremely well on the test data and very poorly on any other data.

Another approach is to thin the attributes.  This is the feature selection problem.  The idea is select the best (or at least some reasonably good) set of features for a model.  The stupid (but foolproof) way to do this is to try every possible combination of features, and select the best combination.  But of course that's infeasible in many cases (such as mine), so a variety of alternative approaches have been created.  RapidMiner has some built-in capabilities for feature selection, and there's a nice extension to add more feature selection capabilities here.

I experimented with a variety of different feature selection approaches.  I was hopeful that different approaches would show overlap and help identify derived attributes that were important, but for the most part that did not happen.  However, taking all the attributes recommended by any of the feature selection approaches did give me a more reasonable sized population of derived statistics to test.

More on this topic next time.

New Papers

(All of the following papers have been added to the papers archive.)


[Gill 2008] "Assessing Methods for College Football Rankings," JQAS 2008

Summary: This paper purports to "...consider several mathematical methods for ranking college football teams based on point differential... [and] assess the predictive performance of these models using leave-one-out cross validation."  The models considered are variants of least-squares fitting of rating values to point differential.  Variants include different fitting methods (e.g., weighted least squares) and methods for limiting the impact of blowouts (e.g., cutting off the point differential at 14 or 28 points).  Predictive performance is used to assess cutoff values for blowouts.

Comment:  A disappointing paper for me; from the title and abstract I had hoped that this paper would analyze some set of football ranking approaches for their predictive value.  Instead, the main conclusion of the paper seems to be that one can construct a rating system that emphasizes nearly any aspect of competition by selecting the right approach and tuning constants.

[Wigness 2010]  "A New Iterative Method for Ranking College Football Teams," JQAS 2010
And see: WWR Rankings

Summary: This paper describes a method for ranking college football teams.  The method uses (potentially) score, location (home or away) and time of season to create an initial value for each game, and then iteratively re-rates games until equilibrium is achieved.  The method has a number of parameter/options, and the paper evaluates the performance of several combinations.  Performance is measured by the % of correct predictions for bowl games.   Over 9 seasons, the best combination predicts about 59% of the total bowl games correctly, and about 63% of the total BCS bowl games.  In contrast, over the same span the BCS computer rankings have predicted about 57% of the BCS games correctly.

Comment:  A fairly interesting paper, and apparently the work mostly done by an undergraduate.  The approach is at least somewhat novel -- it involves creating a graph where the nodes are teams and the links are games between teams, and then summing all the simple paths originating from a team and going out "K" links.  (Where K is a parameter, but K=4 was the best performing.)  There's no intuitive (to me at least) meaning for doing this, but to some extent it captures the strength of opposition, the same way RPI uses OWP, OOWP, etc.  I'd like to implement and test this system, but the naive implementation for calculating all the simple paths is likely going to be very slow, and if there's a clever matrix implementation it doesn't occur to me.  I've put a question in to the authors asking about their implementation.


[Loeffelholz 2009] "Predicting NBA Games Using Neural Networks," JQAS

Summary:  An ensemble of several different neural networks fed with team statistics was used to predict NBA games.  Performance was assessed using "% Correct" and compared to consensus picks from five experts published in USA Today.  The ensemble methods did not improve upon the best included baseline predictor.  The best predictor (feed-forward NN) predicted 74% of the test games correctly (compared to 69% for the human experts). 

Comment: There are number of interesting results in this paper.  First, the authors looked at both (1) splitting team statistics based on home/away, and (2) using only the most recent 5 games, and in both cases found no value.  This agrees with my own experiments with similar approaches.  Second, the authors experimented with various combinations of statistics and had the best performance using only FG% and FT% for each team.

[Beckler 2009] "NBA Oracle," CMU Classwork
And see:  Matthew Beckler's Home Page


Summary: This paper describes an effort to use various machine learning techniques to predict NBA game outcomes (as well as some related tasks).  Inputs to the learning process were 62 features for each game -- most features were averages for the current season and the previous season of team statistics such as rebounding, shooting percentage, etc.  The most effective technique was linear regression, which predicted about 70% of games correctly -- comparable to human experts.  The most important statistics were team winning percentage in the previous season, and (in decreasing importance) defensive rebounds, points made by opposing team, number of blocks and assists made by opposing team.


Comment:  A fairly straightforward attempt to predict NBA games based upon team statistics.  Prediction accuracy is in line with similar work (although below Loeffelholz) -- around 70% seems to be fairly easy to achieve for NBA games.  There's no attempt to predict MOV.

[Orendorff 2007] "First-Order Probabilistic Models for Predicting the Winners of Professional Basketball Games," JQAS 2007

Summary: This paper describes an effort to apply Bayesian Logic (BLOG) and Markov Logic Networks (MLN) to predicting NBA games.  Inputs to the models are won-loss records.  The MLN model performs best, predicting 76% of games correctly.


Comment: The methodology here is similar to my methodology -- the research uses a x-validation on the entire NBA season.  However, there is one very important distinction.  This research uses the entire season's data to predict the held-out games -- not just the season up to the time of the predicted game.  This makes a huge difference in prediction performance, so take the authors' result of 76% accuracy with a grain of salt.  It's likely that the accuracy using season-to-date data would be 15-20% lower.

[Trono 2010] "Rating/Rankings Systems, Post-Season Bowl Games, and 'The Spread'", JQAS 2010

Summary: This paper compares a number of simple systems for predicting college football bowl games. 



Comment: This is a difficult paper to analyze.  It is written in a very colloquial, unorganized manner and lacks a clear purpose.  The systems analyzed are described in vague terms that make it difficult to understand the computational implementation, or even to attribute authorship of the systems.  All that said, at least one system described has out-performed the Las Vegas line (by 1 game) over a 7 year period.

[West 2008] "A New Application of Linear Modeling in the Prediction of College Football Bowl Outcomes and the Development of Team Ratings," JQAS 2008

Summary: This paper uses linear regression to build a predictive model for college football bowl games.  The inputs to the model are average statistical measures (e.g., "Offensive yardage accumulated per game").  The model predicted 19 of 32 bowl games correctly (59.4%).


Comment: This paper is of particular interest to me at the moment because I've also turned to looking at prediction using statistical team measures.  This work seems to agree with my result that only a few measures (mostly related to scoring) have significance in the final model.  Also of interest here is that West pre-conditions his statistical measures by expressing all of them in units of "standard deviations from the mean."

The Development Cycle

My development cycle seems to go something like this:

  Work on content --> Clean up code --> Remove impediments --+

        ^                                                    |

        |                                                    |

        +----------------------------------------------------+

(Excuse the 1970s typewriter graphics...)  I'm in the latter half of the cycle right now, re-factoring my Lisp code to make it better organized & maintainable, and also addressing some little impediments in my tools (primarily on the Emacs / Lisp end). 

Lee Ming was also nice enough to scrape the rest of the 2010-2011 basketball season, so I also spent some time incorporating that into my test data.  Lee's archive is missing about 10% of the games over the course of the season -- and that's comparing it to my independent scrape, which I know is missing games.  Lee is taking a look at why he's missing games, but it's frustratingly hard to get a good, complete data set scraping Yahoo!.  If anyone knows somebody at Yahoo! that we can bug to have a dataset released (or to set up an API for the scores), please let me know!

Update

I've been remiss in posting lately. Mostly because it is summer time and I've simply had less time to work on this topic. But also because I've been doing some ground work for the next stage of analysis. All the work I've done here so far has used only game outcomes, and I've been able to use the excellent and complete set of game scores collected by Lee over at Number Crunching Life.  However, for the next stage of analysis I want to look at game statistics like Field Goal Percentage, Offensive Rebounds, etc.  I have partially collected these stats for the last two seasons, but I need to quality-check the data I have, fill in missing games and so on.  I have a crawler written using Web Harvest but it seems to sporadically miss games.  The crawler from Lee is written in C#, and doesn't do exactly what I want, which presents it's own problems.

I should probably also fire off an email to the folks at Yahoo! Sports and see if they won't just make an archive available in some convenient format.

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.