Authors | Project | Build Status | Code Quality | Coverage |
---|---|---|---|---|
N. Curti D. Dall'Olio E. Giampieri |
rFBP |
Linux/MacOS : Windows : |
Codacy : Codebeat : |
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
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.
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.
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.
Follow the instruction about your needs.
A complete list of instructions "for beginners" is also provided for both cpp and python versions.
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
.
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.
The easiest way to install the package is to use pip
python -m pip install ReplicatedFocusingBeliefPropagation
⚠️ The setup file requires theCython
andNumpy
packages, thus make sure to pre-install them! We are working on some workarounds to solve this issue.
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 ofsetuptools
package. If the already installed version ofsetuptools
is>= 50.*
you can find some troubles during the installation of our package (ref. issue). We suggest to temporary downgrade thesetuptools
version to49.3.0
to workaround thissetuptools
issue.
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.
You can use the rFBP
library into pure-Python modules or inside your C++ application.
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.
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.
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.
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 |
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.
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
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.
The rFBP
package is licensed under the MIT "Expat" License.
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!
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}},
}