readme

gibbs

This README covers the Gibbs sampling code, along with code used
to test inference methods in general.

Comments to Daniel Lowd (lowd at cs dot washington dot edu)

This code is provided to accompany ``Naive Bayes Models for
Probability Estimation'', by Daniel Lowd and Pedro Domingos,
to appear in ICML 2005.  This document describes basic 
installation and usage.

Outline:
I.   License
II.  Installation
III. Usage
IV.  Source code


I. LICENSE

You are welcome to use the code under the terms of the modified BSD license
for research or commercial purposes, however please acknowledge its use with a
citation:

Lowd, D. and Domingos, P. "Naive Bayes Models for Probability Estimation".
To appear in ICML, 2005.  Bonn, Germany: ACM Press.

If you like, please also drop us a line about what you do with it and what
results you obtain.  See the LICENSE file for official license information.


II. INSTALLATION

To build the code on a UNIX-like system (e.g., Linux, Mac OS X, etc.),
you must first edit the Makefile.  Change the line:
    NBEDIR=../nbe
so that it references the directory in which you have compiled the NBE
code (from nbe.tar.gz).  This is absolutely necessary, because the Gibbs
sampling code uses some of those object files.

You must also have the expat library installed, so that it can be linked
using -lexpat.  (If you installed expat in an unusual location, you may have
to edit the Makefile.)  This is required for reading in WinMine model files.

Then run: make


III. USAGE

The program used for all of our query experiments is given in inftest.cpp.
Basic usage is as follows:
    ./inftest -[jm] <testfile> <condfile> -[gbn] [other parameters]

For the first flag, -j refers to multiple-variable queries, and -m refers to
single-variable queries.  These are sometimes referred to as joint and
marginal queries in the code, but that terminology is incorrect.  The
difference is that, with -j, we're testing the ability to predict any
configuration of the query variables.  With -m, we're testing the ability
to predict the configuration of each query variable *independent* of
the other query variables.  Thus, the -m queries are all single-variable,
even if there are multiple free variables.

For the second flag, -g refers to Gibbs sampling, -b refers to belief
propagation (only usable with -m), and -n refers to NBE inference.

The <testfile> consists of examples in NBE training format: space-delimited
attribute value indices, surrounded by parentheses.  For example:
    (2 1 0 0 3 2)
A question mark (?) indicates a missing value, over which we should
marginalize.  For example,
    (? 1 0 ? ? ?)
That last test example specifies that we're predicting (at most) the second
and third attributes, and marginalizing over the rest.

The <condfile> consists of examples in the same format, which function
as evidence.  For example, if the first test example is:
    (? 1 0 ? 3 ?)
And the first evidence example is:
    (? 1 ? ? ? ?)
Then the first query is either:
    P( 3rdAttrib=0, 5thAttrib=3 | 2ndAttrib=1)
        OR
    P( 3rdAttrib=0 | 2ndAttrib=1 ) * P( 5thAttrib=3 | 2ndAttrib=1 )

The former query corresponds to -j; the latter, to -m.  The actual
log likelihood that is reported by inftest is averaged over all
queries for -j, or all queries * query-variables for -m.
    
WARNING: the WinMine model files accepted by inftest do not correspond
to all WinMine model files.  This is a subset with very simply patterned
formatting.  The code to load WinMine model files is very brittle!



IV. SOURCE CODE

GibbsSampler.{h|cpp} contain the implementation of Gibbs sampling used
in our experiments.  We also include our implementation of belief propagation,
and the hooks we used for running NBE inference.

As mentioned before, references to "joint" versus "marginal" inference,
both in comments and in method names, may be misleading.  This actually
refers to the -j versus the -m option of inftest.