Inferring typing behaviour: II

MCMC in practice: sampling issues

The great thing about MCMC approaches is that you can basically write down your model and then run inference directly. There is no need to derive complex approximations, or to restrict ourselves to limited models for which we can compute answers analyitically.

The bad thing about MCMC approaches is that, even though it will do the "right thing" asymptotically, the choice of sampling strategy has a very large influence for the kind of sample runs that are practical to execute.

Bayesian inference should depend only on the priors and the evidence observed; but MCMC approaches also depend on the sampling strategy used to approximate the posterior.

MCMC allows us to use distributions we can't even sample from directly. First we couldn't calculate the evidence P(B), so we integrated; but we couldn't solve the integral, so we sampled; but then we couldn't sample from the distribution so we used MCMC. It's a very general approach!

Rejection sampling

The simplest way to perform Monte Carlo sampling for a distribution we can't sample directly is to do rejection sampling. We have a distribution we want to sample given by a pdf $p(x)$, and instead sample from an easy distribution $q(x)$, (usually uniform, i.e. a box) where $q(x)>p(x) \forall x$. Then, we draw a new sample $x_q$ from $q(x)$ (horizontal sample) and then sample uniformly from $x_s = [0,x_q]$ (vertical sample) and see if $x_s<f(x_q)$. If we so we keep it as a draw from the distribution, otherwise we reject it.

This is easy to implement, but works very poorly in high dimensions because the rejection rate increases exponentially with increasing dimension.

Metropolis-Hastings

Metropolis-Hastings (or just plain Metropolis) takes a different approach, and is able to work in high-dimensional spaces. Metropolis also uses an auxiliary distribution $q(x)$, but it uses this to wander around in the distribution space, accepting jumps to new positions based on both $q(x)$ and $p(x)$. This random walk (a Markov chain, because we make a random jump conditioned only on where we currently are) is a the "Markov Chain" bit of "Markov Chain Monte Carlo".

We just take our current position $x$, and propose a new position $x^\prime = x + x_q$, where $x_q$ is a random sample drawn from $q(x)$. This makes local steps in the space of the probability density. If $q(x)$ has a simple, symmetric form (e.g. is Gaussian), there is a very simple formula to decide whether to accept or reject a step from $p(x)$ to a new candidate position $p(x^\prime)$: $$ p(\text{accept}) = \begin{cases} p(x^\prime)/p(x), & p(x)>=p(x^\prime) \\ 1, & p(x)<p(x^\prime) \end{cases} $$

The asymmetric case is only slightly more involved, but it is very unusual to need to use it.

Others

There are many other MCMC samplers, such as:

• Gibbs samplers, which are very efficient when we can sample from the marginal distribution (i.e. from one dimension of a distribution at a time), but not from the joint directly.
• Hamiltonian samplers, which extend Metropolis-like steps with "virtual physics" which pushes the samples in sensible directions (i.e. not down the gradient of the function!)
• Slice samplers, which are very clever and efficient, but only work for 1-dimensional (univariate) distributions.

Burn-in and thinning

MCMC tries to draw independent, unbiased samples from the posterior, but the sampling process (like Metropolis), is not inherently unbiased. For example, successive samples in a random walk are correlated and obviously not independent.

And although the Markov Chain approach (under fairly relaxed assumptions) will asympotically sample from all of the posterior, if the random walk starts off very far from the bulk of the distribution, it will "wander in the wilderness" for some time before reaching significant probability density. This means early samples from the distribution might be unreasonably dense in very low probability regions in the posterior. How "good" the Markov chain is at sampling from the posterior is called mixing; some MCMC setups may mix very badly until they get warmed up.

To mitigate these two common issues, there are a couple of standard tricks:

• Burn-in, which ignores the first $n$ samples from an MCMC draw, to make sure the chain is mixing well. Typically, several thousand samples might be ignored.
• Thinnning, which takes one sample from every $k$ consecutive samples from the chain, to reduce correlation. Values of raound 5-50 are common.

Tuning these is a matter of art!

If you're interested in learning more about MCMC, David Mackay's book chapter is a good reference.

Language modelling

In the keystroke event datasets, we are predicting a sequence of discrete symbols, which has very regular and repetitive structure. Capturing the regularities in symbol sequences is language modelling. In traditional text entry, a language model captures natural language to improve typing performance. We'll look at using a language model to predict keystroke data for the coding and navigating tasks that we have captured, using standard language modelling approaches.

Bigram model

We can build a very simple probabilistic language model using n-grams, where we predict the next occurence of a symbol given some previous sequence of $n$ symbols. This is a Markov assumption; that the current state depends only on the previous state (a fixed sequence of $n$ previous symbols can be bundled into a single previous state for the sake of argument).

A very basic model is a character-level bigram model, where we model the probability of a character $c_n$ given a previously seen character $c_{n-1}$, $p(c_n|c_{n-1})$.

The probability distribution can be inferred from data simply by counting the occurence of each pair $(c_{n-1}, c_{n})$ and storing the result in a matrix which has dimensions $d \times d$ where $d$ is the number of distinct characters. If we then normalise by dividing each row by the total count of that character, we approximate the probability distribution of the language.

Log probabilities

The probability of multiple independent random variables taking on a set of values can be computed from the product: $$p(x,y,z) = p(x)p(y)p(z)$$ and in general $$p(x_1, \dots, x_n) = \prod_{i=1}^{n} x_i$$

We often have to have to compute such products, but to multiply lots of values $<1$ leads to numerical issues. Instead, we often prefer to manipluate log probabilities, which can be summed instead of multiplied: $$\log p(x_1, \dots, x_n) = \sum_{i=1}^{n} \log p(x_i)$$

This is simply a numerical conveience.

Imputation

In PyMC, variables can be observed (fixed) or unobserved (random). PyMC cycles through the array of known values for the observed variables and updates the rest of the graph.

But what if you want to ask "what if?"-style question? For example, if you knew the last two key codes and timings, what is the distribution over the possible times for the next key?

PyMC implements this using imputation, where certain missing values in an observed variable can be inferred (imputed) from the rest of the model. Masked arrays are used to implement imputation; these allow arrays to have "blank" values, that PyMC can fill in automatically.

This approach creates one new random variable per missing data item; this can create very large models if you are not careful!

Note that, while it makes sense to be able to infer $x$ given $y$, as well as the $y$ given $x$ we just did, PyMC cannot automatically infer variables in this manner. It can only infer the "forward" path in the graph. In theory, if all the determinstic functions (like the line function) were invertible, then this reverse inference could be performed automatically without changing the model.

Challenge

Task: Build a better model of typing behaviour, and then test if you can predict inter-key times using imputation.

Extend the MCMC model to include key type information (for example, space+enter, punctiuation, numbers, letters). You choose the categories and write code to classify the keystrokes. There is a list of keycodes here. Only choose at most three or four categories of keystroke, or your model will never converge in a reasonable time.

Build a PyMC model that models the time to the next keystroke, dependent on:

• The previous keystroke code category and the current keystroke code category
• The previous keystroke press duration and the current keystroke press duration
• The time between the previous keystroke and this one
• The user ID

This model will be something like:

if you just pressed a whitespace key and then you pressed a directional key, and you are user 202, and you held the last key for 104ms, then the next key will happen in x milliseconds.

Use all of the keystroke data you have. Select the last three elements of the keylog, and try imputing the inter-key time.

Plot a graph showing the predictive posterior against the true values.

Tips

• Start off with a very simple model, and add variables one at a time. You might start with just a model depending on the user ID, and work from there, or start with the duration of the current keycode only, and work from there.
• You might want to condense the key code categories and the user id into a single categorical variable to make the model easier to write down.
• If you find you're not getting a good model, try limiting to a single user to begin with, and then expand to multiple users
• For discrete variables (e.g. keycode category, user_id) use observed Categorical variables
• For the timings, try using a Gamma distribution; you could also use a log-normal distribution, but you will have to implement the log transform yourself (not hard, but may require some online research [i.e. check StackOverflow!])