[MRG+1] Implement greedy A-optimal acquisition function for pure exploration #432

kiudee · 2017-07-12T09:10:23Z

This acquisition function aims at reducing the overall uncertainty of our objective function approximation.
This is useful if you want to accurately gauge the effect of every hyperparameter on the objective function, typically to set proper ranges for the subsequent optimization or to remove a parameter completely.

The gaussian_a_opt function uses the standard deviation provided by the base estimator and samples those points first where it is maximal.

Suggestions for improvement are welcome.

codecov-io · 2017-07-12T09:48:14Z

Codecov Report

Merging #432 into master will increase coverage by 0.02%.
The diff coverage is 75%.

@@            Coverage Diff             @@
##           master     #432      +/-   ##
==========================================
+ Coverage   86.43%   86.46%   +0.02%     
==========================================
  Files          22       22              
  Lines        1563     1581      +18     
==========================================
+ Hits         1351     1367      +16     
- Misses        212      214       +2

Impacted Files	Coverage Δ
skopt/acquisition.py	`95.95% <75%> (-0.89%)`	⬇️
skopt/callbacks.py	`95.65% <0%> (-0.51%)`	⬇️

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update afb0e49...3824ef0. Read the comment docs.

iaroslav-ai · 2017-07-12T11:04:51Z

Looks interesting!

Could you elaborate a bit more on particular use cases for the function, eg a bit more description of practical use cases? Also could you provide some references to the literature where such thing is used? Would be good so that people can take a look at it a bit more in detail.

One idea I would have in my mind is to possibly use this instead of random initialization for the optimizers, so that initial points generated are distributed "more evenly" across search space.

kiudee · 2017-07-12T14:05:06Z

The general setting is called active learning in which you want to learn the target function with as few evaluations as possible.

"A-optimality" was established in optimal design . The goal is to specify design points in advance which reduce the average variance of the parameter estimates. See [1] for a good treatment of the different optimality criteria when applied in Bayesian optimization. This reference could also be useful if we want to implement more criteria like the mutual information.

For initialization we could calculate a fixed set of n_random_starts points to implement an optimal design.
I would advise against using the surrogate model for that purpose.
For quasi-random initialization I would recommend a sequence of points satisfying low-discrepancy (see [2] for a recent paper on quasi-monte carlo integration). This captures your intuition of "more evenly" exploring the search space.
The library Spearmint uses a Sobol sequence for initialization. I would recommend choosing a random start value of the sequence, otherwise it will always start with the exact same points.

[1] Krause, Andreas, Ajit Singh, and Carlos Guestrin. "Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies." Journal of Machine Learning Research 9.Feb (2008): 235-284.
[2] Dick, Josef, Frances Y. Kuo, and Ian H. Sloan. "High-dimensional integration: the quasi-Monte Carlo way." Acta Numerica 22 (2013): 133-288.

betatim · 2017-07-12T19:45:08Z

Naive question: how is this acquisition function different from evaluating the objective using a Sobol (or your favourite quasi random) sequence? Is it because with a Sobol sequence you explore the space "evenly" and here you pick points that have large uncertainty? Is there a simple example where the two don't lead to "the same" thing? (a heteroscedastic objective?)

MechCoder · 2017-07-12T20:36:56Z

Hmm, I think you can achieve the same by setting Kappa to a very-high value in LCB. Is it not?

kiudee · 2017-07-13T07:23:30Z

@betatim I will play around with a few GPs to come up with an example where the behavior is different. In any case the Sobol sequence is not adaptive, ie it will not change if the user provides an initial set of points for which the objective value is already known.

@MechCoder Yes, indeed I was doing exactly this as a workaround before deciding to implement the acquisition function. In my opinion it is cleaner this way, since the effect of the mean is completely removed.

MechCoder · 2017-07-15T01:21:48Z

In that case, I would prefer having a special value for Kappa that will set exploitation to zero (and will have no controversy in getting merged) instead of having yet another acquisition function.

kiudee · 2017-07-15T07:11:34Z

Ok, that sounds like a good compromise. I can make the change next week since I'm going on vacation today.

…

On Sat, 15 Jul 2017, 03:21 MechCoder, ***@***.***> wrote: In that case, I would prefer having a special value for Kappa that will set exploitation to zero (and will have no controversy in getting merged) instead of having yet another acquisition function. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#432 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAic-cowSLCuHnAGWiiDJeMrf__pxlbtks5sOBQsgaJpZM4OVVss> .

kiudee · 2017-07-19T09:23:00Z

I made the change, by letting the user provide a special string 'Aopt' as the parameter kappa in LCB.

Somehow Github did not like that I rebased the commits and force-pushed. Any ideas on how to fix the pull request without recreating it?
edit: It appears simply reopening it fixed the history, but we need to rerun the tests.

glouppe · 2017-07-21T04:04:11Z

Looks good to me. +1 for merge

MechCoder · 2017-07-22T04:34:58Z

skopt/acquisition.py

        Controls how much of the variance in the predicted values should be
        taken into account. If set to be very high, then we are favouring
        exploration over exploitation and vice versa.
+        If set to 'Aopt', the acquisition function will only use the variance


Sorry for being a prick but is Aopt the best name?
`

I agree, since we do not have any other acquisition functions approximating optimal designs, we could call it something like 'var', 'variance', 'var_only' or 'explore_only'. I am open to suggestions.

"variance" is fine with me.

MechCoder · 2017-07-26T04:22:41Z

skopt/acquisition.py

        Controls how much of the variance in the predicted values should be
        taken into account. If set to be very high, then we are favouring
        exploration over exploitation and vice versa.
+        If set to 'variance', the acquisition function will only use the variance


Sorry again, but this should be `std'?

Do you talk about the name of acquisition function? Some might have weird associations with 'std' as abbreviation 😅

kiudee · 2017-07-26T06:49:03Z

After looking at the scikit-optimize documentation I would propose calling it uncertainty which is the term used in the introduction of Bayesian optimization. Though technically true that we pick the points maximizing standard deviation and equivalently variance, I would say it is more consistent to use uncertainty. Thoughts?

…

On Wed, 26 Jul 2017, 06:22 MechCoder, ***@***.***> wrote: ***@***.**** commented on this pull request. ------------------------------ In skopt/acquisition.py <#432 (comment)> : > Controls how much of the variance in the predicted values should be taken into account. If set to be very high, then we are favouring exploration over exploitation and vice versa. + If set to 'variance', the acquisition function will only use the variance Sorry again, but this should be `std'? — You are receiving this because you modified the open/close state. Reply to this email directly, view it on GitHub <#432 (review)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAic-YV9JRVmmJuFnD9kbyJkysGenqgHks5sRr8RgaJpZM4OVVss> .

MechCoder · 2017-07-27T05:42:02Z

So the confusion on my side is because kappa denotes the value by which the std is multiplied and not the acquisition function itself.

I would be fine with allowing kappa="inf" or/and kappa=np.inf with a note that says this sets off exploitation. WDYT?

glouppe · 2017-07-27T05:53:47Z

No strong opinion from my side. Either way is fine for me. (sent from my phone)

…

On 27 Jul 2017 07:42, "MechCoder" ***@***.***> wrote: So the confusion on my side is because kappa denotes the value by which the std is multiplied and not the acquisition function itself. I would be fine with allowing kappa="inf" or/and kappa=np.inf with a note that says this sets off exploitation. WDYT? — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#432 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAdKSwKLv4ENwGT8IeHjOyvdKcEXGzZ1ks5sSCMqgaJpZM4OVVss> .

kiudee · 2017-07-27T07:26:57Z

I would be fine calling it `'inf'` and explaining it in the docstring. Gilles Louppe <[email protected]> schrieb am Do., 27. Juli 2017 um 07:53 Uhr:

…

No strong opinion from my side. Either way is fine for me. (sent from my phone) On 27 Jul 2017 07:42, "MechCoder" ***@***.***> wrote: > So the confusion on my side is because kappa denotes the value by which > the std is multiplied and not the acquisition function itself. > > I would be fine with allowing kappa="inf" or/and kappa=np.inf with a note > that says this sets off exploitation. WDYT? > > — > You are receiving this because you commented. > Reply to this email directly, view it on GitHub > < #432 (comment) >, > or mute the thread > < https://github.com/notifications/unsubscribe-auth/AAdKSwKLv4ENwGT8IeHjOyvdKcEXGzZ1ks5sSCMqgaJpZM4OVVss > > . > — You are receiving this because you modified the open/close state. Reply to this email directly, view it on GitHub <#432 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAic-dmLTgCPa8hRLqPdoQC2N4TFzxa_ks5sSCXsgaJpZM4OVVss> .

Since in LCB the variable kappa is used to describe how much weight is given to the standard deviation, 'inf' is a more natural name for the limit of this weight.

glouppe · 2017-07-27T11:54:26Z

Good to go for me when Travis is happy.

kiudee · 2017-07-27T12:16:35Z

The Travis build canceled due to
The job exceeded the maximum time limit for jobs, and has been terminated.

MechCoder · 2017-07-28T04:08:42Z

Thanks!

kiudee force-pushed the aopt branch from e6291fd to 0da7b5c Compare July 12, 2017 09:11

betatim mentioned this pull request Jul 12, 2017

Picking initial points with latin hypercubes #433

Open

kiudee closed this Jul 19, 2017

kiudee force-pushed the aopt branch from 0da7b5c to a151a9a Compare July 19, 2017 09:11

Implement A-optimal selection in LCB acquisition

283e830

kiudee reopened this Jul 19, 2017

glouppe changed the title ~~Implement greedy A-optimal acquisition function for pure exploration~~ [MRG+1] Implement greedy A-optimal acquisition function for pure exploration Jul 21, 2017

MechCoder reviewed Jul 22, 2017

View reviewed changes

MechCoder reviewed Jul 26, 2017

View reviewed changes

Rename Aopt to inf

3824ef0

Since in LCB the variable kappa is used to describe how much weight is given to the standard deviation, 'inf' is a more natural name for the limit of this weight.

kiudee force-pushed the aopt branch from acec653 to 3824ef0 Compare July 27, 2017 11:12

MechCoder merged commit bb73e24 into scikit-optimize:master Jul 28, 2017

yngtodd mentioned this pull request Jul 31, 2017

Mutual information acquisition function for Gaussian processes? #456

Open

sqbl mentioned this pull request Dec 27, 2023

Use of gradient calculation in acq_funct's novonordisk-research/ProcessOptimizer#209

Closed

[MRG+1] Implement greedy A-optimal acquisition function for pure exploration #432

[MRG+1] Implement greedy A-optimal acquisition function for pure exploration #432

Uh oh!

Conversation

kiudee commented Jul 12, 2017

Uh oh!

codecov-io commented Jul 12, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

iaroslav-ai commented Jul 12, 2017

Uh oh!

kiudee commented Jul 12, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

betatim commented Jul 12, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

MechCoder commented Jul 12, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

kiudee commented Jul 13, 2017

Uh oh!

MechCoder commented Jul 15, 2017

Uh oh!

kiudee commented Jul 15, 2017 via email

Uh oh!

kiudee commented Jul 19, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

glouppe commented Jul 21, 2017

Uh oh!

MechCoder Jul 22, 2017

Choose a reason for hiding this comment

Uh oh!

kiudee Jul 24, 2017

Choose a reason for hiding this comment

Uh oh!

glouppe Jul 25, 2017

Choose a reason for hiding this comment

Uh oh!

MechCoder Jul 26, 2017

Choose a reason for hiding this comment

Uh oh!

iaroslav-ai Jul 26, 2017

Choose a reason for hiding this comment

Uh oh!

kiudee commented Jul 26, 2017 via email

Uh oh!

MechCoder commented Jul 27, 2017

Uh oh!

glouppe commented Jul 27, 2017 via email

Uh oh!

kiudee commented Jul 27, 2017 via email

Uh oh!

glouppe commented Jul 27, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

kiudee commented Jul 27, 2017

Uh oh!

MechCoder commented Jul 28, 2017

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

codecov-io commented Jul 12, 2017 •

edited

Loading

kiudee commented Jul 12, 2017 •

edited

Loading

betatim commented Jul 12, 2017 •

edited

Loading

MechCoder commented Jul 12, 2017 •

edited

Loading

kiudee commented Jul 19, 2017 •

edited

Loading

glouppe commented Jul 27, 2017 •

edited

Loading