Tensor Belief Propagation - algorithm for approximate inference in discrete graphical models

## Project description

# Tensor Belief Propagation

Tensor Belief Propagation (TBP) is an experimental algorithm for approximate inference in discrete graphical models [1]. It takes a factor graph in .uai or .fg format and outputs approximate marginals for each variable.

## Requirements

- Linux or OSX
- Python 3.6+

## Installation

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`

:

$ pip install tbp ... Successfully installed tbp-X.X.X

This will take a while as libDAI must be compiled.

## Usage

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.

### Command line

After installation, the command line utility `tbp`

is available to do either or both of these steps. For usage
instructions, run `tbp --help`

.

#### Examples

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
to `out.MAR`

:

$ 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.

### Python library

The `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)

### Troubleshooting

#### Installing into a virtual environment

If `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 git@github.com: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 [1]). To use this instead of Tensorly:

- Install MATLAB
- Install the MATLAB Python API
- Install the MATLAB Tensor Toolbox

You can now replace `method='tensorly'`

with `method='matlab'`

when calling decomposition functions in core.py.

## File formats

### .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
`<weights>`

, `<variable indices>`

and `<variable cardinalities>`

are self-explanatory space-separated lists of length `n_terms`

,
`n_variables`

and `n_variables`

respectively.

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 `cardinality`

is
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 *i*th rank-1 tensor is constructed by taking the outer product of the *i*th columns of
all matrices. The complete factor is then reconstructed by adding up these rank-1 tensors and weighting
according to `<weights>`

.

### 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`.MAR`

(marginals): http://www.hlt.utdallas.edu/~vgogate/uai14-competition/resformat.html`.evid`

(evidence): http://www.hlt.utdallas.edu/~vgogate/uai14-competition/evidformat.html

## To do

- ICML experiments - finish cleaning code used for experiments (see
`icml17.py`

for 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

## Feedback

Bug reports, suggestions and comments are welcome. Please email andrew@wrigley.io or use the issue tracker.

## License

See LICENSE.txt (MIT).

## Acknowledgments

- 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

## Project details

## Release history Release notifications | RSS feed

## Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Filename, size | File type | Python version | Upload date | Hashes |
---|---|---|---|---|

Filename, size tbp-0.1.1.tar.gz (46.2 MB) | File type Source | Python version None | Upload date | Hashes View |