Distance-Preserving Probabilistic Embeddings with Side Information: Variational Bayesian Multidimensional Scaling Gaussian Process

Harold SohIJCAI 2016 · OpenReview

Abstract

Embeddings or vector representations of objects have been used with remarkable success in various machine learning and AI tasks—from dimensionality reduction and data visualization, to vision and natural language processing. In this work, we seek probabilistic embeddings that faithfully represent observed relationships between objects (e.g., physical distances, preferences). We derive a novel variational Bayesian variant of multidimensional scaling that (i) provides a posterior distribution over latent points without computationally-heavy Markov chain Monte Carlo (MCMC) sampling, and (ii) can leverage existing side information using sparse Gaussian processes (GPs) to learn a nonlinear mapping to the embedding. By partitioning entities, our method naturally handles incomplete side information from multiple domains. Furthermore, the derived approximate bounds can be used to discover the intrinsic dimensionality of the data and limit embedding complexity. We demonstrate the effectiveness of our methods empirically on synthetic problems and real-world tasks including political unfolding analysis and multi-sensor localization.

The Challenge of Traditional MDS

Multidimensional Scaling (MDS) is a cornerstone technique for visualizing high-dimensional data by embedding objects in a low-dimensional space while preserving their relative distances. However, traditional MDS implementations face three significant hurdles:

  1. Lack of Uncertainty: Most methods provide only point estimates, offering no measure of confidence in the resulting coordinates.
  2. Computational Inefficiency: Bayesian MDS variants typically rely on Markov Chain Monte Carlo (MCMC) sampling, which is prohibitively slow for large-scale datasets.
  3. Isolation from Side Information: Standard MDS cannot easily incorporate auxiliary features—such as text descriptions or metadata—to refine embeddings or generalize to unseen data points.

Methodology: VBMDS-GP

To address these limitations, we propose Variational Bayesian Multidimensional Scaling Gaussian Process (VBMDS-GP). The framework utilizes a Log-Normal Likelihood to better model distance data noise compared to standard Gaussian assumptions.

To achieve computational efficiency, we employ Variational Inference to derive an Evidence Lower Bound (ELBO), transforming the inference task into a fast optimization problem. A second-order Taylor approximation is used to handle the non-conjugate log-normal likelihood efficiently.

Figure 1: Synthetic lattice analysis demonstrating how the variational lower bound (bottom right) can be used to identify the intrinsic dimensionality of the data.

The "secret sauce" of our approach is the integration of Sparse Gaussian Processes (GPs). By using GPs to learn a non-linear mapping from an object's side information to its embedding location, the model can perform "out-of-sample" projections. This allows for the placement of new objects into the embedding space without retraining the entire model.

Key Results and Applications

Political Unfolding Analysis

We applied VBMDS-GP to US Election data (1968 and 2004), using voter preferences as distances and Wikipedia entries as side information. The model successfully recovered the liberal-conservative ideological spectrum. Notably, VBMDS-GP achieved results visually indistinguishable from MCMC but was 22 times faster (e.g., ~4 minutes vs. over 70 minutes for the 2004 dataset).

Figure 2: Political candidate embeddings for 1968 and 2004. The accompanying table demonstrates that VBMDS provides a massive speedup over MCMC with comparable k-NN error.

Multi-sensor Localization

In the Cricket sensor dataset, which involves ultrasonic range readings, VBMDS-GP reduced localization error to 3.1 cm. This represents a near-doubling of precision compared to previous state-of-the-art methods, which typically achieved errors around 6.6 cm. The model's ability to provide uncertainty estimates is particularly valuable here, as it indicates how much to trust specific coordinate predictions.

Conclusion

VBMDS-GP provides a robust, scalable framework for distance-preserving embeddings. By combining the speed of variational inference with the flexibility of Gaussian Processes, it solves the "cold-start" problem for new data points and provides automatic complexity control via the variational lower bound. Future work will explore different likelihood functions for non-physical distance domains and alternative GP kernels to further enhance out-of-sample accuracy.

Summary updated

Abstract

Embeddings or vector representations of objects have been used with remarkable success in various machine learning and AI tasks--from dimensionality reduction and data visualization, to vision and natural language processing. In this work, we seek probabilistic embeddings that faithfully represent observed relationships between objects (e.g., physical distances, preferences). We derive a novel variational Bayesian variant of multidimensional scaling that (i) provides a posterior distribution over latent points without computationally-heavy Markov chain Monte Carlo (MCMC) sampling, and (ii) can leverage existing side information using sparse Gaussian processes (GPs) to learn a nonlinear mapping to the embedding. By partitioning entities, our method naturally handles incomplete side information from multiple domains, e.g., in product recommendation where ratings are available, but not all users and items have associated profiles. Furthermore, the derived approximate bounds can be used to discover the intrinsic dimensionality of the data and limit embedding complexity. We demonstrate the effectiveness of our methods empirically on three synthetic problems and on the real-world tasks of political unfolding analysis and multi-sensor localization.
BibTeX
@inproceedings{soh2016distance,
  author = {Harold Soh},
  title = {{Distance-Preserving Probabilistic Embeddings with Side Information: Variational Bayesian Multidimensional Scaling Gaussian Process}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=B1bSW4z_-S},
}
Figure