You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by lu...@free.fr on 2009/07/07 11:44:48 UTC
Re: svn commit: r791766 - in /commons/proper/math/trunk/src:
java/org/apache/commons/math/analysis/solvers/
java/org/apache/commons/math/distribution/ site/xdoc/
test/org/apache/commons/math/analysis/solvers/
test/org/apache/commons/math/distribution/
The following commit solved MATH-280. Here are some explanations about the change.
The issue was triggerred by a bracketing attempt in AbstractContinuousDistribution.bracket. This bracketing attempt starts from an initial value (here it was exactly 1.0 since it was mean + standard deviation and we were working on a normalized gaussian). From this initial value, it increases an interval by moving both a lower bound and an upper bound by steps of 1.0, so the intervals used are [0.0, 2.0], [-1.0, 3.0], [-2.0, 4.0] ... In fact, at the first iteration the upper bound (2.0) is exactly the root of the function, so f(b)=0 and the loop ends due to criteria f(a)*f(b) > 0. However the following check was f(a)*f(b) >= 0 and an exception was triggered.
In fact, there was already a protection against exact solutions in the AbstractContinuousDistribution.inverseCumulativeProbability method. The exception thrown by the bracket method was caught and the domain endpoint were checked to see if they are a solution to the
inverse cumulative computation problem. Here, is was not the case because the solution was an intermediate point (2.0), and the endpoints were 0.0 and Double.MAX_VALUE. So the exception was rethrown ...
The solution I used was to have consistent tests in the bracket method: both now use f(a)*f(b) > 0 and the correct result is returned.
This however have changed the behaviour of the bracket method: it doesn't throw an exception anymore when an exact root is encountered. This seemed a logical choice as there was already some defensive code in the upper level methods and I think we have fixed the solvers one year ago to find root exactly at endpoints (see MATH-204). This behaviour was used in a test case (testBracketCornerSolution). I have removed this test but feel uncomfortable with this choice.
Could someone either acknowledge this choice or propose another fix for the problem ?
thanks,
Luc
----- luc@apache.org a écrit :
> Author: luc
> Date: Tue Jul 7 09:19:46 2009
> New Revision: 791766
>
> URL: http://svn.apache.org/viewvc?rev=791766&view=rev
> Log:
> fixed a bracketing issue due to inconsistent checks
> JIRA: MATH-280
>
> Modified:
>
> commons/proper/math/trunk/src/java/org/apache/commons/math/analysis/solvers/UnivariateRealSolverUtils.java
>
> commons/proper/math/trunk/src/java/org/apache/commons/math/distribution/AbstractContinuousDistribution.java
> commons/proper/math/trunk/src/site/xdoc/changes.xml
>
> commons/proper/math/trunk/src/test/org/apache/commons/math/analysis/solvers/UnivariateRealSolverUtilsTest.java
>
> commons/proper/math/trunk/src/test/org/apache/commons/math/distribution/NormalDistributionTest.java
>
> Modified:
> commons/proper/math/trunk/src/java/org/apache/commons/math/analysis/solvers/UnivariateRealSolverUtils.java
> URL:
> http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/analysis/solvers/UnivariateRealSolverUtils.java?rev=791766&r1=791765&r2=791766&view=diff
> ==============================================================================
> ---
> commons/proper/math/trunk/src/java/org/apache/commons/math/analysis/solvers/UnivariateRealSolverUtils.java
> (original)
> +++
> commons/proper/math/trunk/src/java/org/apache/commons/math/analysis/solvers/UnivariateRealSolverUtils.java
> Tue Jul 7 09:19:46 2009
> @@ -131,7 +131,7 @@
> /**
> * This method attempts to find two values a and b satisfying
> <ul>
> * <li> <code> lowerBound <= a < initial < b <= upperBound</code>
> </li>
> - * <li> <code> f(a) * f(b) < 0 </code> </li>
> + * <li> <code> f(a) * f(b) <= 0 </code> </li>
> * </ul>
> * If f is continuous on <code>[a,b],</code> this means that
> <code>a</code>
> * and <code>b</code> bracket a root of f.
> @@ -141,7 +141,7 @@
> * function at <code>a</code> and <code>b</code> and keeps
> moving
> * the endpoints out by one unit each time through a loop that
> terminates
> * when one of the following happens: <ul>
> - * <li> <code> f(a) * f(b) < 0 </code> -- success!</li>
> + * <li> <code> f(a) * f(b) <= 0 </code> -- success!</li>
> * <li> <code> a = lower </code> and <code> b = upper</code>
> * -- ConvergenceException </li>
> * <li> <code> maximumIterations</code> iterations elapse
> @@ -195,7 +195,7 @@
> } while ((fa * fb > 0.0) && (numIterations <
> maximumIterations) &&
> ((a > lowerBound) || (b < upperBound)));
>
> - if (fa * fb >= 0.0 ) {
> + if (fa * fb > 0.0 ) {
> throw new ConvergenceException(
> "number of iterations={0}, maximum
> iterations={1}, " +
> "initial={2}, lower bound={3}, upper bound={4},
> final a value={5}, " +
>
> Modified:
> commons/proper/math/trunk/src/java/org/apache/commons/math/distribution/AbstractContinuousDistribution.java
> URL:
> http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/distribution/AbstractContinuousDistribution.java?rev=791766&r1=791765&r2=791766&view=diff
> ==============================================================================
> ---
> commons/proper/math/trunk/src/java/org/apache/commons/math/distribution/AbstractContinuousDistribution.java
> (original)
> +++
> commons/proper/math/trunk/src/java/org/apache/commons/math/distribution/AbstractContinuousDistribution.java
> Tue Jul 7 09:19:46 2009
> @@ -65,7 +65,7 @@
> }
>
> // by default, do simple root finding using bracketing and
> default solver.
> - // subclasses can overide if there is a better method.
> + // subclasses can override if there is a better method.
> UnivariateRealFunction rootFindingFunction =
> new UnivariateRealFunction() {
> public double value(double x) throws
> FunctionEvaluationException {
>
> Modified: commons/proper/math/trunk/src/site/xdoc/changes.xml
> URL:
> http://svn.apache.org/viewvc/commons/proper/math/trunk/src/site/xdoc/changes.xml?rev=791766&r1=791765&r2=791766&view=diff
> ==============================================================================
> --- commons/proper/math/trunk/src/site/xdoc/changes.xml (original)
> +++ commons/proper/math/trunk/src/site/xdoc/changes.xml Tue Jul 7
> 09:19:46 2009
> @@ -39,6 +39,9 @@
> </properties>
> <body>
> <release version="2.0" date="TBD" description="TBD">
> + <action dev="luc" type="fix" issue="MATH-280">
> + Fixed a bracketing issue in inverse cumulative probability
> computation
> + </action>
> <action dev="luc" type="add" issue="MATH-279" due-to="Michael
> Bjorkegren">
> Added a check for too few rows with respect to the number of
> predictors in linear regression
> </action>
>
> Modified:
> commons/proper/math/trunk/src/test/org/apache/commons/math/analysis/solvers/UnivariateRealSolverUtilsTest.java
> URL:
> http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/analysis/solvers/UnivariateRealSolverUtilsTest.java?rev=791766&r1=791765&r2=791766&view=diff
> ==============================================================================
> ---
> commons/proper/math/trunk/src/test/org/apache/commons/math/analysis/solvers/UnivariateRealSolverUtilsTest.java
> (original)
> +++
> commons/proper/math/trunk/src/test/org/apache/commons/math/analysis/solvers/UnivariateRealSolverUtilsTest.java
> Tue Jul 7 09:19:46 2009
> @@ -17,13 +17,12 @@
>
> package org.apache.commons.math.analysis.solvers;
>
> -import org.apache.commons.math.ConvergenceException;
> +import junit.framework.TestCase;
> +
> import org.apache.commons.math.MathException;
> import org.apache.commons.math.analysis.SinFunction;
> import org.apache.commons.math.analysis.UnivariateRealFunction;
>
> -import junit.framework.TestCase;
> -
> /**
> * @version $Revision$ $Date$
> */
> @@ -91,15 +90,6 @@
> assertTrue(sin.value(result[1]) > 0);
> }
>
> - public void testBracketCornerSolution() throws MathException {
> - try {
> - UnivariateRealSolverUtils.bracket(sin, 1.5, 0, 2.0);
> - fail("Expecting ConvergenceException");
> - } catch (ConvergenceException ex) {
> - // expected
> - }
> - }
> -
> public void testBadParameters() throws MathException {
> try { // null function
> UnivariateRealSolverUtils.bracket(null, 1.5, 0, 2.0);
>
> Modified:
> commons/proper/math/trunk/src/test/org/apache/commons/math/distribution/NormalDistributionTest.java
> URL:
> http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/distribution/NormalDistributionTest.java?rev=791766&r1=791765&r2=791766&view=diff
> ==============================================================================
> ---
> commons/proper/math/trunk/src/test/org/apache/commons/math/distribution/NormalDistributionTest.java
> (original)
> +++
> commons/proper/math/trunk/src/test/org/apache/commons/math/distribution/NormalDistributionTest.java
> Tue Jul 7 09:19:46 2009
> @@ -17,6 +17,8 @@
>
> package org.apache.commons.math.distribution;
>
> +import org.apache.commons.math.MathException;
> +
> /**
> * Test cases for NormalDistribution.
> * Extends ContinuousDistributionAbstractTest. See class javadoc
> for
> @@ -161,4 +163,11 @@
> }
> }
> }
> +
> + public void testMath280() throws MathException {
> + NormalDistribution normal = new NormalDistributionImpl(0,1);
> + double result =
> normal.inverseCumulativeProbability(0.9772498680518209);
> + assertEquals(2.0, result, 1.0e-12);
> + }
> +
> }
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: svn commit: r791766 - in /commons/proper/math/trunk/src: java/org/apache/commons/math/analysis/solvers/
java/org/apache/commons/math/distribution/ site/xdoc/ test/org/apache/commons/math/analysis/solvers/
test/org/apache/commons/math/distribution/
Posted by Phil Steitz <ph...@gmail.com>.
luc.maisonobe@free.fr wrote:
> The following commit solved MATH-280. Here are some explanations about the change.
>
> The issue was triggerred by a bracketing attempt in AbstractContinuousDistribution.bracket. This bracketing attempt starts from an initial value (here it was exactly 1.0 since it was mean + standard deviation and we were working on a normalized gaussian). From this initial value, it increases an interval by moving both a lower bound and an upper bound by steps of 1.0, so the intervals used are [0.0, 2.0], [-1.0, 3.0], [-2.0, 4.0] ... In fact, at the first iteration the upper bound (2.0) is exactly the root of the function, so f(b)=0 and the loop ends due to criteria f(a)*f(b) > 0. However the following check was f(a)*f(b) >= 0 and an exception was triggered.
>
> In fact, there was already a protection against exact solutions in the AbstractContinuousDistribution.inverseCumulativeProbability method. The exception thrown by the bracket method was caught and the domain endpoint were checked to see if they are a solution to the
> inverse cumulative computation problem. Here, is was not the case because the solution was an intermediate point (2.0), and the endpoints were 0.0 and Double.MAX_VALUE. So the exception was rethrown ...
>
Agree with your analysis. I was....slowly...coming to the same
conclusion ;)
> The solution I used was to have consistent tests in the bracket method: both now use f(a)*f(b) > 0 and the correct result is returned.
>
> This however have changed the behaviour of the bracket method: it doesn't throw an exception anymore when an exact root is encountered. This seemed a logical choice as there was already some defensive code in the upper level methods and I think we have fixed the solvers one year ago to find root exactly at endpoints (see MATH-204).
Looks like only Brent was fixed in MATH-204, but others are OK, except
for Secant, which we should probably fix.
> This behaviour was used in a test case (testBracketCornerSolution). I have removed this test but feel uncomfortable with this choice.
>
The contract of the method was changed - and documented - so removing
this test case is OK. Probably should replace it with a test confirming
success when a root is encountered.
> Could someone either acknowledge this choice or propose another fix for the problem ?
>
I am +1 on the changes. Since the release notes will be generated from
changes.xml, it is probably best to add some more commentary there on
the contract change for UnivariateSolverUtils.bracket. Since solvers
are pluggable in the inverse probability distribution computations, it
is probably also a good idea to make the following change to the
UnivariateRealSolver.solve javadoc:
s/A solver may require that the interval brackets a single zero root./A
solver may require that the interval brackets a single zero root.
Solvers that do require bracketing should be able to handle the case
where one of the endpoints is itself a root./
Phil
> thanks,
> Luc
>
> ----- luc@apache.org a écrit :
>
>
>> Author: luc
>> Date: Tue Jul 7 09:19:46 2009
>> New Revision: 791766
>>
>> URL: http://svn.apache.org/viewvc?rev=791766&view=rev
>> Log:
>> fixed a bracketing issue due to inconsistent checks
>> JIRA: MATH-280
>>
>> Modified:
>>
>> commons/proper/math/trunk/src/java/org/apache/commons/math/analysis/solvers/UnivariateRealSolverUtils.java
>>
>> commons/proper/math/trunk/src/java/org/apache/commons/math/distribution/AbstractContinuousDistribution.java
>> commons/proper/math/trunk/src/site/xdoc/changes.xml
>>
>> commons/proper/math/trunk/src/test/org/apache/commons/math/analysis/solvers/UnivariateRealSolverUtilsTest.java
>>
>> commons/proper/math/trunk/src/test/org/apache/commons/math/distribution/NormalDistributionTest.java
>>
>> Modified:
>> commons/proper/math/trunk/src/java/org/apache/commons/math/analysis/solvers/UnivariateRealSolverUtils.java
>> URL:
>> http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/analysis/solvers/UnivariateRealSolverUtils.java?rev=791766&r1=791765&r2=791766&view=diff
>> ==============================================================================
>> ---
>> commons/proper/math/trunk/src/java/org/apache/commons/math/analysis/solvers/UnivariateRealSolverUtils.java
>> (original)
>> +++
>> commons/proper/math/trunk/src/java/org/apache/commons/math/analysis/solvers/UnivariateRealSolverUtils.java
>> Tue Jul 7 09:19:46 2009
>> @@ -131,7 +131,7 @@
>> /**
>> * This method attempts to find two values a and b satisfying
>> <ul>
>> * <li> <code> lowerBound <= a < initial < b <= upperBound</code>
>> </li>
>> - * <li> <code> f(a) * f(b) < 0 </code> </li>
>> + * <li> <code> f(a) * f(b) <= 0 </code> </li>
>> * </ul>
>> * If f is continuous on <code>[a,b],</code> this means that
>> <code>a</code>
>> * and <code>b</code> bracket a root of f.
>> @@ -141,7 +141,7 @@
>> * function at <code>a</code> and <code>b</code> and keeps
>> moving
>> * the endpoints out by one unit each time through a loop that
>> terminates
>> * when one of the following happens: <ul>
>> - * <li> <code> f(a) * f(b) < 0 </code> -- success!</li>
>> + * <li> <code> f(a) * f(b) <= 0 </code> -- success!</li>
>> * <li> <code> a = lower </code> and <code> b = upper</code>
>> * -- ConvergenceException </li>
>> * <li> <code> maximumIterations</code> iterations elapse
>> @@ -195,7 +195,7 @@
>> } while ((fa * fb > 0.0) && (numIterations <
>> maximumIterations) &&
>> ((a > lowerBound) || (b < upperBound)));
>>
>> - if (fa * fb >= 0.0 ) {
>> + if (fa * fb > 0.0 ) {
>> throw new ConvergenceException(
>> "number of iterations={0}, maximum
>> iterations={1}, " +
>> "initial={2}, lower bound={3}, upper bound={4},
>> final a value={5}, " +
>>
>> Modified:
>> commons/proper/math/trunk/src/java/org/apache/commons/math/distribution/AbstractContinuousDistribution.java
>> URL:
>> http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/distribution/AbstractContinuousDistribution.java?rev=791766&r1=791765&r2=791766&view=diff
>> ==============================================================================
>> ---
>> commons/proper/math/trunk/src/java/org/apache/commons/math/distribution/AbstractContinuousDistribution.java
>> (original)
>> +++
>> commons/proper/math/trunk/src/java/org/apache/commons/math/distribution/AbstractContinuousDistribution.java
>> Tue Jul 7 09:19:46 2009
>> @@ -65,7 +65,7 @@
>> }
>>
>> // by default, do simple root finding using bracketing and
>> default solver.
>> - // subclasses can overide if there is a better method.
>> + // subclasses can override if there is a better method.
>> UnivariateRealFunction rootFindingFunction =
>> new UnivariateRealFunction() {
>> public double value(double x) throws
>> FunctionEvaluationException {
>>
>> Modified: commons/proper/math/trunk/src/site/xdoc/changes.xml
>> URL:
>> http://svn.apache.org/viewvc/commons/proper/math/trunk/src/site/xdoc/changes.xml?rev=791766&r1=791765&r2=791766&view=diff
>> ==============================================================================
>> --- commons/proper/math/trunk/src/site/xdoc/changes.xml (original)
>> +++ commons/proper/math/trunk/src/site/xdoc/changes.xml Tue Jul 7
>> 09:19:46 2009
>> @@ -39,6 +39,9 @@
>> </properties>
>> <body>
>> <release version="2.0" date="TBD" description="TBD">
>> + <action dev="luc" type="fix" issue="MATH-280">
>> + Fixed a bracketing issue in inverse cumulative probability
>> computation
>> + </action>
>> <action dev="luc" type="add" issue="MATH-279" due-to="Michael
>> Bjorkegren">
>> Added a check for too few rows with respect to the number of
>> predictors in linear regression
>> </action>
>>
>> Modified:
>> commons/proper/math/trunk/src/test/org/apache/commons/math/analysis/solvers/UnivariateRealSolverUtilsTest.java
>> URL:
>> http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/analysis/solvers/UnivariateRealSolverUtilsTest.java?rev=791766&r1=791765&r2=791766&view=diff
>> ==============================================================================
>> ---
>> commons/proper/math/trunk/src/test/org/apache/commons/math/analysis/solvers/UnivariateRealSolverUtilsTest.java
>> (original)
>> +++
>> commons/proper/math/trunk/src/test/org/apache/commons/math/analysis/solvers/UnivariateRealSolverUtilsTest.java
>> Tue Jul 7 09:19:46 2009
>> @@ -17,13 +17,12 @@
>>
>> package org.apache.commons.math.analysis.solvers;
>>
>> -import org.apache.commons.math.ConvergenceException;
>> +import junit.framework.TestCase;
>> +
>> import org.apache.commons.math.MathException;
>> import org.apache.commons.math.analysis.SinFunction;
>> import org.apache.commons.math.analysis.UnivariateRealFunction;
>>
>> -import junit.framework.TestCase;
>> -
>> /**
>> * @version $Revision$ $Date$
>> */
>> @@ -91,15 +90,6 @@
>> assertTrue(sin.value(result[1]) > 0);
>> }
>>
>> - public void testBracketCornerSolution() throws MathException {
>> - try {
>> - UnivariateRealSolverUtils.bracket(sin, 1.5, 0, 2.0);
>> - fail("Expecting ConvergenceException");
>> - } catch (ConvergenceException ex) {
>> - // expected
>> - }
>> - }
>> -
>> public void testBadParameters() throws MathException {
>> try { // null function
>> UnivariateRealSolverUtils.bracket(null, 1.5, 0, 2.0);
>>
>> Modified:
>> commons/proper/math/trunk/src/test/org/apache/commons/math/distribution/NormalDistributionTest.java
>> URL:
>> http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/distribution/NormalDistributionTest.java?rev=791766&r1=791765&r2=791766&view=diff
>> ==============================================================================
>> ---
>> commons/proper/math/trunk/src/test/org/apache/commons/math/distribution/NormalDistributionTest.java
>> (original)
>> +++
>> commons/proper/math/trunk/src/test/org/apache/commons/math/distribution/NormalDistributionTest.java
>> Tue Jul 7 09:19:46 2009
>> @@ -17,6 +17,8 @@
>>
>> package org.apache.commons.math.distribution;
>>
>> +import org.apache.commons.math.MathException;
>> +
>> /**
>> * Test cases for NormalDistribution.
>> * Extends ContinuousDistributionAbstractTest. See class javadoc
>> for
>> @@ -161,4 +163,11 @@
>> }
>> }
>> }
>> +
>> + public void testMath280() throws MathException {
>> + NormalDistribution normal = new NormalDistributionImpl(0,1);
>> + double result =
>> normal.inverseCumulativeProbability(0.9772498680518209);
>> + assertEquals(2.0, result, 1.0e-12);
>> + }
>> +
>> }
>>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org