A Hybrid Approach for Probabilistic Inference using Random Projections

We introduce a new meta-algorithm for proba-bilistic inference in graphical models based on random projections. The key idea is to use ap-proximate inference algorithms for an (exponen-tially) large number of samples, obtained by ran-domly projecting the original statistical model using universal hash functions. In the case where the approximate inference algorithm is a variational approximation, this approach can be viewed as interpolating between sampling-based and variational techniques. The number of sam-ples used controls the trade-off between the accu-racy of the approximate inference algorithm and the variance of the estimator. We show empiri-cally that by using random projections, we can improve the accuracy of common approximate inference algorithms