Semantic Search and Hybrid Search

জিনিসটা কী, কেন দরকার

একজন customer help centre এ "ERR-517" খোঁজে। আরেকজন লেখে "I want my cash returned"। প্রথমজনের দরকার এমন একটা code এর হুবহু match যেটা কোনো embedding model বোঝে না; দ্বিতীয়জনের দরকার অর্থ, কারণ কোনো document এ "cash" শব্দটাই নেই। যে search শুধু একটা সামলায়, সে তোমার অর্ধেক user কে ফেল করায়।

Keyword search (BM25) হুবহু নাম, code, ID আর rare শব্দে দারুণ, আর সমার্থক শব্দে অন্ধ। Semantic search (embedding, আগের lesson) অন্যভাবে বলা কথা আর অন্য ভাষা বোঝে, আর হুবহু string এ ঝাপসা। Hybrid search দুইটাই চালায় আর result মেলায়, যাতে একটার অন্ধ জায়গা অন্যটা ঢাকে। আজ production এর RAG system এ এটাই default retrieval এর setup, আর মেলানোর ধাপটা, reciprocal rank fusion, মাত্র তিন লাইনের code।

ভেতরে কীভাবে চলে

BM25, keyword ranking এর standard (Elasticsearch, OpenSearch, Lucene, Postgres extension এ ব্যবহার হয়), Part 1 এর project এর TF-IDF কে তিনভাবে উন্নত করে:

• IDF: rare শব্দের গুরুত্ব বেশি ("ERR-517" আছে একটা document এ; "the" সবগুলোতে)।
• Saturation (k1): একটা শব্দের প্রথমবার আসা অনেক গোনায়, পঞ্চমবার প্রায় কিছুই না। শুধু একটা শব্দ বারবার লিখে কোনো document জিততে পারে না।
• দৈর্ঘ্যের normalisation (b): ছোট, নির্দিষ্ট বিষয়ের document এ match লম্বা document এর একই match এর চেয়ে বেশি গোনায়।

Semantic search: query embed করো, যে document গুলোর cosine similarity সবচেয়ে বেশি সেগুলো নাও (আগের lesson)।

দুইটা মেলানো। BM25 এর score (0 থেকে মোটামুটি 20) আর cosine score (0.75 থেকে 0.9) আলাদা মাপে থাকে, তাই যোগ করা অর্থহীন। Reciprocal rank fusion (RRF) score বাদ দিয়ে শুধু অবস্থান ব্যবহার করে: প্রতিটা list প্রতিটা document কে দেয় 1 / (k + rank), সাধারণত k = 60, আর যোগফল শেষ ক্রম ঠিক করে। দুই list এরই উপরের দিকে থাকা document একটায় প্রথম আর অন্যটায় অনুপস্থিত document কে হারায়। কোনো tune লাগে না, score মেলাতে হয় না।

কোনটা কখন জেতে:

Query এর ধরন	ভালো
error code, order ID, product এর নাম, rare শব্দ	keyword
অন্যভাবে বলা কথা, প্রশ্ন, অন্য ভাষা, অর্থের ভুল	semantic
মিশ্র ("EID50 not working")	hybrid

আগে অনুমান করো

একটা document BM25 এ 1 নম্বর আর semantic search এ 20 নম্বর। আরেকটা দুইটাতেই 3 নম্বর। RRF (k = 60) এ কোনটা আগে আসবে?

যেটা দুইটাতেই 3 নম্বরযেটা BM25 এ 1 নম্বরসমানতাদের BM25 আর cosine score এর উপর নির্ভর করে

ছবিতে দেখো

Play

Code এ তিন রকম search

বারোটা help-centre এর টুকরো, error code, একটা promo code আর restaurant এর নাম সহ। জানা সঠিক answer সহ আটটা test query। হাতে লেখা BM25, local বহুভাষিক model থেকে আসল embedding, আর RRF। Table দেখায় প্রতিটা পদ্ধতিতে সঠিক document কোথায় আসে।

"""Keyword search (BM25), meaning search (embeddings), and fusing both with reciprocal rank fusion."""
import math
import re
from collections import Counter
import numpy as np
from embed import embed

DOCS = [
    "Error ERR-402 means the bKash payment was declined; try another wallet",
    "Error ERR-517 appears when the restaurant is closed for the day",
    "How to get your money back after a cancelled order",
    "Refunds go to the original payment method within 3 working days",
    "The rider could not find your address; update the pin on the map",
    "Delivery is late because of heavy rain or traffic",
    "Promo code EID50 gives 50 taka off orders above 500 taka",
    "Change your phone number from Profile > Settings",
    "The OTP SMS may take two minutes; check your network",
    "Food arrived cold? Report it within one hour for a credit",
    "Kacchi Bhai and Sultan's Dine are open until 11 pm",
    "Vegetarian dishes are marked with a green leaf icon",
]
QUERIES = [  # (query, index of the right document)
    ("ERR-517", 1),
    ("what does ERR-402 mean", 0),
    ("I want my cash returned", 2),
    ("my parcel is taking forever", 5),
    ("EID50 not working", 6),
    ("the biryani reached me cold", 9),
    ("is Sultan's Dine open now", 10),
    ("rider went to the wrong place", 4),
]

def tokenize(t):
    return re.findall(r"[a-z0-9]+(?:-[0-9]+)?", t.lower())

class BM25:
    """Keyword relevance: rare words count more, repeated words count less and less, long docs are damped."""
    def __init__(self, docs, k1=1.5, b=0.75):
        self.docs = [Counter(tokenize(d)) for d in docs]
        self.lens = [sum(c.values()) for c in self.docs]
        self.avg = sum(self.lens) / len(docs)
        df = Counter(w for c in self.docs for w in c)
        self.idf = {w: math.log(1 + (len(docs) - n + 0.5) / (n + 0.5)) for w, n in df.items()}
        self.k1, self.b = k1, b

    def scores(self, query):
        out = np.zeros(len(self.docs))
        for i, (c, n) in enumerate(zip(self.docs, self.lens)):
            for w in tokenize(query):
                tf = c.get(w, 0)
                out[i] += self.idf.get(w, 0) * tf * (self.k1 + 1) / (tf + self.k1 * (1 - self.b + self.b * n / self.avg))
        return out

bm25 = BM25(DOCS)
D = embed(DOCS)

def rank_keyword(q):
    return list(np.argsort(-bm25.scores(q), kind="stable"))

def rank_semantic(q):
    return list(np.argsort(-(D @ embed([q], kind="query")[0]), kind="stable"))

def rank_hybrid(q, k=60):
    """Reciprocal rank fusion: each list votes 1/(k + rank); no score scaling needed."""
    fused = Counter()
    for ranking in (rank_keyword(q), rank_semantic(q)):
        for r, i in enumerate(ranking):
            fused[i] += 1 / (k + r + 1)
    return [i for i, _ in fused.most_common()]

print(f"{'query':<30} {'keyword':>8} {'semantic':>9} {'hybrid':>7}   (rank of the right document)")
totals, worst = Counter(), Counter()
for q, want in QUERIES:
    ranks = {name: fn(q).index(want) + 1 for name, fn in
             (("keyword", rank_keyword), ("semantic", rank_semantic), ("hybrid", rank_hybrid))}
    for name, r in ranks.items():
        totals[name] += r == 1
        worst[name] = max(worst[name], r)
    print(f"{q:<30} {ranks['keyword']:>8} {ranks['semantic']:>9} {ranks['hybrid']:>7}")
print(f"{'right document first':<30} {totals['keyword']:>6}/8 {totals['semantic']:>7}/8 {totals['hybrid']:>5}/8")
print(f"{'worst rank':<30} {worst['keyword']:>8} {worst['semantic']:>9} {worst['hybrid']:>7}")

Output:

query                           keyword  semantic  hybrid   (rank of the right document)
ERR-517                               1         1       1
what does ERR-402 mean                1         1       1
I want my cash returned               3         1       2
my parcel is taking forever           1         4       1
EID50 not working                     2         1       1
the biryani reached me cold           1         1       1
is Sultan's Dine open now             1         1       1
rider went to the wrong place         1         1       1
right document first                6/8       7/8     7/8
worst rank                            3         4       2

কী দেখলাম:

• Code আর নাম এখানে দুইটাতেই কাজ করে, কারণ এই embedding model "ERR-517" আর "EID50" এর মতো string দেখেছে। যে domain এর ID সে দেখেনি (ভেতরের SKU, আইনের ধারা নম্বর), সেখানে embedding প্রায়ই মিস করে আর BM25 করে না।
• "I want my cash returned": কোনো document এ "cash" নেই, তাই BM25 সঠিকটাকে 3 নম্বরে রাখে। Semantic search 1 নম্বরে পায়।
• "my parcel is taking forever": semantic search সঠিক document টাকে 4 নম্বরে রাখে; BM25 পায় 1 নম্বরে, শুধু "is" মিলিয়ে। এটা ভাগ্য, বোঝা না: BM25 ভুল কারণে ঠিক হতে পারে, আর বড় corpus এ সেই ভাগ্য ফুরিয়ে যায়।
• Hybrid 8 এর 7 টায় প্রথম, semantic এর মতো, কিন্তু তার সবচেয়ে খারাপ rank 2, keyword এর 3 আর semantic এর 4 এর জায়গায়। RAG এর জন্য এই সংখ্যাটাই জরুরি: সঠিক document প্রথম 3 এ থাকলে model সেটা পড়তে পায়।
• 8 টা query তে এই সংখ্যাগুলো একটা প্রদর্শন, benchmark না (Part 1 এর statistics)। Part 8 ঠিকঠাক retrieval evaluation বানায়।

Production এ যা মাথায় রাখবে

• Hybrid দিয়ে শুরু করো। বেশিরভাগ search engine আর vector database (Elasticsearch, OpenSearch, Weaviate, Qdrant, pgvector + full-text সহ Postgres) দুইটাই আর RRF সরাসরি দেয়।
• BM25 এর জন্য tokenizer ঠিক করো। "ERR-517" এর মতো code, বাংলা text আর Banglish এর দরকার বুদ্ধিমান ভাগ; যে tokenizer "-517" বা সব বাংলা অক্ষর ফেলে দেয় ([a-z] যেমন করে), সে চুপচাপ keyword search ভেঙে দেয়।
• বেশি তোলো, তারপর rerank করো। Hybrid থেকে প্রথম 50 নাও, তারপর একটা cross-encoder দিয়ে নতুন করে সাজাও (পরের lesson), আর প্রথম 5 টা LLM কে দাও।
• Data বললে list গুলোকে weight দাও। কিছু system weighted RRF ব্যবহার করে (ধরো 0.7 semantic, 0.3 keyword), তোমার query set এ মেপে বাছা, আন্দাজে না।
• দুইটা index একসাথে রাখো। প্রতিটা document update কে keyword index আর vector index দুইটাতেই পৌঁছাতে হবে, নইলে result গুলো বিভ্রান্তিকরভাবে আলাদা হবে।

এক কথায়

BM25 হুবহু code, নাম আর rare শব্দ ধরে; embedding ধরে অর্থ আর অন্য ভাষা; hybrid search দুইটাই চালিয়ে reciprocal rank fusion দিয়ে মেলায়, প্রতিটা list থেকে 1/(60 + rank), যেটার কোনো score মেলানো লাগে না আর সঠিক document কে খুব কমই অনেক নিচে ফেলে রাখে।

নিজে করে দেখো

"taka ferot chai" query টা যোগ করো (Banglish এ "I want money back", সঠিক answer: document 2) আর এমন একটা query যেটায় একটা order ID আছে যা শুধু একটা document এ আছে (একটা document যোগ করো "Order 90817 was refunded on 3 March")। চালানোর আগে আন্দাজ করো প্রতিটায় কোন পদ্ধতি জিতবে, তারপর মিলিয়ে নাও।

Answer

"taka ferot chai" এর সাথে কোনো document এর কোনো English শব্দ মেলে না, তাই BM25 খুঁজে পায় না (প্রতিটা score 0 আর ranking এলোমেলো); semantic search এর একটা সুযোগ আছে, model Banglish কতটা সামলায় তার উপর নির্ভর করে। "90817" উল্টো: BM25 হুবহু token টা মেলায়, অথচ embedding model একটা এলোমেলো সংখ্যা দেখে আর document টাকে নিচে রাখতে পারে। Hybrid এর উচিত দুইটাকেই উপরের কয়েকটার মধ্যে রাখা, ঠিক এজন্যই এটা নিরাপদ default। আসল rank দেখতে চালিয়ে নাও।