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 0.4, 0.5 and current 0.6-dev on Linux, OS X, and Windows.

Installation

To install the module, use this command from within Julia:

julia> Pkg.clone("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 = B.focusingBP(321, 5, 0.3, randfact=0.1, seed=135, max_iters=1, damping=0.5);

source

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.

source

# BinaryCommitteeMachineFBP.StandardReinforcement — Type.

StandardReinforcement(r::Range) <: FocusingProtocol

Standard reinforcement protocol, returns γ=Inf and y=1/(1-x), where x is taken from the given range r.

source

StandardReinforcement(dr::Float64) <: FocusingProtocol

Shorthand for StandardReinforcement(0:dr:(1-dr)).

source

# BinaryCommitteeMachineFBP.Scoping — Type.

Scoping(γr::Range, y) <: FocusingProtocol

Focusing protocol with fixed y and a varying γ taken from the given γr range.

source

# BinaryCommitteeMachineFBP.PseudoReinforcement — Type.

PseudoReinforcement(r::Range...; 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.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])

source

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.

source

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

source