This paper presents a novel practical framework for Bayesian model averaging and model selection in probabilistic graphical models. Our approach approximates full posterior distributions over model parameters and structures, as well as latent variables, in an analyt(cid:173) ical manner. These posteriors fall out of a free-form optimization procedure, which naturally incorporates conjugate priors. Unlike in large sample approximations, the posteriors are generally non(cid:173) Gaussian and no Hessian needs to be computed. Predictive quanti(cid:173) ties are obtained analytically. The resulting algorithm generalizes the standard Expectation Maximization algorithm, and its conver(cid:173) gence is guaranteed. We demonstrate that this approach can be applied to a large class of models in several domains, including mixture models and source separation.