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 > > ><[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 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/
