ERAS

ERAS (Exact Remainder-Aware Series) computes a rigorous interval for the range of a function over a small interval of one shared parameter, where ordinary interval arithmeticarithmetic on ranges of numbers, so that the result is a proven bound returns one far too wide to use. It implements two classical centered formsbounds built from the value of the function at the midpoint of the interval plus a bounded correction of interval analysis, the mean-value form and the Taylor form, after Moore, Krawczyk and Neumaier, Makino and Berz, and Neumaier. The package also includes a verification suite that any modification or extension of these forms should pass before its results are trusted.

What it does

Interval ("ball") arithmetic carries a midpoint and a radius through a calculation, so the final radius is a proven error bound. Its weakness is the dependency problem: when one parameter $p$ appears in many places, each occurrence is treated as varying on its own, and the bound can grow far beyond the true range.

The typical case is a likelihood that is a product of hundreds of factors sharing one rate parameter. The reference function included with the package is such a product with 318 factors. Evaluated directly over a parameter interval of radius $10^{-4}$, it returns a relative width near $10^{23}$, although its true variation there is a small fraction of its value.

ERAS uses centered forms instead.

Derivatives are exact. Every quantity carries its $d/dp$ (forward-mode dual numbers, class D) or its truncated Taylor series with interval coefficients (class S), on top of the Arb ball-arithmetic library through python-flint. You write the function with these types, give it a parameter interval, and get back an enclosure, an interval that provably contains $F(p)$ for every $p$ in the closed parameter interval.

Software for Taylor models (a polynomial plus an interval remainder, carried as one object through the arithmetic) already exists: COSY INFINITY by Berz and Makino, and TaylorModels.jl by Sanders and Benet. ERAS provides Taylor forms with interval coefficients over Arb balls from Python. It has no Taylor-model arithmetic or composition.

The verification suite, verify_eras_adversarial.py, tests any adaptation of these forms, such as a new function or several parameters. An adaptation is an object with the methods enclose and point_eval and, optionally, deriv and degraded (listed under Routines). The suite first collects the intervals for every box ($p_0 \pm$ radii, one interval per parameter) and order $K$, then runs these checks:

An infinite interval, one wider than 1000 times the spread of the sampled values, or one whose point_eval is too coarse to judge, counts as no information, never as a pass.

ERAS has these limits:

For general-purpose ball arithmetic use Baller, a separate package that leaves Taylor-form enclosures to ERAS. POSQ is a package whose engine was run through this suite.

Examples

Run the package self-test. With python-flint installed (see Requirements), run from the package directory tools/eras/:

python3 eras.py selftest

The script evaluates both forms of the reference function at two parameter points and compares them with stored 50-digit values to within $10^{-30}$. It checks the forward-mode derivative against a central finite difference to within $10^{-20}$, and confirms that a deliberately wrong input, one input count changed by one, shifts both forms by a clearly nonzero amount. Each check line begins OK or FAIL, and the run ends SELFTEST PASS or SELFTEST FAIL with exit code 0 or 1.

Run the verification suite on the included reference forms. This is the full set of checks, as a user would run them before relying on the package:

python3 verify_eras_adversarial.py all

The script prints every check, then NOTES and FATALS, then one verdict line beginning VERIFY PASS, VERIFY FAIL or VERIFY INDET. The verdict line counts the informative, no-information and declared-expected cells (a cell is one box at one order $K$). Most cells of the reference run are in the regime where the interval blows up (naive evaluation, low order, or large radius), and they are declared in advance as expected no-information. The PASS therefore rests on the cells at the working setting.

Test your own adaptation from Python. The POSQ package does this in tools/posq/verify_posq_adaptation.py; the relevant lines are

import verify_eras_adversarial as vb           # noqa: E402

SHELLS = [(("709/2048", "10"), ("1e-3", "5e-2")),
          (("709/2048", "10"), ("5e-3", "2.5e-1")),
          (("709/2048", "10"), ("2e-2", "1e0"))]
PLANT_AT = (1, 0)

cfg = vb.Cfg(seed=a.seed, points=a.points, fd_tol=a.fd_tol)
res = vb.run_battery(adapt, SHELLS, [0], cfg, plant_at=PLANT_AT)

adapt is the object under test, with two parameters, so each shell pairs a tuple of centers with a tuple of radii, written as strings. [0] is the list of orders $K$ to test, a holds the script's parsed options, and plant_at names the (shell index, $K$) cell where the corrupted variants and the precision check are applied. The call prints the command-line report and returns a result object. res.ok (equal to bool(res)) is the pass signal, and a caller that exits 0 without checking it has a bug.

Routines

CommandWhat it does
eras.py selftestReference-value, derivative and wrong-input checks; exit 0 on pass. The default
eras.py blowupNaive against mean-value widths by radius, with containment checks
eras.py taylorkOrder-$K$ Taylor-form widths by radius and $K$, with containment checks
verify_eras_adversarial.py allBoth runs below. The default
verify_eras_adversarial.py referenceThe univariate reference forms: radii $10^{-4}$ to $10^{-1}$, orders $K$ from 0 to 16
verify_eras_adversarial.py selftestThe three-parameter example and a large-value regression case

Each command is run with python3. blowup and taylork save their tables as JSON under $TMPDIR/eras_results (override with ERAS_RESULTS). The suite takes the options --seed, --points, --fd-tol, --degrade-factor, --vacuous-factor, --point-margin and --fd-h-bits. Its exit code is 0 PASS, 1 FAIL, or 2 INDET (nothing failed, but too little informative coverage to pass).

The module eras.py:

FunctionWhat it returns
D(v, d=None)A dual number holding a value and its $d/dp$ as Arb balls; supports +, -, *, /, integer **, exp(), log()
dconst(x, like)A constant as a dual number with zero derivative
S(c)A truncated power series in $p - p_0$ with ball coefficients c; supports +, -, *, /, recip(), exp(), powi(n)
s_var(x0, K)The series of $p$ itself about center x0, to order K
mv_form(fn, pball)(mv_enclosure, naive_ball, F0_dual, Fball_dual): the mean-value enclosure of fn, a function from D to D, over pball
taylor_encl(fn_series, pball, K)(enclosure, point_series, ball_series): the order-K Taylor enclosure of fn_series, a function from S to S
taylor_ladder(fn_series, pball, Ks){K: enclosure}: enclosures for several orders from one pair of series evaluations
relwidth(b)The radius of a ball divided by its absolute midpoint

The reference function is defined in the same file (L_prod_D, L_prod_S, G_unc_D, G_unc_series).

The module verify_eras_adversarial.py:

FunctionWhat it returns
Cfg(seed, points, fd_tol, ...)The settings for one run; each command-line option is a keyword (--fd-tol is fd_tol)
run_battery(adapt, shells, Ks, cfg, plant_at, fd_box, Ks_by_shell, expect_indet)A BatteryResult for the whole suite on one adaptation; shells is a list of (p0, radii)
BatteryResultFields ok, fatals, notes, cells_pass, cells_indet, cells_declared; bool(result) == result.ok
MultivariateSelfTest(prec=128)The worked three-parameter adaptation; a template for your own

Your adaptation is an object with a label and the methods below. The docstring of verify_eras_adversarial.py gives the full protocol.

FunctionWhat it returns
enclose(p0, radii, K)An interval rigorous for the closed box $p_0 \pm$ radii ($K=0$ naive, $1$ mean-value, $\ge 2$ Taylor)
point_eval(p, prec=None)A high-precision value
deriv(p, dim)Optional. The derivative along parameter dim
degraded()Optional. The same adaptation at low precision

Requirements

Source and references

The code is in tools/eras/ in the BootLoops repository. GUIDE.md there carries the credits.

ReferenceWhat it supplies
R. E. Moore, Interval Analysis, Prentice-Hall (1966)The mean-value form
Krawczyk and Neumaier, SIAM J. Numer. Anal. 22 (1985) 604The centered forms
Makino and Berz, Int. J. Pure Appl. Math. 4 (2003) 379Taylor models
Neumaier, Reliable Computing 9 (2003) 43Taylor forms
F. Johansson, IEEE Trans. Comput. 66 (2017) 1281, arXiv:1611.02831; python-flint by F. Johansson, O. Benjamin and contributorsArb, the ball arithmetic, and its Python bindings
Felsenstein, J. Mol. Evol. 17 (1981) 368The likelihood of the reference function
Kolipakam, Jordan, Dunn, Greenhill, Bouckaert, Gray and Verkerk, DravLex v1.0, R. Soc. Open Sci. 5 (2018) 171504; data set doi:10.5281/zenodo.5121580The Dravidian lexical database from which the counts in QUARTET_COLLAPSE.json are derived

← back to the tools index