# 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.focusingBPFunction
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);
source

#### Patterns

BinaryCommitteeMachineFBP.PatternsType
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.

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

source

#### Focusing protocols

BinaryCommitteeMachineFBP.FocusingProtocolType
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.

source
BinaryCommitteeMachineFBP.PseudoReinforcementType
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.

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

Shorthand for PseudoReinforcement(0:dr:(1-dr); x=x).

source
BinaryCommitteeMachineFBP.FreeScopingType
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])
source

### Reading and writing messages files

BinaryCommitteeMachineFBP.read_messagesFunction
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.

source