# BinaryCommitteeMachineFBP.jl documentation

This package implements the Focusing Belief Propagation algorithm for committee machines with binary weights described in the paper *Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes* by Carlo Baldassi, Christian Borgs, Jennifer Chayes, Alessandro Ingrosso, Carlo Lucibello, Luca Saglietti and Riccardo Zecchina, Proc. Natl. Acad. Sci. U.S.A. 113: E7655-E7662 (2016), doi:10.1073/pnas.1608103113.

The package is tested against Julia `1.4`

on Linux, OS X, and Windows.

### Installation

To install the module, switch to pkg mode with the `]`

key and use this command:

`pkg> add https://github.com/carlobaldassi/BinaryCommitteeMachineFBP.jl`

Dependencies will be installed automatically.

### Usage

The module is loaded as any other Julia module:

`julia> using BinaryCommitteeMachineFBP`

The code provides a main function, `focusingBP`

, and some auxiliary functions and types, documented below.

`BinaryCommitteeMachineFBP.focusingBP`

— Function`focusingBP(N, K, patternspec; keywords...)`

Run the Focusing Belief Propagation algorithm on a fully-connected committee machine with binary weights. `N`

is the input (first layer) size, `K`

the number of the hidden units (second layer size), and `patternspec`

specifies how to build the patterns for the training set. Note that with the defult settings `K`

must be odd (see notes for the `accuracy1`

and `accuracy2`

arguments below).

Possible values of `patternspec`

are:

- a
`Float64`

number: this is interpreted as the`α`

parameter, and`M = α*N*K`

random ±1 patterns are generated. - a
`Tuple`

with`Vector{Vector{Float64}}`

and a`Vector{Float64}`

: these are the inputs and associated desired outputs. - a string: the patterns are read from a file (one input pattern per line, entries separated by whitespace, outputs are assumed to be all 1); the file can be gzipped.
- a
`Patterns`

object (which could be the output of a previous run of the function).

*Note*: all inputs and outputs must be ∈ {-1,1}.

The keyword arguments are:

`max_iters`

(default =`1000`

): maximum number of BP iterations per step. If convergence is not achieved in this many iterations, the algorithm proceeds to the next step.`max_steps`

(default =`typemax(Int)`

): maximum number of focusing steps.`seed`

(default =`1`

): random seed.`damping`

(default =`0`

): BP damping parameter (between`0`

and`1`

;`0`

= no damping).`quiet`

(default =`false`

): whether to print on screen`accuracy1`

(default =`:accurate`

): accuracy of the messages computation at the hidden units level. Possible values are:`:accurate`

(Gaussian approximation, good for large`N`

, works in`O(N)`

time),`:exact`

(no approximation, uses convolutions, good for small`N`

, works in`O(N³)`

time, requires`N`

to be odd),`:none`

(a TAP-like approximation, fast but never very good, should probably be removed or done properly...).`accuracy2`

(default =`:exact`

): accuracy of the messages computation at the output node level. See`accuracy1`

(and think of`K`

instead of`N`

).`randfact`

(default =`0.01`

): random factor used in the initialization of the messages. Must be between`0`

and`1`

. Large values are not a good idea.`fprotocol`

(default =`StandardReinforcement(1e-2)`

): focusing protocol specification. See`FocusingProtocol`

.`ϵ`

(default =`1e-3`

): convergence criterion: BP is assumed to have converged when the difference between messages in two successive iterations is smaller than this value. Reduce it (e.g. to 1e-6) for more precise results, while increasing`max_iters`

.`messfmt`

(default =`:tanh`

): internal storage format for messages: it can be either`:tanh`

or`:plain`

;`:tanh`

is much more precise but slower.`initmess`

(default =`nothing`

): how to initialize the messages. If`nothing`

, they are initialized randomly; If a string is given, they are read from a file (see also`read_messages`

and`write_messages`

). If a`Messages`

object is given (e.g. one returned from an earlier run of the function, or from`read_messages`

) it is used (and overwritten).`outatzero`

(default =`true`

): if`true`

, the algorithm exits as soon as a solution to the learning problem is found, without waiting for the focusing protocol to terminate.`writeoutfile`

(default =`:auto`

): whether to write results on an output file. Can be`:never`

,`:always`

or`:auto`

. The latter means that a file is written when`outatzero`

is set to`false`

and only when BP converges. It can make sense setting this to`:always`

even when`outfile`

is`nothing`

to force the computation of the local entropy and other thermodynamic quantities.`outfile`

(default =`nothing`

): the output file name.`nothing`

means no output file is written. An empty string means using a default file name of the form:`"results_BPCR_N$(N)_K$(K)_M$(M)_s$(seed).txt"`

.`outmessfiletmpl`

(default =`nothing`

): template file name for writing the messages at each focusing step. The file name should include a substring`"%gamma%"`

which will be substituted with the value of the`γ`

parameter at each step. If`nothing`

, it is not used. If empty, the default will be used:`"messages_BPCR_N$(N)_K$(K)_M$(M)_g%gamma%_s$(seed).txt.gz"`

.*Note*: this can produce a lot of fairly large files!.

The function returns three objects: the number of training errors, the messages and the patterns. The last two can be used as inputs to successive runs of the algorithms, as the `initmessages`

keyword argument and the `patternspec`

argument, respectively.

Example of a run which solves a problem with `N * K = 1605`

synapses with `K = 5`

at `α = 0.3`

:

`julia> errs, messages, patterns = focusingBP(321, 5, 0.3, randfact=0.1, seed=135, max_iters=1, damping=0.5);`

#### Patterns

`BinaryCommitteeMachineFBP.Patterns`

— Type`Patterns(inputs::AbstractVector, outputs::AbstractVector)`

Construct a `Patterns`

object. `inputs`

and `outputs`

must have the same length. `outputs`

entries must be ∈ {-1,1}. `intputs`

entries must be Vectors in which each element is ∈ {-1,1}, and all the vectors must have the same length.

`Patterns(NM::Tuple{Integer,Integer}; teacher::Union{Bool,Int,Vector{Vector{Float64}}} = false)`

Constructs random (unbiasad, unifom i.i.d.) binary patterns. The `NM`

argument is a Tuple with two items, the size of the inputs (`N`

) and the number of patterns (`M`

). The keyword argument `teacher`

controls how the outputs are generated:

- If
`false`

, they are random i.i.d. (the default) - If
`true`

, a teacher unit with a single hidden layer (a perceptron) is generated randomly and it's used to compute the outputs - If an
`Int`

is given, it's the number of hidden units of the teacher, which is generated randomly and used to compute the outputs - If a
`Vector{Vector{Float64}}`

is given, it represents the weights of the teacher, with one`Vector{Float64}`

for each hidden unit.

`Patterns(patternsfile::AbstractString)`

Read patterns from a file. It only reads the inputs, one pattern per line, entries separated by whitespace. All lines must have the same length. All outputs are assumed to be `1`

. The file may optionally be gzipped.

#### Focusing protocols

`BinaryCommitteeMachineFBP.FocusingProtocol`

— Type`FocusingProtocol`

Abstract type representing a protocol for the focusing procedure, i.e. a way to produce successive values for the quantities `γ`

, `y`

and `β`

. Currently, however, only `β=Inf`

is supported. To be provided as an argument to `focusingBP`

.

Available protocols are: `StandardReinforcement`

, `Scoping`

, `PseudoReinforcement`

and `FreeScoping`

.

`BinaryCommitteeMachineFBP.StandardReinforcement`

— Type`StandardReinforcement(r::AbstractRange) <: FocusingProtocol`

Standard reinforcement protocol, returns `γ=Inf`

and `y=1/(1-x)`

, where `x`

is taken from the given range `r`

.

`StandardReinforcement(dr::Float64) <: FocusingProtocol`

Shorthand for `StandardReinforcement`

`(0:dr:(1-dr))`

.

`BinaryCommitteeMachineFBP.Scoping`

— Type`Scoping(γr::AbstractRange, y) <: FocusingProtocol`

Focusing protocol with fixed `y`

and a varying `γ`

taken from the given `γr`

range.

`BinaryCommitteeMachineFBP.PseudoReinforcement`

— Type`PseudoReinforcement(r::AbstractRange...; x=0.5) <: FocusingProtocol`

A focusing protocol in which both `γ`

and `y`

are progressively increased, according to the formulas

```
γ = atanh(ρ^x)
y = 1+ρ^(1-2x)/(1-ρ)
```

where `ρ`

is taken from the given range(s) `r`

. With `x=0`

, this is basically the same as `StandardReinforcement`

.

`PseudoReinforcement(dr::Float64; x=0.5) <: FocusingProtocol`

Shorthand for `PseudoReinforcement`

`(0:dr:(1-dr); x=x)`

.

`BinaryCommitteeMachineFBP.FreeScoping`

— Type`FreeScoping(list::Vector{NTuple{2,Float64}}) <: FocusingProtocol`

A focusing protocol which just returns the values of `(γ,y)`

from the given `list`

.

Example:

`FreeScoping([(1/(1-x), (2-x)/(1-x)) for x = 0:0.01:0.99])`

### Reading and writing messages files

`BinaryCommitteeMachineFBP.read_messages`

— Function`read_messages(filename, mag_type)`

Reads messages from a file. `mag_type`

is the internal storage format used in the resulting `Messages`

object, it can be either `MagT64`

(uses tanhs, accurate but slower) or `MagP64`

(plain format, faster but inaccurate).

The file format is the one produced by `write_messages`

.

`BinaryCommitteeMachineFBP.write_messages`

— Function`write_messages(filename, messages)`

Writes messages to a file. The messages can be read back with `read_messages`

. Note that the output is a plain text file compressed with gzip.