Reconstructing Big Semantic Similarity Networks

Ai He, Shefali Sharma, Chun-Nan HsuEMNLP 2013

TL;DR

This paper introduces a novel, scalable algorithm for learning distance metrics in high-dimensional semantic similarity networks. By combining random projection for dimensionality reduction with a new objective function that regularizes intra-class and inter-class distances, the authors achieve state-of-the-art performance on challenging real-world datasets, overcoming the memory and computational limitations of previous methods.

What Problem Does This Paper Address?

In many fields, like Natural Language Processing (NLP) and Information Retrieval (IR), representing data points (e.g., documents, articles) with high-dimensional feature vectors is crucial for capturing nuanced semantic similarity. However, learning a distance metric that accurately reflects these similarities becomes computationally intractable when dealing with "big data" – datasets with thousands of features and potentially millions of data points. Traditional methods for learning distance metrics, particularly Mahalanobis distance, struggle with memory constraints and can be prone to local optima when applied to such large-scale, high-dimensional problems. Furthermore, existing approaches often don't effectively handle datasets with a large number of distinct classes, which is common in real-world scenarios. This paper aims to bridge this gap by developing a distance metric learning algorithm that is both scalable and robust for these challenging "big semantic similarity network" problems.

Methods

The core of the paper's contribution lies in two key innovations:

  • Random Projection for Dimensionality Reduction: To combat the curse of dimensionality, the authors employ random projection. Unlike Principal Component Analysis (PCA), which can lose significant information, random projection maps high-dimensional data to a lower-dimensional space while preserving pairwise distances with high probability. This significantly reduces the number of parameters to learn. The metric matrix $M$ is then factored into $L^T R L$, where $L$ is a random projection matrix and $R$ is a learned low-dimensional metric matrix. This approach is shown to be more robust than low-rank approximations and outperforms PCA.
  • New Objective Function with Regularization: The authors propose a new objective function that incorporates novel regularization terms. These terms explicitly encourage data points within the same class to be close (intra-class regularization) and data points from different classes to be far apart (inter-class regularization). This is a departure from previous methods that primarily focused on pairwise constraints or hinge loss. They found that minimizing intra-class distances was more critical for performance than maximizing inter-class distances. The overall objective function is designed to be convex and efficiently optimized using a stochastic-batch subgradient descent method, similar to the PEGASOS algorithm.

Datasets

The paper evaluates its approach on two distinct real-world datasets:

  • Wikipedia Articles: This dataset, sourced from previous work, involves predicting semantic distances between Wikipedia documents related to "Search Engine" and "Philosophy Concept." It's characterized by moderately high dimensions (thousands of features) and a moderate number of data points.
  • Phenotype Similarity: This dataset, from a project focused on matching semantically related phenotype variables across genome-wide association studies (GWAS), presents a more challenging scenario. It involves extremely high dimensionality (nearly 19,000 features) and a large number of data points (over 3,700 phenotypes categorized into 160 classes). This dataset is particularly notable for its large number of classes, a challenge that previous metric learning methods often struggle with.

Key Insights and Ideas

  • Random Projection as a Scalable Alternative: The paper convincingly demonstrates that random projection is a powerful and effective technique for handling high-dimensional data in metric learning, outperforming traditional methods like PCA and offering more stability than low-rank approximations.
  • The Importance of Intra-Class Regularization: The authors highlight that explicitly encouraging intra-class compactness is crucial for learning effective distance metrics, especially in scenarios with many distinct classes. This insight helps to better cluster similar data points.
  • Convexity and Scalability: By formulating the problem with a convex objective function and employing stochastic subgradient descent, the algorithm achieves scalability, allowing it to process large datasets that were previously intractable.
  • Robustness Across Domains: The algorithm's success on both document similarity and phenotype matching tasks suggests its generalizability to diverse high-dimensional semantic similarity problems.

Key Results

The proposed algorithm, particularly configuration G (combining random projection with intra-class regularization), consistently outperformed competing methods on both datasets.

  • Wikipedia Articles: Algorithm G achieved the highest Area Under the Curve (AUC) scores (0.7909 for "Search Engine" and 0.7264 for "Philosophy Concept"), indicating superior ranking of semantic distances.
  • Phenotype Similarity: Algorithm G also led in performance on this challenging dataset, with average AUC scores of 0.9433. This is particularly impressive given the high dimensionality and large number of classes.
  • Scalability: The paper notes that learning a full-rank Mahalanobis matrix ($M$) was impossible due to memory limitations, whereas their approach, by reducing dimensionality, was feasible.

Limitations and Future Work

  • Unstable Low-Rank Decomposition: The paper notes that the low-rank decomposition approach (Algorithm E) was unstable and produced highly variable results, suggesting it's prone to overfitting or local optima.
  • Inter-Class Regularization Nuance: While intra-class regularization proved beneficial, the inter-class term did not consistently improve performance and, in some cases, might have distorted the learned feature space. The authors speculate this is because inter-class distances might naturally vary widely.
  • Future Work: The authors plan to investigate the theoretical properties that explain the synergy of random projection and intra-class regularization. They also aim to explore how unlabeled data can be leveraged for semi-supervised learning in this context.

Summary updated

BibTeX
@inproceedings{he2013reconstructing,
  author = {Ai He and Shefali Sharma and Chun-Nan Hsu},
  title = {{Reconstructing Big Semantic Similarity Networks}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2013},
}
Figure