PaperlayerView exact revision on arXiv

Source-linked AI summary

Measuring Semantic Similarity by Latent Relational Analysis

Peter D. Turney

arXiv:cs/0508053v1cs.LGcs.CLcs.IR

TL;DR

Existing similarity measures mainly capture attributional similarity, whereas the paper seeks to measure relational similarity between word pairs for language-processing applications. LRA extends VSM by automatically deriving corpus patterns, smoothing frequency data with SVD, and using synonyms to reformulate word pairs. LRA achieves 56% on 374 analogy questions, statistically equivalent to the 57% average human score, and achieves similar gains over VSM on noun-modifier relation classification.

  • Problem

    Existing similarity measures mainly capture attributional similarity, whereas the paper seeks to measure relational similarity between word pairs for language-processing applications.

  • Method

    LRA extends VSM by automatically deriving corpus patterns, smoothing frequency data with SVD, and using synonyms to reformulate word pairs.

  • Results

    LRA achieves 56% on 374 analogy questions, statistically equivalent to the 57% average human score, and achieves similar gains over VSM on noun-modifier relation classification.

  • Takeaways & Limitations

    LRA provides a state-of-the-art method for measuring relational similarity across analogy solving and noun-modifier relation classification.

  • Takeaways & Limitations

    Noun-modifier results depend on the chosen 30-class semantic-relation scheme, which may not be the best scheme and may differ in machine-learning difficulty.

Abstract

from arXiv · show

This paper introduces Latent Relational Analysis (LRA), a method for measuring semantic similarity. LRA measures similarity in the semantic relations between two pairs of words. When two pairs have a high degree of relational similarity, they are analogous. For example, the pair cat:meow is analogous to the pair dog:bark. There is evidence from cognitive science that relational similarity is fundamental to many cognitive and linguistic tasks (e.g., analogical reasoning). In the Vector Space Model (VSM) approach to measuring relational similarity, the similarity between two pairs is calculated by the cosine of the angle between the vectors that represent the two pairs. The elements in the vectors are based on the frequencies of manually constructed patterns in a large corpus. LRA extends the VSM approach in three ways: (1) patterns are derived automatically from the corpus, (2) Singular Value Decomposition is used to smooth the frequency data, and (3) synonyms are used to reformulate word pairs. This paper describes the LRA algorithm and experimentally compares LRA to VSM on two tasks, answering college-level multiple-choice word analogy questions and classifying semantic relations in noun-modifier expressions. LRA achieves state-of-the-art results, reaching human-level performance on the analogy questions and significantly exceeding VSM performance on both tasks.

1 Introduction

The paper introduces LRA to measure relational similarity, addressing a gap in methods focused mainly on attributional similarity. It extends VSM and reaches human-level performance on college-level analogy questions while achieving state-of-the-art results.

  • 1 Introduction: LRA measures relational similarity: correspondence between relations, where highly similar word pairs are considered analogous.This differs from attributional similarity, which concerns correspondence between attributes and is associated with synonymy.
  • 1 Introduction: Past methods mainly measured attributional similarity; LSA, for example, compares words but not relations.
  • 1 Introduction: VSM represents word-pair relations with frequencies of predefined corpus patterns and scored 47% on 374 college-level analogy questions [Turney and Littman, 2005].
  • 1 Introduction: LRA automatically derives patterns, applies SVD smoothing, and uses automatically generated synonyms to reformulate word pairs.It achieves 56% on the analogy questions, statistically equivalent to the 57% average human score, and state-of-the-art performance on both evaluated problems.
  • 1 Introduction: The paper presents LRA, reviews applications and related work, evaluates it on analogy questions and noun-modifier classification, and discusses limitations and future work.

2 Applications of Relational Similarity

Relational similarity is motivated as a complement to attributional similarity for language-processing tasks. It could help distinguish relations that word-level similarity alone leaves ambiguous, including in word sense disambiguation.

  • 2 Applications of Relational Similarity: A general similarity measure for text chunks could support information retrieval, question answering, machine translation, extraction, disambiguation, summarization, and other NLP tasks.The motivation also connects to paraphrasing and textual entailment.
  • 2 Applications of Relational Similarity: Current approaches often use attributional similarity, such as bag-of-words retrieval, while ignoring relations between words.
  • 2 Applications of Relational Similarity: Relational similarity is proposed as a complement because human similarity judgments involve both attributional and relational similarity.
  • 2 Applications of Relational Similarity: In word sense disambiguation, relations in phrases such as “food for the plant” versus “food at the plant” can distinguish living from industrial meanings of “plant”.
  • 2 Applications of Relational Similarity: A relational-similarity measure could potentially improve applications that currently use attributional similarity.

3 Related Work

Related work represents relational similarity through corpus evidence associated with word pairs. VSM was evaluated on analogy questions and noun-modifier classification, providing the main comparison target for LRA.

  • 3 Related Work: Relational similarity requires inferring hidden relations between two word pairs before comparing those relations.
  • 3 Related Work: VSM represents each relation with a vector and compares two relations using the cosine between their vectors.
  • 3 Related Work: VSM builds a 128-number vector from frequencies of phrases formed with 64 joining terms, then selects the analogy choice with the highest cosine [Turney and Littman, 2005].On 374 SAT analogy questions, this approach achieved 47%.
  • 3 Related Work: The strongest prior SAT performance combined thirteen modules, while the experiments focus on VSM versus LRA because VSM was the best individual module [Turney et al., 2003].
  • 3 Related Work: VSM also served as a nearest-neighbor distance measure for classifying 600 noun-modifier pairs across 30 manually labeled semantic-relation classes [Turney and Littman, 2005].A test pair receives the label of the training pair with the highest cosine.

4 Latent Relational Analysis

LRA combines synonym-based reformulation, automatically extracted corpus patterns, entropy weighting, and SVD-based dimensionality reduction to compare word-pair relations. It uses large-corpus search without labeled or supervised data.

  • 4 Latent Relational Analysis: LRA takes word pairs as input and outputs relational-similarity measures, relying on a large-corpus search engine, a synonym thesaurus, and SVD implementation.It does not use labeled data, structured data, or supervised learning.
  • 4 Latent Relational Analysis: For each pair, LRA generates synonym-based alternates, filters them by phrase frequency, and retains the most frequent alternatives with clearer semantic relations.The experiments use 10 similar words, retain 3 alternates, and search phrases of up to 5 words.
  • 4 Latent Relational Analysis: LRA constructs a sparse pair-by-pattern frequency matrix, applies logarithm and entropy transformations, and weights patterns that vary substantially across pairs.
  • 4 Latent Relational Analysis: SVD produces a rank-k smoothed approximation that reduces noise and sparsity before projecting pairs into a lower-dimensional space for cosine comparisons.The experiments use k = 300, reducing 8,000 columns to 300.
  • 4 Latent Relational Analysis: LRA compares every retained version of two input pairs, yielding (num_filter + 1)^2 alternate-pair comparisons.
  • 4 Latent Relational Analysis: The implementation uses the WMTS search engine over a corpus of about 5 × 10^10 English words and Lin’s automatically generated thesaurus.WMTS runs locally on a 16-CPU Beowulf Cluster; the thesaurus is based on about 5 × 10^7 English words.

5 Experiments with Word Analogy Questions

On 374 SAT analogy questions, LRA outperformed VSM, reached a 56.4% score statistically indistinguishable from the approximately 57% human average, and processed the task faster than VSM-AV.

  • LRA performance: LRA attained 56.4% on the 374 SAT questions, correctly answering 210 and skipping four questions whose pairs had zero relational similarity.Skipped questions received partial credit equivalent to random guessing, 0.2 points each.
  • LRA performance: LRA’s 56.4% score was statistically indistinguishable from the approximately 57% average performance of college-bound senior high school students.The comparison uses the average verbal SAT performance reported by Turney and Littman [2005].
  • LRA versus VSM: LRA scored 56% versus 40% for VSM on the same corpus, a statistically significant 16-point absolute and 40% relative improvement; it remained ahead by 9 points with a ten-times-larger VSM corpus.Table 2 reports these comparisons, and all three pairwise score differences were significant at 95% confidence using the Fisher Exact Test.
  • LRA versus VSM: With the smaller corpus, VSM’s lower score was partly associated with 34 skipped questions versus 5 for VSM-AV, whereas LRA answered as many questions as VSM-AV.The authors attribute LRA’s coverage to synonym substitution through Lin’s [1998] thesaurus.
  • Efficiency: LRA processed the 374 analogy questions in 9 days, compared with 17 days for VSM-AV and 1 day for VSM-WMTS.The VSM-AV comparison includes a five-second delay between queries, whereas WMTS ran locally without such delays.

6 Experiments with Noun-Modifier Relations

The noun-modifier experiments evaluate LRA against VSM using nearest-neighbour classification on manually labeled semantic-relation pairs. LRA significantly outperforms VSM on both 30-class and 5-class problems.

  • Experimental setup: Evaluation used single nearest-neighbour classification with leave-one-out cross-validation over 600 manually labeled noun-modifier pairs.Each pair served once as the test item, while accuracy and macroaveraged F measure were reported.
  • 30-class problem: LRA significantly outperformed both VSM variants on the 30-class noun-modifier task, with 15% higher accuracy in absolute terms and 61% higher in relative terms using the same corpus.The task used 600 noun-modifier pairs labeled with 30 semantic-relation classes; accuracy and all three F-measure differences were statistically significant.
  • LRA representation: The LRA input expands from 600 original pairs to 4,800 after alternate and reversed pairs, producing a 4,748-by-8,000 sparse matrix with 8.4% density.Some pairs were removed because they produced zero vectors or lacked thesaurus entries.
  • 5-class problem: The 5-class results likewise showed significantly higher accuracy and F measure for LRA than for either VSM variant, with a 14% absolute and 32% relative accuracy improvement using the same corpus.The two VSM systems did not differ significantly from each other.

7 Discussion

The discussion presents LRA as substantially better than VSM while emphasizing practical constraints involving accuracy, runtime, corpus size, labeled data, and relation-class design.

  • Performance and applicability: LRA significantly outperforms VSM, but its accuracy may still be inadequate for practical applications.The authors suggest that information-extraction applications might require tuning toward high precision at the expense of recall.
  • Speed: Answering 374 analogy questions took LRA almost nine days, although software optimization, parallelization, hardware progress, or precomputation could reduce this speed limitation.Precomputation would require substantial changes to the algorithm.
  • Corpus size: VSM performance is sensitive to corpus size, while the authors expect LRA to perform better with a larger corpus.The WMTS corpus requires one terabyte of disk space, creating a substantial resource requirement.
  • Labeled data: Noun-modifier accuracy may improve substantially with five or ten times more labeled examples, but acquiring hand-labeled data is time-consuming and expensive.With 600 pairs and 30 classes, the average class contains only 20 examples.
  • Classification scheme: The selected 30-class semantic-relation scheme may not be optimal, and some alternative schemes may be easier for machine learning than others.Other researchers have proposed different classification schemes.

8 Conclusion

The paper concludes that LRA is a new relational-similarity method that outperforms VSM on analogy and noun-modifier tasks. It matches average human performance on SAT analogy questions, though its error rate may remain too high for practical applications.

  • Conclusion: LRA outperforms VSM on both SAT word analogy questions and noun-modifier relation classification.LRA replaces hand-built patterns with dynamically generated patterns, smooths data with SVD, and uses a thesaurus to reformulate word pairs.
  • Implications: Relational similarity measures may support text-processing applications and could contribute to artificial-intelligence systems because relational similarity plays a fundamental role in the mind.The authors position LRA as a possible step toward a broad text-processing “black box.”
  • Future work and scope: LRA matches average human performance on SAT analogy questions, although its error rate may still be too high for practical applications.The authors identify this human-level result as encouraging while leaving practical suitability unresolved.
Loading cs/0508053v1…