andyljones
commented
3 years ago In case it helps, the following is my brief markdown-latex notes on the maths involved in the VB derivation. Install this Chrome extension to get it to render.
Each agent $i$ has a 'skill' $s_i \sim N(\mu_0, \sigma0)$. In a matchup with another agent $j$, the probability of $i$ winning depends on the logit'd difference in skills: $$ p{ij} = \frac{1}{1 + e^{-(s_i - sj)}} $$ and the number of wins in $n{ij}$ games between $i$ and $j$ is drawn from the binomial distribution $$ w{ij} \sim \text{Binom}(n{ij}, p{ij}). $$ Some bits of the above equations are going to turn up a lot in what follows, so let's shorten $p{ij}$'s definition into $p{ij} = \phi(d{ij})$, where $d_{ij} = s_i - s_j$.
Now I want to apply variational Bayes here, with a full-rank normal approximation $q(s) = N(s|\mu, \Sigma)$. Of the many approaches to variational Bayes, our specific approach is going to be gradient ascent on the evidence lower bound. That means repeatedly evaluating
$$ \nabla \text{ELBO} = \nabla (\mathbb{E}_q[\ln p(w, s)] + H[q]) $$
Of the two terms on the RHS there, $H[q]$ - the entropy of the normal distribution - is pretty easy! So let's have a look at the hard term, and let's look at the thing we're taking the expectation of there: $$ \ln p(w, s) = \left[ \sum w{ij} \ln p{ij} + (n{ij} - w{ij}) \ln (1 - p_{ij}) \right] - \left[ \frac{1}{2\sigma_0^2}\sum_i(s_i - \mu_0)^2 \right] + C $$ First term comes out of the binomial distribution; second term comes from the normal prior; and the $C$ captures some independent-of-$s$ terms we don't care about.
How's this change under the expectation? Let's go one term at a time. First up is
$$Eq \ln p{kj} = E [ \ln \phi(s_k - s_j) | N(s|\mu, \Sigma) ]$$
This looks like a misery to evaluate, and it is. But one fortunate thing is that we're only depending on $\mu, \Sigma$ constrained to $j, k$. More, the tricky bit - $\ln \phi(s_k - s_j)$ - depends only on $d = \frac{1}{2}(s_k - s_j)$. It's independent of the orthogonal direction $m = \frac{1}{2}(s_k + s_j)$! So we can change variables from integrating over $s_k, s_j$ to integrating over $d, m$, then integrate over $m$ on the inside. This leaves us with $$ Eq \ln p{kj} = E[ \ln \phi(d) | N(d|R\mu, R\Sigma R^T) ] $$ where $R = [+\frac{1}{2}, -\frac{1}{2}]$ changes the vars from $(s_j, s_k)$ to $(d, m)$ and simultaneously marginalizes out/drops $m$.
By marginalizing out $m$, we're left with only the integral over $d$. And that only depends on two parameters $\mu_d, \sigma^2_d$, so we can pre-emptively cache the integral's value for the full range of likely values! Then evaluating the expectation becomes a simple interpolation between the cached values.
lezcano
This issue was shifted over from the private activelo repo; no point in keeping it separate now boardlaw's public
Hey Mario! I've carved out the active-ELO-learning chunk of my project into this repo. There's a lot about it I'm not happy with, but the bit relevant to geotorch is in a fairly good state.
For end-users (ie, me) the package is meant to be used as per
examples.suggestions.simulate: the user repeatedly plays some games among the agents, uses theactivelo.Solverto fit a distribution to the posterior, then hasactivelo.suggesttake that posterior and use it to suggest which matchup to play next.For geotorch purposes, the whole suggestion thing is irrelevant except maybe as way to generate test data. The bit relevant to geotorch is the solver, in
activelo.solvers. It has some light tests at the bottom of the file, and some examples inexamples.solvers.There're two solver examples included in the repo, as listed in
examples.solvers.saved_examples(). First is an organic example, collected while working on my main AZ project. Second is an artificial one that seems to reliably misbehave, either due to negdef covariance or by a line-search failure. The misbehaving example is a lot bigger than the ones I'm running into day-to-day, so I'm not too pressed to fix them up yet.If you'd like more examples, try running
examples.suggestions.simulate_log_ranksand then taking a slice of the trace.Eyeballing the imports, what's required to get this working should be
I'd also recommend
pip install aljpy, just sos you can usealjpy.extract().Some bits of the repo also make fair use of dotdicts/arrdicts, which are a very-much-idiosyncratic datatype I'm extremely fond of for research work.
I've basically thrown this together in an afternoon. I'm happy to clean it up and answer questions if you find anything confusing or hard to follow :)
Finally, as I mentioned in the email: if you look through this and think 'lol never mind', there'll be no hard feelings!