POSQ

POSQ computes the Bayesian evidence (the likelihood integrated over the prior) of a small continuous-time Markov chaina random process that jumps between states at fixed rates model on a four-leaf tree, as an interval whose two endpoints are proven bounds. From site-pattern counts (the number of sites with each pattern of leaf states) and the prior's parameters it gives that interval for each tree shape, and certified lower bounds on log Bayes factorsratios of the evidence of two models between shapes. The integral is an exact Gauss quadrature sum of positive terms in ball arithmeticevery number is carried as a midpoint plus a radius that provably contains the true value; FLINT/Arb is the library used, with nodes certified in the manner of Johansson and Mezzarobba.

Where it comes from

Walter Gautschi's OPQ suite has two routines for the recurrence coefficients of the Jacobi polynomials: r_jacobi.m, supplied by Dirk Laurie, and r_jacobi01.m. POSQ's routine recur_coeffs follows them. F. Johansson and M. Mezzarobba (2018) certified Gauss–Legendre rules by interval Newton iterationa Newton step carried out on an interval, which proves that the interval contains exactly one root in ball arithmetic. POSQ's rule builder applies their idea to Gauss–Jacobi rulesquadrature rules with n nodes that integrate polynomials up to degree 2n−1 exactly against a power weight on [0,1] and does not call their routine in Arb. The rest of POSQ was written for BootLoops by Claude.

Part of the codeSourceAuthors
Routine that follows their code: recur_coeffsr_jacobi.m and r_jacobi01.m in OPQW. Gautschi; r_jacobi.m supplied by D. Laurie
Node certification that follows their ideaJohansson and Mezzarobba (2018)F. Johansson and M. Mezzarobba
New code: the C kernel and all other codeWritten for BootLoopsCode by Claude

Please cite the authors' works when you use POSQ. POSQ is not affiliated with or endorsed by them.

What it does

Bayesian model comparison rests on the evidence $Z=\int(\text{likelihood})\times(\text{prior})$. For tree models it is usually estimated by Monte Carlo, with a statistical error and no guaranteed bound. Interval arithmetic applied directly gives uselessly wide bounds, because expanding the likelihood into polynomial coefficients produces enormous cancellation. POSQ expands nothing: it evaluates the likelihood as a product of values at quadrature nodes, and every term of the sum is positive.

The model class is a two-state Markov chain on a rooted four-leaf tree with a strict clock (the same rate on every branch), with Felsenstein's (1981) tree likelihood. The clock increments $s_k$ have exponential priors (rate $\lambda$), and the stationary frequency $p$ (the long-run share of one of the two states) has a uniform prior. Substituting $u_k=e^{-\beta s_k}$, with $\beta$ the chain's rate constant, integrates the exponential priors out exactly and leaves

$$Z_s(p)=\frac{c^3}{2}\int_{[0,1]^3}u^{\,c-1}\,F(u;p)\,du,\qquad c=2\lambda p(1-p),$$

where $F$ is the product over observed site patterns of the pattern probability raised to its count: a polynomial in $u$ of known degree, positive on the cube. A Gauss–Jacobi rule for the weight $u^{c-1}$ with enough nodes integrates $F$ with zero error, so the three clock dimensions add nothing to the width of the answer.

POSQ works in four steps.

All of the final width and nearly all of the cost are in the frequency integral, and a looser width target barely lowers the cost. Measured on a 318-site four-taxon data set, one tree shape was run to an $\ln Z$ interval 0.06 to 0.1 nats (natural-log units) wide.

POSQ raises an error instead of returning a number when a weight ball straddles zero, or when a per-node value or an assembled $Z$ fails to certify positive. It does the same when a sweep's relative width is worse than $2^{-100}$. The three balanced shapes $((A,B),(C,D))$ use a separate min/difference change of variables whose exactness checks must pass before any sweep.

POSQ has these limits:

Examples

Quick self-test. With the package set up (see Requirements), check from the package directory tools/posq/ that the exact surrogate and the C kernel agree on this machine:

python3 posq.py --selftest

S1 recomputes the surrogate's evidence at $(p,\lambda)=(709/2048,\,10)$ as an exact fraction and compares its checksum and logarithm with the recorded values. S2 runs the kernel at the same point and requires the certified ball to contain that fraction at relative width better than $2^{-100}$. A passing run prints

[PASS] S1 exact surrogate sha256 pin (e6fc044cdd0dabfb..)
[PASS] S1b ln Z = -25.97566273247789 vs pinned -25.97566273247789
[PASS] S2 live kernel ball contains exact rational (relwidth 2^-248.2, line 2^-100)
posq selftest: PASS

and exits 0. If no kernel binary runs here and none can be built, S2 is skipped with the message POSQ-KERNEL-UNAVAILABLE.

One certified value from Python. Evaluate the surrogate's evidence through the kernel at an exact rational point:

import sys; sys.path.insert(0, '<your-checkout>/tools/posq')
import posq

adapt = posq.PosqKernelAdaptation()
Z = adapt.point_eval(("709/2048", "10"))   # certified ball via the C kernel

Z is an Arb ball: the true value lies within Z.rad() of Z.mid(). Before sweeping, the object rebuilds the three Gauss–Jacobi rules at this point's exact $c$ and rechecks them; a rule that fails raises an error. adapt.deriv(p, dim) gives $\partial Z/\partial p$ or $\partial Z/\partial\lambda$ from an exact closed form with no quadrature, which the verification compares against.

Full verification run. Put the engine through the ERAS adversarial verification suite:

python3 verify_posq_adaptation.py [--seed N] [--points N]

Exit 0 is pass, 1 fail, 2 indeterminate (for example, no runnable kernel). One passing seed is necessary, not sufficient; rerun with several --seed values before trusting an adaptation of your own.

Routines

CommandWhat it does
python3 posq.py --selftestSurrogate checksum and one live kernel containment check; takes seconds
verify_posq_adaptation.py [--seed N] [--points N] [--fd-tol X]The full verification above; imports the ERAS verifier from tools/eras/
bench_rung1_gauss.py <mode>Rule builder and reference-sweep driver
derive_posq_sentences.py [table.json [out.json]]Comparison statements (winner, gap to runner-up and to each split class), rounded outward, from a 15-shape table of $\ln Z$ intervals
selftest_closure_interface.py14 checks of the closure interface against closures with exact evidence
posq_kernel <jobfile>The C sweep kernel (modes cat, bal, ms), normally driven through kernel_io.py

Two modes of bench_rung1_gauss.py run from the checkout: surrogate, the exact 8-count cross-check with a corrupted-count control, and rules, which builds the full-size rules. The other modes need POSQ_STAGE0. derive_posq_sentences.py reads result files of the original runs (POSQ_RESULTS_DIR, POSQ_SD_DIR), which are not included, and stops with a message when they are absent.

FunctionWhat it returns
posq.SurrogateExactThe surrogate as an exact closed form: Z_fr(p, lam) gives a Fraction, jet_arb(p, lam, prec) gives $(Z,\partial_pZ,\partial_\lambda Z)$ as balls
posq.PosqKernelAdaptationThe kernel as a certified point engine: point_eval(p, prec), enclose(p0, radii, K), deriv(p, dim), degraded()
bench_rung1_gauss.build_rule(n, alpha, tag)Certified Gauss–Jacobi nodes and weights for the weight $u^{\alpha}$ on $[0,1]$, with their acceptance record
closure_interface.evaluate_evidence(loglik, dim, budget, seed, name)A labeled Monte Carlo estimate of $\ln Z$ for a user log-likelihood on the unit cube

The box enclosure enclose is valid for $p\lt 1/2$; it is test scaffolding, not the panel scheme. In closure_interface.py, infer_hazard_field() and posterior_draws() raise ClosureObjectMissing: no posterior sampler is provided. GUIDE.md in the package has a table of the engine files and their roles.

Requirements

Source and references

The code is in tools/posq/ in the BootLoops repository. It is also importable as the quad.posq module of Baller, which links to the same files.

ReferenceWhat it supplies
W. Gautschi, OPQ, doi:10.4231/R7959FHP; Orthogonal Polynomials: Computation and Approximation, Oxford (2004)r_jacobi.m (supplied by D. Laurie) and r_jacobi01.m, which recur_coeffs follows
F. Johansson and M. Mezzarobba, SIAM J. Sci. Comput. 40 (2018) C726Certified Gauss–Legendre rules by interval Newton iteration
F. Johansson, IEEE Trans. Comput. 66 (2017) 1281, arXiv:1611.02831Arb, the ball arithmetic
W. Hart, F. Johansson, A. Ahlbäck and the FLINT team, FLINTThe library that holds Arb, called through python-flint and linked by the C kernel
SciPy, scipy.special.roots_jacobiDouble-precision starting values for the nodes
Felsenstein, J. Mol. Evol. 17 (1981) 368The tree likelihood
Kolipakam, Jordan, Dunn, Greenhill, Bouckaert, Gray and Verkerk, DravLex v1.0, R. Soc. Open Sci. 5 (2018) 171504The database from which the site-pattern counts of the 318-site data set are derived; the counts are not in the package

← back to the tools index