search

Yelp / MOE

A global, black box optimization engine for real world metric optimization.
Other
1.31k stars 139 forks source link

literature recommendations #420

Closed rmcgibbo closed 9 years ago

rmcgibbo commented 9 years ago

quick question / suggestion for the docs: could you recommend any papers that describe the constant liar and kriging believer heuristics for the q,p-EI problem? From what I can find, discussion in the docs is not really aimed at Ph.D. students, and the docstrings are kind of like alice in wonderland :)

suntzu86 commented 9 years ago

The docs point to ginsbourger 2008: https://hal.archives-ouvertes.fr/hal-00260579/PDF/qEI_Ginsbourger_leriche_carraro_0303_2008.pdf

@sc932 can correct me, but I think constant liar was actually proposed in that paper. At least I can't find any further references. It's just a really basic heuristic where you can dial up/down how conservative the algorithm will be.

Kriging believer isn't discussed in much detail in there, but "kriging" just refers to gaussian process regression. So kriging believer = just trust the GP. Wiki is a good place to start: http://en.wikipedia.org/wiki/Kriging I'm sure there are more papers out there on kriging for optimization (generally) or for EI optimization. We've found that kriging is a fairly hard heuristic to work with b/c the GP "collapses" after very few points (i.e., variance goes to 0 everywhere).

sc932 commented 9 years ago

@suntzu86 provides some good starting points. Google scholar can help you follow the path that most interests you from there. Let me know if you think the docs should be more verbose in this area. We are in the process of writing up some papers around this which will be helpful moving forward as well.

@peter-i-frazier, want to jump in here?

rmcgibbo commented 9 years ago

Thanks. I know the GPEI problem generally and kriging, but the q,p-EI problem (and ensuing heuristics) was new to me. Thanks for the links. I'm looking forward to reading the papers that you guys are working on.

Generally, are your best results with constant_liar?

sc932 commented 9 years ago

constant liar seems to be better than krigging (in our real-world tests), but EPI seems to be doing the best. There is some work on that in my thesis, and some papers coming out soon.

http://link.springer.com/chapter/10.1007/978-3-642-44973-4_7#page-1

Is also good.

rmcgibbo commented 9 years ago

With constant_liar_min usually?

sc932 commented 9 years ago

Yeah, since we are doing minimization at the core. You could also add some noise to it depending on the situation, we have found that helpful sometimes.

rmcgibbo commented 9 years ago

Cool, thanks.

suntzu86 commented 9 years ago

A little more color on CL-min vs max. If you want to q,p-EI, the strategy you choose should be dependent on the values of q,p. We haven't investigated this super extensively and are not aware of published results. q-EI is the 'regular' problem; I think @sc932 actually proposed the q,p-EI extension. But if you understand q-EI then q,p is nearby.

But basically, solving q-EI or q,p-EI with CL-min can be ill conditioned when q+p is "large". You tell the GP that a bunch of points are really really awesome. The chance of other regions winning is small so EI optimization will return tightly clustered points = singular covariance matrix.

CL-max doesn't have this issue. But on the flip side, you're just telling the GP that every point sucks so it will explore a ton.

So none of these heuristics are amazing (kriging has the variance->0 issue), but at the moment they're all we've tried when we want to avoid the cost of MC integration.