Generalized Bayesian Multidimensional Scaling and Model Comparison

1. Problem Statement

Multidimensional Scaling (MDS) is a fundamental technique for dimension reduction, representing objects as points in a low-dimensional space based on pairwise dissimilarities. While classical (non-Bayesian) MDS methods are computationally efficient, they suffer from three critical limitations:

1. Lack of Uncertainty Quantification: They provide only point estimates, ignoring model uncertainty and noise.
2. Rigid Assumptions: Existing Bayesian MDS (BMDS) methods typically assume Euclidean distances and Gaussian noise. This limits their applicability to domains like text mining (where Cosine distance is preferred) or data with heavy-tailed/skewed errors and outliers.
3. Computational Inefficiency in Model Comparison: Traditional Bayesian inference relies on Markov Chain Monte Carlo (MCMC), which struggles with multimodal posterior landscapes in MDS and makes estimating marginal likelihoods (required for rigorous model comparison via Bayes factors) computationally expensive and prone to bias.

The authors aim to develop a framework that accommodates flexible dissimilarity metrics, robust non-Gaussian error structures, and efficient inference for large-scale datasets.

2. Methodology

The paper proposes the Generalized Bayesian Multidimensional Scaling (GBMDS) framework coupled with an Adaptive Annealed Sequential Monte Carlo (ASMC) algorithm.

A. The GBMDS Framework

The framework generalizes the standard BMDS model (Oh and Raftery, 2001) by relaxing distributional assumptions:

• Dissimilarity Metrics: Instead of restricting to Euclidean distance, GBMDS supports a broad class of metrics, including Cosine distance (for text data) and Jaccard distance (for set-based data).
• Error Structures: The model replaces the standard Gaussian noise assumption with flexible distributions to handle outliers and skewness:
  • Truncated Skewed Gaussian ($M_{TSN}$): Models asymmetric errors using a shape parameter $\psi$.
  • Truncated Student's t-distribution ($M_{TT}$): Models heavy-tailed errors using a scale mixture of Gaussians, providing robustness against outliers.
• Likelihood Formulation: The likelihood is defined based on the chosen metric $D$ and distribution $g$, incorporating truncation to ensure dissimilarities remain positive.

B. Adaptive Annealed Sequential Monte Carlo (ASMC)

To perform inference and model comparison efficiently, the authors design an ASMC algorithm:

• Annealing Schedule: The algorithm transitions from an easy-to-sample reference distribution (prior or CMDS solution) to the complex target posterior distribution via a sequence of intermediate distributions controlled by annealing parameters $\tau_r$.
• Adaptive Mechanism:
  • Adaptive Annealing: The step size of the annealing parameter $\tau_r$ is dynamically adjusted to maintain a target Relative Conditional Effective Sample Size (rCESS), ensuring smooth transitions between distributions and preventing particle degeneracy.
  • Adaptive Inference (Batch Processing): The algorithm supports incremental learning. When new data arrives, it uses the posterior samples from previous batches to initialize particles for existing objects, while using priors for new objects. This allows for real-time updates without re-computing from scratch.
• Marginal Likelihood Estimation: Unlike MCMC, ASMC naturally produces unbiased (or nearly unbiased) estimators of the marginal likelihood as a byproduct of the sequential sampling process. This enables the direct calculation of Bayes Factors for rigorous model selection.

C. Model Comparison and Identifiability

• Model Selection: The framework compares competing models (e.g., $M_{TSN}$ vs. $M_{TT}$, Euclidean vs. Cosine, different dimensions $p$) using Bayes Factors derived from the estimated marginal likelihoods.
• Identifiability: To address the rotational and translational invariance inherent in MDS, the authors apply Procrustes transformations to align posterior samples to a reference configuration, allowing for the construction of credible regions (uncertainty ellipses).

3. Key Contributions

1. Generalized Framework: Introduced GBMDS, which extends BMDS to handle non-Euclidean metrics (Cosine, Jaccard) and non-Gaussian errors (Skewed Gaussian, Student's t).
2. Efficient Inference Algorithm: Developed an ASMC algorithm that leverages existing Metropolis-Hastings proposals, reducing implementation complexity while handling high-dimensional latent spaces and multimodal posteriors more effectively than standard MCMC.
3. Rigorous Model Comparison: Provided a computationally feasible method to estimate marginal likelihoods, enabling the use of Bayes Factors for selecting optimal dissimilarity metrics, error distributions, and latent dimensions.
4. Adaptive/Incremental Learning: Designed a mechanism for sequential data updates, making the method suitable for streaming data and large-scale applications where batch processing is infeasible.
5. Robustness: Demonstrated superior performance in the presence of skewed errors and outliers compared to classical and standard Bayesian methods.

4. Results

The authors evaluated the framework through three simulation studies and four real-world applications:

• Simulation 1 (Known Dimension): Confirmed that the ASMC algorithm correctly identifies the true underlying dimension and that the model with the correct error distribution yields the highest marginal likelihood.
• Simulation 2 (Skewed Errors): In datasets with skewed noise, the $M_{TSN}$ model significantly outperformed the standard Gaussian model in terms of log marginal likelihood. The ASMC algorithm demonstrated comparable or faster runtimes than MCMC, even with complex models.
• Simulation 3 (Outliers): In datasets with 5% and 15% outliers, the $M_{TT}$ (Student's t) model showed superior robustness and lower variance in estimates compared to Gaussian-based models.
• Real-World Applications:
  • NIH Text Data: Successfully applied Cosine distance to 1,471 grant abstracts. The model identified an optimal dimension ($p=9$) and showed that Cosine-based models outperformed Euclidean ones in lower dimensions.
  • Journal Abstract Clustering: Used Jaccard distance to cluster 139 abstracts from three journals. The method achieved 100% classification accuracy and clearly separated the journals in the low-dimensional space.
  • NeurIPS Incremental Update: Demonstrated that the adaptive ASMC algorithm reduced computation time by 24–31% when updating with new data compared to re-running on the full dataset, with negligible loss in accuracy (STRESS values).
  • US City Geographical Data: Showed that GBMDS provided lower STRESS values than classical MDS (CMDS) and successfully visualized uncertainty (credible regions), which tightened as the signal-to-noise ratio increased.

5. Significance

This work bridges the gap between the flexibility of Bayesian modeling and the scalability required for modern data science.

• Practical Impact: It provides a unified framework for analyzing diverse data types (text, sets, geometric shapes) that were previously difficult to model with standard MDS.
• Statistical Rigor: By enabling the calculation of marginal likelihoods, it moves MDS from a purely exploratory visualization tool to a framework capable of principled statistical inference and model selection.
• Scalability: The adaptive ASMC approach addresses the "curse of dimensionality" and computational bottlenecks of MCMC, making Bayesian MDS viable for large and streaming datasets.
• Open Source: The authors provide an R package (GBMDS) integrating R and C++, facilitating reproducibility and adoption in the statistical community.

In conclusion, the paper presents a robust, flexible, and computationally efficient solution for multidimensional scaling that explicitly quantifies uncertainty and adapts to the specific characteristics of complex, real-world data.