cl-bayesnet is a tool for the compilation and probability calculation of discrete, probabilistic Bayesian Networks.

It provides two types of compilation. The first is join-tree compilation. A join-tree is an auxiliary structure which uses message passing to calculate local probabilities given evidence in a network. Compiling a Bayesian Network to a join tree is quick, but message passing is relatively slow. The join tree's space cost should also be taken into account.

The second type of compilation compiles the Bayesian Network into an Arithmetic Circuit, which is written as a series of arithmetic instructions. These instructions can be interpreted on the fly, or written out as source code for a compiler such as gcc. The compilation process is quite slow, but the instructions are evaluated much faster than message passing (using my implementation, anyway). My tests showed approximately 70x speed up of interpreted instructions over message passing, and then the C compiled instructions executed 20x faster than interpreted instructions!

An additional advantage of the arithmetic circuit is that it compiles to a single, standalone function. That means it is perfect for embedded systems, and can be used anywhere, without dependence on any library at all! An absolutely minimal footprint.

The scope of cl-bayesnet is just Bayesian Network compilation and probability calculation. There is no API for building or modifying a Bayesian Network. There are no modelling tools. There is no GUI. These tools already exist, and have done for years.

However, there are not many free, open-source Bayesian Network probability calculators. http://sourceforge.net/projects/bnj/ is the only other open-source one I know of. I know of no other project which can compile direct to machine code (through gcc) like cl-bayesnet can.

The goals of this project is to be useful to developers who want to use the results of their Bayesian Network modelling freely in any domain. If there is demand, compilation to pure Java and compilation to pure Lisp can be quickly developed.

- Load from dne, ace, xmlbif formats.
- Simple query API.
- Use message passing or arithmetic circuit methods.
- Embeddable C code generation. Other languages such as Java and Lisp are possible.

cl-bayesnet uses S-XML to parse xmlbif. It uses trivial-shell to call the C compiler and CFFI to load the resultant shared object file. You can disable the dependencies on CFFI and trivial-shell by adding `:cl-bayesnet-no-cffi`

to your Lisp's features list.

All dependencies are available through quicklisp.

I suggest using quicklisp. Install that, and then grab the source (via tarball or git) and put it in `~/quicklisp/local-projects/`

. Symlinks work okay too.

See the API-Documentation on github. It may not necessarily be up to date.

Or, use `make-api-doc.sbcl`

in this directory to make the API documentation (cl-bayesnet.html). This assumes you have quicklisp and sbcl installed.

See tests/test-alarm.lisp for example usage.

cl-bayesnet's contributors are listed in the `AUTHORS`

file. The authors of cl-bayesnet grant you use of this software under the terms of the Lisp Lesser General Public License (LLGPL). For details see the files `COPYING`

, `COPYING.LESSER`

and `COPYING.LISP`

in this directory.

If you find problems with this library please take the time to report the issue. This helps you by increasing the chance the issue will be fixed. It helps motivate me by letting me know the library is being used. It helps everyone when the fixed issue creates a stronger codebase.

To report an issue, use the cl-bayesnet issue tracker at github.com.

For issue fixes and improvements, I prefer pull requests. Simple one or two liner fixes are okay over email for now.

Load a file in ace file format. Returns a net.

Load a file in Netica's dne file format. Returns a net.

Load a file in xmlbif file format. Returns a net.

Queries a net or node object.
node only - A probability vector for the states of node.
node and integer - The probability the node is in that numbered state
(according to (states node)).
node and symbol - The probability the node is in that state.
node and list - A probability vector for the states of node given
list, which is a plist of node-state pairs.
net only - The joint probability for the whole net.
net and vector - The joint probability for the whole net, given the
vector. Vector has the num-nodes length, and
contains either a state number for each node, or -1
if the node state is unknown.
net and symbol - A probability vector for the states of the node
designated by symbol.
net and list - The joint probability for the whole net, given list,
which is a plist of node-state pairs.

Writes out arithmetic circuit instructions to a c file, compiles it
with gcc, loads the shared object, and prepares the net to use the
loaded function. If source-location is specified, writes the c file
there. Otherwise uses a temporary file.
Returns the closure used, the raw cffi function pointer, and the
number of instructions.

Use interpreted arithmetic circuit instructions for the
net. Returns the instructions object.

Use a join-tree to evaluate this net. Returns the join-tree object.

Create a new trie with the same structure as trie, applying fn to
the key and the old trie node.

Create a new trie with the same structure as trie, applying fn to
each trie-node in turn.

Returns an assignment of a clique node for each net node. Since
lookup within a clique is sequential, just uses an array of lists. An
array of assignments from the node perspective is returned as a second
value.

Returns the best value in seq/hash, along with its position (or key
for the hash), according to compare. The comparison value is returned
as a third value. key extracts the value to be used for comparison.

return the best value in array, along with its position and its comparison value. See best.

return the best value in hash along with its hash-key and its comparison value. See best.

return the best value in list, along with its position and its comparison value. See best.

Builds a clique-tree for dag. The tree is represented by an
upper triangular matrix which has lists of clique-nodes in its
diagonal.

Generates a list of added links (node1 . node2) which are necessary
to form a cluster around node. Uses an (edge-tree).

Create a function which is the composition of the given functions.

Increments att-state according to att-mask; att-state and att-mask
are vectors. att-mask is nil for non-included attributes and the
number of values for included attributes. It takes (reduce
#'* (remove nil att-mask)) to iterate through att-state. att-state
must be a positive integer below the mask's value, wherever mask is
non-nil.

Given the mask and att-state, return an index. Used to map
attribute values to a single lookup value in a table.

Creates a 0-vector of the given length, with the i'th argument set to 1.

Remove references to the node from graph. Replaces the node with t

Calculates the dimensionality of the list. EG:
(make-array (dimension-list list) :initial-contents list)))

Calculates the dimensionality of the list, minus one. EG:
(make-array (dimension-list list) :initial-contents list)))

Write out the matching function for state and val. Returns 1.0 if
state is negative (missing) or state = val. Returns 0.0 otherwise.

This converts a float to a list of fixnums, useful for hashing floats using fixnum-based schemes.

This finds all shortest paths in graph. I could make it more
efficient by using the fact that the paths are symmetric.

Graph is an array of (itree), where each tree contains that node's neighbours.
Returns a list of cliques obtained from triangulating the graph. The
triangulation can be recovered by starting with a moral graph and
ensuring each clique is completely connected. Each clique is an itree
of nodes. Destroys graph.

Generate an arithmetic circuit for the bn represented by a
net (bn.lisp). Note that this version assumes the clique-tree is a
single tree (which is correct at 15/12/2007).

Generate a parameter for the net with the given net-state and node-num.

bn - a net object.
clique-tree - a clique-tree built from the bn's dag. Symmetric array
with node-num lists on the diagonal and t where connected.
node-assignment - (aref node-assignment node-num) == node's clique index.
net-state - array of the current node states. Nil means the node hasn't
been processed.
traversal - the current traversal to operate on: (clique trav1 ... travn)
depth - the current depth of the traversal.

Add the elements of hash to the given trie (if no trie is given,
make one with the same test as the hash table. trie-key (default
#'identity) is a function to apply to the hash-key. It should
convert the hash-key to a list of atoms which are compatible with
the trie's test. trie-value (default #'identity) is a function to
extract the value of interest from the actual value (or the key if
bagp is non-nil) held in the hash.

Enter the observation that node-num is obs.

Calculates the probability of node-num given junction tree jt.

Test whether the tree is in fact a junction tree, meaning for each
pair of cliques, all cliques in between contain their intersection.

Converts a trie alist to a trie-specific hash.

Map fn across integers from 0 below n, returning the results in
an (ordered) list.

applies fn to each pair of items and returns a list of the resulting values.
> (map-pairs #'cons '(1 2 3 4))
=> ((1 . 2) (1 . 3) (1 . 4) (2 . 3) (2 . 4) (3 . 4))

maparray applies fn to all elements in
array, returning the result in an array the
same dimension as the first array

Return a new potential for sep-set to match cluster.

Matches evidence.

Generates a list of neighbours of the node.

Output the net's structure in a viewable form.

Shadowing traversal, returns (tree-node node-mask combinations) for
each tree-node in traversal.

Returns a vector of all node index combinations built from initial.
node-mask is a vector which is nil for non-incremented nodes and
numstates for included nodes. DEPRECATED for being horribly slow.

Normalize a vector. Optionally adds smoothing-factor (which should
be a number) to each element first. If tot is less than or equal to
0.

Create a vector of length (end - start), filled with numbers from
start...(end - 1). Start defaults to 0.

Idea taken from trivial-configuration-parser by Brian Mastenbrook.

Idea taken from trivial-configuration-parser by Brian Mastenbrook.

Puts the form in canonical form for insertion.

Puts the form in canonical form for insertion.

Readies the network for efficient lookup.
Sets a node ordering for the network. Also sets node parent-vec and
parent-indices.

Store information for efficient lookup.

Pushes a form onto instructions, and returns an index into forms.
Won't actually add a form if a matching one exists (acts like pushnew).

Returns the roots of the graph as a list.

Find prod states of x in X + prod states of y in Y. clique1
and clique2 are lists, states is a vector.

Find |intersection| of lists clique1 and clique2

Treat 2D array as a symmetric array. Settable.

Builds a traversal for the undirected tree structure tree. Structure is
;(tree-node subtraversal1 ... subtraversaln)

Returns t if the given trie has no branches.

@arg[extid]{A @class{extid}}
@return[sytemid]{puri:uri or nil}
Returns the System ID part of this External ID.

Count the number of branches of trie.

Return (key . trie-value) for each branch of trie.

Empties the trie, but leaves the test as is.

@arg[extid]{A @class{extid}}
@return[sytemid]{puri:uri or nil}
Returns the System ID part of this External ID.

Insert the value in the trie with the given key. Returns the
accessed trie node.

List all values at the bottom of the trie (i.e. values of all tries
with no branches).

List all values at the given depth (0 is the top level).

Recursively list all values in the trie.

Apply fn to each branch of trie. Returns the trie.

Apply fn to each branch of trie. Returns a list of the returned values.

Create a new trie with the same structure as trie, applying fn to
the key and the old trie node.

Apply fn to the given trie and its children, returning the results
as the values of a matching trie.

Apply fn to the given trie's non-nil values, returning the results
as the values of a matching trie.

Recursively remove all branches in to-prune that don't also appear
in example, thus to-prune is guaranteed to be as small as example or
smaller.

Recursively search the trie for the given key. If key is nil,
We're at the right node, so we return it. The value (which may be
nil) can then be accessed with trie-value.

@arg[extid]{A @class{extid}}
@return[sytemid]{puri:uri or nil}
Returns the System ID part of this External ID.

Build a vector by calling fn num times.

a cluster's weight is the product of its nodes' states.

Saves the existing evidence in the net and sets the evidence to
evidence. Restores the net to its previous state after leaving the
with-evidence block.

Anaphoric if. (lexically sets 'it' to the test-form, which can
then be referenced in then-form and else-form.

Anaphoric when. See aif.

Loop over the trie's branches.

do for upper triangular i and j. i from 0 to len, j from i+1 to len.

(setf ref (* ref multiplier)). Like incf.

An anaphorous macro. binds the first val to `it', allows possible modifications
in the body, then returns the values. A more general prog1.

Continue performing body until expr is false.

Unless label is nil, caches the calculation performed by body using label.
If there is no calculation-context, does not evaluate label, so
don't rely on side effects.

Defines a calculation context within which calculations performed
within with-calculation are cached according to their label.

Sets the evidence in a node via state index or symbol. For a net
or join-tree, adds the evidence as a plist of node-state pairs.

Clear all evidence from object.

Returns the evidence in a node as its state symbol (nil if no
evidence), and for nets and join-trees a plist of node-state
pairs. Settable.

Sets the evidence in a node via state index or symbol. For a net
or join-tree, sets the evidence as either a plist of node-state pairs,
or a vector of state indices (or -1 for unobserved) corresponding to
the net's node-order.

Returns the evidence in a node as a state index and nets as a
vector of state indices. -1 indicates no evidence.

Retrieve the node represented by a keyword name or index from the
given net or join-tree.

Query a net/node.

Randomise the object, which should represent a sequence.

The For a net, a string identifier and for a node, a keyword
identifier.

The Returns the containing net for a node or join-tree.

The Returns a list of node-names as keywords. The ordering matches
their index order. This is set as part of the network compilation
process.

The The amount of nodes in the network.

The The amount of states for the given node.

The A vector of parent names as keywords for the given node.

The A vector of state names as keywords for the given node.

Used by with-calculation(-context) to define a limited caching
environment.

String to pass to format. First arg is source, second is target.

Temporary work directory for C-based network compilation

A trie node.