You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Frank Hess (JIRA)" <ji...@apache.org> on 2012/09/22 00:54:08 UTC
[jira] [Created] (MATH-867) CMAESOptimizer with bounds fits finely
near lower bound and coarsely near upper bound.
Frank Hess created MATH-867:
-------------------------------
Summary: CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
Key: MATH-867
URL: https://issues.apache.org/jira/browse/MATH-867
Project: Commons Math
Issue Type: Bug
Reporter: Frank Hess
When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Nikolaus Hansen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13465719#comment-13465719 ]
Nikolaus Hansen commented on MATH-867:
--------------------------------------
{quote}
I believe the reason is that defaulting sigma to 0.3 times the range causes the fitter to jump from the initial value (which is order of 1 away from the target) to some huge value on the order of 1e16 on the first step.
{quote}
Right. I suggest to make sigmaArray independent of the boundary values. Otherwise setting boundaries like [1e-15,1e15] still will most likely lead to an unexpected behavior: the user just does not want to exceed this value, while the algorithm interprets the interval as being reasonable values to be checked out. Still it makes perfectly sense to check consistency between the initial guess, sigmaArray and boundaries, in that, say,
{code}
fitfun.encode(guess)[i] - sigmaArray[i]/2. > fitfun.encode(boundaries[0])[i]
{code}
in case of a lower bound.
{quote}
It doesn't reach the target exactly due to one of the many stop conditions hard-coded into the generationLoop which decide that the fit is "good enough" and quit.
{quote}
more specifically, stopTolX is defined relative to the initial value of sigmaArray. This specific problem should therefore go away if stopTolX is defined as an absolute value like 1e-11. I think absolute and relative definition of stopTolX are both justified.
Generally, the patch becomes buggy, when encode and decode are changed/reused. In this case, where solutions are compared with boundaries, like
{code}
if(x[i] < boundaries[0][i])
{code}
the comparison must be done with encoded boundaries:
{code}
encLboundaries = fitfun.encode(boundaries[0]);
if (x[i] < encLboundaries[i])
{code}
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Nikolaus Hansen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466199#comment-13466199 ]
Nikolaus Hansen commented on MATH-867:
--------------------------------------
I second to make encode/decode the identity to address the bug. I don't even see a different way to address it. Then, inputSigma/sigmaArray/insigma should become independent of the boundary values (which seems consistent with the doc, as long as encode/decode remains the identity).
my previous snippet must read
{code}
guess[i] - sigmaArray[i]/2. > fitfun.encode(boundaries[0])[i]
{code}
because we have
{code}
final double[] guess = fitfun.encode(getStartPoint());
{code}
i.e. guess is an encoded initial guess.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466222#comment-13466222 ]
Gilles commented on MATH-867:
-----------------------------
I don't understand. This is the documentation:
{code}
/**
* Individual sigma values - initial search volume. inputSigma determines
* the initial coordinate wise standard deviations for the search. Setting
* SIGMA one third of the initial search region is appropriate.
*/
private double[] inputSigma;
{code}
AFAIUC, this says that sigma is _not_ independent on the boundary values.
bq. I second to make encode/decode the identity to address the bug.
I also don't understand this. Referring to the code of "decode":
{code}
public double[] decode(final double[] x) {
if (boundaries == null) {
return x;
}
double[] res = new double[x.length];
for (int i = 0; i < x.length; i++) {
double diff = boundaries[1][i] - boundaries[0][i];
// res[i] = diff * x[i] + boundaries[0][i]; // XXX orig
// res[i] = diff * x[i]; // XXX v1
res[i] = x[i]; // XXX v2
}
return res;
}
{code}
_This_ issue's bug is solved by normalizing the variables (line marked with "XXX v1" in the above snippet). The downside is that "testConstrainedRosen" fails.
When "decode" is made the identity (line marked with "XXX v2"), "testConstrainedRosen" passes but "testFitAccuracyDependsOnBoundary" fails, as with the original code (line marked with "XXX orig").
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Nikolaus Hansen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13463747#comment-13463747 ]
Nikolaus Hansen commented on MATH-867:
--------------------------------------
Why are variables transformations generally desirable? Because, for example, if a parameter x_i should only have positive values, the transformation x_i -> x_i^2 makes the objective function compatible to any unbounded optimizer. Or, for example, rescaling of variables (e.g. unit m in km etc) can change an ill-conditioned problem to a well-conditioned one.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Nikolaus Hansen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13461891#comment-13461891 ]
Nikolaus Hansen commented on MATH-867:
--------------------------------------
It seems important to point out that a parameter transformation or scaling and variable boundaries are two different things. That they are mixed in the code/interface I would indeed consider as a bug. Generally, the boundary handling can be done without any variable transformation and therefore does not need to effect precision.
If we want positive variable values only, the code should support only applying a lower bound in some way.
My suggestion would be indeed to have as interface boundaries and a unit-scale for each parameter (by default one). Only the latter would control the "encoding", in the way suggested above as "diff".
Maybe it is still important to mention: a relevant initial parameter to CMA-ES is an initial step-size (a standard deviation) related to the unit-scale, which seem to be hidden from the user as it is now. You might think of this step-size as similar to the width of the initial simplex in Nelder&Mead.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Nikolaus Hansen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466240#comment-13466240 ]
Nikolaus Hansen commented on MATH-867:
--------------------------------------
regarding the documentation of inputSigma: I don't see in what sense the doc says that it depends on the bounds. The doc says how it should be set (but this is a bit blurry, to the extend of how "initial search volume" and "initial search region" are interpreted)
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Frank Hess (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13461788#comment-13461788 ]
Frank Hess commented on MATH-867:
---------------------------------
I tried changing the FitnessFunction.encode/decode methods so they don't offset and that causes my test program to fit well near both bounds. That is, I changed encode from:
res[i] = (x[i] - boundaries[0][i]) / diff;
to:
res[i] = x[i] / diff;
and changed decode from:
res[i] = diff * x[i] + boundaries[0][i];
to:
res[i] = diff * x[i];
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MATH-867) CMAESOptimizer with bounds fits finely
near lower bound and coarsely near upper bound.
Posted by "Frank Hess (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Frank Hess updated MATH-867:
----------------------------
Attachment: MATH867_patch
Attached a patch. It makes encode/decode identities and removes the restrictions on infinite ranges. The test on fit resolution near upper/lower bounds fails. I believe the reason is that defaulting sigma to 0.3 times the range causes the fitter to jump from the initial value (which is order of 1 away from the target) to some huge value on the order of 1e16 on the first step. The fitter then has to work its way all the way back to the target. It doesn't reach the target exactly due to one of the many stop conditions hard-coded into the generationLoop which decide that the fit is "good enough" and quit. That should probably be entered as a different ticket though, in that there is no way to override the internal stop conditions and make the fitter try harder. The ConvergenceChecker which can be passed into the optimizer only has the ability to terminate the optimizer earlier than it normally would quit, it doesn't suppress the other stop conditions which can't be directly controlled by the user.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466269#comment-13466269 ]
Gilles commented on MATH-867:
-----------------------------
Revision 1391840 contains modified "encode" and "decode" functions. Both unit tests now pass (for "testConstrainedRosen" I had to move the initial guess closer to the solution).
No change was required for "inputSigma"; I still do not understand why it works as is (cf. lines 588, 589). And I have no idea how to improve the documentation...
bq. yes. Otherwise it will sample and evaluation points outside the boundaries.
No, because the modified objective function wouldn't have boundaries.
bq. probably not the same, but possibly reasonably well, unless the boundary is mapped to (or close to) inf, which is likely to lead to unexpected results, if the optimum is on (or close to) the boundary.
In such a case, I imagine that a "penalty" adapter would work better than a "mapping" adapter. Both are available.
bq. The methods developed for CMA-ES should work much better in this case.
Hence, unless someone wants to try it out, we'll of course trust you :) and leave the internal boundary handling in place.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Frank Hess (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13461878#comment-13461878 ]
Frank Hess commented on MATH-867:
---------------------------------
To elaborate on my previous point, the CMAESOptimizer also doesn't allow mixing of bounded and unbounded parameters. So, if I only want to apply a bound to one parameter of a multi-parameter fit, then the best I can do is set the bounds of the "unbounded" parameters to be [-VeryLargeValue, +VeryLargeValue]. This causes the fit precision around zero for the "unbounded" to be much worse than when no bounds are specified at all.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466344#comment-13466344 ]
Gilles commented on MATH-867:
-----------------------------
Revision 1391908 contains the cleaned up code:
* All limitations concerning boundary specifications removed. This supersedes the fix for MATH-865.
* Methods "encode" and "decode" removed.
* "sigmaArray" is assigned the values from "inputSigma" (or 0.3 if "inputSigma" is null). This probably also solves MATH-868.
Please test.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Nikolaus Hansen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466331#comment-13466331 ]
Nikolaus Hansen commented on MATH-867:
--------------------------------------
{quote}
And the two tests still fail.
{quote}
did you correct the bug in the repair method that I proposed above?
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MATH-867) CMAESOptimizer with bounds fits finely
near lower bound and coarsely near upper bound.
Posted by "Frank Hess (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Frank Hess updated MATH-867:
----------------------------
Attachment: Math867Test.java
Attached a test program.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13468711#comment-13468711 ]
Gilles commented on MATH-867:
-----------------------------
Thanks. The improved Javadoc is in revision 1393641.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Fix For: 3.1
>
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466313#comment-13466313 ]
Gilles commented on MATH-867:
-----------------------------
bq. As said before it would simplify the code if both transformations were omitted (but we could leave this to another issue).
I would like to, but as I said, the identity transformation makes one of the tests fail.
It must be because something else in the code assumes that the parameters have been restricted into the [0, 1] interval, which is not true anymore.
I wonder whether the various matrices (around lines 380) are computed based on this assumption...
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466345#comment-13466345 ]
Gilles commented on MATH-867:
-----------------------------
bq. did you correct the bug in the repair method that I proposed above?
Yes. There was some unnecessary fiddling because of asynchronous updates of this page and the email notifications of those updates...
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Nikolaus Hansen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466317#comment-13466317 ]
Nikolaus Hansen commented on MATH-867:
--------------------------------------
I have corrected the repair: the last assignment
{code}
} else {
repaired[i] = x[i];
{code}
was missing (sorry). Now there is some chance that it might pass...
{quote}
I certainly agree. But since there was something wrong before in the code, one could also imagine that it was because of the problem that it passed before...
{quote}
that seems somehow irrelevant: it is an absolute statement about the algorithm, that an implementation of it must pass this test. It's not related to the question when and why it has already been past or not.
otherwise, the code was, AFAICS, not wrong before unless with boundary values as large as 1e16 in absolute value.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13465988#comment-13465988 ]
Gilles commented on MATH-867:
-----------------------------
bq. Attached a patch. It makes encode/decode identities and removes the restrictions on infinite ranges.
Sorry but it is not good: You are removing the fix to your other issue (MATH-865). Even if it won't be necessary anymore when this issue is fixed, it cannot be reverted as part of this issue. Let's leave the possibility to have infinite bounds for later, and focus on making the code work with finite bounds.
bq. The test on fit resolution near upper/lower bounds fails.
This is what must be fixed by the patch, without any side-effects (i.e. other tests failing).
bq. I believe the reason is that defaulting sigma to 0.3 times the range [...]
In MATH-868, I noted that this does not work, since using this value makes the "testFitAccuracyDependsOnBoundary" fail. From this I conclude, that if the doc for "inputSigma" is correct, then there is something else to be changed in the code, or that the doc must be changed to indicate that "inputSigma" is "relative".
Nikolaus seems to confirm the latter (IIUC):
{noformat}
fitfun.encode(guess)[i] - sigmaArray[i]/2. > fitfun.encode(boundaries[0])[i]
{noformat}
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Nikolaus Hansen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466308#comment-13466308 ]
Nikolaus Hansen commented on MATH-867:
--------------------------------------
{quote}
Revision 1391840 contains modified "encode" and "decode" functions. Both unit tests now pass (for "testConstrainedRosen" I had to move the initial guess closer to the solution).
No change was required for "inputSigma"; I still do not understand why it works as is (cf. lines 588, 589).
{quote}
to me it makes perfectly sense: luckily enough line 589 performs the same transformation on inputSigma as the encode function on getStartPoint() (maybe this should be mentioned in a comment?). As the transformation is linear, the situations before and after the transformations are mathematically equivalent (the bug came from loosing digits due to a subtraction, which is now omitted). As said before it would simplify the code if both transformations were omitted (but we could leave this to another issue).
{quote}
And I have no idea how to improve the documentation...
{quote}
I'll think about it.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Nikolaus Hansen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466239#comment-13466239 ]
Nikolaus Hansen commented on MATH-867:
--------------------------------------
{quote}
Since in some previous comments, you indicated that boundaries do not necessarily need to be taken into account inside the CMAES algorithm, a possibility is to review the entire code, and remove all code related to boundaries.
{quote}
I believe that this must be a misunderstanding. We do not need the transformation into [0,1] (or any other transformation for that matter) to take into account boundaries. But we need to possibly take into account the boundaries within CMAES, if the returned solution is supposed to be in the bounds.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Comment Edited] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Nikolaus Hansen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466297#comment-13466297 ]
Nikolaus Hansen edited comment on MATH-867 at 9/30/12 7:52 AM:
---------------------------------------------------------------
{quote}
Revision 1391840 contains modified "encode" and "decode" functions. Both unit tests now pass (for "testConstrainedRosen" I had to move the initial guess closer to the solution).
{quote}
if the test does not pass with initial point at 0.1, something is wrong (and it doesn't look like a good idea to change the test to make the code pass).
I found at least one problem:
{code}
private double[] repair(final double[] x) {
double[] repaired = new double[x.length];
for (int i = 0; i < x.length; i++) {
if (x[i] < 0) {
repaired[i] = 0;
} else if (x[i] > 1.0) {
repaired[i] = 1.0;
} else {
repaired[i] = x[i];
}
}
return repaired;
}
{code}
must read
{code}
private double[] repair(final double[] x) {
double[] repaired = new double[x.length];
if (boundaries == null) {
for (int i = 0; i < x.length; i++) {
repaired[i] = x[i];
}
} else {
final double[] bLoEnc = encode(boundaries[0]);
final double[] bHiEnc = encode(boundaries[1]);
for (int i = 0; i < x.length; i++) {
if (x[i] < bLoEnc[i]) {
repaired[i] = bLoEnc[i];
} else if (x[i] > bHiEnc[i]) {
repaired[i] = bHiEnc[i];
} else {
repaired[i] = x[i];
}
}
}
return repaired;
}
{code}
I am not sure whether or not this is the reason why the test fails.
was (Author: jolievie):
{quote}
Revision 1391840 contains modified "encode" and "decode" functions. Both unit tests now pass (for "testConstrainedRosen" I had to move the initial guess closer to the solution).
{quote}
if the test does not pass with initial point at 0.1, something is wrong (and it doesn't look like a good idea to change the test to make the code pass).
I found at least one problem:
{code}
private double[] repair(final double[] x) {
double[] repaired = new double[x.length];
for (int i = 0; i < x.length; i++) {
if (x[i] < 0) {
repaired[i] = 0;
} else if (x[i] > 1.0) {
repaired[i] = 1.0;
} else {
repaired[i] = x[i];
}
}
return repaired;
}
{code}
must read
{code}
private double[] repair(final double[] x) {
double[] repaired = new double[x.length];
if (boundaries == null) {
for (int i = 0; i < x.length; i++) {
repaired[i] = x[i];
}
} else {
final double[] bLoEnc = encode(boundaries[0]);
final double[] bHiEnc = encode(boundaries[1]);
for (int i = 0; i < x.length; i++) {
if (x[i] < bLoEnc[i]) {
repaired[i] = bLoEnc[i];
} else if (x[i] > bHiEnc[i]) {
repaired[i] = bHiEnc[i];
}
}
}
return repaired;
}
{code}
I am not sure whether or not this is the reason why the test fails.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13465521#comment-13465521 ]
Gilles commented on MATH-867:
-----------------------------
I've tried Frank's proposal [above|https://issues.apache.org/jira/browse/MATH-867?focusedCommentId=13461788&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-13461788]; in the code, I only modified the "encode" and "decode" functions.
This made one unit test fail ("testConstrainedRosen").
I think that the test is partly incorrect in the tolerance setting and in the selection of the starting point, but even with those changed, I get critically different behaviours due to the "isActiveCMA" flag.
If "true", the solution is found with pretty good accuracy:
{noformat}
sol=[1.0000000029406888, 1.0000000045238486, 0.9999999996025084, 0.9999999959542569, 0.9999999988066054, 0.9999999956724651, 1.0000000008220962, 1.0000000011037358, 1.0000000004144547, 0.9999999946437816, 0.9999999977923537, 1.0000000007816154, 1.0000000164552258]
{noformat}
But when set to "false", the result is:
{noformat}
sol=[0.997107074864516, 0.9942080214735094, 0.9884131718553784, 0.9768835748661846, 0.954143705394098, 0.910067297297918, 0.8275510138614142, 0.6833931486612853, 0.4636505565068948, 0.20554769008446425, 0.0, 0.009899135523990096, 0.0]
{noformat}
Is this expected? If so, wouldn't it be safer to always set this flag to "true" (thus removing it as a user input)?
If unexpected, does it indicate that other things must be changed in addition to "encode"/"decode"?
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Nikolaus Hansen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466246#comment-13466246 ]
Nikolaus Hansen commented on MATH-867:
--------------------------------------
{quote}
However v2 makes the remaining modifications simpler.
The problem is that we don't know what are "the remaining modifications":
{quote}
I thought I knew...
{quote}we never got beyond to the point were both "testFitAccuracyDependsOnBoundary" and "testConstrainedRosen" pass.
{quote}
the former, because inputSigma was not adapted appropriately, the latter because the test against boundaries was not adapted appropriately.
{quote}
There are two different things:
1. Does the existence of constraints modify the search procedure is some way (i.e. CMAES must "know" that it deals with boundaries)?
{quote}
yes. Otherwise it will sample and evaluation points outside the boundaries.
{quote}
2. Alternately, is it possible to pass a modified objective function (in which the allowed range of the original objective function has been mapped to the [-inf, +inf] interval) and have CMAES behave the same (i.e. find the same solution)?
{quote}
probably not the same, but possibly reasonably well, unless the boundary is mapped to (or close to) inf, which is likely to lead to unexpected results, if the optimum is on (or close to) the boundary.
checking MultivariateFunctionPenaltyAdapter (which does not map the parameters, rather computes a penalty), the answer is likely to be no, if the optimal solution happens to be on (or very close to) the bound.
{quote}
regarding the documentation of inputSigma: I don't see in what sense the doc says that it depends on the bounds.
Then what is "initial search volume"?
{quote}
the volume/region where points are likely to be sampled in the beginning of the search. Points beyond, say, startpoint + 10*sigma are not likely to be sampled in the beginning.
{quote}
I interpret the doc as roughly saying "0.3 times the range". Perhaps this is wrong, in which case it should be made clearer...
{quote}
I agree, it is not clear (I guess it was taken from another doc and slightly changed context).
{quote}
We noticed that very small or very large values for "sigma" did not work; so maybe we should say "inputSigma must be of order 1" .
{quote}
no, it entirely depends on how far we expect the optimal solution to be from the start solution. Putting it differently: one could rescale parameters by a factor 1000 (say in one case it is km, in the other m), then one would need to rescale inputSigma accordingly (which would not be in the order of one).
Codes I write typically don't accept a default value for inputSigma, basically for this reason. I agree however that a value of 1 might often turn out OK.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Nikolaus Hansen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466309#comment-13466309 ]
Nikolaus Hansen commented on MATH-867:
--------------------------------------
{quote}
Hence, unless someone wants to try it out, we'll of course trust you and leave the internal boundary handling in place.
{quote}
I spent several hundreds of hours (really!) to investigate (and try to understand) this with the greatest care I was able to. That of course doesn't mean there could be still surprises out there...
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466333#comment-13466333 ]
Gilles commented on MATH-867:
-----------------------------
bq. I have corrected the repair: the last assignment [...]
Oops, I had missed that comment.
That's much better now. :)
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Nikolaus Hansen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466297#comment-13466297 ]
Nikolaus Hansen commented on MATH-867:
--------------------------------------
{quote}
Revision 1391840 contains modified "encode" and "decode" functions. Both unit tests now pass (for "testConstrainedRosen" I had to move the initial guess closer to the solution).
{quote}
if the test does not pass with initial point at 0.1, something is wrong (and it doesn't look like a good idea to change the test to make the code pass).
I found at least one problem:
{code}
private double[] repair(final double[] x) {
double[] repaired = new double[x.length];
for (int i = 0; i < x.length; i++) {
if (x[i] < 0) {
repaired[i] = 0;
} else if (x[i] > 1.0) {
repaired[i] = 1.0;
} else {
repaired[i] = x[i];
}
}
return repaired;
}
{code}
must read
{code}
private double[] repair(final double[] x) {
double[] repaired = new double[x.length];
if (boundaries == null) {
for (int i = 0; i < x.length; i++) {
repaired[i] = x[i];
}
} else {
final double[] bLoEnc = encode(boundaries[0]);
final double[] bHiEnc = encode(boundaries[1]);
for (int i = 0; i < x.length; i++) {
if (x[i] < bLoEnc[i]) {
repaired[i] = bLoEnc[i];
} else if (x[i] > bHiEnc[i]) {
repaired[i] = bHiEnc[i];
}
}
}
return repaired;
}
{code}
I am not sure whether or not this is the reason why the test fails.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Nikolaus Hansen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13463721#comment-13463721 ]
Nikolaus Hansen commented on MATH-867:
--------------------------------------
the "bug" is not in the original code. In some CMA-ES codes, variable transformations are provided as an option (not in the one which was translated). This is however just meant as a convenience feature, as it could be equivalently implemented as part of the objective function (and should IMHO preferably viewed as such). This should IMHO be a general feature implemented in the optimization library, as the benefits of variable transformations are not tightly linked to any specific optimization method.
It should be easily possible to drop the transformation in CMAESOptimizer, in which case 0 and 1 must be replaced by the lower and upper boundary values in some parts of the code.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466310#comment-13466310 ]
Gilles commented on MATH-867:
-----------------------------
Thanks for looking into this. Unfortunately, a copy/paste of your version of "repair" (which I totally agree with) makes the tests fail again!
And we can also worry that the tests pass with the wrong version...
bq. if the test does not pass with initial point at 0.1, something is wrong (and it doesn't look like a good idea to change the test to make the code pass).
I certainly agree. But since there was something wrong before in the code, one could also imagine that it was because of the problem that it passed before...
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Comment Edited] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466222#comment-13466222 ]
Gilles edited comment on MATH-867 at 9/30/12 12:40 AM:
-------------------------------------------------------
I don't understand. This is the documentation:
{code}
/**
* Individual sigma values - initial search volume. inputSigma determines
* the initial coordinate wise standard deviations for the search. Setting
* SIGMA one third of the initial search region is appropriate.
*/
private double[] inputSigma;
{code}
AFAIUC, this says that sigma is _not_ independent on the boundary values.
bq. I second to make encode/decode the identity to address the bug.
I also don't understand this. Referring to the code of "decode":
{code}
public double[] decode(final double[] x) {
if (boundaries == null) {
return x;
}
double[] res = new double[x.length];
for (int i = 0; i < x.length; i++) {
double diff = boundaries[1][i] - boundaries[0][i];
// res[i] = diff * x[i] + boundaries[0][i]; // XXX orig
// res[i] = diff * x[i]; // XXX v1
res[i] = x[i]; // XXX v2
}
return res;
}
{code}
_This_ issue's bug is solved by normalizing the variables (line marked with "XXX v1" in the above snippet). The downside is that "testConstrainedRosen" fails.
When "decode" is made the identity (line marked with "XXX v2"), "testConstrainedRosen" passes but "testFitAccuracyDependsOnBoundary" fails, as with the original code (line marked with "XXX orig").
Since in some previous comments, you indicated that boundaries do not necessarily need to be taken into account inside the CMAES algorithm, a possibility is to review the entire code, and remove all code related to boundaries.
Would you (or Frank) be willing to do that? In the affirmative, a new issue must be created for that task.
Then, the "encode"/"decode" functions will disappear (by design) and so will the issue about "inputSigma".
Unit tests "testConstrainedRosen" and "testFitAccuracyDependsOnBoundary" will also be removed since the internal support form boundaries won't exist anymore.
All issues solved in one fell swoop! :)
was (Author: erans):
I don't understand. This is the documentation:
{code}
/**
* Individual sigma values - initial search volume. inputSigma determines
* the initial coordinate wise standard deviations for the search. Setting
* SIGMA one third of the initial search region is appropriate.
*/
private double[] inputSigma;
{code}
AFAIUC, this says that sigma is _not_ independent on the boundary values.
bq. I second to make encode/decode the identity to address the bug.
I also don't understand this. Referring to the code of "decode":
{code}
public double[] decode(final double[] x) {
if (boundaries == null) {
return x;
}
double[] res = new double[x.length];
for (int i = 0; i < x.length; i++) {
double diff = boundaries[1][i] - boundaries[0][i];
// res[i] = diff * x[i] + boundaries[0][i]; // XXX orig
// res[i] = diff * x[i]; // XXX v1
res[i] = x[i]; // XXX v2
}
return res;
}
{code}
_This_ issue's bug is solved by normalizing the variables (line marked with "XXX v1" in the above snippet). The downside is that "testConstrainedRosen" fails.
When "decode" is made the identity (line marked with "XXX v2"), "testConstrainedRosen" passes but "testFitAccuracyDependsOnBoundary" fails, as with the original code (line marked with "XXX orig").
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Nikolaus Hansen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466328#comment-13466328 ]
Nikolaus Hansen commented on MATH-867:
--------------------------------------
{quote}
I may be missing something (and I can just make wild guesses since I have no clue about the CMAES algorithm) but I would be expecting that the code behaves the same way without boundaries as with boundaries that become arbitrarily large (i.e. when the [loBound, hiBound] interval becomes [-inf, +inf]).
The line that uses "inputSigma" does not behave that way since the "range" becomes arbitrarily large as the bounds grow although when there is no boundaries it is set 1.0.
{quote}
as both, x and sigma are transformed in the same way it does not matter mathematically. If you choose boundaries as large as (close to) maxdouble, it will matter numerically.
{quote}
This is also shown by some unit tests which I've just set up, by copying existing ones which minimized a function without constraint and specifying a very large allowed interval (e.g. [-1e20, 1e20]): those tests fail.
{quote}
did you correct the mistake in the repair method I proposed above?
{quote}
Intuitively, when the solution is far from the bounds (and the initial point also), whether there are bounds or not should not matter. But with the current implementation that's clearly not the case.
{quote}
I agree. I am confident we will be able to sort this out.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466323#comment-13466323 ]
Gilles commented on MATH-867:
-----------------------------
bq. to me it makes perfectly sense: luckily enough line 589 performs the same transformation on inputSigma as the encode function on getStartPoint() [...]
I may be missing something (and I can just make wild guesses since I have no clue about the CMAES algorithm) but I would be expecting that the code behaves the same way without boundaries as with boundaries that become arbitrarily large (i.e. when the [loBound, hiBound] interval becomes [-inf, +inf]).
The line that uses "inputSigma" does not behave that way since the "range" becomes arbitrarily large as the bounds grow although when there is no boundaries it is set 1.0.
This is also shown by some unit tests which I've just set up, by copying existing ones which minimized a function without constraint and specifying a very large allowed interval (e.g. [-1e20, 1e20]): those tests fail.
Intuitively, when the solution is far from the bounds (and the initial point also), whether there are bounds or not should not matter. But with the current implementation that's clearly not the case.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13461300#comment-13461300 ]
Gilles commented on MATH-867:
-----------------------------
bq. This is because it internally maps the fitted parameter range into the interval [0,1]
If this is indeed the reason, not much can be done short of modifying the algorithm. The implementation we have in CM was ported from the original code under the supervision of the original author. Maybe you should ask him this question.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466327#comment-13466327 ]
Gilles commented on MATH-867:
-----------------------------
bq. The reason is IMHO line 589, which does need to be changed according to the change in encode/decode.
That cannot be the end of the story; I've just tried:
* remove the division by "range" on that line
* "encode" and "decode" are the identity
And the two tests still fail.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Nikolaus Hansen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466319#comment-13466319 ]
Nikolaus Hansen commented on MATH-867:
--------------------------------------
{quote}
I would like to, but as I said, the identity transformation makes one of the tests fail.
It must be because something else in the code assumes that the parameters have been restricted into the [0, 1] interval, which is not true anymore.
{quote}
The reason is IMHO line 589, which does need to be changed according to the change in encode/decode.
{quote}
I wonder whether the various matrices (around lines 380) are computed based on this assumption...
{quote}
I would not worry much, I am pretty sure they are not.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13465630#comment-13465630 ]
Gilles commented on MATH-867:
-----------------------------
In revision 1391477, I've added a unit test ("testFitAccuracyDependsOnBoundary") based on your attached file. But it is disabled since it fails with the current implementation (as this was the reason for this report).
I changed "isFeasible()" but it was not enough to make the "testConstrainedRosen" pass; modifying "sigmaArray" as per your last comment entails that the above unit test fails again, though it passed with all but the "sigmaArray" changes. :(
Could you please provide a patch against the latest revision, once you are sure that all unit test pass (also removing the "@Ignore" annotation on "testFitAccuracyDependsOnBoundary")? Thanks.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Frank Hess (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13461867#comment-13461867 ]
Frank Hess commented on MATH-867:
---------------------------------
If I'm fitting a peak width, for example, I only want to fit positive widths. So specifying a range with a bound on only one end like [0,+Infinity] would be natural. Now the CMAESOptimizer doesn't accept infinite bounds, so the best I could do would be something like [0, VeryLargeValue]. And I might reasonably use an initial peak width of 1. My expectation as a user is that specifying this bound actually helps the optimizer. Instead what happens is the entirely the opposite (well, actually it works fine when the lower bound is zero but would blow up if you were setting a finite upper bound instead of a finite lower bound).
As a user the encoding of my fitted parameters to the interval 0 to 1 is entirely invisible and internal to the library. So my expectation is the optimizer would give results with a precision matching the precision of the parameter being fitted (in the form I passed it in, not in some internal normalized form I know nothing about).
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Frank Hess (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13461783#comment-13461783 ]
Frank Hess commented on MATH-867:
---------------------------------
I've sent an email to the original author. I've copied what I wrote to him below for reference:
{quote}
Hi,
I was wondering if you have any input on this bug in the Apache Commons implementation of your algorithm:
https://issues.apache.org/jira/browse/MATH-867
It seems to be due to their attempt to follow your "encoding of variables" hint. They map parameters on to the interval [0,1] when boundaries are provided, which can have a bad interaction with how floating point variable ULP are distributed. Since your hint seems to suggest the main point of this encoding is just make the width of the intervals uniform, it seems to me they could just scale the boundaries onto a interval of unit width without offseting the interval to start at zero. This would get rid of the mismatch in ULP distribution between the scaled interval and the original boundaries.
{quote}
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466900#comment-13466900 ]
Gilles commented on MATH-867:
-----------------------------
Thanks; I'll thus set this issue as "resolved".
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Frank Hess (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13461957#comment-13461957 ]
Frank Hess commented on MATH-867:
---------------------------------
bq. It seems important to point out that a parameter transformation or scaling and variable boundaries are two different things. That they are mixed in the code/interface I would indeed consider as a bug. Generally, the boundary handling can be done without any variable transformation and therefore does not need to effect precision.
That's good news, I think things would work a lot closer to my expectations if the boundary handling was done without a transformation.
bq. If we want positive variable values only, the code should IMHO support only applying a lower bound in some way.
AFAICT the variable transformation is the main reason CMAESOptimizer doesn't let you use infinite values as bounds. So if the transformation is dropped, we can have infinity as a bound value, which gives support for only specifying a bound on one side, plus mixing bounded and unbounded parameters.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Frank Hess (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13465568#comment-13465568 ]
Frank Hess commented on MATH-867:
---------------------------------
I think you should also modify isFeasible() and initializeCMA(). isFeasible should use the bounds instead of the unit interval. initializeCMA should initialize sigmaArray to to be equal to inputSigma if inputSigma is not null, or to 0.3 times the range (as long as the boundaries are not such that the range is calculated to be infinity).
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Nikolaus Hansen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13465693#comment-13465693 ]
Nikolaus Hansen commented on MATH-867:
--------------------------------------
{quote}
But when set to "false", the result is:
sol=[0.997107074864516, 0.9942080214735094, 0.9884131718553784, 0.9768835748661846, 0.954143705394098, 0.910067297297918, 0.8275510138614142, 0.6833931486612853, 0.4636505565068948, 0.20554769008446425, 0.0, 0.009899135523990096, 0.0]
Is this expected?
{quote}
No! The code must pass this test with high probability.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13463628#comment-13463628 ]
Gilles commented on MATH-867:
-----------------------------
bq. That they are mixed in the code/interface I would indeed consider as a bug.
Is this "bug" in the original code?
bq. Generally, the boundary handling can be done without any variable transformation [...]
But isn't this variable transformation part of the original code? At least, that's how it looked like from my perspective since [~docdwo] contributed the port while in contact with you.
Do you mean that the "encode" and "decode" steps can be simply dropped from the code without any ill side-effects?
Another issue (MATH-868) also seems related to the default transformation.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Nikolaus Hansen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466238#comment-13466238 ]
Nikolaus Hansen commented on MATH-867:
--------------------------------------
This issue's bug is not solved by v1 alone. The way how to check the boundaries in isFeasible and the method repair must be adapted to the encode/decode function, otherwise a more severe bug has been introduced (even if it would pass all tests). I agree that v1, along with corrected boundary checks, can solve the issue. However v2 makes the remaining modifications simpler.
Besides, the testConstrainedRosen must not fail, definitely not!
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Nikolaus Hansen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466253#comment-13466253 ]
Nikolaus Hansen commented on MATH-867:
--------------------------------------
just another motivation: inputSigma is related to the uncertainty on getStartPoint(), as we cannot intrinsically know whether this is in the order of 1 or 1e-4 or 1e4 or 10e23.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Comment Edited] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Nikolaus Hansen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13461891#comment-13461891 ]
Nikolaus Hansen edited comment on MATH-867 at 9/25/12 3:53 AM:
---------------------------------------------------------------
It seems important to point out that a parameter transformation or scaling and variable boundaries are two different things. That they are mixed in the code/interface I would indeed consider as a bug. Generally, the boundary handling can be done without any variable transformation and therefore does not need to effect precision.
If we want positive variable values only, the code should IMHO support only applying a lower bound in some way.
Maybe it is still important to mention: a relevant initial parameter to CMA-ES is an initial step-size (a standard deviation) possibly in each coordinate. You might think of this step-size as similar to the width of the initial simplex in Nelder&Mead. Choosing this step-size is equivalent to choosing a different "diff"-factor in the encoding as suggested above.
was (Author: jolievie):
It seems important to point out that a parameter transformation or scaling and variable boundaries are two different things. That they are mixed in the code/interface I would indeed consider as a bug. Generally, the boundary handling can be done without any variable transformation and therefore does not need to effect precision.
If we want positive variable values only, the code should support only applying a lower bound in some way.
My suggestion would be indeed to have as interface boundaries and a unit-scale for each parameter (by default one). Only the latter would control the "encoding", in the way suggested above as "diff".
Maybe it is still important to mention: a relevant initial parameter to CMA-ES is an initial step-size (a standard deviation) related to the unit-scale, which seem to be hidden from the user as it is now. You might think of this step-size as similar to the width of the initial simplex in Nelder&Mead.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Resolved] (MATH-867) CMAESOptimizer with bounds fits finely
near lower bound and coarsely near upper bound.
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Gilles resolved MATH-867.
-------------------------
Resolution: Fixed
Fix Version/s: 3.1
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Fix For: 3.1
>
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466243#comment-13466243 ]
Gilles commented on MATH-867:
-----------------------------
bq. This issue's bug is not solved by v1 alone. The way how to check the boundaries in isFeasible and the method repair must be adapted to the encode/decode function, otherwise a more severe bug has been introduced (even if it would pass all tests).
This was assumed; I only copied the "decode" function here, but the rest was changed accordingly, and the result is as I described (and the same as obtained by Frank, see above).
bq. However v2 makes the remaining modifications simpler.
The problem is that we don't know what are "the remaining modifications": we never got beyond to the point were both "testFitAccuracyDependsOnBoundary" and "testConstrainedRosen" pass.
bq. But we need to possibly take into account the boundaries within CMAES, if the returned solution is supposed to be in the bounds.
There are two different things:
1. Does the existence of constraints modify the search procedure is some way (i.e. CMAES must "know" that it deals with boundaries)?
2. Alternately, is it possible to pass a modified objective function (in which the allowed range of the original objective function has been mapped to the [-inf, +inf] interval) and have CMAES behave the same (i.e. find the same solution)?
In the second alternative, CM has adapter classes (e.g. "MultivariateFunctionPenaltyAdapter") that handle the mapping (and re-implementing it within each optimizer is an unnecessary source of bugs).
bq. regarding the documentation of inputSigma: I don't see in what sense the doc says that it depends on the bounds.
Then what is "initial search volume"?
I interpret the doc as roughly saying "0.3 times the range". Perhaps this is wrong, in which case it should be made clearer...
We noticed that very small or very large values for "sigma" did not work; so maybe we should say "inputSigma must be of order 1" (?).
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Nikolaus Hansen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13461853#comment-13461853 ]
Nikolaus Hansen commented on MATH-867:
--------------------------------------
I don't see anything wrong with the new version (the original version better facilitates the display of the evolution of variables in a single picture). It seems also clear where the original version fails: taking the difference in the above computation leads to a loss of significant digits if x[i] and boundaries[0][i] largely differ, that is, if the solution is far away from the lower bound.
However the use of boundaries for a range like [0, 5e16] seems not reasonable to me and it was not meant to be used like that. More specifically, I don't see a good reason to set an upper bound of 5e16, in particular when the initial point is 1. I would expect a reasonable initial point to lie roughly in the middle of the search interval. If the variable is supposed to be as large as 5e16, it is likely advisable to apply a non-linear transformation, e.g. to optimization its logarithm. More general, when searching in an interval of size 1e16 using double precision, one can, in principle, hardly expect to get a solution with a precision better than, say, 10 in which case one has identified the optimum with 15 digits of precision.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Comment Edited] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Frank Hess (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13461878#comment-13461878 ]
Frank Hess edited comment on MATH-867 at 9/25/12 3:09 AM:
----------------------------------------------------------
To elaborate on my previous point, the CMAESOptimizer also doesn't allow mixing of bounded and unbounded parameters. So, if I only want to apply a bound to one parameter of a multi-parameter fit, then the best I can do is set the bounds of the "unbounded" parameters to be [-VeryLargeValue, +VeryLargeValue]. This causes the fit precision around zero for the "unbounded" parameters to be much worse than when no bounds are specified at all.
was (Author: fhess):
To elaborate on my previous point, the CMAESOptimizer also doesn't allow mixing of bounded and unbounded parameters. So, if I only want to apply a bound to one parameter of a multi-parameter fit, then the best I can do is set the bounds of the "unbounded" parameters to be [-VeryLargeValue, +VeryLargeValue]. This causes the fit precision around zero for the "unbounded" to be much worse than when no bounds are specified at all.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Nikolaus Hansen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13467764#comment-13467764 ]
Nikolaus Hansen commented on MATH-867:
--------------------------------------
{quote}
And I have no idea how to improve the documentation...
{quote}
Here are my suggestions: Replace (several times)
{code}
* @param inputSigma Initial search volume; sigma of offspring objective variables.
{code}
with
{code}
* @param inputSigma Initial standard deviations to sample new points from startPoint
{code}
and
{code}
/**
* Individual sigma values - initial search volume. inputSigma determines
* the initial coordinate wise standard deviations for the search. Setting
* SIGMA one third of the initial search region is appropriate.
*/
{code}
with
{code}
/**
* Values in inputSigma define the initial coordinate-wise
* standard deviations for sampling new search points about
* startPoint.
* Setting inputSigma roughly to the predicted distance of
* startPoint to the actually desired optimum is appropriate.
* Small values for inputSigma induce the search to be more local
* and very small values are more likely to find a local optimum
* close to startPoint.
* Extremely small values will however lead to early termination.
*/
{code}
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Fix For: 3.1
>
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Frank Hess (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466811#comment-13466811 ]
Frank Hess commented on MATH-867:
---------------------------------
I looked at the commits, and ran the tests locally. FWIW, everything looks fine to me now.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Comment Edited] (MATH-867) CMAESOptimizer with bounds fits
finely near lower bound and coarsely near upper bound.
Posted by "Nikolaus Hansen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13466246#comment-13466246 ]
Nikolaus Hansen edited comment on MATH-867 at 9/30/12 2:32 AM:
---------------------------------------------------------------
{quote}
However v2 makes the remaining modifications simpler.
The problem is that we don't know what are "the remaining modifications":
{quote}
I thought I knew...
{quote}we never got beyond to the point were both "testFitAccuracyDependsOnBoundary" and "testConstrainedRosen" pass.
{quote}
the former, because inputSigma was not adapted appropriately, the latter because the test against boundaries was not adapted appropriately.
{quote}
There are two different things:
1. Does the existence of constraints modify the search procedure is some way (i.e. CMAES must "know" that it deals with boundaries)?
{quote}
yes. Otherwise it will sample and evaluation points outside the boundaries.
{quote}
2. Alternately, is it possible to pass a modified objective function (in which the allowed range of the original objective function has been mapped to the [-inf, +inf] interval) and have CMAES behave the same (i.e. find the same solution)?
{quote}
probably not the same, but possibly reasonably well, unless the boundary is mapped to (or close to) inf, which is likely to lead to unexpected results, if the optimum is on (or close to) the boundary.
checking MultivariateFunctionPenaltyAdapter (which does not map the parameters, rather computes a penalty), the answer is likely to be no, if the optimal solution happens to be on (or very close to) the bound. The methods developed for CMA-ES should work much better in this case.
{quote}
regarding the documentation of inputSigma: I don't see in what sense the doc says that it depends on the bounds.
Then what is "initial search volume"?
{quote}
the volume/region where points are likely to be sampled in the beginning of the search. Points beyond, say, startpoint + 10*sigma are not likely to be sampled in the beginning.
{quote}
I interpret the doc as roughly saying "0.3 times the range". Perhaps this is wrong, in which case it should be made clearer...
{quote}
I agree, it is not clear (I guess it was taken from another doc and slightly changed context).
{quote}
We noticed that very small or very large values for "sigma" did not work; so maybe we should say "inputSigma must be of order 1" .
{quote}
no, it entirely depends on how far we expect the optimal solution to be from the start solution. Putting it differently: one could rescale parameters by a factor 1000 (say in one case it is km, in the other m), then one would need to rescale inputSigma accordingly (which would not be in the order of one).
Codes I write typically don't accept a default value for inputSigma, basically for this reason. I agree however that a value of 1 might often turn out OK.
was (Author: jolievie):
{quote}
However v2 makes the remaining modifications simpler.
The problem is that we don't know what are "the remaining modifications":
{quote}
I thought I knew...
{quote}we never got beyond to the point were both "testFitAccuracyDependsOnBoundary" and "testConstrainedRosen" pass.
{quote}
the former, because inputSigma was not adapted appropriately, the latter because the test against boundaries was not adapted appropriately.
{quote}
There are two different things:
1. Does the existence of constraints modify the search procedure is some way (i.e. CMAES must "know" that it deals with boundaries)?
{quote}
yes. Otherwise it will sample and evaluation points outside the boundaries.
{quote}
2. Alternately, is it possible to pass a modified objective function (in which the allowed range of the original objective function has been mapped to the [-inf, +inf] interval) and have CMAES behave the same (i.e. find the same solution)?
{quote}
probably not the same, but possibly reasonably well, unless the boundary is mapped to (or close to) inf, which is likely to lead to unexpected results, if the optimum is on (or close to) the boundary.
checking MultivariateFunctionPenaltyAdapter (which does not map the parameters, rather computes a penalty), the answer is likely to be no, if the optimal solution happens to be on (or very close to) the bound.
{quote}
regarding the documentation of inputSigma: I don't see in what sense the doc says that it depends on the bounds.
Then what is "initial search volume"?
{quote}
the volume/region where points are likely to be sampled in the beginning of the search. Points beyond, say, startpoint + 10*sigma are not likely to be sampled in the beginning.
{quote}
I interpret the doc as roughly saying "0.3 times the range". Perhaps this is wrong, in which case it should be made clearer...
{quote}
I agree, it is not clear (I guess it was taken from another doc and slightly changed context).
{quote}
We noticed that very small or very large values for "sigma" did not work; so maybe we should say "inputSigma must be of order 1" .
{quote}
no, it entirely depends on how far we expect the optimal solution to be from the start solution. Putting it differently: one could rescale parameters by a factor 1000 (say in one case it is km, in the other m), then one would need to rescale inputSigma accordingly (which would not be in the order of one).
Codes I write typically don't accept a default value for inputSigma, basically for this reason. I agree however that a value of 1 might often turn out OK.
> CMAESOptimizer with bounds fits finely near lower bound and coarsely near upper bound.
> ---------------------------------------------------------------------------------------
>
> Key: MATH-867
> URL: https://issues.apache.org/jira/browse/MATH-867
> Project: Commons Math
> Issue Type: Bug
> Reporter: Frank Hess
> Attachments: MATH867_patch, Math867Test.java
>
>
> When fitting with bounds, the CMAESOptimizer fits finely near the lower bound and coarsely near the upper bound. This is because it internally maps the fitted parameter range into the interval [0,1]. The unit of least precision (ulp) between floating point numbers is much smaller near zero than near one. Thus, fits have much better resolution near the lower bound (which is mapped to zero) than the upper bound (which is mapped to one). I will attach a example program to demonstrate.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira