Imperial mathematician sheds new light on 50 year old algorithm

An Imperial mathematician has found a new way of formulating a 50 year old algorithm, used when describing the world using mathematical models.

It is anticipated that the proposed technique, published this week in the  Proceedings of the National Academy of Sciences (PNAS), will pave the way for greatly accelerating the calculations involved when making predictions about the behaviour of complex systems in many different areas of science and engineering.

The method is being put into action in a project analysing engineering data from the Victoria and Albert Museum in London, where a new extension is being built.

“Often, scientists are interested in things they can’t measure directly, either because it is too expensive or even because it is physically impossible to do so,” explained Ben Calderhead, from the Department of Mathematics at Imperial College London. “For example, we can’t measure every biological process simultaneously occurring in the human body, nor can we directly measure many of the physical properties of very distant objects in the universe.  However, given a smaller collection of related measurements and a mathematical model, scientists can make predictions about these unobserved components via a process called Bayesian statistical inference.”

He added: “Rather than coming up with a single mathematical description of some observed natural phenomenon, scientists can consider the collection of plausible descriptions that are consistent with the measurements.  Each of these descriptions can be assigned a probability and, as more observations are made, these probabilities can be updated, reflecting our increasing confidence in our description, until we converge on a more and more accurate understanding of the phenomenon we are investigating.”

Currently, many scientists calculate these answers using an approach called Metropolis-Hastings, a 50 year-old method which is considered one of the top 10 most important algorithms of the 20^th century.

Until now, the calculations involved in the Metropolis-Hastings algorithm had to be made sequentially, which could often take a very long time: days or even weeks.  In contrast, the new approach allows multiple elements of the sequence to be calculated at the same time - in parallel - then glued together afterwards in a clever way that still produces the correct answer.   The resulting algorithm can be implemented on high performance supercomputers, delivering answers in just a few hours for many very complex models.

The method is already being put into action in a number of diverse scientific projects, from reverse engineering how the visual system of a fly works, to analysing engineering data from the Victoria and Albert Museum in London, where a new extension is being built.  The Imperial researchers are working on mathematical models based on their measurements to make predictions about the structure of the soil strata underground – information which is of vital importance in civil engineering when laying foundations for new buildings or digging tunnels for new tube lines.

Dr Calderhead added: “As we develop more and more complex mathematical models to describe natural phenomena, the calculations involved in the MH algorithm are taking longer and longer. By ‘parallelising’ that algorithm – working out parts of the answers simultaneously and then piecing the sequence back together – we have provided a much-needed tool that can be used in many areas of scientific research.”