Mixalot
Mixalot is a Python package that computes the Bayesian evidencethe probability of the observed data under a model, with its parameters averaged over their prior of finite mixture modelsstatistical models that read data as a blend of hidden subpopulations for count data exactly, as a rational number. It also gives the exact posterior probability of each possible number of components. It implements the exact mixture-evidence sums of Lin, Sturmfels and Xu (arXiv:0805.3602) and collects the evaluators written for the paper Exact Bayesian evidence for mixture models.
What it does
You give Mixalot a vector of integer counts (how many of N observations fell in each of k categories) and a number of components g. It returns a Python Fraction; for very large problems you print its logarithm rather than its digits. The ratio of two evidences is a Bayes factor, the Bayesian way to decide between "one population" and "two".
For a mixture of g categorical distributions on k states the evidence is an integral over every component's probabilities and the mixing weights. In practice it is almost always estimated by Monte Carlo. With uniform Dirichlet priorsthe standard priors for a vector of probabilities that sum to one the integral collapses to a finite sum over the ways the N observations can be allocated among components. Mixalot computes that sum by dynamic programming in big-integer arithmetic.
The default convention is a fixed observation sequence (no multinomial coefficient) with Dirichlet(1) priors. With measure="lebesgue" the Dirichlet normalizing constants $(g-1)!\,((k-1)!)^g$ are divided out instead.
The package has these parts:
- Counts.
mixalot.Z,mixalot.gstarandmixalot.bayes_factorcover small and medium problems. - Large problems. The bundled evaluators in
mixalot.enginescover closed forms in harmonic numbers for one binary variable, thousands of states, any number of components, and the exact infinite-component (Dirichlet-process) limit. - Tables. Two-way contingency tables are computed modulo many primes and reassembled by the Chinese remainder theorem.
- Box integrals. The
boxwalksubpackage (see Boxwalk below) evaluates the underlying unit-box moment integrals $\int_{[0,1]^n}\prod_k P_k(x)^{u_k}\,dx$ exactly for integer polynomials $P_k$. It uses a recurrence walk modulo primes followed by rational reconstruction (recovering a fraction from its residues modulo primes). - Ordered data.
seg_v1takes an ordered sequence of count vectors (chapters of a book, say). It computes the evidence for g contiguous segments, each with its own profile, and the posterior on where the boundaries fall. - Known profiles. For components with known profiles and unknown Dirichlet weights,
frozen_comp_v1returns the evidence and the Bayes factor for whether a given component is present. - Authorship. For an ordered token sequence,
seamgives the exact evidence that one known profile produced a prefix and another the suffix.dcmuses a Dirichlet-compound-multinomial, so word rates may vary from stretch to stretch.nullcalreads a mixed-versus-pure Bayes factor against the same statistic on objects known to be pure, because a mixture's extra freedom also absorbs ordinary rate variation. - Other models. Further evaluators cover Etienne's sampling formula of neutral biodiversity theory and the telegraph model of gene expression. The Etienne evaluators come in exact, interval-arithmetic and certified maximum-likelihood forms, and include the multi-sample form, the random-fission model and a three-level hierarchical evaluator. A Monte Carlo suite checks a sampler against exact values where both run.
mixalot.verify() re-hashes every bundled file against recorded checksums. It raises VendorTamperError and refuses to compute if any file has changed, is missing or has been added.
The package has these limits:
- With two components, N around $10^5$ is easy. With three, N = 3,000 needs about 1 GB of memory and N = 10,000 about 25 to 30 GB. With four or more, N reaches roughly 500 to 700.
mixalot.advise()reports the measured reach. - The evidence evaluators return exact rationals. The exceptions are marked in their names or modes:
Z_float,lnZ_g_float, the interval mode of the Etienne evaluator and the Monte Carlo suite. - The package handles categorical count data only. A non-integer count raises
NonIntegerCountErrorinstead of being rounded. - For a bare vector of counts from single draws, a mixture of categoricals is itself a categorical. The data then say little about g, and at small N the posterior mostly reflects the prior. Exact computation does not remove this weakness.
Data with structure (ordered units, known profiles) have more power. plant, recover_blind and mic_power measure detection power on synthetic data shaped like yours.
Examples
Exact evidence and the component-count posterior. With the dependencies installed (see Requirements), the manual's quickstart runs against a checkout of the repository, where the package directory is tools/mixalot/:
import sys; sys.path.insert(0, "<your-checkout>/tools/mixalot") import mixalot mixalot.verify() mixalot.Z([4,1,3,2], 2) mixalot.gstar([4,1,3,2], gmax=3) from mixalot.engines import zseries, seg_v1, frozen_comp_v1, w4_blind_gf
verify() returns a report whose vendor_ok list names every bundled file that passed. Its source_missing entries refer to the original source trees, which are not distributed, and are expected. Z returns Fraction(1010921, 2330808480000), the two-component evidence for ten observations on four states.
gstar returns a dictionary with posterior (one Fraction per g from 1 to gmax, summing to one), map_g, p_ge2, evidence, prior and gmax. Here the posterior is roughly 0.22, 0.35, 0.43 for g = 1, 2, 3, so P(g ≥ 2) is near 0.78 with no value of g singled out. Ten bare counts barely constrain g, which is the last limit listed above.
Command line. Put the counts in a JSON file, either a bare list [3, 1, 4, 1, 5] or an object {"U": [3,1,4,1,5], "gmax": 3}, and run
python3 -m mixalot.cli counts.json [--gmax 4]
The output is one JSON block. It holds U, k, N, gmax, the posterior for each g as an exact fraction with a float beside it, map_g, p_ge2, the evidence for each g, and the advise() text for that N. With no file it prints the input schema.
Exact versus Monte Carlo at one point. The self-test suite and examples/worked_examples.py both run this comparison, two components of one binary variable with counts (50, 50):
from mixalot.engines import load
cf = load("closed_form_1var")
z = cf.Z_closed(50, 50)
est = load("estimators")
r = est.run("m1", 2, [50, 50], "nested", seed=1)
z is the exact evidence as a Fraction; its logarithm is −71.0794. r is a dictionary whose fields include logZ_hat, err_est, diagnostics and settings. The recorded test log has logZ_hat = −71.0204, 0.6 standard errors from the exact value, so nested sampling is calibrated at this size.
python3 examples/worked_examples.py prints this and four more demonstrations: the exact log-evidence at N = 100,000, 300 states, the Dirichlet-process limit $Z_{\rm DPM}=5/48$ for counts (2, 1), and the exact finite-g correction $g\,(Z_g - Z_{\rm DPM}) = -1/48$. python3 examples/large_kgn_table.py [--quick] writes the full exact-versus-sampler table.
Routines
The commands run from the package directory tools/mixalot/.
| Command | What it does |
|---|---|
python3 -m mixalot.cli counts.json [--gmax G] | Prints the posterior over the number of components, as JSON |
python3 battery/battery.py [--full] | Runs the self-test suite; exit code 1 on any failure |
python3 examples/worked_examples.py | Prints the five demonstrations of the third example |
python3 examples/large_kgn_table.py [--quick] | Writes the exact-versus-sampler table |
mixalot/acceptance_no55.py | Reproduces the bundled reference values for Federalist No. 55 under the dcm model |
python3 -m mixalot.boxwalk plan SPEC.json | Prints the walk plan of a box integral; produce, fiber and verify run the other boxwalk functions |
The arguments of the boxwalk commands are listed at the top of mixalot/boxwalk/cli.py.
The package is loaded with import mixalot, and the authorship modules with from mixalot import nullcal, seam, dcm.
| Function | What it returns |
|---|---|
verify() | The checksum report for every bundled file |
Z(U, g, measure) | The exact evidence as a Fraction; above N = 2,000,000 it stops with an error that names the evaluators to use |
gstar(U, gmax, prior) | The exact posterior over g from 1 to gmax |
bayes_factor(U, g1, g2) | Z(U, g1) / Z(U, g2), exact |
advise(N, g) | The measured memory and time reach of the exact evaluators |
plant, recover_blind | Synthetic counts from a known mixture, and how often gstar then finds the true g |
core.Zdpm(U, alpha) | The exact evidence in the Dirichlet-process limit |
core.lsx_example(name) | True if the Lin–Sturmfels–Xu benchmark 'swiss', 'coin10' or 'coin242' is reproduced |
engines.load(name) | A bundled evaluator, loaded after its checksum is re-checked |
nullcal.calibrate, nullcal.calibrate_objects | The place of a Bayes factor among known-pure objects, with a verdict INSIDE-NULL, TAIL or ABOVE-NULL |
seam.z_seam(seq, pA, pB) | The exact changeover evidence, with the posterior of the changeover point |
dcm.dcm_pure, dcm.dcm_mixture, dcm.dcm_seam | Exact Dirichlet-compound-multinomial evidences: pure, token mixture and change-point |
dcm.fit_kappa | The shared concentration kappa, fitted on known-pure objects |
z_seam raises ProfileError if a profile does not sum to one. Outside the package, calibrate_objects raises EngineUnavailable unless you pass a Z callable. MANUAL.md describes further functions, among them core.p_g1, blend_vs_pure_bf and z_seam_brute.
The bundled evaluators are loaded as mixalot.engines.<name>.
| Function | What it returns |
|---|---|
bigg.Z_bigg | The exact evidence for any g; the routine behind mixalot.Z |
bigk2.Z_fast2 | The exact evidence for two components and thousands of states |
closed_form_1var.Z_closed | The harmonic-number closed form for two components of one variable |
zseries.z_ray_1var, z_ray_table_modp, Z_table_modp | The series Z(n·U0), exactly or modulo a prime below $2^{25}$, for one variable or a two-way table |
lsx_direct.run_example | The evidence in the Lin–Sturmfels–Xu conventions, by a separate evaluator |
lsx55_exact | A script for their Example 5.5 (the 3×3, N = 132 table), by many primes and rational reconstruction |
w4_blind_gf.Zg_gf, Zdpm_gf | The finite-g evidence with Dirichlet(alpha/g) weights and its exact Dirichlet-process limit |
estimators.run | A Monte Carlo estimate (hm, bridge, ss, chib, nested) for one binary variable (m1) or a four-flip binomial (m4) |
seg_v1.Z_exact, boundary_posterior_exact | The contiguous-segment evidence and boundary posteriors; Z_float and boundary_posterior_float use log-domain floats |
frozen_comp_v1.evidence, presence_bayes_factor | The exact evidence for a blend of known profiles, and the Bayes factor for one more profile |
etienne_evaluate.P_exact, logP_ball | Etienne's sampling formula for a species-abundance vector, exact or as a certified interval |
telegraph_evaluate.pmf_certified, loglik_certified | The transcript-count distribution and log-likelihood of the two-state gene-expression model |
mixalot/engines.py lists every loadable evaluator. MANUAL.md says which evaluator serves which problem. Some evaluators need care:
- Printing. With
bigk2, print the logarithm. The integers exceed Python's default print limit. - Scratch directory.
lsx55_exactandphase2_multisample_eqI(certified maximum likelihood for the multi-sample Etienne formula), run as scripts, write into the current directory, so run them from a scratch directory.lsx55_exacttakes about 6.5 minutes and 3.6 GB per prime. - Environment.
mic_powerandproduction_sweep(a driver used in the cross-checks) refuse to load unlessMIXALOT_PILOT_DIRnames the directory holdingseg_v1.py. - Float.
swap_routegives a float64 log-evidence for k = 2 up to very many components. It is a demonstration checked against the exact value at N = 100, not a general evaluator. - Estimators.
hm,bridge,ssandchibare implemented inside the package, with the package's settings. Bridge sampling follows the formulation of Gronau et al. and is not a run of the R package bridgesampling.nestedcalls dynesty.
Boxwalk is the subpackage mixalot/boxwalk/, loaded with from mixalot import boxwalk.
| Function | What it returns |
|---|---|
boxwalk.load_spec(path_or_dict) | A problem specification |
boxwalk.plan(spec) | The walk plan: class order, mechanism per segment, memory per prime and a program checksum |
boxwalk.produce(spec) | The exact Fraction, with a MANIFEST.json that records the checks it passed |
boxwalk.emit_fiber_recurrence(spec) | The integer-coefficient recurrence of Z along one exponent direction |
boxwalk.verify_manifest(spec, manifest) | The result of a separate replay of a recorded manifest at fresh primes |
A specification holds variables, polynomials (label → {exponent string: integer coefficient}), target_u (label → count), order and options. The example mixalot/boxwalk/examples/jc_quartet.json holds fifteen Jukes–Cantor quartet kernels. produce stops with "increase nprimes" rather than return a wrong value, and verify_manifest estimates its cost first and refuses over max_cells. MANUAL.md lists the remaining functions, among them walk and the shift-operator calculus.
Used on this site
- Mixture models: evaluated the exact evidences on that page.
- Disputed authorship: evaluated the evidence integrals for the Federalist, Shakespeare and Bible analyses.
- The Voynich Manuscript: computed the exact mixture evidence behind the page-by-page dialect classification.
Requirements
- Runs on: Python 3 with the BootLoops common dependencies (
mpmath,sympy,numpy,python-flint) plusscipyanddynesty. - Install:
pip install mpmath sympy numpy python-flint, thenpip install scipy dynesty. Puttools/mixalotonsys.pathas in the first example. - Self-test:
python3 battery/battery.pyfrom the package directory ends with a line beginningOVERALL PASS. SetMIXALOT_BATTERY_OUTto write theBATTERY.txtrecord elsewhere. - Full self-test:
--fulladds longer checks. Some of them skip unlessMIXALOT_REFDATA_PILOT,MIXALOT_REFDATA_SWEEPandMIXALOT_PILOT_DIRpoint at reference data that is not part of the repository. - Authorship modules:
mixalot/selftest.pyruns from any directory and ends with[SELFTEST] ALL PASS. - Boxwalk: needs Singular on the PATH. Its self-test is
python3 -m mixalot.boxwalk selftest; without Singular the Singular part is reported as skipped. The self-test writesSELFTEST.jsoninto the subpackage's directory unlessBOXWALK_SELFTEST_OUTnames another file. - Optional: the comparison estimators based on Hamiltonian Monte Carlo (HMC) import
jax. Boxwalk fits recurrences with the bundled copy of Annihilator;BOXWALK_ANNIHILATOR=/path/to/annihilator.pyselects another copy, such as the stand-alonetools/annihilator/.
Source and references
The code and its manual (MANUAL.md) are in tools/mixalot/ in the BootLoops repository; boxwalk has its own README in mixalot/boxwalk/. The package is new Python code, written by Claude, for the sums and formulas defined in the papers below. Please cite them when you use it.
| Reference | What it supplies |
|---|---|
| M. D. Schwartz and S. Sen, Exact Bayesian evidence for mixture models: from two components to infinity | The exact evidence formulas that the package evaluates |
| S. Lin, B. Sturmfels and Z. Xu, J. Mach. Learn. Res. 10 (2009) 1611, arXiv:0805.3602 | The exact mixture-evidence sums, their recurrence algorithm and conventions, and the benchmark values. The authors' own Maple library is public |
| R. S. Etienne, Ecol. Lett. 8 (2005) 253 and 10 (2007) 608; Etienne and Haegeman, Theor. Ecol. 4 (2011) 87 | The sampling formula of neutral biodiversity theory, its multi-sample form and the random-fission model |
| R. K. S. Hankin, J. Stat. Softw. 22(12) (2007), the untb package | Etienne's worked example, the test target of etienne_evaluate |
| J. Peccoud and B. Ycart, Theor. Popul. Biol. 48 (1995) 222; Larsson et al., Nature 565 (2019) 251 (txburst) | The telegraph model of gene expression; telegraph_evaluate takes its parameter conventions from txburst |
| Madsen, Kauchak and Elkan, ICML 2005, 545 | The Dirichlet-compound-multinomial model of dcm |
| Newton and Raftery, JRSS-B 56 (1994) 3 | The harmonic-mean estimator (hm) |
| Meng and Wong, Stat. Sinica 6 (1996) 831; Gronau et al., J. Math. Psych. 81 (2017) 80 | Bridge sampling (bridge), in the formulation of Gronau et al. |
| Xie et al., Syst. Biol. 60 (2011) 150 | The stepping-stone estimator (ss) |
| Chib, JASA 90 (1995) 1313 | Chib's estimator (chib) |
| Skilling, Bayesian Anal. 1 (2006) 833; Speagle, MNRAS 493 (2020) 3132 (dynesty) | Nested sampling (nested), run through dynesty |
| W. Decker, G.-M. Greuel, G. Pfister and H. Schönemann, Singular | The relation modules of boxwalk |