Variational Beta Linkage

Thomas M. Menino Convention & Exhibition Center 

Bipartite record linkage is the problem of merging two duplicate-free databases in the absence of unique identifiers. Bayesian approaches to this problem offer natural uncertainty quantification and transitivity of matching decisions. However, these approaches rely on Markov chain Monte Carlo (MCMC) for posterior inference, limiting their scalability to small sized databases. In this talk, we propose a variational approximation for a Bayesian bipartite record linkage model. We use hashing and a re-parameterization of the approximating variational distribution to derive a coordinate ascent algorithm with complexity that grows linearly with the number of records in the smaller database. Additionally, we derive a stochastic variational inference algorithm with complexity that is independent of the database sizes. Through a series of simulations and applications, we illustrate that the variational approximations attain comparable accuracy to MCMC based methods, at a significantly decreased computational cost. Specifically, after pre-processing, we are able to merge 400,000 records in under 5 minutes, and 40,000 records in under 5 seconds.

entity resolution

record linkage

variational inference

Bayesian methods 

Survey Research Methods Section