Efficient Model Evidence Computation in Tree-structured Factor Graphs

Model evidence is a fundamental performance measure in Bayesian machine learning as it represents how well a model fits an observed data set. Since model evidence is often an intractable quantity, the literature often resorts to computing instead the Bethe Free Energy (BFE), which for cyclefree models is a tractable upper bound on the (negative log-) model evidence. In this paper, we propose a different and faster evidence computation approach by tracking local normalization constants of sum-product messages, termed scale factors. We tabulate scale factor update rules for various elementary factor nodes and by experimental validation we verify the correctness of these update rules for models involving both discrete and continuous variables. We show how tracking scale factors leads to performance improvements compared to the traditional BFE computation approach.