![]() |
Quick OPR Question
I'm toying around with calculating OPR, but I'm running into something of a road block. The matrix of team pairs is supposed to be diagonally dominant, and thus invertible, but I don't see how this is. If Team A played with two other teams in only one match, the diagonal element would be 1 and there would be two other 1's in Team A's row. This row alone would violate the conditions for diagonal dominance. I know I'm missing something simple, does anyone have any pointers?
|
Re: Quick OPR Question
Quote:
A is a match-team matrix where the rows of A are half-matchs, the columns of A are teams, a 1 indicates that the team represented in that column participated in the half match indicated by the row, and a 0 indicates that the team represented in that column did not participate in the half match indicated by the row. x is the column vector where the values in each row indicate a unique team's OPR, arranged in the same order as are the columns in A. b is a column vector which represents the half-match scores at the event. A is not generally square, so the idea of diagonal dominance is generally meaningless. |
Re: Quick OPR Question
Quote:
If you need more detail, this post shows a simple AWK script for creating the necessary matrix and column vectors, and a simple Octave script for doing the linear algebra. |
Re: Quick OPR Question
Quote:
But if you left-multiply each side of [A][x]≈[b] by [AT], you get [N][x]=[d], where [N] is [AT][A] and [d] is [AT][b] [N] will be an invertible square symmetric positive definite matrix, and [N][x]=[d] will have an exact solution because it's already in the Normalized Equations form. The exact solution to [N][x]=[d] will be the least-squares approximate solution to [A][x]≈[b] (to within computer floating-point rounding error). You can generate [N] (and [d]) directly from the raw score data, but it's more straightforward to generate the binary matrix [A] in sparse form. |
Re: Quick OPR Question
Sorry if I was unclear, the matrix I am using is the square matrix from performing the lease squares estimate of the solution. To use your variables, I am solving A'Ax=A'b, and having trouble with A'A being diagonally dominant.
|
Re: Quick OPR Question
Quote:
|
Re: Quick OPR Question
Are you pulling the list of teams at the event for the event from a separate request (i.e. not deriving it from from parsed match data)? If so, you may have to go through your list of teams and eliminate no-shows, because they will appear on the TBA (assuming you are using TBA data) teams list, but not in any matches, causing the row/column for that no-show team in the original match matrix to be all zeroes, making Ax = b underdetermined and thereby unsolvable. This would also lead to your problem of A'A being a singular matrix, and therefore not strictly diagonally dominant.
|
Re: Quick OPR Question
Here's a link to the raw data (each row is an alliance) and matrix. I'm not worried about the score vector, that is very straightforward. Team data comes from a master spreadsheet used for scouting at the event, checked manually against TBA. I did check the sums of the rows and the values matched what I expected.
https://docs.google.com/a/doubletiss...it?usp=sharing Thanks for the help! |
Re: Quick OPR Question
Quote:
Your "Teams" tab has data for only 44 alliances, which would generate 44 linear equations. But you have 64 teams. So you have more unknowns (Team OPRs) than equations. So the linear system is underdetermined, and has no unique solution. There are an infinite number of solutions. There are at least three ways you could deal with this. 1) Wait until you have enough data so you have an overdetermined system and there is a unique least-squares solution |
Re: Quick OPR Question
Quote:
|
Re: Quick OPR Question
@ngreen: I think you might be misunderstanding the problem at hand. Dan's computation is failing because he is trying to compute OPR with insufficient data, not because he's using the Normal Equations approach (square matrix). I suspect what he is trying to do is get "real time" OPR estimates during the early stages of an event, before enough matches have been played to create an overdetermined system suitable for least-squares estimation. |
Re: Quick OPR Question
Quote:
Real time OPR calcs, like the ones available on FRC Spyder, are not very helpful before ~5 matches are played. Even then I don't rely on them before about 8 matches. This is one of the many nice things about playing in a district system -- we get useful OPR data for our Friday evening scouting discussions. |
Re: Quick OPR Question
Quote:
Take the following alliance data that Dan posted: Code:
1700 5677 2489Code:
54 |
Re: Quick OPR Question
Ether is not referring to lack of accuracy of results when there are not enough data. He is saying there has to be a minimum number of matches before you can even get an answer.
|
Re: Quick OPR Question
Thanks for all the replies. Adding more data did the trick. To clarify, my mistake was assuming that the converse of "a diagonally dominant matrix is invertible" was true.
|
Re: Quick OPR Question
Quote:
|
Re: Quick OPR Question
Quote:
The work Eugene Fang did was great in showing how long it takes to converge. |
Re: Quick OPR Question
Quote:
|
Re: Quick OPR Question
Quote:
|
Re: Quick OPR Question
Quote:
I haven't done any numerical experiments yet to confirm this, but if there is no prior OPR value for a given team at an event, I think you can just pick a reasonable number to seed the calculation, and let the 2x iteration take care of things from there. |
Re: Quick OPR Question
5 Attachment(s)
Here is the basis/motivation for the ixOPR algorithm. Note how many matches must be played before the OPR stabilizes. |
Re: Quick OPR Question
Quote:
Quote:
In the graphs, I used 0 as the initialization, which I knew was a bad idea at the time. I've been trying out using the average match score for the event (up to the currently played match) as the initialization for teams without past events with better* results. * There's a lot of "fuzzy math" going on here and I know OPR is a pretty poor metric for estimating a team's performance, whether there are few matches played or many matches played. I'm just curious to see how accurate one can expect match predictions to be using no other source of scouting data. |
| All times are GMT -5. The time now is 16:10. |
Powered by vBulletin® Version 3.6.4
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Copyright © Chief Delphi