Gordon,
>From our (perhaps limited) experience with Gibbs sampling, in practice
it often exhibits very poor perfomance as a function of time (namely
as an anytime algorithm). Convergence takes too long and is
unpredictale.
And, if one can effort to spend huge amounts of times to get
convergence,
it seems better to spend that time on running the exact algorithm,
instead.
I wonder if there are any empirical studies of
Gibbs sampling. I understand that in practice enhancement such as
likelihood weighting seems to be far better.
----Rina.
Gordon Hazen wrote:
>
> Marek or anyone:
>
> The statement that
>
> > > I have seen some people comparing approximation reults to each other
> > > (comparing to Gibbs sampling for instance) however such comparisons are
> > > meaningless, I think.
>
> surprised me a little. I haven't actually tried to use Gibbs sampling or
> MC Monti Carlo, but aren't these algorithms known to converge to the
> correct posteriors? MC Monti Carlo would have been my suggestion to help
> evaluate the quality of approximation algorithms on large Bayes nets. Are
> there difficulties I'm not aware of? I know that the convergence proof for
> MC Monti Carlo is compromised by too many zero conditional probabilities -
> is this the problem?
>
> Thanks,
>
> Gordon Hazen
>
> At 11:32 AM 5/8/01 -0700, Marek J. Druzdzel wrote:
> >- --On Monday, May 07, 2001, 11:56 AM -0700 Rina Dechter
> ><[EMAIL PROTECTED]> wrote:
> >
> > > The question of evaluating the quality of an approximation to
> > > probabilistic inference is really a very important one and a difficult
> > > one, with which we also struggle with in Irvine.
> > >
> > > Sometimes it is possible to generate by an approximation an upper and
> > > lower bounds of the exact probability which can bound provide some
> > > estimate of the accuracy.
> > > However, such methods are often very inaccurate.
> > > Therefore one produces arbitrary approximations (no guarantees).
> > > In that case, I dont see any other way but to test your approximation
> > > algorithm on relatively small or moderate networks and compare against
> > > the exact figure (computed by an exact algorithm) with the
> > > hope that the information gained from such comparison scales up.
> > > You can then try too show superiority relative to other
> > > competing approximation algorithms.
> >
> >I agree with Rina here. I suggest that you find some networks that are
> >large or complex enough for your algorithm to be challenging and yet
> >solvable using exact methods. This is the approach that my doctoral
> >student, Jian Cheng, and I followed when testing stochastic sampling
> >algorithms (e.g., http://www.jair.org/abstracts/cheng00a.html). Unless you
> >have a good theory for putting bounds on your posteriors (we have a
> >forthcoming UAI paper along these lines; still we test this approach by
> >comparing the results to exact answers!), only when you have exact answers
> >can you saying anything meaningful about your approximate results.
> >
> > > I have seen some people comparing approximation reults to each other
> > > (comparing to Gibbs sampling for instance) however such comparisons are
> > > meaningless, I think.
> >
> >I agree here.
> >
> >Marek
> >--------------------------------------------------------------------------
> >Marek J. Druzdzel http://www.pitt.edu/~druzdzel
> >
>
> Gordon Hazen
> IE/MS Department, McCormick School of Engineering and Applied Science
> Northwestern University, Evanston, IL. USA 60208-3119
> Phone 847-491-5673 Fax 847-491-8005
> Web: www.iems.nwu.edu/~hazen/
--
-----------------------------------------------------------------------------
Rina Dechter [EMAIL PROTECTED]
Information and Computer Science Dept. (949) 824-6556
University of California, Irvine fax: (949)-824-4056
Irvine, CA 92717
http://www.ics.uci.edu/~dechter
