1
$\begingroup$

I'm new to ML, linear algebra, statistics, etc. so bear with me on the terminology...

I’m looking to find a vector that produces the maximum correlation for the relationship between 1) all relationships among dimensions of the vector (determined by subtraction) and 2) some output value produced by said relationships. I'm specifically using this to create a sports ranking system that takes a number of matches and the resulting scores and attempts to assign a value to the teams that can be used to predict future scores. In other words, the difference between any two team's ratings should be predictive of the score differential for the next match between the two.

So for example, if I have 3 teams, A, B, and C, each start with unknown ratings:

$$ \begin{array}{c|c} A&?\\ B&?\\ C&?\\ \end{array} $$

If each team played each other team once, the left table would be used to calculate their rating differences (column team's rating minus row team's rating). The right table would be the difference in scores in the respective matchups.

$$ \begin{equation} \begin{array}{c|c} &A&B&C \\ \hline A&*& B - A& C - A\\ B&A - B& *& C - B\\ C&A - C& B - C& *\\ \end{array} \Rightarrow \begin{array}{c|c} &A&B&C \\ \hline A&0&3&6\\ B&-3&0&3\\ C&-6&-3&0\\ \end{array} \end{equation} $$

Here is a possible solution that, for this example, would result in a perfect correlation between team rating differentials and score differentials.

$$ \begin{array}{c|c} A&1\\ B&2\\ C&3\\ \end{array} $$

This would be the regression line where x2 is the column team's rating and x1 is the row team's rating.

$$y = 3 * (x_2 - x_1)$$

It’s worth noting that what matters is the relationship between the various values (not their nominal values) since this would be another possible solution:

$$ \begin{array}{c|c} A&2\\ B&4\\ C&6\\ \end{array} $$

Which would result in a linear equation that looks like this, which would also have a correlation of 1:

$$y = {3\over 2} * (x_2 - x_1)$$

What I want to do is find a method to determine values for A, B, and C that maximizes the correlation between the pairwise differences and resulting output values. The one additional catch for the teams example is that not every team will play every other team so any resulting matrices will be asymmetrical (assuming that matters).

Are there any existing techniques to address this problem?

$\endgroup$
1
$\begingroup$

This is one approach you can follow:

  • Setup a linear regression system, with each match as a row, and each feature corresponding to a team.
  • The unknown feature coefficient for each team is the team 'strength' that we try to determine.
  • The feature values will be one of 0, 1, or -1, depending on whether the team did not play, was the column team, or the row team respectively in that match.
  • The regression target will be the score differential (column team score - row team score) in that match.

Eg: For the result matrix above, the system would be:

$$ (-1) * x_1 + (1) * x_2 + (0) * x_3 = 3\\ (-1) * x_1 + (0) * x_2 + (1) * x_3 = 6\\ (0) * x_1 + (0-1) * x_2 + (1) * x_3 = 3 $$

  • One solution to the above system is: $x_1=-6; x_2=-3; x_3=0$
  • Multiple solutions are possible, which can be viewed as translations of each other (adding a constant to all team strengths).
  • If there are 'n' teams, then there are only 'n-1' linearly independent columns in the regression. (In R, one of the coefficients comes out as NA. This can be treated as 0, or dropped from the regression, effectively making it 0).
$\endgroup$
  • $\begingroup$ I realized that I could do gradient descent where MSE would be the sum of (m(T2 - T1) + b - Actual)^2 for all matchups, which I think is just an algebraic representation of what you’re saying? Are you saying there’s a more straightforward approach other than gradient descent? $\endgroup$ – SuperCodeBrah Mar 28 at 13:58
  • 1
    $\begingroup$ What is 'm' in your comment? If predicted score = x_1 - x_2, and we want to minimize MSE between actual and prediction, then (in addition to gradient descent) there is an analytical solution as well: towardsdatascience.com/… $\endgroup$ – raghu Mar 28 at 14:12
  • $\begingroup$ Yes, predicted score is a function of the m coefficient multiplied by the difference in two team coefficients, y = m(x_1 - x_2) + b. Ultimately I'm trying to optimize m to to minimize MSE for this function. I noticed that the solution you linked requires matrix inversion - will that be an issue for a matrix of roughly size [6000, 350]? Are there any solutions that are definitely stable for this type of problem? $\endgroup$ – SuperCodeBrah Mar 29 at 0:41
  • 1
    $\begingroup$ A test using some randomly generated data (6000 matches among 350 teams) ran fine on my laptop. You can go through the link below, that compares various solution methods for linear regression (including gradient descent and matrix inversion): stats.stackexchange.com/questions/160179/… $\endgroup$ – raghu Mar 29 at 14:10
  • $\begingroup$ This was very helpful, thank you. I was previously able to get it to work with gradient descent but I found an SVD method here: machinelearningmastery.com/…. I've barely delved into linear algebra and don't really know python so it was a bit of a process, but it resulted in a better overall fit and is faster than the gradient descent method. I definitely have a lot to learn but am excited by the power of these techniques. Thank you. $\endgroup$ – SuperCodeBrah Mar 29 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.