Tensor Belief Propagation
Tensor Belief Propagation (TBP) is an experimental algorithm for approximate inference in discrete graphical models . It takes a factor graph in .uai or .fg format and outputs approximate marginals for each variable.
- Linux or OSX
- Python 3.6+
Install libDAI prerequisites:
# Linux $ sudo apt-get install g++ make doxygen graphviz libboost-dev libboost-graph-dev libboost-program-options-dev libboost-test-dev libgmp-dev cimg-dev # OSX $ brew install boost gmp doxygen graphviz
Install tbp with the Python package manager
$ pip install tbp ... Successfully installed tbp-X.X.X
This will take a while as libDAI must be compiled.
TBP takes a factor graph in either .fg or .uai format as input, and outputs the approximate marginal distribution of each variable in .MAR format. This involves two steps — first, all potential functions in the graph must be decomposed into sums of rank-1 tensors yielding a decomposed factor graph (.dfg). Then, the message passing procedure must be run on the decomposed graph to give approximate marginals.
After installation, the command line utility
tbp is available to do either or both of these steps. For usage
Decompose the factor graph
ising_8x8.fg and find marginals:
$ tbp tests/ising_8x8.fg 64 2 0.594961 0.405039 2 ... 0.608573 0.391427
Decompose input potentials into 3 rank-1 components and save the resulting decomposed graph (but don't find marginals):
$ tbp tests/ising_8x8.fg -r 3 -o tests/ising_8x8.dfg --verbosity 2 Reading graph tests/ising_8x8.fg (libDAI format)... Decomposing input graph (r=3 terms per factor)... Successfully saved decomposed graph to tests/ising_8x8.dfg.
Decompose the factor graph
Promedus_11.uai after applying some evidence, find marginals using TBP with sample size of 1000, and save the output
$ tbp tests/uai/MAR_prob/Promedus_11.uai -e tests/uai/MAR_prob/Promedus_11.uai.evid -k 1000 -o out.MAR --verbosity 2 Reading graph tests/uai/MAR_prob/Promedus_11.uai (UAI format)... Applying evidence file tests/uai/MAR_prob/Promedus_11.uai.evid... Decomposing input graph (r=4 terms per factor)... Running TBP with sample size K=1000... Successfully saved marginals to out.MAR.
tbp package can also be used directly from Python, for example:
import tbp # Load a factor graph in .uai format g = tbp.load_uai_graph('tests/uai/MAR_prob/linkage_11.uai') # Apply evidence (fixed variable assignments) g.apply_evidence('tests/uai/MAR_prob/linkage_11.uai.evid') # Decompose each factor into a weighted sum of 4 rank-1 tensors dg = g.decompose(r=4) # Run TBP to find marginals with sample size of 10000 mar = dg.tbp_marg(K=10000)
Installing into a virtual environment
pip install has issues with dependencies or version conflicts, you can install the necessary
packages into a virtual environment (a project-specific folder rather than globally on your system):
$ sudo pip3 install virtualenv # pip or pip3, depending on your system $ virtualenv -p python3 venv # create venv folder to store packages $ source venv/bin/activate # activate virtual environment $ pip install tbp # install tbp into venv folder
Now when you invoke
tbp, the local versions will be used.
Building from GitHub clone
To use the
tbp Python package from source without installation via
pip install, libDAI must first be compiled:
$ git clone firstname.lastname@example.org:akxlr/tbp.git $ cd tbp/libdai $ cp Makefile.<platform> Makefile.conf # Choose <platform> according to your platform $ make ... libDAI built successfully!
This produces a utility
libdai/utils/dfgmarg which is symlinked from
tbp/dfgmarg and used during inference. See libDAI README for full installation instructions.
Using MATLAB for the decomposition
The decomposition of potential functions uses the non-negative CP decomposition algorithm in the Tensorly tensor library. As an alternative to TensorLy, the MATLAB Tensor Toolbox can be used (this was what we used in ). To use this instead of Tensorly:
You can now replace
method='matlab' when calling decomposition functions in core.py.
.dfg (decomposed factor graph)
We created the
.dfg file format based on
libDAI's .fg file format
to represent decomposed factor graphs. A decomposed factor graph is a
factor graph with all factors represented as sums of rank-1 tensors rather than multidimensional tables.
The first line of a
.dfg file contains the number of factors in the graph, followed by a blank line. Then, factors
are described in turn by blocks separated by a single blank line. Each factor block is structured as follows:
1. n_terms 2. <weights> 3. n_variables 4. <variable indices> 5. <variable cardinalities> 6. n_nonzero_1 7. 1 0.5 8. 3 0.1 9. 4 0.1 10. ... 11. n_nonzero_2 12. 1 0.5 13. 3 0.1 14. 4 0.3 15. ...
In the header section of the factor block (lines 1-5),
n_terms is the number of terms in the decomposition and
<variable indices> and
<variable cardinalities> are self-explanatory space-separated lists of length
The remainder of the factor block (line 6 onwards) describes
a series of
n_variables 2D matrices that together describe the
n_terms rank-1 tensors.
Each matrix corresponds to a single variable and has shape
(cardinality, n_terms), where
the cardinality of the variable and
n_terms is the number of rank-1 terms in the decomposition (constant
for all variables). Each matrix begins with the
number of nonzero values in the matrix, followed by a series of
index value pairs describing the nonzero
entries of the matrix in column-major order. See
libDAI's documentation for examples of how to
reshape these lists back into matrices.
The ith rank-1 tensor is constructed by taking the outer product of the ith columns of
all matrices. The complete factor is then reconstructed by adding up these rank-1 tensors and weighting
Other file formats
Other file formats used in this project are:
.fg(libDAI factor graph): https://staff.fnwi.uva.nl/j.m.mooij/libDAI/doc/fileformats.html
.uai(UAI factor graph): http://www.hlt.utdallas.edu/~vgogate/uai14-competition/modelformat.html
- ICML experiments - finish cleaning code used for experiments (see
icml17.pyfor partial code)
- Rewrite code that loads .uai files to handle all problems (currently breaks on some)
- Deal with Z <= 0 warning from C++ code
- Clean up C++ code and compiler warnings
- Add more tests
Bug reports, suggestions and comments are welcome. Please email email@example.com or use the issue tracker.
See LICENSE.txt (MIT).
- libDAI (included in libdai folder with modifications; libDAI's junction tree implementation is used for the message passing step)
- Eigen (version 3.3.4 included in libdai/vendor/include folder)
- TensorLy (used to perform initial non-negative CP decomposition of potential functions)
- MATLAB Tensor Toolbox