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.

Basketball Season Underway

I spent the last few days scraping game data, dusting off code and generally getting the basketball predictor back online.  The current version of the predictor uses an average of 4 linear regressions.  These models are based upon: (1) the Govan rating, (2) the TrueSkill rating, (3) a Batch Gradient Descent (BGD) rating, and (4) a rating based on a wide variety of statistical measures (such as "offensive rebounds per possession").   Individually, each of these models has a RMSE of less than 11 on my test corpus.   Unfortunately, they're all highly correlated, so the combined model doesn't do any better than the best of the underlying models.  Currently it has an RMSE of 10.79 on my test corpus.

During the season I compare the model predictions against the line and "bet" games where the prediction differs significantly from the line.  "Significantly" is a relative term.  When I first started doing this, my model often differed from the line by 10 points or more.  As the model has improved, those differences have narrowed considerably.  (As would be expected.  The line is usually the best predictor.)  In my testing so far this year, I've only seen a difference of more than 5 points once.  There is some good mathematical work on sizing wagers based upon bankroll, perceived advantage, etc., but I've gone to a simple approach of betting $10 with an advantage of < 5 points and $20 with an advantage of >5 points.  (Adopted after the 1/14 games shown below.)

Here are the games the model has "bet" so far (no real money was harmed):

Date	Home	Score	Away	Score	MOV	Line	Pred	Adv	Risk	Win	Result	Won	v.Line
1/14	Tennessee St.	52	SIU Edwardsville	49	3	16	8.8	-7.2	20	17.39	17.39	1	1
1/14	LA Lafayette	87	Florida Intl.	81	6	10	5.1	-4.9	20	19.05	19.05	1	1
1/14	Murray St.	81	Tennessee Tech	73	8	12	16.5	4.5	20	18.18	-20	1	0
1/14	Houston	55	Memphis	89	-34	-8.5	-4.2	4.3	20	17.39	-20	1	0
1/15	Ohio St.	80	Indiana	63	17	13.5	9.1	-4.4	10	9.09	-10	1	0
1/15	Bradley	78	Northern Iowa	67	11	-10	-7.2	2.8	10	8.70	8.70	0	1
1/15	USC	47	UCLA	66	-19	2	1.5	-0.5	10	9.09	9.09	0	1
1/16	Syracuse	71	Pittsburgh	63	8	13.5	17.3	3.8	10	9.09	-10	1	0

So far this season the model is 50% against the line (and subsequently down about $5) and 75% picking the correct outcome.  The (evolving) model picked 38 games last year, and over the two seasons so far is at a 63% win percentage and 60% versus the line (+$133).  Both are probably short-term aberrations -- the model has a 74% win percentage when tested against my corpus of 12K games.

I won't generally be posting predictions, but I will try to summarize the model's performance a few times during the season, as I'm sure it makes for interesting reading :-).

Football Wrap-Up

A quick wrap-up of my performance predicting NCAA football.

This experiment started around the beginning of October, when some friends challenged me to use my program to predict football against a couple of other guys.  In addition to predicting games, we would be "betting" against the line.  We could use any betting strategy we desired to allocate $40 per week.  The default strategy was to bet the biggest differences between the prediction and the line, allocating bets of $10, $8, $6... etc.  My own betting strategy was a bit more complex.  I allocated money according to the formula:

$$ =  80*ABS(Prediction-Line)/(100+5*ABS(Line)))

.The idea being to scale the bet to the relative magnitude of the difference between the prediction and the line.  A difference of 3 points is much more significant when the line is 3 than when the line is 27.

I predicted games from Oct 16 through the end of the bowl season.  My program doesn't account for neutral site games, so the bowl games were treated as home games for the higher-ranked team.  (This works well in practice on the basketball side for the NCAA tournament.)  I predicted a total of 224 games.  The results:

Measure	Performance
Correct game winner	73%
Correct pick against the line	56%
Betting result	+$29

Overall, better results than I expected.  56% against the line is sufficient to be a winning bettor (if it can be maintained).

A Call from Bill Hancock

(I promise to get back to the prediction stuff soon -- after a dalliance with NCAA football I've started to ramp back up for basketball.  In the meantime, this imagined scenario from last night, inspired by my earlier comment that the NCAA was only allowing ten players on defense to spice up the bowl season.)

Phone call at spacious Turner Mansion last night:

(Ring, Ring)

Me:  Hello?  Oh, hello Mr. Hancock.  How is your job as BCS Executive Director going?

Hancock: (mumble mumble mumble)

Me: Well, you're welcome.  I'm glad my suggestion to only play ten players on defense has worked out so well.

Hancock: (mumble mumble mumble)

Me: *Nine* on defense?  No, I'm not sure that's a good idea.  We've been counting on the fact that most sports writers can't count past ten.   So far they haven't noticed.  But you put nine players out there and someone is going to write about it.  And where does it all end?  Eight players?  Seven players?

Hancock: (mumble mumble mumble)

Me: No, sir, that was a joke.  I'm not recommending seven players on defense.  Listen, I don't think this is a good idea.  Baylor just obliterated the points scoring record for a bowl game.  This is Baylor, the doormat of the Big 12, a university whose only men's championship is in *tennis*.  And then you had Wisconsin -- Wisconsin of all teams! -- throwing the ball all over the field and scoring 38 points.  That's more than the Wisconsin basketball team scored last season.  I realize you want to turn it up to eleven for the Orange Bowl, but this is not a good idea.

Hancock: (mumble mumble mumble)

Me: You're worried about Clemson's defense?  With all due respect, sir, Clemson is an ACC team.  The last time the ACC won a meaningful bowl game it was actually played for a bowl.  If you gave the ACC space lasers they couldn't defend Fort Knox against a Boy Scout troop.

Hancock: (mumble mumble mumble)

Me: True, it is West Virginia.

Hancock: (mumble mumble mumble)

Me: No, sir, West Virginia is part of the United States.

Hancock: (mumble mumble mumble)

Me: No apology necessary.  It's a common misconception.

Hancock: (mumble mumble mumble)

Me: Well, you do what you have to do, sir.  Personally, I'm a traditionalist.  Just tell the officials the result and let them take care of it.  That's worked for Duke basketball for decades and no one's the wiser.  Do they have a "charging" call in football?  I can't remember.  But I'm sure you'll make a good decision.

Hancock: (mumble mumble mumble)

Me:  "Bet the over"?  Ha, ha, good one, sir.

k-NN Prediction

"Andywocky" commented not too long ago on my Prediction by Similarity posting asking whether I'd looked at k-nearest neighbors (k-NN) algorithms.  At the time I made the original posting I hadn't, but shortly thereafter I had a "D'oh" moment and realized that what I was doing was re-creating k-NN.  So I re-created some of the work I'd done using RapidMiner's k-NN operator.

The basic idea behind k-NN is that we predict the outcome of a new game by finding some number of similar past games, and then use those (say by averaging) to create a prediction for the new game.  The "k" in "k-NN" refers to the "some number" of similar past games -- k might be 5 or 50, indicating that we were using the five most similar, or 50 most similar past games.  "Nearest Neighbor" is just another way of saying similar.  If we think of the games living in a multi-dimensional space -- say a dimension for each statistical value for the game (e.g., rebounds per minute, free throw percentage, etc.) -- then the most similar games are the ones that are the nearest neighbors in this multidimensional space.

There are some subtleties in how this works.  For example, team free throw percentage might vary from (say) 50% to 100%, while rebounds per minute might vary from 0.00 to 0.056.  If we don't normalize those dimensions, one or the other is likely to be far more important in determining the nearest neighbor than the other. But a reasonable starting approach is to characterize each game with as many statistical properties as we have, normalize those to similar scales, and then predict MOV by averaging the MOVs of k nearest-neighbors.

Here's the result of doing that with k=10.  For comparison, I include the performance of the best linear regression predictor based upon the same statistical properties.

Predictor	% Correct	MOV Error
Best Statistical Predictor	72.3%	11.04
k-NN, k=10	59.7%	11.65

This isn't tremendous performance, but we have a few tweaks we can perform.  First, we can try varying k to see if some different number of neighbors provides better performance.  Some searching around produces the best performance in this case when k=41:

Predictor	% Correct	MOV Error
Best Statistical Predictor	72.3%	11.04
k-NN, k=10	59.7%	11.65
k-NN, k=41	71.2%	11.44

Interestingly, this shows a lot of improvement in games correct with only modest improvement in MOV error.

Another tweak we can look at is weighting our results.  Instead of doing a flat average of the 41 nearest neighbors, we can weight each neighbor's contribution to the answer by how close it is to the new game.  We can also try eliminating some of our dimensions to see if accuracy improves.  This provides some further improvement:

Predictor	% Correct	MOV Error
Best Statistical Predictor	72.3%	11.04
k-NN, k=10	59.7%	11.65
k-NN, k=41	71.2%	11.44
k-NN, k=44, weighted subset	72.4%	11.17

With this tweak k-NN is competitive with the best linear regression.  (Although they both trail the best predictors.)

I'm inclined to draw a couple of conclusions from these experiments.  First, 40+ neighbors is a large number, suggesting that while games between statistically similar may be broadly comparable, there's not a strong relationship.  Conversely, the improvement gained by using weighting suggests that closer is still better.  It would seem that good performance with this approach requires a moderate amount of generalization to help "wash out" the random component in game outcomes.

Football Predictions (11/15/11)

I hope to have some time in the next day or so for some postings, so here are the predictions for this week in NCAA football.  I've been tracking this performance for a contest, and for the past three weeks I'm 56% against the line (and 71% winners).  That might be anomalously good performance, but I've been positive against the line every week, so take that for what it is worth.

As always, heed the Net Prophet Disclaimer.

NCAA Football Predictions (11/15/11)

Home Team	Away Team	MOV
Air Force	Nevada-Las Vegas	16.1
Arizona State	Arizona	18
Arkansas	Mississippi State	13.1
Baylor	Oklahoma	-14.2
Bowling Green State	Ohio	-6.7
Brigham Young	New Mexico State	15.7
Buffalo	Akron	12.3
Central Michigan	Toledo	-14.9
Connecticut	Louisville	0.4
Duke	Georgia Tech	-6.9
East Carolina	Central Florida	-8
Florida State	Virginia	16.8
Georgia	Kentucky	24.5
Hawaii	Fresno State	9
Houston	Southern Methodist	18.3
Idaho	Utah State	-8.3
Illinois	Wisconsin	-9.9
Iowa State	Oklahoma State	-17
Kent	Eastern Michigan	6
Louisiana-Monroe	Florida International	-3.3
Memphis	Marshall	-15.4
Miami (Ohio)	Western Michigan	-2.4
Michigan	Nebraska	10.2
Michigan State	Indiana	20.9
Middle Tennessee State	Arkansas State	-11.5
Mississippi	Louisiana State	-26.3
Missouri	Texas Tech	15.2
Nevada	Louisiana Tech	1.8
North Carolina State	Clemson	-9.1
North Texas	Western Kentucky	2
Northern Illinois	Ball State	11.5
Northwestern	Minnesota	14.3
Notre Dame	Boston College	22.3
Ohio State	Penn State	1
Oregon	Southern California	14.9
Oregon State	Washington	-0.4
Purdue	Iowa	-1.6
Rice	Tulane	15
Rutgers	Cincinnati	0.8
San Diego State	Boise State	-13.6
San Jose State	Navy	-1.8
South Florida	Miami (Florida)	3.9
Stanford	California	20.3
Temple	Army	15.8
Tennessee	Vanderbilt	2.6
Texas	Kansas State	3
Texas A&M	Kansas	23.8
Texas Christian	Colorado State	24.4
Texas-El Paso	Tulsa	-10.4
Troy	Florida Atlantic	11.2
Uab	Southern Mississippi	-26.2
Ucla	Colorado	12.2
Virginia Tech	North Carolina	6
Wake Forest	Maryland	11.1
Washington State	Utah	-2.4
Wyoming	New Mexico	20.4

One Bad (Good) Game

As mentioned in my previous posting, I recently looked at the effect of dropping a football team's best game (highest Margin of Victory) and their worst game (lowest MOV).  The intuitive notion is that everybody has bad days, where everything goes wrong, and good days, where everything goes right, and maybe those days don't tell us anything useful about the real strength of a team.  If that's so, then dropping those games might give us ratings that are more accurate.

To test this hypothesis I implemented this "drop the worst score" grading system for a couple of the rating systems I use for football and measured performance in the usual way.  Here are the results for one of the rating systems:

Predictor	% Correct	MOV Error
BGD Baseline	73.7%	16.52
BGD w/o blowouts or lowouts	72.6%	16.77
BGD w/o lowouts	72.9%	16.69
BGD w/o blowouts	73.6%	16.62

Here I'm using the whimsical "lowout" to indicate the worst loss for a team.

As this shows, eliminating the blowouts/lowouts hurts predictive performance.  For what it's worth, the losses seem to be more important than the wins.  (I saw the same effect in basketball when I looked at this last year.)