Slashdot Mirror
Using Graph Theory To Predict NCAA Tournament Outcomes
New submitter SocratesJedi writes "Like many technically-minded people, I don't have a lot of time to keep up with sports. Nevertheless, trying to predict the outcome of the NCAA men's basketball tournament is a fun activity to share with friends, family and colleagues. This year, I abandoned my usual strategy of quasi-randomly choosing teams and instead modeled the win-loss history of all Division I teams as a weighted network. The network included information from 5242 games played during the 2011-2012 season. From this, teams came be ranked using tools from graph theory and those rankings can be used to predict tournament outcomes. Without any a priori information, this method accurately identified all the #1 seeds in the top 5 best teams. It also predicts that at least one underdog, Belmont (#14 seed), will reach the Elite Eight. Although the ultimate test will be how well it predicts tournament outcomes, initial benchmarks suggest 70-80% accuracy would not be unreasonable."
Then what, pray tell, are you doing here?
You can only drink 30 or 40 glasses of beer a day, no matter how rich you are.
-- Colonel Adolphus Busch
wouldn't running the algorithm against past years' records and testing against past tournament results be the best possible test to tune the algorithm?
Everyone knows who the big names are who are likely to make it to the final four. It's predicting how things will go at the middle and bottom, where teams are much more likely to be evenly matched, that's really hard.
SJW: Someone who has run out of real oppression, and has to fake it.
Okay, you can get 50% accuracy just by flipping a coin.
If you go with "the higher seed wins", you get to 85% or so. Color me unimpressed.
Blogger blogs on his blog! News at 11!
You can get very reasonable results by just taking last years results. This works for most sports.
People have been doing this, either knowing or unknowingly, since the inception of sports gambling.
Some problems I see. Disclaimer: I know there's a margin of error here as the author said, and I know my observations will be based largely on anecdotal evidence, making it inferior. But if sports were so easy to predict there would be no sports gambling.
- That's probably too far for Belmont; a #14 has only ever gotten as far as the Sweet 16, twice (Cleveland State '86, Chattanooga '97). Lowest seed to make an Elite 8 is Missouri in 2002 as a #12 . Belmont is actually going to be one of the more popular upset picks, but they would have to upset two far superior teams twice in 3 days.
- It's a bit too "chalk". #1 seeds generally survive the first two games (undefeated against #16's, 55-14 v. #8's, 59-6 v. #9's), but the #2's have it worse (only four losses v. #15's, but 58-21 v. #7's and 29-21 v. #10's). I know two #12's, a #13 and a #14 doesn't seem like "chalk" but historically it's much more likely that we'll see more #5-7 or #10-11's. To have only one #2 not make the Elite 8 and all the #1's would be almost unheard of.
- A #12 always beats a #5, but three of them doing so in one year would seem unlikely, as they're only 39-89 overall.
- Some of the other first round matchups seem a bit improbably. It has every #6 and every #7 winning, for example.
... have a lot of time to keep up with sports."
Yes, if you enjoy sports, you must not be technically-minded. Tis for the plebes...
But, I bet you have time for Skyrim!
...you're rich! 70~80% accuracy beats the 70~80% of people who don't know/use/master the graph theory, thus you're gonna win 70~80% of online bets.
Slashdot, fix the reply notifications... You won't get away with it...
March Madness is notoriously hard to predict, partly because of the number of teams involved and also because of the single elimination system that I love so much. Its prevalent in few sports and makes each game mean a lot more, also opening the door for cinderalla to take her 15 minutes of fame. 7-game playoff rounds like they have in Baseball and the NBA tend to nullify those outliers. I honestly think that's a big reason for the success of the NFL too - every game and every play means a hell of a lot more when the best possible record is 19-0.
Can you write a windows installer for it and sell it to gamblers?
Like many technically-minded people, I don't have a lot of time to keep up with sports.
The word you're looking for is "Nerd". It's OK to say it, it's in the title-bar of Slashdot.
It can't.
No way to account for the levels of idiocy on Wall Street. See AAPL's PE vs growth rate for example.
I make my brackets based on mascots. Look at the mascots and decide, "In a fight, which would beat the other one".
Just have to find one with 32 tentacles. Or a large appetite.
Development is programmable; Discovery is not programmable. (Fuller)
here are my two algorithms for ncaa football and basketball.
http://homepages.uc.edu/~carrahle/rankFootball.py
http://homepages.uc.edu/~carrahle/ncaa.py
the first uses a hits model, so multi component ranking while the latter uses principle component analysis.
i agree, with the above comment 70-80 seems high. I actually went through a somewhat lengthy projection to latent space learning phase to try and better rank information about teams. instead of simply using win/loss through multiple years (also weighting time distance) i also used the full box scores such as rebounds, shots on, fouls etc for each player. And didnt come near that accuracy. My end conclusions is that especially for basketball, the teams are just too turbulent to be very consistently accurate with. none-the-less good luck. I think this is why we don't use PCA to seed bowl games in football, simply put, people are better at ranking.
You're some way behind the curve if you want to make money sports betting on this. There is an extreme non-stationarity problem with basketball teams which inevitably means methods using past statistics will never be that successful. I know of professional basketball modellers who pay an army of students and the like to watch college games while clicking on hand-held devices to record second-by-second data on passes, interceptions etc. This data is then fed into their models and provides a very accurate picture of how a team is playing right now. They are then able to handicap the games and look for value where the line is wrong.
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1176059&tag=1 : "Temporal principal component analysis - advances in dual auto-regressive modeling for blind Gaussian process identification "
This paper combines Autoregressive model with a principle component model. could be useful to better discover hot streaks, ie UC beating Marquette, Georgetown, Villanova then Syracuse! despite being heavily outranked. It was a winning streak and they totally need to be modelled.
Nothing like a little graph theory to bring excitement to NCAA Basketball.
(I'm not even kidding.)
Between 70 and 80%. That's a HUGE difference. That means that compared to the other computerized systems out there you're either totally awesome or really suck.
That's like saying, "I did a lap in a Formula 1 car, and I'm either 15 seconds ahead of last year's world champion, or I'm a minute behind the field."
You haven't done this before, have you?
His statistical reasoning is always well described, so that if you disagree with his results, at least you understand why you disagree. He's got "picks" and a description of the system used to generate them.
The original article is an interesting network analysis exercise, but it is really limited by its assumption of no a priori quality data. (Any time you beat Kentucky or North Carolina or other perennial powerhouses, that's almost always a quality win.) Sagarin and LRMC follow similar logic, but without an explicit network piece.
See AAPL's PE vs growth rate for example.
You mean how low their PE is? By rights their stock should be up around $600/share.
The opposite of progress is congress
You don't have time to follow sports, but you have time to model "information from 5242 games played during the 2011-2012 season".
You could be honest and just say you don't really care, but get involved in the playoffs because everyone else is talking about it.
I'm guessing your level 80 warlock probably doesn't 'have time' either. :)
1. Go to Vegas
2. Use you predictions to place bets
3. profit!
It seems in office pools I do the best by picking favorite team colors.
70%-80% accuracy is what most algorithms can do (the others being worse), which is also similar to expert prediction. Here we have a way of being very precise, but of not significantly increasing accuracy. I suppose it might be more accurate than the designers' guesswork, however.
Yes. If fairly valued at a PE of say 25 or so (which is still low for their growth rate), their stock should be at $875 or so.
MOT, INTC, EMC, JNPR are all similarly valued. But have much lower growth rates.
BIDU is the only large tech company with a similar growth rate. It's PE is 46, which would put AAPLs stock price at $1615.
VMware has lower growth, but a PE of 60. AAPL would be at $2100 if similarly valued.
http://www.google.com/finance#stockscreener
There are two types of people in the world: Those who crave closure
Yeah, like when someone intentionally throws a game. As long as people are gambling (somewhere) and money is to be made, there is an opportunity and incentive to cheat. Get your graph theory to account for that!
Or maybe regression analysis is better like Levitt used to find cheating with Sumo wrestling and US student test takers in his book Freakonomics. (Awesome book BTW) ;)
At least in Skyrim, you're an interactive participant. That, and Skyrim isn't just a polite way for people to act out their base tribalistic instincts.
Give me Classic Slashdot or give me death!
After reviewing his results, both ranking team and the bracket results, I notice that he ranks West Virginia University 91. Two teams WVU beat handily, Kansas State and Georgetown are ranked 66 and 65 respectively. WVU also lost some very close games to ranked teams, including at Syracuse by 1 point, to Baylor by a basket, and Marquette by a basket.
Regarding the bracket, the four No 1 seeds march along, undefeated, until they meet in the final four. While this can happen, it seems like a trivial and unsophisticated result to me. Perhaps the algorithm should include a bump for a team that looses a close game to a team ranked at 3rd in the nation? Maybe some way to account for a coaches' history in tournament play? Some coaches are better able to prepare a team for specific games, aren't they?
Comment removed based on user account deletion
Skyrim isn't a polite way to act out my base tribalistic instincts? Am I offending people when I slaughter entire towns of virtual Argonian civilians?
Comment removed based on user account deletion
Comment removed based on user account deletion
Someone is still smarting about being stuffed into lockers?
There's too much data and too many variables. Even just inputting all the known, public data might significantly improve the accuracy, but there's also lots of unknown private data that can influence games. Algorithms like this can't account for things like the coach's son getting killed in an automobile accident the night before a game, or the star center getting hit with a bad flu. And when you make it complex enough to take in all that data, it still has to get all that data somewhere, which means it has to have access to all news feeds, and it has to be accurate at knowing which ones are appliccable, etc. etc... or you have to manually input all that data, which would take a horrific amount of time. In the end, it's so much easier to just intuitively account for things like that without using a computer, which I believe is why human experts are just as good as computers at predicting outcomes. We don't calculate the hard statistics as well, but we can account for the human element.
There is no -1 Disagree mod. Slashdot.org/faq defines mod options. USE IT.
... modeled the win-loss history of all Division I teams as a weighted network. The network included information from 5242 games played during the 2011-2012 season. From this, teams came be ranked using tools from graph theory ...
... you obviously don't have enough time to keep up with sports.
It must have been something you assimilated. . . .
A quick glance at the predictions suggests that something just doesn't look right.
Typically, the 14 seeds are teams that got in by virtue of winning their conference. It's highly unlikely to have an at-large selection seeded below 13. It's very odd to see two at-large teams, BYU and Iona, in a play-in game for a 14 seed. I'm surprised just to see an at-large team come from the Metro Atlantic. This makes a huge difference because the at-large teams got in because of their resume and not because they got an automatic bid from a weak conference. There's a big drop-off from the 13 to the 14 seeds, and another drop-off with the 15 seeds. Although upsets by 14 seeds are hardly unheard of, unlike the very rare 15 over 2 upset, it would be very surprising to see two 14 seeds win. I would be even more surprised to see a 14 seed advance to the elite eight. The lowest seed I can remember advancing to the elite eight was Missouri, a 12 seed, back in 2001-02. But that was an incredibly talented Missouri team that was once ranked as high as #3 before collapsing during the Big 12 conference schedule. They were an at large team, and played some good basketball right at the end of the season to earn their way into the tournament.
If I was going to pick a 14 seed to advance, I might pick the winner of the BYU-Iona game. But even that's questionable. I'm not impressed at all with Iona's resume. I might suspect they could beat a quality team in the tournament if they had pulled out the win against Purdue. I know, it's at the beginning of the season, but there's not much impressive on Iona's schedule. And, had they won against Purdue, they likely wouldn't be in a play-in game as a 14 seed, either. While BYU has a similar record to Gonzaga, there's a big difference between the overall profiles. Gonzaga has non-conference wins that look really impressive, especially against Notre Dame. Again, BYU is a 14 seed for a reason and there's not a whole lot to like. They had a chance for a much bigger win than Iona's game against Purdue when BYU lost by three points to Baylor. Beating Baylor would have convinced me they could pull out a win against a higher seeded team in the tournament. But, then again, if they had beat Baylor, they would quite possibly be a 12 seed instead of a 14 seed. None of the 14 seeds look worthy of an upset pick.
Teams like VCU and George Mason, which also made runs in the past few years, were 11 seeds. Harvard and Long Beach State might be good candidates to make a run in the tournament. VCU can't be ignored, either. Even Davidson showed they could beat good teams when they upset Kansas at the Sprint Center, which might as well have been a home game for the Jayhawks. If you want to pick an upset below the 5-12 games, I'd pick Davidson to win a game.
It's also very unlikely to see all the teams seeded at 6, 7, and 8 winning their first games. Those teams are very evenly matched and there is basically no difference between an 8 and a 9 seed. I have no problem with three 12 seeds winning in the first round. But I would pick some 11, 10, and 9 seeds to win games, too.
Maybe the predictions will work out better than I expect. But if I'm entering a bracket in a pool, it sure wouldn't look like that. If Belmont makes it to the elite eight, someone will make a lot of money from that bracket. But I sure wouldn't be betting on that.
""The problem stems from the fact that we traditionally predict a team will win if it is a stronger or better team, and we use our graph theory to produce relative team ratings. And if each game of the tournament were played over and over again with the winner of the majority going to the next round, then our methods would work even better. As it stands though, we are trying to predict a single sampling from a probability distribution - which will necessarily have error. Informally, the real tournament has upsets (when a weaker team beats a stronger one). Our algorithms can't predict these, the best they can do is gain a better understanding than humans as to which team is better.""
You cannot predict this stuff because you have no way to factor in players performances no matter which team they are on. You could have players on top ranked teams just suck out, and players on the lower seeded teams have the game of there season. Injuries, and fouls play a roll in which teams go on and those that go home. Then there is always the karma factor, for some strange reason science cannot fully figure out. IE Bounces going one way fouls that players are not getting to go there way, or bad foul calls.
Prefect game for this is Ice Hockey, for some odd reason a team has won 7 out of 10 games by one goal lost 3 by one goal. The 11th game sees them get blown out by a score of 8 - 0, 2-3 games later they do the same to the another team. In the 11th game you can usually tell it is not going there way sticks are breaking while trying to clear pucks, the pucks bounce over there sticks, players falling to the ice with no one around. But no one can explain why this happens it just does.
This is the same for any prediction the weather is a prime example of how bad they fail at predictions, factors not fully known or unseen account for this.
I understand these predictions are for fun, or just something to mess with. You have a 30% chance of getting your predictions right, in one of those off the wall tourney years. And 70% if the Tourneys go the way they are usually expected.
Yeah, screw those people reading books, watching movies, or listening to music. They should be doing something more interactive! Seriously, why do you care if people want to relax by watching sports?
Yeah... no. If I ever see that headline I'll eat my hat. And I'm not even a KU fan.