TL;DR
This paper introduces "conditional Multidimensional Scaling" (conditional MDS), a novel dimension reduction technique that leverages known features to improve the discovery of unknown features in high-dimensional data. By explicitly accounting for prior knowledge, conditional MDS enhances visualization and simplifies the knowledge discovery process, outperforming traditional methods in various real-world examples.
What Problem Does This Paper Address?
Mapping high-dimensional data to a lower-dimensional space is crucial for understanding complex datasets in science and engineering. Traditional dimension reduction methods often treat all features as unknown, which can lead to suboptimal results. Specifically, they might fail to fully utilize available information, potentially masking important underlying patterns or requiring practitioners to discover all features simultaneously. This is particularly problematic when some features are already known or easily measurable, but their influence on the data's structure is not explicitly modeled. The paper addresses the challenge of incorporating this "prior information" to achieve more accurate and interpretable low-dimensional representations.
Methods
The core contribution is the conditional Multidimensional Scaling (MDS) framework. This method extends traditional MDS by explicitly incorporating known features. The key idea is to model the pairwise dissimilarities between data points not only based on unknown features but also on known features.
- Conditional Stress Function: A new objective function, "conditional stress," is defined. It aims to minimize the discrepancy between observed dissimilarities and those predicted by a model that includes both unknown (represented by coordinates $U$) and known features (represented by an affine transformation $B^T v$).
- Conditional SMACOF Algorithm: An optimization algorithm, "conditional SMACOF," is developed to solve the conditional stress minimization problem. This algorithm is an adaptation of the SMACOF algorithm for metric MDS, utilizing a majorization technique to ensure convergence.
- Incorporating Known Features: The known features ($v$) are incorporated through an affine transformation ($B^T v$), allowing the model to learn how these known features influence the pairwise distances. The learned matrix $B$ quantifies this influence.
Datasets
The paper evaluates conditional MDS on several real-world and simulated datasets:
- Kinship Terms: A dataset of 14 kinship terms used to demonstrate how conditional MDS can reveal hierarchical relationships (Kinship Degree, Generation) by marginalizing out known features like Gender.
- Facial Expressions: Data from a study on 13 facial expressions, where known features (Schlosberg scales like Pleasant-Unpleasant) are used to improve the estimation of unknown features.
- Textile Fabrics: Images of textile fabrics with underlying features like texture, rotation, and contractions. The study uses both Kullback-Leibler (KL) dissimilarity and Euclidean distance (ED) measures.
- Car-Brand Perception: Simulated data for 30 car brands, based on seven features and their weights from a consumer survey. This dataset is used to test the robustness of conditional MDS with varying numbers of known and irrelevant features.
- Cylinder Machining: Surface measurements of 90 cylinders machined with different lathe-turning parameters. This example uses the turning speed and cutting depth as known features to uncover unknown factors contributing to surface variation.
Key Insights and Ideas
- Marginalizing Out Knowns: Conditional MDS effectively "marginalizes out" the influence of known features, allowing the underlying structure related to unknown features to be more clearly revealed. This is crucial for avoiding the "masking problem" where known features can obscure patterns related to unknown ones.
- Iterative Knowledge Discovery: The framework supports a sequential knowledge discovery process. Discovered unknown features can be incorporated as known features in subsequent analyses, leading to the identification of progressively deeper levels of structure.
- Improved Estimation Quality: By leveraging prior information, conditional MDS achieves higher accuracy in estimating the low-dimensional representation compared to traditional methods that treat all features as unknown.
- Interpretability of $B$: The learned matrix $B$ provides insights into how known features contribute to the pairwise dissimilarities, offering a way to understand the relationship between known and unknown features.
- Robustness to Irrelevant Features: The method demonstrates robustness even when irrelevant features are included in the set of known features, maintaining good performance in learning the effects of truly relevant known features.
Key Results
- Kinship Terms: Conditional MDS successfully identified "Kinship Degree" and "Generation" features, which were not clearly discernible with standard metric MDS when Gender was the only known feature.
- Facial Expressions: Conditional MDS significantly improved the estimation accuracy (measured by Average Canonical Correlation - ACC) compared to metric MDS across various scenarios of known features, with improvements up to 0.23 in ACC.
- Textile Fabrics: Using KL dissimilarity, conditional MDS achieved near-perfect canonical correlations (0.99) between its learned dimensions and the true underlying features, vastly outperforming metric MDS (0.66) and other methods.
- Car-Brand Perception: Conditional MDS consistently achieved higher ACCs than metric MDS, ISOMAP, t-SNE, and UMAP, especially as the number of known features increased. The method also showed good accuracy in estimating the influence matrix $B$ even with irrelevant features.
- Cylinder Machining: Conditional MDS identified a third unknown feature (cylinder rotation) in addition to the two known lathe-turning parameters, revealing more nuanced variations in the machining process.
- Computational Efficiency: While not as fast as UMAP in some cases, conditional MDS offers comparable or better performance than SMACOF and ISOMAP, with its computational complexity being similar to conventional SMACOF.
Limitations and Future Work
- Interpretation of Unknown Features: Conditional MDS helps expose unknown features but does not directly solve the challenge of interpreting their meaning. Future work could explore methods that enhance the interpretation of these discovered features.
- Scalability: The time complexity of conditional MDS does not scale as well with the number of data points ($N$) as some other methods. The authors suggest exploring stochastic gradient-based optimization with $O(N)$ complexity as a potential direction to address this limitation.
- Broader Applications: The authors propose extending conditional MDS to other application contexts, such as precipitation forecasting and handling missing data, where pairwise dissimilarities can be derived or are naturally present.
Summary updated