Empirical studies would be interesting. Why not run an exact algorithm if
one has huge amounts of time available? Because, as I understand it,
peformance for Gibbs is linear in problem size, whereas performance for an
exact algorithm is exponential in problem size.
-- Gordon
At 10:27 AM 5/10/01 -0700, Rina Dechter wrote:
>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
> > ><dechter@ics.uci.edu> 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 dechter@ics.uci.edu
>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
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/
This archive was generated by hypermail 2b29 : Fri May 11 2001 - 18:54:47 PDT