Bayesian object matching

Arto KlamiMachine Learning 2013 · DOI

Abstract

This paper presents a Bayesian framework for cross-domain object matching (CDOM), the task of finding correspondences between two datasets without shared features or distance metrics. By incorporating a permutation parameter into a Bayesian Canonical Correlation Analysis (BCCA) model, the proposed method enables full posterior inference. Experimental results across artificial, image, metabolic, and cross-lingual datasets demonstrate that this approach significantly outperforms traditional maximum-likelihood and kernel-based methods, particularly in handling uncertainty and high-dimensional feature spaces.

Introduction

Cross-Domain Object Matching (CDOM) involves pairing observations from two distinct datasets that describe the same set of entities but lack a common feature space or pre-defined distance measure. For instance, matching physical athlete measurements with their performance statistics when identifiers are missing. While classical approaches like the Hungarian algorithm solve linear assignment problems given a cost matrix, CDOM requires learning the relationship between feature spaces simultaneously with the matching.

Existing solutions often rely on maximizing statistical dependency or Maximum Likelihood Estimation (MLE). However, MLE is prone to overfitting and fails to account for the uncertainty inherent in the matching process. This work addresses these gaps by proposing a Bayesian approach that explores the entire posterior distribution of possible matches, providing a more robust solution than point-estimate methods.

Methods

The proposed framework extends Bayesian Canonical Correlation Analysis (BCCA) by introducing a hidden permutation matrix $\pi$ that reorders one dataset to maximize its correlation with the other. The model assumes that both datasets are generated from a shared latent space.

Graphical model and matrix representation of the BCCA with a latent permutation matrix.

As exact inference over $N!$ possible permutations is computationally intractable, two approximation strategies are developed:

  1. Gibbs Sampling ("Gibbs-hard"): A sampling-based approach using an approximate Metropolis-Hastings step to update the permutation matrix by selecting the most likely pairings iteratively.
  2. Variational Bayes (VB): An optimization-based approach that approximates the posterior. Variants like VB-numInt use numerical integration to better capture dependencies between the matching and latent variables.

To handle the non-convex nature of the problem, a "consensus" initialization strategy is employed, where the model is run multiple times from random starts to find a stable initial configuration.

Key Insights and Results

A significant finding is the "dimensionality flip": Gibbs sampling proves superior in high-dimensional spaces where the posterior is highly peaked, whereas Variational Bayes performs better in low-dimensional, noisier settings due to its inherent regularization.

The Bayesian treatment of CCA parameters allows the model to maintain uncertainty about feature relationships, preventing premature convergence to incorrect correspondences. Furthermore, the model provides "soft assignments," offering a probability for each pairing rather than a simple binary decision.

Experimental Performance

  • Image Matching: In a task pairing halves of 320 images (2,400 features), the "Gibbs-hard" method correctly matched 275 pairs, significantly exceeding the previous state-of-the-art (206 matches).
  • Document Alignment: For difficult cross-lingual pairs like English-Finnish, the Bayesian Gibbs-hard method achieved 100% accuracy, compared to ~30% for prior methods.
  • Metabolite Matching: The framework successfully aligned metabolic profiles across different populations, demonstrating its utility in low-dimensional time-series data.

Conclusion

The Bayesian object matching framework offers a powerful alternative to traditional MLE and kernel methods by treating alignment as a latent variable within a generative model. While the approach is computationally intensive due to the requirement of solving a Linear Assignment Problem in each iteration, its accuracy and ability to quantify uncertainty make it highly effective for datasets in the hundreds to low thousands of samples. Future work will focus on improving scalability and reducing sensitivity to initialization.

Summary updated

BibTeX
@article{klami2013bayesian,
  author = {Arto Klami},
  title = {{Bayesian object matching}},
  journal = {Machine Learning},
  year = {2013},
  doi = {10.1007/s10994-013-5357-4},
}
Figure