Alternative Phrases and Natural Languages Information Retrieval

Gann Bierner

Abstract

Traditional search engines often fail to correctly interpret "alternative markers" such as other than, besides, and such as, frequently returning the very items a user intends to exclude. This paper proposes a formal semantic framework based on Combinatory Categorial Grammar (CCG) to model these phrases. By translating this formal analysis into practical search constraints, the proposed system improves search precision from approximately 15% to over 60% in natural language information retrieval tasks.

Introduction

When users interact with information retrieval (IR) systems using natural language, they often use linguistic markers to constrain the search space. Phrases like "web browsers other than Netscape" explicitly define a category ("web browsers") while excluding a specific instance ("Netscape"). However, most modern search engines treat these markers as noise or, worse, prioritize the excluded term due to its high keyword weight. This paper, authored by Gann Bierner at the University of Edinburgh, explores the semantic complexity of these "alternative phrases" and demonstrates how a theory-driven approach can significantly enhance search accuracy.

The Prevalence of Alternative Markers

To establish the importance of this problem, Bierner analyzed human-to-human tutorial dialogs in Physics and Electronics. The data reveals that alternative markers are a frequent feature of natural information-seeking behavior.

Frequency of alternative markers in tutorial dialog corpora

As shown in the table above, words like "other" and "another" appear hundreds of times across the corpora, highlighting the need for IR systems to handle them correctly.

Formal Semantic Analysis

The core of the proposed solution is a formal model using Combinatory Categorial Grammar (CCG). Bierner treats alternative phrases as "alternative sets"—propositions that differ by a single argument. These are categorized into "assembly" markers (e.g., such as), which expand a set, and "excision" markers (e.g., other than), which remove items from a set.

CCG derivation for "other web browsers than Netscape"

The CCG derivation illustrates how the system models the presupposition that the "figure" (Netscape) belongs to the "ground" category (web browsers) while ensuring the final logical form excludes the figure from the result set.

From Theory to Practice: Hybrid Queries

Recognizing that full logic engines are computationally expensive for real-time search, the paper introduces an "operational approximation." The formal analysis is translated into a "hybrid query" for the Electric Knowledge search engine. For a query like "browsers other than Netscape," the system identifies the figure (Netscape) and ground (browsers), then appends a structural constraint: Query :|: ANSWER NOT NEAR (| figure). This instruction directs the backend to find the ground category but reject results where the figure is the primary answer.

Evaluation and Results

The system was evaluated using a custom set of "excision" queries against a search index of ~11,000 pages on American history and literature. The results were compared against baseline performance from standard engines like Alta Vista and Ask Jeeves.

  • Precision Improvement: The hybrid approach increased precision from a baseline of 14.9% to 58% overall. For the top 5 results, precision reached 66.3%.
  • Error Reduction: The rate of "False Positives Containing Figure"—results that were incorrect specifically because they included the excluded item—dropped from 44% to 12.8%.

Conclusion and Future Work

Bierner's work demonstrates that even a "lossy" approximation of formal linguistic theory can provide massive gains in IR precision. By treating alternative markers as structured constraints rather than simple keywords, systems can avoid the "keyword trap" where rare, excluded terms dominate results. Future research will focus on automating the translation process and improving anaphora resolution, where the "figure" of an alternative phrase refers back to a previous turn in a dialog.

Summary updated

BibTeX
@inproceedings{bierner2001alternative,
  author = {Gann Bierner},
  title = {{Alternative Phrases and Natural Languages Information Retrieval}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2001},
  doi = {10.3115/1073012.1073021},
}
Figure