New algorithm creates 3D images from 2D 100,000 times more accurately
Tue 18 Aug 2015
“In some ways optimization is the most important problem you’ve never heard of because it turns up in all areas of science, engineering and business.”
So says senior author Pedro Domingos, professor of computer science and engineering at the University of Washington.
In July, a paper co-authored by Domingos and Washington University Ph.D. student Abram Friesen shared the top prize at the biggest AI conference in the world, the 24th International Joint Conference on Artificial Intelligence, for its radical new approach to the field of optimisation, with methods described which significantly – and in some areas vastly – outperform rival approaches.
Optimisation is a mathematical way to find the optimal solution for particular variables, given certain parameters. People design an algorithm for a computer to use in order to optimise the required variables, and depending on the desired context, this can be applied to a great number of different things.
Domingos notes “But a lot of optimization problems are extremely difficult to solve because they have a huge number of variables that interact in intricate ways.”
In order to deal with this, Friesen and Domingos applied decomposition techniques (from artificial intelligence and puzzle solving) to continuous optimisation problems that are more commonly found in the areas of engineering, physics, and applied mathematics.
According to the paper [PDF] itself, “We first define local structure and then present our algorithm, RDIS, which (asymptotically) finds the local optimum of a nonconvex function (R)ecursively (D)ecomposing the function into locally (I)ndependent (S)ubspaces.”
On average, RDIS was between 100,000 and 10 billion times more accurate than the other methods
The RDIS algorithm takes an extremely complex problem and simplifies it into smaller, easier-to-solve pieces. While this approach is already common when the choices are in the form of ‘yes or no’, this is the first time it’s been applied to numeric variables.
By identifying the right variables, and then setting them to specific values, the algorithm can break the problem down into almost-independent sub-problems, which are treated as fully independent in order to reduce error.
RDIS was tested against current leading methods of optimisation. In the area of predicting the way in which a protein will fold, RDIS did significantly better, especially for large proteins. For the medical profession, the ability to predict this accurately can substantially speed up the development of new treatments.
In the realm of taking two-dimensional images (from the ‘eyes’ of a robot) and reconstructing them into three-dimensional ones (which is very important for, say, a robot performing surgery safely, or, as lead author Abram Friesen points out, a self-driving car knowing what to avoid in order not to crash), the new algorithm was phenomenally more successful. On average, RDIS was between 100,000 and 10 billion times* more accurate than the other methods.
So this means that RDIS is between 5 and 10 orders of magnitude more accurate than other methods at reconstructing 2D images into 3D. That’s astounding.
Domingos went on to highlight the significance of this research, by pointing out that compared to previous methods, which were very different, “This approach…does something magical, which is solve some problems exponentially faster. And anytime you can do that, that’s when you get a big win”.
Next, the researchers plan to apply the algorithm to other contexts, and see how it does. Domingos said, “This can be applied to pretty much any machine learning problem, but that’s not to say it’s going to be good for every machine learning problem,” adding, “That’s what we have to work on and find out.”
In the meantime, however, having made terrific progress at optimising methods of optimisation, Friesen and Domingos can count themselves as the best of the best.
* We can probably assume that this is a reference to an American billion, which is a thousand million, or 1,000,000,000; as opposed an English billion, which is a million million, or 1,000,000,000,000
