scipy: ENH: Robust and fast numerical derivative for error propagation
Is your feature request related to a problem? Please describe.
I am a particle physicist by trade, and error propagation is very important for us. We need to propagate errors through complex functions that may execute arbitrary code and whose analytical behavior we do not understand in detail. Therefore, it is important to have a reliable and fast black-box derivative that just works and does not require expert knowledge about the function.
Describe the solution you’d like.
I wrote the jacobi library (docs) which I would like to include in scipy. Jacobi is an implementation of John d’Errico’s DERIVEST algorithm for matlab written from scratch. Jacobi has remarkable features that make it ideal for this use case. It is a fast, safe-to-use, black-box numerical derivative for many applications. I think it is a great match for a foundational scientific library like scipy. On top of the derivative, I wrote a function propagate which uses the derivative to do error propagation for any vector-valued function.
Jacobi uses an adaptive algorithm to compute the numerical derivative. It converges fast if the derivative is trivial (constant or linear) and it can handle functions which have poor numerical accuracy (they are numerically noisy, use single precision arithmetic etc.). The amount of numerical noise is detected automatically and propagated into an error estimate for the derivative, which is computed alongside the derivative. This is fairly unique for such a library. By default, the algorithm runs until the error on the result does not improve anymore (usually when it reaches machine precision), but one can also set an accuracy target and jacobi will stop once the estimated error drops below this target.
jacobi uses polynomial extrapolation, which is a higher-order form of Richardson extrapolation. Thanks to extrapolation, it can compute numerical derivatives to machine precision. The polynomial fit also provides the error estimate on the extrapolated derivative.
jacobi is written in pure Python and the implementation is written in a concise way by me, a Python expert and author and maintainer of several open source Python and C++ libraries. I am also the designer and author of Boost Histogram in the Boost C++ project. Jacobi uses only 250 lines. It is very fast, too, because it uses numpy array math efficiently. It is faster than numdifftools by up to a factor of 2 to 1000, depending on the problem.
Describe alternatives you’ve considered.
- scipy.misc.derivative is too difficult to use correctly. The step size
dxhas to be provided by the user, it is not determined automatically. I cannot run this function like a black box and get my derivative to machine precision, I need to know what I am doing and set the parametersdxandorderto suitable values, which I can only do optimally if I already know a lot about my function and its implementation. jacobi is a black-box derivative. It just works, parameters like step size and order are determined automatically from an iterative analysis of the function response. - scipy.optimize.approx_fprime or scipy.optimize.approx_derivative are not robust, cannot achieve machine precision unless “cs” step is used which is rarely possible in practice, and do not provide an error estimate. They call a low-order finite difference formula, which has sqrt(EPS) precision at best (unless “cs” step is used, which is rarely possible in practice), while jacobi often achieves EPS. They are not robust, because these algorithms cannot detect that the function is noisy; the step size that each algorithm selects to find the optimum between truncation error and round-off error is only valid for a function that calculates the correct result within a few ULPs. Non-trivial functions often do not achieve this. It is also possible that some part of the internal calculation is done in single precision, but the inputs and outputs are double precision. In that case, neither algorithm can detect the right step size. jacobi handles this case just fine, because it detects the precision of the calculation by probing the function response iteratively.
- numdifftools offers a black-box derivative, but it is neither robust nor fast. It does not provide an error estimate. The implementation is also much more complex than jacobi due to excessive use of code structuring.
- automatic differentiation libraries like JAX are very intrusive, this is bad. They cannot be integrated into an existing code base, one has to write the application around the AD library. Jacobi can be integrated into any application and it can calculate the derivative for any function, whatever the implementation of that function does (it could call into C or Fortran, use numba, etc.).
Additional context (e.g. screenshots, GIFs)
Jacobi is not intended to provide first derivatives for numerical minimizers like those accessible via scipy.optimize.minimize. It is not a replacement for scipy.optimize.approx_fprime or scipy.optimize.approx_derivative. Numerical minimizers are designed to handle imperfect derivatives that can be computed very fast. Jacobi is not fast enough for those applications and too accurate.
Check out https://hdembinski.github.io/jacobi/ for plots and benchmarks that show how well jacobi works.
About this issue
- Original URL
- State: closed
- Created 4 years ago
- Reactions: 6
- Comments: 37 (35 by maintainers)
In https://github.com/mdhaber/jacobi/pull/1, @HDembinski and I talked a bit about my plan to add a private elementwise differentiation function. The rationale for writing it rather than just using Jacobi was that a) I wanted to focus on elementwise functions for the new univariate statistical distribution framework, and b) it fit neatly into the elementwise iterative method framework, so it shares a lot of code with the new integrator, root-finder, minimizer, and bracket-finders I was already writing. The private differentiation function was merged in gh-18811, and we made it possible to use it for calculating Jacobians and Hessians in gh-20063. The documentation and tests were written to the same standards as other new functions. One to-do is investigating behavior at saddle-points (https://github.com/scipy/scipy/pull/18811#discussion_r1276704177).
It works by starting with a low-order differentiation rule, and it adds new points to the stencil to get progressively higher-order estimates until the termination conditions are satisfied. Mathematically, this should produce the same estimates as Richardson extrapolation; it does not seem as stable for very high orders, but it typically converges well before running into problems.Hah, I forgot that I changed it. The order is fixed now. Each iteration, $n$ ($1$ for one-sided differences, $2$ for central differences) points are added to the stencil with smaller step sizes, and $n$ points with the largest step size are removed from the stencil. It is not as robust to noise as Jacobi’s polynomial extrapolation, and the error estimates seem more conservative, but it’s a bit faster. Of course, there is room to add other methods; we discussed that we can incorporate some of Jacobi’s ideas in the future.In short, we now have a private differentiation function (
scipy.optimize._differentiate) with performance comparable to Jacobi for elementwise derivatives, and I don’t see why the performance would be any different for dense Jacobians (e.g. noforloops are needed). For example, modifying the examples from https://github.com/HDembinski/jacobi to compare_differentiate(instead of numdifftools) against Jacobi:More extensive benchmarking on less trivial functions (
scipy.statsCDFs) is available in https://github.com/mdhaber/jacobi/pull/1#issuecomment-1607843479.The question is where to put a public version of the function.
Here are some possibilities that have been suggested already and one that I’m adding now:
scipy.optimize😄scipy.diff- ❤️derivative,jacobian,hessian) would not really be enough for a full-blown sub-package. We want a few general purpose differentiation tools, but we don’t aim to replace existing packages.scipy.stats🎉stats.sobol_indices, in the sense that they can both be seen as forms of “sensitivity analysis” (local and global).scipy.stats.scipy.integrate: 🚀calculus; it’sintegrate, which suggest the opposite of differentiation.Can we use emojis to get a sense of where people are leaning? Feel free to include other comments and ideas below.