Project: Find Similar Sentences with NumPy

কী বানাবে

একটা support team এর কাছে একই প্রশ্ন বারবার আসে। Customer যখন লেখে "how do I get a refund", help widget এর উচিত আগে থেকে থাকা সবচেয়ে কাছের answer গুলো দেখানো। তুমি বানাবে এর পেছনের search টা: একটা sentence দাও, একটা list থেকে সবচেয়ে মিলে যাওয়া sentence গুলো score সহ সাজিয়ে ফেরত পাও।

ব্যবহার করবে শুধু NumPy আর এই part এর ধারণাগুলো: sentence হবে vector, মিল মাপবে cosine দিয়ে, আর সব sentence একসাথে score করা মানে একটা matrix multiply। শেষে এটাও দেখবে এই পদ্ধতি ঠিক কোথায় ভেঙে পড়ে, আর embedding model (Part 5) কেন আছে সেটা ওখান থেকেই বুঝবে।

যা আগে জানা লাগবে

• Vectors and Matrices: dot product, cosine similarity, shape।
• Probability and Statistics: IDF formula টা "যত rare, তত বেশি তথ্য" হিসেবে পড়তে পারার মতো।
• NumPy install করা Python (pip install numpy)।

Architecture

Play

সব search engine এর মতো দুইটা phase:

Phase	কখন চলে	খরচ
Index	একবার, sentence বদলালে	প্রতিটা sentence tokenize, count, weight আর normalize
Query	প্রতিটা search এ	একটা query কে vector বানানো, একটা matrix multiply, একটা sort

Query সস্তা রাখার কৌশল: index বানানোর সময়ই প্রতিটা row কে length 1 করে রাখো। তখন cosine similarity মানে শুধু dot product, আর সবগুলো একসাথে মানে matrix @ query।

ধাপে ধাপে বানাও

Step 1: tokenize। Text ছোট হাতের করো, শুধু অক্ষরের টুকরোগুলো রাখো। Punctuation আর বড় ছোট হাতের পার্থক্য আর গোনায় আসে না: "Password?" আর "password" একই শব্দ।

Step 2: vocabulary। সব sentence এর আলাদা আলাদা শব্দ জড়ো করো, প্রতিটাকে একটা column নম্বর দাও। Sort করে নিলে প্রতিবার চালালে column একই থাকে।

Step 3: count matrix। প্রতি sentence এ একটা row, প্রতি শব্দে একটা column, প্রতিটা ঘরে সেই শব্দ কতবার এসেছে। একে বলে bag of words: শব্দের ক্রম ফেলে দেওয়া হয়, থাকে শুধু গোনা।

Step 4: IDF weight। "how", "do", "i", "my" এর মতো শব্দ সবখানে আছে, তাই এগুলো মিলে গেলে তেমন কিছু বোঝা যায় না। Inverse document frequency প্রতিটা শব্দকে একটা weight দেয়: অনেক sentence এ থাকলে ছোট, অল্প কয়েকটায় থাকলে বড়: log((1 + n) / (1 + df)) + 1, এখানে df হলো কয়টা sentence এ শব্দটা আছে। প্রতিটা column কে তার weight দিয়ে গুণ করো। Count × IDF কে বলে TF-IDF।

Step 5: normalize। প্রতিটা row কে তার length দিয়ে ভাগ করো। খালি row সামলাও: যে sentence এর একটা শব্দও vocabulary তে নেই, সেটা শূন্য দিয়ে ভাগ হয়ে NaN দেবে।

Step 6: query। Query কে একই step 1, 3, 4, 5 দিয়ে পার করাও (একই vocabulary আর weight দিয়ে), গুণ করো, sort করো, প্রথম k টা ফেরত দাও।

পুরো module টা:

"""Find similar sentences with nothing but NumPy: bag of words, TF-IDF, cosine, top-k."""
import re
import numpy as np

DOCS = [
    "How do I reset my password",
    "I forgot my password and cannot log in",
    "Change the email on my account",
    "The app crashes when I open the camera",
    "Camera does not work after the update",
    "How do I delete my account",
    "Refund for a cancelled order",
    "My order arrived late and the box was damaged",
    "Where is my order",
    "Cancel my order and give me a refund",
    "How do I change my phone number",
    "How do I track my parcel",
    "How do I contact support",
]

def tokenize(text):
    return re.findall(r"[a-z]+", text.lower())

def build_vocab(docs):
    words = sorted({w for d in docs for w in tokenize(d)})
    return {w: i for i, w in enumerate(words)}

def count_matrix(docs, vocab):
    m = np.zeros((len(docs), len(vocab)))
    for row, d in enumerate(docs):
        for w in tokenize(d):
            if w in vocab:  # words never seen while building the vocabulary are dropped
                m[row, vocab[w]] += 1
    return m

def idf_weights(counts):
    df = (counts > 0).sum(axis=0)              # how many docs contain each word
    return np.log((1 + len(counts)) / (1 + df)) + 1

def normalize(m):
    norms = np.linalg.norm(m, axis=1, keepdims=True)
    norms[norms == 0] = 1                      # an empty row stays all zeros, no NaN
    return m / norms

class Index:
    def __init__(self, docs, use_idf=True):
        self.docs = docs
        self.vocab = build_vocab(docs)
        counts = count_matrix(docs, self.vocab)
        self.idf = idf_weights(counts) if use_idf else np.ones(len(self.vocab))
        self.matrix = normalize(counts * self.idf)  # (n_docs, n_words), each row length 1

    def search(self, query, k=3):
        q = normalize(count_matrix([query], self.vocab) * self.idf)[0]
        scores = self.matrix @ q                    # one matrix multiply = every cosine at once
        top = np.argsort(-scores, kind="stable")[:k]
        return [(float(scores[i]), self.docs[i]) for i in top]

একটা script যেটা প্রতিটা step চালায় আর plain count এর সাথে TF-IDF মিলিয়ে দেখায়:

from search import DOCS, Index, build_vocab, count_matrix, tokenize

print("step 1  tokens:", tokenize("How do I reset my Password?"))
vocab = build_vocab(DOCS)
print("step 2  vocabulary size:", len(vocab))
counts = count_matrix(DOCS, vocab)
print("step 3  count matrix shape:", counts.shape)

for use_idf in (False, True):
    index = Index(DOCS, use_idf=use_idf)
    print(f"\nstep 4  {'TF-IDF' if use_idf else 'plain counts'}")
    for query in ["how do i get a refund", "i can't log in", "automobile insurance"]:
        print(f"  query: {query!r}")
        for score, doc in index.search(query, k=2):
            print(f"    {score:.3f}  {doc}")

Output:

step 1  tokens: ['how', 'do', 'i', 'reset', 'my', 'password']
step 2  vocabulary size: 48
step 3  count matrix shape: (13, 48)

step 4  plain counts
  query: 'how do i get a refund'
    0.600  How do I contact support
    0.548  How do I reset my password
  query: "i can't log in"
    0.612  I forgot my password and cannot log in
    0.258  How do I contact support
  query: 'automobile insurance'
    0.000  How do I reset my password
    0.000  I forgot my password and cannot log in

step 4  TF-IDF
  query: 'how do i get a refund'
    0.468  Refund for a cancelled order
    0.388  Cancel my order and give me a refund
  query: "i can't log in"
    0.626  I forgot my password and cannot log in
    0.107  How do I reset my password
  query: 'automobile insurance'
    0.000  How do I reset my password
    0.000  I forgot my password and cannot log in

কী দেখলাম:

• 13 টা sentence থেকে 48 টা আলাদা শব্দ, তাই index হলো (13, 48) এর matrix। প্রতিটা sentence 48 dimension এর একটা vector, বেশিরভাগ ঘরই শূন্য।
• Plain count "how do i get a refund" এ ভুল করে। উপরে এসেছে "How do I contact support" আর "How do I reset my password", কারণ "how", "do", "i" মিলে গেছে। Refund এর sentence গুলো হেরে গেছে।
• TF-IDF ঠিক করে দেয়। চারটা FAQ লাইন "How do I" দিয়ে শুরু, তাই ওই শব্দগুলোর weight কম, আর "refund" (মাত্র 2 টা sentence এ আছে) বেশি weight পায়। এখন refund এর দুইটা sentence ই উপরে।
• "automobile insurance" সব জায়গায় 0.000 পায়। এর একটা শব্দও vocabulary তে নেই, তাই vector টা পুরো শূন্য। যে result গুলো "এসেছে" সেগুলো স্রেফ প্রথম দুইটা row। Bag of words অর্থ বোঝে না: "car" আর "automobile" ও একে অপরের সাথে 0 পাবে।

Test করো

এই search এর যেকোনো version কে তিনটা জিনিস মানতেই হবে:

from search import DOCS, Index

index = Index(DOCS)

def test_exact_sentence_ranks_first_with_score_one():
    for doc in DOCS:
        score, top = index.search(doc, k=1)[0]
        assert top == doc and abs(score - 1) < 1e-9

def test_unknown_words_give_zero_not_nan():
    for score, _ in index.search("zzz qqq", k=3):
        assert score == 0

def test_scores_are_sorted():
    scores = [s for s, _ in index.search("refund my order", k=5)]
    assert scores == sorted(scores, reverse=True)

if __name__ == "__main__":
    for name, fn in list(globals().items()):
        if name.startswith("test_"):
            fn()
            print("pass", name)

pass test_exact_sentence_ranks_first_with_score_one
pass test_unknown_words_give_zero_not_nan
pass test_scores_are_sorted

• একটা sentence নিজেকে খুঁজে পায় score 1 নিয়ে। এটা fail করলে normalization বা vocabulary তে গণ্ডগোল।
• অজানা শব্দে 0, কখনো NaN না। এটা step 5 এর খালি row এর পাহারা। এটা ছাড়া একটা খালি query পুরো sort নষ্ট করে।
• Score গুলো sort হয়ে আসে। Check করা সস্তা, আর argsort এ উল্টো sort এর common ভুলটা ধরে ফেলে।

Unit test ছাড়াও কিছু আসল query আর তাদের প্রত্যাশিত answer এর একটা ছোট list রাখো (একটা ছোট্ট golden set, Part 8), আর প্রতিটা change এর পরে প্রথম result টা check করো।

Trade-offs

Choice	ভালো দিক	খরচ
Bag of words	সহজ, দ্রুত, ব্যাখ্যা করা যায়: কোন শব্দ মিলেছে দেখা যায়	অর্থ নেই: সমার্থক শব্দ 0 পায়, শব্দের ক্রম হারায় ("dog bites man" = "man bites dog")
Count এর বদলে TF-IDF	common শব্দ আর জরুরি শব্দগুলোকে চাপা দেয় না	weight corpus এর উপর নির্ভর করে; sentence যোগ করলে সব score বদলায়
Dense matrix	এক লাইনের NumPy তে scoring	13 × 48 কিছুই না, কিন্তু 10 লাখ sentence × 1 লাখ শব্দ মানে 400 GB, বেশিরভাগ শূন্য; আসল system এ sparse matrix বা inverted index লাগে
সবগুলো একে একে score	একদম সঠিক, tune করার মতো কোনো index নেই	প্রতিটা sentence এ খরচ বাড়ে; লাখ লাখ হলে Part 5 এর approximate search লাগবে

এই পদ্ধতি production এ এখনো বেঁচে আছে BM25 নামে, TF-IDF এর একটা উন্নত রূপ, Elasticsearch সহ অনেকে ব্যবহার করে। Part 5 এ এটাকে embedding এর সাথে মিলিয়ে hybrid search বানাবে, কারণ একটা যা মিস করে অন্যটা সেটা ধরে।

আরো এগিয়ে নাও

1. Bigram (পাশাপাশি দুই শব্দের জোড়া, যেমন "log in") আলাদা column হিসেবে যোগ করো, দেখো "i can't log in" এর ranking ভালো হয় কিনা।
2. Dense matrix এর বদলে scipy.sparse.csr_matrix ব্যবহার করো, আর 50,000 টা বানানো sentence দিয়ে দুইটার সময় মাপো।
3. একটা minimum score রাখো: 0.2 এর নিচে হলে "ভালো কোনো match নেই" বলো, "automobile insurance" এর মতো অপ্রাসঙ্গিক row না দেখিয়ে।
4. এমন তিনটা query লিখে রাখো যেখানে অর্থ জরুরি ("my parcel is late", "money back")। Part 5 এ embedding শেখার পরে আবার চালিয়ে তুলনা করো।