boltzmann-brain alternatives and similar packages
Based on the "Math" category
* Code Quality Rankings and insights are calculated and provided by Lumnify.
They vary from L1 to L5 with "L5" being the highest. Visit our partner's website for more details.
Do you think we are missing an alternative of boltzmann-brain or a related project?
Boltzmann Brain is a Haskell library and standalone application meant for random generation of combinatorial structures. Using an easy and intuitive context-free text input representing a combinatorial specification of rational or algebraic objects, Boltzmann Brain allows its users to:
- sample random structures following the given input specification;
- visualize sampled objects using the GraphViz graph visualization software, and finally
- compile a self-contained, dedicated analytic sampler for optimal sampling efficiency.
Remarkably, using Boltzmann Brain it is possible to control the outcome distribution of generated objects and, in particular, skew it to one needs. You provide the target distribution, we handle the sampling process for you!
If you can specify it, you can sample it!
Citing Boltzmann Brain
If you use Boltzmann Brain or its components for published work, we encourage you to cite the accompanying paper:
Maciej Bendkowski, Olivier Bodini, Sergey Dovgal
Boltzmann Brain (bb for short) is an open-source analytic sampler compiler. Given a textual representation of the combinatorial system, bb constructs a dedicated analytic sampler. The sampler itself is a self-contained, and reusable Haskell module which, by construction, is guaranteed to sample random objects following the given, feasible target distribution. Using state-of-the-art optimization techniques, bb compiles an efficient sampler implementation which can be further modified, incorporated in other software or used as a standalone module.
The input specification format mimics that of Haskell algebraic data types where in addition each type constructor may be annotated with an additional weight parameter. For instance:
-- Motzkin trees MotzkinTree = Leaf | Unary MotzkinTree (2) | Binary MotzkinTree MotzkinTree.
In the above example, a
MotzkinTree data type is defined. It contains three
- a constant
Leafof weight one (default value if not annotated);
- a unary
Unaryconstructor of weight two, and
- a binary contructor
Binaryof default weight one.
- a unary
The definition ends with an obligatory dot.
Each definition constitutes an algebraic data type where each inhabitant has an intrinsic size, defined as the sum of all its building constructor weights.
Given a system of (possibly) mutually recursive types, Boltzmann Brain automatically detects the specification kind (either rational or algebraic) and constructs a singular, rejection-based analytic sampler able to sample uniformly random, conditioned on size, inhabitants of the system types. Though the exact size of the outcome is a random variable, the outcome sampler allows to control the desired lower and upper bounds of the generated objects.
Boltzmann Brain supports a target frequency calibration using convex optimisation techniques. These are implemented as a Python library Paganini built using cvxpy. Boltzmann Brain communicates with Paganini through a tiny executable called medulla (see the medulla subdirectory). Consider the following example of a specification defining Motzkin trees with some arbitrary size notion:
-- Motzkin trees MotzkinTree = Leaf | Unary MotzkinTree (2) [0.3] | Binary MotzkinTree MotzkinTree (2).
Unary construct is given weight 2 and a target frequency of
0.3. In consequence, the system is to be tuned such that the
node contributes, on average, 30% of the total size of constructed Motzkin
trees. It is hence possible to distort the natural frequency of each
constructor in the given system.
Note however, such an additional non-trivial tuning procedure causes a not insignificant change in the underlying probability model. In extreme cases, such as for instance requiring 80% of internal nodes in plane binary trees, the constructed sampler might be virtually ineffective due to the sparsity of tuned structures.
Please tune with caution!
For standard help/usage hints type
bb -h (or
paganini -h). For more advanced options, Boltzmann Brain provides its own annotation system (see example below):
-- Motzkin trees @module Sampler @precision 1.0e-12 @maxiter 30 @withIO y @withLists y @withShow y M = Leaf | Unary M [0.3] | Binary M M.
@module annotation controls the name of the generated Haskell module (it
Sampler if not explicitly given). Next two annotations
@maxiter are parameters passed to Paganini and control the
quality of the tuning procedure. If not provided, some reasonable default values are
assumed (depending on the detected system type). The last three parameters
control some additional parameters used while generating the sampler code.
Specifically, whether to generate addtional
IO (input/output) generators, whether to generate
list samplers for each type in the system, and finally whether to include
deriving Show clauses for each type in the system. By default,
@withShow are enabled (to disable them, set them to
is by default disabled if not stated otherwise in the input specification.
Using annotations it is also possible to control the sampling parameters of Boltzmann Brain . Consider the following example:
-- Random sampling of Motzkin trees -- Parameters for "tuning" @precision 1.0e-12 @maxiter 30 -- Sampling parameters @lowerBound 100 @upperBound 10000 @generate M M = Leaf | Unary M [0.3] | Binary M M.
In the above example, three more annotations are used. The first two dictate the
admissible size window of the generated structures whereas the third one specifies
the type from which we want to generate. If no bounds are provided, Boltzmann Brain uses
some (small) default ones. If no
@generate annotation is provided, Boltzmann Brain
assumes some default type.
For parameter tuning, Boltzmann Brain invokes the external medulla script. Usually, Boltzmann Brain automatically calls medulla once tuning is in order. If no special handling is required, it just suffices to have
paganini available in the system; Boltzmann Brain will automatically pass it necessary data and retrieve the tuning data.
However, it needed, a manual tuning workflow is also supported. To tune a combinatorial specification "by hand", you can start with generating a Paganini representation of the system, e.g. using
bb spec -i specification.in -o specification.out.
Boltzmann Brain ensures that the input specification is sound and well-founded. Otherwise, (arguably) user-friendly error messages are provided. Once the Paganini specification is generated, we type
medulla -i paganini.pg > bb.param
which runs Paganini and outputs the required tuning data for
can alter the default agruments of
paganini scripts such as tuning precision,
optimisation problem solver, maximum number of iterations, and explicitly
specify if the type of the grammar is rational (for rational specifications the optimization problem
might become unbounded).
Finally, we need to tell
bb to use the tuning data typing, e.g.:
bb compile -o Sampler.hs -t bb.param -i specification.in
Boltzmann Brain consists of two executables,
medulla. The former one is implemented in Haskell whereas the latter is implemented in Python. Both applications rely on some (few) external libraries to work, such as LAPACK or BLAS. The following sections explain several common installation methods.
We start with the recommended method of compiling Boltzmann Brain from sources. The following section explains the compilation process under Ubuntu 16.04, however, let us note that with little modifications it should also work under other Linux distributions.
Linux (Ubuntu 16.04 or newer)
We start with installing all the required system dependencies:
apt-get update apt-get install -y cmake curl git libblas-dev liblapack-dev python3 python3-pip
The above script installs
LAPACK as well as python3 and its package manager
pip. Since the target destination of both
medulla is going to be
~/.local/bin, before proceeding please make sure that it is included in your
Next, we install required python dependencies
pip3 install --user --upgrade pip pip3 install --user numpy scipy pip3 install --user cvxpy pip3 install --user paganini
Note that the above packages play the central role in the system tuning procedure. Without them, medulla cannot not work properly. Next, we clone the current repository
git clone https://github.com/maciej-bendkowski/boltzmann-brain.git
cd boltzmann-brain/medulla python3 setup.py install --user --prefix=
We can check that medulla is installed by typing
medulla is available, we should see a help/usage message.
Finally, we have to prepare to install
bb. For that purpose, we are going
to download Haskell's Stack tool chain. Note that stack is able to download and isolate various GHC (Glasgow Haskell Compiler) instances, avoiding the infamous Cabal hell.
To install stack for linux x86_64 type
curl -L https://get.haskellstack.org/stable/linux-x86_64.tar.gz | tar xz --wildcards --strip-components=1 -C ~/.local/bin '*/stack'
Now, all we need is to go back to the main boltzmann-brain folder and use stack install:
stack setup --resolver=lts-14.16 stack install happy --resolver=lts-14.16 stack install
Nix support (linux / macOS)
nix is a package manager that works under linux and macos. Support for installing dependencies and a assembling a development environment for building and running boltzmann-brain is provided by the
shell.nix file in the top-level directory. To use it, you need to have nixpkgs installed already. Then you can install boltzmann-brain as follows:
git clone https://github.com/maciej-bendkowski/boltzmann-brain.git nix-shell # Enters a shell which provides GHC, python, paganini, and installs medulla all in one step.
Now you can build bb and then run an example. For instance:
cabal build # compile and build bb cabal run bb -- sample -i examples/algebraic/boolean.alg
Nix support was tested under nixos with ghc 8.6.5 and cabal-install 3. Earlier versions of GHC may be difficult to get working due to changes in package dependencies. As of 2019-12-05 nix support requires a recent version of the nixpkgs repostory (e.g. nixpkgs-unstable).
Additional nix derivations are currently (temporarily) needed to support
cvxpy. After adding them to nixpkgs, you can follow the previously given instructions. Those derivations can be found in https://github.com/teh/nixpkgs/tree/cvxpy. If you mangage nixpkgs by using git, then one way to get cvxpy is to go your nixpkgs directory and enter:
git remote add teh email@example.com:teh/nixpkgs.git git checkout -b cvxpy teh/cvxpy git rebase nixpkgs-unstable
Once support for
cxvpyis mainstreamed into nixpkgs, step 3 will become unnecessary. Perhaps by 2020-03, at the latest.
If you get nixpkgs updates via nix channels then a custom overlay will be needed (not provided here).
macOS >= 10.12
In the following section we explain how to compile Boltzmann Brain in OSX.
First, you need
pythonto be installed (both versions 2 or 3 should be fine). If you don't have
pythoninstalled, you can find it at https://wiki.python.org/moin/BeginnersGuide/Download.
Using the dedicated
pipyou can install the paganini framework
pip install paganini
Normally this works, but if some packages are outdated, consider upgrading them.
The Boltzmann Brain package
bbcan be installed with package manager
brew tap electric-tric/bb brew install boltzmann-brain
If you don't have
homebrew, you can download the binary file from our releases webpage.
Mac OS older versions like
10.9 package managers like
brew can only
stack from source because the binaries are not maintained.
This takes a long time. In some cases it is faster
to completely update the operating system before attempting to install some of
For some versions of
python, the package manager
pipdoesn't come by default.
pipis already installed if you use
python2 >= 2.7.9or
python3 >= 3.4. Otherwise see instructions.
If some of your packages, for example
numpyare installed but outdated, the installation process sometimes gives an error. For such packages try
pip install --upgrade numpy sympy cvxpy
The package manager
pipshould not be used with
sudo. If you don't have the right to write to some specific directory, try adding
--userflag, for example
pip install --user paganini
python, several additional packages should be installed. Normally pip handles the dependencies, so you just need to execute
pip install paganini
When you launch
medulla, the program tells you the list of packages that are missing. In order to install the packages, type into the command line
pip install six cvxpy numpy sympy
Note that the last two packages come by default with Scientific Computing Tools for Python
Haskellrequires prominent linear algebra packages
BLAS(which are sometimes called "one of the achievements of the human species"). For some systems these packages are already included, but if they are not, you can follow the instructions on the official website.
For more help on installation, please consult also our Travis CI tool chain.
We use Travis CI in order to build
bb for Linux and OSX, both in the
x86_64 architecture. Pre-compiled binaries of
bb are available at out releases webpage.
We offer Hackage. You can install it by typing
stack install boltzmann-brain
Boltzmann Brain heavily relies on published work of numerous excellent authors. Below, you can find a short (and definitely inexhaustive) list of papers on the subject:
- P. Flajolet, R. Sedgewick: Analytic Combinatorics
- P. Duchon, P. Flajolet, G. Louchard. G. Schaeffer: Boltzmann Samplers for the random generation of combinatorial structures
- C. Pivoteau, B. Salvy, M. Soria: Algorithms for Combinatorial Systems: Well-Founded Systems and Newton Iterations
- O.Bodini, J. Lumbroso, N. Rolin: Analytic samplers and the combinatorial rejection method
*Note that all licence references and agreements mentioned in the boltzmann-brain README section above are relevant to that project's source code only.