Abstract
Maximum Likelihood learning of graphical models is not possible in problems where inference is intractable. In such settings it is common to use approximate inference (e.g. Loopy BP) and maximize the so-called "surrogate" likelihood objective. We examine the effect of using different approximate inference methods and, therefore, different surrogate likelihoods, on the accuracy of parameter estimation. In particular, we consider methods that utilize a control parameter to trade computation for accuracy. We demonstrate empirically that cheaper, but worse quality approximate inference methods should be used in the small data setting as they exhibit smaller variance and are more robust to model mis-specification.