Abstract
This paper describes a Markov Chain Monte Carlo method for token matching. We commence by constructing a graphical model in which the roles of token correspondence and token alignment are made explicit. According to this model, the Markov Chain represents the conditional dependencies between the alignment parameters and the correspondence assignments. Through a process of Monte-Carlo sampling, we recover both alignment parameters and correspondence assignments to maximize the joint data likelihood. An important feature of our method is the way in which the alignment parameter distribution is sampled. We do this by selecting k-tuples of tokens. The size of the k-tuples is sufficient to determine the alignment parameters when token correspondence is known. In this way, we generate the alignment parameter distribution, which can be sampled by MCMC.