Alternative Phrases and Natural Language Information Retrieval

Gann Bierner

TL;DR

This paper tackles the challenge of natural language search engines failing to understand queries containing "alternative phrases" (like "other than" or "besides"). The authors propose a formal semantic analysis for these phrases and demonstrate how approximating this analysis can significantly improve search engine performance, making them more accurate and less prone to returning irrelevant results.

What Problem Does This Paper Address?

Natural language information retrieval (NLIR) systems aim to understand user queries expressed in everyday language. However, a common pitfall is their inability to correctly interpret phrases that specify exclusions or alternatives. For instance, a query like "Where can I find web browsers other than Netscape?" might be treated by a naive search engine as simply "Where can I find web browsers?", leading to results that include Netscape, which the user explicitly wanted to avoid. These "alternative phrases" are frequent in human-to-human dialogue and are crucial for users to precisely constrain their search space. The paper highlights that current NLIR systems often ignore these phrases or misinterpret them, resulting in a significant number of irrelevant or "false positive" results.

Methods

The core of the paper lies in a formal semantic analysis of "alternative markers" and "alternative phrases." The authors adopt a pragmatic view of presuppositions, separating a word's meaning into assertion and presupposition. A key concept introduced is the "alternative set," which represents a collection of entities sharing a common property but differing in one argument.

The analysis models alternative phrases as defining these alternative sets. For example, "other than X" implies a set of items that are like X but not X itself. The paper then proposes a grammar formalism, Combinatory Categorial Grammar (CCG), to implement this analysis.

To make this formal analysis practical for existing search engines, the paper proposes an "approximation" that is compatible with their operational semantics. For the Electric Knowledge (EK) search engine, which uses pattern matching, this approximation involves transforming the natural language query into a hybrid query. This hybrid query combines the original natural language query with specific restrictions, often expressed as "ANSWER NOT NEAR (word list)," to enforce the exclusion specified by the alternative phrase.

Datasets

The paper uses two corpora of human-to-human dialogue for analyzing the frequency of alternative phrases:

  • A corpus from tutorial situations in Physics.
  • A corpus from tutorial situations in Basic Electricity and Electronics.

For evaluation, the authors used queries derived from these corpora and from existing EK search engine queries. They also created new query sets for evaluating the enhanced EK search engine, focusing on indices of pages about American history and literature.

Key Insights and Ideas

  • Alternative phrases are crucial for precise search: Users employ phrases like "other than" and "besides" to refine their searches, and ignoring them leads to significant user dissatisfaction.
  • Presuppositions hold valuable information: Alternative markers carry presuppositions that imply the existence and category of the excluded item (e.g., "other than Netscape" presupposes Netscape is a web browser). This information can be leveraged.
  • Formal semantics can be approximated for practical systems: A sophisticated semantic analysis, while powerful, can be computationally expensive. The paper shows that a well-designed approximation can bridge the gap between theoretical understanding and practical implementation in existing NLIR systems.
  • Hybrid queries offer a pragmatic solution: By combining natural language queries with explicit restrictions (like "NOT NEAR"), search engines can better handle alternative phrases without a complete overhaul.
  • Ignoring alternative phrases leads to high false positives: When systems fail to understand exclusions, a large percentage of returned results can be about the very thing the user wanted to avoid.

Key Results

  • Frequency of alternative phrases: In human-to-human dialogue, an average of 3.65 alternative phrases per dialog were observed, and 1.54 alternative phrases per dialog occurred in question contexts. This indicates their prevalence.
  • Improved precision with approximated analysis: For the Electric Knowledge search engine, transforming queries with alternative phrases into a hybrid format (e.g., "What are some web browsers? :|: ANSWER NOT NEAR (| netscape)") dramatically improved precision.
  • Baseline precision for queries with alternative phrases was around 15%.
  • The hybrid query approach achieved an average precision of 58% and a top-5 precision of 66.3%.
  • Reduced false positives: The hybrid query approach significantly reduced "false positives containing the figure" (results about the excluded item), from an average of 44% in the baseline to 12.8% with the transformed query.

Limitations and Future Work

  • User awareness and trust: Users often avoid using natural language features they believe the system won't understand, leading to less effective queries. Future work could involve improving user awareness and trust in NL capabilities.
  • Iterative search: The paper acknowledges that search is often an iterative process, and current evaluations might not fully capture real-world user experiences.
  • Operational semantics evolution: The authors suggest that as the operational semantics of natural language applications improve, even larger gains from their approach will be possible.
  • Characterizing documents: Future work could also involve using alternative phrases to better characterize documents themselves, rather than just processing queries.

Summary updated

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