[jira] [Created] (MATH-785) Numerical Underflow in ContinuedFraction

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

[jira] [Created] (MATH-785) Numerical Underflow in ContinuedFraction

ASF GitHub Bot (Jira)
Colin J. Fuller created MATH-785:
------------------------------------

             Summary: Numerical Underflow in ContinuedFraction
                 Key: MATH-785
                 URL: https://issues.apache.org/jira/browse/MATH-785
             Project: Commons Math
          Issue Type: Bug
    Affects Versions: 3.0
         Environment: Issue seen in both 3.0 release binary version as well as a fresh checkout of the subversion trunk.

java -version output:

java version "1.6.0_26"
Java(TM) SE Runtime Environment (build 1.6.0_26-b03)
Java HotSpot(TM) 64-Bit Server VM (build 20.1-b02, mixed mode)

(On Ubuntu 12.04)





            Reporter: Colin J. Fuller


The ContinuedFraction calculation can underflow in the evaluate method, similar to the overflow case already dealt with.  I encountered this problem while trying to evaluate the inverse cumulative probability of an F distribution with a large number of degrees of freedom.

I would guess this has the same cause as MATH-718 and MATH-738, though I am not experiencing inaccurate results but rather an exception.

For instance, the following test case fails:

double prob = 0.01;
FDistribution f = new FDistribution(200000, 200000);
double fails = f.inverseCumulativeProbability(prob);

This produces a NoBracketingException with the following stack trace:

org.apache.commons.math3.exception.NoBracketingException: function values at endpoints do not have different signs, endpoints: [0, 1], values: [-0.01, -∞]
        at org.apache.commons.math3.analysis.solvers.BrentSolver.doSolve(BrentSolver.java:118)
        at org.apache.commons.math3.analysis.solvers.BaseAbstractUnivariateSolver.solve(BaseAbstractUnivariateSolver.java:190)
        at org.apache.commons.math3.analysis.solvers.BaseAbstractUnivariateSolver.solve(BaseAbstractUnivariateSolver.java:195)
        at org.apache.commons.math3.analysis.solvers.UnivariateSolverUtils.solve(UnivariateSolverUtils.java:77)
        at org.apache.commons.math3.distribution.AbstractRealDistribution.inverseCumulativeProbability(AbstractRealDistribution.java:156)

I could avoid the issue as in the comment to MATH-718 by relaxing the default value of epsilon in ContinuedFraction, although in my test case I can't see any reason the current default precision shouldn't be attainable.

I fixed the issue by implementing underflow detection in ContinuedFraction and rescaling to larger values similarly to how the overflow detection that is already there works.  I will attach a patch shortly.

One possible issue with this fix is that if there exists a case where there is a legitimate reason for p2 or q2 to be zero (I cannot think of one), it might break that case.

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira


Reply | Threaded
Open this post in threaded view
|

[jira] [Updated] (MATH-785) Numerical Underflow in ContinuedFraction

ASF GitHub Bot (Jira)

     [ https://issues.apache.org/jira/browse/MATH-785?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Colin J. Fuller updated MATH-785:
---------------------------------

    Attachment: patch.txt

Patch to fix the numerical underflow problem in ContinuedFraction.
               

> Numerical Underflow in ContinuedFraction
> ----------------------------------------
>
>                 Key: MATH-785
>                 URL: https://issues.apache.org/jira/browse/MATH-785
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 3.0
>         Environment: Issue seen in both 3.0 release binary version as well as a fresh checkout of the subversion trunk.
> java -version output:
> java version "1.6.0_26"
> Java(TM) SE Runtime Environment (build 1.6.0_26-b03)
> Java HotSpot(TM) 64-Bit Server VM (build 20.1-b02, mixed mode)
> (On Ubuntu 12.04)
>            Reporter: Colin J. Fuller
>         Attachments: patch.txt
>
>
> The ContinuedFraction calculation can underflow in the evaluate method, similar to the overflow case already dealt with.  I encountered this problem while trying to evaluate the inverse cumulative probability of an F distribution with a large number of degrees of freedom.
> I would guess this has the same cause as MATH-718 and MATH-738, though I am not experiencing inaccurate results but rather an exception.
> For instance, the following test case fails:
> double prob = 0.01;
> FDistribution f = new FDistribution(200000, 200000);
> double fails = f.inverseCumulativeProbability(prob);
> This produces a NoBracketingException with the following stack trace:
> org.apache.commons.math3.exception.NoBracketingException: function values at endpoints do not have different signs, endpoints: [0, 1], values: [-0.01, -∞]
> at org.apache.commons.math3.analysis.solvers.BrentSolver.doSolve(BrentSolver.java:118)
> at org.apache.commons.math3.analysis.solvers.BaseAbstractUnivariateSolver.solve(BaseAbstractUnivariateSolver.java:190)
> at org.apache.commons.math3.analysis.solvers.BaseAbstractUnivariateSolver.solve(BaseAbstractUnivariateSolver.java:195)
> at org.apache.commons.math3.analysis.solvers.UnivariateSolverUtils.solve(UnivariateSolverUtils.java:77)
> at org.apache.commons.math3.distribution.AbstractRealDistribution.inverseCumulativeProbability(AbstractRealDistribution.java:156)
> I could avoid the issue as in the comment to MATH-718 by relaxing the default value of epsilon in ContinuedFraction, although in my test case I can't see any reason the current default precision shouldn't be attainable.
> I fixed the issue by implementing underflow detection in ContinuedFraction and rescaling to larger values similarly to how the overflow detection that is already there works.  I will attach a patch shortly.
> One possible issue with this fix is that if there exists a case where there is a legitimate reason for p2 or q2 to be zero (I cannot think of one), it might break that case.

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira


Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-785) Numerical Underflow in ContinuedFraction

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ https://issues.apache.org/jira/browse/MATH-785?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13272797#comment-13272797 ]

Thomas Neidhart commented on MATH-785:
--------------------------------------

I have looked into this patch, and it looks very reasonable.

My original experiments with the epsilon were just scraping on the symptom but this seems to deal with the actual cause of the numerical instability problems.

Results of distributions using this fix also greatly improved to the situation before.
               

> Numerical Underflow in ContinuedFraction
> ----------------------------------------
>
>                 Key: MATH-785
>                 URL: https://issues.apache.org/jira/browse/MATH-785
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 3.0
>         Environment: Issue seen in both 3.0 release binary version as well as a fresh checkout of the subversion trunk.
> java -version output:
> java version "1.6.0_26"
> Java(TM) SE Runtime Environment (build 1.6.0_26-b03)
> Java HotSpot(TM) 64-Bit Server VM (build 20.1-b02, mixed mode)
> (On Ubuntu 12.04)
>            Reporter: Colin J. Fuller
>         Attachments: patch.txt
>
>
> The ContinuedFraction calculation can underflow in the evaluate method, similar to the overflow case already dealt with.  I encountered this problem while trying to evaluate the inverse cumulative probability of an F distribution with a large number of degrees of freedom.
> I would guess this has the same cause as MATH-718 and MATH-738, though I am not experiencing inaccurate results but rather an exception.
> For instance, the following test case fails:
> double prob = 0.01;
> FDistribution f = new FDistribution(200000, 200000);
> double fails = f.inverseCumulativeProbability(prob);
> This produces a NoBracketingException with the following stack trace:
> org.apache.commons.math3.exception.NoBracketingException: function values at endpoints do not have different signs, endpoints: [0, 1], values: [-0.01, -∞]
> at org.apache.commons.math3.analysis.solvers.BrentSolver.doSolve(BrentSolver.java:118)
> at org.apache.commons.math3.analysis.solvers.BaseAbstractUnivariateSolver.solve(BaseAbstractUnivariateSolver.java:190)
> at org.apache.commons.math3.analysis.solvers.BaseAbstractUnivariateSolver.solve(BaseAbstractUnivariateSolver.java:195)
> at org.apache.commons.math3.analysis.solvers.UnivariateSolverUtils.solve(UnivariateSolverUtils.java:77)
> at org.apache.commons.math3.distribution.AbstractRealDistribution.inverseCumulativeProbability(AbstractRealDistribution.java:156)
> I could avoid the issue as in the comment to MATH-718 by relaxing the default value of epsilon in ContinuedFraction, although in my test case I can't see any reason the current default precision shouldn't be attainable.
> I fixed the issue by implementing underflow detection in ContinuedFraction and rescaling to larger values similarly to how the overflow detection that is already there works.  I will attach a patch shortly.
> One possible issue with this fix is that if there exists a case where there is a legitimate reason for p2 or q2 to be zero (I cannot think of one), it might break that case.

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira


Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-785) Numerical Underflow in ContinuedFraction

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ https://issues.apache.org/jira/browse/MATH-785?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13279874#comment-13279874 ]

Thomas Neidhart commented on MATH-785:
--------------------------------------

I looked further into it and am not convinced anymore that this really to solve the numerical stability problems. In fact the results are pretty much random depending on the choice of the scaling factor.

In fact I implemented the modified Lentz-Thompson algorithm to do the continued fraction evaluation and the results are much much better. All the unit tests run through and the probability evaluations for the different distributions for large trials are stable and return correct values.
               

> Numerical Underflow in ContinuedFraction
> ----------------------------------------
>
>                 Key: MATH-785
>                 URL: https://issues.apache.org/jira/browse/MATH-785
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 3.0
>         Environment: Issue seen in both 3.0 release binary version as well as a fresh checkout of the subversion trunk.
> java -version output:
> java version "1.6.0_26"
> Java(TM) SE Runtime Environment (build 1.6.0_26-b03)
> Java HotSpot(TM) 64-Bit Server VM (build 20.1-b02, mixed mode)
> (On Ubuntu 12.04)
>            Reporter: Colin J. Fuller
>         Attachments: patch.txt
>
>
> The ContinuedFraction calculation can underflow in the evaluate method, similar to the overflow case already dealt with.  I encountered this problem while trying to evaluate the inverse cumulative probability of an F distribution with a large number of degrees of freedom.
> I would guess this has the same cause as MATH-718 and MATH-738, though I am not experiencing inaccurate results but rather an exception.
> For instance, the following test case fails:
> double prob = 0.01;
> FDistribution f = new FDistribution(200000, 200000);
> double fails = f.inverseCumulativeProbability(prob);
> This produces a NoBracketingException with the following stack trace:
> org.apache.commons.math3.exception.NoBracketingException: function values at endpoints do not have different signs, endpoints: [0, 1], values: [-0.01, -∞]
> at org.apache.commons.math3.analysis.solvers.BrentSolver.doSolve(BrentSolver.java:118)
> at org.apache.commons.math3.analysis.solvers.BaseAbstractUnivariateSolver.solve(BaseAbstractUnivariateSolver.java:190)
> at org.apache.commons.math3.analysis.solvers.BaseAbstractUnivariateSolver.solve(BaseAbstractUnivariateSolver.java:195)
> at org.apache.commons.math3.analysis.solvers.UnivariateSolverUtils.solve(UnivariateSolverUtils.java:77)
> at org.apache.commons.math3.distribution.AbstractRealDistribution.inverseCumulativeProbability(AbstractRealDistribution.java:156)
> I could avoid the issue as in the comment to MATH-718 by relaxing the default value of epsilon in ContinuedFraction, although in my test case I can't see any reason the current default precision shouldn't be attainable.
> I fixed the issue by implementing underflow detection in ContinuedFraction and rescaling to larger values similarly to how the overflow detection that is already there works.  I will attach a patch shortly.
> One possible issue with this fix is that if there exists a case where there is a legitimate reason for p2 or q2 to be zero (I cannot think of one), it might break that case.

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira


Reply | Threaded
Open this post in threaded view
|

[jira] [Resolved] (MATH-785) Numerical Underflow in ContinuedFraction

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

     [ https://issues.apache.org/jira/browse/MATH-785?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Thomas Neidhart resolved MATH-785.
----------------------------------

       Resolution: Fixed
    Fix Version/s: 3.1

The problem has fixed together with MATH-718. Instead of applying the attached patch, the evaluation of the continued fraction has been changed to the modified Lentz-Thompson algorithm which does not suffer from underflow/overflow problems as the original implementation. A test case for the described problem has been added too.

Thanks for the report.
               

> Numerical Underflow in ContinuedFraction
> ----------------------------------------
>
>                 Key: MATH-785
>                 URL: https://issues.apache.org/jira/browse/MATH-785
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 3.0
>         Environment: Issue seen in both 3.0 release binary version as well as a fresh checkout of the subversion trunk.
> java -version output:
> java version "1.6.0_26"
> Java(TM) SE Runtime Environment (build 1.6.0_26-b03)
> Java HotSpot(TM) 64-Bit Server VM (build 20.1-b02, mixed mode)
> (On Ubuntu 12.04)
>            Reporter: Colin J. Fuller
>             Fix For: 3.1
>
>         Attachments: patch.txt
>
>
> The ContinuedFraction calculation can underflow in the evaluate method, similar to the overflow case already dealt with.  I encountered this problem while trying to evaluate the inverse cumulative probability of an F distribution with a large number of degrees of freedom.
> I would guess this has the same cause as MATH-718 and MATH-738, though I am not experiencing inaccurate results but rather an exception.
> For instance, the following test case fails:
> double prob = 0.01;
> FDistribution f = new FDistribution(200000, 200000);
> double fails = f.inverseCumulativeProbability(prob);
> This produces a NoBracketingException with the following stack trace:
> org.apache.commons.math3.exception.NoBracketingException: function values at endpoints do not have different signs, endpoints: [0, 1], values: [-0.01, -∞]
> at org.apache.commons.math3.analysis.solvers.BrentSolver.doSolve(BrentSolver.java:118)
> at org.apache.commons.math3.analysis.solvers.BaseAbstractUnivariateSolver.solve(BaseAbstractUnivariateSolver.java:190)
> at org.apache.commons.math3.analysis.solvers.BaseAbstractUnivariateSolver.solve(BaseAbstractUnivariateSolver.java:195)
> at org.apache.commons.math3.analysis.solvers.UnivariateSolverUtils.solve(UnivariateSolverUtils.java:77)
> at org.apache.commons.math3.distribution.AbstractRealDistribution.inverseCumulativeProbability(AbstractRealDistribution.java:156)
> I could avoid the issue as in the comment to MATH-718 by relaxing the default value of epsilon in ContinuedFraction, although in my test case I can't see any reason the current default precision shouldn't be attainable.
> I fixed the issue by implementing underflow detection in ContinuedFraction and rescaling to larger values similarly to how the overflow detection that is already there works.  I will attach a patch shortly.
> One possible issue with this fix is that if there exists a case where there is a legitimate reason for p2 or q2 to be zero (I cannot think of one), it might break that case.

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira