This message was created automatically by mail delivery software.

A message that you sent could not be delivered to one or more of its
recipients. This is a permanent error. The following address(es) failed:

  zhangl2@rpi.edu
    SMTP error from remote mailer after end of data:
    host mail.rpi.edu [128.113.2.6]: 554 5.7.1 Message rejected because of unacceptable content.  For help, please quote incident ID 45814655.

------ This is a copy of the message, including all the headers. ------

Return-path: <jorism@slartibartfast.azn.nl>
Received: from jorism by slartibartfast.azn.nl with local (Exim 4.50)
	id 1HOFzM-0001hZ-6Q
	for zhangl2@rpi.edu; Mon, 05 Mar 2007 17:24:40 +0100
Date: Mon, 5 Mar 2007 17:24:40 +0100
From: j.mooij@science.ru.nl
To: zl <zhangl2@rpi.edu>
Subject: Re: About libDAI package
Message-ID: <20070305162440.GB2600@mbfys.ru.nl>
References: <20070301104231.GC30076@mbfys.ru.nl> <DPEGLDAOPHHAJMHMNOINOEDHDBAA.zhangl2@rpi.edu>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <DPEGLDAOPHHAJMHMNOINOEDHDBAA.zhangl2@rpi.edu>
User-Agent: Mutt/1.5.9i

Hi Lei,

sorry for my late reply, your message got lost in my spam folder...

> Thank you very much for your kind responses. What you wrote was clear and in detail.
> I am familiar with C++ but I usually use windows system. Anyway, it is not 
> a big problem. I have not much difficulty with reading these C++ codes.
> The most difficulty thing is to understand how your packages are designed, 
> organized and how to use it.

Okay, fine. Discussing the design and organization of the whole thing
indeed needs to be done.

> I have some experience with Bayesian Network and Markov Random Fields.
> In MRF, it is possible to query the joint probability of multiple varibales. Is it 
> possible to do this in your Factor Graph? I am not sure about this. The function
> FactorGraph::ExactMarginal() seems to support querying a set of nodes.

The FactorGraph::ExactMarginal() function will probably be removed
in newer versions because it would be more logical to write an
ExactInference class that uses exhaustive summation to do exact
inference. I don't even remember why I wrote it, probably to quickly
test something.

Anyway, there is a better method to calculate exact joint probabilities
of multiple variables in the FactorGraph by using the
JTree::calcMarginal() method (which assumes that run() has been called
already; so to use this one, construct a JTree object, invoke init(),
invoke run() and then use calcMarginal(nodeset) to calculate the joint
marginal on the nodeset).

If you use approximate inference (e.g. BP), you can also calculate
approximate marginal distributions over subsets of nodes in the 
following way. For each joint configuration of the nodes in the
subset, run BP and calculate the log-partition sum of the factor
graph "clamped" to that particular joint configuration. This is 
already implemented in daialg.cpp:

  Factor calcMarginal( const InfAlg & obj, const VarSet & ns, bool reInit )

calculates the Marginal on some VarSet ns, using the InfAlg object obj.
So e.g., after you have constructed the bp object in the example
discussed last time, instead of doing init() and run(), you can invoke
calcMarginal( bp, bp.var(0) | bp.var(1) | bp.var(2), false ) to 
calculate the joint marginal on the variables with indices 0, 1 and 2
(note that the operator | is overloaded for VarSets and just adds
Vars to VarSets). This will result in an approximation to the exact
margnial distribution.

You can also do this using the jtree object instead. In that case,
you'll obtain the exact joint marginal distribution. In fact, this
should be the same result as that obtained by JTree::calcMarginal()
discussed above, although the latter method is faster but has 
received less testing by me. 

> Another question is about the pariwise belief. For example, in MRF with pairwise
> cliques, we can calculate the believes of a pairwise clique. In Factor Graph, I think
> the pairwise relationship becomes a factor node, right? Can I query the belief for a factor
> node? This may be important for parameter learning.

You are right, in factor graphs the pairwise relationship become factor
nodes. And you can query the belief for a factor node. In fact, the
belief( VarSet bla ) method (that each approximate inference method
should support) supplies this functionality. To elaborate on the example
that I discussed in the previous email: after having constructed the
bp object, invoking init() and run(), you can not only query the single
node beliefs by using

	for( size_t i = 0; i < fg.nrVars(); i++ )
		cout << bp.belief(fg.var(i)) << endl;

but also all the factor beliefs by using

	for( size_t I = 0; I < fg.nrFactors(); I++ )
		cout << bp.belief( fg.factor(I).vars() ) << endl;

(I often use capital I, J, K, ... for factor nodes and small i, j, k
for variable nodes by the way). This just iterates over all factor
nodes in the factor graph, and for each factor index I, it 
requests the BP belief on the variables corresponding to the I'th
factor.

The belief(VarSet &) method in general will return the approximate
marginal distribution on the VarSet (set of variables). It depends
on the particular inference algorithm whether or not that particular
VarSet is supported. BP supports single nodes and all factor nodes,
but beyond that, the only alternative is to use the calcMarginal()
routine discussed above.

> I tried to read the factorgraph.cpp file. But I cannot understand the
> purposes of few functions, e.g. FactorGraph::undoProb.

Yes, these are a bit vague. The idea is that in many situations, you
have some factor graph, then you want to clamp some variables or factors
(e.g. if you have new evidence) or more generally you may want to alter
just a few of all factors. Then you want to do some computation
(inference) on the altered factorgraph and finally you want to restore
the factor graph to its old state. Of course, you could make a temporary
copy of the whole FactorGraph object before changing some factors, but
this is not very efficient if you only change few factors. So saveProbs
can be used to save the contents of few factors and undoProbs restores
those factors. updatedFactor is also related to that.  You can see how
they are used in the implementatino of the calcMarginal function in
daialg.cpp (discussed above). 

> About the file format, do I only need to define the factors in .fg
> file in order to define a Factor Graph? That is, the random variable
> node and the factor node are defined in the same format, right? In
> addition, is the cluster file for defining the connection between
> factors? 

In fact, a factor graph can be specified as follows: for each factor,
write down which variables occur in the factor, what their respective
cardinalities (dimensions) are, and then a big table listing all the
values of that factor for all possible configurations of these
variables. In fact, the .fg format is not much more than that. It starts
with a line containing the number of factors in that graph, followed
by empty line. After that we one block for each factor, where the blocks
are seperated by empty lines.

Each block starts with a line containing the number of variables in that
factor. The second line contains the indices of these variables,
seperated by spaces (indices are nonnegative integers and to avoid 
confusion, it is suggested to start counting at 0). The third line
contains the number of possible values of each of these variables,
also seperated by spaces. Note that this is slightly redundant, since
if a variable appears in more factors, the possible number of values
of that variable appears several times in the .fg file, but this is
checked for consistency (I believe :)). Please do not try inconsistent
values :) The fourth line contains the number of non-zero entries in
the factor table. The rest of the lines contain these non-zero entries;
each entry consists of a table index, followed by white-space, followed
by the value of that table index. The most difficult part is getting
the indexing right. The convention used is that the left-most variables
cycle through their values the fastest. An example block describing one
factor is:

3
4 8 7
3 2 2
11
0 0.1
1 3.5
2 2.8
3 6.3
4 8.4
6 7.4
7 2.4
8 8.9
9 1.3
10 1.6
12 6.4
11 2.6

which corresponds to the following factor:

x_4 x_8 x_7 | value
 0   0   0  |  0.1
 1   0   0  |  3.5
 2   0   0  |  2.8
 0   1   0  |  6.3
 1   1   0  |  8.4
 2   1   0  |  0.0
 0   0   1  |  7.4
 1   0   1  |  2.4
 2   0   1  |  8.9
 0   1   1  |  1.3
 1   1   1  |  1.6
 2   1   1  |  2.6

Note that the value of x_4 goes fastest, followed by x_8 and x_7
varies the slowest; this corresponds to the second line of the block
("4 8 7"). Further, x_4 can take on three values, and x_8 and x_7
take on two values, as described in the third line of the block ("3 2
2"). The table contains 11 non-zero entries (all except for the fifth
entry). Note that the eleventh and twelveth entries are interchanged.
I hope this example is clear enough.

> About the belief propagation, is it Sum-Product BP or Max-Product BP?

It is Sum-Product BP. Modifications for Max-Product BP are almost
trivial.

> I really appreciate that you are providing such a package for the
> public use. And thank you for spending your time to answer my
> questions.

It would be nice if my package saves you (and other people) some work.
Your questions actually help writing the documentation, so the more
questions you'll ask, the more documentation will be written ;)

Kind regards,
Joris
