{"id":6715,"date":"2015-11-18T05:46:39","date_gmt":"2015-11-18T05:46:39","guid":{"rendered":"http:\/\/revoscience.com\/en\/?p=6715"},"modified":"2015-11-18T05:46:39","modified_gmt":"2015-11-18T05:46:39","slug":"shrinking-bulls-eye-algorithm-speeds-up-complex-modeling-from-days-to-hours","status":"publish","type":"post","link":"https:\/\/www.revoscience.com\/en\/shrinking-bulls-eye-algorithm-speeds-up-complex-modeling-from-days-to-hours\/","title":{"rendered":"\u201cShrinking bull\u2019s-eye\u201d algorithm speeds up complex modeling from days to hours"},"content":{"rendered":"

Algorithm may be applied to a broad range of complicated problems.<\/strong><\/em><\/span><\/p>\n

\"Stills<\/a>
Stills from the Weather Research and Forecasting Model.
Image: Wikipedia\/Almoz<\/figcaption><\/figure>\n

CAMBRIDGE, Mass.<\/strong> —\u00a0To work with computational models is to work in a world of unknowns: Models that simulate complex physical processes \u2014 from Earth\u2019s changing climate to the performance of hypersonic combustion engines \u2014 are staggeringly complex, sometimes incorporating hundreds of parameters, each of which describes a piece of the larger process.<\/span><\/p>\n

Parameters are often question marks within their models, their contributions to the whole largely unknown. To estimate the value of each unknown parameter requires plugging in hundreds, if not thousands, of values, and running the model each time to narrow in on an accurate value \u2014 a computation that can take days, and sometimes weeks.<\/span><\/p>\n

[pullquote]The algorithm can be applied to any complex model to quickly determine the probability distribution, or the most likely values, for an unknown parameter.[\/pullquote]<\/p>\n

Now MIT researchers have developed a new algorithm that vastly reduces the computation of virtually any computational model. The algorithm may be thought of as a shrinking bull\u2019s-eye that, over several runs of a model, and in combination with some relevant data points, incrementally narrows in on its target: a probability distribution of values for each unknown parameter.<\/span><\/p>\n

With this method, the researchers were able to arrive at the same answer as a classic computational approaches, but 200 times faster.<\/span><\/p>\n

Youssef Marzouk, an associate professor of aeronautics and astronautics, says the algorithm is versatile enough to apply to a wide range of computationally intensive problems.<\/span><\/p>\n

\u201cWe\u2019re somewhat flexible about the particular application,\u201d Marzouk says. \u201cThese models exist in a vast array of fields, from engineering and geophysics to subsurface modeling, very often with unknown parameters. We want to treat the model as a black box and say, \u2018Can we accelerate this process in some way?\u2019 That\u2019s what our algorithm does.\u201d<\/span><\/p>\n

Marzouk and his colleagues \u2014 recent PhD graduate Patrick Conrad, Natesh Pillai from Harvard University, and Aaron Smith from the University of Ottawa \u2014 have published their findings this week in the\u00a0Journal of the American Statistical Association.<\/em><\/span><\/p>\n

Modeling \u201cMonopoly\u201d<\/strong><\/span><\/p>\n

In working with complicated models involving multiple unknown parameters, computer scientists typically employ a technique called Markov chain Monte Carlo (MCMC) analysis \u2014 a statistical sampling method that is often explained in the context of the board game \u201cMonopoly.\u201d<\/span><\/p>\n

To plan out a monopoly, you want to know which properties players land on most often \u2014 essentially, an unknown parameter. Each space on the board has a probability of being landed on, determined by the rules of the game, the positions of each player, and the roll of two dice. To determine the probability distribution on the board \u2014 the range of chances each space has of being landed on \u2014 you could roll the die hundreds of times.<\/span><\/p>\n

If you roll the die enough times, you can get a pretty good idea of where players will most likely land. This, essentially, is how an MCMC analysis works: by running a model over and over, with different inputs, to determine a probability distribution for one unknown parameter. For more complicated models involving multiple unknowns, the same method could take days to weeks to compute an answer.<\/span><\/p>\n

Shrinking bull\u2019s-eye<\/strong><\/span><\/p>\n

With their new algorithm, Marzouk and his colleagues aim to significantly speed up the conventional sampling process.<\/span><\/p>\n

\u201cWhat our algorithm does is short-circuits this model and puts in an approximate model,\u201d Marzouk explains. \u201cIt may be orders of magnitude cheaper to evaluate.\u201d<\/span><\/p>\n

The algorithm can be applied to any complex model to quickly determine the probability distribution, or the most likely values, for an unknown parameter. Like the MCMC analysis, the algorithm runs a given model with various inputs \u2014 though sparingly, as this process can be quite time-consuming. To speed the process up, the algorithm also uses relevant data to help narrow in on approximate values for unknown parameters.<\/span><\/p>\n

In the context of \u201cMonopoly,\u201d imagine that the board is essentially a three-dimensional terrain, with each space represented as a peak or valley. The higher a space\u2019s peak, the higher the probability that space is a popular landing spot. To figure out the exact contours of the board \u2014 the probability distribution \u2014 the algorithm rolls the die at each turn and alternates between using the computationally expensive model and the approximation. With each roll of the die, the algorithm refers back to the relevant data and any previous evaluations of the model that have been collected.<\/span><\/p>\n

At the beginning of the analysis, the algorithm essentially draws large, vague bull\u2019s-eyes over the board\u2019s entire terrain. After successive runs with either the model or the data, the algorithm\u2019s bull\u2019s-eyes progressively shrink, zeroing in on the peaks in the terrain \u2014 the spaces, or values, that are most likely to represent the unknown parameter.<\/span><\/p>\n

\u201cOutside the normal\u201d<\/strong><\/span><\/p>\n

The group tested the algorithm on two relatively complex models, each with a handful of unknown parameters. On average, the algorithm arrived at the same answer as each model, but 200 times faster.<\/span><\/p>\n

\u201cWhat this means in the long run is, things that you thought were not tractable can now become doable,\u201d Marzouk says. \u201cFor an intractable problem, if you had two months and a huge computer, you could get some answer, but you would not necessarily know how accurate it was. Now for the first time, we can say that if you run our algorithm, you can guarantee that you\u2019ll find the right answer, and you might be able to do it in a day. Previously that guarantee was absent.\u201d<\/span><\/p>\n

Marzouk and his colleagues have applied the algorithm to a complex model for simulating movement of sea ice in Antarctica, involving 24 unknown parameters, and found that the algorithm is 60 times faster arriving at an estimate than current methods. He plans to test the algorithm next on models of combustion systems for supersonic jets.<\/span><\/p>\n

\u201cThis is a super-expensive model for a very futuristic technology,\u201d Marzouk says. \u201cThere might be hundreds of unknown parameters, because you\u2019re operating outside the normal regime. That\u2019s exciting to us.\u201d<\/span><\/p>\n

This research was supported, in part, by the Department of Energy.<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"

MIT researchers have developed a new algorithm that vastly reduces the computation of virtually any computational model.<\/p>\n","protected":false},"author":6,"featured_media":6716,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[17,28],"tags":[],"class_list":["post-6715","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-research","category-techbiz"],"featured_image_urls":{"full":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/11\/MIT-Modeling-Unknowns_0.jpg",448,299,false],"thumbnail":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/11\/MIT-Modeling-Unknowns_0-150x150.jpg",150,150,true],"medium":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/11\/MIT-Modeling-Unknowns_0-300x200.jpg",300,200,true],"medium_large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/11\/MIT-Modeling-Unknowns_0.jpg",448,299,false],"large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/11\/MIT-Modeling-Unknowns_0.jpg",448,299,false],"1536x1536":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/11\/MIT-Modeling-Unknowns_0.jpg",448,299,false],"2048x2048":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/11\/MIT-Modeling-Unknowns_0.jpg",448,299,false],"ultp_layout_landscape_large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/11\/MIT-Modeling-Unknowns_0.jpg",448,299,false],"ultp_layout_landscape":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/11\/MIT-Modeling-Unknowns_0.jpg",448,299,false],"ultp_layout_portrait":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/11\/MIT-Modeling-Unknowns_0.jpg",448,299,false],"ultp_layout_square":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/11\/MIT-Modeling-Unknowns_0.jpg",448,299,false],"newspaper-x-single-post":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/11\/MIT-Modeling-Unknowns_0.jpg",448,299,false],"newspaper-x-recent-post-big":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/11\/MIT-Modeling-Unknowns_0.jpg",448,299,false],"newspaper-x-recent-post-list-image":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/11\/MIT-Modeling-Unknowns_0.jpg",95,63,false],"web-stories-poster-portrait":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/11\/MIT-Modeling-Unknowns_0.jpg",448,299,false],"web-stories-publisher-logo":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/11\/MIT-Modeling-Unknowns_0.jpg",96,64,false],"web-stories-thumbnail":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/11\/MIT-Modeling-Unknowns_0.jpg",150,100,false]},"author_info":{"info":["Amrita Tuladhar"]},"category_info":"Research<\/a> Tech<\/a>","tag_info":"Tech","comment_count":"0","_links":{"self":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts\/6715","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/users\/6"}],"replies":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/comments?post=6715"}],"version-history":[{"count":0,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts\/6715\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/media\/6716"}],"wp:attachment":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/media?parent=6715"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/categories?post=6715"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/tags?post=6715"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}