Scientists crack code to solve the Curse of Dimensionality
Published 12/10/2016 | 10:16
It is a problem so fiendishly difficult that academics feared it was impossible to solve - and even gave it a name that sounds like a rejected Indiana Jones movie script.
But a team of University of Cambridge researchers believe they have devised a method to crack the Curse of Dimensionality, paving the way for predictions on meaningful issues such as the chances of life elsewhere in the universe.
The Curse refers to the apparent impossibility of tackling mathematical problems in "high-dimensional space" - when there are so many variables and possible outcomes that they seem to be beyond the limits of human calculation.
A simple example is this: Imagine that you have a cup containing 100 grains of rice.
You pick it up, shake it, and put it down again.
The arrangement within the cup changes, but what are the chances of that arrangement occurring, relative to all other possibilities?
While most people would reasonably consider that problem not just impossible, but largely pointless, it illustrates the type of maths needed to make predictions about much bigger - and more meaningful - issues.
These include the impact of deforestation, how power grids respond to demand, the probability of our own existence on earth and the chance life may occur elsewhere in the universe.
The new study was led by Stefano Martiniani, of St John's College, Cambridge, who carried out the work with colleagues in the Department of Chemistry and at Microsoft Research in Cambridge.
"There is a very large class of problems that can be solved through the sort of approach that we have devised," Mr Martiniani said. "It opens up a whole world of possibilities in the study of things like dynamical systems, chemical structure prediction, or artificial neural networks."
In maths, dimensions refer to parameters, and the challenge is viewed as an "energy landscape".
Researchers built computer software to model the high-dimensional systems and make calculations within them.
The simplest model is a brute force approach, which essentially takes a reading, shakes the system up, takes another reading, and repeats the process - many millions of times - in an attempt to establish the probability of certain outcomes.
"In most cases you are like a blindfolded person, walking around drunk in the energy landscape," Mr Martiniani said. "At any given moment, you only really know where you are and where you have just come from."
In the new study, however, the team developed a method which seeks out the furthest and least likely limits instead of averages from random samples.
Testing showed they were able to sample and quantify outcomes that would only be found randomly once in a googol - which in decimal notation is written as the digit 1 followed by a hundred noughts.
"In basic terms it goes where brute force sampling never will, because if you started to try, you would never finish," Mr Martiniani added.
"Technically, the limits of the problems we can solve are now not those of the approach, but the computing power we need to simulate the underlying energy landscape.
"When addressing these kinds of problems in high-dimensional space, this should now be the technique of choice."