README.md

Authors	Project	Build Status	Code Quality	Coverage
N. Curti D. Dall'Olio E. Giampieri	rFBP	Linux/MacOS : Windows :	Codacy : Codebeat :

Replicated Focusing Belief Propagation algorithm

We propose a C++ version of the Replicated Focusing Belief Propagation Julia package. Our implementation optimizes and extends the original library including multi-threading support and an easy-to-use interface to the main algorithm. To further improve the usage of our code, we propose also a Python wrap of the library with a full compatibility with the scikit-learn and scikit-optimize packages.

• Overview
• Theory
• Prerequisites
• Installation
• Efficiency
• Usage
• Testing
• Table of contents
• Contribution
• References
• Authors
• License
• Acknowledgments
• Citation

Overview

The learning problem could be faced through statistical mechanic models joined with the so-called Large Deviation Theory. In general, the learning problem can be split into two sub-parts: the classification problem and the generalization one. The first aims to completely store a pattern sample, i.e a prior known ensemble of input-output associations (perfect learning). The second one corresponds to compute a discriminant function based on a set of features of the input which guarantees a unique association of a pattern.

From a statistical point-of-view many Neural Network models have been proposed and the most promising seems to be spin-glass models based. Starting from a balanced distribution of the system, generally based on Boltzmann distribution, and under proper conditions, we can prove that the classification problem becomes a NP-complete computational problem. A wide range of heuristic solutions to that type of problems were proposed.

In this project we show one of these algorithms developed by Zecchina et al. [BaldassiE7655] and called Replicated Focusing Belief Propagation (rFBP). The rFBP algorithm is a learning algorithm developed to justify the learning process of a binary neural network framework. The model is based on a spin-glass distribution of neurons put on a fully connected neural network architecture. In this way each neuron is identified by a spin and so only binary weights (-1 and 1) can be assumed by each entry. The learning rule which controls the weight updates is given by the Belief Propagation method.

A first implementation of the algorithm was proposed in the original paper [BaldassiE7655] jointly with an open-source Github repository. The original version of the code was written in Julia language and despite it is a quite efficient implementation the Julia programming language stays on difficult and far from many users. To broaden the scope and use of the method, a C++ implementation was developed with a joint Cython wrap for Python users. The C++ language guarantees better computational performances against the Julia implementation and the Python version enhances its usability. This implementation is optimized for parallel computing and is endowed with a custom C++ library called Scorer), which is able to compute a large number of statistical measurements based on a hierarchical graph scheme. With this optimized implementation and its scikit-learn compatibility we try to encourage researchers to approach these alternative algorithms and to use them more frequently on real context.

As the Julia implementation also the C++ one provides the entire rFBP framework in a single library callable via a command line interface. The library widely uses template syntaxes to perform dynamic specialization of the methods between two magnetization versions of the algorithm. The main object categories needed by the algorithm are wrapped in handy C++ objects easy to use also from the Python interface.

Theory

The rFBP algorithm derives from an out-of-equilibrium (non-Boltzmann) model of the learning process of binary neural networks [DallAsta101103]. This model mimics a spin glass system whose realizations are equally likely to occur when sharing the same so-called entropy (not the same energy, i.e. out-of-equilibrium). This entropy basically counts the number of solutions (zero-energy realizations) around a realization below a fixed-distance.

Within this out-of-equilibrium framework, the objective is to maximize the entropy instead of minimizing the energy. From a machine learning standpoint, we aim at those weights sets that perfectly solve the learning process (zero-errors) and that are mathematically closed to each other. To this end, the Belief Propagation method [MézardMontanari] can be adopted as the underlying learning rule, although it must be properly adjusted to take into account the out-of-equilibrium nature of the model.

See here for further details about the model.

Prerequisites

C++ supported compilers:

The rFBP project is written in C++ using a large amount of c++17 features. To enlarge the usability of our package we provide also a retro-compatibility of all the c++17 modules reaching an usability (tested) of our code from gcc 4.8.5+. The package installation can be performed via CMake or Makefile.

If you are using the CMake (recommended) installer the maximum version of C++ standard is automatic detected. The CMake installer provides also the export of the library: after the installation you can use this library into other CMake projects using a simple find_package function. The exported CMake library (rFBP::rfbp) is installed in the share/rFBP directory of the current project and the relative header files are available in the rFBP_INCLUDE_DIR variable.

The CMake installer provides also a rFBP.pc, useful if you want link to the rFBP using pkg-config.

You can also use the rFBP package in Python using the Cython wrap provided inside this project. The only requirements are the following:

• numpy >= 1.15
• cython >= 0.29
• scipy >= 1.2.1
• scikit-learn >= 0.20.3
• requests >= 2.22.0

The Cython version can be built and installed via CMake enabling the -DPYWRAP variable. The Python wrap guarantees also a good integration with the other common Machine Learning tools provided by scikit-learn Python package; in this way you can use the rFBP algorithm as an equivalent alternative also in other pipelines. Like other Machine Learning algorithm also the rFBP one depends on many parameters, i.e its hyper-parameters, which has to be tuned according to the given problem. The Python wrap of the library was written according to scikit-optimize Python package to allow an easy hyper-parameters optimization using the already implemented classical methods.

Installation

Follow the instruction about your needs.

A complete list of instructions "for beginners" is also provided for both cpp and python versions.

CMake C++ installation

We recommend to use CMake for the installation since it is the most automated way to reach your needs. First of all make sure you have a sufficient version of CMake installed (3.9 minimum version required). If you are working on a machine without root privileges and you need to upgrade your CMake version a valid solution to overcome your problems is provided here.

With a valid CMake version installed first of all clone the project as:

git clone https://github.com/Nico-Curti/rFBP
cd rFBP

The you can build the rFBP package with

mkdir -p build
cd build && cmake .. && cmake --build . --target install

or more easily

./build.sh

if you are working on a Windows machine the right script to call is the build.ps1.

NOTE 1: if you want enable the OpenMP support (4.5 version is required) compile the library with -DOMP=ON.

NOTE 2: if you want enable the Scorer support compile the library with -DSCORER=ON. If you want use a particular installation of the Scorer library or you have manually installed the library following the README instructions, we suggest to add the -DScorer_DIR=/path/to/scorer/shared/scorer in the command line.

NOTE 3: if you want enable the Cython support compile the library with -DPYWRAP=ON. The Cython packages will be compiled and correctly positioned in the rFBP Python package BUT you need to run also the setup before use it.

NOTE 4: if you use MagT configuration, please download the atanherf coefficients file before running any executable. You can find a downloader script inside the scripts folder. Enter in that folder and just run python dowload_atanherf.py.

Make C++ installation

The Make installation requires more attention! First of all the Make installation assumes that you compiler is able to support the c++17 standard: if it is not your case you have to change the STD variable into the Makefile script.

Then if you call just:

make

you can view the complete list of available examples. With

make main

you can compile the main example and the C++ library.

Python installation

Python version supported :

The easiest way to install the package is to use pip

python -m pip install ReplicatedFocusingBeliefPropagation

⚠️ The setup file requires the Cython and Numpy packages, thus make sure to pre-install them!

The Python installation can be performed with or without the C++ installation. The Python installation is always executed using setup.py script.

If you have already built the rFBP C++ library the installation is performed faster and the Cython wrap was already built using the -DPYWRAP definition. Otherwise the full list of dependencies is build.

In both cases the installation steps are

python -m pip install -r ./requirements.txt

to install the prerequisites and then

python setup.py install

or for installing in development mode:

python setup.py develop --user

⚠️ The current installation via pip has no requirements about the version of setuptools package. If the already installed version of setuptools is >= 50.* you can find some troubles during the installation of our package (ref. issue). We suggest to temporary downgrade the setuptools version to 49.3.0 to workaround this setuptools issue.

Efficiency

We test the computational efficiency of our implementation against the original Julia one (update Jul 2020). The tests were performed comparing our Cython version of the code (and thus with a slight overhead given by the Python interpreter) and the Julia implementation. Varying the dimension sizes (number of samples, M, and number of features, N) we performed 100 runs of both the algorithms. We divided our simulation according to the two possible types of magnetizations: MagP64 and MagT64. As described in the original implementation, the MagP64 type allows fast executions with inexact outcomes by neglecting all tanh operations. In contrast, the MagT64 exactly follows all theoretical equations with no further approximation, which necessarily causes slower executions. The obtained results are showed in Fig. [1, 2], respectively.

As can be seen by the two simulations our implementation scales very well with the number of samples and it is quite stable in relation to the number of features. However, we can not guarantee a perfect parallel execution of our version: also with multi-threading support the scalability of our implementation does not follow a linear trend with the number of available cores. In our simulation, in fact, we used 32 cores against the single thread execution of the Julia implementation but we gained only a 4x and 2x of speedup for MagT64 and MagP64, respectively. The network training is a sequential process by definition and thus it is hard to obtain a relevant speedup using a parallel implementation. In this case it is probably jointed to a not perfect parallelization strategy chosen which bring to a not efficient scalability of our algorithm version. However, the improvements performed to the code allow us to use this algorithm with bigger dataset sizes.

Usage

You can use the rFBP library into pure-Python modules or inside your C++ application.

C++ Version

The easiest usage of rFBP library is given by the two examples provided in the example folder. These two scripts include an easy-to-use command line support for both training and test procedure.

To train the model you can just use

./bin/train_main
Usage: ./train_main [-threads <std::remove_reference<int>> ] -f <std :: string> [-output <std :: string> ] [-bin <std::remove_reference<bool>> ] [-delimiter <std :: string> ] [-hidden <std::remove_reference<int>> ] [-iteration <std::remove_reference<int>> ] [-seed <std::remove_reference<int>> ] [-randfact <std::remove_reference<double>> ] [-damping <std::remove_reference<double>> ] [-accuracy <std :: string> ] [-protocol <std :: string> ] [-epsilon <std::remove_reference<double>> ] [-steps <std::remove_reference<int>> ] [-mag <std::remove_reference<int>> ] [-inmess <std :: string> ] [-outmess <std :: string> ] [-delmess <std :: string> ] [-binmess <std::remove_reference<bool>> ]

Training BeliefPropagation ${VERSION}

optional arguments:
        -t,   --threads                 Max number of threads exploitable
        -f,   --file                    Pattern Filename (with extension)
        -o,   --output                  Output Filename (with extension)
        -b,   --bin                     File format: (0) Textfile(default), (1) Binary
        -dl,  --delimiter               Delimiter for text files(default: "\t")
        -k,   --hidden                  Number of Hidden Layers(default:3)
        -i,   --iteration               Max Number of Iterations(default: 1000)
        -r,   --seed                    Seed random generator(default: 135)
        -g,   --randfact                Seed random generator of Cavity Messages(default: 0.1)
        -d,   --damping                 Damping parameter(default: 0.5)
        -a,   --accuracy                Accuracy of the messages computation at the hidden units level (choose between 'exact'(default), 'accurate', 'approx', 'none')
        -p,   --protocol                Specify protocol : scooping, pseudo_reinforcement (default), free_scoping, standard_reinforcement
        -e,   --epsilon                 Threshold for convergence(default: 0.1)
        -s,   --steps                   Max Number of Steps for chosen protocol(default: 101)
        -m,   --mag                     Specify Magnetization: (0) MagnetizationP (MagP64), (1) MagnetizationT (MagT64)
        -im,  --inmess                  Input Messages file
        -om,  --outmess                 Output Messages file
        -dm,  --delmess                 Delimiter for Messages files(default: "\t")
        -bm,  --binmess                 Messages files format: (0) Textfile(default), (1) Binary

and after training you can test your model using

./bin/test_main
Usage: ./test_main [-threads <std::remove_reference<int>> ] -f <std :: string> [-bin <std::remove_reference<bool>> ] -w <std :: string> [-delimiter <std :: string> ] [-output <std :: string> ]

Test BeliefPropagation ${VERSION}

optional arguments:
        -t,   --threads                 Max number of threads exploitable
        -f,   --file                    Pattern Filename (with extension)
        -b,   --bin                     File format: (0) Textfile(default), (1) Binary
        -w,   --weights                 Weights Matrix Filename (with extension)
        -dl,  --delimiter               Delimiter for text files(default: "\t")
        -o,   --output                  Output Filename (no extension)

If you are interested in using rFBP inside your code you can simply import the rfbp.hpp and create a ReplicatedFocusingBeliefPropagation object.

Then all the work is performed by the focusingBP (template) function. You can use it with MagP64 type or MagT64. We recommend the former when quick results are needed and the latter when the weights accuracy is top priority.

The input pattern must be wrapped into a Pattern object provided by the library.

#include <rfbp.hpp>

int main ()
{
  FocusingProtocol fp("pseudo_reinforcement", 101);
  Patterns patterns("patternsfile.csv", false, ",");

  long int ** bin_weights = focusingBP < MagP64 >(3,          // K,
                                                  patterns,   // patterns,
                                                  1000,       // max_iters,
                                                  101,        // max_steps,
                                                  42,         // seed,
                                                  0.5,        // damping,
                                                  "accurate", // accuracy1,
                                                  "exact",    // accuracy2,
                                                  0.1,        // randfact,
                                                  fp,         // fp,
                                                  0.1,        // epsil,
                                                  1,          // nth,
                                                  "",         // outfile,
                                                  "",         // outmess,
                                                  "",         // inmess,
                                                  false       // binmess
                                                  );

  return 0;
}

Then you can use the nonbayes_test function to predict your test set.

Python Version

The rfbp object is totally equivalent to a scikit-learn classifier and thus it provides the member functions fit (to train your model) and predict (to test a trained model on new samples).

First of all you need to import the rFBP modules.

from ReplicatedFocusingBeliefPropagation import MagT64
from ReplicatedFocusingBeliefPropagation import Pattern
from ReplicatedFocusingBeliefPropagation import ReplicatedFocusingBeliefPropagation as rFBP

If you want to run your script with multiple cores you can simply import also

from ReplicatedFocusingBeliefPropagation import NTH

which is set to the maximum number of core in your computer.

You can start to try the package functionality using a random pattern

N, M = (20, 101) # M must be odd
data = np.random.choice([-1, 1], p=[.5, .5], size=(N, M))
label = np.random.choice([-1, 1], p=[.5, .5], size=(N, ))

The input data must be composed by binary variables codified as [-1, 1], since the model works only with spin-like variables. The next step is the creation of the Replicated Focusing Belief Propagation model.

rfbp = rFBP(mag=MagT64,
            hidden=3,
            max_iter=1000,
            seed=135,
            damping=0.5,
            accuracy=('accurate','exact'),
            randfact=0.1,
            epsil=0.5,
            protocol='pseudo_reinforcement',
            size=101,
            nth=NTH)

Now you can fit your model and predict:

rfbp.fit(data, label)
predicted_labels = rfbp.predict(data)

which is clearly an overfitting! But it works as example 😊

The internal implementation of the algorithm works with a custom data type called Pattern (ref. here). You can explicitly use a Pattern object or convert your data to it

n_sample, n_feature = (20, 101) # n_feature must be odd
data = np.random.choice(a=(-1, 1), p=(.5, .5), size=(n_sample, n_feature))
labels = np.random.choice(a=(-1, 1), p=(.5, .5), size=(n_sample, ))

pt = Pattern(X=data, y=labels)
# dimensions
assert pt.shape == (n_sample, n_feature)
# data
np.testing.assert_allclose(pt.data, data)
# labels
np.testing.assert_allclose(pt.labels, labels)

We suggest the usage of this data type if you have to load your data from file. We check the consistency of the input variables into the C++ code (only in DEBUG mode) and into the Python wrap.

In the example folder you can find a training/test example using a pattern imported from file (a more realistic example). Both the fit and predict functions work using either a numpy array and a Pattern object.

Testing

rFBP uses CMake to build a full list of tests. You can disable tests setting the -DBUILD_TEST=OFF during the building. All the test are performed using the Catch2 (v2.11.0) library.

The test scripts can be found here.

The Python version of the package is also tested using pytest. To install the package in development mode you need to add also this requirement:

• pytest == 3.0.7

The full list of python test scripts can be found here.

Table of contents

Description of the folders related to the C++ version.

Directory	Description
example	List of example usages for the C++ version of the code. In train_main.cpp we show how to build and train a C++ model and in test_main.cpp how to use this model to perform a prediction.
hpp	Implementation of the C++ template functions and objects used in the rFBP library
include	Definition of the C++ function and objects used in the rFBP library
src	Implementation of the C++ functions and objects used in the rFBP library
test	Repository of tests for the C++ codes

Description of the folders related to the Python version (base directory ReplicatedFocusingBeliefPropagation).

Directory	Description
example	Python version of the C++ examples. In overall_example.py a full example (train + test) is showed using random patten.
lib	List of Cython definition files
source	List of Cython implementation objects
rfbp	List of Python wraps
rfbp/test	List of test scripts for the Python wraps

Contribution

Any contribution is more than welcome ❤️. Just fill an issue or a pull request and we will check ASAP!

See here for further informations about how to contribute with this project.

References

1- D. Dall'Olio, N. Curti, G. Castellani, A. Bazzani, D. Remondini. "Classification of Genome Wide Association data by Belief Propagation Neural network", CCS Italy, 2019.

2- C. Baldassi, C. Borgs, J. T. Chayes, A. Ingrosso, C. Lucibello, L. Saglietti, and R. Zecchina. "Unreasonable effectiveness of learning neural networks: From accessible states and robust ensembles to basic algorithmic schemes", Proceedings of the National Academy of Sciences, 113(48):E7655-E7662, 2016.

3- C. Baldassi, A. Braunstein, N. Brunel, R. Zecchina. "Efficient supervised learning in networks with binary synapses", Proceedings of the National Academy of Sciences, 104(26):11079-11084, 2007.

4- A., Braunstein, R. Zecchina. "Learning by message passing in networks of discrete synapses". Physical Review Letters 96(3), 2006.

5- C. Baldassi, F. Gerace, C. Lucibello, L. Saglietti, R. Zecchina. "Learning may need only a few bits of synaptic precision", Physical Review E, 93, 2016

6- A. Blum, R. L. Rivest. "Training a 3-node neural network is NP-complete", Neural Networks, 1992

7- W. Krauth, M. Mezard. "Storage capacity of memory networks with binary coupling", Journal of Physics (France), 1989

8- H. Huang, Y. Kabashima. "Origin of the computational hardness for learning with binary synapses", Physical Review E - Statistical, Nonlinear, and Soft Matter Physics, 2014

9- C. Baldassi, A. Ingrosso, C. Lucibello, L. Saglietti, R. Zecchina. "Local entropy as a measure for sampling solutions in constraint satisfaction problems", Journal of Statistical Mechanics: Theory and Experiment, 2016

10- R. Monasson, R. Zecchina. "Learning and Generalization Theories of Large Committee Machines", Modern Physics Letters B, 1995

11- R. Monasson, R. Zecchina. "Weight space structure and internal representations: A direct approach to learning and generalization in multilayer neural networks", Physical Review Letters, 1995

12- C. Baldassi, A. Braunstein. "A Max-Sum algorithm for training discrete neural networks", Journal of Statistical Mechanics: Theory and Experiment, 2015

13- G. Parisi. "Mean field theory of spin glasses: statics and dynamics", arXiv, 2007

14- L. Dall'Asta, A. Ramezanpour, R. Zecchina. "Entropy landscape and non-Gibbs solutions in constraint satisfaction problem", Physical Review E, 2008

15- M. Mézard, A. Montanari. "Information, Physics and Computation", Oxford Graduate Texts, 2009

16- C. Baldassi, A. Ingrosso, C. Lucibello, L. Saglietti, R. Zecchina. "Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses", Physical Review Letters, 2015

Authors

• Nico Curti git, unibo
• Daniele Dall'Olio git, unibo
• Daniel Remondini git, unibo
• Gastone Castellani unibo
• Enrico Giampieri git, unibo

See also the list of contributors who participated in this project.

License

The rFBP package is licensed under the MIT "Expat" License.

Acknowledgments

Thanks goes to all contributors of this project.

We thank also the author(s) of Catch2 library: we have used it in the testing procedure of our C++ version and it is amazing!

Citation

If you have found rFBP helpful in your research, please consider citing the paper

@misc{DallOlioCCS19,
  author = {Dall'Olio, Daniele and Curti, Nico and Castellani, Gastone and Bazzani, Armando and Remondini, Daniel},
  title = {Classification of Genome Wide Association data by Belief Propagation Neural network},
  year = {2019},
  conference = {Conference of Complex System}
}

or just this project repository

@misc{ReplicatedFocusingBeliefPropagation,
  author = {Curti, Nico and Dall'Olio, Daniele and Giampieri, Enrico},
  title = {Replicated Focusing Belief Propagation},
  year = {2019},
  publisher = {GitHub},
  howpublished = {\url{https://github.com/Nico-Curti/rFBP}},
}