4
$\begingroup$

I am not sure if this is the correct place to ask this kind of question, I hope it is. I am studying this paper on an improvement of Elo rating system called Elo++. On page 4 the author states that he want minimize a function called total loss that is

$$L=\sum_{i,j\in T}w_{i j}\left( \hat o_{i j}-o_{i j}\right)^2+\lambda\sum_{i\in D}\left(r_i-a_i\right)^2$$

where $r_i$ is the rank of the player that as to be estimated, $ \hat o_{i j}$ is the outcome of a game where player $r_i$ plays against player $r_j$, $a_i$ is the arithmetic average of the set $D$ of the player $r_j$ (the players $r_j$ which have played against $r_i$), $o_{i j}$ is the predicted outcome that is a function of $r_i, r_j$.

The problem for me comes at page 5 where the author says that in order to minimize the total loss, he had used a stochastic gradient descent. The updating formula in the stochastic gradient descent is

$$ r_i \leftarrow r_i-\eta\left(w_{i j}\left(\hat o_{i j}-o_{i j}\right)\hat o_{i j}\left(1-\hat o_{i j}\right)+\frac{\lambda}{N_i} \left(r_i-a_i\right)\right) $$

How is this updating formula is related to the problem of minimizing the first condition?

$\endgroup$
2
  • $\begingroup$ Are you asking why that formula comes from the gradient of the loss function $L$? The coordinates of the gradient when you just consider the $j$th opponents are proportional to $\bigg( \cdots \bigg)$ because of the formula for $o_{ij}$ and the chain rule. $\endgroup$ Sep 2 '12 at 9:06
  • $\begingroup$ If you put this comment in a form of answer i will give you a +1 :) $\endgroup$
    – emanuele
    Sep 2 '12 at 9:54
6
$\begingroup$

There is some disagreement between your notation and the notation in the paper. You disagree on whether $\hat o$ or $o$ is the predicted outcome or the observed outcome. I'll use the paper's notation.

In one step of the stochastic gradient descent, you compute a noisy estimate of the gradient of the loss function as the gradient of the loss attributed to one example,

$$L = w_{ij} (\hat o_{ij} - o_{ij})^2 + \frac \lambda N_i (r_i - a_i)^2. $$

We want the partial derivative of this with respect to $r_i.$ By the chain rule,

$$\frac {\partial L}{\partial r_i} = 2 w_{ij}(\hat o_{ij} - o_{ij})( \frac{\partial}{\partial r_i} \hat o_{ij}) + 2 \frac \lambda N_i (r_i - a_i).$$

Here $\hat o_{ij}$ is a logistic function $\hat o_{ij} = P(-r_j+r_i+\gamma) = 1/(1 + \exp(r_j - r_i- \gamma))$. The logistic function $P(x)$ has the property that $P'(x) = P(x)(1-P(x)),$ which is easily checked by the chain rule. So,

$$ \frac {\partial}{\partial r_i} \hat o_{ij} = \hat o_{ij}(1- \hat o_{ij})$$

$$\frac {\partial L}{\partial r_i} = 2 w_{ij}(\hat o_{ij} - o_{ij})( \hat o_{ij}(1- \hat o_{ij})) + 2 \frac \lambda N_i (r_i - a_i).$$

The factor of $2$ is absorbed into $\eta$ to give the update rule for $r_i$. For $r_j$, there is an extra factor of $-1$ from the chain rule applied to $P(-r_j+r_i+\gamma),$ so

$$ \frac {\partial}{\partial r_j} \hat o_{ij} = -\hat o_{ij}(1- \hat o_{ij}).$$

$\endgroup$

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.