A tighter bound for graphical models M.A.R. Leisink.pdf

A tighter bound for graphical modelsM.A.R. Leisink and H.J. KappenyDepartment of BiophysicsUniversity of Nijmegen, Geert Grooteplein 21NL 6525 EZ Nijmegen, The Netherlandsfmartijn,bertg@mbfys.kun.nlAbstractWe present a method to bound the partition function of a Boltz-mannmachine neural network with any odd order polynomial. Thisis a direct extension of the mean eld bound, which is rst order.We show that the third order bound is strictly better than meaneld. Additionally we show the rough outline how this bound isapplicable to sigmoid belief networks. Numerical experiments in-dicate that an error reduction of a factor two is easily reached inthe region where expansion based approximations are useful.1 IntroductionGraphical models have the capability to model a large class of probability distri-butions. The neurons in these networks are the random variables, whereas theconnections between them model the causal dependencies. Usually, some of thenodes have a direct relation with the random variables in the problem and arecalled `visibles. The other nodes, known as `hiddens, are used to model morecomplex probability distributions.Learning in graphical models can be done as long as the likelihood that the visiblescorrespond to a pattern in the data set, can be computed. In general the time ittakes, scales exponentially with the number of hidden neurons. For such architec-tures one has no other choice than using an approximation for the likelihood.A well known approximation technique from statistical mechanics, called Gibbssampling, was applied to graphical models in [1]. More recently, the mean eldapproximation known from physics was derived for sigmoid belief networks [2]. Forthis type of graphical models the parental dependency of a neuron is modelled by anon-linear (sigmoidal) function of the weighted parent states [3]. It turns out thatthe mean eld approximation has the nice feature that it bounds the likelihoodfrom below. This is useful for learning, since a m