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 code | Source | Authors |
|---|---|---|
Routine that follows their code: recur_coeffs | r_jacobi.m and r_jacobi01.m in OPQ | W. Gautschi; r_jacobi.m supplied by D. Laurie |
| Node certification that follows their idea | Johansson and Mezzarobba (2018) | F. Johansson and M. Mezzarobba |
| New code: the C kernel and all other code | Written for BootLoops | Code 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.
- Rules. It builds the nodes and weights by interval Newton iteration at 2048-bit precision. It accepts a rule only when every weight is provably positive and the rule reproduces exact moments.
- Sweep. Positive weights times positive values cannot cancel: a full-size sweep of 48.7 million nodes at 192 bits encloses $Z_s(p)$ to relative width near $2^{-179}$.
- Frequency integral. It integrates $p$ over fixed panels with certified Gauss–Legendre nodes, a remainder bounded by an exactly integrable Bernstein-basis majorant (a polynomial that bounds its absolute value), and exact bands at the endpoints.
- Comparison. A certified comparison is the winner's lower endpoint minus the rival's upper endpoint, rounded outward for display.
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:
- It covers rooted four-leaf trees only (12 caterpillar shapes, such as $(((A,B),C),D)$, and 3 balanced shapes). Six leaves and ascertainment-corrected likelihoods (adjusted for how the sites were selected) are not covered.
- A different model in the same family needs its degree bookkeeping and prior-to-weight map re-derived, its rules rebuilt, and the verification rerun.
- The repository holds the engine, an exact-rational 8-count surrogate problem for testing, and the verification driver. The full-size driver, data and result tables are not included.
- Scripts that need the data stop with
POSQ-PRODUCTION-DATA-ABSENTunlessPOSQ_STAGE0points at a directory containing it. - A separate module,
closure_interface.py, estimates the evidence of a user-written log-likelihood on the unit cube by Monte Carlo. Its numbers are floating-point estimates, not certified, and it needs an upstream build (POSQ_R3_ROOT) that is not in the repository.
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]
- Phase 0. It repeats the self-test, adds a deliberately corrupted count vector that the kernel must detect, and checks a box enclosure against exact values.
- Phase 1. It samples parameter boxes on three shells and requires every enclosure to contain the kernel's point values. It plants narrowed, shifted and dimension-dropped enclosures that must be caught, and compares finite differences with the exact derivatives. It rebuilds the rules at 53 bits to confirm that too little precision yields no answer, never a wrong one.
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
| Command | What it does |
|---|---|
python3 posq.py --selftest | Surrogate 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.py | 14 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.
| Function | What it returns |
|---|---|
posq.SurrogateExact | The 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.PosqKernelAdaptation | The 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
- Runs on: Python 3 with
python-flint, andscipyfor the initial node guesses in the rule builder. - Install: no kernel binary is included. On first use
kernel_iocompilesposq_kernel.cinto a cache directory (POSQ_KERNEL_CACHE, default~/.cache/posq), which needs a C compiler plus the FLINT, MPFR and GMP headers. To build it yourself, rungcc -O2 -o posq_kernel posq_kernel.c -lflint -lmpfr -lgmp -lmand setPOSQ_KERNEL. - Self-test:
python3 posq.py --selftestends withposq selftest: PASS.python3 verify_posq_adaptation.pyneedstools/eras/beside it and ends with a line beginningVERIFY PASS. - Optional:
numpyandscipyfor the closure-interface self-test, which also needsPOSQ_R3_ROOT.
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.
| Reference | What 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) C726 | Certified Gauss–Legendre rules by interval Newton iteration |
| F. Johansson, IEEE Trans. Comput. 66 (2017) 1281, arXiv:1611.02831 | Arb, the ball arithmetic |
| W. Hart, F. Johansson, A. Ahlbäck and the FLINT team, FLINT | The library that holds Arb, called through python-flint and linked by the C kernel |
SciPy, scipy.special.roots_jacobi | Double-precision starting values for the nodes |
| Felsenstein, J. Mol. Evol. 17 (1981) 368 | The tree likelihood |
| Kolipakam, Jordan, Dunn, Greenhill, Bouckaert, Gray and Verkerk, DravLex v1.0, R. Soc. Open Sci. 5 (2018) 171504 | The database from which the site-pattern counts of the 318-site data set are derived; the counts are not in the package |