Incorporating Opposing Alliance Information in CCWM Calculations

[AGPapa]

Originally Posted by wgardner

Yes, this makes sense if you want to compare results across events. Sounds like a good idea, though perhaps then it needs a different name as it's not a WM measure? Also, if I continue to find that scaling the WMPRs down does a better job at winning margin prediction, that needs to be done before the average event score/3 is added in.

I'll try to get to the verification on testing data in the next day or so.

I personally like this normalized WMPR (nWMPR?) better than EPR as the interpretation is cleaner: we're just trying to predict the winning margin. EPR is trying to predict the individual scores and the winning margin and weighting the residuals all the same. It's a bit more ad-hoc. On the other hand, one could look into which weightings result in the best overall result in terms of whatever measure of result folks care about.

I'd still consider it a WM measure, as it doesn't only take offense into account (like OPR). This WMPR tells us how many points this robot will score and how many it'll take away from the opponents, that sounds like win margin to me, no? I don't really like the nWMPR name, it's long/slightly confusing. I think this thread should work out the kinks in this new statistic and call the final product "WMPR".

In order for this to catch on it should
1. Be better than OPR at predicting the winner of a match
2. Be easy to understand
3. Have a catchy name
4. Apply very well to all modern FRC games
5. Be easy to compare across events

I think that by adding in the average score and calling it "WMPR" we accomplish all of those things. 2015 is probably the strangest game we've had (and I would think the worst for WMPR), and yet WMPR still works pretty well.

I'm not sure why scaling down gives you better results at predicting the margin. I know you said it decreases the variance of the residuals, but does it also introduce bias? Would you propose a universal scaling factor, or one dependent on the event/game?

Originally Posted by Ed Law

I think EPR would be more accurate in predicting match scores. Would somebody like to test it out?
Another reason I like EPR is that it is easier to compute without all that
SVD stuff. I would prefer high school students to be able to understand and implement this on their own.

You actually don't need to know anything about singular value decomposition to understand WMPR. It can be explained simply like this:

Ax=b

Where A is who played on what alliance in each match and b is the margin of victory in each match. x is the contribution from each robot to the margin. You'd expect x to be the inverse of A times b, but A is not invertable, so we use the pseudoinverse of A instead.

In Matlab the code is

x = pinv(A)*b

And that's it, pretty simple.

I agree with you though that the ultimate test would be how it performs in predicting matches. I compared it to WMPR in the 2014 Archimedes division, although that was with using the training data as the testing data, so it's probably not the best test.

[Ether]

Originally Posted by AGPapa

Thoughts?

See attached XLS. I was playing around with it yesterday. There's all sorts of fun things you could try.

Column D looks a lot like what you're suggesting, except it adds the average OPR instead.


Also attached are 2013 A b T for OPR CCWM WMPR and EPR. The raw qual match data from TBA used to generate those is posted here.

Originally Posted by saikiranra

If I'm understanding this properly, are we setting square matrix for that system as the following?

| 2 2 2 -1 -1 -1 | |r1| = |2RS - BS|
| 2 2 2 -1 -1 -1 | |r2| = |2RS - BS|
| 2 2 2 -1 -1 -1 | |r3| = |2RS - BS|
| -1 -1 -1 2 2 2 | |b1| = |2BS - RS|
| -1 -1 -1 2 2 2 | |b2| = |2BS - RS|
| -1 -1 -1 2 2 2 | |b3| = |2BS - RS|

Each match generates 3 equations (3 rows in the A matrix and 3 scores in the b matrix).

If you look at _Aepr.CSV (or _Aepr.dat) and _bepr.CSV (or _bepr.dat) it should be pretty clear.

Then you solve for EPR like so: EPR = pinv(Aepr)*bepr

If you want to see what the matrix for the normal equations looks like, look at Method 2 in this post. N will be square.

Originally Posted by wgardner

perhaps then it needs a different name as it's not a WM measure?

?? I thought Wm stood for "William"




Just kidding.

[Basel A]

Originally Posted by wgardner

Thoughts? This seems like an improvement to me, but I'd be curious to hear what other stat-nerds like me have to say on the matter. And if somebody else has already looked into all of this, accept my apologies and please help educate me.

Won't you simply end up with OPR? OPR does R = C1 + C2 + C3 and B = C4 + C5 + C6. Your suggestion subtracts the second equation from the first, so it's really the same. Or will the solution be different because of the different error term being minimised?

[wgardner]

Originally Posted by Basel A

Won't you simply end up with OPR? OPR does R = C1 + C2 + C3 and B = C4 + C5 + C6. Your suggestion subtracts the second equation from the first, so it's really the same. Or will the solution be different because of the different error term being minimised?

I don't think so. Minimizing (R - (C1+C2+C3))^2 + (B - (C4+C5+C6))^2 is different than minimizing ((R-B) - ((C1+C2+C3)-(C4+C5+C6))^2

Another way to look at it: Say that all Team 2 does is play defense against the opposing alliance and reduce its score by 25 points every time it plays. C2 should be 25 (minus any mean term). But if you only look at C1+C2+C3 as a way to predict R, C2 will look like zero because C2 doesn't affect R. But C2 does affect (R-B) by making B smaller by 25 points, so the new metric should be able to capture this effect.

[Ether]

Originally Posted by wgardner

So, here's my proposal.

Instead of modeling each match outcome twice as above, do it only once as follows:
R-B = (C1 + C2 + C3) - (C4 + C5 + C6)

I dub this metric GPR :-)

I ran the numbers for 2015 MISJO (40 teams, 80 qual matches, no DQs, no surrogates).

[AGPapa]

Originally Posted by Ether

I dub this metric GPR :-)

I ran the numbers for 2015 MISJO (40 teams, 80 qual matches, no DQs, no surrogates).

EDIT2: Ignore this, it uses incorrect numbers.

I checked out how these stats relate to the match results.

Your numbers correctly predicted* the outcome of 66% of matches, while OPR and CCWM both predicted the correct winner 84% of the time.

It makes sense that this stat doesn't work for a game where the other alliance can't affect your score. Can you run the numbers for a 2014 event so we can see if it's better with that?


*I don't like these sorts of "predictions" because they occur with numbers obtained after the fact. Could you also run numbers for the first ~60 qual matches and then we'll see how they do on the next 20?


EDIT: Looking through the numbers a little, more, I can see that this new stat gives radically different evaluations to a few teams than OPR and CCWM. Look at these select teams:

Team         GCCWM    OPR      CCWM
3688	   -22.0    44.7	23.5
2474	   -2.3	    54.2        21.8
1940	    8.4	     5.4       -22.5

The first two are very undervalued by GCCWM while the last one is very overvalued. These aren't the only egregious differences.

Here are the correlation coef for each pair of metrics:
OPR-CCWM: 0.82
GCCWM-CCWM: 0.39
GCCWM-OPR: 0.35

Originally Posted by wgardner

But the easy way around this is to just find the minimum norm solution (one of the many solutions) using, say, the singular value decomposition(SVD), and then subtract off the mean from all of the values. The resulting combined contributions to winning margin values represent how much a team will contribute to its winning margin compared to the average team's contribution (which will be 0, of course).

Could you explain a bit more how SVD will help you find the minimum norm solution? Unfortunately I'm only familiar with SVD in terms of geometric transformations.

[saikiranra]

Attached is the GPR calculated for all 8 championship divisions this year, with OPR, CCWM, and DPR also given as reference (I did not take in account surrogate matches and such). I can generate a new one of these for any event that has data on TBA.

Originally Posted by AGPapa

Could you explain a bit more how SVD will help you find the minimum norm solution? Unfortunately I'm only familiar with SVD in terms of geometric transformations.

I believe you can use the SVD to find the psuedo inverse matrix using the Moore-Penrose method. I used a Moore-Penrose psuedo matrix method in the Python Numpy library, although I believe that the general solve method in Numpy does something similar. I'm also new at this entire statistics world, so I'm sure one of the guru's here can fill us in.

[wgardner]

Long post to come later today with more detailed thoughts and examples (I hope), but some quick initial thoughts are:

1. Please drop the "G" from everything. Since I can't think of anything better, may I suggest we call it CCWM with Opposing Alliances, or CCWMOA?

2. As other's noted, CCWM and CCWMOA aren't well suited to the 2015 FRC game because there's virtually no defense and thus virtually no benefit to looking at winning margins over just final offensive scores. Can we look instead at 2014, which had a lot of defense?

3. I'm wondering if the method may be doomed due to insufficient data? With CCWMOA, we only get 1 data point per match, while OPR and CCWM get 2 data points per match. In Ether's example tournament, there were 40 teams and 80 matches, so CCWMOA is trying to use 80 noisy data points to find 40 values, while OPR and CCWM are trying to use 160 noisy data points to find 40 values. Comparing CCWM and CCWMOA, I argue that CCWMs data values are noisier for reasons that I said in my first post, but maybe fitting with 160 noisier data points still gives you a better result than fitting with only 80 data points that are cleaner?

This is like trying to find the slope of a line that you know goes through the origin using 2 noisy points vs 4 noisier points. Which one is better will depend on the ratios of the noises. I hope to think about this more and comment more further with some data to back it up, but I'd be curious to hear the thoughts of other folks too.

Thanks everybody for the discussions!

[wgardner]

Originally Posted by saikiranra

I believe you can use the SVD to find the psuedo inverse matrix using the Moore-Penrose method. I used a Moore-Penrose psuedo matrix method in the Python Numpy library, although I believe that the general solve method in Numpy does something similar. I'm also new at this entire statistics world, so I'm sure one of the guru's here can fill us in.

Yeah, that. For a real positive semi-definite symmetric matrix (like A'A for any A), the SVD is something like U D U' where U is orthogonal and D is diagonal. In our case, A'A is not full rank, so the last diagonal value of D is 0. Using the method in the link above, the pseudo-inverse is computed as U E U' where E is diagonal with elements Ei = 1/Di except where Di=0, in which case Ei=0 too. This makes the product of a matrix and its pseudo-inverse equal to U' F U where F is diagonal with Fi = 1 if Di is non-zero and Fi=0 if Di = 0.

So if the original matrix is full rank, the pseudo-inverse is just the regular inverse and the product of the matrix and pseudo-inverse is U U' = I. If the original matrix is not full rank, then multiplying by the pseudo inverse basically zeros out the component of the vector in the zero-rank projection and multiplies by the inverse of the remaining subspace. Or, the product of the matrix and its pseudo-inverse is U U' except that you replace the vector of U corresponding to Di=0 with a zero vector.

In this case, the zero-rank projection (or the row vector of U' that corresponds to the Di that is zero) is something like 1/T[ 1 1 1 1 ...1] which computes the mean, because the direction in the C vector corresponding to its mean is the direction that cannot be determined.

One other formulation for CCWMOA would just be:
if we have T teams, have T-1 unknown values C1, C2, ..., C(T-1) and set CT = -Sum(C1, C2,... C(T-1)) in all of the equations (thus enforcing that all T values of Ci are zero mean). Then we only have T-1 equations with T-1 unknowns and everything is full rank. This is just another way of saying we want to find the values of C1, C2, ... CT that minimize the prediction error subject to the constraint that the resulting set of Ci values have zero mean.

[wgardner]

One more interesting tid-bit:

For the 2015 FRC game, we would expect that the underlying OPR and CCWM/CCWMOA to be identical except for a mean as a team's only ability to contribute to a winning margin is with offense. The fact that these numbers do deviate substantially (or, that DPR varies as much as it does) shows that we aren't close to having enough data to really get precise estimates of underlying parameters.

Edit: This may not be entirely true. Litter and the initial race for the center cans can both cause one alliance to adversely impact the other alliances score, so it's not 100% true to say that the only way to contribute to the winning margin in the 2015 FRC game was though increasing you own alliance's score.

[Ether]

Originally Posted by wgardner

Yeah, that. For a real positive semi-definite symmetric matrix (like A'A for any A), the SVD is something like U D U' where U is orthogonal and D is diagonal. In our case, A'A is not full rank, so the last diagonal value of D is 0.

With rounding error, it will not be exactly zero. For the 2015 MISJO event, it is 3.43E-16. So your code needs to use a threshold.

Using the method in the link above, the pseudo-inverse is computed as U E U' where E is diagonal with elements Ei = 1/Di except where Di=0

use abs(Di)<threshold instead of Di==0

One other formulation for CCWMOA

We need a better acronym. That's too awkward.

... would just be:
if we have T teams, have T-1 unknown values C1, C2, ..., C(T-1) and set CT = -Sum(C1, C2,... C(T-1)) in all of the equations (thus enforcing that all T values of Ci are zero mean). Then we only have T-1 equations with T-1 unknowns and everything is full rank. This is just another way of saying we want to find the values of C1, C2, ... CT that minimize the prediction error subject to the constraint that the resulting set of Ci values have zero mean.

I ran the numbers for all 117 events in 2015 and found that the following two computational methods yield virtually identical results for min L2 norm of b-Ax:


Method 1

1a) [U,S,V] = svd(A)

1b) Replace the diagonal elements of S with their reciprocals, except when abs(Sjj)<threshold (I used 1e-4 for threshold), in which case make Sjj zero.

1c) compute x = V*S*(U'*b)


Method 2

2a) N = A'*A

2b) d= A'*b

2c) compute x = N\d ..... (Octave mldivide notation)

2d) compute m = mean(x)

2e) subtract m from each element of x


Notice Method 1 factors A, not A'A, resulting in less rounding error.

[wgardner]

Thanks Ether!

I'd love to see the residual of the predictions of the winning margins using OPR, CCWM, and whatever you want to call the new thing (how about WMPR, if you don't like CCWMOA)? It would be interesting to see the average squared winning margin prediction residual and the distribution of the prediction residual (like you did with your L1 v. L2 comparison) for both 2015 FRC tournaments (where defense was essentially non-existent) and 2014 FRC tournaments (where defense mattered more).

It might also be interesting to see if tournaments with lots of matches per team are different from tournaments with few matches per team.

I'm puzzled by AGPapa's finding that the match outcomes (such as they were in 2015) are not predicted as well with the new measure. While minimizing the prediction error in the winning margin isn't the same as predicting the match outcomes, I'd expect the match outcome results to be fairly similar. Thoughts? (BTW, I haven't verified AGPapa's finding, so I suppose there's a chance that there's a bug in the code he used to predict the match outcomes?)

[Edit: AGPapa later found an error with his initially reported results.]

And if you had a lot of time and/or processing power on your hands, I'd also love to see how well the winning margins are predicted for matches that aren't in the training data. Given that we're so low on data, I'm reluctant to suggest the "model with the first 1/2 of the data, then test with the second 1/2 of the data" proposals as we may not have enough data to get a reliable model as it is. Instead, I'd suggest the "model with all of the data except for match 1, then test with match 1, then remodel with all of the data except match 2, then test on match 2, etc." approach as then the data size is almost the same but you're testing on data that's not in the training set.

I'd be happy to do this in scilab too, especially if you could get some 2014 tournament data in your nice formats.

BTW, I computed the new metric this morning using the data from the MISJO tournament you provided and got the same results for the new measures (using the new A and b that you provided), so that confirms that we're talking about the same thing.

[wgardner]

The following results are from my scilab sim for the 2015 MISJO tournament. Again, this should be a BAD tournament year for both CCWM and WMPR as there was little defense involved.

For OPR, the winning margin was predicted by computing the prediction for the offensive score of the red alliance and subtracting the prediction for the offensive score of the blue alliance from it.

For CCWM, the winning margin was predicted by computing the prediction of the winning margin of the red alliance and subtracting the prediction for the winning margin of the blue alliance from it.

For WMPR, the winning margin was computed the same was as in CCWM, but using the values computed using the WMPR derivation instead of the CCWM derivation.

Standard deviations of the prediction residuals of the winning margins:
OPR: 25.6
CCWM: 21.1
WMPR: 15.9

(interesting that CCWM and WMPR both do better than OPR, even in a game with "no defense." Perhaps the race to get the center cans acts like defense in that a team that does well at that may cause the opposing alliance to have a lower score? Or litter?)

The tournament had 80 matches but one match appeared to be a tie, so there were only 79 matches where the match outcome could be predicted.

# of match outcomes predicted correctly:
OPR: 67
CCWM: 66
WMPR: 68

(This is all on the training data (!). I'm not using data not in the training set yet.)

[AGPapa]

Originally Posted by wgardner

# of match outcomes predicted correctly:
OPR: 67
CCWM: 66
WMPR: 68

Can you please attach match-by-match predictions?

I'm getting:

OPR: 67
CCWM: 66
WMPR: 53


Are you using the same numbers in the MISJO_GPR.CSV file that Ether attached? A difference with numbers we're using seems to be the only explanation for this difference since our OPR and CCWM predictions match up.


In the previously attached spreadsheet I erroneously awarded the blue alliance a victory in match 69, it should have been a tie.

[wgardner]

Originally Posted by AGPapa

Can you please attach match-by-match predictions?

I'm getting:

OPR: 67
CCWM: 66
WMPR: 53

Are you using the same numbers in the MISJO_GPR.CSV file that Ether attached?

Attached.
Col1 is WMPR based WM prediction.
Col2 is CCWM based WM prediction.
Col3 is OPR based WM prediction.
Col4 is actual match WM.

I'm using my sim to compute the WMPR values, which I earlier verified matched Ether's values (at least the min and max were identical).