0
$\begingroup$

Working through a lecture exercise on MCMC methods. I have a dataset containing the outcome of N chess games $-$ in the format Winner, Loser $-$ between M players.

When 2 players $p_1$ and $p_2$ play against one another in game $g$, the outcome is modeled as $y_g = sign(W_{p_1} - W_{p_2} + v_g)$, where:

  • $W_{p_i}$ represents the skill of player $p_i$. As a prior, all players have their skills $W_{p_i}$ ~ $N(0,1)$ (so all players are i.i.d),
  • $W_{p_1} - W_{p_2}$ is the skill difference between $p_1$ and $p_2$,
  • $v_g$ ~ $Laplace(0, \frac{1}{2})$ models the performance variance of both players jointly.

I would like to find values of $W$ that maximize the likelihood of all N games across all M players. To do so, I would like to practice implementing Metropolis-Hastings (MH) on that dataset, in Python. I understand the MH algorithm as the following (from here):

Given:

  • $f$, the PDF of the distribution to sample from,
  • $w^{0}$, initial values for $W$,
  • $w = w^{0}$,
  • The transition model, which here is given as a Gaussian distribution $w^{t+1}_{p_i}$ ~ $N(w^{t}_{p_i},\sigma_p)$, with $\sigma_p$ a hyper-parameter,

For n steps:

  • $p = f(y |W=w)P(w)$,
  • $w'$ ~ $N(w^{t}_{p_i},\sigma_p)$
  • $p' = f(y |W=w')P(w')$,
  • $ratio = \frac{p'}{p}$
  • Draw $r$ from $U(0,1)$, if $ratio > r$, set $w^{t+1}_{p_i} = w'$

Questions

  1. Is my understanding of MH correct?
  2. I have seen Python examples which implement MH for a single variable. IIUC, here, we have M variables - one skill per player. How can I implement MH for a multi-variate case? Or am I completely off?

Sorry about the long post. I'll update as needed if it isn't clear. Thanks!

Edit 1 Just clarifying that I'm interested in code examples using MH on vectors of parameters, not a single scalar.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ $W$ is a vector of dimension $M$ and $y$ of dimension $N$. This is standard Metropolis Hastings. $\endgroup$
    – Xi'an
    Commented Dec 19, 2022 at 18:26
  • 1
    $\begingroup$ MH is used to draw samples from some distribution you cannot characterize ($f$ in your notation), but you can evaluate some function proportional to said distribution. This is useful when one wants to draw samples from a posterior distribution, for example. However, there is really no scope for the MH in the maximum likelihood estimation you described. In other words, what is $f$ in your example? $\endgroup$
    – Banach
    Commented Dec 19, 2022 at 18:29
  • $\begingroup$ @Banach you are correct, $f$ in this case is the posterior ($P(W | y)$), which is intractable. The above (in my understanding) uses Bayes's theorem to use the likelihood $P(y|W)$ instead, which is tractable. $\endgroup$
    – LucDupont
    Commented Dec 19, 2022 at 20:35
  • $\begingroup$ @Xi'an Yes, I agree with you. My problem is how can I implement MH for vectors instead of scalars? The examples I've seen so far all deal with scalars. $\endgroup$
    – LucDupont
    Commented Dec 19, 2022 at 20:37
  • 1
    $\begingroup$ Here is an example: stats.stackexchange.com/q/525373/7224 And another one stats.stackexchange.com/a/441746/7224 The algorithm does not change in essence, all you need is a multivariate proposal to move the vector rather than the scalar. $\endgroup$
    – Xi'an
    Commented Dec 19, 2022 at 21:30

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.