Thursday, June 9, 2011

LRMC Revisited

As mentioned last time, the poor performance of LRMC in my testing had me concerned that I had misunderstood some essential element of the system, or had a mistake in my implementation.  So I took the time over the last few days to re-read the original papers and create a second implementation.  My original implementation adapted the Random Walkers model, essentially simulating the Markov Chain network iteratively until it settled to steady-state values.  An alternative approach is to solve the Markov Chain problem via linear algebra.  There are a couple of possible approaches, but (simply because it was easiest to implement) I settled on the Power Method.  The basic idea is to calculate the transition values of the Markov Chain and capture them in a large matrix (~350x350, the number of NCAA Div I Basketball teams) which we call T, and then create a 350x1 matrix containing an initial guess at the ratings of all the teams, which we call π.  We then perform the following calculation iteratively:

πk+1 = πkT
Until π reaches a steady state.  (In this case, 8 iterations gives us accuracy to 4 digits.)  With a 350x350 transition matrix, it is also feasible to solve this analytically as a system of linear equations, but I didn't have a library handy for that computation.

Here are the comparative results of the two different implementations:

  Predictor    % Correct    MOV Error  
TrueSkill + iRPI72.9%11.01
LRMC (random walkers, 2006)71.3%11.65
LRMC (matrix, 2006)71.5%11.65
LRMC (random walkers, 2010)71.8%11.40
LRMC (matrix, 2010)72.2%11.37

(2006 and 2010 here refer to the two different LRMC functions from [Sokol 2006] and [Sokol 2010].)

This shows some small differences between the implementations (probably due to different degrees of accuracy) but no significant errors. So it would appear that despite its good showing in predicting recent NCAA Tournament results, LRMC is not as accurate as TrueSkill, IMOV and some of the other ratings.

No comments:

Post a Comment