Query Processing & Expansion: Techniques, Feedback & Ranking

TAKEAWAYS:

• Query processing transforms raw user input into structured queries using stemming, stopword removal, and query expansion to match documents more accurately.
• Relevance feedback (explicit/implicit) refines queries by analyzing user interactions (clicks, dwell time) to improve ranking.
• Pseudo-relevance feedback assumes top-ranked documents are relevant and expands queries using their terms—critical for systems like YouTube’s search suggestions.
• Query rewriting techniques (e.g., Rocchio algorithm) adjust queries based on feedback to reduce ambiguity (e.g., "Nepal earthquake 2015" vs. "earthquake").
• Evaluation metrics (precision, recall, MAP) measure how well expanded queries perform compared to originals.
• Real-world systems (e.g., WhatsApp’s search, Ncell’s customer support chatbots) use these techniques to handle noisy input and user intent.

1. Query Processing: From Raw Input to Structured Query

Query processing is the bridge between what a user types and what the search engine retrieves. It involves normalization, expansion, and rewriting to handle ambiguity, typos, and intent.

Key Steps in Query Processing

graph TD
    A["Raw Query"] --> B["Preprocessing"]
    B --> C["Tokenization"]
    C --> D["Stopword Removal"]
    D --> E["Stemming/Lemmatization"]
    E --> F["Query Expansion"]
    F --> G["Rewriting"]
    G --> H["Ranking"]

A. Preprocessing

1. Tokenization: Splitting the query into terms (e.g., "best laptops under 50000" → ["best", "laptops", "under", "50000"]).

2. Stopword Removal: Filtering out common words (e.g., "under", "the", "is") that add no meaning.

3. Stemming/Lemmatization:

   • Stemming (e.g., Porter Stemmer) reduces words to root forms:
     • "running" → "run"
     • "better" → "good"
   • Lemmatization uses vocabulary (e.g., "better" → "good" vs. "better" → "best" in some contexts).

   Worked Example: For the query "How to fix a broken phone screen?" after preprocessing:

   • Tokenized: ["how", "fix", "broken", "phone", "screen"]
   • Stopwords removed: ["fix", "broken", "phone", "screen"]
   • Stemmed (Porter): ["fix", "break", "phon", "scree"] → Note: Over-stemming can lose meaning (e.g., "phone" → "phon" might miss "smartphone").

B. Query Expansion

Expands short or ambiguous queries using:

• Synonyms: "car" → "vehicle", "automobile".
• Related Terms: "Nepal earthquake" → "Gorkha earthquake 2015".
• Pseudo-Relevance Feedback: Uses top-ranked documents’ terms to expand queries (e.g., if "Ncell recharge" returns docs with "top-up", "reload", add these to the query).

Why Expand Queries?

• Short Queries: Users often type 1–3 words (e.g., "laptop"), leading to poor recall.

• Ambiguity: "Java" could mean programming, coffee, or the island.

• Typos: "googl" → expanded to "google", "search".

• Original query: "best phone under 30000"

• Expanded query: "best phone under 30000 + budget + affordable + Samsung + Xiaomi + review".

C. Query Rewriting

Adjusts queries based on:

1. User Feedback: Explicit (thumbs up/down) or implicit (clicks, dwell time).
2. Algorithms: Rocchio algorithm (adjusts query vector based on relevant/irrelevant docs).
   • Formula: $$Q_{new}=\alpha \cdot Q_{original}+\beta \cdot \frac{1}{|D_r|}\sum _{d\in D_r}d-\gamma \cdot \frac{1}{|D_{nr}|}\sum _{d\in D_{nr}}d$$ Where:
     • $D_r$ = relevant docs, $D_{nr}$ = irrelevant docs.
     • $\alpha ,\beta ,\gamma$ = weights (typically 1, 0.75, 0.15).

Real-World Example: WhatsApp Search

• When you search for "old messages", WhatsApp expands the query to include:
  • Synonyms: "previous", "past", "archived".
  • Related terms: "chat history", "conversations".
• Uses implicit feedback (e.g., if you click a message but don’t open it, it assumes partial relevance).

2. Relevance Feedback: Learning from User Behavior

Relevance feedback improves queries by analyzing how users interact with results.

Types of Feedback

1. User submits query → System returns docs.
2. User clicks/documents → System marks as relevant.
3. Algorithm rewrites query using Rocchio or LSI.

Pseudo-Relevance Feedback (PRF)

• Process:
  1. Retrieve top k docs (e.g., k=10) for the original query.
  2. Extract terms from these docs (excluding stopwords).
  3. Add these terms to the original query with weights (e.g., TF-IDF).
• Example:
  • Original query: "best phone 2023".
  • Top 10 docs contain: "Samsung", "iPhone", "flagship", "camera", "5G".
  • Expanded query: "best phone 2023 + Samsung + iPhone + flagship + camera + 5G".

Worked Example: Daraz Search

• If you search "laptop under 40000" and click on a Lenovo IdeaPad listing but don’t open others, Daraz’s PRF might:
  1. Assume "Lenovo" and "IdeaPad" are relevant.
  2. Expand future queries for similar searches to include:
     • "Lenovo", "IdeaPad", "budget", "RAM 8GB", "Windows 11".

3. Evaluation Metrics for Query Expansion

How do we measure if expansion works? Key metrics:

Example Calculation: For query "Nepal earthquake 2015" with 5 relevant docs in top 10:

• Precision@10 = 5/10 = 50%.
• If the 5th relevant doc is ranked 7th, NDCG penalizes lower ranks.

• X-axis: Recall (0 to 1).
• Y-axis: Precision (0 to 1).
• Curve for original vs. expanded query (expanded should dominate).

4. Advanced Techniques

A. Latent Semantic Indexing (LSI)

• Uses Singular Value Decomposition (SVD) to find hidden relationships between terms and docs.
• Example: "king" and "queen" might not appear together but are semantically linked via LSI.

B. Query Log Analysis

• Mines past queries to expand new ones. Example:
  • If many users search "how to reset iPhone" after "iPhone stuck", the system pre-expands "reset" queries with "stuck", "force restart".

C. Neural Query Expansion

• Uses BERT or Word2Vec to find contextually similar terms.

• Example: For "best coffee in Kathmandu", Word2Vec might suggest "espresso", "latte", "Thamel".

• Input: "best coffee".

• Output: Nearest neighbors in vector space: "espresso", "latte", "Thamel", "Nepali coffee".

## In the Real World

1. eSewa (Nepal)
   • What it uses: Query expansion + pseudo-relevance feedback.
   • How: When you search for "electricity bill payment", eSewa expands the query to include:
     • Synonyms: "bill", "payment", "online".
     • Related terms: "Nepal Electricity Authority (NEA)", "Kathmandu", "Lalitpur".
   • Why: Users often type short queries, and expansion improves recall for rural areas with low internet literacy.

2. Khalti (Digital Payments)

   • What it uses: Explicit relevance feedback + query rewriting.
   • How: If you search for "transfer money to friend" but keep getting "merchant payment" results, Khalti’s system:
     1. Detects you clicked "personal transfer" but not "merchant".
     2. Rewrites the query to prioritize terms like "individual", "bank account", "phone number".
   • Result: Precision improves from 30% to 85%.

3. YouTube Search

   • What it uses: Pseudo-relevance feedback + neural embeddings.
   • How: For "how to cook dal bhat":
     1. Shows top 10 videos; assumes those with high watch time are relevant.
     2. Expands query with terms like "Nepali dal bhat", "rice", "lentils", "pressure cooker".
     3. Uses BERT to understand intent (e.g., "quick dal bhat" vs. "traditional").
   • Impact: Reduces ambiguity for multilingual users (e.g., Nepali vs. Hindi terms).

4. Ncell Customer Support Chatbot

   • What it uses: Query rewriting + user feedback loops.
   • How: If you type "my phone not charging":
     1. System expands to: "phone charging issue", "dead battery", "Ncell battery swap".
     2. If you reply "no", it rewrites to: "Ncell network issue", "signal problem".
   • Real Example: In 2022, Ncell’s chatbot handled 30% more queries after implementing PRF for common issues like "SIM not working".

5. NEPSE Stock Search

   • What it uses: Synonym expansion + log analysis.
   • How: For "buy shares Nepal":
     • Expands to: "NEPSE shares", "stock market Nepal", "Nabil Bank", "Global IME".
     • Uses past queries to suggest: "dividend stocks", "high growth 2023".
   • Why: Helps retail investors navigate Nepali stock terms (e.g., "share" vs. "stock").

## Exam Tip

How This Unit is Tested (Based on Past TU/PU Exams):

1. Definitions & Concepts (30%):

   • Expect questions like:
     • "Define pseudo-relevance feedback and give an example."
     • "How does the Rocchio algorithm work?"
   • Answer Tip: Use formulas (e.g., Rocchio) and real examples (e.g., WhatsApp search).

2. Ranking Documents (25%):

   • Given a query and docs, rank them using TF-IDF + expansion.
   • Worked Example:
     • Query: "state machine"
     • Docs:
       • Doc1: "finite state machine"
       • Doc2: "transition machine"
       • Doc3: "transition state"
     • Steps:
       1. Stem all terms: "state" → "stat", "machine" → "machin", "transition" → "transit".
       2. Expand query with synonyms: "state machine" → "finite automaton", "FSM".
       3. Rank by term overlap:
          • Doc1: 2 matches ("finite", "state").
          • Doc2: 1 match ("machine").
          • Doc3: 1 match ("state").
     • Final Rank: Doc1 > Doc3 > Doc2.

3. Query Expansion Techniques (20%):

   • Compare synonym expansion, PRF, and LSI.

   • Answer Tip: Use a table like this:

     Technique	How It Works	Example	Pros	Cons
     Synonym Expansion	Replaces terms with synonyms.	"car" → "vehicle", "automobile".	Simple, improves recall.	Limited to predefined synonyms.
     PRF	Expands query with terms from top docs.	Query: "laptop"; adds "Dell", "RAM".	No user input needed.	Assumes top docs are relevant.
     LSI	Uses SVD to find latent relationships.	Links "king" and "queen" via context.	Handles polysemy (e.g., "Java").	Computationally expensive.

4. Evaluation Metrics (15%):

   • Calculate precision, recall, or MAP given a scenario.
   • Example Question: "For a query with 3 relevant docs in top 5 results, what is precision@5?"
     • Answer: $\frac{3}{5}=60\%$.

5. Real-World Applications (10%):

   • Link techniques to Nepali apps (e.g., "How does Daraz use query expansion?").
   • Answer Tip: Name the app, the technique, and a specific example (e.g., "Daraz uses PRF to expand 'laptop' with 'Lenovo', 'RAM 8GB' based on clicked listings").

Common Pitfalls to Avoid:

• Over-stemming: Don’t reduce "phone" to "phon" if it loses meaning.
• Ignoring stopwords: Removing "the", "is" is correct, but don’t remove domain-specific terms (e.g., "Nepal" in "Nepal earthquake").
• Assuming all top docs are relevant: PRF can fail if the initial ranking is poor (e.g., spam docs).

Final Advice:

• Draw diagrams for Rocchio, PRF, and query expansion steps.
• Memorize formulas for Rocchio and evaluation metrics.
• Practice ranking docs using TF-IDF + expansion.