Inferring typing behaviour: I

Topic purpose

This section will cover probabilistic inference. Rather than learning a single set of parameters by optimisation, we can model probability distributions over possible models that might be compatible with our data. We'll use Monte Carlo sampling to make it simple and easy (if not very efficient) to work with probabilistic models. We will use these approaches to model typing behaviour at the keystroke level, and both make predictions given some data ("how likely is it that this sequence was typed by user X?") and quantify how much confidence we have in those models.

Outline

In the next two hours, we will:

[Part I]

• Discuss keystroke modelling
• Look at graphical models of expressions
• Get to grips with the basics of Bayesian probabilistic inference
• Have a quick introduction to probabilistic programming with PyMC

• **Practical**: build a simple Bayesian probabilistic model to model keystroke timings and use MCMC to fit it.

[Part II]

• Discuss issues in MCMC sampling.
• Look at simple Markov language models.
• Discuss imputation of missing data.

• **Challenge**: build a fully probabilistic model that can predict the *distribution* over the likely next time of a key event.

---

Keystroke modelling

Specifically, we'll look at inter-key timing data, that you have all been collecting from your notebooks today. This dataset is very simple. It captures a sequence of key events and their timing.

This is enough to answer some interesting questions; for example, can we detect which user is typing based on the distribution of inter-key times? Or more precisely, can we infer a probability distribution over users that might be generating a timing sequence and update that as we see more keystrokes?

Alternatively, we could see if the type of key hit (e.g. space versus letter, or left side versus right side) influences the timing of the next keystroke, and build a predictive model to infer the likely next time to key impact.

If we are very ambitiuous, we could try and recover the keystrokes themselves from timing alone. There probably isn't enough information to do this, at least without very large user-specific datasets and a robust language model, but we could probably identify unusual keys (e.g. identify space or enter "punctuation" in the timing stream).

The "key" message here is that we are going to build probabilistic models -- we will maintain uncertainty over future possibilities.

This is probabilistic programming.

---

Graphical models

Transformations of expressions to graphs is familiar to most computer scientists -- it is an essential part of most optimising compilers. For example, the equation of a straight line might be written as a graph (this is how a compiler would break down the expression):

Adding unknowns

If we have multiple dependent random variables whose distribution we want to infer, we can draw a graph of dependencies to form a graphical model. This explictly models dependencies between random variables (i.e. ones we don't know the value of precisely) and inference can be performed on the entire graph.

In CS terms, we are writing expressions down without fixing the variables, and then allowing the distribution of the values to be inferred when we observe data. This inference process narrows down the likely range a random variable could take on (hopefully!).

In a probabilistic graphical model, some nodes in the graph are observed -- that is we know their state because we have explicity measured it, and others are unobserved -- we know (or have guessed) the form of their distribution but not the parameters of that distribution. Some dependencies are deterministic (i.e. fully defined by the values of their parents), while others are stochastic. We can infer the posterior distribution of unobserved nodes by integrating over the possible values that could have occured given the observed values.

We can modify our straight line equation to write a model for linear regression:

All we need to do is specify that we expected the output $y$ to be normally distributed around the equation of a line given by $m$ and $c$; we can now infer $\sigma, m, c$ from observed data. Or we can fix any of them, and infer the remainder (if, e.g. we knew in advance that $c=0$). Our assumption here is that we will observe data which has a latent structure modelled by a linear dependence on a variable $x$, plus some normally-distributed observation noise.

Note that we must put some prior distribution on every stochastic node.

Probabilistic approaches

Random variables

A random variable is a variable that can (at some point in the future) take on different values; i.e. one that is "unassigned". Proability theory allows us to manipulate random variables without having to assign them a specific value.

Distributions

A probability distribution defines how likely different states of a random variable are. The probability distribution of a random variable $x$ is written: $$P(x)$$ Random variables can be continuous (e.g. the height of a person) or discrete (the value showing on the face of a dice). The distribution of a discrete variable is described with a probability mass function (PMF) which gives each outcome a specific value. A continuous variable has a probability density function (PDF) which specifies the spread of the probability as a continuous function.

A probability distribution must assign probabilities in the range 0 (impossible) to 1 (definite) and the PMF or PDF must integrate to exactly 1 as the random variable under consideration must take on some value.

Joint, marginal, conditional

The joint probability of two random variables is written $$P(x,y)$$ and gives the probability that $x$ and $y$ take the same value simultaneously.

The marginal probability is the derivation of $P(x)$ from $P(x,y)$ by integrating (summing) over all the possible choices of $y$: $$P(x) = \int P(x,y) dy$$

Two random variables are independent if the they do not have any dependence on each other. If this is the case then the joint distribution is just the product of the individual distributions: $P(x,y) = P(x)P(y)$

The conditional probability of $x$ given $y$ is written as $$P(x|y)$$ and can be computed as $$P(x|y) = \frac{P(x,y)}{P(x)}.$$ This tells us how likely $x$ is to occur if we already know (or fix) the value of $y$.

Probability theory and Bayesian inference

Probability as a calculus of belief

Bayesians treat probability as a calculus of belief; in this model of thought, probabilities are measures of degrees of belief. $P(X)=0$ means a belief that $X$ cannot be true and $P(X)=1$ is a belief that $X$ is certainly 1.

Probability as the optimal way of representing uncertainty

Other representations of uncertainty are strictly inferior to probabilistic methods in the sense that a person, agent, computer placing "bets" on future events using probabilistic models has the best possible "return" out of all decision systems when there is uncertainty.

Bayesians allow for belief in states to be combined and manipulated via the rules of probability. The key process in Bayesian logic is updating of beliefs. Given some prior belief (it's Glasgow, it's not likely to be sunny) and some new evidence (there seems to be a bright reflection inside) we can update our belief to calculate the posterior -- our new probability that it is sunny outside. Bayesian inference requires that we accept priors over events, i.e. that we must explicitly quantify our assumptions with probability distributions.

Prior, likelihood, posterior

We often want to know the probability of a model (and its parameters) given some data $p(H, \theta|D)$. But we can only compute the likelihood of the data being generated by the model. Bayes' rule gives a consistent model for inverting the probability distribution: $$ p(A|B) = \frac{p(B|A) P(A)}{P(B)} $$

$P(A|B)$ is called the posterior, $P(B|A)$ is called the likelihood, $P(A)$ is the prior and $P(B)$ is the evidence. Bayes' rule gives a consistent rule to take some prior belief and combine it with observed data to estimate a new distribution which combines them.

Integration over the evidence

We can say that the posterior probability is proportional to the product of the prior and the likelihood. But to evaluate its value, we need to compute $P(B)$, the evidence. This is tricky, but because probabilities must add up to 1, we can write $P(B)$ as: $$ P(B) = \sum_{i} P(B|A_i) P(A_i) $$ for a set of discrete possibilities $A_i$ or $$ P(B) = \int_{A} P(B|A) P(A) dA $$ for a continuous distribution over $A$.

This trick is essential in understanding Bayesian inference!

In general this is difficult to compute. For binary simple cases where there are only two possible outcomes ($A$ can only be true or false), Bayes' rule can be written as:

$$P(A|B) = \frac{P(B|A)P(A)}{P(B|A)P(A) + P(B|\bar A) P(\bar A)}, $$

where $\bar A$ means "when A is false". In words:

The probability that it is sunny given I can see a bright reflection is equal to:
    The probability that I would see a bright reflection if it *were* sunny times the probability that it might be sunny 
    over
    The probability that I would see a bright reflection if it *were* sunny times the probability that it might be sunny plus the probability that I would see a bright reflection if it were *not* sunny times the probability it might not be sunny.

Sampling

We can draw samples from a distribution, which gives us a set of definite (non-random) variables which are distributed according to the PDF or PMF. The mean $\mu$ of a set of samples from a distribution is an estimate of the expectation, which improves as the number of samples $N$ increases.

We can write this as: $$ \frac{1}{N} \sum_{i=0}^{N} x_i \approx \int p(x) dx,$$ where $x_i$ are random samples from $p(x)$.

Furthermore, if we want to apply any function $f(x)$ to the distribution (e.g. to answer question like 'what is the expected value of a normal distribution whose "output" is squared'), we can estimate of $E[f(x)]$ very simply: $$ \frac{1}{N} \sum_{i=0}^{N} f(x_i) \approx \int f(x) p(x) dx,$$.

Monte Carlo inference

We often cannot compute the integral to normalise the probability distribution. One common way to get round this is to use Monte Carlo sampling, where we approximate the integration over all the parameters by summing over random samples drawn from the distribution of parameters. There are many techinques to do this efficiently, as the naive sampling methods become very inefficient in high dimensional spaces (i.e. $N$ must be very large to reliably sample the space).

This allows us to solve the tricky denominator in Bayes Rule:

$$ p(A|B) = \frac{p(B|A) P(A)}{P(B)} $$$$ = \frac{p(B|A) P(A)}{\int_{A} P(B|A) P(A) dA} $$

$$ \approx \frac{p(B|A) P(A)}{\frac{1}{N} \sum_{i=0}^{N} P(B|x) P(x)} $$

Since we can usually sample from $P(A)$ easily, this becomes very straightforward to compute (as long as we can sample from P(B|A), but there are tricks to do this even if it has an unpleasant form).

One of these techniques is Markov chain Monte Carlo (MCMC) constructs random walks which "wander" about in probablity distributions in a way that makes samples drawn from them represent the true distribution correctly.

---

---

Let's do it: PyMC

We'll use the excellent PyMC module to do the inference. If you have questions about this module, you can read this tutorial or the API docs. There's a new and even nicer version with very powerful capabilities currently called PyMC3, but the dependencies are "hard" to install at the moment.

Let's implement the linear regression model in the intro in practice, using PyMC to build a graphical model and then run MCMC to sample from the posterior (i.e. estimate the distribution of random variables after seeing some evidence).

A simple mixture model

We can include both discrete and continuous variables. A very important case is where we have a mixture model. That is, we believe our observations come from one of a number of distributions. For example, in modelling human heights, we might expect height to be normally distributed, but to have two different distributions for men and women.

It is very straightforward to add this to a PyMC graphical model; it is just another random variable to infer.

Practical: Modelling typing with a MCMC model

You'll build a simple model which assumes inter-key timings are Gamma distributed, with distribution parameters that are different for each person.

Steps

You will need to construct the PyMC model specification, then run the MCMC sampler. The structure should be a mixture model, like the one above. But the inter-key timings should be a Gamma rather than normal (Gaussian). Note that this is a mixture model, but unlike the above example, the mixture component is an observed variable (you know the user id)

Load the data from keylogs.csv. This has four columns:

    user_id  delta_t  duration_t  keycode

user_id is a unique integer per-user. Time (delta_t) is in milliseconds since the previous keydown event. duration_t is the duration the key was held down, in milliseconds. keycode is the keycode (result of e.which in Javascript) of the keypress.

Link to Inferring Typing Behaviour: Part II