Incorporating Opposing Alliance Information in CCWM Calculations

[wgardner]

This post is primarily of interest to stat-nerds. If you don't know or care what OPR and CCWM are and how they're computed, you probably want to ignore this thread.

---------------------------------------------

It has bothered me for a while that the CCWM calculation does not incorporate any knowledge of which teams are on the opposing alliance, which would seem to be important for a calculation involving the winning margin between the alliances.

The standard calculation is performed as follows:

Let's say that in the first match, the red alliance is teams 1, 2, and 3 and the blue alliance is teams 4, 5, and 6. Let's let the red score in this match be R and the blue score be B. We're trying to find the expected contributions to the winning margins for each team. Let's call these contributions C1, C2, ... for teams 1, 2, ...

The standard CCWM calculation models the winning margin of each match twice (!), first as
R-B = C1 + C2 + C3 (ignoring that teams 4, 5, and 6 are involved!)
and then again as
B-R = C4 + C5 + C6 (ignoring that teams 1, 2, and 3 are involved!)

It finds the least squares solution for the Ci values, or the values of the Ci numbers that minimize the squared prediction error over all of the matches.

This solution in matrix form is solving
(A' A) C = A' M
where (A' M) ends up being the vector of the sum of the winning margins for each team's matches, and
(A' A) is a matrix with diagonal elements equal to the # of matches each team plays and the off diagonal elements equal to the number of times teams i and j were on the same alliance.

Note again that nowhere does this factor in if teams were on opposing alliances (!). If a particular team on the blue alliance always scores 1000 points, that will make the winning margin for the red alliance be awful, and IMHO, that should be taken into account.

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)
(the left set is all the teams on the red alliance and the right set is the blue teams).
Now, we're factoring in both your alliance partners' abilities AND your opponent's abilities.

If you go through the entire derivation, you end up with a similar set of equations, but the new A matrix has a 1 in the i,jth spot if the jth team was on the red alliance in match i, a -1 if the jth team was on the blue alliance in match i, and 0 otherwise.

The solution has the same format, i.e. solving the following formula
(A' A) C = A' M
(A' M) ends up being exactly the same as before even though the A and M are a little different: (A' M) is just the sum of the winning margins for each team's matches.
But now (A' A) is a little different. The diagonal elements are the same, but the off diagonal elements are equal to the number of times teams i and j are on the same alliance minus the number of times they're on opposing alliances (!). So now opposing alliance contributions are included.

One oddity emerges from this formulation: the new (A' A) is not invertible (!). This is because if you add any constant to all of the teams' contributions, the winning margins are the same. For example, if you think the red teams contributed 10, 20, and 30 points each and the blue teams contributed 40, 50, and 60 points each, you'd get exactly the same winning winning margins if the teams' contributions were 110, 120, 130, and 140, 150, and 160, or even 1010, 1020, 1030, and 1040, 1050, and 1060.

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).

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.

[RyanCahoon]

I'd love to see somebody actually quantitatively compare the predictive power of all of these different metrics across the various games. For a given year, take the games from the first half of every competition's qualifying rounds, compute a stat for every team and measure it's ability to predict the outcome of the second half of the qualifying matches. Each of the last 4 years should give a sample size of ~7,500 matches and ~2,500 teams. EDIT: these counts are for FRC. An analysis for FTC would be interesting as well.

[Foster]

And also look at the opposing alliance prior record to get to this match. How did they get their OPR?

Wait, Dean is a big data guy and he wants us to dig into all the past matches? This entire robot thing is just a ruse to get interested in Big Data?

((I worked at one time for a MLB stat company and all of the stats are important. Weather, prior events, crowd sizes, etc. We have just touched the surface of stat possibilities))

[Caleb Sykes]

Originally Posted by Foster

And also look at the opposing alliance prior record to get to this match. How did they get their OPR?

I'm having trouble understanding this sentence. Could you please clarify?

[EricDrost]

Originally Posted by RyanCahoon

I'd love to see somebody actually quantitatively compare the predictive power of all of these different metrics across the various games. For a given year, take the games from the first half of every competition's qualifying rounds, compute a stat for every team and measure it's ability to predict the outcome of the second half of the qualifying matches.

After week 1 this year, normal OPR was the best (non-manual) score predictor. That's what I used throughout the season, though by CMP a different metric could have been better.

More useful than predicting the outcome of the second HALF of the matches is taking the Day 1 matches and seeing how they predict the Day 2 matches. This is more than half the matches, so it's bound to be a *better* predictor than half the matches because of the increased sample size too.

Originally Posted by Caleb Sykes

I'm having trouble understanding this sentence. Could you please clarify?

I believe he's talking about using an Opponent's WLT to determine how much defense (or in 2015, can starvation, noodles in landfill, etc) was encountered in the matches a team's OPR was based off of.

I don't suspect defensive ability and WLT have a very strong correlation though. I'd like to see that correlation proved before I try to "normalize" a team's OPR with this metric.

[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.