Try calculating “OPR” using min L1 norm of residuals (LAD) instead of min L2 norm (least squares), and see how that compares.
I’ve tried the L1 optimization problem, but l1-magic is giving me fits. For some reason, it blows up after 10 iterations.
However, I have done the analysis that I wanted. I calculated all the rating systems using data from events prior to CMP, then I used that data to predict CMP matches.
In summary:
OPR: 72.46% Correct
TrueSkill: 69.31% Correct
Elo: 72.90% Correct
Elo Mod: 71.71% Correct
TL;DR: We’re okay, but not great at predicting matches. OPR is okay at it, but Elo is better.
I’m still somewhat surprised that Elo is slightly better.
Updated Spreadsheet: https://dl.dropboxusercontent.com/u/5193107/Elo%20Trueskill%202.xlsx
What solver are you using ?
Try CCWM.
I’m using the l1eq_pd.m function in the L1-Magic library (http://users.ece.gatech.edu/~justin/l1magic/)
CCWM: 71.41%
That’s the wrong solver.
*
***% l1eq_pd.m
%
% Solve
% min_x ||x||_1 s.t. Ax = b **
Firstly, you cannot find a min L1 norm vector x such that Ax=b because there is no vector x such that Ax=b, since the system is overdetermined.
Secondly, what you want to find is the min L1 norm of the residuals, not of the solution vector itself.
For the set of overdetermined linear equations Ax ≈ b, x is the solution vector. The residuals are b-Ax. So you want find a solution vector x which minimizes the L1 norm of b-Ax.
*Attached is a comparison of b-Ax residuals for L2 and L1 OPR.
Alliance scores computed from L1 OPR are within +/-10 points of the actual scores 33.5% of the time.
Alliance scores computed from L2 OPR are within +/-10 points of the actual scores only 22.4% of the time.
It is on that basis that I postulate that L1 OPR might be a better predictor of match outcome.
[EDIT]Cannot add attachments to threads associated with papers. Brandon: can you please change this setting to allow attachments? Thank you.[/EDIT]
I just ran the OPR numbers using the data you linked in your earlier post. I came up with 6919 of 8921 matches correctly “postdicted”, or 77.56%
Our numbers are very close, but I had expected them to be identical.
Here’s a link to an XLS spreadsheet.
The differences are how we’re calling tied matches. The way you’re calculating if OPR “correctly” predicted falls apart when the actual result of the match was a tie. Almost always, the OPR will not predict a tie.
Ya, I’ll admit I don’t know what I’m doing with the L1 stuff. It’s a new concept to me, so I just did some quick googling and thought I found a quick solution.
77.75% correct (discarding ties)
77.11% correct (counting ties as incorrect)
77.93% correct (counting ties as correct)
It looks like we’re in agreement when counting ties as incorrect.
You have an overdetermined linear system
Ax ≈ b,
where A is the (binary) design matrix of alliances, b is a column vector of alliance scores, and x is what you are trying to find: a column vector of team “OPR” scores.
There is no exact solution for x, since the system is overdetermined. So the idea is to find the “best” solution (in some sense of the word “best”).
Notice that the left-hand side (Ax) is a column vector of alliance scores computed from whatever solution x you come up with.
The residuals are b-Ax: a column vector of the differences between the actual alliance scores (b) and the computed alliance scores (Ax).
Looking at it that way, it becomes clear that what you are trying to do is find a solution x which minimizes the residuals (in some sense of the word “minimize”).
The most common way to do this is to find x which minimizes the L2 norm of the residuals. The L2 norm of a vector is the square root of the sum of the squares of the vector’s elements. The L2 norm solution is also known as the “least squares” solution (for obvious reasons).
It turns out that finding the x which minimizes the L2 norm of b-Ax is computationally straightforward.
In Octave, it’s one line of code: x = A\b. The backslash in this context is known as “left division”. The syntax is simple, but under the hood there’s a lot going on.
For the Ax ≈ b overdetermined linear systems were are dealing with in FRC to compute OPR scores, it turns out that there is a computationally faster way to compute the least squares solution for x. Here’s how:
Multiply both sides of Ax ≈ b by the transpose of A to get A’Ax = A’b, or Nx =d where N=A’A and d = A’b.
Nx =d is known as the system of “Normal Equations”, and its solution x = N\d gives the same answer as A\b (within rounding error) and is faster to compute.
But “least squares” (min L2 norm of residuals) is not the only possible “best fit” solution to the overdetermined system Ax ≈ b.
For example, there’s the “Least Absolute Deviations (LAD)” solution (min L1 norm of residuals). The L1 norm of a vector is the sum of the absolute values of the vector’s elements.
Finding an LAD solution for Ax ≈ b is more computationally intensive than least squares.
Perhaps the best way to proceed is to convert the problem to a “Linear Program” (LP) and then use one of the many LP solvers.
For example, here’s the AMPL code I used to compute the LAD OPR for your data:
param m;
param n;
set I := {1..m};
set J := {1..n};
param A{I,J};
param b{I};
var x{J};
var t{I} >= 0;
minimize sum_dev:
sum {i in I} t*;
subject to lower_bound {i in I}:
-t* <= b* - sum {j in J} A**x[j];
subject to upper_bound {i in I}:
b* - sum {j in J} A**x[j] <= t*;