Slashdot Mirror

← Back to Stories (view on slashdot.org)

'Shrinking Bull's-eye' Algorithm Speeds Up Complex Modeling From Days To Hours (mit.edu)

Posted by Soulskill on from the meteorologists-can-now-be-more-precisely-wrong dept.

rtoz sends word of the discovery of a new algorithm that dramatically reduces the computation time for complex processes. Scientists from MIT say it conceptually resembles a shrinking bull's eye, incrementally narrowing down on its target. "With this method, the researchers were able to arrive at the same answer as a classic computational approaches, but 200 times faster." Their full academic paper is available at the arXiv. "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 — 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."

48 comments

  1. This sounds familiar... by __aaclcg7560 · · Score: 0

    Scientists from MIT say it conceptually resembles a shrinking bull's eye, incrementally narrowing down on its target.

    Zeno's Dichotomy Paradox

    https://en.wikipedia.org/wiki/Zeno's_paradoxes#Dichotomy_paradox

    1. Re:This sounds familiar... by geantvert · · Score: 3, Informative

      Not really, Zeno's paradox is about an infinite sum giving a finite result.

      The technique in the article look more like a typical monte-carlo method (that is generating a lot of random values to find a result) combined with some localized search around local maximums. As such that does not seem to be a new idea. I haven't read the whole paper yet but the innovation seems to be in the fact that they managed to apply this idea to a new class of problems.

    2. Re: This sounds familiar... by Anonymous Coward · · Score: 0

      Bingo. Simulated annealing does the same. Since 20 years.

    3. Re: This sounds familiar... by Anonymous Coward · · Score: 0

      >75 years I am sure you meant to say.

    4. Re: This sounds familiar... by Anonymous Coward · · Score: 0

      Nothing new, a similar thing called the unscented transform in filtering

    5. Re: This sounds familiar... by Hussman32 · · Score: 1

      How is this faster than a gradient method? Or does this replace a simplex method?

      --
      "Who are you?" "No one of consequence." "I must know." "Get used to disappointment."
  2. Estimation of distribution algorithm by goombah99 · · Score: 2

    Uh isn't this a toy version of the entire field Estimation of Distribution Algorithms for parameter optimization??? Anyone want to point out what is new here since the MIT article sure didn't point it out.

    --
    Some drink at the fountain of knowledge. Others just gargle.
    1. Re:Estimation of distribution algorithm by Anonymous Coward · · Score: 5, Informative

      Indeed, it looks much like this. I happend to have a dozen EDA papers from the past couple decades open on my desktop at this moment! The foremost of the three hard problems in estimation of distribution is how one describes a probability distribution over high dimensional space in a compact low dimensional way. An efficient, if naive, way to do this is just fit the distribution to a function like a Gaussian and then just change the axes and width of the gaussian to evolve it. one then can easily sample and update this gaussian process to narrow down on the parameter guesses. This may be what they "bullseye" approach is doing from the description. Another more general approach I just happened to be re-reading today is the Probability collective which sort of divides the high dimensional space into a low dimensional product distribution. This can handle non-unimodal surfaces and by adapting the basis for the product space coordiantes adapt itself to the local topology. there's a lot of papers on this including this one: http://www.worldscientific.com... (perhaps not the best starting place but I had the link handy!).

      The other two hard problems are how one optimally re-uses old data which was taken in what is now the low probality region. one has to down weight it wrt to fresher samples but how is unclear. Finally there's the annealing schedule which reflects the trade between exploration of the surface versus exploitation of the available data. anneal quickly and you converge to local minimum and miss the global minimum. Usually these are arbitrary. But Probability collectives has some clever techniques to make those decisions more principled. In general setting the annealing rate by cross validation is good way to decide if you should anneal faster or slower.

    2. Re:Estimation of distribution algorithm by notea42 · · Score: 2

      Yep - it looks like they rediscovered known methods for optimization using a series of cheap approximations of the black-box. You find the optimal solution of the approximation and use that to choose one or more points to evaluate on the original black-box. Then you update your approximation with the results and repeat. I was doing this in college back in 1999. I wrote to generate pseudo-random functions to test on, and we used the same class of functions as approximations for the harder, more expensive problem.

    3. Re:Estimation of distribution algorithm by notea42 · · Score: 2

      Found the other relevant paper - "Model-assisted pattern search methods for optimizing expensive computer simulations" by Seifert, Torczon, and Trosset at The College of William and Mary in VA

    4. Re:Estimation of distribution algorithm by turning+in+circles · · Score: 1

      So, it's the computerized version of the back of the envelope method for zeroing in on a correct answer?

      --
      Might as well face it I'm addicted to data.
    5. Re:Estimation of distribution algorithm by plopez · · Score: 1

      I'm curious about the claim "any complex model". Really? ANY complex model?[1] Is this the silver bullet? The Holy Grail? After testing it on two "complex" (definition please) models?

      So yeah, I was curious and it looks like they are doing sparse parameter estimation of sorts. I wonder how they deal with non-uniqueness and convergence on local maxima.

      What is just as import is knowing parameter sensitivity. If a parameter does not add much to the accuracy of the model, throw it out. This has it's own pitfalls and is why modeling is a black art.

      I'll have to dig deeper into it but this is my first impression.

      [1] I had a Prof. with a PhD from MIT. It was his favorite phrase "we can model any situation using equation ". Of course this was after making assumptions which resulted in the problem becoming linear with deterministic behavior and a unique solution. I wasn't impressed.

      --
      putting the 'B' in LGBTQ+
    6. Re:Estimation of distribution algorithm by Anonymous Coward · · Score: 0

      Of course this was after making assumptions which resulted in the problem becoming linear with deterministic behavior and a unique solution.

      If you can solve the problem for a spherical cow in a vacuum, you're practically done.

    7. Re:Estimation of distribution algorithm by Anonymous Coward · · Score: 0

      Hmmm, while reading your post I kept thinking about 'The Black Swan'. You don't take away the number you first thought of at any point do you?

  3. Re:THE QUANTUM COMPUTER HAS ARRIVED!! by Anonymous Coward · · Score: 0

    Maybe if you attended your CS lectures instead of getting drunk you'd realize how ridiculous you sound.

  4. Somewhat hyped by GlobalEcho · · Score: 4, Informative

    It looks to me that the new algorithm offers no real speed advantage over gaussian process optimization. Rather, by making similar local approximations it gains some convergence proofs. Those are nice and all, but not often relevant to real-world applications.

    1. Re:Somewhat hyped by xiox · · Score: 1

      How is this relevant? The algorithm is for speeding up Markov Chain Monte Carlo (MCMC) analyses, which are very commonly used in science to examine posterior probability distributions for a particular model. I run MCMC codes most weeks and they're becoming increasingly more common in my field of science. Being able to speed up the analysis by a large factor to avoid model likelihood evaluations would be very valuable.

    2. Re:Somewhat hyped by GlobalEcho · · Score: 1

      How is this relevant? The algorithm is for speeding up Markov Chain Monte Carlo (MCMC) analyses

      The paper is phrasing it in terms of MCMC but it's more generally applicable if you think of it as an optimizer.

    3. Re:Somewhat hyped by DavidHumus · · Score: 1

      It's hard to say without doing all the implementation work, but the paper does say that the algo is "...general enough to describe both local polynomial and Gaussian process approximations..." and there is a section called "Local Gaussian process surrogates". So, they do in fact incorporate this in the larger framework of their algo.

      In fact, they claim "...that the accuracy is nearly identical for all the cases, but the approximate chains use fewer evaluations of the true model, reducing costs by more than an order of magnitude for quadratic or Gaussian process approximations (Figure 10b)."

    4. Re:Somewhat hyped by GlobalEcho · · Score: 1

      It's hard to say without doing all the implementation work, but the paper does say that the algo is "...general enough to describe both local polynomial and Gaussian process approximations..." and there is a section called "Local Gaussian process surrogates". So, they do in fact incorporate this in the larger framework of their algo.

      In fact, they claim "...that the accuracy is nearly identical for all the cases, but the approximate chains use fewer evaluations of the true model, reducing costs by more than an order of magnitude for quadratic or Gaussian process approximations (Figure 10b)."

      Indeed, though that quote is simply pointing out that the relative performance of their algorithm is at its best with its mode set to local Gaussian approximations.

    5. Re:Somewhat hyped by plopez · · Score: 1

      Parameter estimation.

      --
      putting the 'B' in LGBTQ+
  5. Looks familiar ... by leftover · · Score: 2

    Is this not hill-climbing on an assumed-flat-ish response surface? There is history and a whole forest of approaches using approximation when the "cost" function is expensive to evaluate. Solving a honking big set of PDEs certainly qualifies for that.

    A big part of the history is work to predict whether the degree of assumed flatness is not in conflict with reality. That in itself can become computationally expensive.

    Fun stuff though!

    --
    Bent, folded, spindled, and mutilated.
  6. IANACS by Anonymous Coward · · Score: 2, Interesting

    So I'm a lay-idiot, but whats to stop this getting stuck on a local maxima / minima for a given parameter if it's not doing a comprehensive evaluation?

    1. Re: IANACS by Anonymous Coward · · Score: 1

      Probably some amount of random retries...

  7. 8K per eye VR goggles by Anonymous Coward · · Score: 0, Funny

    Will this enable me to have 8K per eye VR goggles? I need an 8K Oculus Rift asap.

  8. Great, they learn to approximate by Anonymous Coward · · Score: 0

    Hype but no meat.

    This is a standard approximation routine. Been using for years, even when taken the SAT,

  9. SP500 Trading System by Anonymous Coward · · Score: 0

    So can I use this to optimize a simple moving average window period to come up with a positive expectancy (ie profitable) trading system for the SP500?

    1. Re: SP500 Trading System by Anonymous Coward · · Score: 0

      In alchemy, whatever floats boats is ok.

      Just have the time time machine ready to extract yourself from the black swan event.

    2. Re: SP500 Trading System by Anonymous Coward · · Score: 0

      No, you are a dumbass, but someone else could do that, not using this though

  10. This is about Sampling from a distribution... by Anonymous Coward · · Score: 0

    It's not just about finding the peak of some hyper-surface, but rather sampling from a distribution defined by that hypersurface, while using local approximations WITHOUT altering the distribution from which you're sampling.

  11. Huh by ThatsNotPudding · · Score: 2

    It looks to me that the new algorithm offers no real speed advantage over gaussian process optimization. Rather, by making similar local approximations it gains some convergence proofs. Those are nice and all, but not often relevant to real-world applications.

    Huh. You think they would have realized that more quickly.

    1. Re:Huh by GlobalEcho · · Score: 1

      Huh. You think they would have realized that more quickly.

      I'm sure the authors are well aware of it. It's the press hype that I'm pointing out.

  12. Enigma / bomba by ai4px · · Score: 2

    Isn't this shrinking bullseye the same strategy that was used by Turning to throw out all the impossible solutions to the enigma machine? This left the team with many fewer possible solutions to try by brute force.

  13. Obligatory "Star Trek II" Reference by Anonymous Coward · · Score: 1

    Algorithm Speeds Up Complex Modeling From Days To Hours . . .

    Kirk: Kirk to Enterprise.

    Spock: Spock here.

    Kirk: Captain Spock, damage report.

    Spock: Admiral, if we go "by the book". like Lieutenant Saavik, hours could seem like days.

    Kirk: I read you captain. Let's have it.

    Spock: The situation is grave, Admiral. We won't have main power for six "days". Auxiliary power has temporarily failed. Restoration may be possible, in two "days". By the book, Admiral.

      . . .

    Saavik: You lied!

    Spock: I exaggerated.

    Kirk: Hours instead of days! Now we have minutes instead of hours!

  14. This would help just about every couple I know by Rinikusu · · Score: 1

    "What do you want to eat?"
    "I dunno, what do you want to eat?"

    Sounds like a perfect fit!

    --
    If you were me, you'd be good lookin'. - six string samurai
  15. Shrinking Bulls-eye by Anonymous Coward · · Score: 0

    Expanding Bulls-hit.

  16. RBF by durdur · · Score: 1

    As far as I know the state of the art for nonlinear optimization when the objective is a very expensive process to run (or simulation of a process) is Radial Basis Function modeling/estimation. Much of the work on this was done at Cornell University - see for example Rommel Regis's papers. These algorithms do some random sampling, then build a model of the objective function, then based on that pick one or more new points to sample, and repeat.

    1. Re:RBF by GlobalEcho · · Score: 1

      I'm not familiar with it (and I'm a dilettante in the domain), but it sounds interesting. Can you recommend a starting point?

    2. Re:RBF by durdur · · Score: 1

      I think the original paper on this is by H. M. Gutman. For an intro to more modern methods see Regis and Shoemaker's 2007 paper.

      Juliane Mueller has some working code available.

  17. So to summarize... by Anonymous Coward · · Score: 0

    Select a model that requires multiple iterations to arrive at a final solution.

    1. Run the simulation using the full model. Accumulate knowledge.
    2. Run the simulation using approximation. Add approximation to accumulated knowledge.
    3. Lather, rinse, repeat to arrive at a final solution.
    4. Profit, because you arrive at the final result more rapidly than running the full model.

  18. Sounds like a branch and bound algorithm by Anonymous Coward · · Score: 1

    Nothing to see here