Go to Post Defense is a good thing! - Kevin Sheridan [more]
Home
Go Back   Chief Delphi > Competition > Rules/Strategy > Scouting
CD-Media   CD-Spy  
portal register members calendar search Today's Posts Mark Forums Read FAQ rules

 
Reply
Thread Tools Rate Thread Display Modes
  #1   Spotlight this post!  
Unread 10-04-2016, 20:18
JewishDan18's Avatar
JewishDan18 JewishDan18 is offline
Registered User
FRC #1700
Team Role: Engineer
 
Join Date: Feb 2009
Rookie Year: 2007
Location: Sunnyvale, CA
Posts: 185
JewishDan18 is a splendid one to beholdJewishDan18 is a splendid one to beholdJewishDan18 is a splendid one to beholdJewishDan18 is a splendid one to beholdJewishDan18 is a splendid one to beholdJewishDan18 is a splendid one to behold
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?
Reply With Quote
  #2   Spotlight this post!  
Unread 10-04-2016, 20:41
Caleb Sykes's Avatar
Caleb Sykes Caleb Sykes is offline
Registered User
FRC #4536 (MinuteBots)
Team Role: Mentor
 
Join Date: Feb 2011
Rookie Year: 2009
Location: St. Paul, Minnesota
Posts: 1,059
Caleb Sykes has a reputation beyond reputeCaleb Sykes has a reputation beyond reputeCaleb Sykes has a reputation beyond reputeCaleb Sykes has a reputation beyond reputeCaleb Sykes has a reputation beyond reputeCaleb Sykes has a reputation beyond reputeCaleb Sykes has a reputation beyond reputeCaleb Sykes has a reputation beyond reputeCaleb Sykes has a reputation beyond reputeCaleb Sykes has a reputation beyond reputeCaleb Sykes has a reputation beyond repute
Re: Quick OPR Question

Quote:
Originally Posted by JewishDan18 View Post
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?
For the OPR equation Ax ~= b where:
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.

Last edited by Caleb Sykes : 10-04-2016 at 21:34. Reason: team's, not teams'
Reply With Quote
  #3   Spotlight this post!  
Unread 10-04-2016, 21:02
Ether's Avatar
Ether Ether is offline
systems engineer (retired)
no team
 
Join Date: Nov 2009
Rookie Year: 1969
Location: US
Posts: 8,094
Ether has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond repute
Re: Quick OPR Question

Quote:
Originally Posted by JewishDan18 View Post
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?
Caleb explained it very clearly in the previous post.

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.


Reply With Quote
  #4   Spotlight this post!  
Unread 10-04-2016, 21:26
Ether's Avatar
Ether Ether is offline
systems engineer (retired)
no team
 
Join Date: Nov 2009
Rookie Year: 1969
Location: US
Posts: 8,094
Ether has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond repute
Re: Quick OPR Question

Quote:
Originally Posted by Ether View Post
Caleb explained it very clearly in the previous post.

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.
Also note the following: in Caleb's discussion, [A] is a non-square binary matrix (each element is either 1 or 0) with 2M rows and T columns, where M is the number of matches and T is the number of teams... and [b] is a 2M by 1 column vector of alliance scores. So [A][x]≈[b] is indeed an overdetermined system which has no exact solution.

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.


Reply With Quote
  #5   Spotlight this post!  
Unread 10-04-2016, 21:30
JewishDan18's Avatar
JewishDan18 JewishDan18 is offline
Registered User
FRC #1700
Team Role: Engineer
 
Join Date: Feb 2009
Rookie Year: 2007
Location: Sunnyvale, CA
Posts: 185
JewishDan18 is a splendid one to beholdJewishDan18 is a splendid one to beholdJewishDan18 is a splendid one to beholdJewishDan18 is a splendid one to beholdJewishDan18 is a splendid one to beholdJewishDan18 is a splendid one to behold
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.
Reply With Quote
  #6   Spotlight this post!  
Unread 10-04-2016, 21:32
Ether's Avatar
Ether Ether is offline
systems engineer (retired)
no team
 
Join Date: Nov 2009
Rookie Year: 1969
Location: US
Posts: 8,094
Ether has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond repute
Re: Quick OPR Question

Quote:
Originally Posted by JewishDan18 View Post
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.
Post your raw data and I will post an OPR solution with all the intermediate matrices and column vectors so you can locate where the error is.


Reply With Quote
  #7   Spotlight this post!  
Unread 10-04-2016, 22:49
wjordan wjordan is offline
FRC Stathead
AKA: Wes Jordan
FRC #2363 (Triple Helix)
Team Role: College Student
 
Join Date: Apr 2015
Rookie Year: 2013
Location: Blacksburg, VA
Posts: 40
wjordan is a jewel in the roughwjordan is a jewel in the roughwjordan is a jewel in the roughwjordan is a jewel in the rough
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.
__________________


2016: Northern Virginia Winners (1418, 2421), Hampton Roads Finalists (1885, 5954)
2015: Virginia Winners (384, 1610), Chesapeake Winners (1690, 4050)
2014: Chesapeake Winners (1629, 623), Galileo Winners (67, 973, 2481)
2013: Virginia Finalists (2053, 3015)

Last edited by wjordan : 10-04-2016 at 22:53.
Reply With Quote
  #8   Spotlight this post!  
Unread 11-04-2016, 00:36
JewishDan18's Avatar
JewishDan18 JewishDan18 is offline
Registered User
FRC #1700
Team Role: Engineer
 
Join Date: Feb 2009
Rookie Year: 2007
Location: Sunnyvale, CA
Posts: 185
JewishDan18 is a splendid one to beholdJewishDan18 is a splendid one to beholdJewishDan18 is a splendid one to beholdJewishDan18 is a splendid one to beholdJewishDan18 is a splendid one to beholdJewishDan18 is a splendid one to behold
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!
Reply With Quote
  #9   Spotlight this post!  
Unread 11-04-2016, 10:45
Ether's Avatar
Ether Ether is offline
systems engineer (retired)
no team
 
Join Date: Nov 2009
Rookie Year: 1969
Location: US
Posts: 8,094
Ether has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond repute
Re: Quick OPR Question

Quote:
Originally Posted by JewishDan18 View Post
Here's a link to the raw data (each row is an alliance)
OK:

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

2) Solve the system using the Moore-Penrose pseudo-inverse: x=pinv(A)*b. This will select the solution x which has minimum ||x||

3) Just compute each team's average (instead of OPR) until you have enough data: if a team played on L alliances, sum those alliance scores and divide the sum by 3L.

Reply With Quote
  #10   Spotlight this post!  
Unread 11-04-2016, 11:16
Caleb Sykes's Avatar
Caleb Sykes Caleb Sykes is offline
Registered User
FRC #4536 (MinuteBots)
Team Role: Mentor
 
Join Date: Feb 2011
Rookie Year: 2009
Location: St. Paul, Minnesota
Posts: 1,059
Caleb Sykes has a reputation beyond reputeCaleb Sykes has a reputation beyond reputeCaleb Sykes has a reputation beyond reputeCaleb Sykes has a reputation beyond reputeCaleb Sykes has a reputation beyond reputeCaleb Sykes has a reputation beyond reputeCaleb Sykes has a reputation beyond reputeCaleb Sykes has a reputation beyond reputeCaleb Sykes has a reputation beyond reputeCaleb Sykes has a reputation beyond reputeCaleb Sykes has a reputation beyond repute
Re: Quick OPR Question

Quote:
Originally Posted by Ether View Post
There are at least three ways you could deal with this.
Another (very impractical) way to deal with this could be to selectively remove matches from the data set until an overdetermined system is created. This could potentially find OPRs for a subset of teams. This is wholly impractical for official FRC events since the scheduler highly prioritizes unique partners, so I doubt a combination of n matches could be found which would also remove >n teams.

Last edited by Caleb Sykes : 11-04-2016 at 11:32. Reason: remove, not removes
Reply With Quote
  #11   Spotlight this post!  
Unread 11-04-2016, 17:34
Ether's Avatar
Ether Ether is offline
systems engineer (retired)
no team
 
Join Date: Nov 2009
Rookie Year: 1969
Location: US
Posts: 8,094
Ether has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond repute
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.




Last edited by Ether : 11-04-2016 at 17:36.
Reply With Quote
  #12   Spotlight this post!  
Unread 11-04-2016, 19:27
Richard Wallace's Avatar
Richard Wallace Richard Wallace is offline
I live for the details.
FRC #3620 (Average Joes)
Team Role: Engineer
 
Join Date: Jan 2003
Rookie Year: 1996
Location: Southwestern Michigan
Posts: 3,658
Richard Wallace has a reputation beyond reputeRichard Wallace has a reputation beyond reputeRichard Wallace has a reputation beyond reputeRichard Wallace has a reputation beyond reputeRichard Wallace has a reputation beyond reputeRichard Wallace has a reputation beyond reputeRichard Wallace has a reputation beyond reputeRichard Wallace has a reputation beyond reputeRichard Wallace has a reputation beyond reputeRichard Wallace has a reputation beyond reputeRichard Wallace has a reputation beyond repute
Re: Quick OPR Question

Quote:
Originally Posted by Ether View Post
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.
I think you are right.

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.
__________________
Richard Wallace

Mentor since 2011 for FRC 3620 Average Joes (St. Joseph, Michigan)
Mentor 2002-10 for FRC 931 Perpetual Chaos (St. Louis, Missouri)
since 2003

I believe in intuition and inspiration. Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution. It is, strictly speaking, a real factor in scientific research.
(Cosmic Religion : With Other Opinions and Aphorisms (1931) by Albert Einstein, p. 97)
Reply With Quote
  #13   Spotlight this post!  
Unread 11-04-2016, 20:43
Ether's Avatar
Ether Ether is offline
systems engineer (retired)
no team
 
Join Date: Nov 2009
Rookie Year: 1969
Location: US
Posts: 8,094
Ether has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond repute
Re: Quick OPR Question

Quote:
Originally Posted by ngreen View Post
I'm not confused by his issue, but since he was using a spreadsheet and seeming to do something similar to me I thought I'd share what worked okay for me.
I don't see how what worked OK for you is related to the problem Dan posted.

Take the following alliance data that Dan posted:
Code:
1700 5677 2489
1868 256 4171
254 852 4990
2035 6036 2643
841 846 5027
114 5026 6039
1678 5940 2473
100 5171 581
3303 5089 1351
5700 1967 1280
3482 6059 5655
670 253 199
8 5924 4643
192 2854 5905
668 4186 4765
5728 5104 2813
368 4904 2367
1662 2135 972
604 5737 766
649 4255 4159
971 1868 115
751 5700 3256
852 5924 6039
581 5655 5089
2473 6036 3303
4186 5905 841
100 2854 846
1967 972 6059
649 2643 5728
1678 8 2813
1700 1662 5104
254 971 4255
256 4643 766
668 5026 253
192 199 2367
5940 604 3256
115 4171 5027
4765 4904 3482
114 1280 5171
751 2489 4990
368 670 2035
1351 5737 5677
6039 4159 2643
2135 4186 5924
... plus this example alliance score vector:
Code:
54
59
115
45
89
49
111
47
78
45
67
79
121
57
119
52
93
87
63
40
80
87
115
34
41
94
31
102
40
78
55
98
120
106
102
121
123
68
120
108
62
49
130
46
... and try to run your OPR computation on that data.


Reply With Quote
  #14   Spotlight this post!  
Unread 11-04-2016, 21:17
Ed Law's Avatar
Ed Law Ed Law is offline
Registered User
no team (formerly with 2834)
 
Join Date: Apr 2008
Rookie Year: 2009
Location: Foster City, CA, USA
Posts: 752
Ed Law has a reputation beyond reputeEd Law has a reputation beyond reputeEd Law has a reputation beyond reputeEd Law has a reputation beyond reputeEd Law has a reputation beyond reputeEd Law has a reputation beyond reputeEd Law has a reputation beyond reputeEd Law has a reputation beyond reputeEd Law has a reputation beyond reputeEd Law has a reputation beyond reputeEd Law has a reputation beyond repute
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.
__________________
Please don't call me Mr. Ed, I am not a talking horse.
Reply With Quote
  #15   Spotlight this post!  
Unread 13-04-2016, 21:43
JewishDan18's Avatar
JewishDan18 JewishDan18 is offline
Registered User
FRC #1700
Team Role: Engineer
 
Join Date: Feb 2009
Rookie Year: 2007
Location: Sunnyvale, CA
Posts: 185
JewishDan18 is a splendid one to beholdJewishDan18 is a splendid one to beholdJewishDan18 is a splendid one to beholdJewishDan18 is a splendid one to beholdJewishDan18 is a splendid one to beholdJewishDan18 is a splendid one to behold
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.
Reply With Quote
Reply


Thread Tools
Display Modes Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is Off
HTML code is Off
Forum Jump


All times are GMT -5. The time now is 16:10.

The Chief Delphi Forums are sponsored by Innovation First International, Inc.


Powered by vBulletin® Version 3.6.4
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Copyright © Chief Delphi