| Markov chain Monte Carlo(MCMC) methods have been widely applied to problems in approximate counting and combinatorial optimization. They provide approximate solutions by estimating the expectations of various functions with some distribution. MCMC methods can be used to solve some complex computation problems in machine learning, such as sampling from the posterior distribution in Bayesian learning and dot products with an exponential number of terms. A specific application, Learning DNF with Winnow, will be used to demonstrate how to use MCMC methods. |