RE: [UAI] how to evaluate approximate algorithms when exact solution is not available?

[SKAANNING,CLAUS (HP-Denmark,ex1)]

The complexity of MCMC methods is linear in the number of
variables.  This is a well-known proven result.  Some
good references would be:

Besag, J. (2000).  Markov chain Monte Carlo for statistical inference.
University of Washington, Seattle, USA.  URL:
http://citeseer.nj.nec.com/besag00markov.html.

Geyer, C.J. (1992).  Practical Markov chain Monte Carlo.
Statistical Science, v. 7, no. 4, pp. 473-511.

Gilks, W.R., Richardson, S. and Spiegelhalter, D.J. (eds) (1996).
Markov chain Monte Carlo in practice.  Chapman & Hall, London, UK.

However, convergence of an MCMC method can rarely be proven
when applied to large, complex Bayesian networks.

To prove convergence, it is necessary to establish irreducibility
of the Markov chain which means that it must be possible to reach
any configuration from any other configuration.  This is very
hard to show for the single-site Gibbs sampler, for instance, where
only one variable is changed at a time.  It becomes slightly easier
to handle for a blocked Gibbs sampler, where many variables can
be changed in a single update.

There is no general method for showing irreducibility, which
makes it impossible to know whether an MCMC method converges on
a given Bayesian network.  I suspect that it is NP hard to do
this, but as far as I know it hasn't been proven or disproven
yet.

There are cases where irreducibility is trivially fulfilled,
e.g., when all prior and conditional probabilities are non-zero.
This is called the positivity condition.

Best regards,
Claus



> -----Original Message-----
> From: Gordon Hazen [mailto:[EMAIL PROTECTED]]
> Sent: Tuesday, May 15, 2001 6:13 AM
> To: [EMAIL PROTECTED]
> Subject: Re: [UAI] how to evaluate approximate algorithms when exact
> solution is not available?
> 
> 
> Bob, Rina:
> 
> I was speaking off the cuff - I don't immediately have any 
> references to 
> give, so until I do, I can't back up my linearity assertions. 
>  I'll let you 
> know if I come across anything.
> 
> Gordon
> 
> At 10:20 PM 5/13/01 -0700, Rina Dechter wrote:
> 
> >Gordon,
> >
> >If you have referenice to this theoretical results or experiments
> >it can be very useful.
> >Thanks,
> >------Rina.
> >
> >Gordon Hazen wrote:
> > >
> > > I don't  think so - MC Monte Carlo and Monte Carlo in 
> general provide only
> > > a statistical approximation whose convergence is 
> guaranteed, but no
> > > guaranteed bound.  What I think is true is that 
> convergence to within a
> > > given confidence range is linear in problem size, but of 
> course a 95%
> > > confidence bound is only an estimate, not a guarantee.
> > >
> > > -- Gordon
> > >
> > > At 07:22 PM 5/12/01 -0700, Bob Welch wrote:
> > > >Gordon:
> > > >
> > > >If that were true then wouldn't there be a counter 
> example to the NP hard
> > > >results for both exact and approximate solutions?
> > > >
> > > >Bob
> > > >----- Original Message -----
> > > >From: "Gordon Hazen" <[EMAIL PROTECTED]>
> > > >To: <[EMAIL PROTECTED]>
> > > >Sent: Friday, May 11, 2001 7:49 PM
> > > >Subject: Re: [UAI] how to evaluate approximate 
> algorithms when exact
> > > >solution is not available?
> > > >
> > > >
> > > > > 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
> > > > >
> > >
> > > 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/
> 

------- End of Forwarded Message