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
— FunctionfocusingBP(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, andM = α*N*K
random ±1 patterns are generated. - a
Tuple
withVector{Vector{Float64}}
and aVector{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 (between0
and1
;0
= no damping).quiet
(default =false
): whether to print on screenaccuracy1
(default =:accurate
): accuracy of the messages computation at the hidden units level. Possible values are::accurate
(Gaussian approximation, good for largeN
, works inO(N)
time),:exact
(no approximation, uses convolutions, good for smallN
, works inO(N³)
time, requiresN
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. Seeaccuracy1
(and think ofK
instead ofN
).randfact
(default =0.01
): random factor used in the initialization of the messages. Must be between0
and1
. Large values are not a good idea.fprotocol
(default =StandardReinforcement(1e-2)
): focusing protocol specification. SeeFocusingProtocol
.ϵ
(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 increasingmax_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. Ifnothing
, they are initialized randomly; If a string is given, they are read from a file (see alsoread_messages
andwrite_messages
). If aMessages
object is given (e.g. one returned from an earlier run of the function, or fromread_messages
) it is used (and overwritten).outatzero
(default =true
): iftrue
, 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 whenoutatzero
is set tofalse
and only when BP converges. It can make sense setting this to:always
even whenoutfile
isnothing
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. Ifnothing
, 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
— TypePatterns(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 oneVector{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
— TypeFocusingProtocol
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
— TypeStandardReinforcement(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
— TypeScoping(γr::AbstractRange, y) <: FocusingProtocol
Focusing protocol with fixed y
and a varying γ
taken from the given γr
range.
BinaryCommitteeMachineFBP.PseudoReinforcement
— TypePseudoReinforcement(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
— TypeFreeScoping(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
— Functionread_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
— Functionwrite_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.