TL;DR
This paper investigates how to improve web search by expanding keywords with their synonyms and morphological variations, then composing these expanded queries using different Boolean logic strategies. The authors found that these linguistic optimizations, particularly when combined with a Cartesian composition approach, significantly enhance search engine performance compared to a baseline keyword-only search.
What Problem Does This Paper Address?
Traditional web search engines often rely on simple keyword matching, which can be limiting. Users might not use the exact terms found in relevant documents, or relevant documents might use variations of those terms. This paper tackles the challenge of bridging this lexical gap by exploring how to leverage linguistic knowledge – specifically, morphological derivations (e.g., "inventor" to "invention") and synonyms (e.g., "inventor" to "discoverer") – to enrich search queries. The core problem is not just how to expand keywords, but also how to effectively combine these expanded terms into a query that a search engine can process to retrieve better results.
Methods
The authors propose and evaluate three query composition strategies:
- Keyword "AND" Composition Search (KAS): This is the baseline, representing the default behavior of most search engines. It simply combines the basic keywords of a query using an AND operator. No lexical expansions are used.
- Keyword Expansion Insertion Search (KIS): This strategy expands each basic keyword with its morphological derivations and synonyms. It then constructs a disjunctive Boolean expression where each element is an AND clause. These clauses combine the original basic keywords with a single expansion. To ensure it doesn't lose results from KAS, it also includes the basic AND clause and individual basic keywords as separate disjuncts.
- Keyword Cartesian Composition Search (KCS): This is the most sophisticated strategy. It also expands keywords but constructs a disjunctive expression where each element is an AND clause formed by combining all possible tuples of expansions across the original keywords. Similar to KIS, it includes the basic AND clause and individual basic keywords to guarantee at least the same results as KAS.
The linguistic expansions (morphological derivations and synonyms) were derived from an Italian monolingual dictionary and manually extracted from the Italian WordNet database.
Datasets
The paper describes an experiment using a set of 20 fact-based, short-answer questions. These questions were selected from an initial set of 40, ensuring they had at least one web document answering them. The authors note that about 15% of the initial questions were ambiguous, but they were not eliminated to avoid bias. The questions were then manually translated into basic keywords. The evaluation involved retrieving up to ten documents for each query and having fifteen researchers assess the relevance of these documents.
Key Insights and Ideas
- Linguistic expansion is beneficial: The core hypothesis that lexical expansions improve search performance is confirmed.
- Composition matters: Simply expanding keywords isn't enough; how these expanded terms are combined into a query significantly impacts results.
- Cartesian composition shines: The KCS strategy, which explores a wider range of term combinations, generally outperforms both KAS and KIS, especially when a question has multiple expansions. This suggests that exploring more complex relationships between expanded terms can uncover relevant documents missed by simpler methods.
- Context is crucial: The evaluation considered not just the presence of an answer but also the contextual relevance of the document. Both KIS and KCS showed significant improvements in "context retrieval" scores, indicating they bring back documents that are more thematically aligned with the query, even if a direct answer isn't immediately found.
- No clear winner for expansion type: The paper doesn't definitively conclude whether synonyms or morphological derivations are more impactful individually. They seem to contribute to performance in a similar way.
Key Results
- The KAS baseline (no expansions) achieved an average relevance score ($f_-$) of 0.21 and ($f_+$) of 0.23.
- KIS showed an average increase of +19% in relevance compared to KAS.
- KCS showed a larger average increase of +33% in relevance compared to KAS.
- For questions with 2-3 lexical expansions (QS2), KCS demonstrated a remarkable improvement of +59% for $f_-$ and +77% for $f_+$.
- Both KIS and KCS significantly increased "context retrieval" scores, with KIS showing a +31% to +37% increase and KCS showing a +38% to +41% increase.
- About 6% of requested URLs were not retrieved across all methods.
Limitations and Future Work
- Limited expansion depth: The experiment only considered one level of expansion (e.g., "inventor" -> "scopritore" -> "discovery"). The authors acknowledge that recursive expansions (e.g., "inventor" -> "scopritore" -> "discovery" -> "discoverer") could be explored further.
- Manual expansion: While the search composition is automatic, the recognition of multiwords and the selection of synsets for expansion were done manually. Automating these steps, particularly word sense disambiguation in WordNet, is a key area for future work to make the system fully automatic and efficient.
- Question set size: The experiment used a relatively small set of 20 questions, which limits the generalizability of the findings.
- Future evaluation: The authors plan to conduct further evaluations to determine if specific numbers or types of lexical expansions perform better for individual questions and to explore automatic evaluation methods to speed up the research cycle.
Summary updated