Mining the Web for Synonyms: PMI-IR versus LSA on TOEFL

Peter D. Turney

article2001European Conference on Machine Learning1,513 citationsECML PKDD 10 Year Award

Introduces PMI-IR, an unsupervised algorithm that uses web search engine query statistics to measure word similarity, outperforming Latent Semantic Analysis by ten percentage points on standard TOEFL synonym tests.

Listen

Building and maintaining lexical databases manually requires substantial labor and often results in poor coverage of specialized and emerging terminology. While statistical techniques can automate synonym recognition, they historically suffered from data scarcity when analyzing rare words. The article evaluates an unsupervised statistical method that leverages the vast scale of web search engines to measure semantic similarity without manual intervention.

The article demonstrates that Pointwise Mutual Information combined with Information Retrieval (termed PMI-IR) can accurately identify synonyms by querying web document collections. The analysis evaluates four variations of PMI-IR across 80 synonym questions from the Test of English as a Foreign Language (TOEFL) and 50 questions from English as a Second Language (ESL) tests, benchmarking results against Latent Semantic Analysis (LSA) and human performance averages using AltaVista search queries.

The findings show that the most refined version of PMI-IR achieved a 73.75% accuracy rate on the TOEFL benchmark and 74% on the ESL benchmark, outperforming the 64.5% average human score for college applicants from non-English speaking countries. PMI-IR scored nearly 10 percentage points higher on TOEFL questions than LSA, which reached 64.4%. Refining search queries from whole-document co-occurrence to local word proximity (within 10 words) significantly improved accuracy from 62.5% to 72.5% on TOEFL and from 48% to 62% on ESL. Filtering out negative contexts and incorporating local sentence context further boosted ESL accuracy from 66% to 74%.

These results demonstrate that simple statistical co-occurrence models can outperform complex dimensionality reduction techniques like LSA when given access to massive data corpora. For operational applications, this approach bypasses the high computational overhead of matrix decomposition methods like Singular Value Decomposition. It also offers practical benefits for automated lexicon construction, query expansion in information retrieval, and keyword extraction.

Organizations developing natural language systems should consider using web-scale statistical querying as a lightweight alternative to complex statistical models. Because relying on live web queries introduces network latency—taking roughly 16 seconds per question in sequential processing—implementers should adopt multithreading or deploy hybrid architectures that resolve common words locally and reserve external search engines for rare terms. Further testing is needed to directly compare PMI and LSA on identical corpora to fully isolate the relative impacts of data volume and text window size.

National Research Council Canada engine lsi mutual informations synonym recognition PMI-IR algorithm semantic similarity

arXiv: cs/0212033

Paper: Indexing By Latent Semantic Analysis, Scott Deerwester et al. (1990). Introduces Latent Semantic Analysis (LSA), which serves as the primary comparative baseline and conceptual benchmark evaluated against PMI-IR in the paper.
Paper: Word Association Norms, Mutual Information, and Lexicography, Kenneth Ward Church et al. (1989). Establishes the foundational pointwise mutual information (PMI) metric for measuring statistical word associations from text corpora upon which PMI-IR is built.
Paper: An Information-Theoretic Definition of Similarity, Dekang Lin (1998). Provides the formal information-theoretic foundation for quantifying word similarity that contextualizes statistical and distributional semantic measures.
Paper: Automatic Retrieval and Clustering of Similar Words, Dekang Lin (1998). Demonstrates corpus-based statistical discovery of word similarity and automatic thesaurus generation, establishing standard evaluation methodologies for synonymy.
Paper: Probabilistic Latent Semantic Analysis, Thomas Hofmann (1999). Develops a probabilistic framework for latent semantic indexing, addressing structural limitations of classical LSA discussed in the paper.

Paper: Thumbs Up or Thumbs Down? Semantic Orientation Applied to Unsupervised Classification of Reviews, Peter D. Turney (2002). Directly applies the web-based PMI-IR co-occurrence methodology to determine the semantic orientation of phrases for unsupervised review classification.
Paper: Measuring praise and criticism: Inference of semantic orientation from association, Peter D. Turney et al. (2003). Extends the PMI-IR framework by comparing PMI and LSA on large-scale web data to infer word evaluative polarity across expanded lexicons.
Paper: The Google Similarity Distance, Rudi Cilibrasi et al. (2004). Generalizes the idea of extracting semantic similarity from search engine page counts into an information-theoretic Normalized Google Distance.
Paper: From Frequency to Meaning: Vector Space Models of Semantics, Peter D. Turney et al. (2010). Synthesizes vector space models of semantics, contextualizing PMI-based co-occurrence statistics alongside matrix factorization methods on benchmark tasks like TOEFL synonymy.
Paper: Neural Word Embedding as Implicit Matrix Factorization, Omer Levy et al. (2014). Proves theoretically that modern predictive neural word embeddings implicitly perform matrix factorization on shifted Pointwise Mutual Information matrices.
Paper: Computing Semantic Relatedness Using Wikipedia-based Explicit Semantic Analysis, Evgeniy Gabrilovich et al. (2007). Advances semantic relatedness computation beyond surface web co-occurrence by projecting text into high-dimensional concepts derived from Wikipedia.

Cover for Mining the Web for Synonyms: PMI-IR versus LSA on TOEFL

Abstract

This paper presents a simple unsupervised learning algorithm for recognizing synonyms, based on statistical data acquired by querying a Web search engine. The algorithm, called PMI-IR, uses Pointwise Mutual Information (PMI) and Information Retrieval (IR) to measure the similarity of pairs of words. PMI-IR is empirically evaluated using 80 synonym test questions from the Test of English as a Foreign Language (TOEFL) and 50 synonym test questions from a collection of tests for students of English as a Second Language (ESL). On both tests, the algorithm obtains a score of 74%. PMI-IR is contrasted with Latent Semantic Analysis (LSA), which achieves a score of 64% on the same 80 TOEFL questions. The paper discusses potential applications of the new unsupervised learning algorithm and some implications of the results for LSA and LSI (Latent Semantic Indexing).

Topics

engine lsi mutual informations semantic information supervised machine learning web search engines web searches unsupervised learning method web content latent factor

Keywords

synonym recognition PMI-IR algorithm semantic similarity TOEFL questions keyword extraction unsupervised learning Web search engines

1 Introduction
2 PMI-IR
3 Related Work
4 Latent Semantic Analysis
5 TOEFL Experiments
6 ESL Experiments
7 Discussion of Results
8 Applications
9 Conclusions
References

Knowls

Knowl 1 — Pointwise Mutual Information for Synonym Recognition (PMI-IR)
model/method
The Pointwise Mutual Information - Information Retrieval (PMI-IR) method selects the best synonym for a problem word from a set of candidate words by finding the candidate that maximizes statistical co-occurrence. Given a target word $problem$ and candidate choices $\{choice_1, choice_2, \dots, choice_n\}$ , the standard Pointwise Mutual Information (PMI) metric is:

$score(choice_i) = \log_2 \frac{p(problem \ \&\ choice_i)}{p(problem)\,p(choice_i)}$

where $p(problem \ \&\ choice_i)$ is the joint probability that the two words co-occur, and $p(problem)$ and $p(choice_i)$ are their unconditional probabilities. Because the logarithm is strictly monotonically increasing and $p(problem)$ is constant across all candidate choices for a given problem word, the ranking criterion simplifies to the conditional probability of the problem word given the choice word:

$score(choice_i) = \frac{p(problem \ \&\ choice_i)}{p(choice_i)} = p(problem \mid choice_i)$

PMI-IR estimates these probabilities empirically by submitting queries to an indexed Web search engine and using the retrieved document hit counts.
Knowl 2 — Four Query Formulations for PMI-IR Probability Estimation
equation
PMI-IR defines four increasingly refined scoring functions to estimate $p(problem \mid choice_i)$ based on search engine document hit counts $hits(\cdot)$ :
1. Document-level co-occurrence ( $score_1$ ): Measures whether both terms appear anywhere within the same document: $score_1(choice_i) = \frac{hits(problem\text{ AND }choice_i)}{hits(choice_i)}$
2. Proximity-constrained co-occurrence ( $score_2$ ): Restricts the query to documents where the two words appear within ten words of each other in either order via the search engine NEAR operator: $score_2(choice_i) = \frac{hits(problem\text{ NEAR }choice_i)}{hits(choice_i)}$
3. Antonym-penalized co-occurrence ( $score_3$ ): Reduces high co-occurrence scores between antonym pairs (such as big and small) by filtering out co-occurrences appearing in proximity to the word "not": $score_3(choice_i) = \frac{hits((problem\text{ NEAR }choice_i)\text{ AND NOT }((problem\text{ OR }choice_i)\text{ NEAR }\text{"not"}))}{hits(choice_i\text{ AND NOT }(choice_i\text{ NEAR }\text{"not"}))}$
4. Context-sensitive co-occurrence ( $score_4$ ): Evaluates candidate synonyms when an additional disambiguating context word $context$ is present: $score_4(choice_i) = \frac{hits((problem\text{ NEAR }choice_i)\text{ AND }context\text{ AND NOT }((problem\text{ OR }choice_i)\text{ NEAR }\text{"not"}))}{hits(choice_i\text{ AND }context\text{ AND NOT }(choice_i\text{ NEAR }\text{"not"}))}$
Knowl 3 — Automatic Context Word Selection for Contextual Synonym Identification
algorithm
When a synonym question contains sentence-level context, conjoining multiple context words in search engine queries reduces sample sizes and increases sensitivity to noise. PMI-IR automatically selects a single optimal context word $context^*$ by finding the non-stopword in the sentence with the highest semantic similarity to the problem word:
Input: Sentence $S$ , problem word $problem$ , candidate alternatives $C = \{choice_1, \dots, choice_n\}$
Output: Selected context word $context^*$
Words $\leftarrow$ tokenize( $S$ )
Candidates $\leftarrow$ Words $\setminus (\{problem\} \cup C \cup \text{StopWords})$
best_score $\leftarrow -\infty$
$context^* \leftarrow \text{null}$
for each $w \in \text{Candidates}$ do
    score $\leftarrow \frac{hits((problem\text{ NEAR }w)\text{ AND NOT }((problem\text{ OR }w)\text{ NEAR }\text{"not"}))}{hits(w\text{ AND NOT }(w\text{ NEAR }\text{"not"}))}$
    if score > best_score then
        best_score $\leftarrow$ score
         $context^* \leftarrow w$
    end if
end for
return $context^*$
The selected word $context^*$ is then plugged into the context-sensitive scoring function $score_4(choice_i)$ to rank candidate synonyms.

Knowl 4 — Evaluation of PMI-IR and Baselines on TOEFL Synonym Questions

data/table

The PMI-IR algorithm was evaluated on 80 multiple-choice synonym test questions from the Test of English as a Foreign Language (TOEFL), where each question presents a problem word and four alternatives without context. Hit counts were collected from the AltaVista search engine (indexing approximately 350 million web pages). Results are compared against Latent Semantic Analysis (LSA) trained on an encyclopedia corpus of 30,473 articles and reduced to rank 300 via Singular Value Decomposition, as well as the average score of non-English human applicants to US colleges.

Method	Query Formulation	Number Correct	Percentage
PMI-IR ( $score_1$ )	Document co-occurrence (AND)	50/80	62.5%
PMI-IR ( $score_2$ )	Proximity co-occurrence (NEAR)	58/80	72.5%
PMI-IR ( $score_3$ )	Proximity with negation filtering (NEAR and NOT)	59/80	73.75%
Latent Semantic Analysis	Rank 300 SVD matrix cosine	51.5/80	64.4%
Average Non-English US College Applicant	Human baseline	51.6/80	64.5%

PMI-IR using $score_3$ obtains 73.75%, outperforming both LSA (64.4%) and the average human applicant (64.5%) by nearly 10 percentage points.

Knowl 5 — Evaluation of PMI-IR Formulations on ESL Synonym Questions

data/table

PMI-IR was validated on 50 English as a Second Language (ESL) synonym questions. Each question embeds the problem word inside a sentence context alongside four alternative answer choices.

Method	Query Formulation	Number Correct	Percentage
PMI-IR ( $score_1$ )	Document co-occurrence (AND)	24/50	48.0%
PMI-IR ( $score_2$ )	Proximity co-occurrence (NEAR)	31/50	62.0%
PMI-IR ( $score_3$ )	Proximity and negation filtering (NEAR and NOT)	33/50	66.0%
PMI-IR ( $score_4$ )	Proximity, negation filtering, and context word	37/50	74.0%

Performance increases monotonically with query refinement: moving from document-level co-occurrence ( $score_1$ ) to 10-word proximity ( $score_2$ ) provides a 14 percentage point gain, negation filtering ( $score_3$ ) adds 4 percentage points, and incorporating the automatically chosen context word ( $score_4$ ) yields an additional 8 percentage points, reaching 74.0%.

Knowl 6 — Hypotheses on Data Scale and Chunk Size in PMI-IR versus LSA
theoretical result
Two structural hypotheses explain why PMI-IR outperforms Latent Semantic Analysis (LSA) on synonym recognition:
1. Corpus Scale versus Matrix Smoothing: PMI is known to be vulnerable to the sparse data problem on small-to-moderate text corpora. LSA uses Singular Value Decomposition (SVD) to project word-document co-occurrence matrices into a lower-dimensional space (e.g., rank 300), which acts as a smoothing and compression mechanism. However, PMI-IR overcomes data sparsity by querying a corpus of hundreds of millions of web pages indexed by search engines. At web scale, brute-force sample sizes make algebraic smoothing unnecessary.
2. Co-occurrence Chunk Size: When PMI-IR uses full-document co-occurrence ( $score_1$ ), its TOEFL accuracy (62.5%) closely matches LSA's accuracy (64.4%), which is computed over entire encyclopedia articles. Constraining co-occurrence to a 10-word window ( $score_2$ ) increases accuracy to 72.5%, indicating that evaluating tight local co-occurrence rather than whole-document co-occurrence accounts for most of the performance gain over LSA.
Knowl 7 — Hypothesis on Equivalence of Latent Semantic Indexing and Pseudo-Relevance Query Expansion
theoretical result
In Information Retrieval benchmarks (such as TREC2 and TREC3), Latent Semantic Indexing (LSI)—the application of LSA to IR—demonstrated no clear performance advantage over competitive retrieval systems that used pseudo-relevance query expansion.

Because words with high semantic similarity (e.g., cars and automobiles) have high conditional co-occurrence probabilities $p(\text{automobiles} \mid \text{cars})$ , an initial search query for cars naturally retrieves top documents containing automobiles. Query expansion extracts terms from these top retrieved documents and adds them to the query for a subsequent search, which automatically bridges synonymy gaps in the same manner as LSI's reduced-rank representation. This implies that while LSI improves upon baseline IR without query expansion, it provides no substantial advantage over IR systems that already incorporate pseudo-relevance query expansion.
Knowl 8 — Latency and Infrastructure Limitations of Web-Scale PMI-IR
limitation
The primary operational bottleneck of PMI-IR is network latency when querying remote search engines. Evaluating one 4-choice TOEFL question using $score_3$ requires 8 separate search queries to AltaVista (4 for individual candidate terms with negation, and 4 for joint proximity terms). At approximately 2 seconds per query over standard network connections, sequential execution requires 16 seconds per question (reducible to ~2 seconds if queries are issued concurrently via multi-threading).

Additionally, PMI-IR depends on search engine query language features that support boolean logic and proximity operators (such as NEAR), and relies on external index infrastructure rather than operating on a self-contained local model.

Coverage note — Omitted background descriptions of existing lexical databases (WordNet, BRICO, EuroWordNet) and standard Singular Value Decomposition mathematics for LSA that do not represent original contributions of this paper.

References

1.Church, K.W., Hanks, P.: Word Association Norms, Mutual Information and Lexicography. In: Proceedings of the 27th Annual Conference of the Association of Computational Linguistics, (1989) 76-83.
2.Church, K.W., Gale, W., Hanks, P., Hindle, D.: Using Statistics in Lexical Analysis. In: Uri Zernik (ed.), Lexical Acquisition: Exploiting On-Line Resources to Build a Lexicon. New Jersey: Lawrence Erlbaum (1991) 115-164.
3.AltaVista, AltaVista Company, Palo Alto, California, http://www.altavista.com/.
4.Test of English as a Foreign Language (TOEFL), Educational Testing Service, Princeton, New Jersey, http://www.ets.org/.
5.Tatsuki, D.: Basic 2000 Words - Synonym Match 1. In: Interactive JavaScript Quizzes for ESL Students, http://www.aitech.ac.jp/~iteslj/quizzes/js/dt/mc-2000-01syn.html (1998).
6.Landauer, T.K., Dumais, S.T.: A Solution to Plato’s Problem: The Latent Semantic Analysis Theory of the Acquisition, Induction, and Representation of Knowledge. Psychological Review, 104 (1997) 211-240.
7.Deerwester, S., Dumais, S.T., Furnas, G.W., Landauer, T.K., Harshman, R.: Indexing by Latent Semantic Analysis. Journal of the American Society for Information Science, 41 (1990) 391-407.
8.Berry, M.W., Dumais, S.T., Letsche, T.A.: Computational Methods for Intelligent Information Access. Proceedings of Supercomputing ’95, San Diego, California, (1995).
9.Manning, C.D., Schütze, H.: Foundations of Statistical Natural Language Processing. Cambridge, Massachusetts: MIT Press (1999).
10.Firth, J.R.: A Synopsis of Linguistic Theory 1930-1955. In Studies in Linguistic Analysis, pp. 1-32. Oxford: Philological Society (1957). Reprinted in F.R. Palmer (ed.), Selected Papers of J.R. Firth 1952-1959, London: Longman (1968).
11.AltaVista: AltaVista Advanced Search Cheat Sheet, AltaVista Company, Palo Alto, California, http://doc.altavista.com/adv_search/syntax.html (2001).
12.Fellbaum, C. (ed.): WordNet: An Electronic Lexical Database. Cambridge, Massachusetts: MIT Press (1998). For more information: http://www.cogsci.princeton.edu/~wn/.
13.Haase, K.: Interlingual BRICO. IBM Systems Journal, 39 (2000) 589-596. For more information: http://www.framerd.org/brico/.
14.Vossen, P. (ed.): EuroWordNet: A Multilingual Database with Lexical Semantic Networks. Dordrecht, Netherlands: Kluwer (1998). See: http://www.hum.uva.nl/~ewn/.
15.Turney, P.D.: Learning Algorithms for Keyphrase Extraction. Information Retrieval, 2 (2000) 303-336.
16.Grefenstette, G.: Finding Semantic Similarity in Raw Text: The Deese Antonyms. In: R. Goldman, P. Norvig, E. Charniak and B. Gale (eds.), Working Notes of the AAAI Fall Symposium on Probabilistic Approaches to Natural Language. AAAI Press (1992) 61-65.
17.Schütze, H.: Word Space. In: S.J. Hanson, J.D. Cowan, and C.L. Giles (eds.), Advances in Neural Information Processing Systems 5, San Mateo California: Morgan Kaufmann (1993) 895-902.
18.Lin, D.: Automatic Retrieval and Clustering of Similar Words. In: Proceedings of the 17th International Conference on Computational Linguistics and 36th Annual Meeting of the Association for Computational Linguistics, Montreal (1998) 768-773.
19.Richardson, R., Smeaton, A., Murphy, J.: Using WordNet as a Knowledge Base for Measuring Semantic Similarity between Words. In Proceedings of AICS Conference. Trinity College, Dublin (1994).
20.Lee, J.H., Kim, M.H., Lee, Y.J.: Information Retrieval Based on Conceptual Distance in IS-A Hierarchies. Journal of Documentation, 49 (1993) 188-207.
21.Resnik, P.: Semantic Similarity in a Taxonomy: An Information-Based Measure and its Application to Problems of Ambiguity in Natural Language. Journal of Artificial Intelligence Research, 11 (1998) 95-130.
22.Jiang, J., Conrath, D.: Semantic Similarity Based on Corpus Statistics and Lexical Taxonomy. In: Proceedings of the 10th International Conference on Research on Computational Linguistics, Taiwan, (1997).
23.Brin, S., Motwani, R., Ullman, J., Tsur, S.: Dynamic Itemset Counting and Implication Rules for Market Basket Data. In: Proceedings of the 1997 ACM-SIGMOD International Conference on the Management of Data (1997) 255-264.
24.Sullivan, D.: Search Engine Sizes. SearchEngineWatch.com, internet.com Corporation, Darien, Connecticut, http://searchenginewatch.com/reports/sizes.html (2000).
25.Papadimitriou, C.H., Raghavan, P., Tamaki, H., Vempala, S.: Latent Semantic Indexing: A Probabilistic Analysis. In: Proceedings of the Seventeenth ACM-SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Seattle, Washington (1998) 159-168.
26.Sparck Jones, K.: Comparison Between TREC2 and TREC3. In: D. Harman (ed.), The Third Text REtrieval Conference (TREC3), National Institute of Standards and Technology Special Publication 500-226, Gaithersburg, Maryland (1994) C1-C4.
27.Buckley, C., Salton, G., Allan, J., Singhal, A.: Automatic Query Expansion Using SMART: TREC 3. In: The Third Text REtrieval Conference (TREC3), D. Harman (ed.), National Institute of Standards and Technology Special Publication 500-226, Gaithersburg, Maryland (1994) 69-80.

Citation

MLA

Turney, P. D. “Mining the Web for Synonyms: PMI-IR Versus LSA on TOEFL”. Proceedings of the Twelfth European Conference on Machine Learning, (2001), Freiburg, Germany, 491-502, 2002, http://arxiv.org/abs/cs/0212033v1.

APA

Turney, P. D. (2002). Mining the Web for Synonyms: PMI-IR versus LSA on TOEFL. Proceedings of the Twelfth European Conference on Machine Learning, (2001), Freiburg, Germany, 491-502. http://arxiv.org/abs/cs/0212033v1

Chicago

Turney, P. D. 2002. “Mining the Web for Synonyms: PMI-IR Versus LSA on TOEFL”. Proceedings of the Twelfth European Conference on Machine Learning, (2001), Freiburg, Germany, 491-502. http://arxiv.org/abs/cs/0212033v1.

Harvard

Turney, P.D. (2002) “Mining the Web for Synonyms: PMI-IR versus LSA on TOEFL”, Proceedings of the Twelfth European Conference on Machine Learning, (2001), Freiburg, Germany, 491-502 [Preprint]. Available at: http://arxiv.org/abs/cs/0212033v1.

Vancouver

1. Turney PD (2002) Mining the Web for Synonyms: PMI-IR versus LSA on TOEFL. Proceedings of the Twelfth European Conference on Machine Learning, (2001), Freiburg, Germany, 491-502

BibTeX

@article{turney2002mining,
  title = {Mining the Web for Synonyms: PMI-IR versus LSA on TOEFL},
  author = {Turney, Peter D.},
  year = {2002},
  journal = {Proceedings of the Twelfth European Conference on Machine Learning, (2001), Freiburg, Germany, 491-502},
  url = {http://arxiv.org/abs/cs/0212033v1},
  eprint = {cs/0212033}
}

Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Mining the Web for Synonyms: PMI-IR versus LSA on TOEFL

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Pointwise Mutual Information for Synonym Recognition (PMI-IR)

Knowl 2 — Four Query Formulations for PMI-IR Probability Estimation

Knowl 3 — Automatic Context Word Selection for Contextual Synonym Identification

Knowl 4 — Evaluation of PMI-IR and Baselines on TOEFL Synonym Questions

Knowl 5 — Evaluation of PMI-IR Formulations on ESL Synonym Questions

Knowl 6 — Hypotheses on Data Scale and Chunk Size in PMI-IR versus LSA

Knowl 7 — Hypothesis on Equivalence of Latent Semantic Indexing and Pseudo-Relevance Query Expansion

Knowl 8 — Latency and Infrastructure Limitations of Web-Scale PMI-IR

References

Citation

BibTeX

Access the Paper