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.
- Mean-value form. It evaluates the function exactly at the midpoint $m$ and bounds the rest through the derivative over the whole interval $P$: $F(P) \subseteq F(m) + F'(P)\,(P-m)$. The derivative bound still suffers from dependency, but it is multiplied by the small radius.
- Taylor form of order $K$. It takes the first $K-1$ Taylor coefficients at the midpoint and bounds only the $K$-th, the Lagrange remainder, over the interval.
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:
- Containment. Precise values at the box's exact corners and faces, in thin bands just inside each face, and at two batches of random points must lie inside the intervals.
- Corrupted variants. Deliberately corrupted copies of the adaptation (narrowed, shifted, one radius ignored) must all be detected.
- Derivative.
deriv, if the adaptation has it, is compared with finite differences. - Precision. The low-precision copy returned by
degraded(), if the adaptation has it, must be caught.
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:
- The guarantee holds for functions built from the operations the two classes provide (arithmetic, integer powers,
exp, and forDalsolog). - The width is not guaranteed to be small. On the reference function the working setting is order $K=16$ with a parameter half-width of about $3\times10^{-3}$ or less.
- Constants must be built at the working precision. One left at 53-bit double precision widens the reference interval by a factor near $10^{11}$.
- The midpoint must be exactly representable, or its rounding error added to the radius.
- The core module handles one scalar parameter. Multivariate forms are yours to write, and the suite tests them;
MultivariateSelfTestinverify_eras_adversarial.pyis a worked three-parameter example. - One passing seed is not enough on its own, since a corruption confined to a thin unsampled region is caught only with some probability. Rerun with several
--seedvalues. - The suite cannot protect against edits to
verify_eras_adversarial.pyitself.
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
| Command | What it does |
|---|---|
eras.py selftest | Reference-value, derivative and wrong-input checks; exit 0 on pass. The default |
eras.py blowup | Naive against mean-value widths by radius, with containment checks |
eras.py taylork | Order-$K$ Taylor-form widths by radius and $K$, with containment checks |
verify_eras_adversarial.py all | Both runs below. The default |
verify_eras_adversarial.py reference | The univariate reference forms: radii $10^{-4}$ to $10^{-1}$, orders $K$ from 0 to 16 |
verify_eras_adversarial.py selftest | The 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:
| Function | What 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:
| Function | What 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) |
BatteryResult | Fields 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.
| Function | What 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
- Runs on: Python 3 with
python-flint(the Arb ball-arithmetic library). - Install: nothing is compiled. Run the scripts from inside the package directory
tools/eras/. - Data file:
QUARTET_COLLAPSE.jsonholds the 318 pattern counts that define the reference function (shared with POSQ). It must sit besideeras.pyor in the directory named byERAS_BASE; a missing file raises an error at import. - Self-test:
python3 eras.py selftestends with a line beginningSELFTEST PASSand takes a few seconds.python3 verify_eras_adversarial.py allends with a line beginningVERIFY PASSand takes about a minute.
Source and references
The code is in tools/eras/ in the BootLoops repository. GUIDE.md there carries the credits.
| Reference | What it supplies |
|---|---|
| R. E. Moore, Interval Analysis, Prentice-Hall (1966) | The mean-value form |
| Krawczyk and Neumaier, SIAM J. Numer. Anal. 22 (1985) 604 | The centered forms |
| Makino and Berz, Int. J. Pure Appl. Math. 4 (2003) 379 | Taylor models |
| Neumaier, Reliable Computing 9 (2003) 43 | Taylor forms |
F. Johansson, IEEE Trans. Comput. 66 (2017) 1281, arXiv:1611.02831; python-flint by F. Johansson, O. Benjamin and contributors | Arb, the ball arithmetic, and its Python bindings |
| Felsenstein, J. Mol. Evol. 17 (1981) 368 | The 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.5121580 | The Dravidian lexical database from which the counts in QUARTET_COLLAPSE.json are derived |