

                      Software that implements

           FLEXIBLE BAYESIAN MODELS BASED ON NEURAL NETWORKS, 

       GAUSSIAN PROCESSES, MIXTURES, AND DIRICHLET DIFFUSION TREES

                         and that demonstrates

                   MARKOV CHAIN MONTE CARLO METHODS

              Copyright (c) 1995-2004 by Radford M. Neal 

                         Version of 2004-11-10

Permission is granted for anyone to copy, use, modify, or distribute
these programs and accompanying documents for any purpose, provided
this copyright notice is retained and prominently displayed, along
with a note saying that the original programs are available from
Radford Neal's web page, and note is made of any changes made to these
programs.  These programs and documents are distributed without any
warranty, express or implied.  As the programs were written for
research purposes only, they have not been tested to the degree that
would be advisable in any important application.  All use of these
programs is entirely at the user's own risk.

If you have comments, bug reports, or questions, you may contact me at
the following address:

                   Radford Neal
                   Dept. of Statistics
                   University of Toronto
                   100 St. George Street
                   Toronto, Ontario  M5S 3G3
                   CANADA

or e-mail me at radford@stat.toronto.edu or radford@cs.toronto.edu.

Information on any updates or other related work may from time to time
be available via the World Wide Web, starting from my home page at the
following URL:

              http://www.cs.utoronto.ca/~radford/



                                 CONTENTS


Facilities.doc      Facilities provided by this software

Install.doc         Installing the software

Overview.doc        Overview of the software

Ex-intro.doc        Introduction to the examples

Ex-dist.doc         Examples of Markov chain sampling for simple distributions

  Ex-dist-n.doc        Sampling from a univariate normal distribution
  Ex-dist-g.doc        Sampling from a ring distribution in three dimensions
  Ex-dist-f.doc        Sampling from a funnel distribution in ten dimensions

Ex-circ.doc         Examples of circularly-coupled Markov chain sampling

Ex-bayes.doc        Examples of Markov chain sampling for simple Bayesian models
  
  Ex-bayes-r.doc       A linear regression model
  Ex-bayes-t.doc       Modeling real-valued data with a t-distribution
  Ex-bayes-p.doc       Modeling probabilities for categorical data
  Ex-bayes-e.doc       A random effects model

Ex-netgp.doc        Examples of flexible Bayesian regression and classification 
                    models based on neural networks and Gaussian processes

  Ex-netgp-r.doc       A simple regression problem 
  Ex-netgp-b.doc       A problem with a binary response 
  Ex-netgp-c.doc       A three-way classification problem 
  Ex-netgp-o.doc       A regression problem with outliers   

Ex-mixdft.doc       Examples of mixture models and Dirichlet diffusion trees

  Ex-mixdft-b.doc      A probability estimation problem with binary data 
  Ex-mixdft-r.doc      A bivariate density estimation problem 
  Ex-dft-a.doc         Building an additive model using two diffusion trees

Ex-surv.doc         Examples of Bayesian neural network survival models

Ex-gdes.doc         Examples of gradient descent learning with early stopping

Hints.doc           Hints and warnings

Guide.doc           Guide to further documentation

Acknowledgements.doc 



FACILITIES PROVIDED BY THIS SOFTWARE

This software is meant to support research and education regarding:

   * Flexible Bayesian models for regression and classification 
     based on neural networks and Gaussian processes, and for
     probability density estimation using mixtures and Dirichlet
     diffusion trees.  Neural network training using early stopping 
     is also supported.

   * Markov chain Monte Carlo methods, and their applications to
     Bayesian modeling, including implementations of Metropolis,
     hybrid Monte Carlo, slice sampling, and tempering methods.

These facilities might be useful for actual problems, but you should
note that many features that might be needed for real problems have
not been implemented, that the programs have not been tested to the
extent that would be desirable for important applications.

The complete source code (in C) is provided, allowing researchers to
modify the program to test new ideas.  It is not necessary to know C
to use the programs (assuming you manage to install them correctly).

This software is designed for use on a Unix or Linux system, using
commands issued to the command interpreter (shell).  No particular
window system or other GUI is required, but a plotting program will be
very useful.  I use the xgraph plot program, written by David
Harrison, which allows plots to be produced by just piping data from
one of the commands; it can be obtained from my web page.


Markov chain Monte Carlo facilities.

All the Bayesian models are implemented using Markov chains to sample
from the posterior distribution.  For the elaborate models based on
neural networks, Gaussian processes, mixtures, and Dirichlet diffusion
trees, this is done by combining general-purpose Markov chain sampling
procedures with special modules written in C.  Other models could be
implemented in the same way, but this is a fairly major project.

To allow people to play around with the various Markov chain methods
more easily, a facility is provided for defining distributions (on
R^n) by giving a simple formula for the probability density.  Many
Markov chain sampling methods, such as the Metropolis algorithm,
hybrid Monte Carlo, slice sampling, simulated tempering, and annealed
importance sampling may then be used to sample from this distribution.
Bayesian posterior distributions can be defined by giving a formula
for the prior density and for the likelihood based on each of the
cases (which are assumed to be independent).

A long review paper of mine on "Probabilistic Inference Using Markov
Chain Monte Carlo Methods" can be obtained from my web page.  This
review discusses methods based on Hamiltonian dynamics, including the
"hybrid Monte Carlo" method.  These methods are also discussed in my
book on "Bayesian Learning for Neural Networks".  My web page also has
papers on slice sampling ("Markov chain Monte Carlo methods based on
`slicing' the density function" and "Slice sampling"), Annealed
Importance Sampling, and circularly-coupled Markov chain sampling, all
of which are implemented in this software.


Neural network and Gaussian process models.

The neural network models are described in my thesis, "Bayesian
Learning for Neural Networks", which has now been published by
Springer-Verlag (ISBN 0-387-94724-8).  The neural network models
implemented are essentially as described in the Appendix of this book.
The Gaussian process models are in many ways analogous to the network
models.  The Gaussian process models implemented in this software, and
computational methods that used, are described in my technical report
entitled "Monte Carlo implementation of Gaussian process models for
Bayesian regression and classification", available from my web page,
and in my Valencia conference paper on "Regression and classification
using Gaussian process priors", in Bayesian Statistics 6.  The
Gaussian process models for regression are similar to those evaluated
by Carl Rasmussen in his thesis, "Evaluation of Gaussian Processes and
other Methods for Non-Linear Regression", available from his web page,
at the URL http://www.cs.utoronto.ca/~carl/; he also talks about
neural network models.  To understand how to use the software
implementing these models, it is essential for you to have read at
least one of these references.

The neural network software supports Bayesian learning for regression
problems, classification problems, and survival analysis, using models
based on networks with any number of hidden layers, with a wide
variety of prior distributions for network parameters and
hyperparameters.  The Gaussian process software supports regression
and classification models that are similar to neural network models
with an infinite number of hidden units, using Gaussian priors.

The advantages of Bayesian learning for both types of model include
the automatic determination of "regularization" hyperparameters,
without the need for a validation set, the avoidance of overfitting
when using large networks, and the quantification of uncertainty in
predictions.  The software implements the Automatic Relevance
Determination (ARD) approach to handling inputs that may turn out to
be irrelevant (developed with David MacKay).  

For problems and networks of moderate size (eg, 200 training cases, 10
inputs, 20 hidden units), fully training a neural network model (to
the point where one can be reasonably sure that the correct Bayesian
answer has been found) typically takes up to several hours on a modern
personal computer.  However, quite good results, competitive with
other methods, are often obtained after training for just a few
minutes.  The time required to train the Gaussian process models
depends a lot on the number of training cases.  For 100 cases, these
models may take only a few minutes to train (again, to the point where
one can be reasonably sure that convergence to the correct answer has
occurred).  For 1000 cases, however, training might well take a day.

The software also implements neural network training using early
stopping, as described in my paper on "Assessing relevance
determination methods using DELVE", in Neural Networks and Machine
Learning, C. M. Bishop, editor, Springer-Verlag, 1998.  A similar
early stopping method is also described in Carl Rasmussen's thesis
(see above).


Bayesian mixture models and Dirichlet diffusion trees.

The software implements Bayesian mixture models for multivariate real
or binary data, with both finite and countably infinite numbers of
components.  The countably infinite mixture models are equivalent to
Dirichlet process mixture models.  The sampling methods that I have
implemented for these models are described in my technical report on
"Markov chain sampling methods for Dirichlet process mixture models",
which can be obtained from web page; see also my technical report on
"Bayesian mixture modeling by Monte Carlo simulation".

The software also implements models based on Dirichlet diffusion
trees, described in my technical report on "Defining priors for
distributions using Dirichlet diffusion trees", and in my Valencia
conference paper on "Density modeling and clustering using Dirichlet
diffusion trees", in the Bayesian Statistics 7.  Dirichlet diffusion
trees can be seen both as a way of modeling distributions and as a
method for hierarchical clustering.


Software components.

The software consists of a number of programs and modules.  Each major
component has its own directory, as follows:
  
    util    Modules and programs of general utility.

    mc      Modules and programs that support sampling using Markov 
            chain Monte Carlo methods, using modules from util.

    dist    Programs for doing Markov chain sampling on a distribution
            given by a simple formula, or by giving a Bayesian prior
            and likelihood, using the modules from util and mc.

    net     Modules and programs that implement Bayesian inference
            for models based on multilayer perceptron neural networks, 
            using the modules from util and mc.  Also implements simple
            gradient descent training, possibly with early stopping.

    gp      Modules and programs that implement Bayesian inference
            for models based on Gaussian processes, using the modules
            from util and mc.

    mix     Modules and programs that implement Bayesian inference
            for finite and infinite mixture models, using modules
            from util and mc.

    dft     Modules and programs that implement density modeling and
            clustering methods based on Dirichlet diffusion trees.

In addition, the 'bvg' directory contains modules and programs for
sampling from a bivariate Gaussian distribution, as a simple
demonstration of how the Markov chain Monte Carlo facilities can be
used from a special module written in C.  Other than by providing this
example, and the detailed documentation on various commands, I have
not attempted to document how you might go about using the Markov
chain Monte Carlo modules for another application written in C.

The following directories contain examples of how these programs can
be used, many of which are discussed in the documentation:

    ex-netgp  Examples of Bayesian regression and classification 
              models based on neural networks and Gaussian processes.

    ex-mixdft Examples of Bayesian mixture models and Dirichlet diffusion
              tree models.  Includes command files for the test in my 
              paper on "Markov chain sampling methods for Dirichlet process 
              mixture models" and for one of the tests in "Density modeling 
              and clustering using Dirichlet diffusion trees".

    ex-dist   Examples of Markov chain sampling on distributions
              specified by simple formulas.

    ex-bayes  Examples of Markov chain sampling for Bayesian models
              specified using formulas for the prior and likelihood.

    ex-surv   Examples of neural network survival models.

    ex-gdes   Examples of neural network learning using gradient 
              descent and early stopping.

    ex-ais    Contains command and data files used for the tests in
              my paper on "Annealed importance sampling".

You should note, however, that these examples do not constitute
"recipes" that can be used unchanged for new problems.  They are
intended to help you understand the models, priors, and computational
methods, so that you can devise an appropriate way of handling
whatever problem you are interested in.

The 'bin' directory contains links to all the programs.  The 'doc'
directory contains all the documentation.


Portability of the software.

The software is written in ANSI C, and is meant to be run in a UNIX
environment.  It is known to work on various Linux systems running on
a Pentium processor, on a Solaris system running on a SPARC processor,
and on an SGI machine running IRIX Release 6.5.  It also runs OK on
Compaq Alpha machines, provided that the -ieee and -std options are
given to the Compaq C compiler (this may no longer be necessary - I
haven't checked recently).  As far as I know, the software does not
depend on any peculiarities of these environments (except perhaps for
the use of the drand48 pseudo-random number generator, and the lgamma
function, and the Unix facilities used to start programs to evaluate
"external" functions in the 'dist' module), but you may nevertheless
have problems getting it to work in substantially different
environments, and I can offer little or no assistance in this regard.

There is no dependence on any particular graphics package or graphical
user interface.  The 'xxx-plt' programs are designed to allow their
output to be piped directly into the 'xgraph' plotting program, but
other plotting programs can be used instead, or the numbers can be
examined directly.  The 'xxx-tbl' programs output the same information
in a different format, which is useful when plotting or analysing data
with S-Plus or R, since this format is convenient for the S-Plus or R
read.table command.



INSTALLING THE SOFTWARE

This section describes how to unpack and compile the software for a
Unix machine.  Note that getting the software to work in a non-Unix
environment may be difficult or impossible.


Unpacking the files.

The software is distributed as a Unix tar archive.  To obtain the
files, download the tar archive for the desired version by anonymous
ftp or via your Web browser to a file of the form 'fbm.YYYY-MM-DD.tar', 
and then issue the Unix command

    tar xf fbm.YYYY-MM-DD.tar

If you got the archive in compressed form, as 'fbm.YYYY-MM-DD.tar.Z',
you must use the command "uncompress fbm.YYYY-MM-DD.tar.Z" before
doing the above.  The following instructions cover what to do next for
the current version; you should read the old documentation if for some
reason you are installing an older version.

The tar command should create a directory called 'fbm.YYYY-MM-DD',
where YYYY-MM-DD is the release date.  It should place numerous files
and sub-directories in this directory.  If this seems to have worked,
you can remove the file 'fbm.YYYY-MM-DD.tar'.  You should now change
into the 'fbm.YYYY-MM-DD' directory, as the following instructions
assumed that you are there.

If you prefer that this directory be called something other than
'fbm.YYYY-MM-DD', change the name now, BEFORE compiling the programs,
since the programs look for a file of random numbers in the directory
under the name it had when they were compiled.


Looking at the documentation.

The directory 'doc' contains links to all the documentation files.
The file 'manual' contains all the introductory documentation
(including this) as a simple text file; the same information is also
contained in several .doc files.  Other .doc files contain more
detailed information.  Files of the form 'Release.YYYY-MM-DD.doc'
contain information on current and past releases.  These may be of
interest if you are upgrading from an older version of the software.

If you have a Web browser, you can access all these documentation
files via 'index.html' in the 'doc' directory, as described in
Guide.doc.


Compiling the programs.

You will probably be able to compile the programs as described below
without making having to change anything.  However, it is possible
that you will want to use a different C compiler, or set certain
compilation options.  You can probably set the required options by
modifying the 'make.include' file in the main directory, which is
included at the beginning of all Makefiles, though for some problems
you might have to modify the 'Makefile' and 'xxx.make' files in the
various sub-directories, or modify the source files.

Here are some reasons that you might need to customize things:

  1) The programs are written in ANSI standard C.  If you compiler
     defaults to some other idea of what C is, you should try to
     persuade it otherwise.  On DEC Alpha machines, the "-std" flag
     does this.  It can be put in CFLAGS in 'make.include'.

  2) The programs were written with IEEE floating-point in mind, and
     therefore may occasionally perform operations that result in
     overflow or underflow.  If this causes program termination on
     your machine (eg, with a "floating point exception"), you will
     need to figure out how to disable these errors.  On DEC Alpha
     machines, for example, the problem can be fixed using a "-ieee"
     compiler option, which can be put in CFLAGS in 'make.include'.

  3) The 'util' directory contains a file of 100,000 natural random
     bytes, which are used in combination with pseudo-random numbers
     This file is accessed by many of the programs, using a path 
     name that by default points into this 'util' directory.  If you 
     plan on moving this file elsewhere, you will need to change the 
     compilation command for rand.c at the end of 'util/util.make'.

  4) If you are rather short of memory, you might want to reduce the
     size of the Max_optional_memory constant defined in gp/gp-mc.c.
     This will save memory at the cost of some time.

Once you have made any required changes, you can compile the programs
by going to the main directory where you installed the software and
issuing the command

    make-all

This will compile programs in the various sub-directories.  Note that
some modules will be compiled over again in each directory where they
are used; this is intentional.

It is possible that these compilation commands will fail for some
reason, in which case you'll have to figure out what's wrong and fix
it.  Note that the 'make-all' command just moves into each of the
directories and does a 'make' there.  You can do this manually for
each directory to see where the problem is.  For these makes to work
correctly, the programs MUST be kept in separate 'util', 'mc', 'dist',
'bvg', 'net', 'gp', and 'mix' sub-directories, with these names.


Using the programs.

Once you have successfully compiled the programs, you should put the
'bin' directory (within the main directory for this software) in your
search path.  How this is done depends on the shell program you are
using; consult a local expert if you don't know how.  This directory
contains symbolic links to all the programs making up this software.
Subsequent instructions assume that you have this 'bin' directory in
your search path.

The above is the simple version of how to use the programs.  However,
if you want to use the programs on more than one type of machine, you
will need to compile them several times, once for each machine
architecture, and you will need to set your search path to a directory
that contains the versions of the programs compiled for the machine
you are currently using.  By convention, these directories should be
called "bin.ARCH", where ARCH is the name of the machine architecture.
The shell file install-arch creates such a directory (if necessary)
and copies the programs from the "bin" directory to the "bin.ARCH"
directory for the current architecture.  It is assumed that a program
called 'arch' exists that returns the name of the architecture.


Cleaning things up.

Once the compilations have finished, you can save some disk space by
issuing the command

    rm */*.o

when you are in the main directory.  You can get rid of the compiled
programs by using the command

    make-clean

when in the main directory.  Of course, you then won't be able to use
the programs until you do another make-all to recompile them, unless
you had copied them to a "bin.ARCH" directory.



OVERVIEW OF THE SOFTWARE

The software is organized in a modular fashion.  The 'util' directory
provides a number of general facilities, some of which may be of use
for other purposes.  The 'mc' module provides support for Markov chain
Monte Carlo methods, which the 'dist' module allows you to use for a
distribution specified by a formula.  The modules 'net', 'gp', 'mix',
and 'dft' are more specialized modules that use the Markov chain
methods to support Bayesian inference for neural networks, Gaussian
process models, finite and infinite mixture models, and Dirichlet
diffision tree models.  This section provides an overview of the
various components of the software.


Program usage.

The software is designed to be usable interactively by typing commands
to run the various programs to the Unix shell.  These programs may
create or modify files that hold the results.  You will usually want
to create a directory for each project you are working on, and change
to that directory before issuing these commands, so that the files
pertaining to that project will be separate.

Since I've gotten e-mail from people who were quite confused by the
simplicity of this concept, let me say it again.  YOU USE THE SOFTWARE
BY TYPING UNIX COMMANDS TO RUN THE VARIOUS PROGRAMS.  There is NO
master program that you run and type commands to - or to put it
another way, that master program is the Unix command interpreter (the
shell).

If you're doing serious work, you will probably want to create Unix
command files holding the main commands, so that you won't forget what
you did.


Log files.

Most of the programs make use of a "log file" facility supported by
modules and programs in 'util'.  A log file records all the
information pertaining to a "run" of an iterative program.  The first
few records of the log file (with "indexes" of -1) contain the
specifications for the run (such as the network architecture and the
source of training data).  These records are written by "spec"
programs (eg, 'net-spec' and 'data-spec') that the user invokes at the
beginning of the run.  Once the run has been specified, the program
that performs iterations is invoked (eg, 'net-mc').  This program will
append further records to the log file, one for each iteration for
which the user has asked the state to be saved (this might be every
iteration, or might be every n'th if minimizing disk usage is a
concern).  Each record written has the iteration number as its index,
and contains the complete state of the program at that time (eg, all
the parameters and hyperparameters of the network being trained).

Note that log files contain binary data; they are not human-readable.
They may also not be readable on a different type of machine from the
one on which they were written.

After an iterative program finishes, the user may decide to let the
run continue for more iterations.  This is easily done by just
invoking the program again with a larger iteration limit, whereupon it
restarts using the last state stored in the log file, and then appends
records to the log file for further iterations.

The information about iterations that is stored in the log file can be
examined using various programs both during and after a run.  In
particular, the user can plot the progress of various quantities
during the course of the run, without having to decide beforehand
which quantities will be of interest.  The states saved at various
iterations are also the basis for making Monte Carlo estimates, and in
particular for making Bayesian predictions based on a sample from the
posterior distribution.


Models and data.

The 'util' directory also contains modules and programs that specify
the final portion of a probabilistic model (which is independent of
the details of networks or other functional schemes), that support
reading of numeric input from data files or other sources, and that
specify sets of training and test cases.

The models supported include those for regression, classification,
probability density estimation, and survival analysis.  See
model-spec.doc for details.

The data files used must contain numbers in standard ASCII form, with
one line per case, but there is considerable freedom regarding
separators and in the ordering of items.  "Input" and "target" items
that pertain to a case may come from the same file, or different
files, and the position within a line of each item may be specified
independently.  The set of cases (lines) to be used for training or
testing can be specified to be a subset of all the lines in a file.
The data source can also be specified to be the output of a program,
rather than a data file.

Specifications for where the training and test data comes from are
written to a log file by the 'data-spec' program, which also allows
the user to specify that certain transformations are to be done to the
data items before they are used.  In particular, the data can be
translated and re-scaled in a user-specified way, or by amounts that
are automatically determined from the training data.

The source of "test" data can also be specified explicitly by
arguments to the relevant commands, allowing the final results of
learning to be applied to any data set for which predictions are
desired.

Note that mixture models and Dirichlet diffusion tree models can
presently be used only for data in which the number of "input" items
is zero. 

See data-spec.doc for further details on how to specify the source and
format of the data.


Random number generation.

A scheme for combining real and pseudo random numbers is implemented
by modules in the 'util' directory, along with procedures for sampling
from various standard distributions, and for saving the state of the
random number generator.

The 'rand-seed' program is used to specify a random number seed to use
for a run.  The state of the random number generator is saved with
each iteration in the log file in order to ensure that resuming a run
produces the same results as if the run had continued without
stopping.


Markov chain Monte Carlo.

The 'mc' directory contains modules and programs that support the use
of Markov chain Monte Carlo methods.  These methods can be applied to
a distribution specified by a formula using the 'dist' programs (see
below).  More elaborate Markov chain Monte Carlo applications can be
created by adding modules in C that compute certain application
specific quantities, of which the most central is the probability
distribution to sample from.  For example, the neural network
application provides a procedure for computing the posterior
probability density of the network parameters.  An application may
also provide implementations of specialized sampling procedures, such
as the procedures for doing Gibbs sampling for hyperparameters in the
neural network application.

For the user of neural network, Gaussian process, mixture, and
Dirichlet diffusion tree models, the most important 'mc' program is
'mc-spec', which is used to specify how the Markov chain sampling is
to be done.  There are a large number of reasonable ways of sampling
for neural networks or Gaussian processes.  The best way is still the
subject of research.  Good results can be obtained using several
standard approaches, however, as described in the examples in other
sections of this documentation.  You can also read all about the
various methods in mc-spec.doc.  Note, however, that for each model
there are also sampling methods specific to that model alone, which
are documented in net-mc.doc, gp-mc.doc, and mix-mc.doc.  At present,
sampling for mixture models is done only by the specific procedures
described in mix-mc.doc.

Tempering methods and Annealed Importance Sampling are currently
supported for neural network models and Dirichlet diffusion tree
models, but not for Gaussian processes and mixture models.  Circular
coupling is now supported, but it currently works for only a limited
number of Markov chain operations.


Sampling from a specified distribution.

The 'dist' directory contains programs for sampling from a
distribution specified by a formula for its "energy" (minus the log
probability density, plus an arbitrary constant), or by formulas for
the prior and likelihood for a Bayesian model.  The full range of
Markov chain sampling methods implemented by the 'mc' module can be
used for these distributions, including the tempering and Annealed
Importance Sampling facilities.

The 'dist-spec' program is used to specify the distribution, along
with 'data-spec' to say where the data comes from, if the distribution
is the posterior for a Bayesian model.  The 'mc-spec' program is then
used to specify the Markov chain updates, after which 'dist-mc' does
the actual sampling.  The 'dist-display' and 'dist-plt' programs can
be used to monitor the runs, and 'dist-est' can be used to estimate
the expectation of some function with respect to the distribution.


Neural network models.

The 'net' directory contains the modules and programs that implement
Bayesian learning for models based on multilayer perceptron networks,
making use of the modules in the 'util' and 'mc' directories.  The
networks and data models supported are as described in my book,
Bayesian Learning for Neural Networks, with the addition of
experimental models for survival analysis.

A network training run is started with the 'net-spec' program, which
creates a log file to which it writes specifications for the network
architecture and priors.  In a simple run, the 'model-spec',
'data-spec' and 'mc-spec' programs would then be used to specify the
way the outputs of the network are used to model the targets in the
dataset, what data makes up the training set (and perhaps the test
set), and the way the sampling should be done.  The 'net-mc' program
(a specialization of the generic 'xxx-mc' program) would then be
invoked to do the actual sampling.  Finally, the 'net-pred' program
would be used to make predictions for test cases based on the networks
saved in the log file.

Usually, one would want to see how the run had gone before making
predictions.  The 'net-display' program allows one to examine the
network parameters and hyperparameters at any specified iteration.
The 'net-plt' program can be used to obtain the values of various
quantities, such as the training set error, for some range of
iterations.  The output of 'net-plt' would usually be piped to a
suitable plot program for visual examination, though it is also
possible to directly look at the numbers.

Several other programs are also present in the 'net' directory.  Some
of these will probably not be of interest to the ordinary user, as
they were written for debugging purposes, or to do specialized tasks
relating to my thesis.


Gaussian process models.

The 'gp' directory contains the modules and programs that implement
Bayesian inference for Gaussian process models, making use of the
modules in the 'util' and 'mc' directories.  These Gaussian process
programs are analogous to the neural network programs.  The models
based on Gaussian processes are also similar to models based on large
neural networks using Gaussian priors (or other priors with finite
variance).

To start, the 'gp-spec' program is used to specify a Gaussian process
model - that is, to specify the form of the covariance function, and
the priors on the hyperparameters that control this covariance
function.  The 'model-spec' and 'data-spec' programs are then used to
specify how the Gaussian process is used to model data, and the source
of the training data (and possibly test data).  The Markov chain
sampling method is then specified using 'mc-spec', and sampling is
done using 'gp-mc'.  Finally, 'gp-pred' is used to make predictions
for test cases using the Gaussian processes that were saved in the log
file by 'gp-mc'.

The 'gp-display' and 'gp-plt' programs can be used to view the
parameters of the Gaussian processes generated by 'gp-mc', both during
and after the run.  Several other programs in the 'gp' directory may
also be of interest.


Mixture models.

The 'mix' directory contains the modules and programs that implement
Bayesian inference for finite and infinite mixture models, making use
of the modules in the 'util' and 'mc' directories.  These models are
used to model the probabilities for vectors of binary data, or the
probability densities for real vectors.  The infinite mixture models
are equivalent to what are called Dirichlet process mixtures.

The 'mix-spec' program is used to specify a mixture model - that is,
to say how many components there are in the mixture (perhaps countably
infinite), and to specify the priors on the parameters and
hyperparameters.  The 'model-spec' and 'data-spec' programs are then
used to complete the specification of the data model and data source.
For mixture models, the data items are all considered to be "targets",
with the number of "inputs" being zero.  The Markov chain sampling
procedures to use are then specified using 'mc-spec', and the sampling
is done with 'mix-mc'.  One can look at the parameter values for
states drawn from the posterior with 'mix-display', and generate
future datasets using 'mix-cases'.


Dirichlet diffusion tree models.

The 'dft' directory contains the modules and programs that implement
density modeling and clustering using Dirichlet diffusion trees,
making use of the modules in the 'util' and 'mc' directories.  

The 'dft-spec' program specifies the prior for the tree structure.
The 'model-spec' and 'data-spec' programs are then used to complete
the specification of the model and data source.  As for mixture
models, the data items are all considered to be "targets", with the
number of "inputs" being zero.  The Markov chain sampling procedures
to use are then specified using 'mc-spec', and the sampling is done
with 'dft-mc'.  One can then examine the resulting trees with
'dft-display' or 'dft-dendrogram', or find predictive densities with
'dft-pred'.


Quantities obtainable from log files.

The 'xxx-plt' programs (eg, 'dist-plt', 'net-plt', 'gp-plt',
'mix-plt', and 'dft-plt') are the principal means by which simulation
runs are monitored.  These programs allow one to see the values of
various "quantities", evaluated for each iteration stored in a log
file within some range.  Some other programs (eg, 'xxx-hist') also use
the same set of quantities.

A quantity is specified by an identifying character, perhaps with a
numeric modifier.  Some quantities are single numeric values
(scalars); others are arrays of values, in which case the desired
range of values is also specified following an "@" sign.  Some
quantities can be either scalars or arrays, depending on whether a
range specification is included.

There is a hierarchy of quantities, as defined by modules at different
levels.  A few quantities are universally defined - principally 't',
the index of the current iteration.  Many more are defined for any
Markov chain Monte Carlo application - such as 'r', the rejection rate
for Metropolis or Hybrid Monte Carlo updates.  The 'dist' module also
defines some quantities, and a large number of quantities are defined
for neural networks and Gaussian processes - for example, 'b', the
average squared error on the training set, and 'n', the current value
of the noise standard deviation (for a regression model) - and for
mixture models - for example, 'Cn', the total probability for the n
largest components in the mixture.  For details, see quantities.doc
along with mc-quantities.doc, dist-quantities.doc, net-quantities.doc,
gp-quantities.doc, mix-quantities.doc, and dft-quantities.doc.



INTRODUCTION TO THE EXAMPLES

The following sections how the software can be used on several toy
problems.  These examples are meant to illustrate the features of the
software.  You should note that the models and Markov chain methods
used are not necessarily appropriate for other problems.  To gain a
full understanding of the various possibilities, and their advantages
and disadvantages, you will need to read both the pertinent references
(see Facilities.doc), and the detailed documentation on the various
commands.

The output shown for these examples was obtained by running the
software on our machine, with ">" at the start of a line indicating a
command line that was input.  It is possible (even likely) that your
results will differ, even if you have installed the software
correctly, since small differences in floating point arithmetic can be
magnified into large differences in the course of the simulation.
However, unless one of the simulations became stuck in an isolated
local mode, the final predictions you obtain (eg, from 'net-pred' or
'gp-pred'), and the final distributions of model parameters, should be
close to those reported below.

Some of the examples show the output of "xxx-plt" commands being piped
into a program called "plot".  Any plot program could be used that
reads pairs of numbers from standard input and plots them (in some
cases, a blank line is present to indicate the start of a new
sub-plot).  I use the "xgraph" program written by David Harrison,
which can be obtained from my web page.  If you don't have a plot
program that can be used in this convenient fashion, you can redirect
the output to a file (eg, "net-plt t l log >file") and then read this
file into whatever plotting program you have.  As a last resort, you
can also just look at the numbers in the file yourself.

All the data sets mentioned here are present in directories with names
beginning with "ex", along with the C source of the programs that
generated the data.  The commands given assume that you are in the
directory containing the data.  The command sequences used for each
example are also stored in these directories, in shell files with the
names like 'rcmds.net', 'rcmds.gp', 'bcmds.net', 'bcmds.gp', etc.
Some of these directories also contain other command files used for
examples in my papers.

Computation times are given for many of the examples.  These are all
for the current version of the software, run on the system described
in Ex-system.doc, except for the examples in Ex-dist-g.doc and
Ex-dist-f.doc, which I've left with times for an older version of the
software, run on a 550 MHz Pentium III.



EXAMPLES OF MARKOV CHAIN SAMPLING FOR SIMPLE DISTRIBUTIONS

Almost all uses of the software in this package involve sampling from
a distribution using Markov chain methods, and then making Monte Carlo
estimates for the expectations of functions of state based on this
sample.  This is done, for example, when make predictions for test
cases based on the posterior distribution of a neural network model.

Some ways of doing Markov chain sampling are illustrated in the
examples of modeling with neural networks, Gaussian processes, etc.
If your main interest is in those models, you could start with those
examples, but the simpler examples in this section may be more helpful
in understanding the Markov chain methods.  These examples also
introduce the facilities of the 'dist' module, which are used when
sampling from Bayesian models defined using formulas for the prior and
likelihood, as illustrated by the examples in Ex-bayes.doc.  The
examples there also illustrate some additional aspects of Markov chain
sampling.

The commands used in these examples can also be found in command files
in the "ex-dist" directory.


SAMPLING FROM A UNIVARIATE NORMAL DISTRIBUTION

I will start with a trivial example showing how the "Metropolis"
Markov chain method can be used to sample from a univariate normal
distribution.  This will illustrate the basic facilities for
specifying distributions, for specifying the Markov chain operations
to use, for looking at log files, and for estimating the expectations
of functions.


Specifying the distribution.

We begin by specifying the distribution we want to sample from.  This
is done by giving a formula for the "energy function", which is minus
the log of the probability density, plus any arbitrary constant.  To
sample from a univariate normal distribution for a variable called
"x", with mean 10 and variance 1, we can type the following command to
the Unix command interpreter (the shell):

    > dist-spec nlog "(x-10)^2/2"

Here, "nlog" is the name of a "log file", in which this specification
is saved, and in which the results of sampling will later be stored.
The energy formula "(x-10)^2/2" is minus the log of the probability
density for the desired distribution over "x", with the constant term
Log(2*Pi)/2 omitted, as it is not necessary for most purposes.  Such
formulas must usually be put in quotes, since some characters such as
parentheses will otherwise have special meaning to the shell.  See
formula.doc for the syntax of formulas, which is fairly conventional,
except perhaps that function names must be capitalized (eg, "Sin").

Since only a single variable, "x", is mentioned in the specification,
this is a univariate distribution.  We could have mentioned other
"state variables" in the specification, as in the example in the next
section (see Ex-dist-g.doc).  Valid state variable names start with
one of "u", "v", "w", "x", "y", or "z", which may optionally be
followed by a single digit.  See dist-spec.doc for further details.

The density functions for some distributions, including the normal,
are pre-defined.  We could have used the following command instead of
the one above:

    > dist-spec nlog "Normal(x,10,1)"

The same result can also be obtained as follows:

    > dist-spec nlog "x ~ Normal(10,1)"

This last form is particularly useful for specifying Bayesian models
(see Ex-bayes.doc).


Sampling using Metropolis updates.

After specifying the distribution, we specify what Markov chain
operations should be used to sample from this distribution, using a
command such as:

    > mc-spec nlog metropolis 1

This specifies that each Markov chain iteration should consist of a
single Metropolis operation, with a "stepsize" of 1.  In a Metropolis
operation, a new state is proposed by randomly drawing from the normal
distribution centred at the current state, with standard deviation
given by the stepsize.  This proposed state is then accepted or
rejected based on the change in the energy (ie, on the change in
probability density).  If the proposed state is rejected, the new
state is the same as the old state.

This Markov chain specification is saved in the log file, after the
distribution specification.  We could also specify an initial state
for the Markov chain (see dist-initial.doc), but here we will let the
initial state default to x=0.  To actually do some Markov chain
iterations, we use a command such as:

    > dist-mc nlog 1000

This performs 1000 Markov chain updates, as specified by the last
mc-spec command, and saves the state after each update in the log
file.  This takes only a fraction of a second on our machine, but
Markov chain sampling runs for more difficult problems can take much
longer, so one would often wish to run the 'dist-mc' command in the
background, by putting an "&" at the end of the command line.

If we later decided that we wanted to continue Markov chain sampling
for more iterations, we could just use another 'dist-mc' command with
a larger iteration limit.  For example, the command

    > dist-mc nlog 10000

would produce another 9000 iterations, for a total of 10000.  We could
issue another mc-spec command before this, if we wished to use
different Markov chain operations for these further iterations.


Checking how well the sampling worked.

After or during the Markov chain sampling, we can look at how the
state has changing during the run, and at certain properties of the
Markov chain methods.

The 'dist-display' command lets us see the state at any given
iteration.  For example, the state at iteration 10 of the Markov chain
run above might look like this:

    > dist-display nlog 10

    STATE VARIABLES IN FILE "nlog" WITH INDEX 10

        x = 1.45784   

However, what you see might not be exactly the same as this, due to
differences in random number generators or in floating-point roundoff
errors.  If the iteration number is omitted, 'dist-display' shows the
last iteration.

The 'dist-plt' command is usually more useful in getting a picture of
how well the chain is sampling.  The following command will show how
the state changes over the course of the run:

    > dist-plt t x nlog | plot

If 'plot' is an appropriate plotting program, this will display a
graph of the state variable "x" vs. the iteration number (the "t"
quantity).  From this plot, you will likely see that up to about
iteration 50, the values of "x" are not typical of those seen later in
the run.  These early iterations should be discarded when estimating
functions of state (see below).

After iteration 50, the chain seems to move around the region that has
high probability fairly rapidly.  It should therefore be possible to
estimate expectations of functions of the state with reasonable
accuracy.  If instead, the chain moved very slowly, it would be
necessary to run it for many more iterations, or to use better Markov
chain operations.

Other interesting quantities can also be plotted using 'dist-plt'.
For instance, the energy can be monitored with the following command:

    > dist-plt t E nlog | plot

The change in energy on the basis of which the Metropolis proposals
were accepted or rejected can be examined as follows:

    > dist-plt t D nlog | plot-points

Here, it is best if the plot program used is set up to plot individual
points, rather than lines.  For this chain, the energy difference is
often less than one, so many proposals will be accepted.  If instead
the energy change was almost always large, it would be necessary to
reduce the "stepsize" argument following the "metropolis" operation in
'mc-spec'.  On the other hand, if the energy change is usually very
close to zero, a larger stepsize would produce better sampling.

Other quantities that can be plotted are documented in quantities.doc,
mc-quantities.doc, and dist-quantities.doc.


Estimating expectations of functions.

Finally, we can use the states from the Markov chain to estimate the
expectations of functions of this state.  Since we decided above that
the first 50 iterations were not typical of the chain's equilibrium
distribution, we will use only states after these when estimating
expectations.

The 'dist-est' command is one way of estimating expectations.  The
following command estimates the expectation of the "x" itself:

    > dist-est x nlog 51:

    Number of sample points: 950

    Estimates for x:

      Mean:    10.1496  (standard error 0.0336591)
      Std.dev: 1.03744

    NOTE: The standard errors assume points are independent

The arguments to 'dist-est' are a formula for what we want to
estimate, the log file for the run, and the range of iterations to use
from that log file (here, from 51 on).  The output (which might be a
bit different when you run the programs) gives the estimated
expectation (mean) for the requested function of state, along with its
estimated standard deviation.  

A standard error is also given for the estimated mean, but it is valid
only if the points are independent, which is generally not true if
they were obtained using Markov chain sampling.  In the output above,
the estimate differs from the true mean of 10 by over four times the
standard error, which illustrates that the standard error cannot be
trusted when the points are not independent.

Ideally, the 'dist-est' program would automatically compensate for
this lack of independence, and give correct standard errors, but it
doesn't yet.  If you are interested in the expectation of a state
variable, however, you can get correct standard errors using the
'series' program, which adjusts the standard errors based on estimated
autocorrelations, if told how far out to look.  The following command
illustrates the procedure:

    > dist-tbl x nlog 51: | series msac 15

    Number of realizations: 1  Total points: 950
    
    Mean: 10.149550  S.E. from correlations: 0.096872
    
    Standard deviation: 1.037442  
    
      Lag  Autocorr.  Cum. Corr.
    
        1   0.793346    2.586691
        2   0.620884    3.828460
        3   0.492481    4.813421
        4   0.406282    5.625986
        5   0.332223    6.290432
        6   0.261235    6.812903
        7   0.195664    7.204231
        8   0.162258    7.528748
        9   0.129544    7.787835
       10   0.104300    7.996435
       11   0.079715    8.155866
       12   0.055909    8.267684
       13   0.032055    8.331795
       14   0.011870    8.355534
       15  -0.020351    8.314831

The 'dist-tbl' command produces a list of values for "x" at iterations
from 51 on.  This list is piped into the 'series' program.  With the
options "msac 15", the 'series' program calculates estimates for the
mean and standard deviation, which match those calculated above by
'dist-est'.  It also estimates the autocorrelations for "x" at lags up
to 15.  From these autocorrelation estimates, 'series' finds the
"cumulative correlations" at the various lags, which are defined as
one plus twice the sum of the autocorrelations up to that lag.  If the
autocorrelations from that point on are approximately zero, as seems
to be the case above, the cumulative correlations to that point will
approximate the autocorrelation time for the quantity, which is the
factor by which the effective sample size is less than the number of
points used.  In calculating the standard error for the mean, 'series'
assumes that this is the case, and it therefore divides the sample
size by the cumulative correlation for the last lag requested when
computing the standard error. 

In the example above, the standard error calculated by 'series'
appears to be realistic.  This will be true only if the maximum lag
given as an argument to series is appropriate, however.  This maximum
lag should be large enough that the autocorrelations at larger lags
are close to zero, but not too much larger than this, since including
autocorrelations at many lags introduces extra noise into the estimate
of the autocorrelation time.

An alternative approach is to use 'series' to find out the lag past
which the autocorrelations are almost zero, and then use 'dist-est' to
find the expectation, telling it to look at iterations separated by
that lag.  This is somewhat wasteful of data, but is at present the
only easy way to get correct standard errors when estimating some
function of state rather than a state variable itself.  For example,
from the output of 'series' above, it seems that autocorrelations for
"x" are almost zero at about lag 10.  This is consistent with states
at that lag being almost independent (although lack of correlation
does not guarantee independence).  On that basis, we might estimate
the expectation of Sin(x) with the following command:

    > dist-est "Sin(x)" nlog 51:%10

    Number of sample points: 95

    Estimates for Sin(x):

      Mean:    -0.358403  (standard error 0.0654498)
      Std.dev: 0.637926

    NOTE: The standard errors assume points are independent

These results are consistent with the true expectation of Sin(x) with
respect to the Normal(10,1) distribution, which is -0.330.


SAMPLING FROM A RING DISTRIBUTION IN THREE DIMENSIONS

I will here demonstrate a variety of Markov chain sampling methods
using as an example a distribution that forms a ring in a space of
three dimensions, parameterized by variables called "x", "y", and "z".
For details on the various methods described, see mc-spec.doc.  A
table comparing the performance of the methods on these examples is
included at the end of this section.

The times reported here are for an older version of the software, run
on a 550 MHz Pentium III.


Specifying the distribution.

The "ring" distribution is specified by a 'dist-spec' command such as
the following (the "\" says the command continues on the next line):

    > dist-spec glog \
        "x^2/2 + y^2/2 + z^2/2 + (x+y+z)^2 + 10000/(1+x^2+y^2+z^2)"

Recall that the formula given to 'dist-spec' is the "energy function",
which is minus the log probability density, plus any constant.  If the
energy function above consisted of only the first three terms, the
distribution would be multivariate normal, with x, y, and z being
independent, each having mean zero and variance one.  The fourth term,
(x+y+z)^2, leaves the distribution still normal, but squashes it in
the direction where x, y, and z increase equally.  The final term is
large near the origin, and from there decreases to zero symmetrically
in all directions.  It has the effect of making a hole in the centre
of what would otherwise have been a normal distribution, leaving a
ring shape.

The examples below are assumed to start with a 'dist-spec' command of
the above form, except that "glog" is replaced with the name of the
log file used for the method being demonstrated.


Multivariate Metropolis updates.

We will first see how to sample from this distribution using a
variation of the Metropolis algorithm in which all three state
variables are changed simultaneously.  In the proposal distribution
used, new values for the state variable are chosen independently, each
from a normal distribution with mean equal to the present value, and a
specified standard deviation.

The following command specifies that 50 Metropolis operations of this
sort should be done for each full iteration:

    > mc-spec glog.met,1 repeat 50 metropolis 1 end

Here, "glob.met,1" is the name of the log file to use, which would
have been created using a 'dist-spec' command like the one above.  The
"repeat 50 ... end" construction causes the enclosed operations to be
repeated the given number of times.  This saves space in the log file,
compared to doing one metropolis operation for 50 times as many
iterations.  This is appropriate when many such operations will be
needed to get to a substantially different point.  A similar result
can be obtained using an extra argument to 'dist-mc' (see xxx-mc.doc),
but using "repeat" has the advantage that one can also easily look at
the rejection rate over the 50 repetitions.

We can now sample for 2000 Markov chain iterations (a total of 100000
metropolis updates) with the following command:

    > dist-mc glog.met,1 2000

This takes about three seconds on a 550MHz Pentium III, as will all
the other sampling commands in this section.

We can look at what happened to the three state variables during these
2000 iterations with a command such as

    > dist-plt t xyz glog.met,1 | plot

Depending on your plot program's requirements, you might instead use
a command such as

    > dist-tbl txyz glog.met,1 | plot

or you might have to plot the variables one at a time, with commands
such as
   
    > dist-plt t x glog.met,1 | plot

From these plots, you can see that the chain quite rapidly reached the
equilibrium distribution - maybe even by the end of the first
iteration (ie, within the first 50 metropolis updates).  Just to be
sure, however, let's discard the first 10 iterations as "burn-in".

We can now take a look at the "ring" distribution with commands like

    > dist-plt x y glog.met,1 11: | plot-points

If "plot-points" plots points rather than lines, this will produce a
scatterplot of the distribution for "x" and "y" (with "z" ignored),
which will look like a flattened ring.  The ring is actually circular,
but it's tilted with respect to the axes, so you'll be able to see it
as a circle only if you have a three-dimensional plotting program.

However, the plot above will probably not show points distributed
perfectly uniformly around the ring.  Instead, there will be clumps
here or there, which result from inadequate sampling.  The 1990 points
plotted are not independent, as can also be seen from the plots of
"x", "y", and "z" versus "t".  To get a sample of points that are a
good representation of the distribution using this chain, it would
need to be run for more iterations.

We can get a quantitative idea of how poor the sampling is with the
following command:

    > dist-tbl x glog.met,1 11: | series mac 50

    Number of realizations: 1  Total points: 1990

    Mean: 1.917904  S.E. from correlations: 0.835186
    
      Lag  Autocorr.  Cum. Corr.
    
        1   0.947969    2.895939
        2   0.903250    4.702439
        3   0.856662    6.415764
        4   0.815864    8.047491
        5   0.779712    9.606916
        6   0.743362   11.093639
        7   0.709530   12.512700
        8   0.673265   13.859229
        9   0.637696   15.134622
       10   0.601621   16.337865
       11   0.570915   17.479695
       12   0.540031   18.559758
       13   0.510186   19.580130
       14   0.482173   20.544476
       15   0.453319   21.451113
       16   0.425552   22.302216
       17   0.403801   23.109819
       18   0.383645   23.877109
       19   0.360901   24.598911
       20   0.346566   25.292043
       21   0.331396   25.954835
       22   0.318166   26.591167
       23   0.301436   27.194038
       24   0.283314   27.760666
       25   0.269474   28.299614
       26   0.254748   28.809109
       27   0.238075   29.285260
       28   0.221027   29.727313
       29   0.204618   30.136549
       30   0.190573   30.517694
       31   0.178569   30.874831
       32   0.166869   31.208569
       33   0.154004   31.516577
       34   0.139692   31.795961
       35   0.123347   32.042654
       36   0.106315   32.255285
       37   0.090566   32.436417
       38   0.077699   32.591815
       39   0.067531   32.726877
       40   0.056948   32.840774
       41   0.050116   32.941005
       42   0.042926   33.026856
       43   0.037561   33.101978
       44   0.030714   33.163407
       45   0.020496   33.204398
       46   0.010639   33.225675
       47   0.002995   33.231666
       48  -0.004550   33.222567
       49  -0.005873   33.210820
       50  -0.010653   33.189514

The 'dist-tbl' command above outputs a list of values for "x" for
iterations from 11 on.  The 'series' command with options "mac" finds
the mean of these numbers, their autocorrelations (out to lag 50
here), and the cumulative correlations.  The cumulative correlation at
the earliest lag past which the autocorrelations are about zero
indicates the factor by which sampling is made inefficient by the
correlations (here, about 33); see Ex-dist-n.doc for more details.

From symmetry, we know that the true mean for "x" is zero.  The
estimate of 1.917904 above is consistent with this, in view of the
estimated standard error of +-0.835186.  (Note that differences from
the true value of up to about twice the standard error are plausible.)
We can also get estimates using 'dist-est', but as discussed in
Ex-dist-n.doc, the standard errors it produces do not account for
autocorrelation.

We might try to improve the efficiency of sampling by changing the
standard deviation of the Metropolis proposal distribution - which is
also known as the "stepsize" for the operation.  One indication of
whether the stepsize is appropriate is the rejection rate for the
Metropolis operations, which can be viewed with a command such as

    > dist-plt t r glog.met,1 | plot

Here, the rejection rate is about 0.75, which is acceptable.  Very low
or very high rejection rates are usually an indication that sampling
would work better with a different stepsize.

Although the stepsize of 1 that was used above appears to be OK, we
could try a smaller stepsize with the following commands (following a
'dist-spec' command):

    > mc-spec glog.met,0.2 repeat 50 metropolis 0.2 end
    > dist-mc glob.met,0.2 2000

Or we might try a larger stepsize:

    > mc-spec glog.met,5 repeat 50 metropolis 5 end
    > dist-mc glob.met,5 2000

If enough iterations are done, the same estimates should be obtained
all these chains, but some stepsizes will produce a more efficient
chain than others.  By examining plots of how the state variables
change, and looking at the autocorrelations with 'series', one can
conclude that sampling is much less efficient with a stepsize of 0.2
than with a stepsize of 1 (about four times less efficient, based on
cumulative correlations).  With a stepsize of 5, the sampling is about
as good as with a stepsize of 1, even though the rejection rate is
quite high.  This is a phenomenon that occurs only in problems with an
effective dimensionality of three or less - for higher-dimensional
problems, a rejection rate close to one is generally an indication of
poor sampling.


Single-variable Metropolis updates.

We can also try sampling using Metropolis updates that change only one
variable at a time.  This is done using "met-1" operations, specified
as follows:

    > mc-spec glog.met1,1 repeat 18 met-1 1 end

As with "metropolis" operations, we specify a "stepsize", which is the
standard deviation for proposed change to a variable.  Each "met-1"
operation tries to change each variable in turn, accepting or
rejecting the change based on the change in energy as a result of
making the proposed change to just that variable.  Since there are
three state variables for this distribution, a single "met-1"
operation must therefore calculate the energy three times, and hence
takes about three times as long as a "metropolis" operation.  To
facilitate comparisons, the repeat count is corresponding less in this
specification.

As before, can now sample for 2000 iterations using a 'dist-mc' command:

    > dist-mc glog.met1,1 2000

You can see how well this method samples in the same ways as discussed
above.  You could also try sampling using "met-1" with a stepsize of
0.2 and 5.  You should see that the rejection rate with "met-1" is
lower than with "metropolis" operations using the same stepsize.
Nevertheless, sampling from this distribution seems to be less
efficient with "met-1" than with "metropolis".  This is not always so,
however.  For distributions where at least some of the variables are
close to being independent, updating one variable at a time can be
more efficient.  It is also sometimes possible to save computation
time when recomputing the energy after a change to just one variable,
though that possibility is not presently exploited by this software.


Single-variable slice sampling.

Variables can also be updated one at a time is using single-variable
slice sampling, which is described in my tech report on "Markov chain
Monte Carlo methods based on `slicing' the distribution" (available
from my web page), or the newer version, called "Slice sampling".
Several variations on this procedure are implemented in this software.
The method in which the slice is found by "stepping out" can be done
as follows:

    > mc-spec glog.slc1,1 repeat 4 slice-1 1 end
    > dist-mc glog.slc1,1 2000

This does single-variable slice sampling using an initial interval of
size 1, which is extended in steps of the same size until both ends
are outside the slice.  The "doubling" procedure is also implemented,
but is not illustrated here.

The "e" quantity records the average number of energy function
evaluations done in the slice sampling updates for one iteration.
We can find the average of this quantity over all iterations with
a command such as

    > dist-tbl e glog.slc1,1 | series m

    Number of realizations: 1  Total points: 2000

    Mean: 5.390583

Note that 5.390583 is the average number of evaluations for updating
one variable, not for updating all three of them.

As with the Metropolis methods, performance varies with the stepsize
chosen.  However, one advantage of single-variable slice sampling is
that it is a bit less sensitive to the choice of stepsize than the
single-variable Metropolis algorithm.


Multivariate slice sampling.

We can also use variations of slice sampling in which all variables
are updated simultaneously, described in my new technical report on
"Slice sampling".  The simplest such scheme randomly places a
hyperrectangle containing the current point, picks points randomly
from it, and shrinks it when the point chosen is outside the slice,
until a point inside the slice is finally found.  This can be done
with an mc-spec command such as the following:

    > mc-spec glog.slc,5 repeat 13 slice 5 end

This works almost as well as multivariate Metropolis with a stepsize
of 1 or 5.

One can also specify that shrinkage is to occur only in the coordinate
direction where the product of the energy gradient and the dimension
of the hyperrectangle is greatest in magnitude.  The following command
does this, with the number of repetitions set so that the time per
iteration is about the same:

    > mc-spec glog.slcg,5 repeat 6 slice -g 5 end

For this problem, using the gradient information with -g (or -G,
another variant) gives little or no advantage, after accounting for
the extra time needed to compute the gradient.  However, for problems
where variables have greatly differing scales (not compensated for by
differing stepsizes), the -g and -G options can be very beneficial.

One can also try multivariate slice sampling with Gaussian "crumbs"
rather than hyperrectangles:

    > mc-spec glog.sgau,5 repeat 13 slice-gaussian -e 5 end

The -e option results in the Gaussian distribution being shrunk on the
basis of the energy of the rejected trial point.


Sampling with Hamiltonian dynamics.

It is possible to sample much more efficiently by suppressing the
random walk behaviour that the methods above all exhibit.  One way of
doing this is by adding "momentum" variables, which will keep the
state moving in the same direction for an extended period of time.
The original "position" variables along with these "momentum"
variables can be updated by applying Hamiltonian dynamics for some
period of fictitious time, implemented by performing some number of
"leapfrog" steps with a specified stepsize.  To produce an ergodic
Markov chain, the momentum should also be changed using "heatbath"
updates, but it should not be changed too quickly, as this will
re-introduce random walk behaviour.  For a detailed discussion of this
"stochastic dynamics" method, see my book, Bayesian Learning for
Neural Networks, or my review paper, Probabilistic Inference Using
Markov Chain Monte Carlo Methods.

We can try out this dynamical method as follows:

    > mc-spec glog.dyn,0.3 repeat 40 heatbath 0.98 dynamic 1 0.3 end
    > dist-mc glog.dyn,0.3 2000

The argument of "heatbath" is the factor by which to multiply the old
momentum variables (after which noise is added).  A value of 1-d
results in random walks being suppressed for around 1/d iterations.

If you now look at the state variables with a command such as

    > dist-plt t xyz glog.dyn,0.3 | plot

you will see that they are initially far from their stationary
distribution, but after about 50 iterations they settle down, and from
there on the chain samples very well.  The initial behaviour of the
chain can be understood by looking at what is happening to the the
"kinetic energy", which is half the sum of squares of the momentum
variables:

    > dist-plt t K glog.dyn,0.3 | plot

Initially, the kinetic energy (as well as the "potential" energy,
which is what is specified in 'dist-spec') is very large.  It is only
slowly dissipated, as a result of the "heatbath" updates of the
momentum variables.  Eventually, however, the kinetic energy reaches
its equilibrium distribution (around a value of 3/2), and the chain
samples from approximately the desired distribution. 

This method is not exact, however, because the Hamiltonian dynamics is
simulated inexactly, biasing the results.  The hybrid Monte Carlo
method eliminates this bias by a using an acceptance test.


Hybrid Monte Carlo.

Several variations of the hybrid Monte Carlo method are supported by
this software.  In the "standard" method, each iteration starts by
picking completely new values for the momentum variables with the
"heatbath" operation.  Hamiltonian dynamics is then simulated for some
number of leapfrog steps, using some specified stepsize, and the
end-point of the simulated trajectory is accepted or rejected based on
the change in the total energy.  

The following commands apply the standard hybrid Monte Carlo method,
using trajectories of 45 leapfrog steps, done with a stepsize of 0.3.
To avoid problems with large initial energies, a few Metropolis
updates are done at the beginning.

    > mc-spec glog.hmc,0.3 repeat 50 metropolis 1
    > dist-mc glog.hmc,0.3 1
    > mc-spec glog.hmc,0.3 heatbath hybrid 45 0.3
    > dist-mc glog.hmc,0.3 2000

The length of the trajectory should be chosen based on the number of
steps for which we want to suppress random walks - longer for more
difficult problems where it takes many steps to get from one end of
the distribution to the other.

As with the Metropolis methods, you can check the rejection rate with
a command such as the following (the 2: causes the first iteration,
which consisted of Metropolis updates, to be excluded):

    > dist-tbl r glog.hmc,0.3 2: | series m

    Number of realizations: 1  Total points: 2000

    Mean: 0.035518

It is also useful to look at the changes in energy on which the
decisions to accept or reject were made:

    > dist-plt t D glog.hmc,0.3 2: | plot-points

If most of these points are much greater than one, the rejection rate
will be high.  With a stepsize of 0.3, the change in energy is seldom
greater than 0.5, but if the stepsize is increased to 0.8 much larger
changes are often seen, and with a stepsize of 1, almost no
trajectories are accepted.  

We can see how well the chain is sampling by plotting the state
variables, as described above, and by looking at the autocorrelations,
with a command such as:

    > dist-tbl x glog.hmc,0.3 10: | series mac 10

    Number of realizations: 1  Total points: 1991
    
    Mean: 0.476539  S.E. from correlations: 0.283180
    
      Lag  Autocorr.  Cum. Corr.
    
        1   0.519048    2.038096
        2   0.256602    2.551300
        3   0.129376    2.810052
        4   0.064013    2.938078
        5   0.042513    3.023104
        6   0.052457    3.128018
        7   0.026001    3.180021
        8   0.030900    3.241821
        9   0.025965    3.293750
       10  -0.004491    3.284769

From the cumulative correlations, we can estimate that estimating the
expectation of "x" using points from this chain is a factor of only
about 3.3 less efficient than using independent points.  This is about
ten times better than the best of the chains described above.

On the other hand, we have seen that some care is needed to pick an
appropriate stepsize for hybrid Monte Carlo, and it is also often
necessary to start at a reasonably good point, as was done here by
doing a few Metropolis updates at the beginning.

The "persistent" form of hybrid Monte Carlo (described in Bayesian
Learning for Neural Networks) is also implemented.  Here are the
appropriate commands:

    > mc-spec glog.phmc,0.18 repeat 50 metropolis 1
    > dist-mc glog.phmc,0.18 1
    > mc-spec glog.phmc,0.18 repeat 35 heatbath 0.99 hybrid 1 0.18 negate end
    > dist-mc glog.phmc,0.18 2000

The use of a "heatbath" operation with a non-zero "decay" causes the
momentum to change only slowly.  Because of this, even though only a
single leapfrog update is done, random walk behaviour will still be
suppressed.  The "negate" operation negates the momentum, which
normally undoes a negation at the end of the "hybrid" operation.  If
the "hybrid" update was rejected, however, the first negation will not
have been done, and movement will be reversed, undermining the random
walk suppression.  To avoid this, a smaller stepsize is used, to keep
the rejection rate very small.  Performance is a bit worse than for
the standard hybrid Monte Carlo method.


Reflective slice sampling.

Another way of avoiding random walks is to apply slice sampling to all
variables at once, and to sample from within the multivariate slice by
a sort of dynamical method that proceeds at a constant speed while
reflecting off the boundaries of the slice.  We would rather not
compute these boundaries exactly, however.  Instead, we can proceed in
steps of some size and when we cross the boundary reflect at either
the last inside point or the first outside point.  These reflection
operations are based on the gradient of the energy at that point.

Slice sampling with reflection from the last inside point is done as
follows:

    > mc-spec glog.slci,0.3 heatbath slice-inside 35 0.3
    > dist-mc glog.slci,0.3 2000

The "heatbath" operation picks a random momentum vector, which sets
the speed of motion and the initial direction.  We then find the slice
and take 35 steps within the slice with that velocity, using a
stepsize of 0.3 (ie, the change in the state at each step is 0.3 times
the momentum vector).  If a step takes us from inside the slice to
outside the slice, we backtrack, and change the momentum vector by
reflection based on the gradient.  It is necessary to check that this
reflection would also occur in the reversed trajectory; if not, we
must reject by negating the momentum, causing further steps to retrace
the trajectory.  Rejections will be less frequent if the stepsize is
small.

Slice sampling with outside reflection is done as follows:

    > mc-spec glog.slco,0.3 heatbath slice-outside 45 0.3 
    > dist-mc glog.slco,0.3 2000

This method operates as described for inside reflection, except that
when a step ends at a point outside the slice, we stay there, but
reflect based on the gradient at that point.  If the final point is
inside the slice, we accept it.  Otherwise we reject, and return to
the point from which the trajectory started.  

Both inside and outside reflection work reasonably well for this
distribution - not quite as good as hybrid Monte Carlo, but better
than the other methods.


Overrelaxed slice sampling.

Random walks can also be suppressed for some distributions using
single-variable slice sampling with "overrelaxation", in which
variables are changed from their current point to the corresponding
point on the "other side" of their conditional distribution.  This can
be done with the following commands:

    > mc-spec glog.slcv,0.3 slice-over 8 0.1 0.3 
    > dist-mc glog.slcv,0.3 2000

The first argument of "slice-over" is the number of "refinements" used
to more accurately pin down the end-points of the slice (using
bisection).  More refinements result in an update that is closer to an
ideal overrelaxed update, and also reduces the probability of
rejection (caused by the overrelaxed point being outside the slice).
The second argument specifies the probability of doing an ordinary
single-variable slice sampling update rather than an overrelaxed one.
Occasional ordinary updates are necessary in order to ensure
ergodicity, but they should not be done too often if random walks are
to be suppressed.  The final argument is the stepsize to use when
finding the endpoints of the slice initially.

For this distribution, overrelaxation does not work as well as the
dynamical methods or reflective slice sampling, but it is effective
for some other distributions.


Performance summary.

The following table summarizes the inefficiency factor for estimating
the expectation of the "x" variable using the various methods (the
autocorrelation time), determined from estimates of the cumulative
correlations up to when the autocorrelations are near zero.  The
repetition counts for the methods were set so that they all required
about 3 seconds of computation time for 2000 iterations (on a 550MHz
Pentium III).


  METHOD      STEPSIZE   AUTOCORR.  NOTES
                           TIME

  metropolis     0.2        130
                  1          33
                  5          21

  met-1          0.2        460  
                  1         140
                  5         170

  slice-1        0.2         77     Computation time was a bit over 3 seconds
                  1          59
                  5          65      

  slice           5          40
  slice -g        5          58
  slice -G        5          35

  slice-gaussian  5          68

  dynamic        0.3        2.0     This method is not exact

  hybrid (HMC)   0.3        3.3

  persistent HMC 0.18       8.9

  slice-inside   0.3         11
  
  slice-outside  0.3        5.6

  slice-over      2          35

The relative performance of the different methods will of course be
somewhat different for different distributions, but large gains from
using hybrid Monte Carlo (HMC) or other methods that suppress random
walks are common.


SAMPLING FROM A FUNNEL DISTRIBUTION IN TEN DIMENSIONS

Here I will illustrate some of the dangers of Markov chain sampling by
showing how even a rather simple distribution can pose problems, which
may not be obvious from simple plots.  This example also illustrates
how the adaptive nature of slice sampling can help prevent disaster.

The times reported here are for an older version of the software, run
on a 550 MHz Pentium III.


Specifying a "funnel" distribution.

Here is the specification for the distribution in this example:

    > dist-spec flog \
        "v~Normal(0,3^2)     + x1~Normal(0,Exp(v)) \
       + x2~Normal(0,Exp(v)) + x3~Normal(0,Exp(v)) \
       + x4~Normal(0,Exp(v)) + x5~Normal(0,Exp(v)) \
       + x6~Normal(0,Exp(v)) + x7~Normal(0,Exp(v)) \
       + x8~Normal(0,Exp(v)) + x9~Normal(0,Exp(v))"

(A "\" just indicates that the command is continued on the next line.)

There are ten variables above: "v" and "x1" to "x9".  The distribution
of v is normal with mean zero and standard deviation 3.  Given v, the
other variables are independent, and each has mean zero and variance
of Exp(v).  This can be pictured as a funnel - with v large at the
mouth of the funnel, getting smaller as the funnel narrows - except
that a cross section of the funnel has nine dimensions rather than the
two of the funnels found in kitchens.

It is of course possible to sample from this distribution directly, by
simply sampling for v, and then sampling for each of x1 to x9 given
this value for v, obtaining independent points from exactly the
correct distribution.  And even without doing this, we know what the
marginal distribution of v should be - just Normal(0,3^2), since the
dependency of x1 to x9 on v doesn't influence the distribution of v
itself.  It's precisely this ease of finding the right answer that
makes this an interesting test problem for the Markov chain methods.
The idea is to pretend that we don't already know the answer, and then
compare what we would conclude using the Markov chain method to what
we know is actually correct.

The dist-spec command above will be assumed to have been issued before
the commands discussed below, except that various log file names other
than "flog" will be used.


Specifying an initial state.

We'll have to start sampling in some initial state.  By default, the
state where all variables have the value zero is used, but we'll
assume here that a different initial state was specified using the
following command:

    > dist-initial flog v=0 x1=1 x2=1 x3=1 x4=1 x5=1 x6=1 x7=1 x8=1 x9=1

The point specified is typical of the distribution, since zero is the
median value for v, and v=0 corresponds to the variances of x1 to x9
being one, so that values of 1 for these variables are of typical
magnitude given this value for v.


Multivariate Metropolis updates.

As we did for the "ring" distribution (see Ex-dist-g.doc), we'll start
by trying to sample from this distribution using the Metropolis
algorithm, with proposals that change all variables simultaneously.
Using normally-distributed proposals centred on the current state,
with standard deviation of 1, seems like a plausible approach.  We can
specify this sampling method with mc-spec as follows:

    > mc-spec flog.met,1 repeat 10000 metropolis 1

The "repeat" above specifies that each iteration will consist of 10000
Metropolis updates.  The following command does 2000 such iterations,
for a total of 20 million Metropolis updates altogether:

    > dist-mc flog.met,1 2000

The state at the end of each iteration (ie, after each group of 10000
Metropolis updates) is saved in the log file.

Once this command has finished (which takes 16 minutes on a 550 MHz
Pentium III), we can produce a scatterplot from the points obtained in
order to see the relationship of x1 to v:

    > dist-plt x1 v flog.met,1 | plot-points

Here, plot-points is assumed to be a suitable plotting program.  The
"funnel" or "fan" shape should be visible in this plot.

We can look at how v varies from iteration to iteration with a plot
such as:

    > dist-plt t v flog.met,1 | plot-points

Exactly what you will see in this plot may depend on the machine you
run the programs on, due to possible differences in the random number
generator or in the details of floating-point arithmetic.  You can try
different random number seeds if you want to investigate the
possibilities (see rand-seed.doc).  However, it is likely that you
will see a plot in which the values of v at different times appear to
be almost independent, from which you might well conclude that the
Metropolis updates had converged to the right distribution, and moved
around it quite well.

But in fact, the answer obtained is very wrong.  You will probably see
few or no values for v less than -4, even though over 9% of the points
from a normal distribution with mean 0 and standard deviation 3 should
be less than this.  You're even less likely to see any values for v
less than -6, even though 2.3% of the points should be below this
value.

What you're probably seeing is therefore a "nightmare scenario" for
MCMC methods - a seriously wrong answer, with no apparent indication
that anything is amiss.  However, there is a chance that you will see
something that might warn you of the problem.  Now and then, the
Markov chain simulated above will "stick" at a low value of v (near
-4), due to rejections, and this sometimes lasts long enough for it to
be obvious in the plot.  Even if it's not obvious, if you are
suspicious enough to look closely, it's quite likely that you'll be
able to see such consecutive iterations where "v" has not changed.
The following plot is also revealing:

    > dist-plt t r flog.met,1 | plot-points

This shows that even though the average rejection rate for the
Metropolis updates is a fairly reasonable 80% (ie, 20% are accepted),
there are extended periods of time when the rejection rate is very
close to 100%.  A final confirmation of what's going on can be
obtained by looking at the relationship of the rejection rate over the
10000 Metropolis updates in an iteration with the value of v at the
end of the iteration:

    > dist-plt v r flog.met,1 | plot-points

This will show that the rejection rate tends to be high when v is
small.  

This is not surprising, at least in hindsight.  When v is -4, the
standard deviation of each of x1 to x9 (given this value of v) is
Exp(-4/2) = 0.135.  The chances that a Metropolis proposal with a
standard deviation of one for x1 to x9 will lie in the region of high
probability for x1 to x9 given v=-4 is very low (on the order of
0.135^9, which is about 1.5e-8).  The value of v also changes in a
Metropolis proposal, so this doesn't give the exact acceptance rate,
but it is nevertheless clear that the acceptance rate will be very low
when v is -4 or less, since the stepsize of one is too large for this
region.  Since the Metropolis updates leave the right distribution
invariant, it follows that the chain must only rarely move to points
were v is this small - since otherwise it would spend too much time
there.


Single-variable Metropolis updates.

Perhaps Metropolis updates that change only one variable at a time
will work better, since such updates will not suffer from the
extremely small acceptance probabilities that can result when the
proposals are too wide in many dimensions.

We can try this out using commands similar to those above, but with
the mc-spec command changed as follows:

    > mc-spec flog.met1,1 repeat 1300 met-1 1

The "met-1" operation does a single-variable Metropolis update for
each variable in turn (v and x1 to x9).  To make the comparison fair,
the number of repetitions has been reduced from 10000 to 1300, so that
the computation time per iteration is about the same as before.

As before, we can check how well the chain is moving around by
examining plots such as the following:

    > dist-plt t v flog.met1,1 | plot-points

Exactly what you will see may once again depend on what machine you
run the programs on, but you should see values for v that extend
downward much further than before, perhaps down to about -10.  The
single-variable updates do seem to avoid the problem encountered
before.

Unfortunately, the answer may still be wrong.  You will probably see
that for long stretches of time (many hundreds of iterations, perhaps
the entire run), the chain does not produce any values for v that are
greater than 7.  But almost 1% of points from a normal distribution
with mean zero and standard deviation 3 ought to be greater than 7,
about 20 points in the run of 2000 iterations.  Indeed, you'll
probably see about that many values for v less than -7 in the opposite
(symmetrical) tail of the distribution.

However, if you are lucky, you may see about the right number of
values for v greater than 7.  Once in a while, the chain enters the
region where v is this large, and then stays there for dozens of
iterations (ie, for tens of thousands of Metropolis updates).  As in
the explanation of the previous problem, since the chain stays a long
time in this region once it gets there, it must enter this region only
rarely, if it is to produce the right answer asymptotically.  In any
particular run, even one this long (2000 iterations, 2.6 million
"met-1" operations, 26 million single-variable updates), there is a
fairly large chance that this region will never be entered, in which
case the answer will be wrong without the plot showing any signs of
trouble.

Why does the chain stay a long time in the region where v is large
once it gets there?  The problem is the opposite version of that seen
before - the stepsize of one is too small.  When v is 7 or more, the
standard deviation of each of x1 to x9 is Exp(7/2) = 33 or larger.
Exploring the distribution of x1 to x9 given such a value for v by a
random walk with stepsize one is inefficient, and in particular, for a
long time, x1 to x9 can remain set to values that are incompatible
with a smaller value for v.  The problem is less noticeable for the
multivariate proposals above, since then all of x1 to x9 are changed
simultaneously, and the typical distance moved is Sqrt(9) = 3, which
leads to exploration that is 9 times faster.


Metropolis with random randomly-chosen stepsizes.

Since the problems above are due to the stepsize chosen being either
too big or too small given the current value of v, we might hope to do
better by not chosing a single stepsize, but instead picking a
stepsize randomly for each update, from some distribution.  

The following command does this, for multivariate Metropolis updates:

    > mc-spec flog.metv,1 repeat 10000 metropolis 1:-6

The the stepsize specification of 1:-6 means that the stepsize is
chosen randomly, with a median of 1, spread out uniformly over 6
orders of magnitude.  That is, the log base 10 of the stepsize is
uniformly distributed from -3 to +3.

After running this chain for 2000 iterations, we can look at how well
v is being sampled:

    > dist-plt t v flog.met1,1 | plot-points

The results are better than for multivariate Metropolis with a fixed
stepsize of one.  Values for v down to about -6 are sampled reasonably
well.  However, values smaller than -6 are sampled inefficiently, and
might not appear at all in a run of this length if you are unlucky.

Although random stepsize selection helps somewhat when the necessary
stepsize varies, it's hard to be sure that the range of stepsizes is
large enough to cover the necessary values without making the range so
large that the sampling becomes very inefficient simply because most
stepsizes chosen are ridiculously large or small.


Single-variable slice sampling.

One advantage of single-variable slice sampling is that the initial
interval can be expanded until it contains the entire slice using the
"stepping-out" or "doubling" procedures, and conversely, the interval
can be shrunk when the point selected from it is found to be outside
the slice.  The result is that the interval size adapts to the current
situation, without the inefficiency of randomly selecting stepsizes as
in the example of the previous section.

Single-variable slice sampling (with an initial interval size of one)
can be specified as follows:

    > mc-spec flog.slc1,1 repeat 120 slice-1 1

The repetition count of 120 is set much lower than for the Metropolis
updates so that the computation time per iteration will be roughly the
same.  (Slice sampling may require evaluating the energy function at
many points in order to expand and contract the interval.)

After running the slice sampling chain for 2000 iterations, we can see
how well it did with a plot of v over time, as before:

    > dist-plt t v flog.slc1,1 | plot-points

The results this time appear good, with both tails being sampled well.
Points where v is greater than 9 and where v is less than -9 are
probably visible.  Out of 2000 points from a normal distribution with
mean zero and standard deviation 3, an average of 2.7 should be above
9, and similarly for the lower tail.


Multivariate slice sampling.

We can also try sampling using multivariate slice sampling, in which a
hyperrectangle containing the slice replaces the interval used in
single-variable slice sampling.  The simplest scheme such scheme, in
which the hyperrectangle is shrunk in all directions when the point
found is outside the slice, can be specified as follows:

    > mc-spec flog.slc,1 repeat 4000 slice 1

As before, the repetition count is chosen to make the computation time
per iteration approximately the same as for the other methods.  Note
that the software currently does not support expansion of the initial
hyperrectangle, so the hypercube of length one per side that is
created initially with this specification can only shrink, not expand.

This method does much better than the multivariate Metropolis method
at sampling small values of v (though it perhaps still has problems
for v less than -8), but it does not sample well for v greater than 6.
This is not surprising, since variables can change by no more than one
in each update, which will be inefficient when v is large.  This
problem can be reduced by making the stepsize larger (eg, "slice 10"),
but at the cost of somewhat greater computation time per update. It
seems that for this problem single-variable updates work better.



EXAMPLES OF CIRCULARLY-COUPLED MARKOV CHAIN SAMPLING

Circular coupling is a new method for diagnosing covergence and
discarding "burn-in" iterations, described in my technical report on
"Circularly-coupled Markov chain sampling".  The examples here
demonstrate this software's facilities for simple circular coupling,
using "xxx-wrap" (see xxx-wrap.doc), and for circular coupling with
multiple starting points (possibly done in parallel), using "xxx-circ"
(see xxx-circ.doc).

Note that although these facilities are implemented in a way that is
designed for general use, not all aspects of the software have been
adapted to this scheme.  Also, the coupling techniques used are still
being improved.  Presently, circular coupling cannot be used at all
with mixture models, and it is probably not yet useful for most neural
network models.  It can be used for regression models using Gaussian
processes (if appropriate Markov chain operations are used), but not
for classification models, or other models requiring latent variables.

The example below is pretty simple.  A more interesting example is in
the latest version of the technical report, but isn't included here.
There are also some command files demonstrating circular coupling in
the ex-bayes directory.

The command files for the example here and for two other examples are
in the ex-circ directory.


Circularly-coupled sampling for a Cauchy model.

To start, we can look at a simple example of a Bayesian model for data
that is Cauchy distributed.  There is just one parameter, u, for this
model, which is the location of the Cauchy distribution (the scale is
fixed at one).  The prior for u will be Normal(0,20^2), and two data
points will be assumed to have been observed, with values of 18 and 25.

Here is a specification for the resulting posterior distribution:

    > dist-spec clog "u~Normal(0,20^2)" "Log[1+(u-18)^2] + Log[1+(u-25)^2]"

Here, the two data values have been put into the likelihood expression
as constants.  There will therefore be no data file for this example.
The log file is written as "clog" above, but other names will be used
for the examples below.

One way of using circular coupling is to first simulate a chain in the
usual way, and then "wrap the chain around" in order to discard an
appropriate "burn-in" period, which is not from the stationary
distribution of the chain.  For this to work, however, we have to use
Markov chain operations that couple appropriately.  For one
dimensional problems, "random grid" Metropolis updates work well.  We
can specify such updates (with stepsize of 5) with the following
command, issued after the dist-spec command:

    > dist-spec clog.forw "u~Normal(0,20^2)" "Log[1+(u-18)^2] + Log[1+(u-25)^2]"
    > mc-spec clog.forw rgrid-met 5

The log file "clog.forw" will be the normal, "forward" version of the
chain.  We can run the chain for 500 iterations as follows:

    > dist-mc clog.forw 500

You can now plot the progress of the chain over time, starting from
its default initial state of u=0, using the following command:

    > dist-plt t u clog.forw | plot

Clearly, the initial portion of the chain is not representative of the
stationary distribution.  But it's not clear exactly how many
iterations should be discarded from the beginning.  With traditional
Markov chain sampling methods, we'd just have to make a somewhat 
ad hoc decision about this.

As an alternative, we can wrap the chain around - running it again
with log file clog.wrap, using the last state of clog.forw as the
start state, with the same random numbers as before.  This is done
with the following command:

    > dist-wrap clog.forw clog.wrap

The dist-wrap procedure will recognize when (if ever) the new chain
coalesces with the old chain (ie, reaches the same state).  Once that
occurs, there is no need to perform any further computation - the
remaining iterations in clog.wrap can simply be copied from clog.forw.

For this example, coalescence will probably occur within a few dozen
iterations.  The wrapped around chain can be plotted as follows:

    > dist-plt t u clog.wrap | plot

Provided certain assumptions about rapid coalescence are satisfied,
all the iterations in clog.wrap will come from approximately the right
distribution.

For other problems, however, it is possible that the wrapped-around
chain will not coalese with the original chain.  In this case, the
procedure must be repeated with a larger number of iterations.  Even
if coalescence does occur, however, it is possible that it takes too
long, on average - violating the assumptions needed for the answer to
be guaranteed to be (approximately) correct.

These assumptions can be tested by running chains from many starting
points, which this software draws from the prior distribution.  This
is done as follows:

    > dist-spec clog.circ "u~Normal(0,20^2)" "Log[1+(u-18)^2] + Log[1+(u-25)^2]"
    > mc-spec clog.circ rgrid-met 5
    > dist-circ clog.circ 10 50 5

The dist-spec and mc-spec commands are as before.  The dist-circ
command runs a circularly-coupled simulation from 10 starting points
(the first numerical argument), equally spaced along a 500-iteration
span, so that the sections between starting points consist of 50
iterations (the second numerical argument).  Each section is simulated
and re-simulated up to 5 times (the third numerical argument), with
the starting point the first time (called stage 0) being drawn from
the prior, and the starting points for later stages being set to the
final point from the last simulation of the previous section (with
wrap-around from the last section to the first).

A consistent circular chain is obtained if this process reaches a
state where every section starts at the final state of the previous
section, and ends at the initial state of the next section.  If this
happens after a number of stages that's no more than half the total
number, there is fairly good reason to think that the necessary
assumptions are met, and the states of the circular chain (which will
be in clog.circ) all come from a good approximation to the correct
posterior distribution.

If the -p option is given to dist-circ, the simulation will be done in
parallel, in so far as this is possible with the number of processors
your machine has.



EXAMPLES OF MARKOV CHAIN SAMPLING FOR SIMPLE BAYESIAN MODELS

The 'dist' programs can be used to sample from the posterior
distribution of the parameters of a Bayesian model, specified by
giving formulas for minus the log of the prior distribution, and for
minus the log likelihood for one case.  The model defines the
conditional distribution of one or more "target" values in a case,
given the values of the "inputs" for that case.  The cases are
independent of each other.

Models of this sort can handle regression and classification problems,
in which the "targets" are the response variables and the "inputs" the
predictor variables.  When the number of inputs is zero, the models
will estimate the joint probability or probability density of the
target values.  However, the set of allowed models is restricted by
the range of formulas supported, as well as by the present restriction
to no more than 10 inputs and 10 targets per case.  Also, latent
variables cannot be explicitly represented at present, though some
latent variable models can be defined by summing over the possible
latent values in the likelihood.  The facilities of this module are
meant primarily as a way of demonstrating the Markov chain sampling
methods on statistical problems, not as a comprehensive statistical
modeling package.

These examples also illustrate some of the Markov chain sampling
facilities not demonstrated earlier.  The linear regression example
(Ex-bayes-r.doc) illustrates the use of "windows" with hybrid Monte
Carlo.  The t-distribution example (Ex-bayes-t.doc) shows how one can
set stepsizes differently for different variables.  The example of
probability estimation for categorical data (Ex-bayes-p.doc) shows how
the marginal likelihood for a model (more generally, the normalizing
constant for the distribution) can be found using Annealed Importance
Sampling.

The data and command files for these examples are in the "ex-bayes"
directory.


A LINEAR REGRESSION MODEL

I generated 100 cases of synthetic data for this example, each case
consisting of two input (predictor) values and one target (response)
value.  The first input (i0) was randomly generated from the normal
distribution with mean zero and standard deviation one.  The second
input (i1) was set to the first input plus an offset that was normally
distributed with mean zero and standard deviation 0.1.  The two inputs
were therefore highly correlated.  The target value (t) was set to 
0.5 + 2.5*i0 - 0.5*i1 + e, where e was normally distributed noise with
mean zero and standard deviation 0.1.  This data was stored in the
file "rdata".


Specifying the model.

We can specify a Bayesian linear model for this data with a command
such as the following:

    > dist-spec rlog.met \
    >   "u ~ Normal(0,10^2) + w0 ~ Normal(0,10^2) + w1 ~ Normal(0,10^2) \
    >      + v ~ ExpGamma(1,0.2)" \
    >   "t ~ Normal (u + w0i0 + w1i1, Exp(-v))"

Here, the "\" characters at the ends of the lines tell the Unix shell
that the command is continued on the next line.  The "rlog.met"
argument of 'dist-spec' is the name of the log file to use.  The next
argument (which takes up two lines) is the prior specification.  It
must be put in quotes to keep the shell from interpreting the special
characters used.  The last argument is the likelihood specification,
which will also usually have to be quoted.

Let's first examine the likelihood above:

    t ~ Normal (u + w0i0 + w1i1, Exp(-v))

This says that the target value for a case, t, is modeled by a normal
distribution with mean given by u + w0i0 + w1i1 and variance given by
Exp(-v).  Here, u, w0, w1, and v are parameters of the model.  Model
parameters must have names starting with "u", "v", "w", "x", "y", or
"z", possibly followed by a single digit.  The two inputs for the case
are called i0 and i1.  If there were more than one target, they would
be called t0, t1, etc., but here the name "t" is used, which is a
synonym for "t0" (similarly "i" is a synonym for "i0").

The notation in the likelihood specification using "~" is actually an
abbreviation for the following:

    Log(2*Pi)/2 + [t - (u+w0i0+w1i1)]^2 / [2Exp(-v)]

which is minus the log of the normal probability density for t with
the given mean and variance.  In general, the likelihood is specified
by a formula giving minus the log of the probability or probability
density for the target or targets in one case, given the values of the
inputs.  Since the cases are assumed to be independent, minus the
total log likelihood is found by just adding these terms for all
cases.

The prior specification above is constructed with similar notation:

    u ~ Normal(0,10^2) + w0 ~ Normal(0,10^2) + w1 ~ Normal(0,10^2) 
      + v ~ ExpGamma(1,0.2)

This gives each of u, w0, and w1 an independent normal prior with mean
of 0 and standard deviation of 10 (ie, variance of 10^2).  The prior
specification is a formula for minus the log of the prior density, so
terms pertaining to different parameters are simply added together.
The terms involving "~" are abbreviations for minus the log prior
density for a known distribution.  Here, all the parameters are
independent under the prior, but it would be possible to make one
parameter depend on another, for instance by changing the term above
involving w1 to w1 ~ Normal(w0,10^2).

The "v" parameter is the log of the "precision" (inverse variance) for
the error term in the model.  The Markov chain sampling procedures
assume that the range of all variables being sampled is the entire
real line.  Since the precision is constrained to be positive, we must
represent it with some unconstrained variable that is transformed to
produce the actual precision.  An exponential transformation is often
convenient, and in this case is probably desirable in any case, in
order to make the Markov chain sampling more efficient.

Here, the prior for the precision is specified to be Gamma with shape
parameter of 1 and scale of 0.2 (which gives a mean value of 5).
Since we will generally want to represent Gamma variables by their
logs, the built-in ExpGamma distribution used here is for a variable
whose exponential has a Gamma distribution with the indicated shape
and scale parameters.


Specifying the data source.

After specifying the model with 'dist-spec', we need to say where the
data is found using 'data-spec', as follows:

    > data-spec rlog.met 2 1 / rdata .

The arguments after the name of the log file say that there are two
input values and one target value.  After the slash, the files where
the inputs and targets are found are given.  The "." says that the
targets are found in the same file as the inputs, following them on
the same line.  See data-spec.doc for more details and other options.


Sampling with Metropolis updates.

We can now sample from the posterior distribution of the model
parameters, after specifying how we want this to be done.  Here we'll
try sampling by Metropolis updates to all variables simultaneously:

    > mc-spec rlog.met repeat 45 metropolis 0.02 
    > dist-mc rlog.met 500

Each iteration will consist of 45 Metropolis updates, done using a
proposal distribution that adds a normally-distributed offset to each
variable with standard deviation 0.02.  The 'dist-mc' command does 500
such iterations (for a total of 22500 Metropolis updates).  This takes
4.4 seconds on the system used (see Ex-system.doc).

We can see what the average rejection rate was for these updates as
follows:

    > dist-tbl r rlog.met | series m

    Number of realizations: 1  Total points: 500

    Mean: 0.708978  

A rejection rate of 0.7 is about right, so the stepsize of 0.02 looks
to be about optimal.  If you had started by trying a much larger or
smaller stepsize, you would need to adjust it by trial and error to
get a rejection rate in the range of about 0.3 to 0.8.

We can look at how well the chain is sampling by plotting the four
state variables over time:

    > dist-plt t uw0w1v rlog.met | plot

From this plot, it appears that the equilibrium distribution is
reached by about iteration 100, and that the chain is sampling
somewhat adequately from then on, though with a substantial degree of
autocorrelation.  We can quantify the inefficiency in estimation of
the log precision, v, that results from these autocorrelations as
follows:

    > dist-tbl v rlog.met 100: | series mac 30

    Number of realizations: 1  Total points: 401
 
    Mean: 4.461414  S.E. from correlations: 0.026037
   
      Lag  Autocorr.  Cum. Corr.
    
        1   0.893653    2.787307
        2   0.807894    4.403095
        3   0.709395    5.821885
        4   0.621722    7.065329
        5   0.539335    8.143999
        6   0.462553    9.069106
        7   0.379245    9.827595
        8   0.311431   10.450456
        9   0.244173   10.938802
       10   0.198226   11.335254
       11   0.164614   11.664482
       12   0.126405   11.917293
       13   0.092779   12.102850
       14   0.074293   12.251436
       15   0.049729   12.350895
       16   0.037565   12.426024
       17   0.028010   12.482045
       18   0.026148   12.534341
       19   0.043167   12.620674
       20   0.062433   12.745541
       21   0.083616   12.912773
       22   0.108346   13.129465
       23   0.112400   13.354265
       24   0.111866   13.577997
       25   0.092298   13.762593
       26   0.076360   13.915313
       27   0.051526   14.018364
       28   0.038505   14.095374
       29   0.018084   14.131542
       30   0.006680   14.144903

The cumulative correlation up to lag 30, where the autocorrelation is
approximately zero, indicates that about 14 times as many points will
be needed to get an estimate of a given accuracy as would be needed if
the points were independent.  This inefficiency results from the high
dependency between w0 and w1, which can be seen in the following plot:

    > dist-plt w0 w1 rlog.met 100: | plot-points

This dependency is why the stepsize must be so small - proposed
changes must be small, as otherwise the new point is likely to be
incompatible with this dependency between w0 and w1.

Estimates for various functions of state can be found using
'dist-est'.  For example, we can predict the target value for input
values of i0=1.9 and i1=2.1 as follows:

    > dist-est "u + w0*1.9 + w1*2.1" rlog.met 100:
    
    Number of sample points: 401
    
    Estimates for u + w0*1.9 + w1*2.1:

      Mean:    4.18959  (standard error 0.00150075)
      Std.dev: 0.0300526

    NOTE: The standard errors assume points are independent

Note that since the points aren't close to being independent, the
standard error shown is not correct.  Note also that the standard
deviation shown is the posterior standard deviation of the linear fit
at this point.  The prediction for a target value in a case with these
inputs would have additional uncertainty due to the noise.


Sampling with hybrid Monte Carlo.

The posterior dependency between w0 and w1 makes Markov chain sampling
somewhat difficult for this problem.  One could try to eliminate this
dependency by a reparameterization, which would certainly be possible
for this fairly simple problem, but in general this may be tedious or
infeasible.  However, the inefficiencies caused by dependencies may be
reduced by suppressing the random walk aspect of the sampling, which
can be done by using hybrid Monte Carlo rather than the simple
Metropolis updates used above.

After 'dist-spec' and 'data-spec' commands that are the same as those
described above (apart from the name of the log file), we can sample
using hybrid Monte Carlo with commands such as the following:

    > mc-spec rlog.hmc heatbath hybrid 25 0.01
    > dist-mc rlog.hmc 500

One hybrid Monte Carlo update is done each iteration, consisting of a
"heatbath" operation that picks new values for the momentum variables,
followed by a dynamical trajectory of 25 leapfrog steps, with a
stepsize of 0.01.  This stepsize was picked by trial and error, and
results in a rejection rate of about 0.13.  In general, the stepsize
for this standard form of hybrid Monte Carlo should chosen so that the
rejection rate is somewhere between about 0.05 and 0.25.  The 500
iterations take 4.7 seconds on the system used (see Ex-system.doc),
about the same as the Metropolis run above.

From examining plots of the state variables over time, it seems that
the hybrid Monte Carlo chain reaches equilibrium much more quickly
than the Metropolis chain, and samples more efficiently once
equilibrium is reached.  For example, here are the autocorrelations
for the precision parameter, which we also looked at for the
Metropolis chain:

    > dist-tbl v rlog.hmc 20: | series mac 5

    Number of realizations: 1  Total points: 481
    
    Mean: 4.451747  S.E. from correlations: 0.005397
    
      Lag  Autocorr.  Cum. Corr.
    
        1  -0.077573    0.844854
        2   0.048169    0.941192
        3  -0.059657    0.821878
        4   0.021492    0.864861
        5  -0.071308    0.722244

The estimated autocorrelations above do not differ significantly from
zero.  It therefore appears that hybrid Monte Carlo is about ten times
more efficient than the simple Metropolis algorithm for this problem.


Hybrid Monte Carlo with windows.

Many other Markov chain methods could be applied to this problem, but
I will mention just one more - the variation of hybrid Monte Carlo in
which acceptance is based on "windows" of states at the start and at
the end of a trajectory.  This variation is described in my paper on
"An improved acceptance procedure for the hybrid Monte Carlo
algorithm" (Journal of Computational Physics, vol. 111, pp. 194-203,
1994), and more briefly in my book on Bayesian Learning for Neural
Networks.

This method can be applied to this problem as follows (after suitable
'dist-spec' and 'data-spec' commands):

    > mc-spec rlog.whmc heatbath hybrid 25:2 0.01
    > dist-mc rlog.whmc 500

The only difference compared to the specification for standard hybrid
Monte Carlo is the ":2" after the number of leapfrog steps (25).  This
specifies that windows of two states at the start and end of the
trajectory should be used.  Acceptance is based on the difference in
the total probability of all states in the window at the start and in
the window at the end.  The next state is picked from the end window,
if the trajectory was accepted, or from the start window, if the
trajectory was rejected, with state selected from the appropriate
window according to their relative probabilities.

Note that when windows are used the state may change even when there
was a "rejection", as long as one of the states in the start window is
of comparable probability to the starting state.  This provides some
insurance against getting stuck at a point where the rejection rate is
very high.  The use of windows also tends to reduce the rejection
rate.  In this problem, the rejection rate with windows is only 0.05,
less than the rate of 0.13 seen above for the standard hybrid Monte
Carlo algorithm, while the time is only slightly greater (due to a
slight overhead from using windows).  The benefit is small here, since
the standard hybrid Monte Carlo method was doing very well in any
case, but use of windows can make a bigger difference for some other
problems, and is almost cost-free if the window size is a small
fraction of the trajectory length.


MODELING REAL-VALUED DATA WITH A T-DISTRIBUTION

One can also define models for the unconditional distribution of one
or more target values, without reference to any input values.  Here, 
I will show how one can sample from the posterior distribution for the
parameters of a univariate t-distribution.  This example also shows
how to specify different stepsizes for different state variables.


Specifying the model.

Here is a specification for a model in which the degrees of freedom of
the t-distribution are fixed (at two), but the location and scale
parameters are unknown:

    > dist-spec tlog1 d=2 "u ~ Normal(0,10^2) + w ~ Normal(0,1)" \
                          "w + [(d+1)/2] Log { 1 + [(t-u)/Exp(w)]^2/d }"

The "d=2" argument defines a constant (the degrees of freedom), which
may be used in the formulas for the prior and the likelihood.  The
location parameter, u, is given a normal prior with mean zero and
standard deviation 10.  The log of the scale parameter, w, is given a
normal prior with mean zero and standard deviation 1.  The software
does not have a built-in t-distribution, so the likelihood has to be
specified by explicitly writing a formula for minus the log of the
probability of the target value (t) for given values of the model
parameters.  This formula must include all terms that depend on the
model parameters, but for sampling from the posterior it is not
necessary to include constant terms.  (However, it is necessary to
include all terms in the likelihood if the marginal likelihood for the
model is to be found using Annealed Importance Sampling.)


Specifying the data source.

We can specify that the data comes from the file "tdata" as follows:

    > data-spec tlog1 0 1 / tdata .

This says that there are no input values and one target value, and
that the data comes from the file "tdata" (note that one must say
where the input values come from even though there are zero of them,
but that one can then say that the targets come from the same place
using the "." specification).

The contents of "tdata" are as follows:

    0.9
    1.0
    1.1
    6.9
    7.0
    7.1


Sampling with the Metropolis algorithm.

We can now try sampling using the Metropolis algorithm with a stepsize
of 1, repeated 10 times each iteration:

    > mc-spec tlog1 repeat 10 metropolis 1
    > dist-mc tlog1 5000

This takes 1.6 seconds on the system used.  We can look at plots such
as the following to assess convergence:

    > dist-plt t uw tlog1 | plot

Equilibrium appears to have been reached within 50 iterations.  We can
now see a picture of the posterior distribution using a command such as

    > dist-plt u w tlog1 50:%3 | plot-points

This produces a scatterplot for the values of the two state variables
at those iterations from 50 on that are divisible by three.  Looking
at only every third state reduces the number of points that will be
superimposed, due to rejections of the Metropolis proposals.  (If some
points are superimposed, the scatterplot might be misleading.)

If you produce such a plot, you should see a tooth-shaped distribution
whose main mass is around u=3.9 and w=1, with two roots descending at
u=1 and u=7.


Varying the stepsizes.

The rejection rate of the metropolis operations with stepsize of 1 can
be estimated as follows:

    > dist-tbl r tlog1 | series m

    Number of realizations: 1  Total points: 5000

    Mean: 0.620760  

The efficiency of this chain at estimating the mean of u can be
assessed as follows:

    > dist-tbl u tlog1 50: | series mac 10

    Number of realizations: 1  Total points: 4951
    
    Mean: 3.963551  S.E. from correlations: 0.055950
    
      Lag  Autocorr.  Cum. Corr.
    
        1   0.625358    2.250717
        2   0.388528    3.027772
        3   0.254716    3.537205
        4   0.168077    3.873358
        5   0.106168    4.085695
        6   0.062758    4.211211
        7   0.031260    4.273732
        8   0.009645    4.293023
        9   0.001954    4.296931
       10  -0.006025    4.284882

An inefficiency factor of 4.2 is not bad, but we still might try to
improve sampling by using a different stepsize.  We can use a stepsize
twice as big by changing the 'mc-spec' command as follows:

    > mc-spec tlog2 repeat 10 metropolis 2

This produces a higher rejection rate:

    > dist-tbl r tlog2 | series m

    Number of realizations: 1  Total points: 5000

    Mean: 0.813800  

Despite this, the efficiency of sampling is improved:

    > dist-tbl u tlog2 50: | series mac 10
    
    Number of realizations: 1  Total points: 4951
    
    Mean: 3.916702  S.E. from correlations: 0.048513
    
      Lag  Autocorr.  Cum. Corr.
    
        1   0.502745    2.005491
        2   0.246632    2.498755
        3   0.133819    2.766394
        4   0.081335    2.929063
        5   0.053313    3.035689
        6   0.028491    3.092671
        7   0.013611    3.119892
        8   0.024985    3.169861
        9   0.013700    3.197261
       10   0.018007    3.233274

From the scatterplot of the posterior distribution, the larger
stepsize seems appropriate for u, but it seems too big for w.  We can
specify different stepsizes for u and w as follows:

    > dist-stepsizes tlog12 w=1 u=2
    > mc-spec tlog12 repeat 10 metropolis 1

The 'dist-stepsizes' command lets you specify individual stepsizes for
the state variables.  These values are multiplied by the stepsize
specified for the "metropolis" operation before being used, so you can
change the overall size of the steps by changing this argument, while
keeping the relative stepsizes the same.  

Using twice as big a stepsize for u as for w seems to work well, as 
seen by looking at the autocorrelations for u:

    > dist-tbl u tlog12 50: | series mac 10
    
    Number of realizations: 1  Total points: 4951
    
    Mean: 3.876082  S.E. from correlations: 0.036181
    
      Lag  Autocorr.  Cum. Corr.
    
        1   0.282051    1.564102
        2   0.061686    1.687474
        3   0.019975    1.727424
        4   0.010014    1.747453
        5  -0.004439    1.738575
        6   0.000983    1.740540
        7   0.000207    1.740954
        8   0.025230    1.791413
        9   0.004726    1.800866
       10  -0.001624    1.797619

The autocorrelations have been reduced to the point where the estimate
based on the points from this chain are a factor of only about 1.7
times less efficient than an estimate based on independent points.


MODELING PROBABILITIES FOR CATEGORICAL DATA

As an example of a model for categorical data, I will show here how to
model probabilities for targets that come from the set {0,1,2}, with
the prior distribution for these probabilities being uniform over the
simplex of valid probabilities.  This example illustrates one way of
representing probabilities using unbounded real parameters.  It can
easily be generalized to arbitrary Dirichlet priors.  I also show how
to compute the marginal likelihood for this model by using Annealed
Importance Sampling, and also by using simple importance sample (which
can be done as a degenerate case of AIS).


Specifying the model.

The probabilities for the three possible values of the target will be
represented using the parameters w0, w1, and w2, with the probability
of the value "0" being Exp(w0)/[Exp(w0)+Exp(w1)+Exp(w2)] and similarly
for the other values.  These probabilities will be positive and sum to
one for any values of the parameters.  This is necessary if we are to
use this software, since it doesn't allow state variables to be
constrained.

With this representation, the model can be specified by the following
somewhat formidable command:

    > dist-spec plog.met \
       "w0~ExpGamma(1,1) + w1~ExpGamma(1,1) + w2~ExpGamma(1,1)" \
       "-Delta(t-0)*(w0-LogSumExp(w0,w1,w2)) \
        -Delta(t-1)*(w1-LogSumExp(w0,w1,w2)) \
        -Delta(t-2)*(w2-LogSumExp(w0,w1,w2))"

These priors for w0, w1, and w2 will produce a uniform prior for the
resulting probabilities.  More generally, if the priors for w0, w1,
etc. are ExpGamma(a1,1), ExpGamma(a2,1), etc., the prior distribution
for the probabilities Exp(w0)/[Exp(w0)+...], Exp(w1)/[Exp(w0)+...],
and so forth will be Dirichlet with parameters a1, a2, etc.

The terms in the likelihood are constructed using the "Delta" function
which has the value one when its argument is zero and has the value
zero otherwise.  Since the target, t, is in the set {0,1,2}, exactly
one of the terms in the likelihood will be non-zero for each case.
When the target has the value "0", the likelihood should be minus the
log of the probability of the target being "0", that is:

    - Log { Exp(w0) / [ Exp(w0) + Exp(w1) + Exp(w2) ] }

In the specification above, this is written as

    - (w0 - LogSumExp(w0,w1,w2))

using the "LogSumExp" function, which computes the log of the sum of
the exponentials of its arguments.  This is shorter and faster.  More
importantly, the LogSumExp function is guaranteed to produce a valid
result even when computing Exp(w0), Exp(w1), or Exp(w2) would result
in floating point overflow or underflow.  This is probably not crucial
for this example, but it is important in some similar contexts.


Specifying the data source.

The data is stored one item per line in the file "pdata".  This source
is specified with the following command:

    > data-spec plog.met 0 1 3 / pdata .

The arguments after the log file are the number of input variables
(0), the number of target variables (1), and an argument (3) that
indicates that the targets are categorical with three possible values,
represented by the integers 0, 1, and 2.  This argument could have
been left out, but including it causes the data to be checked to
ensure that each item is in the set {0,1,2}.

The remaining arguments give the files where the inputs (all zero of
them) and targets come from, with the "." for the latter indicating
that the targets come from the same place as the inputs.

The file "pdata" contains 17 items, of which 6 are "0", 8 are "1", and
3 are "2".


Sampling with the Metropolis algorithm.

We can sample from the posterior distribution using any of various
Markov chain methods.  Here's one example using the Metropolis
algorithm:

    > mc-spec plog.met repeat 10 metropolis 1
    > dist-mc plog.met 1000

This takes 1.1 seconds on the system used (see Ex-system.doc).
Convergence is quite rapid, and the sampling efficiency is reasonably
good.

We can estimate the probabilities of the three possible values as
follows:

    > dist-est "Exp(w0)/[Exp(w0)+Exp(w1)+Exp(w2)]" plog.met 100:
    
    Number of sample points: 901
    
    Estimates for Exp(w0)/[Exp(w0)+Exp(w1)+Exp(w2)]:
    
      Mean:    0.349174  (standard error 0.00342273)
      Std.dev: 0.102739
    
    NOTE: The standard errors assume points are independent
    
    > dist-est "Exp(w1)/[Exp(w0)+Exp(w1)+Exp(w2)]" plog.met 100:
    
    Number of sample points: 901
    
    Estimates for Exp(w1)/[Exp(w0)+Exp(w1)+Exp(w2)]:
    
      Mean:    0.450742  (standard error 0.00354029)
      Std.dev: 0.106268
    
    NOTE: The standard errors assume points are independent
    
    > dist-est "Exp(w2)/[Exp(w0)+Exp(w1)+Exp(w2)]" plog.met 100:
    
    Number of sample points: 901
    
    Estimates for Exp(w2)/[Exp(w0)+Exp(w1)+Exp(w2)]:
    
      Mean:    0.200084  (standard error 0.00290151)
      Std.dev: 0.0870937
    
    NOTE: The standard errors assume points are independent

Note that since the points are not entirely independent, the standard
errors are not quite right.  For comparison, the exactly correct
posterior means of the three probabilities (found analytically) are
0.35, 0.45, and 0.2.

    
Computing the marginal likelihood with Annealed Importance Sampling.

We can use Annealed Importance Sampling (AIS) to find the prior
probability of the observed data given this model - sometimes called
the "marginal likelihood".  This is the normalizing constant for the
posterior distribution, if it is specified as the product of the prior
and the likelihood.  Annealed Importance Sampling (which is described
in a technical report of this name available from my web page) can
also help in handling isolated modes, though this should not be a
problem for this model.

To use AIS, we specify the model and the data source as above, and
then use the following commands:

    > mc-temp-sched plog.ais 0.1 0.3 0.6
    > mc-spec plog.ais AIS repeat 10 metropolis 0.5
    > dist-mc plog.ais 1000

The 'mc-temp-sched' command specifies a "tempering schedule": a series
of distributions that the annealing run will pass through.  For a
Bayesian model, these distributions are created by multiplying the log
likelihood part of the "energy" by various "inverse temperatures",
listed as arguments to 'mc-temp-sched'.  A final distribution with
inverse temperature of 1 is assumed at the end of the schedule.  This
final distribution is the posterior, which we wish to sample from, and
to find the normalizing constant for.

The chain proceeds sequentially through these distributions.  The
"AIS" operation moves to the next distribution in the schedule, and
updates a "weight" according to the ratio of probabilities under the
new and old distributions.  If the chain is at the last distribution
(at inverse temperature 1), it moves to the first distribution (here,
at inverse temperature 0.1), after first drawing a new state from the
distribution at inverse temperature 0, which for a Bayesian model is
the prior.  There are four temperatures in the tempering schedule
here, and each iteration does one "AIS" operation.  The 1000
iterations will therefore produce 250 annealing runs.

Markov chain operations such as "metropolis" operate as usual, except
that the "energy function" is modified by the inverse temperature.

For AIS to operate, it must be possible to sample from the prior.  If
the prior is specified entirely as a sum of "~" terms, with no
circular references, the software knows how to sample from it.
Otherwise, you must provide a separate program to do the sampling.
For how this is done, see the documentation on the -read-prior option
in dist-spec.doc and also the information in dist-mc.doc.

The commands above take 1.2 seconds on the system used (see
Ex-system.doc).  Once they have finished, we can estimate functions of
state with 'dist-est', which will automatically look at only the
iterations that pertain to the final distribution of interest.  It
also computes weighted estimates using the weights found during the
annealing runs.  Here is an example:

    > dist-est "Exp(w0)/[Exp(w0)+Exp(w1)+Exp(w2)]" plog.ais
    
    Number of sample points: 250
    
      Variance of normalized weights: 1.21148
      Adjusted sample size: 113.0  (reduction factor 0.452)
    
    Estimates for importance weights:
    
      Mean of weights: 2.85948e-09  (standard error 1.99056e-10)
      Log of mean:    -19.6726  (standard error 0.0696127)
    
    Standard estimates for Exp(w0)/[Exp(w0)+Exp(w1)+Exp(w2)]:
    
      Mean:    0.342344  (standard error 0.00925806)
      Std.dev: 0.100527
    
      Effective sample size: 117.9  (reduction factor 0.472)
    
    Jacknife estimates for Exp(w0)/[Exp(w0)+Exp(w1)+Exp(w2)]:
    
      Mean:    0.342353  (standard error 0.00934127)
    
      Effective sample size: 115.8  (reduction factor 0.463)
    
    NOTE: The standard errors assume points are independent
    
Note that there is no need to discard any of the early iterations,
since each annealing run is independent.  Because of this
independence, the standard errors computed are valid, subject to the
usual caveats regarding the possibility that some important part of
the distribution has been missed entirely.

Along with an estimate for expectation of the specified function,
'dist-est' outputs an estimate for the mean of the weights, which for
a Bayesian model will be the marginal likelihood, provided the
likelihood specification included all terms, even those that are
constant.  The log of this estimate is also output, since the value
will often be extremely small or large.

For this model, the marginal likelihood can be computed exactly by
multiplying successive predictive probabilities.  For this data, it is

       6! 8! 3! 
       --------  =  2.86378e-9    log is -19.67112
       19! / 2!

The estimates and estimated standard errors are consistent with this.

This problem is actually easy enough that the marginal likelihood can
be found by simple importance sampling.  This can be viewed as a
degenerate form of Annealed Importance Sampling in which the tempering
schedule has only one distribution - the assumed one, at temperature
1, which is the posterior.  We can do simple importance sampling with
the following commands:

    > mc-temp-sched plog.is -
    > mc-spec plog.is AIS 
    > dist-mc plog.is 1000

The 'mc-temp-sched' command with the argument "-" sets up the null
tempering schedule.  The 'mc-spec' command just has an "AIS"
operation, with no Markov chain operations.  This causes a new state
to be drawn from the prior every iteration, and the appropriate weight
to be computed based on the likelihood.

Estimates for expectations and for the marginal likelihood can be
found using 'dist-est'.  For example:

    > dist-est "Exp(w0)/[Exp(w0)+Exp(w1)+Exp(w2)]" plog.is

    Number of sample points: 1000
    
      Variance of normalized weights: 3.85409
      Adjusted sample size: 206.0  (reduction factor 0.206)
    
    Estimates for importance weights:
    
      Mean of weights: 2.83221e-09  (standard error 1.75827e-10)
      Log of mean:    -19.6822  (standard error 0.0620814)
    
    Standard estimates for Exp(w0)/[Exp(w0)+Exp(w1)+Exp(w2)]:
    
      Mean:    0.344737  (standard error 0.00530831)
      Std.dev: 0.104735
    
      Effective sample size: 389.3  (reduction factor 0.389)
    
    Jacknife estimates for Exp(w0)/[Exp(w0)+Exp(w1)+Exp(w2)]:
    
      Mean:    0.344731  (standard error 0.00532859)
    
      Effective sample size: 386.3  (reduction factor 0.386)
    
    NOTE: The standard errors assume points are independent
    
Importance sampling is faster than Annealed Importance Sampling for
this easy problem.  However, importance sampling quickly becomes
infeasible for problems with more parameters or with more data.
Annealed Importance Sampling is more feasible for realistic problems,
though some work is needed to set up a good tempering schedule, which
may have to include many more distributions than were needed for this
easy problem (often hundreds or more).  See mc-ais.doc for
documentation on how to obtain information that is helpful in
adjusting the tempering schedule.

The software also supports the related methods of simulated tempering,
tempered transitions, and tempered hybrid Monte Carlo.  Annealed
importance sampling and the tempering schemes are also supported for
neural network models and Dirichlet diffusion tree models (but not for
Gaussian process and mixture models).  There's no tutorial
documentation on these features, however, just the detailed command
documentation, and the command files in the 'ex-ais' directory that
implement the tests done in my "Annealed Importance Sampling" paper.


A RANDOM EFFECTS MODEL

In the simple random effects model treated here, measurements of some
quantity are available for individuals in a number of groups.  Each
group has associated with it a mean for individuals in the group
(these are the "random effects").  Note that this is the population
mean, not the mean for those individuals in the group that were
actually measured.  The measurements on individuals in the group are
equal to the group mean plus random individual variation.  The
distribution of the group means is modeled as being normal with some
unknown mean and unknown variance.  The individual variation within a
group is also modeled as being normal, with an unknown variance that
is the same for all groups.  The number of individuals in each group
for which there are measurements is considered to be externally
determined, and is thus not modeled.

The number of individuals in each group together with the sample means
and sample variances for each group are sufficient statistics for this
model; only these are provided in the data file 'edata' (one line per
group, in that order).  This data was synthetically generated using
the S-Plus program in sgen.s.  There are 18 groups, with the following
numbers of individuals in each group:

       1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4

The overall mean used to generate the data was 25, the variance of the
group means was 12^2, and the variance within a group was 6^2.


Specifying the model.

We can specify this random effects model as follows:

    > dist-spec elog.met \
       "u~Normal(0,10^2) + v1~Normal(0,2^2) + v2~Normal(0,2^2)" \
       "t0~Normal(u,Exp(v1)+Exp(v2)/i) + \
       (1-Delta(i-1)) * ExpGamma2(Log(t1),i-1,Exp(v2))"

There are three model parameters: the overall mean (u), the log of the
variance of the group means (v1), and the log of the variance of the
measurements within a group (v2).  The variances are represented by
their logs so that they will not have to be constrained.

The argument after the name of the log file to use ("elog.met") is the
prior specification.  The prior for the overall mean is normal with
mean zero and standard deviation 10.  The priors for the logs of the
variances are both normal with mean zero and standard deviation 2.
These parameters are independent under the prior, so the prior
specifications are just added together.

Each group will correspond to a "case", in the terminology used
elsewhere, since given values for the parameters the data on each
group is independent of the other groups.  The number of measurements
for the group will be regarded as an "input", since it is not being
modeled, while the sample mean and sample variance for the group will
be regarded as "targets".  (This distinction is currently just a
convention, but might be essential in future versions of the software.)

The likelihood for the data in a group is given by the last argument
(which is split between two lines).  The sample mean for the group
(target 0, written as "t0") has a normal distribution whose mean is
given by the overall mean parameter and whose variance is the sum of
the variance of the group means (Exp(v1)) and the variance of the
measurements within a group (Exp(v1)) divided by the group size (the
input, written as "i0", or "i").  As is well known, the sample
variance is independent of the sample mean, and has a gamma
distribution.  This is specified by the last term in the likelihood
argument.  There is a complication due to the possibility of a group
with just one measurement, for which the sample variance is undefined
(it will be zero in the data file).  This is handled by including a
factor of (1-Delta(i-1)), which is zero if "i" is one, and is one
otherwise.  The remainder of this term, ExpGamma2(Log(t1),i-1,Exp(v2)), 
evaluates to the log of the density for Log(t1), the log of the sample
variance.  This specifies that t1 has the gamma distribution with
shape parameter (i-1)/2 and mean Exp(v2), which corresponds to the sum
of the squared deviations having a chi-squared distribution with i-1
degrees of freedom.  Note that the syntax using "~" cannot be used
for a transformed variable such as Log(t1).  


Specifying the data source.

The source of the data is specified as follows:

    > data-spec elog.met 1 2 / edata .

For this model, each "training case" is a group.  The above command
says there is one "input" for each group (the number of measurements)
and two "targets" (the sample mean and sample variance for the group).
The inputs come from 'edata', and the targets come from there as well,
following on the same line as the input.


Sampling with Metropolis updates.

We can now specify what Markov chain operations to use in each
iteration.  The following command specifies that each iteration should
consist of 25 Metropolis updates using a proposal distribution in
which each of the three parameters are changed by an amount that is
normally-distributed with standard deviation 0.5:

    > mc-spec elog.met repeat 25 metropolis 0.5

We can now sample for 10000 iterations with the following command:

    > dist-mc elog.met 10000

This takes 28 seconds on the system used (see Ex-system.doc).

A scatterplot of the posterior distribution for v1 and v2 can be
obtained using a command such as

    > dist-plt v1 v2 elog.met 100: | plot-points

The first 100 iterations are discarded, as possibly not being
representative of the posterior distribution.  This plot should show
most of the points in an ellipse centred at v1=4.5, v2=3.8, which
corresponds to a between-group standard deviation of about 9.5 and a
within-group standard deviation of about 6.7.  However, a few points
are far outside this ellipse, having much smaller values of v1, and
values for v2 around 5.  These points correspond to the possibility
that the group means are almost the same, with the variation in the
sample means for the groups being almost entirely due to sampling
variation resulting from the within-group variance.  Given the data
seen, this is is unlikely, but it is not completely excluded.


Slice sampling.

We can also use slice sampling for this problem.  One variation of
slice sampling is specified as follows:

    > mc-spec elog.slc repeat 5 slice-1 2 1
    > dist-mc elog.slc 10000

Each iteration consists of 5 repetitions of a single-variable slice
sampling update for each parameter.  These updates are based on
randomly positioning an interval of width 2 around the current point,
and then sampling successively from this interval until a point within
the slice is found.  The last argument of "1" specifies that the
maximum interval size is just one times the width parameter.  Since
there is no possibility of widening the interval, there is no need to
evaluate the energy function at the interval's endpoints.  This saving
may make this approach beneficial in some circumstances.

These 5 slice sampling operations take about the same time as the 25
Metropolis updates of the previous section.  The resulting sampling
efficiency is also about the same for this example.



EXAMPLES OF FLEXIBLE BAYESIAN REGRESSION AND CLASSIFICATION MODELS
BASED ON NEURAL NETWORKS AND GAUSSIAN PROCESSES

Neural networks and Gaussian processes can be used to to predict a
target value (or values) from a set of input values.  When the target
is real-valued, this is known as "regression".  When the target takes
on values from a finite set, it is known as "classification".
Examples of both sorts are discussed here.

The data and command files for these examples are in the "ex-netgp"
directory.


A SIMPLE REGRESSION PROBLEM

As a first example, we will look at a simple regression problem, 
in which there is one real-valued input for each case, and one
real-valued target, whose value is to be predicted.

I generated synthetic data of this type in which the input variable,
x, for each case had a standard Gaussian distribution and the
corresponding target value came from a Gaussian distribution with
standard deviation 0.1 and mean given by

         0.3 + 0.4*x + 0.5*sin(2.7*x) + 1.1/(1+x^2)

I generated 200 cases in total, stored in the file 'rdata'.  Each case
consists of a line containing first the input value and then the
target value.  The first 100 of these cases are meant for training,
and the second 100 for testing.


A neural network model for the regression problem.

We will model this data using a multilayer perceptron with one input
unit, one hidden layer of eight tanh units, and a single output unit
whose activation function is the identity.  The value of the output
unit will be taken as the mean of a Gaussian distribution for the
target, with the standard deviation of this Gaussian (the noise level)
being a hyperparameter to be estimated along with the parameters of
the network.  We will also use hyperparameters to express the prior
distributions for the network parameters.  Specifically, we will use
one hyperparameter for the input-to-hidden weights, one for the hidden
unit biases, and one for the hidden-to-output weights.  The output
unit bias will be given a simple Gaussian prior, with no adjustable
hyperparameter.  (The role of hyperparameters is primarily to
introduce dependencies between parameters, so they are usually not
used when they would control just a single parameter.)

The first step in applying this model to the data is to create a log
file containing the specifications for the network architecture and
the priors to use for the network parameters.  This can be done using
the following command:

    > net-spec rlog.net 1 8 1 / - 0.05:0.5 0.05:0.5 - x0.05:0.5 - 100

Here, "rlog.net" is the name of the new log file, and the arguments
"1", "8", and "1", specify the numbers of input, hidden, and output
units.  Following the "/", the priors for the various groups of
network parameters are given, with a "-" indicating that a parameter
group should be omitted (equivalent to the parameters being zero).
The order of the groups is a bit hard to remember, but you can get a
summary easily by just invoking 'net-spec' with no arguments.  The
groups in the above command that are not omitted are the input-hidden
weights, the hidden biases, the hidden-output weights, and the output
bias.

In general, the prior specifications used in the net-spec command
consist of a "width" value followed by up to three "alpha" values,
with perhaps an option character tacked on to the front.  For the full
details, see Appendix A of my thesis and prior.doc.  Here, I will just
comment on the particular priors used above.

The prior specification used for the output bias is simply "100",
which means that the bias has a Gaussian prior with mean zero and
standard deviation 100.  The prior specifications of the form
"0.05:0.5" indicate that the parameters in these groups are associated
with a hyperparameter, which gives the standard deviation of a
Gaussian prior for these parameters.  The hyperparameter itself has a
rather vague prior that spans several orders of magnitude around one.
The inverse gamma priors used are somewhat difficult to visualize,
because their tails are asymmetrical, but some standard choices are
often appropriate.  Here, the "0.5" after the colon controls how vague
the prior is (closer to zero is more vague).  The "0.05" specifies the
location of this vague distribution, but due to the asymmetry of the
tails, it is closer to being the lower limit of the prior than the
centre (for vague priors such as this).

The "x" in front of the prior for the hidden-to-output weights
indicates that the prior should be automatically rescaled based on the
number of hidden units, so as to produce an effect that is independent
of the number of hidden units (in the limit of large numbers).

Once the network has been specified, we need to say how the network
outputs will be used to model the targets (response variables) in the
data set.  We do this with the 'model-spec' command:

    > model-spec rlog.net real 0.05:0.5

In this case, the targets are real-valued, and are modeled as the
network output plus Gaussian noise, with the noise standard deviation
being a hyperparameter having the prior given by the last argument of
the command.  The syntax of the prior specification is the same as for
the priors on network parameters. 

You can view the architecture and prior specifications stored in the
log file by invoking 'net-spec' with just a log file argument.  In
this example, this should give the following result:

    > net-spec rlog.net

    Network Architecture:
    
      Input layer:     size 1
      Hidden layer 0:  size 8  tanh
      Output layer:    size 1
    
    
    Prior Specifications:
    
             Hidden Layer 0
    
      Input-Hidden Weights:    0.050:0.50
      Hidden Biases:           0.050:0.50
    
             Output Layer
    
      Hidden0-Output Weights: x0.050:0.50
      Output Biases:           100.000

You can also view the model specification by invoking 'model-spec'
with just one argument giving the log file.

Once the network and data model have been specified, we need to
specify the data sets to be used for training and (optionally) for
testing.  We do this using the 'data-spec' command:

    > data-spec rlog.net 1 1 / rdata@1:100 . rdata@101:200 .
    Number of training cases: 100
    Number of test cases: 100

Here, "rlog.net" is the log file we created with 'net-spec', to which
the data specifications will be appended.  The "1" and "1" arguments
give the numbers of inputs and targets.  These must be consistent with
the network architecture (if not, an error will be reported later when
you try to start the training).

After the "/", specifications for where to get the training and test
data are given.  Each such specification consists of two parts: the
source for the inputs, and the source for the targets.  The
specification "rdata@1:100" means that the training inputs come from
the file 'rdata', in lines 1 to 100, while the specification of
"rdata@101:200" for the test inputs indicates that they also come from
the file 'rdata', but in lines 101 to 200.  In the above command, the
sources for the targets are given as just ".", which means the target
items are on the same lines as the inputs, following the last input
item.  We could have said that the targets come from a completely
different file, however.  It is also possible to specify exactly where
on a line the inputs and targets are located (and hence to ignore some
items in the file).  For documentation on these and other features,
see numin.doc.

Though it is not done above, the 'data-spec' command also allows you
to specify transformations to be applied to the inputs or targets
before they are used.  This is useful, for example, if you wish to use
inputs that have been "standardized" to have mean zero and variance
one, based on the training data.  See data-spec.doc for the details.
In this example, the data already has approximately mean zero and
variance one, so the priors used are sensible without normalization.

In the training runs reported in the thesis, I used a short "initial
phase" to get things started, followed by a long "sampling phase" to
bring the simulation to equilibrium and then produce a sample of
networks from the posterior for use in prediction.  I still use the
same general procedure, but with some changes to how the initial phase
is done.

It seems desirable to start the simulation in a state where the
hyperparameters take on moderate values, and leave them fixed for a
few iterations so that the network parameters will also take on
moderate values.  This can be accomplished using the following
commands:

    > net-gen rlog.net fix 0.5
    > mc-spec rlog.net repeat 10 sample-noise heatbath hybrid 100:10 0.2
    > net-mc rlog.net 1

The 'net-gen' command stores a network in the log file with index
zero, in which the hyperparameters have values of 0.5, and the network
parameters are zero.  This is the initial state of the simulation run.
The following 'mc-spec' command specifies the Markov chain operations
to be performed in the initial phase.  Here, each iteration consists
of ten repetitions of the following steps:  Gibbs sampling for the
noise level, a heatbath replacement of the momentum variables, and a
hybrid Monte Carlo update with a trajectory 100 leapfrog steps long,
using a window of 10, and a stepsize adjustment factor of 0.2.  Note
that the hyperparameters are not updated, and hence will remain fixed
at values of 0.5.  Finally, a single such iteration is done by calling
'net-mc' with an iteration limit of 1.

The stepsize adjustment factor of 0.2 used above is typical of what is
needed, but will not be appropriate in all circumstances.  After the
'net-mc' command has finished, the number of the 10 hybrid Monte Carlo
updates that were rejected can be determined using the command
'net-plt t r rlog.net', which will write the iteration number (of 1)
and the rejection rate on standard output.  If the rejection rate is
high (say, over 0.3), a new run should be done using a smaller
stepsize adjustment factor.  In the initial phase, one would generally
start by guessing a value for the stepsize adjustment factor that is
on the low side, since there is no point in optimizing this choice.

At this point, we hope to have a network stored in the log file (with
index 1) that has values for both the parameters and hyperparameters
that are of moderate magnitude, and which have adapted at least
somewhat to the training data.  We can now start serious sampling with
the following commands:

    > mc-spec rlog.net sample-sigmas heatbath hybrid 1000:10 0.4
    > net-mc rlog.net 400

The 'mc-spec' command appends a new set of Markov chain operations to
the log file, which will override the previous set.  These operations
are Gibbs sampling for both the hyperparameters and the noise level
(the "sigmas"), a heatbath update for the momentum variables, and a
hybrid Monte Carlo update with a trajectory 1000 leapfrog steps long,
a window of 10, and a stepsize adjustment factor of 0.4.  A long
trajectory length is typically desirable for the sampling phase.  As
in the initial phase, the stepsize adjustment factor of 0.4 used is
typical, but not universally applicable.  It may pay at this stage to
experiment in order to find out how large this factor can be while
keeping the rejection rate low.  The use of a "window" of around 10
states costs little and is often beneficial.

The 399 iterations of the sampling phase started with the command
'net-mc rlog.net 400' take 160 seconds to complete on the the system
used (see Ex-system.doc).  If you put the command in the background
(or add a '&' to the end of the 'net-mc' command), you will be able to
monitor progress while you wait.  For example, you can look at the
last network saved in the log file (or any earlier one) using
'net-display'.  After a few seconds, you might see the following:

    > net-display rlog.net

    Network in file "rlog.net" with index 15
    
    Input to Hidden Layer 0 Weights [1]
    
     1.38 1.38: -0.85  +1.51  -0.39  -0.08  -2.74  -0.92  +0.87  -0.46
    
    Hidden Layer 0 Biases [2]
    
          2.49: +1.48  -1.93  -4.53  +2.42  -0.39  +2.29  -3.24  +2.46
    
    Hidden Layer 0 to Output Weights [3]
    
     1.54 1.54: -2.73
    
          1.54: -2.32
    
          1.54: +0.70
    
          1.54: +1.88
    
          1.54: -0.71
    
          1.54: -0.31
    
          1.54: +0.72
    
          1.54: +1.50
    
    Output Biases [4]
    
        100.00: -0.21
    
    Noise levels
    
       0.09 -  0.09

This display of network parameters and hyperparameters is divided into
sections for different parameter groups.  Within each section, the
numbers before the colons are hyperparameters, those after are
parameters (weight and biases).  There are more hyperparameters shown
than were mentioned earlier, but for this network architecture, the
extra hyperparameters are either fixed in value (the 100 for output
biases), or tied to the value of a higher-level hyperparameter, so
they are effectively not present.

The parameter groups in the 'net-display' output are identified by
numbers in square brackets.  These can be used with the 'h', 'w', 
and 'W' quantities of 'net-plt'.  For example, to see how the
hyperparameter controlling the hidden-to-output weights has changed
during the simulation (so far), one can use the command

    > net-plt t h3 rlog.net | plot

where 'plot' is some suitable plot program.  (One can also just invoke
net-plt and look at the numbers printed on standard output.)  Here
'h3' refers to the top-level hyperparameter for group 3, which is seen
in the output of 'net-display' above to be the hidden-to-output group.
Here's a command that shows how the individual weights in this group
change during the run:

    > net-plt t w3@ rlog.net | plot

In this case, the "plot" program must be one (such as xgraph) that is
capable of displaying more than one superimposed graph, with the data
for each graph being separated by a blank line.  Some plot programs
may prefer the data to come with multiple values per line, which is
the format produced by the 'net-tbl' command:

    > net-tbl tw3@ rlog.net | plot

Note that there is no space between the "t" quantity and the others in
this command.

By looking at plots of the hyperparameters and quantities such as the
squared error on the training set ('b'), one can get an idea of when
the simulation has reached equilibrium.  Networks from that point on
can then be used to make predictions for test case using the
'net-pred' program.  Often, it will not be completely clear that
equilibrium has been reached until the simulation has been allowed to
proceed for quite a long time, but predictions based on shorter runs
may nevertheless be quite good.

For this problem, let's assume that we have decided to discard the
first 100 iterations as perhaps not coming from the equilibrium
distribution.  The following command will use the networks from the
remaining 300 iterations to produce predictions for all test cases, and
report the average squared error:

    > net-pred itn rlog.net 101: 

    Number of iterations used: 300

    Case  Inputs Targets   Means Error^2

       1    0.92    1.49    1.57  0.0059
       2    0.71    1.83    1.78  0.0017
       3    0.20    1.72    1.68  0.0013
 
            ( middle lines omitted )

      98   -0.69    0.35    0.35  0.0000
      99   -1.33    0.19    0.37  0.0303
     100   -0.09    1.31    1.24  0.0061

    Average squared error guessing mean:   0.00941+-0.00123

The options "itn" specified ask for a listing of the inputs ("i") and
targets ("t") for each case, along with the mean ("n") output for that
case of the 80 networks used for prediction.  The squared error when
using this mean to predict the target is shown for each case, and the
average squared error for the test cases is shown at the bottom, along
with its standard error with respect to the random selection of test
cases.  Considering that the average squared error with optimal
prediction is 0.01 (due to the noise of standard deviation 0.1 added
when generating the data), the network model has done quite well, as
one would hope it would on an easy problem such as this.

It is also possible to get predictions for cases that are not in the
test set that was specified with 'data-spec'.  For example:

    > net-pred nb rlog.net 11: / "%echo 2.3"
      +1.36798018e+00

Here, the options "nb" ask for only the predictive mean, with "bare"
output (no headings, also higher precision, in exponential format).
The argument at the end says that the inputs for test cases (here,
just one case) should be taken from the output of the Unix command
"echo 2.3", which just outputs the number 2.3.

The 'net-pred' program can also find the median and the 10% and 90%
quantiles of the predictive distribution.  The program limits the
number of iterations that can be used when finding medians and
quantiles, so the command below uses "%5" to look only at the 60
iterations above 1100 with numbers that are multiples of five:

    > net-pred itdq rlog.net 101:%5

    Number of iterations used: 60
    
    Case  Inputs Targets Medians |Error| 10% Qnt 90% Qnt

       1    0.92    1.49    1.57  0.0791    1.45    1.68
       2    0.71    1.83    1.79  0.0386    1.67    1.90
       3    0.20    1.72    1.68  0.0338    1.57    1.80
       4    0.19    1.76    1.66  0.0983    1.55    1.78
       5    1.18    1.18    1.22  0.0437    1.11    1.34
       6   -2.10    0.05    0.06  0.0151   -0.08    0.20
       7   -1.34    0.30    0.37  0.0615    0.24    0.49
       8   -1.62    0.48    0.40  0.0766    0.27    0.53
       9   -2.29   -0.41   -0.25  0.1599   -0.46   -0.06
      10   -0.23    0.89    0.97  0.0782    0.85    1.09
    
                        (middle lines omitted)

      91   -0.16    1.21    1.10  0.1079    0.98    1.22
      92    0.79    1.70    1.72  0.0185    1.60    1.83
      93   -1.99    0.19    0.19  0.0027    0.05    0.32
      94    0.18    1.71    1.65  0.0613    1.53    1.77
      95    1.56    0.84    0.83  0.0060    0.71    0.95
      96   -0.32    0.80    0.82  0.0153    0.70    0.94
      97   -0.12    1.23    1.18  0.0524    1.06    1.29
      98   -0.69    0.35    0.35  0.0025    0.23    0.46
      99   -1.33    0.19    0.36  0.1724    0.24    0.49
     100   -0.09    1.31    1.24  0.0784    1.12    1.35
    
    Average abs. error guessing median:    0.07807+-0.00594

We see here that all but one of the actual targets for the twenty test
cases shown lie between the 10% and 90% quantiles.  When the median is
used as the "best guess", performance is judged by the average
absolute error, not squared error, since this is the error measure
that is minimized by the true median.


A Gaussian process model for the regression problem.

We can also model this data using a Gaussian process.  Such a model is
similar to a network model with an infinite number of hidden units.
The weights in this hypothetical infinite network are not represented
explicitly (fortunately, since this would require an infinite amount
of memory).  Only the hyperparameters are explicitly represented.

A Gaussian process model is specified using the gp-spec command, which
is analogous to the net-spec command.  For the simple regression
model, the following is one appropriate specification:

    > gp-spec rlog.gp 1 1 100 / 0.05:0.5 0.05:0.5

Here, "rlog.gp" is the name of the new log file that will hold the
results of the Gaussian process run.  The first two arguments
following the log file are the numbers of inputs and outputs,
respectively, both "1" for this problem.

The (optional) argument of "100" that follows is the prior for the
constant part of the covariance function used.  This corresponds to
the prior for the output unit bias in a network model.  A
specification for a linear part of the covariance could follow (but
doesn't here); it would correspond to a prior for direct input-output
connections in a network.  For reasons of computational accuracy, it
is best not to use too vague a prior for the constant part of the
covariance, even though that would not usually be a problem from a
statistical point of view.

The remaining arguments (after the "/") give the priors for the
hyperparameters used in an exponential term of the covariance
function.  These priors correspond to those for the hidden-output and
input-hidden weights in a network model.  (There is no counterpart
here to the prior for the hidden unit biases in a network model.)  The
first prior is for the scale of this term, which controls the
magnitude of the non-linear variation in the function.  The second
prior is for the relevance of the input, which controls the amount by
which the input has to change to produce a change in the non-linear
component of the function that is comparable to the overall scale over
which this component varies.  The prior specifications are in the same
form as is used for network specifications (see prior.doc).  The
specifications of "0.05:0.5" used here are vague, allowing these
hyperparameters to take on values over a wide range.

The specification can be viewed by invoking 'gp-spec' with just the
name of the log file:

    > gp-spec rlog.gp
    
    Number of inputs:    1
    Number of outputs:   1

    Constant part of covariance:  100.000

    Exponential parts of covariance:

       Scale           Relevance            Power

       0.050:0.50      0.050:0.50           2.000

Once the Gaussian process model for functions has been specified, we
can specify how the function values are used to model the targets in
the dataset using 'model-spec', in exactly the same was as for a
network model:

    > model-spec rlog.gp real 0.05:0.5

We also say where the training and (optionally) the test data comes
from using 'data-spec':

    > data-spec rlog.gp 1 1 / rdata@1:100 . rdata@101:200 .

The model and data specifications can be viewed by invoking these
programs with just the name of a log file.

We are now ready to sample from the posterior distribution of the
hyperparameters for the Gaussian process model.  To start, we can fix
the hyperparameters at reasonable initial values, using 'gp-gen':

    > gp-gen rlog.gp fix 0.5 0.1

This fixes the scale hyperparameters to 0.5 and the relevance
hyperparameters to 0.1 (linear hyperparameters, if present, would be
fixed to the product of these).  By default, the hyperparameters are
set to the "width" value from their prior specification.  Because the
priors are often vague (as here), this may not be a very reasonable
starting point.

We now specify the Markov chain operations to be used in sampling.
There are a great many possibilities for these operations.  Here is
one reasonable method:

    > mc-spec rlog.gp heatbath hybrid 20:4 0.5

This uses hybrid Monte Carlo, with trajectories 20 leapfrog steps
long, with a window of 4 states.  The stepsize adjustment factor used
is 0.5.  If the rejection rate turns out to be too high (as can be
checked using the 'gp-plt t r rlog.gp' command), the stepsize should
be adjusted downward.

To perform these sampling operations 100 times, we use the following
command:

    > gp-mc rlog.gp 100

We can let this run in the background (eg, by adding '&' to the end of
the command), and use 'gp-plt' or 'gp-display' to monitor progress.
The quantities that can be plotted with 'gp-plt' are similar to those
that can be plotted using 'net-plt', except that quantities relating
to test cases have been omitted, since they would often take a long
time to compute (the 'E' and 'H' quantities, defined in the "mc"
module, may also take a long time).  See gp-quantities.doc for
details.

Once the gp-mc run has completed, which takes 13 seconds on the system
used (see Ex-system.doc), iterations from the latter part of the run
can be used to make predictions for test cases.  This is done using
'gp-pred', which operates much like 'net-pred'.  The following command
makes predictions for the test cases based on the last 80 of the 100
iterations, and reports the average squared error:

    > gp-pred na rlog.gp 21:

    Number of iterations used: 80

    Number of test cases: 100

    Average squared error guessing mean:   0.00999+-0.00139

This takes less than a second on the sytem used (see Ex-system.doc).
Predictions will take longer when the number of training cases is
larger, or if the median or log probability are to be found (options
"d" or "p" of 'gp-pred').  As can be seen, the performance of the
Gaussian process model is quite similar to that of the neural network
model for this problem.  (The difference in average performance seen
is probably not statistically significant.)

The predictions for test cases made above are found directly from the
covariances between the targets in the training cases and the unknown
target in a test case.  The values of the regression function for the
training cases are never explicitly found.  Consequently, it is not
possible to plot quantities such as the squared error on training
cases over the course of the run.  To plot such quantities, you will
have to ask for the function values for training cases to be generated
in each iteration.  This takes a significant amount of time, and can
potentially cause numerical problems, which is why gp-plt won't just
do it as needed.

If you want to be able to plot the squared error on training cases (or
similar quantities such as case-by-case likelihoods), you will need to
change the 'mc-spec' command to the following:

    > mc-spec rlog.gp2 discard-values heatbath hybrid 20:4 0.5 sample-values

The "sample-values" operation at the end generates function values for
all the training cases, which will be stored in the log file.  These
values can later be used to compute the squared error for training
cases, which can be plotted with a command such as

    > gp-plt t b rlog.gp2 | plot

The "discard-values" operation throws away the function values (if
present) before the operations for updating hyperparameters.  Throwing
away information may seem wasteful, but it actually improves
convergence in this context.

Unfortunately, if you make only this change, you will probably get the
following error message when you try to run 'gp-mc':

  Couldn't find Cholesky decomposition of posterior covariance in sample-values!

This message is produced when the round-off error in the matrix
computations used by "sample-values" is enough to turn the results
into nonsense.  The problem is due to the poor "conditioning" of the
covariance matrix.  Roughly speaking, the covariances between
neighbouring training cases are so high that knowing all but one
function value is enough to determine the remaining function value to
a precision comparable to the level of round-off error.

To fix this, the conditioning of the covariance matrix must be improved.
Changing the 'gp-spec' command as follows is sufficient on our machine:

    > gp-spec rlog.gp2 1 1 10 - 0.01 / 0.05:0.5 0.05:0.5

There are two changes here from the 'gp-spec' command used before.
First, the constant part of the covariance has been reduced from 100
to 10, which makes little difference when the data is centred at about
zero, as it is for this problem.  Since arithmetic is done in floating
point, this increases the effective precision of the covariances.
Second, the covariance now includes a "jitter" part of 0.01 (the "-"
preceding this indicates that there is still no linear part).  Jitter
is much like noise, in that it varies independently from one case to
another, but it is considered part of the function value, which noise
is not.  The jitter makes all the function values less predictable,
reducing the problem of poor conditioning.  Jitter plays a more
crucial role for binary and class models.


A PROBLEM WITH A BINARY RESPONSE

In this example, each case consists of two real-valued inputs, x1 and
x2, and a binary target.  Data was generated by drawing the inputs for
a case independently from standard Gaussian distributions.  The target
was then set to "1" with the following probability:

    exp ( - ((x1-0.4)^2 + (x2+0.3)^2) ^ 2 )

ie, the negative exponential of the fourth power of the distance of
(x1,x2) from (0.5,-0.3).  I generated 500 cases, and used the first
300 for training and the remaining 200 for testing.


A neural network model for the binary response problem.

We will try modeling this data using a network with one layer of 15
hidden units and a single output unit.  For a binary target, a
Gaussian data model would be inappropriate; instead, we can use a
logistic regression model, in which the probability of the target
being "1" is obtained by passing the value of the output unit through
the logistic function, f(x)=1/(1+exp(-x)).

The network, model, and data specification commands needed are quite
similar to those used in the regression problem (see Ex-netgp-r.doc):

    > net-spec blog.net 2 15 1 / - 0.05:0.5 0.05:0.5 - x0.05:0.5 - 100 
    > model-spec blog.net binary
    > data-spec blog.net 2 1 2 / bdata@1:300 . bdata@301:500 .
    Number of training cases: 300
    Number of test cases: 200

The data model used is "binary", with no need for a noise level prior.

The 'data-spec' command also says that there are two inputs, and one
target.  It also has a third argument of "2" just before the "/",
which indicates that the target must be an integer with two possible
values (which are "0" and "1").

The initial phase commands that were used for the simple regression
problem turn out to be adequate for this problem as well:

    > net-gen blog.net fix 0.5
    > mc-spec blog.net repeat 10 sample-noise heatbath hybrid 100:10 0.2
    > net-mc blog.net 1

(The sample-noise operation above is actually unnecessary, since there
is no noise for this model.)  For the sampling phase, we could also
try using commands similar to those presented above, but we might as
well try something different (the mc-spec command needed here is long,
so it is continued by putting a "\" at the end of the first line):

    > mc-spec blog.net repeat 10 sample-sigmas heatbath 0.95 \
                                 hybrid 100:10 0.3 negate
    > net-mc blog.net 200

The above 'mc-spec' command specifies the variant of hybrid Monte
Carlo with "persistence" in which relatively short trajectories are
used, but random walks are suppressed by only partially replacing the
momentum in the 'heatbath' step.  Note that for this to work well, the
rejection rate must be quite small.  This alternative method has the
advantage that it allows for more frequent hyperparameter updates
(with 'sample-sigmas').

The 200 iterations requested above take about 7.5 minutes on the
system used (see Ex-system.doc).  During this time, one can monitor
the simulation, for instance with the command:

    > net-plt t h1h2h3 blog.net | plot

where again, 'plot' is some appropriate plotting program, which in
this case must be capable of plotting three superimposed graphs, for
the three hyperparameters h1, h2, and h3.  The values for these
hyperparameters exhibit quite a high degree of autocorrelation, which
is why it is advisable to allow the simulation to go for 200
iterations, in order to be more confident that the simulation has
explored all high-probability regions of the posterior distribution.

Once the run has finished, we can make predictions using 'net-pred',
based, say, on the networks from the final 3/4 of the run (which is a
generally reasonable portion).  For a problem such as this, where the
response is binary, we might be interested in guessing whether the
target is '0' or '1', with performance measured by how often we are
right.  We can get such predictions as follows:

    > net-pred itmp blog.net 51: 

    Number of iterations used: 150

    Case  Inputs        Targets  Log Prob  Guesses  Wrong?

       1   -1.56   0.90    0.00    -0.001      0       0
       2    0.09  -0.13    1.00    -0.057      1       0
       3   -0.79   0.85    0.00    -0.004      0       0

                     (some lines omitted )

      99    0.14   0.86    1.00    -2.594      0       1
     100    0.21   0.18    1.00    -0.103      1       0
     101   -1.32  -0.19    0.00    -0.006      0       0

                     (some lines omitted )

     198    1.49   0.70    0.00    -0.030      0       0
     199   -2.23  -0.28    0.00    -0.007      0       0
     200   -0.91  -0.03    0.00    -0.055      0       0

    Average log probability of targets:    -0.244+-0.034
    Fraction of guesses that were wrong:  0.0850+-0.0198

The "itmp" options ask for output listing the inputs, the targets, the
the guesses based on the mode of the predictive distribution, and the
log of the probability of the correct target in the predictive
distribution.  A summary is also printed showing the average log
probability of the correct target and the fraction of guesses that
were wrong, along with the standard errors for these as estimates of
performance on the population of cases.  The average log probability
is an overall indication of how well the model has done.  The
classification error rate might be more directly relevant for some
applications.


A Gaussian process model for the binary response problem.

This binary data can be modeled using a Gaussian process as well.  The
Gaussian process specifies a distribution over real-valued functions.
The function value for the inputs in a particular case can be passed
through the logistic function, f(x) = 1/(1+exp(-x)), to give the
probability that the target in that case will be '1' rather than '0'.

The specifications for a Gaussian process model analogous to the
network model used above are as follows:

    > gp-spec blog.gpl 2 1 1 - 0.1 / 0.05:0.5 0.05:0.5
    > model-spec blog.gpl binary
    > data-spec blog.gpl 2 1 2 / bdata@1:300 . bdata@301:500 .
    Number of training cases: 300
    Number of test cases: 200

The 'gp-spec' command used here does not quite correspond to the
'net-spec' command used above.  The following command would give a
closer correspondence:

    > gp-spec blog.gpl 2 1 100 / 0.05:0.5 0.05:0.5

The reason for modifying this, by reducing the constant part of the
covariance (from 100 to 1) and introducing a small (0.1) "jitter"
part, is to solve computational problems of poor conditioning and slow
convergence.  The "jitter" part lets the function value vary randomly
from case to case, as if a small amount of Gaussian noise were added.
This makes the function values less tightly tied to each other, easing
the computational difficulties (with the unmodified specification,
'gp-mc' would probably work only if the dataset was very small).
These changes have little effect on the statistical properties of the
model, at least for this problem.

Sampling might now be done using the following commands:

    > gp-gen blog.gpl fix 0.5 1
    > mc-spec blog.gpl repeat 4 scan-values 200 heatbath hybrid 8 0.3
    > gp-mc blog.gpl 50

These commands (and variations on them) are similar to those that you
might use for a regression problem, except that a "scan-values 200"
operation has been included.  This operation performs 200 Gibbs
sampling scans over the function values for each training case.  An
explicit representation of function values is essential for a binary
model, though not for a simple regression model, because the
relationship of function values to targets is not Gaussian.
Unfortunately, for the very same reason, the direct "sample-values"
operation is not available, so one must use Gibbs sampling or
Metropolis-Hastings updates (the met-values or mh-values operations).

The 50 sampling iterations take 5.9 minutes on the system used (see
Ex-system.doc).  While you wait, you can check the progress of the
hyperparameters using gp-display:

    > gp-display blog.gpl

    GAUSSIAN PROCESS IN FILE "blog.gpl" WITH INDEX 10
    
    HYPERPARAMETERS
    
    Constant part:
    
          1.000
    
    Jitter part:
    
            0.1
    
    Exponential parts:
    
          5.973
          0.620 :      0.620      0.620

Note that there are only two variable hyperparameters, since the
constant and jitter parts are fixed, and the relevance hyperparameters
for each input are tied to the higher-level relevance hyperparameter.
A time plot of two variable hyperparameters can be obtained as follows:

    > gp-plt t S1R1 blog.gpl | plot

Once sampling has finished, predictions for test cases can be made
using 'gp-pred'.  The following command prints only the average
classification performance:

    > gp-pred ma blog.gpl 21:%2

    Number of iterations used: 15

    Number of test cases: 200

    Fraction of guesses that were wrong:  0.0950+-0.0208

This takes 2.5 seconds on the system used (see Ex-system.doc).  This
is slower than prediction using a network model, since the Cholesky
decomposition of the covariance matrix must be found for each
iteration used (saving these would take up lots of disk space).  The
accuracy achieved is about the same as for the network model, which is
not too surprising, given that they both use a logistic function to
relate function values to target probabilities.

It is possible to define a Gaussian process model that will behave as
what is known is statistics as a "probit" model rather than a
"logistic" model.  This is done by simply setting the amount of jitter
to be large compared to the span over which the logistic function
varies from nearly 0 to nearly 1.  This can be done by changing the
'gp-spec' command to the following, in which the jitter part is 10
(the constant part is also changed to be of the same magnitude):

    > gp-spec blog.gpp 2 1 10 - 10 / 0.05:0.5 0.05:0.5

One can then proceed much as above (though it turns out that a larger
stepsize can be used).  The final performance is similar, but the
scale hyperparameter takes on much larger values.


A THREE-WAY CLASSIFICATION PROBLEM

I also created a synthetic data set for a three-way classification
problem.  Data items were generated by first drawing quantities x1,
x2, x3, and x4 independently from distributions uniform over (0,1).
The class of the item, represented by "0", "1", or "2", was then
selected as follows: if the two-dimensional Euclidean distance of
(x1,x2) from the point (0.4,0.5) was less than 0.35, the class was set
to "0"; otherwise, if 0.8*x1+1.8*x2 was less than 0.6, the class was
set to "1"; and if neither of these conditions held, the class was set
to "2".  Note that x3 and x4 have no effect on the class.  The class
selected by this procedure was the target value for the network; the
inputs available for use in predicting the class were not x1, x2, x3,
and x4 themselves, however, but rather these four values plus Gaussian
noise of standard deviation 0.1.  I generated 1000 cases in this way,
of which 400 were used for training and 600 for testing.


A neural network model for the three-way classification problem.

This example will illustrate the "softmax" model for target values in
a small set, and the Automatic Relevance Determination (ARD) prior for
input-to-hidden weights.  The network and model specifications used
were as follows:

    > net-spec clog.net 4 8 3 / - x0.2:0.5:0.5 0.05:0.5 - \
                                x0.05:0.5 - 0.05:0.5
    > model-spec clog.net class

This specifies a network with 4 input units, 8 hidden units, and 3
output units.  The output units have identity activation functions,
but their values are used in a "softmax" data model, in which the
probability for target i is exp(o_i) / SUM_j exp(o_j), where the o_j
are the values of the output units. 

The prior specified for input-to-hidden weights, "x0.2:0.5:0.5", has
two "alpha" values, indicating that there is both a high-level
hyperparameter controlling the overall magnitude of input-to-hidden
weights, and lower-level hyperparameters for each input unit, which
control the magnitudes of weights out of each input.  If some of the
inputs are irrelevant (as are the third and fourth inputs in this
problem), we hope that the corresponding hyperparameters will take on
small values, forcing the weights out of these inputs to be close to
zero, and thereby avoiding any damage to predictive performance that
could result from the inclusion of these irrelevant inputs. The prefix
of "x" causes the width of this prior to be automatically scaled
according to the number of inputs.  This is appropriate if the number
of highly relevant inputs is thought not to depend on the total number
of inputs.

We need to use the following data specification for this problem:

    > data-spec clog.net 4 1 3 / cdata@1:400 . cdata@401:1000 .
    Number of training cases: 400
    Number of test cases: 600

The arguments "4" and "1" are the numbers of input and target values.
The "3" before the "/" says that each target must be one of the
integers "0", "1", or "2".  This "3" must match the number of softmax
output units specified in the network architecture, or an error will
result when training is started.

The initial and sampling phases of the simulation can be done using
the same approach as was used above for the binary data set (but the
"sample-noise" operation doesn't actually do anything here):

    > net-gen clog.net fix 0.5
    > mc-spec clog.net repeat 10 sample-noise heatbath hybrid 100:10 0.2
    > net-mc clog.net 1
    > mc-spec clog.net repeat 10 sample-sigmas heatbath 0.95 \
                                 hybrid 100:10 0.3 negate
    > net-mc clog.net 200

This takes 8.7 minutes on the system used (see Ex-system.doc).

We can see the effect of the ARD model by looking at the values of
the low-level input-hidden hyperparameters over the course of the
simulation, with the command:

    > net-plt t h1@ clog.net | plot

The third and fourth hyperparameters are much smaller than the first
two, indicating that ARD has done its job.

Predictions for test cases based on the predictive mode can now be
done in the same way as for the binary response problem.  If we are
interested only in the estimated classification performance, we can
use the following command:

    > net-pred ma clog.net 51:

    Number of networks used: 150

    Number of test cases: 600

    Fraction of guesses that were wrong:  0.1400+-0.0142

Here, the "a" option is used to suppress everything except the summary.

If we are interested in the probabilities for each class, we can use
the "n" option, as follows:

    > net-pred tn clog.net 51:

    Number of iterations used: 150

    Case Targets   Means               Error^2

       1    2.00    0.19   0.00   0.81  0.0726
       2    2.00    0.23   0.01   0.76  0.1073
       3    2.00    0.12   0.00   0.87  0.0319
       4    0.00    0.82   0.04   0.13  0.0524
                     
                       . . .

     597    2.00    0.04   0.00   0.96  0.0027
     598    1.00    0.33   0.65   0.01  0.2346
     599    0.00    0.23   0.00   0.77  1.1964
     600    2.00    0.03   0.00   0.97  0.0016

    Average squared error guessing mean:   0.20556+-0.01623

The "Means" columns give the predictive probabilities for the three
classes for each case.  The "Error^2" column gives the squared error
found by summing the squared differences of these probabilities with
the indicator variables that are zero for the wrong classes and one
for the correct class.  


A Gaussian process model for the three-way classification problem.

Gaussian process models can also be used for multi-way classification
problems, in much the same way as for a binary response.  Here are
commands that implement a "probit" style model for the three-way
classification problem, using "persistent" hybrid Monte Carlo:

    > gp-spec clog.gpp 4 3 10 - 10 / 0.05:0.5 x0.2:0.5:1
    > model-spec clog.gpp class
    > data-spec clog.gpp 4 1 3 / cdata@1:400 . cdata@401:1000 .

    > gp-gen clog.gpp fix 0.5 1
    > mc-spec clog.gpp repeat 5 scan-values 100 heatbath 0.9 \
                                hybrid 1 0.3 negate
    > gp-mc clog.gpp 5
    > mc-spec clog.gpp repeat 5 scan-values 100 heatbath 0.98 \
                                hybrid 1 0.3 negate
    > gp-mc clog.gpp 100

For the first five iterations, the persistence is fairly small (0.9),
so that the high initial energy will be dissipated rapidly.  The
remaining iterations use a larger persistence (0.98) to suppress
random walks.  This run takes 19 minutes on the system used (see
Ex-system.doc).  The cubic scaling of the computations for the
Gaussian process models leads to their becoming slower relative to
neural network models as the number of training cases increases.

One can observe how the relevance hyperparameters change during the
run as follows, assuming that the "plot" program can display four
superimposed graphs:

    > gp-plt t R1@ clog.gpp | plot

Once the run is finished, predictions for test cases can be made
as illustrated below:

    > gp-pred itm clog.gpp 21:%5

    Number of iterations used: 16
    
    Case  Inputs                       Targets  Guesses  Wrong?
    
       1    0.29   0.90   0.74   0.33    2.00       2       0
       2    0.70   0.27   0.17   0.89    2.00       2       0
       3   -0.11   0.76   0.11  -0.02    2.00       2       0
       4    0.54   0.24   0.39   0.78    0.00       0       0

                      (middle lines omitted)

     597   -0.10   0.93   0.27   0.28    2.00       2       0
     598    0.14   0.19   0.08   0.70    1.00       1       0
     599    0.66   0.79   0.03   0.09    0.00       2       1
     600    0.76   0.90   0.73  -0.03    2.00       2       0
    
    Fraction of guesses that were wrong:  0.1350+-0.0140
    
This takes 27 seconds on the system used (see Ex-system.doc).  The "n"
option can be used to get the predictive probability for each class,
as illustrated above for net-pred.

A "logistic" style model can be obtained by decreasing the jitter,
using a 'gp-spec' command such as the following:

    > gp-spec clog.gpl 4 3 1 - 0.1 / 0.05:0.5 x0.2:0.5:1

A smaller stepsize is necessary with this model (0.15 rather than
0.3).  Performance is similar.


A REGRESSION PROBLEM WITH OUTLIERS

Finally, we will go back to the simple regression problem we started
with, but now some of the cases will be "outliers", for which the
noise is much greater than for normal cases.

In this synthetic data, the input variable, x, again had a standard
Gaussian distribution and the corresponding target value came from a
distribution with mean given by

         0.3 + 0.4*x + 0.5*sin(2.7*x) + 1.1/(1+x^2)

For most cases, the distribution about this mean was Gaussian with
standard deviation 0.1.  However, with probability 0.05, a case is an
"outlier", for which the standard deviation was 1.0 instead.

I generated 200 cases in total, stored in the file 'odata'.  The first
100 of these cases are meant for training, the second 100 for testing.
It is also possible to test on 'rdata', to see how well the function
learned predicts data that is never corrupted by high noise.


A neural network model for regression with outliers.

One way to model data with "outliers" is to let the noise level vary
from one case to another.  If the noise for the outlier cases is set
to be higher, they will end up having less influence on the function
learned, as is desirable.  The software allows the noise variance for
a case to vary according to an inverse gamma distribution.  This is
effectively the same as letting the noise have a t-distribution rather
than a Gaussian distribution.

The commands used to do this are as follows:

    > net-spec olog.net 1 8 1 / - 0.05:0.5 0.05:0.5 - x0.05:0.5 - 100 
    > model-spec olog.net real 0.05:0.5::4
    > data-spec olog.net 1 1 / odata@1:100 . odata@101:200 .

    > net-gen olog.net fix 0.5
    > mc-spec olog.net repeat 10 sample-noise heatbath hybrid 100:10 0.2
    > net-mc olog.net 1

    > mc-spec olog.net sample-sigmas heatbath hybrid 1000:10 0.4
    > net-mc olog.net 400

The crucial difference is in the 'model-spec' command, where the noise
prior of 0.05:0.5::4 specifies that the per-case noise precision
(inverse variance) follows a gamma distribution with shape parameter
of 4.  When this is integrated over, a t-distribution with 4 degrees
of freedom results.  This t-distribution is by no means an exact model
of the way the noise was actually generated, but its fairly heavy
tails are enough to prevent the model from paying undue attention to
the outliers.

The above commands take 165 seconds on the system used (see
Ex-system.doc).  The resulting model can be tested on data from the
same source using net-pred:

    > net-pred na olog.net 101:

    Number of iterations used: 300

    Number of test cases: 100

    Average squared error guessing mean:   0.01917+-0.01057

One can also see how well the model does on the uncorrupted data that
was used originally:

    > net-pred na olog.net 101: / rdata@101:200 .

    Number of iterations used: 300

    Number of test cases: 100

    Average squared error guessing mean:   0.00927+-0.00124

This is similar to the results obtained earlier with the model trained
on uncorrupted data (slightly better, in fact, but that's just luck).

In contrast, the results are substantially worse when the data with
outliers is used to train a standard model where the noise is
Gaussian, with the same variance for each case.


A Gaussian process model for regression with outliers.

Gaussian process regression can also use a t-distribution for the
noise, specified using 'model-spec', as above.  Implementation of this
model requires sampling for function values in training cases, so a
small amount of "jitter" will almost always have to be included in the
covariance function.  A "sample-variances" operation must also be
specified in 'mc-spec', to allow the case-by-case noise variances to
be sampled.  The following commands illustrate how this is done:

    > gp-spec olog.gpt 1 1 1 - 0.001 / 0.05:0.5 0.05:0.5
    > model-spec olog.gpt real 0.05:0.5::4
    > data-spec olog.gpt 1 1 / odata@1:100 . odata@101:200 .

    > gp-gen olog.gpt fix 0.5 0.1
    > mc-spec olog.gpt sample-variances heatbath hybrid 20:4 0.5
    > gp-mc olog.gpt 200

This takes 30 seconds on the system used (see Ex-system.doc).  The
progress of the run can be monitored by examining the case-by-case
noise standard deviations in (say) the first 8 training cases, as
follows:

    > gp-plt t v@0:7 olog.gpt | plot

Once the run has converged, a few of these standard deviations (for
cases that are outliers) should be much bigger than the others.  The
noise standard deviations can also be examined using the "-n" option
of 'gp-display'.

Predictions can be made using 'gp-pred':

    > gp-pred na olog.gpt 101:%5

    Number of iterations used: 20

    Number of test cases: 100

    Average squared error guessing mean:   0.01939+-0.01134

This performance is very similar to that of the network model.



EXAMPLES OF BAYESIAN MIXTURE AND DIRICHELT DIFFUSION TREE MODELS.

Mixture models can be used to model complex distributions of "target"
values, without any dependence on input values.  The mixture
components that are found by the model might also be interpretable as
representing underlying "latent classes" in the data.  Examples are
given here of how this can be done for binary and for real-valued
data.

Dirchlet diffusion trees can also be used to model such data, and are
also a way of performing hierarchical clustering.  These models are
demonstrated on the same examples as are used for the mixture models,
and also on an example that illustrates the use of two diffusion trees
to produce an additive model.

The data and command files for these examples are in the "ex-mixdft"
directory.  The real-valued data was used as one example in my paper
on "Density modeling and clustering using Dirichlet diffusion trees".
This directory also contains the data and command files used for the
example in my tech report on "Markov chain sampling methods for
Dirichlet process mixture models".


A PROBABILITY ESTIMATION PROBLEM WITH BINARY DATA

As a first illustration of the mixture model and Dirichlet diffusion
tree software, I generated a dataset in which each case was composed
of ten binary attributes.  The distribution of these binary vectors
was a mixture of four component distributions, in each of which the
ten attributes were independent.  The four components each had
probability 0.25 of being chosen to generate a case.  The
probabilities for each component for each binary attributes were as
shown below:

          1    2    3    4    5    6    7    8    9   10

     1   0.1  0.2  0.2  0.2  0.2  0.8  0.8  0.8  0.8  0.7
     2   0.1  0.8  0.8  0.8  0.8  0.2  0.2  0.2  0.2  0.7
     3   0.9  0.2  0.2  0.8  0.8  0.2  0.2  0.8  0.8  0.7
     4   0.9  0.8  0.8  0.2  0.2  0.8  0.8  0.2  0.2  0.7

Each row gives the probabilities of each of the attributes being '1'
for one component of the mixture.  The columns are for the ten binary
attributes in each case.  The vectors generated in this way can be
seen as coming from one of four "patterns": 0000011111, 0111100001,
1001100111, and 1110011001, but with each bit of the chosen pattern
having a small probability of being switched (ranging from 0.1 to 0.3)
in any particular case.

I generated 1000 cases from this distribution, which are stored in the
file 'bdata'.  The first 500 are used for training, the rest for
testing.


A finite mixture model for the binary data.

We will first see what happens when we model this data as a mixture of
four components, which is the true number of components for this
problem.  Each component of the mixture will give each target
attribute a certain probability of being '1' rather than '0'.  These
probabilities are determined from the "offset" parameters for each
target, by means of the "logistic" function:

   Pr(target=1)  =  1 / (1 + exp(-offset))

The offset parameters for each attribute for each component are given
Gaussian prior distributions, with means and standard deviations that
are hyperparameters.  These hyperparameters could be fixed, but here
we will make them variable, separately for each target attribute, but
with each of them linked to a top-level hyperparameter, common to all
targets.

We set up this mixture model with the 'mix-spec' command, as follows:

    > mix-spec blog.4 0 10 4 / x1 0.05:0.5:0.2 10

Here, "blog.4" is the name of the log file used for this run, which is
created by the 'mix-spec' command.  The arguments of 'mix-spec' that
follow the name of the log file are the number of input attributes
(always 0 for mixture models at present), the number of target
attributes (10 for this problem), and the number of mixture components
(set to the true value of 4 in the command above).  The specifications
for priors are given following these arguments, after a "/" separator.

The first prior specification gives the concentration parameter of the
Dirichlet distribution for the mixing proportions for the components.
If this specification starts with "x", this value is automatically
divided by the number of components, which is the scaling required for
the model to reach a sensible limit as the number of components goes
to infinity.  The specification of "x1" above mildly favours unequal
mixing proportions (recall that the true proportions are equal).

The second argument after the "/" specifies the prior for the standard
deviations of the "offsets" for components (which determine the
probabilities for the binary target attributes).  In the hierarchical
scheme specified here (described in general in prior.doc), there is a
top-level standard deviation hyperparameter, given a prior in which
the corresponding "precision" (standard deviation to the power -2) has
a gamma distribution with mean 0.05 and shape parameter 0.5.  There is
a lower-level standard deviation hyperparameter for each target; for
each of these, the corresponding precision has a gamma distribution
with mean given by the higher-level precision, and shape parameter of
0.2.  Both these priors are rather vague (but the shape parameter of
0.2 is vaguer than 0.5), so these hyperparameters can adapt to the
structure of the data.

The last argument of 'mix-spec' is the standard deviation for the
means of the offsets for each of the targets, here set to 10.
Currently, this standard deviation for the mean offset is the same for
all targets, and is fixed in the 'mix-spec' command (it cannot be a
variable hyperparameter).

We can look at these specifications by calling 'mix-spec' with just
the log file as an argument:

    > mix-spec blog.4

    Number of inputs:      0
    Number of targets:     10

    Number of components:  4

    Dirichlet concentration parameter: x1.000
    Prior for SD hyperparameters:       0.050:0.50:0.20
    Prior for mean component offsets:   10.000

After the 'mix-spec' command, we need to specify that the targets are
binary using the 'model-spec' command, as follows:

    > model-spec blog.4 binary

We can then specify where the data comes from using 'data-spec':

    > data-spec blog.4 0 10 2 / bdata@1:500 . bdata@501:1000 .

The number of inputs is here specified to be 0 (as it must be at
present for mixture models), and the number of targets is specified to
be 10.  These must match the values given to 'mix-spec'.  We also
specify that the targets must be the integers 0 or 1 putting in a
following argument of 2 (meaning that there are 2 possible values,
which start at 0).  After a slash, we say where the inputs and targets
come from.  Note that we have to say where the inputs come from even
though there are 0 of them, but fortunately, we can then say that the
targets come from the same place by just using the "." argument.  In
the specification above, the data comes from the first 500 lines of
the file 'bdata', with one case per line.  The remaining 500 lines are
specified to be used for testing.  See data-spec.doc for more details.

Finally, we need to specify how Markov chain sampling is to be done
for this model.  At present, none of the standard Markov chain methods
are allowed for mixture models, only the specialized procedures
documented in mix-mc.doc.  Each of these procedures updates one of the
three parts of the state - the values of the hyperparameters, the
values of the parameters for the various mixture components, and the
values of the indicator variables saying which mixture component is
currently associated with each training case.  The values in each of
these parts of the state can be updated by Gibbs sampling, using the
corresponding procedure.  The following call of 'mc-spec' sets this
up:

    > mc-spec blog.4 repeat 20 gibbs-indicators gibbs-params gibbs-hypers

Here, the three Gibbs sampling operations are repeated 20 times each
iteration, just to cut down on the number of states saved in the log
file.

We can now run the Markov chain simulation for 100 iterations with the
following command:

    > mix-mc blog.4 100

The simulation starts with a state in which all the training cases are
associated with the same component, whose parameters are set to their
means, as specified by hyperparameter values that are also set to
their prior means.  The 'mix-gen' program could be used to initialize
things differently (see mix-gen.doc).

The above run takes 29 seconds on the system used (see Ex-system.doc).
It can be run in the background, in which case progress can be
monitored with the 'mix-display' and 'mix-plt' programs.  For example,
after a while, you might see the following:

    > mix-display blog.4

    MIXTURE MODEL IN FILE "blog.4" WITH INDEX 50
    
    HYPERPARAMETERS
    
    Standard deviations for component offsets:
    
        0.326:     1.407    1.159    1.213    3.331    1.417
                   1.557    3.433    2.203    4.990    0.192
    
    Means for component offsets:
    
                  -0.370   -0.126   -0.538   +0.521   -0.620
                  -1.642   +1.510   -1.206   -1.502   +0.941
    
    
    PARAMETERS AND FREQUENCIES FOR COMPONENTS OF THE MIXTURE
    
       1: 0.286   -1.799   +0.931   +1.753   +1.481   +0.853
                  -1.503   -1.433   -0.942   -1.245   +1.165
    
       2: 0.252   +1.905   +1.054   +1.749   -2.588   -1.594
                  +1.062   +1.625   -1.532   -1.227   +1.252
    
       3: 0.250   -2.109   -1.505   -2.220   -0.961   -1.402
                  +2.265   +1.635   +1.463   +2.015   +1.082
    
       4: 0.212   +1.743   -1.050   -1.470   +1.502   +1.553
                  -1.593   -1.376   +1.569   +1.025   +0.864

This displays the state at the last iteration computed so far (here
iteration 50).  The hyperparameter values are shown first, with
top-level hyperparameters on the left, before the colon.  The
lower-level hyperparameters follow, ordered by the target attribute
that they pertain to.  Values for the component parameters follow,
sorted by the fraction of training cases that they are currently
associated with.  These fractions are the first numbers after 1:, 2:,
etc.; note that the actual mixing probabilities are not explicitly
represented, but are instead always integrated over.  Any components
that are not associated with any training case are omitted from the
output, and are not explicitly represented in the state.  The other
numbers shown for each component are the "offset" parameters for each
target attribute.

In this example, the simulation appears to have learned the essence of
the distribution by the iteration shown above.  Recall that a positive
offset corresponds to the probability of a 1 being greater than 1/2, a
negative offset to the probability of a 1 being less than 1/2.  The
four components shown above can thus be seen to correspond to the four
patterns used to generate the cases, as described earlier.  Note that
the last of the offset standard deviation hyperparameters (for the
last target attribute) is quite small.  This indicates that the model
has "learned" that the probabilities for the last target are the same
for all components, and hence can be modeled most efficiently at the
hyperparameter level, by the mean for that offset, rather than
separately for each component.

The indicators of which components are associated with each training
case can also be examined with 'mix-display', and of course iterations
other than the last can be viewed.  See mix-display.doc for details.

One can also look at the progress of the simulation using 'mix-plt'.
For example, the following will produce a time-plot of the cumulative
proportions of the training cases associated with the four components
(as sorted by decreasing frequency):

    > mix-plt t C1C2C3C4 blog.4 | plot

Here, 'plot' is some suitable plotting program.  One can also just let
the output of 'mix-plt' go to standard output, and then examine the
numbers manually.  Other quantities can also be plotted, as described
in mix-quantities.doc.

As well as examining quantities with 'mix-display' and 'mix-plt', one
can also produce a sample of cases from the predictive distribution
using 'mix-cases'.  Predictive probabilities for test cases can be
found using 'mix-pred'.  The following command gives the average log
probability for all the test cases, using the last 80 iterations:

    > mix-pred pa blog.4 21:

    Number of iterations used: 80

    Number of test cases: 500

    Average log probability of targets:    -6.097+-0.069

For comparison, the average log probability for these test cases
using the true mixture distribution is -6.034.


A countably infinite mixture model for the binary data.

Even though the true distribution for this example is a mixture of
four components, good results can nevertheless be obtained using a
mixture with a countably infinite number of components.  The prior for
mixture proportions used with such a model is designed so that a few
of the infinite number of components have substantial probability, so
the model does not result in an "overfitted" solution, in which every
training case is "explained" as coming from a different component.

We specify a countably infinite mixture model by simply omitting the
argument to 'mix-spec' that gives the number of components.  For this
example, we change the 'mix-spec' command used above to the following:

    > mix-spec blog.inf 0 10 / x1 0.05:0.5:0.2 10

The Dirichlet prior specification for mixing proportions of "x1" is
the same as for the mixture model with four components.  The "x"
specifies scaling downward with the number of components, which
produces a sensible limit as the number of components goes to
infinity, as here.  The "x" is therefore required for infinite
mixtures.

The other arguments of 'mix-spec' are as described for the finite
mixture model.  The 'model-spec' and 'data-spec' commands used are
also the same:

    > model-spec blog.inf binary
    > data-spec blog.inf 0 10 2 / bdata@1:500 . bdata@501:1000 .

We must change the 'mc-spec' command, however, since it is impossible
to do Gibbs sampling for the component indicators associated with
training cases - since their number is infinite, we can't compute all
the required conditional probabilities.  However, we can instead use a
specialized Metropolis-Hastings update, in which a new component to go
with a training case is proposed with probability determined by the
frequencies with which components are associated with other training
cases.  The proposal is accepted or rejected based on the resulting
change in likelihood.  The process can then be repeated any desired
number of times, to produce an approximation to Gibbs sampling (the
"approximation" is only with respect to convergence speed, the answer
is exact, asymptotically).  With this change, we can use the following
'mc-spec' command for this model:

    > mc-spec blog.inf repeat 20 met-indicators 10 gibbs-params gibbs-hypers

This is the same as for the finite mixture model, except that 10
repetitions of the Metropolis-Hastings update for the indicators are
specified using 'met-indicators 10', in place of 'gibbs-indicators'.

As before, we can now run the simulation with a command such as:

    > mix-mc blog.inf 100

We can examine the states with 'mix-display'.  For example, once the
'mix-mc' command completes, which takes 63 seconds on the system used
(see Ex-system.doc), the state should be something like the following:

    > mix-display blog.inf
    
    MIXTURE MODEL IN FILE "blog.inf" WITH INDEX 100
    
    HYPERPARAMETERS
    
    Standard deviations for component offsets:
    
        0.359:     2.747    4.294    1.280    3.530    1.353
                   2.461    5.661    2.928    1.506    0.080
    
    Means for component offsets:
    
                  +0.023   +0.452   +0.792   +0.507   -0.084
                  -0.634   -4.794   +4.560   -0.293   +1.124
    
    
    PARAMETERS AND FREQUENCIES FOR COMPONENTS OF THE MIXTURE
    
       1: 0.310   -1.565   +0.617   +1.467   +1.191   +0.468
                  -0.569   -1.192   -0.397   -0.749   +1.003
    
       2: 0.254   -1.374   -1.134   -2.009   -1.008   -1.825
                  +2.384   +2.377   +1.579   +2.553   +1.080
    
       3: 0.238   +2.949   +0.979   +2.419   -2.694   -1.331
                  +1.597   +1.590   -1.689   -1.190   +1.124
    
       4: 0.168   +1.565   -1.687   -1.958   +1.762   +1.633
                  -1.365   -6.917   +1.001   +1.180   +0.919
    
       5: 0.012   +1.780   -3.038   -0.664   +5.257   -3.499
                  -8.315   -5.443   +0.816   -0.774   +1.143
    
       6: 0.012   +1.892   -0.991   +3.387   +0.513   +1.287
                  -4.129   +1.283   +8.346   +1.452   +0.882
    
       7: 0.004   +5.850   +1.412   +0.295   -5.867   +0.701
                  -0.403   -9.392   +7.748   -2.211   +1.163
    
       8: 0.002   +1.028   -3.102   +2.383   -1.070   +1.691
                  +0.497   +0.062   +0.505   -0.762   +1.226
    
The output is similar to that seen for the mixture model with four
components, except that eight components are associated with at least
one training case at iteration 100, as shown above.  (The infinite
number of remaining components are not explicitly represented, and are
not displayed by 'mix-display'.)  Four of these components are
associated with very few training cases, however (as seen from the
fractions of the training set after the component number).  This is to
be expected when the true distribution can be expressed using only
four components.  The number of such low-frequency components will
vary from iteration to iteration, as will other aspects of the state,
in accordance with the variability in the posterior distribution.

Since there are exactly four components in the real distribution, one
would expect that the model with four components would perform better
than a model with an infinite number of components.  Any penalty is
quite small in this example, however, as can be seen by looking at the
predictive probabilities:

    > mix-pred pa blog.inf 21:

    Number of iterations used: 80

    Number of test cases: 500

    Average log probability of targets:    -6.105+-0.069

This is almost the same as the average log probability for the four
component model.

A number of other ways of sampling for the indicators for countably
infinite mixture models are also available.  Here are two:

    > mc-spec blog.inf2 repeat 20 \
                gibbs-ext-indicators 2 gibbs-params gibbs-hypers

    > mc-spec blog.inf3 repeat 20 \
                met1-indicators gibbs1-indicators gibbs-params gibbs-hypers

These methods may be more efficient than using the "met-indicators"
operation for some models.  See mix-mc.doc for descriptions of these
and other Markov chain operations for mixture models.


A Dirichlet diffusion tree model for the binary data.

Binary data can also be modeled using Dirichlet diffusion trees.  This
is not the simplest example of how Dirichlet diffusion trees can be
used, since the trees naturally produce real valued data.  To model
binary data, these real values are treated as latent values, which are
put through the logistic function to produce the probabilities for the
binary data to be "1".  The binary data example here does not have the
sort of hierarchical structure that would make use of a Dirichlet
diffusion tree model desirable.  For both these reasons, the following
example of how to model binary data with a Dirichlet diffusion tree
may not be the best introduction to such models - you might want to
read the real-valued example in Ex-mixdft-r.doc first.

Nevertheless, this example does demonstrate how binary data can be
modeled, and shows that even when there is no hierarchical structure
to the data, a Dirichlet diffusion tree model can do quite well.

We start by specifying a Dirichlet diffusion tree model, as follows:

    > dft-spec blog.dft 0 10 / 2 - 1

As for a mixture mdoel specification, this says that there are 0
"input" variables (as there must be at present), and 10 "target"
variables.  The argument of "2" is the standard deviation for the
diffusion process that produces the latent variables used to model the
binary variables (this could have been a prior specification rather
than a fixed value).  The last two arguments are the parameters of the
divergence function used to determine (stochastically) when the
diffusion paths for different cases diverge.  The general form of the
divergence function is

   a(t) = c0 + c1/(1-t) + c2/(1-t)^2

The parameters c0, c1, c2 are given at the end of the 'dft-spec'
command, with "-" being equivalent to zero.  Any zero parameters at
the end can just be omitted.  The specification above therefore
corresponds to the divergence function a(t) = 1/(1-t).  Any of c0, c1,
and c2 can be a prior specification, instead of a constant.  See
dft-spec.doc for details, and Ex-mixdft-r.doc for an example.

We next specify the data model, which is "binary", indicating binary
data modeled using the logistic function:

    > model-spec blog.dft binary

We go on to specify the source of the data, as for the mixture example
above:

    > data-spec blog.dft 0 10 2 / bdata@1:500 . bdata@501:1000 .

Finally, we need to specify how to do Markov chain sampling for the
posterior distribution of the trees and latent values that underly the
data.  

    > mc-spec blog.dft repeat 10 gibbs-latent slice-positions met-terminals

Since the hyperparameters are all fixed for this model, there is no
need for Markov chain operations to update them.  The operations above
will lead to the state of the Markov chain being only the latent
values and the tree structure, with divergence times, but without the
locations of non-terminal nodes (which will be integrated over).  The
'gibbs-latent' operation does a Gibbs sampling scan over the latent
values associated with the targets in training cases.  (Initially, the
latent values are taken to be +1 for targets of "1", and -1 for
targets of "0".)  The 'slice-positions' and 'met-terminals' operations
both update the tree structure and divergence times.  See dft-mc.doc
for details.

We can run the Markov chain for 100 iterations with the following
command:

    > dft-mc blog.dft 100

We can see the progress of the Markov chain by examining various
quantities, such as the latent values associated with training cases.
The following command will plot the latent values for the first target
for the first six training cases:

    > dft-plt t o1@1:6 blog.dft | plot

The first four of these cases have "0" for their first target value,
the last two have "1".  The plot should show that the latent values
for the first four cases tend to be negative, whereas the latent
values for the last two cases tend to be positive, at least once the
Markov chain has approached convergence.

The 'dft-mc' command above takes 11 minutes of time on the system used
(see Ex-system.doc).  Once it is done, we can see how well the model
predicts new data using the following command, which looks at the
Dirichlet diffusion tree models produced by the last 60 iterations of
the Markov chain:

    > dft-pred pa blog.dft 41:

    Number of iterations used: 60

    Number of test cases: 500

    Average log probability of targets:    -6.102+-0.067

This takes 3.5 minutes on the system used (see Ex-system.doc).
Performance is not much worse than for the four-component mixture
model above, which is based on the true structure of the data.


A BIVARIATE DENSITY ESTIMATION PROBLEM

As a second illustration of the mixture model and Dirichlet diffusion
tree software, I generated bivariate real data from a mixture of two
component distributions, with probabilities 0.3 and 0.7.  These two
distributions were not exactly Gaussian, and the two real variables
were not exactly independent within one of these components.
Accordingly, modeling this data well with a mixture of Gaussian
distributions will require more than two components in the mixture.

For the exact distribution used, see the source of the generation
program, in rgen.c.  I generated 1000 cases with this program, stored
in 'rdata', of which the first 500 are used for training, and the rest
for testing.


A two-component mixture model for the density estimation problem.

We can first see what happens when we model this data with a mixture
of two Gaussians - even though we know the data cannot be perfectly
modeled in this way.  We specify this two-component model using the
'mix-spec' and 'model-spec' commands, as follows:

    > mix-spec rlog.2 0 2 2 / 1 0.05:0.5:0.2 10
    > model-spec rlog.2 real 0.05:0.5:0.5:1

The 'mix-spec' command creates the log file "rlog.2".  The arguments
following the log file name are the number of input attributes in a
case (always 0 at present), the number of target attributes (2 for
this bivariate problem), and the number of mixture components to use
(2 for this model).  

The Dirichlet concentration parameter follows the "/".  In this model,
its value is 1 (unscaled, since there's no 'x'), which produces a
uniform prior for the single number determining the probabilities of
the two components.

The "offset" parameters of the two components represent the Gaussian
means when modeling real data.  Hyperparameters determine the prior
means and standard deviations of these offsets (separately for the two
target attributes); priors for these hyperparameters are specified in
'mix-spec'.  In the above command, the prior for the mean of an offset
is Gaussian with standard deviation 10 (the last argument).  The
standard deviations for the offsets are given a hierarchical prior,
with a higher-level hyperparameter common to both the lower-level
standard deviations.  The top-level precision (standard deviation to
the power -2) is given a Gamma prior with mean 0.05 and shape
parameter 0.5; the precisions for the lower-level hyperparameters have
Gamma priors with mean given by the higher-level precision, and shape
parameter 0.2.  This is all specified by the second-to-last argument
of 'mix-spec'.

A similar hierarchical scheme is used for the "noise" standard
deviations (the standard deviations of the Gaussian distributions in
the mixture), except that this scheme has three levels - a top-level
hyperparameter, a hyperparameter for each target attribute, and
hyperparameters for each target for each component.  The 'model-spec'
command gives the top-level mean, and the shape parameters for the
Gamma priors going down the hierarchy.

We next specify where the data comes from, with 'data-spec':

    > data-spec rlog.2 0 2 / rdata@1:500 . rdata@501:1000 .

This says that there are 0 input attributes and 2 target attributes.

For this finite model, we can specify that all the Markov chain
updates should be done with Gibbs sampling, as follows:

    > mc-spec rlog.2 repeat 20 gibbs-indicators gibbs-params gibbs-hypers

The "repeat 20" just repeats these operations in a single iteration,
to reduce the volume of data stored in the log file.

Finally, we run the Markov chain simulation for 100 iterations:

    > mix-mc rlog.2 100

This takes 2.9 seconds on the system used (see Ex-system.doc) Once it
has finished, we can look at the hyperparameters and component
parameters at various iterations.  The last iteration should look
something like the following:

    > mix-display rlog.2

    MIXTURE MODEL IN FILE "rlog.2" WITH INDEX 100
    
    HYPERPARAMETERS
    
    Standard deviations for component offsets:
    
        0.068:     3.259    7.159
    
    Means for component offsets:
    
                  -1.408  +17.102
    
    Standard deviations for Gaussian target distributions:
    
        0.173:     0.201    4.680
    
    
    PARAMETERS AND FREQUENCIES FOR COMPONENTS OF THE MIXTURE
    
       1: 0.706   -2.052  +11.597
    
                   1.034    5.355
    
       2: 0.294   +1.751  +20.920
    
                   1.115    6.476

We see above that the two components are associated with fractions of
approximately 0.7 and 0.3 of the training cases, as expected from the
way the data was generated.  For each component, the two offset
parameters, giving the Gaussian means, are shown on the first line,
and the standard deviation parameters on the following line.  These
component parameters are approximately what we would expect from
looking at a plot of the data, but of course the two Gaussian
components cannot perfectly model the actual distribution.

A quantitative measure of how well the model fits the data can be
found by looking at the average log probability density of the test
cases:

    > mix-pred pa rlog.2 21:

    Number of iterations used: 80

    Number of test cases: 500

    Average log probability of targets:    -5.175+-0.048


An infinite mixture model for the density estimation problem.

To more closely approximate the true distribution, we can use a
mixture model with a countably infinite number of Gaussian components.
An infinite mixture is used if we simply omit the argument giving the
number of components in the 'mix-spec' command.  We must also change
the specification for the Dirichlet concentration parameter, preceding
it with an 'x' to indicate that it should be scaled so as to produce a
sensible infinite limit.  In the specification below, the moderate
value of 5 is chosen for this specification in order to indicate that
we believe that a fairly large number of components will have
substantial probability (the other prior specifications are the same
as before):

    > mix-spec rlog.inf 0 2 / x5 0.05:0.5:0.2 10

The 'model-spec' and 'data-spec' commands are the same as before:

    > model-spec rlog.inf real 0.05:0.5:0.5:1
    > data-spec rlog.inf 0 2 / rdata@1:500 . rdata@501:1000 .

The 'mc-spec' command must be altered, however, since it is not
possible to do Gibbs sampling for component indicators when there are
an infinite number of components.  The met-indicators operation is
used instead, with 10 changes being proposed to every indicator:

    > mc-spec rlog.inf repeat 20 met-indicators 10 gibbs-params gibbs-hypers

We can now run the simulation for 100 iterations:

    > mix-mc rlog.inf 100

This takes 19 seconds on the system used (see Ex-system.doc).  If we
now examine the state with 'mix-display', we will find that quite a
few (eg, 20) mixture components are associated with training cases -
though fewer components account for the bulk of the cases.

This model appears to fit the data slightly better than the
two-component model, as can be seen below:

    > mix-pred pa rlog.inf 21:

    Number of iterations used: 80

    Number of test cases: 500

    Average log probability of targets:    -5.101+-0.048

We can also see how well the model has captured the true distribution
by generating a sample of cases from a distribution drawn from the
posterior, as represented by the state at a particular iteration.  We
do this as follows:

    > mix-cases rlog.inf 100 new 1000

This command generates 1000 new cases based on iteration 100, and
stores them (one per line) in the file "new".  We can now use a plot
program to view a scatterplot of the data in "new", and compare it
with a scatterplot of data from the actual distribution.  Note that
the data in "new" is taken jointly from one example of a distribution
from the posterior distribution.  If 'mix-cases' is called for another
iteration, it will produce data from a different distribution from the
posterior, which in general could be quite different.  This variation
represents the uncertainly regarding the true distribution that
remains when only a finite amount of training data is available.  A
representation of the predictive distribution for a single new data
point, which is the average of distributions drawn from the posterior,
could be obtained by combining the output of 'mix-cases' for a number
of iterations.


Dirichlet diffusion tree models for the density estimation problem.

We can also model this data with a Dirichlet diffusion tree model.
The Dirichlet diffusion tree can either model the data points
directly, or model latent value to which noise is added to produce the
data points.  Different divergence functions can also be used, as well
as various schemes for Markov chain sampling.

We can start with a model in which the data points are directly
produced by the Dirichlet diffusion tree.  We start by specifying
the model and the priors as follows:

    > dft-spec rlog.dft1a 0 2 / 0.5:0.5:0.5 - 0.1:0.5

This command specifies that there are 0 input variables (as required
at the moment) and 2 target variables.  The first argument after the
"/" specifies a hierarchical prior for the diffusion standard
deviations.  The first level of this prior is for a value common to
both target variables, with the base sigma of 0.5 being followed by
the shape parameter of 0.5.  The third 0.5 is the shape parameter for
the next level of the hierarchy, in which a sigma for each variable is
linked to the common sigma.  The next two arguments specify the values
of coefficients in the divergence function, which has the form

   a(t) = c0 + c1/(1-t) + c2/(1-t)^2

The "-" indicates that c0 is fixed at zero, the next argument gives a
prior for c1, and the absense of an argument after tha indicates that
c2 is fixed at zero.

To indicate that the Dirichlet diffusion tree models the data directly,
we simply do not include any 'model-spec' command.  We specify the
source of the data as follows:

    > data-spec rlog.dft1a 0 2 / rdata@1:500 . rdata@501:1000 .

Finally, we need to specify how the Markov chain sampling is to be done:

    > mc-spec rlog.dft1a repeat 25 slice-positions met-terminals \
    >                              gibbs-sigmas slice-div

The sampling will be done without explicit representation of node
locations, since none of the operations in this specification create
node locations.  The 'slice-positions' and 'met-terminals' operations
update the tree structure and divergence times for nonterminal nodes.
The 'gibbs-sigmas' and 'slice-div' operations update the diffusion
standard deviations for the two target variables (as well as the
common standard deviation linking them) and the c1 parameter of the
divergence function.

We can now run the Markov chain with these operations in order to
sample from the posterior distribution of trees and hyperparameters
given the data:

    > dft-mc rlog.dft1a 100

This takes 2.6 minutes on the system used (see Ex-system.doc).  After
it has finished, we can look at the result with 'dft-display':

    > dft-display rlog.dft1a       

    DIFFUSION TREE MODEL IN FILE "rlog.dft1a" WITH INDEX 100
    
    
    PARAMETERS OF TREE 1
    
    Standard deviation parameters for diffusion process
    
        1.665:     2.121   13.638
    
    Divergence function parameters: - 1.6233 -

This lists the value at iteration 100 of the common standard
deviation, the diffusion standard deviations for the two target
variables, and the c1 parameter of the divergence function.

Other options to 'dft-display' allow examination of the tree
structure.  For instance,

    > dft-display -n rlog.dft1a 

    DIFFUSION TREE MODEL IN FILE "rlog.dft1a" WITH INDEX 100
    
    
    NON-TERMINAL NODES IN TREE 1
    
      Node  Children  Points  Div.Time
    
        -1 -336  337       6  0.603746
        -2  247  370       2  0.913668
        -3   23  181       2  0.995280
        -4 -409  334       3  0.944195
        -5 -211  374       4  0.995491
        -6 -385 -291      26  0.947063
        -7   91  209       2  0.926064
        -8 -493 -149       7  0.848791
        -9  139  355       2  0.997983
       -10 -275 -258       5  0.868474
       -11 -119  171      58  0.834055
       -12 -400   -1      17  0.583088
         
                    etc.

This shows the tree structure in terms of the children of each
nonterminal node, with nonterminal nodes being given negative numbers,
and terminal nodes (corresponding to data points) being given positive
numbers.  The "Points" column is the number of data points descended
from that node.

For diagnosing convergence, plots over time are more useful.  For
example, we can look at how the divergence times for the last common
ancestors of pairs of data points change over the course of the
simulation:

    > dft-plt t a1003123a14521 rlog.dft1a | plot

This plots the divergence time for the last common ancestor of
training cases 3 and 123 (numbered starting at 1) and the divergence
time of the last common ancestor of training cases 45 and 21.  The
syntax is a bit tricky.  The "a" indicator is followed by the number
of the tree, which is always 1 for this model, but more complex models
can have several trees.  This is followed by the indexes for the two
training cases, which MUST be written using the same number of digits
(with leading zeros added if necessary).

We can see how well the model has captured the distribution by seeing
how well it does at predicting test cases, using iterations from the
point when convergence seems to have been reached:

    > dft-pred tp rlog.dft1a 21:

    Number of iterations used: 80
    
    Case Targets         Log Prob
    
       1   -1.22   5.83    -4.336
       2   -2.73  16.33    -4.721
       3   -1.96   6.04    -3.990
       4   -0.77   9.24    -4.542
       5   -0.56   4.78    -5.072
    
         (middle lines omitted)

     496   -3.88  18.14    -6.200
     497    1.38   3.62    -8.357
     498   -0.40  26.50    -7.663
     499   -2.79  11.23    -3.938
     500   -2.28   4.53    -4.768
    
    Average log probability of targets:    -5.088+-0.047

This takes 23 seconds on the system used (see Ex-system.doc).
Performance is a bit better than for the infinite mixture model above.

Another approach to Markov chain sampling for this model is to keep
node locations as part of the state of the chain.  Updates to the tree
structure can then be done faster, but the number of iterations needed
for convergence and subsequent sampling may be greater.  Here is an
'mc-spec' command for this approach:

    > mc-spec   rlog.dft1b repeat 10 sample-locations \
                                     slice-positions met-terminals \
                                     gibbs-sigmas slice-div

Performing 100 iterations with these operations takes only 38 seconds
on the system used (see Ex-system.doc), and for this example,
predictive performance is nearly identical to that above.

One can also use a model with a different divergence function, as in
the following specification:

    > dft-spec  rlog.dft2a 0 2 / 0.5:0.5:0.5 0.01:0.5 - 0.01:0.5

The last three arguments of this command give priors for the c0 and c2
parameters of the divergence function, and specify that the c1
parameter is zero.  The divergence function therefore has the form
a(t) = c0 + c1/(1-t)^2.  This prior produces smoother density
functions, which is more appropriate for this example, although it
turns out that the difference in predictive performance is negligible.


BUILDING AN ADDITIVE MODEL USING TWO DIFFUSION TREES.

Here, I give an example of how a distribution with an additive
structure can be modeled using more than one diffusion tree.  The data
for this example (in file 'adata') consists of 30 cases, each with
eight binary variables.  It was manually constructed so that the first
four variables were unreleated to the last four variables.  With
respect to the first four variables, there are two groups, in which
these variables tend to all be "1", or all be "0".  Similarly, there
are two groups with respect to the last four variables.  The combined
effect is that there are four overall groups, corresponding to
patterns of 00000000, 11110000, 00001111, and 11111111. 

We could model this data as a mixture, or using a single Dirichlet
diffusion tree.  Even though this fails to capture the division into
two sets of variables, it does work fairly well.  Here is one way this
could be done with a diffusion tree model:

    > dft-spec   alog.dft1 0 8 / 0.2:4:2 - 1
    > model-spec alog.dft1 binary
    > data-spec  alog.dft1 0 8 2 / adata .
    > dft-gen    alog.dft1 fix 2
    > mc-spec    alog.dft1 repeat 50 gibbs-latent slice-positions met-terminals\
    >                                gibbs-sigmas 
    > dft-mc     alog.dft1 100

This is similar to what is done in the example of Ex-mixdft-b.doc.
The 'dft-gen' command fixes the diffusion standard deviations to 2
initially.  The subsequent 'gibbs-latent' command will produce values
for the latent variables that fit the data reasonably, starting the
chain off in from a reasonable state.  (Without the 'dft-gen' command,
the latent variables start off rather small.)

The above commands take 82 seconds on the system used (see
Ex-system.doc).  We can look at the tree found using 'dft-display'
with the "-g" option, or using the following command:

    > dft-dendrogram alog.dft1 100 alabels | ghostview -

The 'dft-dendrogram' command produces a Postscript picture of the
tree, which is here piped into the ghostview utility (it could instead
by printed).  This command shows the final tree, at iteration 100, and
uses the labels for cases in the file 'alabels', which labels the four
patterns mentioned above with A, B, C, and D .  You should be able to
see that cases with each of the four patterns are mostly grouped
together in subtrees.

To better capture the structure of this data, we can use a model with
two trees, specified as follows:

    > dft-spec   alog.dft2 0 8 / 0.1:4:1 - 1 / 0.1:4:1 - 1
    > model-spec alog.dft2 binary
    > data-spec  alog.dft2 0 8 2 / adata .

The two sets of specifications in 'dft-spec' after the slashes
(identical here) are for two Dirichlet diffusion trees, which are
generated independently in the prior distribution.  The values at the
terminal nodes of these trees are added together to produce the latent
values for the cases, which define the probabilities of the variables
being "0" or "1".  We hope that this will allow one tree to specialize
in modeling the first four variables and the other tree to specialize
in modeling the last four.

Here are the commands used to sample from the posterior distribution:

    > dft-gen  alog.dft2 fix 1.4
    > mc-spec  alog.dft2 create-latent repeat 50 gibbs-locations sample-latent \
    >                                            slice-positions met-terminals \
    >                                            gibbs-sigmas 
    > dft-mc   alog.dft2 100

Here again, the 'dft-gen' command helps start the chain off in a
reasonable state.  The 'create-latent' operation ensures that latent
values exist, which is necessary when there is more than one tree when
the model is non-Gaussian.  

These commands take 56 seconds on the system used (see Ex-system.doc).
We can look at the resulting hyperparameters as follows:

    > dft-display alog.dft2
    
    DIFFUSION TREE MODEL IN FILE "alog.dft2" WITH INDEX 100
    
    
    PARAMETERS OF TREE 1
    
    Standard deviation parameters for diffusion process
    
        0.247:     1.380    0.796    7.847    2.466    0.312
                   0.169    0.554    0.182
    
    Divergence function parameters: - 1.0000 -
    
    PARAMETERS OF TREE 2
    
    Standard deviation parameters for diffusion process
    
        0.147:     0.057    0.350    0.106    0.148    4.766
                 691.193    4.756    0.956
    
    Divergence function parameters: - 1.0000 -

We see that the first tree has mostly larger diffusion standard
deviations for the first four variables than the last four.  This is
reversed for the second tree, for which the diffusion standard
deviations are small for the first four variables and large for the
last four.  This is consistent with the two trees dividing up the
modeling task.  (In another run, the roles of the two trees might be
reversed.)

We can view the two trees as follows:

    > dft-dendrogram alog.dft2 100 1 alabels | ghostview -
    > dft-dendrogram alog.dft2 100 2 alabels | ghostview -

This should show that one tree divides the A and B cases from the C
and D cases, whereas the other tree divides the A and C cases from the
B and D cases.  This shows that the two-tree model has discovered the
structure of the data.



EXAMPLES OF NEURAL NETWORK SURVIVAL MODELS

The neural network software can also be used to model survival data.
In this application, the network models the "hazard function", which
determines the instantaneous risk of "death".  The hazard may be
depend on the values of inputs (covariates) for a particular case.  It
may be constant through time (for each case), or it may change over
time.  The data may be censored - ie, for some cases, it may be known
only that the individual survived for at least a certain time.

The details of these models are described in model-spec.doc.  Command
files for the examples below are found in the ex-surv directory.  This
sub-directory "pbc" contains files for the examples used in my talk on
"Survival analysis using a Bayesian neural network" at the 2001 Joint
Statistical Meetings in Atlanta.


Survival models with constant hazard.

I generated 700 cases of synthetic data in which the hazard function
is constant through time, but depends on one input, which was randomly
generated from a standard normal distribution.  When the input was x,
the hazard was h(x) = 1+(x-1)^2, which makes the distribution of the
time of death be exponential with mean 1/h(x).  For the first 200
cases, the time of death was censored at 0.5; if the actual time of
death was later than this, the time recorded was minus the censoring
time (ie, -0.5).  

The first 500 of these cases were used for training, and the remaining
200 for testing.

The network used to model this data had one input (x), and one output,
which was interpreted as log h(x).  One layer of eight hidden units
was used.  The following commands specify the network, model, and data
source:

    > net-spec clog.net 1 8 1 / - 0.05:1 0.05:1 - x0.05:1 - 100 
    > model-spec clog.net survival const-hazard
    > data-spec clog.net 1 1 / cdata@1:500 . cdata@-1:500 .

We can now train the network using the same general methods as for
other models.  Here is one set of commands that work reasonably well:

    > net-gen clog.net fix 0.5
    > mc-spec clog.net repeat 10 heatbath hybrid 100:10 0.2
    > net-mc clog.net 1
    > mc-spec clog.net repeat 4 sample-sigmas heatbath hybrid 500:10 0.4
    > net-mc clog.net 100

This takes 7.0 minutes on the system used (see Ex-system.doc).

Predictions for test cases can now be made using net-pred.  For
example, the following command produces the 10% and 90% quantiles of
the predictive distribution for time of death, based on iterations
from 25 onward.  These predictions can be compared to the actual times
of death (the "targets"):

    > net-pred itq clog.net 25:

    Number of iterations used: 76

    Case  Inputs Targets 10% Qnt 90% Qnt

       1   -0.01    0.29    0.05    1.05
       2   -1.43    0.04    0.02    0.37
       3   -0.68    0.03    0.02    0.52
       4    0.47    0.11    0.09    1.67
       5    0.63    0.97    0.07    1.74

            ( middle lines omitted )

     196    1.39    0.21    0.08    1.99
     197    0.04    0.07    0.06    1.11
     198    1.66    0.56    0.09    1.61
     199    1.33    1.48    0.07    1.76
     200   -1.41    0.08    0.01    0.39

Since there is only one input for this model, we can easily look at
the posterior distribution of the log of the hazard function with the
following command:

    > net-eval clog.net 25:%5 / -3 3 100 | plot

This plots sixteen functions that are drawn from the posterior
distribution of the log of the hazard function.  These functions
mostly match the actual function, which is log(1+(x-1)^2), for values
of x up to about one.  There is considerable uncertainty for values of
x above one, however.  Some of the functions from the posterior are a
good match for the true function in this region, but most are below
the true function.  Note that the data here are fairly sparse.


Survival models with piecewise-constant hazard.

One can also define models in which the hazard function depends on
time, as well, perhaps, on various inputs.  To demonstrate this, I
generated synthetic data for which the hazard function was given by
h(x,t) = (1+(x-1)^2) * t, which makes the cumulative distribution
function for the time of death of an individual for whom the covariate
is x be 1-exp(-(1+(x-1)^2)*t^2/2).

I generated 1000 cases (none of which were censored), and used the
first 700 for training and the remaining 300 for testing.

The network for this problem has two input units.  The first input is
set to the time, t, the second to the value of the covariate, x.
There is a single output unit, whose value will be interpreted as the
log of the hazard function.  If we decide to use one layer of eight
hidden units, we might specify the network as follows:

    > net-spec vlog.net 2 8 1 / - 0.05:1:1 0.05:1 - x0.05:1 - 100 

The prior for the input-hidden weights uses separate hyperparameters
for the two input units (representing time, t, and the covariate, x),
allowing the smoothness of the hazard function to be different for the
two.  In particular, if the hazard is actually constant, the time
input should end up being almost ignored.  (This can be demonstrated
by applying this model to the data used in the previous example.)

The hazard function determines the likelihood by means of its integral
from time zero up to the observed time of death, or the censoring
time.  Computing this exactly would be infeasible if the hazard
function was defined to be the network output when the first input is
set to a given time.  To allow these integrals to be done in a
reasonable amount of compute time, the hazard function is instead
piecewise constant with respect to time (but continuous with respect
to the covariates).  The time points where the hazard function changes
are given in the model-spec command.  For example, we can use the
following specification:

    > model-spec vlog.net survival pw-const-hazard 0.05 0.1 0.2 0.35 \
                                                    0.5 0.7 1.0 1.5

The eight numbers above are the times at which the hazard function
changes.  The log of the value of the hazard before the first time
(0.05) is found from the output of the network when the first input is
set to this time (and other inputs are set to the covariates for the
case); similarly for the log of the value of the hazard function after
the last time point (1.5).  The log of the hazard for other pieces is
found by setting the first input of the network to the average of the
times at the ends of the piece.  For instance, the log of the value of
the hazard function in the time range 0.7 to 1.0 is found by setting
the first input to (0.7+1.0)/2 = 0.85.  Alternatively, if the "log"
option is used, everything is done in terms of the log of the time
(see model-spec.doc for details).

Note that the number of time points specified is limited only by the
greater amount of computation required when there are many of them.
The hyperparameters controlling the weight priors will be able to
control "overfitting" even if the hazard function has many pieces.

The data specification for this problem says there is just one input
(the covariate) and one target (the time of death, or censoring time):

    > data-spec vlog.net 1 1 / vdata@1:700 . vdata@-1:700 .

Note that data-spec should be told there is only one input even though
net-spec is told there are two inputs - the extra input for the net is
the time, not an input read from the data file.

The following commands sample from the posterior distribution:

    > net-gen vlog.net fix 0.5
    > mc-spec vlog.net repeat 10 heatbath hybrid 100:10 0.2
    > net-mc vlog.net 1
    > mc-spec vlog.net repeat 4 sample-sigmas heatbath hybrid 500:10 0.4
    > net-mc vlog.net 100

This takes 28 minutes on the system used (see Ex-system.doc).

The net-pred command can be used to make predictions for test cases.
Here is a command to display the median of the predictive distribution
for time of death, based on iterations from 25 on, along with the
covariates (inputs) and the actual times of death (targets) for the
test cases:

    > net-pred itd vlog.net 25:

    Number of iterations used: 76
    
    Case  Inputs Targets Medians |Error|

       1    0.00    0.07    0.84  0.7711
       2   -0.22    0.42    0.74  0.3155
       3   -2.24    0.04    0.39  0.3480
       4   -0.81    0.26    0.58  0.3172
       5    1.02    3.12    1.04  2.0784
 
             ( middle lines omitted )

     296   -0.81    0.28    0.58  0.2966
     297    1.19    1.60    1.05  0.5503
     298   -1.53    0.57    0.48  0.0940
     299    0.99    2.67    1.09  1.5773
     300    0.28    1.13    0.92  0.2030

    Average abs. error guessing median:    0.32997+-0.01644

The predictive medians can be plotted against the inputs as follows:

    > net-pred idb vlog.net 25: | plot-points

The fairly small amount of scatter seen in this plot is a result of
computing the medians by Monte Carlo, which produces some random
error.  The exact median time of death as predicted by the model is a
smooth function of the input.

These predictions can be compared to the true median time of death for
individuals with the given covariates, as determined by the way the
data was generated, which are in the file "vmedians".

The log of the true hazard function for this problem is the sum of a
function of x only and a function of t only - what is called a
"proportional hazards" model.  A network model specified as follows
can discover this:

    > net-spec v2log.net 2 8 8 1 / - 0.05:1:1 0.05:1 - - 0.05:1:1 0.05:1 - \
                                   x0.05:1 x0.05:1 - 100 

The input-hidden weights for the two hidden layers have hierarchical
priors that allow one of them to look at only the time input and the
other to look at only the covariate.  There are no connections between
the hidden layers.  Final output can therefore be an additive function
of time and the covariate, if the hyperparameters are set in this way.

The remaining commands can be the same as above, except that the
stepsize needs to be reduced to get a reasonable acceptance rate (the
number of leapfrog steps is increased to compensate):

    > model-spec v2log.net survival pw-const-hazard 0.05 0.1 0.2 0.35 \
                                                     0.5 0.7 1.0 1.5

    > data-spec v2log.net 1 1 / vdata@1:700 . vdata@-1:700 .

    > net-gen v2log.net fix 0.5
    > mc-spec v2log.net repeat 10 heatbath hybrid 100:10 0.1
    > net-mc v2log.net 1

    > mc-spec v2log.net repeat 4 sample-sigmas heatbath hybrid 1000:10 0.25
    > net-mc v2log.net 400

This takes 15 hours to run on the system used (see Ex-system.doc).

The model does in fact discover that an additive form for the log
hazard is appropriate, as can be seen by examining the hyperparameters
with a command such as the following:

    > net-plt t h1@h3@ v2log.net | plot

One can see from this that the Markov chain spends most of its time in
regions of the hyperparameter space in which one hidden layer looks
almost only at the time input, and the other looks almost only at the
covariate.



EXAMPLES OF LEARNING WITH GRADIENT DESCENT, EARLY STOPPING & ENSEMBLES

Although this software is intended primarily to support research in
Bayesian methods, I have also implemented traditional gradient-descent
learning for neural networks.  This allows easy comparisons of
traditional and Bayesian methods, and supports research into
variations of traditional methods that may work better.

In particular, the software supports the "early stopping" technique.
When a network is trained to a minimum of the error on the training
set (minus the log likelihood), performance on test data is often bad,
since the training data has been "overfit".  To avoid this, many
people use one of the networks from earlier in the training process,
selected based on the error on a separate "validation set".

To do early stopping, the available training data must be partitioned
into an "estimation set" and a "validation set".  The network
parameters (weights and biases) are randomly initialized to values
close to zero, and then gradually changed (by gradient descent) so as
to minimize error on the estimation set.  The error on the validation
set is computed for the networks found during this process, and the
single network with minimum validation error is used to make
predictions for future test cases.

The split into estimation and validation sets in this procedure seems
a bit arbitrary and wasteful.  To alleviate this problem, one can
train several networks using early stopping, based on different
splits, and on different random initializations of the weights.
Predictions for training cases are then be made by averaging the
predictions from the networks selected from each of these runs, a
process somewhat analogous to the averaging done when making
predictions for a Bayesian model based on a sample from the posterior
distribution.

Neural network training using early stopping and ensembles is
described by Carl Rasmussen in his thesis (available in Postscript
from http://www.cs.utoronto.ca/~carl), and in a paper of mine on
``Assessing relevance determination methods using DELVE'' (see my web
page).

To demonstrate how the software can be used to do gradient descent
learning, early stopping, and prediction using ensembles, I will show
here how these methods can be applied to the binary response problem
used as an example earlier (see Ex-netgp-b.doc).

The data and command files for these examples are in the "ex-gdes"
directory.


Gradient descent learning for the binary response problem.

First, we will see how to use the software to set the network
parameters so as to minimize error (minus the log likelihood) on the
entire training set, or at least to get as close to the minimum error
as we can using gradient descent optimization.  We can then see how
well this network performs on test data.

To start, we need to specify the network architecture.  This is done
using the same sort of command as is used for Bayesian networks,
except that the prior specifications are simply "+" or "-", indicating
whether the corresponding sets of weights are present or absent.  The
following command creates a network with two inputs, one layer of 15
hidden units, and one output unit, with input-hidden weights, hidden
biases, hidden-output weights, and an output bias:

    > net-spec blog.gd 2 15 1 / - + + - + - +

The "+" is actually translated to a very large number, with the result
that the "prior" for these parameters has virtually no effect.
Instead of a "+", one can put a positive number, s, which produces the
effect of "weight decay" with penalty equal to the sum of the squares
of these weights times 1/(2*s^2).  More elaborate hierarchical priors
are meaningless if training is to be done by gradient descent.

Next, we must specify the data model.  For this problem, the response
is binary, and we use a model in which the probability of a response
of 1 is found by passing the output of the network through the
logistic function.  The following command specifies this:

    > model-spec blog.gd binary

When the response is real, a noise standard deviation of 1 would
conventionally be used, which causes minus the log likelihood to be
half the squared error.

The location of the data is specified as for Bayesian networks:

    > data-spec blog.gd 2 1 2 / bdata.train . 

For these examples, the 300 training cases are stored in bdata.train
(one per line, with the two inputs coming first).  The 200 test cases
are in bdata.test, but this is not mentioned above.  The reason for
doing things this way (rather than putting all the data in one file)
will be apparent when we get to the examples using early stopping.

Finally, we can train the network using gradient descent, with the
command:

    > net-gd blog.gd 100000 1000 / 0.4 batch

This does 100000 iterations of "batch" gradient descent (ie, with each
update based on all training cases), with networks being saved in the
log file every 1000 iterations.  The software also supports "on-line"
gradient descent, which is often faster to converge initially, but
does not reach the exact optimum.  See net-gd.doc for details.

The stepsize to use for gradient descent learning is specified as
well; here it is 0.4.  If learning is unstable (ie, the error
sometimes goes up rather than down), the stepsize will have to be
reduced.  Net-gd does not try to determine relative stepsizes itself,
but stepsizes for groups of parameters can be set individually.

The above command takes 200 seconds on the system used (see
Ex-system.doc).  While waiting, you can monitor progress using
net-plt.  For example, the progress of the training error can be
viewed with the command:

    > net-plt t l blog.gd | plot

Individual networks can be displayed using net-display.  For example,

    > net-display -w blog.gd 1000

displays the network at iteration 1000.  The "-w" option suppresses
the hyperparameter values, which are meaningless with this model.

Once training has finished, we can make predictions based on the last
network, which should have the lowest training error.  The following
command prints a summary of performance at predicting the cases in
bdata.test, both in terms of the log probability assigned to the
correct target value and in terms of the error rate when guessing the
target:

    > net-pred mpa blog.gd 100000 / bdata.test .

    Number of iterations used: 1

    Number of test cases: 200

    Average log probability of targets:    -0.364+-0.066

    Fraction of guesses that were wrong:  0.1450+-0.0250

Performance is substantially worse than that obtained using Bayesian
training.  This is due to "overfitting".  The following command
illustrates the problem by plotting the change during the run of the
training error and the error on the test cases:

    > net-plt t lL blog.gd / bdata.test . | plot

From this plot, it is clear that we would have been better off to stop
training earlier than 100000 iterations.  Of course, we can't stop
training based on the test error plotted above, since we don't know
the test targets when training.


Gradient descent with early stopping for the binary response problem.

We can try to prevent overfitting by choosing one of the networks
found during training according to performance on a subset of the
available training cases that we have excluded from the set used for
the gradient descent training.  This training scheme can be
implemented using the following commands:

    > net-spec blog.gdes 2 15 1 / - + + - + - +
    > model-spec blog.gdes binary

    > data-spec blog.gdes 2 1 2 / bdata.train@1:225 . bdata.train@226:300 .

    > net-gd blog.gdes 100 5 / 0.4 batch
    > net-gd blog.gdes 1000 50 / 0.4 batch
    > net-gd blog.gdes 20000 500 / 0.4 batch

    > net-plt t L blog.gdes | find-min

Of the 300 available training cases, the first three-quarters are used
for the gradient descent training, while the last quarter are used to
choose the a network from those found during training.  These 75
validation cases are listed as "test" cases in the data-spec command
above, though they are not true test cases.  This allows the best of
the networks according to error on the validation set to be found
using the net-plt command, in conjunction with find-min (documented in
find-min.doc).  Note that to save computer time, one might wish to
actually stop the training once it becomes apparent that further
training is unlikely to find a better network, but that is not
attempted here.

Three net-gd commands are used above so that networks can be saved to
the log file more frequently early in training.  It sometimes happens
that the best network according to validation error is from very early
in the training process.  We would not wish to miss it as a result of
saving too few networks in the early stages of training.

The final find-min command above outputs "3000" as the iteration that
gives the best validation error.  We can use this network to make
predictions for test cases, as below:

    > net-pred mpa blog.gdes 3000 / bdata.test .                           

    Number of iterations used: 1

    Number of test cases: 200

    Average log probability of targets:    -0.263+-0.043

    Fraction of guesses that were wrong:  0.1150+-0.0226

As can be seen, performance is considerably better than that obtained
in the previous section by training for 100000 iterations.


Using an ensemble of networks trained by early stopping.

In the early stopping procedure just described, the use of the first
three-quarters of the training data for estimation and the last
one-quarter for validation is arbitrary.  Whenever a training
procedure involves arbitrary or random choices, it is generally better
(on average) to repeat the procedure several times with different
choices, and then make predictions by averaging the predictions made
by the networks in this "ensemble".  The following commands implement
this idea for early stopping, by averaging over both the choice of
which quarter of the data to use for validation, and over the random
choice of initial weights:

    > net-spec blog.gdese1 2 15 1 / - + + - + - +
    > model-spec blog.gdese1 binary
    > data-spec blog.gdese1 2 1 2 / bdata.train@-226:300 . bdata.train@226:300 .

    > rand-seed blog.gdese1 1

    > net-gd blog.gdese1 100 5 / 0.4 batch
    > net-gd blog.gdese1 1000 50 / 0.4 batch
    > net-gd blog.gdese1 20000 500 / 0.4 batch

    > net-plt t L blog.gdese1 | find-min

    > net-spec blog.gdese2 2 15 1 / - + + - + - +
    > model-spec blog.gdese2 binary
    > data-spec blog.gdese2 2 1 2 / bdata.train@-151:225 . bdata.train@151:225 .

    > rand-seed blog.gdese2 2

    > net-gd blog.gdese2 100 5 / 0.4 batch
    > net-gd blog.gdese2 1000 50 / 0.4 batch
    > net-gd blog.gdese2 20000 500 / 0.4 batch

    > net-plt t L blog.gdese2 | find-min

    > net-spec blog.gdese3 2 15 1 / - + + - + - +
    > model-spec blog.gdese3 binary
    > data-spec blog.gdese3 2 1 2 / bdata.train@-76:150 . bdata.train@75:150 .

    > rand-seed blog.gdese3 3 

    > net-gd blog.gdese3 100 5 / 0.4 batch
    > net-gd blog.gdese3 1000 50 / 0.4 batch
    > net-gd blog.gdese3 20000 500 / 0.4 batch

    > net-plt t L blog.gdese3 | find-min

    > net-spec blog.gdese4 2 15 1 / - + + - + - +
    > model-spec blog.gdese4 binary
    > data-spec blog.gdese4 2 1 2 / bdata.train@-1:75 . bdata.train@1:75 .

    > rand-seed blog.gdese4 4

    > net-gd blog.gdese4 100 5 / 0.4 batch
    > net-gd blog.gdese4 1000 50 / 0.4 batch
    > net-gd blog.gdese4 20000 500 / 0.4 batch

    > net-plt t L blog.gdese4 | find-min

The networks selected from the four training runs above as having
lowest validation error are at iterations 3000, 950, 3500, and 11000.
We can now make predictions for test cases using these four networks,
as follows:

    > net-pred mpa blog.gdese1 3000 blog.gdese2 950 \
                   blog.gdese3 3500 blog.gdese4 11000 / bdata.test .

    Number of iterations used: 4

    Number of test cases: 200

    Average log probability of targets:    -0.263+-0.040

    Fraction of guesses that were wrong:  0.1050+-0.0217

The resulting classification performance is slightly better than was
found using just the first of the four networks.



HINTS AND WARNINGS

1) The error messages for invalid specifications of quantities for
   the plot programs are not very specific.  You should remember that
   quantities may be scalars or arrays, or sometimes either.  If the 
   quantity you want is an array, you have to include a "@" character.  
   To further complicate matters, some quantities take numeric modifiers,
   which are distinct from array indexes.  See quantities.doc and the 
   specific documentation on quantities for each application for more 
   details.

2) Some confusion is possible regarding hyperparameter values because
   they can be looked at in three ways:  as standard deviations (widths),
   as variances (squares of the standard deviations), and as precisions
   (inverse variances).  In particular, note that although the priors 
   for hyperparameters are described in terms of Gamma distributions for
   the precisions, their scale is specified in the net-spec and
   model-spec commands in terms of the corresponding standard deviations.

3) When there is a single output unit in a network, a specification of 
   the form "w:a:b" for the hidden-to-output weights is mathematically
   equivalent to one of the form "w:a::b".  The two specifications
   differ computationally, however.  In the "w:a:b" form, lower-level
   hyperparameters that each control a single weight are explicitly
   represented; with "w:a::b", equivalent hyperparameters exist
   mathematically, but are not represented explicitly.  The "w:a:b"
   form is probably to be preferred, since explicit hyperparameters 
   are of assistance to the heuristic procedure that chooses
   stepsizes for the dynamical updates.

4) Poor conditioning of matrix operations used for Gaussian processes
   can be a problem with the "sample-values" and "scan-values" operations, 
   and for the 'gp-eval' program.  The symptoms are error messages about
   Cholesky decompositions or matrix inversions not working.  Assuming 
   that these aren't due to bugs in the software, the solution is to
   improve the conditioning of the covariance matrix, hopefully without
   making the model depart to any significant degree from what you really
   wanted.  Conditioning can be improved in three main ways:
  
      a) Decrease the constant part of the covariance function.  There's
         almost never any reason for this to be greater than the range of
         the targets in the training cases, assuming the targets are
         centred at about zero.

      b) Increase the jitter part of the covariance.  For 'gp-eval' with
         the "targets" option, noise in the regression model acts the 
         same way as jitter.  Of course, increasing the jitter changes
         the model.

      c) Use a power less than 2 in an exponential part of the covariance.
         Poor conditioning results when the covariance has only constant, 
         linear, and exponential parts, with the exponential part having
         a power of 2 (the default), corresponding to smooth functions.  
         Decreasing the power makes the functions less smooth, and hence
         less predictable, which makes the matrix better conditioned.

      d) Use scan-values rather than sample-values.  The prior covariance
         matrix that is inverted in scan-values is probably less likely
         to be poorly conditioned than the posterior covariance matrix
         inverted in sample-values.  However, scan-values does not produce
         independent draws, so convergence may be slower.

5) When using Annealed Importance Sampling, be careful that the number
   of temperatures in the annealing schedule (set by mc-temp-sched) is
   what you intend.  Remember that there's one more at the end (at a 
   temperature of one) that isn't explicitly specified.  Also be careful 
   that the number of AIS operations in the mc-spec command is such as to
   move through this schedule as desired.  You can check that things are 
   working as desired with a command such as such as "xxx-plt t I".  If 
   you get things wrong, looking at the iterations that were supposed to 
   be at inverse temperature one but aren't will give completely misleading
   results.

6) If the system crashes in the middle of a run of 'net-mc' (say), one
   can usually continue from the last iteration written to the log file 
   by just invoking 'net-mc' again with the same arguments (just as 
   one can continue for more iterations after 'net-mc' terminates 
   normally).  Problems could arise if the system crashed in the middle 
   of writing the records pertaining to an iteration, in which case some 
   fixup using 'log-copy' may be required.  Such problems could come
   either from a partial record at the end of the log file, or from
   a less-than-complete set of full records.  It is best to assess the 
   situation using 'log-records' before proceeding.

7) If you need to change the name of a program to avoid conflicts with 
   other programs you use, it is probably best to simply change the name 
   of the link in this software's 'bin' directory, leaving the name 
   unchanged in all the other directories.



GUIDE TO FURTHER DOCUMENTATION

The overview and examples above are intended just to get you started.
To use the software to do real work, you will probably need to refer
to the detailed documentation on the commands (and on the features
common to more than one command) that is contained in the files ending
with ".doc".  These files are found in the various sub-directories,
and are also all linked to from the 'doc' directory.  For quick
reference, all commands print a brief summary of the command syntax
when they are invoked with no arguments.

In the syntax descriptions used, the characters "[" and "]" enclose
parts of the command that are optional, "{" and "}" enclose optional
parts that can be repeated, and "|" separates alternatives.  Except
for the command name (or other obvious keywords), the words in the
syntax descriptions are descriptive of what is to be entered, except
that words in quotes are to be entered literally (without the quotes).

The ".doc" files present in the various directories are listed below,
with the more important files marked by "*".  Programs listed as
"xxx-something" are generic, with "xxx" being replaced by the name of
an application (eg, "net", "gp", or "mix").  In some cases, further
documentation is available under the specific name.

The file index.html is a hypertext index to this documentation.  It
can be accessed using a Web browser (eg, netscape), by opening
index.html as a local file (which will probably require giving its
full path name).  The index.html file must reside in the 'doc'
directory for this software, so that relative references will work
correctly.  The files accessed this way are .html files derived from
the .doc files.  The content is identical, except that references to
other .doc files have been converted into hypertext links that you can
follow with the browser.

The 'doc' directory also contains comments on the various software
releases, in files of the form 'Release.YYYY-MM-DD.doc'.

All the introductory documentation (including this) is collected into
the 'manual' file, as plain text.  You can print all the documentation
by going to the main directory for this software and issuing a command
such as

  lpr doc/manual util/*.doc mc/*.doc dist/*.doc bvg/*.doc \
      net/*.doc gp/*.doc mix/*.doc dft/*.doc doc/Rel*.doc
 
(or using whatever command other than 'lpr' you use to print text files).
This will produce about 200 pages of paper.


Generic utility programs [util]:

  * log             Facilities for handling log files
    log-types       Types of log file records used by various programs

    log-copy        Copy part of a log file to a new log file
    log-append      Append records from one log file to the end of another
    log-last        Display the index of the last record in a log file
    log-records     List all records in a log file  
    log-equal       Check if records in log files match

    formula         Syntax for arithmetic formulas
    calc            Simple calculator program

  * data-spec       Specify data sets for training and testing
  * numin           Facilities for input of numeric data

  * model-spec      Specify model for targets
  * prior           Meaning and syntax of prior specifications

    find-min        Find entry with minimum value (for cross validation)

    grid            Output a grid of points  
    extract         Extract items at random from a data file 

  * rand-seed       Specify a random number seed  

  * quantities      Numeric quantities obtainable from log files

  * xxx-plt         Write quantities from log files, suitable for plotting
    xxx-tbl         Write quantities from log files in a tabular form
    xxx-hist        Build a histogram for a quantity using data from log files

  * series          Analyse stationary time series data


Markov chain Monte Carlo facilities [mc]:

  * mc              Programs and modules supporting Markov chain Monte Carlo 
  * mc-spec         Specify how to do the Markov chain simulation
  * xxx-mc          Run a Markov chain simulation
  * xxx-circ        Do a circularly-coupled simulation
  * xxx-wrap        Create wrapped-around chain from existing simulation run

  * mc-quantities   Quantities from log files relating to Monte Carlo 

    mc-temp-sched   Specify temperature schedule for tempering methods
    mc-temp-filter  Copy only iterations at a given temperature
    mc-ais          Monitor annealed importance sampling (AIS) runs

    xxx-grad-test   Test the correctness of the energy gradient computations
    xxx-stepsizes   Display and evaluate stepsizes used for dynamics
    xxx-genp        Generate random momentum variables

    xxx-his         Do Hamiltonian importance sampling


Markov chain sampling for a specified distribution [dist]:

  * dist            Markov chain sampling for a specified distribution
  * dist-spec       Specify a distribution to sample from

    dist-initial    Specify initial state for Markov chain
    dist-stepsizes  Display, evaluate, or set stepsizes used for dynamics
  * dist-mc         Do Markov chain sampling for the specified distribution
    dist-gen        Generate values for state variables from the prior

    dist-display    Print state variables at a specified iteration
  * dist-quantities Quantities defined for a specified distribution

  * dist-est        Estimate the expectation of some function of state


Markov chain sampling for a bivariate Gaussian [bvg]:

    bvg             Demo of Markov chain sampling from a bivariate Gaussian
    bvg-spec        Specify a bivariate Gaussian distribution to sample from

    bvg-initial     Set initial state for sampling from a bivariate Gaussian
    bvg-mc          Do Markov chain simulation for a bivariate Gaussian

    bvg-plt         Get quantities from a bvg log file, suitable to plot


Bayesian neural networks [net]:

  * net             Bayesian inference for neural networks using MCMC
  * net-spec        Create a new network, or display existing specifications 

  * net-mc          Do Markov chain simulation to sample networks
  * net-gen         Generate networks from the prior, or with fixed values  
    net-approx      Specify quadratic approximation to replace log likelihood
    net-gd          Train a network by gradient descent in the error

  * net-display     Print network parameters and/or hyperparameters

  * net-quantities  Quantities from log files relating to networks
  * net-plt         Get quantities from net log files, suitable for plotting
    net-tbl         Get quantities from net log files and output as table
    net-hist        Build histogram for quantity obtained from net log files

  * net-pred        Make predictions for test cases

    net-eval        Evaluate network functions over a grid  
    net-dvar        Find the variance of a difference in function values

    net-rej         Generate networks from the posterior by rejection sampling


Gaussian process models [gp]:

  * gp              Bayesian modelling using Gaussian processes
  * gp-spec         Specify a Gaussian process model, or display existing spec

  * gp-mc           Use Markov chain to sample Gaussian process hyperparameters
  * gp-gen          Generate GP hyperparameters randomly, or fix them

  * gp-display      Print Gaussian process hyperparameters & other information
  * gp-quantities   Quantities from log files relating to Gaussian processes

  * gp-pred         Make predictions for test cases using Gaussian process
    gp-eval         Evaluate function drawn from a Gaussian process over a grid

    gp-cov          Print covariance matrix for a Gaussian process 
    gp-eigen        Find eigenvalues/vectors of covariance matrix


Bayesian inference for mixture models [mix]:

  * mix             Bayesian inference for mixture models
  * mix-spec        Specify a mixture model, or display existing spec

  * mix-mc          Use Markov chain to do sampling for a mixture model
  * mix-gen         Generate hyperparameters randomly, or fix them

  * mix-display     Print mixture model parameters, hyperparameters, etc.
  * mix-quantities  Quantities from log files relating to mixture models

  * mix-pred        Make predictions for tests cases using mixture models
    mix-cases       Generate cases from a mixture model


Bayesian inference for Dirichlet diffusion tree models [dft]:

  * dft             Bayesian inference for diffusion tree models
  * dft-spec        Specify a diffusion tree model, or display existing spec

  * dft-mc          Use Markov chain to do sampling for a diffusion tree model
  * dft-gen         Generate hyperparameters randomly, or fix them

  * dft-display     Print diffusion tree model parameters, hyperparameters, etc.
    dft-dendrogram  Create Postscript representation of a dendrogram of a tree
  * dft-quantities  Quantities from log files relating to diffusion tree models

  * dft-pred        Make predictions using Dirichlet diffusion trees
    dft-cases       Generate cases from a diffusion tree model



ACKNOWLEDGEMENTS

Inspiration for implementing the Gaussian process methods came from
the work of Carl Rasmussen and Chris Williams.  I also benefited from
looking at Carl Rasmussen's implementation.

The sampling method for top-level hyperparameters using adaptive
rejection sampling, and the features allowing cpu time to be stored,
displayed, and used to control the number of iterations, are also
based on work by Carl Edward Rasmussen.

Thanks also to Tim Howells, Dirk Husmeier, Krunoslav Kovac, Marcus
Lee, David MacKay, Neil Montgomery, Tony Plate, Jeff Rosenthal, Ricard
Ferran Sans, and Chris Williams for comments on the documentation, for
testing the programs, and for finding bugs.
