This directory contains a package for nonlinear prediction
using agglomerative cluster trees. 

A general description is given in the Appendix of 
the paper T. Frese, C. A. Bouman and K. Sauer, 
'Adaptive Wavelet Graph Model for Bayesian Tomographic 
Reconstruction', to appear in IEEE Transactions on 
Image Processing.

The main functionality of the cluster tree prediction
is to take an input vector x, classify it into a node k
of a binary tree, and then based on this classification,
perform a linear prediction 
         
             y = A_k * x + b_k 

where the parameters A_k and b_k are functions of the 
tree node k. The tree classifier and the MMSE linear
predictors [A_k,b_k] for each node are obtained based 
on training data.

The source code in the src directory generates a 
library called 'libagt.a' which can be used
by other programs to generate and use the 
agglomerative trees. 

The EXAMPLE subdirectory contains sample programs
(see EXAMPLE/src) that use the libagt.a library 
to generate a tree using training data and to
perform the nonlinear prediction on test data.
Sample data and a shell script illustrating the
use of the programs are also supplied in the EXAMPLE
subdirectory.


This README file contains the following sections:

I.   Technical description
II.  Known Problems
III. Installation
IV.  Functionality exported in libagt.a

For instructions on the code in EXAMPLE/src and on
running the example, see the file EXAMPLE/README.EXAMPLE.


I. Technical description
---------------------------------------------------------

The software generates an agglomerative binary 
prediction tree. The tree generation takes as input 
a set of training vectors, where each vector consists
of an x-vector (input to the predictor) and the corresponding y-vector
which is the nominal output. 
The algorithm uses a second data set to perform 
cross-validation in the form of tree pruning
to avoid over-parameterization.

Based on the training and pruning data sets, the tree is 
generated as follows:

1) Obtain the leaves of the tree by finely partitioning
   the input space (x) using standard k-mean
   clustering of the x-vectors of the training set. 
   For each of the clusters k, a minimum mean square error (MMSE)
   linear predictor [A_k, b_k] is computed using only the 
   training samples assigned to cluster k.

2) Merge the clusters into a binary tree. The
   clusters form the leave nodes of the tree. Starting
   with the leaves, pairs of nodes are successively merged
   until a single binary tree is obtained. Merging two nodes
   means combining the training samples of the two nodes
   and computing a single MMSE linear predictor for the 
   merged node. 

   The merging is performed in a greedy fashion. 
   At each step, the pair of nodes to be merged is 
   selected as the one whose merging results in the minimal 
   increase in total prediction error on the training set.

   Merging solely based on increase in prediction error
   is not always robust (especially in cases, where clusters
   have very few data points such that their MMSE predictors
   are over-parameterized and achieve a prediction error of zero).
   To 'regularize' the merging, a term accounting for the 
   distance of the nodes in x-input space can be added to the
   cost function for the merging:
   
   merge_cost= Delta E + alpha*(N_1*|mu_1-mu_m|^2+N_2*|mu_2-mu_m|^2)
 
   Here Delta E is the increase in prediction error due to the 
   merging. N_1 and N_2 are the numbers of samples in the nodes
   to be merged. mu_1 and mu_2 are the means of the x-vectors in
   the two nodes and mu_m is the mean of the data samples in the
   merged node. alpha is a regularization parameter that controls
   the relative weighting of distance term in the cost function.
   
3) After merging the clusters into a tree, the tree is pruned
   using the standard pruning algorithm. Since our data 
   classification at run-time is bottom
   up, pruned nodes are not actually removed from the tree
   but instead, are marked as pruned.
   Based on the pruning set, the prediction covariance
   for each tree node is computed as yer2=(y_hat-y)(y_hat-y)^t
   where the y are the supplied, 'true' y-vectors in the
   pruning file and y_hat=Ax+b are the predicted values.

After the tree is built, the non-linear prediction of an input vector
x is performed as follows: 

  The input vector x is first classified into one of the 
  leaf clusters (from the initial k-means clustering).
  From this leaf, we go up the tree towards the root node
  until we hit the first node k that is NOT marked as pruned.
  This is the classification of the input sample x. The
  linear MMSE predictor [A_k,b_k] of this node k 
  is then used to perform the prediction y=A_k*x+b_k.
   

II. Known problems
---------------------------------------------------------

1) A known problem with the software is that the final
tree can depend significantly on the initial k-means
clustering. When running the make_tree routine several
times with the same input, the resulting number of non-pruned
nodes can vary somewhat based on the randomseed used for
the initial clustering. 

2) The linear MMSE predictors are computed using the
pseudoinvert.c routine in ansi_lib_loc. This routine
relies on 'ansi_lib_loc/svdcmp.c' taken from numerical 
recipes in C. For some matrices, the svdcmp.c routine produces
slightly inaccurate results. This can result in small inaccuracies
in the calculation of the cost function for merging (negative
merge cost). If you have problems with this, you might want 
to comment out the '#define PINV' in AGTREE/agtree.h. 
This will revert to a regular matrix inversion. 
(To avoid problems with singular matrices, a small constant 
INVCONST defined in agtree.h will be added to the diagonal 
before calling invert). 



III. Installation
---------------------------------------------------------

After unpacking the tar-file, you will have a directory
AGTREE. Change directories to AGTREE/src and modify
the Makefile to your needs. For Linux, Sun's, and HP's
the only change that should be necessary is to change
the OS variable.

From the src directory, type 'make'. This
should generate the library AGTREE/libagt.a.

The file AGTREE/agtree.h is the header file
that should be included when linking AGTREE/libagt.a
into other programs.





IV. Functionality exported in libagt.a
---------------------------------------------------------

The library exports the following three routines:

  make_agtree:    routine to generate prediction tree 
                  based on training data

  read_tree:      read-in an existing prediction tree generated
                  with make_agtree.

  classify_xvec:  perform classification of an input x-vector
                  into a tree node.

The linear prediction is not exported since it is
more efficiently implemented in the application 
program (only takes a matrix-vector product, see
EXAMPLE/src/predict.c). 
Below are detailed descriptions of the exported routines:


1) void make_agtree(struct cmds *params)
----------------------------------------

Generates an agglomerative prediction tree based
on training data which must be stored in a file on disc.
The struct 'params' contains the input parameters to 
make_agtree and is defined in agtree.h. 
The input parameters are:

params.trainfile: name of file containing the 
                  training samples (see file-format below).

params.prunefile: name of file containing the
                  pruning samples (if pruning is switched on).

params.outfile: name of output file which will contain 
                the tree information. This file can be 
                read by read_tree. In addition to this outfile,
                make_agtree will write a file <params.outfile>_Evar.
                This file will contain a single matrix of size y_len*y_len
                which is the expected conditional covariance of 
                the predicted vector y.
                This conditional covariance is computed as the
                expectation over the entire pruning set, i.e. over
                all tree nodes, and can be used to regularize
                the covariance estimates in the tree nodes (yer2).
                See the IP paper for details.

params.nb_clusters: number of initial vq-clusters when 
                    building the tree, i.e. the number
                    of leaves in the binary tree. Choice
                    of this number depends on the size of 
                    the training set. On average, each vq
                    cluster should contain at least a few
                    training samples. (For each cluster, 
                    the number of parameters to be estimated for the
                    linear predictor [A_k,b_k] is 
                    x_len*y_len + y_len .

params.alpha: Regularization factor for merging of nodes.
              When set to zero, the merging is performed
              based on prediction error increase on the training set
              only. To increase robustness, a term accounting
              for the distance between the cluster means (in
              x input space) can be added to the cost function 
              for the merging. params.alpha controls the 
              the weight of this distance term (see section I).
              Typically, alpha should NOT be set to zero, but rather
              to a small value (e.g. 0.011) such that clusters 
              with very few data points will be merged in a 
              meaningful manner.
 
params.prune: when set to zero, pruning is switched off. The
              initial vq-clusters will be merged until 
              there are params.merge_limit root nodes left.
	      Normally set to one.              

params.merge_limit: When pruning is on, this must be set to 1
                    in order to merge the initial vq clusters
                    into a single binary tree before pruning is
                    performed. When pruning is off, the initial
                    vq-clusters (leaves) are merged until there
                    are params.merge_limit root nodes left. In this
                    case, the resulting 'tree' (forest) will have 
                    params.merge_limit different classes associated 
                    with prediction filters.
                    Normally set to one.

params.nb_nodes: need not be specified, after returning
                 from make_agtree, this will contain the
                 total number of nodes in the tree including
                 the leaves, not accounting for pruning.
                 For a binary tree (i.e. merge_limit=1),
                 this will always be 2*params.nb_clusters.                    

params.avg_cost_md, params.avg_cost_tot: 
                 These are for testing only and need not be specified.


File-format for training and pruning files:
------------------------------------------

For the training and pruning files, make_agtree expects
TWO files each, one containing the size information and
one containing the data vectors (this is done so that
training files can easily be appended).
Let's say params.trainfile='train_dat'. 
Then make_agtree expects the files

train_dat_sz: ASCII file containing three entries in this order:
              number of training vectors (=lines) in train_dat (no_tr_pts)
              length of input vector x (x_len)
              length of output vector y (y_len)
	      So a valid train_dat_sz would be
                1000
                8
                3
              which would mean 1000 training samples,
              x_len=8, y_len=3. (See AGTREE/EXAMPLE/data/train_dat.asc_sz
	      for an example).

train_dat : ASCII file containing training samples. Each
            line contains one training vector consisting of an
            input x-vector and the corresponding y output vector:
            x_1 y_1
            x_2 y_2 
             ...
            x_no_tr_pts y_no_tr_pts
 
            where each line contains x_len + y_len entries separated
            by white spaces.
            For an example, see AGTREE/EXAMPLE/data/train_dat.asc.

The file format of the pruning file(s) is identical, i.e. 
if params.prunefile='prune_dat', the program expects
the files prune_dat and prune_dat_sz with formats as described
above. See AGTREE/EXAMPLE/data/prune_dat.asc and prune_dat.asc_sz
for examples.






2) struct node* read_tree(char *fname, int *Xlen, 
                          int *Ylen, int *nbclust, int *nbnode);
------------------------------------------------------------------

This routine reads a tree generated by make_agtree.
The data structure 'struct node' is defined in agtree.h
and contains the node information of the tree including the 
linear predictors [A_k,b_k]= [node[k].a,node[k].b] and prediction
covariance matrix of y given by 
R_k(i,j)=node[k].yer2[i][j] where 0<i<y_len, 0<j<y_len.

If fname is the output_file from make_agtree then a call to
read tree would look like this:

struct node tree;
int x_len,y_len,nbclust,nbnodes;

tree=read_tree(fname,&x_len,&y_len,&nbclust,&nbnodes);

The returned x_len and y_len allow for checking whether 
the vector length of the tree is consistent with 
what the application program expects.





3) int classify_xvec(double *xvec, int x_len, struct node *clust, 
                     struct cmds *params);
-------------------------------------------------------------------

This routine takes an input x-vector and classifies it into
a node of the tree. So after generating a tree with make_agtree
and then reading in the tree with read_tree, you can call this
routine to actually classify a data sample (x-vector) to obtain
the node number to identify the correct linear predictor and 
prediction covariance.

A call would look like this:
-------------------
int node_number;
struct cmds params;
struct node tree;
int nbclust,nbnodes,x_len,y_len;

tree=read_tree(fname,&x_len,&y_len,&nbclust,&nbnodes);

params.nb_clusters = nbclust;
params.nb_nodes = nbnodes;

node_number=classify_xvec(xvec,x_len,&tree,&params);
---------------------

where xvec is the input vector of type double with length x_len.
Now the linear predictor for the input vector xvec is

tree[node_number].a[i][j],   0<i<x_len, 0<j<y_len and
tree[node_number].b[j],      0<j<y_len

and the conditional covariance matrix for the predicted y
vector is 

tree[node_number].yer2[i][j],   0<i<y_len, 0<j<y_len and

The prediction of y=Ax+b is then easily performed as:
-----------------------------
for (j=0;j<y_len;j++)
  y_vec[j] =tree[node_number].b[j];

for (j=0;j<y_len;j++)
  for (k=0;k<x_len;k++)
    y_vec[j] += (x_vec[k] * tree[node_number].a[k][j]);
------------------------------

For a working example, see AGTREE/EXAMPLE/src/predict.c

  












