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:
- Lack of Uncertainty: Most methods provide only point estimates, offering no measure of confidence in the resulting coordinates.
- Computational Inefficiency: Bayesian MDS variants typically rely on Markov Chain Monte Carlo (MCMC) sampling, which is prohibitively slow for large-scale datasets.
- 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.
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).
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