詞彙檢索
閱讀約需 98 分鐘 分鐘,12 節 中共有 13 個範例。
讀完本章後,你能從零開始建構詞彙搜尋:將商品文字轉成詞項、為詞項建立索引,並以 TF-IDF 與 BM25 為商品評分,且分數與 bm25s 函式庫逐筆一致。你也能判斷在文字處理與 BM25 參數上,哪些調整值得保留,做法是在訓練查詢上選擇,再於測試查詢上檢驗。
詞彙檢索(lexical retrieval)依商品與查詢共有的詞彙來尋找商品並排序。當購物者搜尋商店的家具與家居用品時,由它負責排序結果:採用 BM25,並透過 bm25s 函式庫實作。當購物者輸入 7qt slow cooker 或 pool floats 時,第 1 章的 BM25 結果並不理想。它在測試查詢上的平均 nDCG@10為 0.725,這顯示了結果不佳,卻無法說明原因,因為第 1 章是以 bm25s 的預設值,將它當作黑箱使用。本章打開這個黑箱。你會在商店的 12,000 項商品上親手重建每個步驟,並與 bm25s 核對,接著一次只更動一個步驟,並依商店的相關性判斷衡量每項更動。
每項更動都在 50 筆訓練查詢上選擇,並在 30 筆測試查詢上檢驗。在查看任何測試結果之前,本章先確定在測試查詢上要進行的比較。共有五項,每項都與未做該更動的同一搜尋相比:
由於有五項事先規劃的比較,本書的規則將門檻設為 p 值 0.01。若成對排列檢定得出的 p 值低於此門檻,即確認該項增益成立。每項比較也會報告成對 t 檢定與 99% 自助法區間,並說明兩者是否與排列檢定的結論一致。
將商品文字切分成詞項
搜尋從不直接比較原始字串。查詢與每項商品的文字,都會先經過相同的處理步驟。將文字切成片段,得到詞元(token)。轉成小寫,使 Chair 與 chair 成為同一個詞元。移除停用詞(stop words),也就是 the 與 with 這類極常見的詞,便留下搜尋用來比較的詞項(term),而目錄中所有的詞項構成其詞彙表(vocabulary)。商品只能憑雙方共有的詞項與查詢相符,因此在任何評分開始之前,這些步驟就已決定了什麼能夠相符。
執行商店 BM25 的 bm25s 在這裡做了三項選擇。它會轉成小寫。它以規則運算式 (?u)\b\w\w+\b 保留每一段由兩個以上單字字元(字母、數字或底線)組成的字串,其說明文件稱這是 scikit-learn 的 CountVectorizer 所用的方法。它還會移除 33 個英文停用詞,其中包括 no、not、with 與 for。除非你傳入詞幹還原器(stemmer),否則它不會做詞幹還原(bm25s tokenizer、stop words)。若要逐步檢視這些步驟,可以手寫出來,將結果與 bm25s.tokenize 在每項商品上的輸出比對,並讓訓練查詢 7qt slow cooker 通過這些步驟:
1"""Splits product text into terms by hand, checks the split against bm25s on every product, then shows what the store's sizes and a negation turn into. The prose's point rests on the line that counts products tokenized differently, and on the lines that count products with the term 7qt and products whose text says 7 qt."""2import re34import bm25s5from bm25s.stopwords import STOPWORDS_EN67from lib.lexical import LexicalSearch8from lib.store import load_products, load_queries, product_text, qrels910# two or more word characters (letters, digits or underscores): a single character, such as the 7 in 7 qt, is no token11TOKEN = re.compile(r"(?u)\b\w\w+\b")12STOPWORDS = set(STOPWORDS_EN) # the 33 English stop words bm25s removes131415def tokenize(text, pattern=TOKEN):16 """Lowercase, split into tokens, and drop stop words."""17 return [token for token in pattern.findall(text.lower()) if token not in STOPWORDS]181920products, queries = load_products(), load_queries()21texts = product_text(products).tolist()22by_hand = [tokenize(text) for text in texts]23# bm25s's own split, with stopwords="en": the same 33 words as STOPWORDS above24with_bm25s = bm25s.tokenize(texts, stopwords="en", return_ids=False, show_progress=False)25print("products tokenized differently:", sum(mine != theirs for mine, theirs in zip(by_hand, with_bm25s)))26print()27query = queries.at[62, "query"] # a train query28print("query 62:", query, "->", tokenize(query))29print("product 1:", products.at[1, "name"], "->", tokenize(products.at[1, "name"]))30print("products with the term 7qt:", sum("7qt" in terms for terms in by_hand))31# a 7 on its own: the lookbehind skips 27 qt and 3.7 qt, which are other sizes32print("products whose text says 7 qt:", sum(re.search(r"(?<![\d.])7 qt\b", text.lower()) is not None for text in texts))33grades = qrels("train")[62]34print("exact products judged for query 62:", sum(grade == 2 for grade in grades.values()))35top_10 = LexicalSearch(products).search(query, k=10).index # chapter 1's BM2536print("exact products in bm25's top 10:", sum(grades.get(product_id) == 2 for product_id in top_10))37digits_apart = re.compile(r"(?u)\d+|[^\W\d_]+") # keeps single digits; 7qt -> 7, qt38changed = queries["query"].map(lambda text: tokenize(text) != tokenize(text, digits_apart))39for split in ["train", "test"]:40 print(f"{split} queries whose terms change with digits apart:", changed[queries["split"] == split].sum())41print()42print("probe:", "rug not wool", "->", tokenize("rug not wool")) # written for this chapter43# whole words, so note and nothing don't count44print("queries with not or no:", queries["query"].str.contains(r"\b(?:not|no)\b").sum())
python tokenize-product-text.pyproducts tokenized differently: 0
query 62: 7qt slow cooker -> ['7qt', 'slow', 'cooker']
product 1: all-clad 7 qt . slow cooker -> ['all', 'clad', 'qt', 'slow', 'cooker']
products with the term 7qt: 0
products whose text says 7 qt: 8
exact products judged for query 62: 9
exact products in bm25's top 10: 1
train queries whose terms change with digits apart: 4
test queries whose terms change with digits apart: 0
probe: rug not wool -> ['rug', 'wool']
queries with not or no: 0
手寫的詞元切分器與 bm25s 切分結果不同的商品數是 0,所以問題不在其中任何一個,而在於它們共用的規則。輸入 7qt slow cooker 的購物者想要 7 夸脫的慢燉鍋,而 7qt 確實會保留為一個詞元。但它與 0 項商品相符,因為商品文字把尺寸分開寫,在 8 項商品中寫成 7 qt,而詞元切分器會丟掉只有一個字元的 7。於是尺寸在比對的兩側都不影響排名,BM25 無法區分 7 夸脫的慢燉鍋與其他慢燉鍋。在評審針對此查詢標為完全相符的 9 項商品中,BM25 的前 10 名包含 1 項。
若採用保留單一數字、並將數字與單位分開的模式 (?u)\d+|[^\W\d_]+,會改變 4 筆訓練查詢與 0 筆測試查詢的詞項,因此商店的評審判斷對它幾乎無從評估。
停用詞表也會以同樣方式出錯,而且 bm25s 不會報錯。以 rug not wool 為例,這是一個探測查詢(probe query):為本章撰寫、用來測試某種行為的查詢,並非商店的查詢。它會變成 rug wool,所以羊毛地毯會同時符合其兩個詞項。評審判斷只能在含有否定的查詢上衡量這種損害,而商店的查詢中有 0 筆含有 not 或 no。搜尋系統已從長停用詞表轉為短表或完全不用,部分原因是停用詞在某些查詢中帶有意義,部分原因是保留它們的成本已變得很低(Manning et al., 2008)。
實用原則: 在調整任何評分之前,先印出查詢與商品轉換後的詞項,並讓兩者使用同一個詞元切分器。如同商店的做法,先從 bm25s 的預設值開始。當購物者輸入尺寸、數量或型號時,使用保留單一數字、並將數字與其單位分開的詞元模式,例如上述模式。當他們輸入否定詞時,關閉停用詞表。每一項都是對搜尋的更動,因此在保留之前,請先在訓練查詢上衡量,並以測試查詢檢驗。
建立反向索引
要為這些詞彙組成的查詢計分,搜尋需要取得包含各個詞彙的商品。對小型樣本而言,每次查詢都讀過每個商品的文字還行得通,但面對數百萬筆商品的目錄就不行了。反向索引(inverted index)把文字的方向倒過來:它為每個詞彙保存一份包含該詞彙的商品清單,稱為該詞彙的倒排清單(postings)(Manning et al., 2008)。倒排清單會連同每個商品一併記錄詞頻(term frequency),也就是該詞彙在該商品文字中出現的次數。一個詞彙的倒排清單中所含的商品數,則是它的文件頻率(document frequency):搜尋引擎把所搜尋的項目稱為文件,在本書中它們就是商品。一次查詢只會讀取自身詞彙的倒排清單。
商店的索引把每個詞彙對應到一個字典,其內容是商品 ID 與詞頻。索引也保存每個商品以詞彙數計的長度,這是 BM25 所需要的資料。建立索引只需對每個商品的文字走訪一遍,並使用上一節的斷詞器。接著,程式碼查詢訓練查詢 7qt slow cooker 的各個詞彙:
1"""Builds the store's inverted index by hand from each product's tokenized text, then looks up a train query's terms in it. The prose's point rests on the lines that count products with every query term and with any query term, and on the line for the product code."""2from collections import Counter34from lib.lexical_by_hand import tokenize5from lib.store import load_products, load_queries, product_text67postings = {} # {term: {product_id: how many times the term occurs in that product}}8lengths = {} # {product_id: number of terms}9for product_id, text in product_text(load_products()).items():10 terms = tokenize(text)11 lengths[product_id] = len(terms)12 for term, count in Counter(terms).items():13 postings.setdefault(term, {})[product_id] = count1415print(f"vocabulary: {len(postings):,} terms")16print(f"average product length: {sum(lengths.values()) / len(lengths):.1f} terms")17# (product ID, term frequency) pairs, starting from product 118print("postings for cooker, first 3:", list(postings["cooker"].items())[:3])19print()20query = load_queries().at[62, "query"]21for term in tokenize(query):22 print(f"products with {term}:", len(postings.get(term, {})))23found = [set(postings.get(term, {})) for term in tokenize(query)]24print("products with any query term:", len(set.union(*found)))25print("products with every query term:", len(set.intersection(*found)))26print("products with w003096809:", len(postings.get("w003096809", {}))) # the code in query 205
python inverted-index-by-hand.pyvocabulary: 20,393 terms
average product length: 50.3 terms
postings for cooker, first 3: [(1, 3), (2, 2), (115, 1)]
products with 7qt: 0
products with slow: 157
products with cooker: 141
products with any query term: 158
products with every query term: 0
products with w003096809: 0
商店的 12,000 個商品使用了 20,393 terms,而一個商品的文字平均為 50.3 terms。cooker 的倒排清單中,每一對資料都是商品 ID 與詞頻。第一筆是商品 1,也就是斷詞器一節中的 7 qt 慢燉鍋。
對於 7qt slow cooker,倒排清單列出 slow 有 157 個商品、cooker 有 141 個、7qt 有 0 個,合計涵蓋 158 個商品。為這個查詢計分時,只需讀取這些商品。同時含有三個詞彙的商品有 0 個,因為沒有任何商品含有 7qt。因此,布林 AND 查詢(只回傳包含所有查詢詞彙的商品)對這個查詢不會回傳任何結果。若像 BM25 那樣,對每個含有任一詞彙的商品計分,仍會回傳慢燉鍋,並交由分數決定哪些排在前面。
**實用原則:**查詢結果看起來不對時,先在索引中查詢它的詞彙,再決定是否更動計分方式。沒有倒排清單的詞彙,例如 7qt,無論計分器如何運作都無法對任何商品有所幫助,因此應修正斷詞器或查詢。對於購物者輸入的查詢,應比對含有任一詞彙的商品,而非全部詞彙,否則只要有一個詞彙無法比對,結果就會是空的。正式服務請使用函式庫的索引,並另外保留像這樣的小型索引,用來檢查某個詞彙比對到哪些商品。
以 TF-IDF 為詞項加權
並非每一次比對的價值都相同。有兩個概念可用來加權。一個詞項在商品文字中出現得愈頻繁,該商品就愈可能是在談論這個詞項:這就是詞項頻率(term frequency,tf)。而且,比對到罕見詞項所提供的資訊,多於比對到常見詞項。Karen Spärck Jones 提出依據包含某詞項的文件數量來為詞項加權,使得「比對到較不常見、較為特定的詞項,其價值高於比對到常見詞項」(Spärck Jones, 1972;免費重印本)。這個權重後來成為逆向文件頻率(inverse document frequency,IDF):商品總數除以該詞項的文件頻率後取對數,罕見詞項的值高,常見詞項的值低(Manning et al., 2008)。TF-IDF 會將每個查詢詞項的 tf 與 IDF 相乘,再加總(Manning et al., 2008):
idf(t) = ln(N / df(t)) N products, df(t) of them contain t
tf-idf(q, d) = sum over query terms t of tf(t, d) × idf(t)
furniture 是這家商店商品中的常見詞項。TF-IDF 建立在反向索引之上。程式碼會顯示 furniture 的 IDF,以及訓練查詢 laundry basket with wheels 中各詞項的 IDF,接著列出 TF-IDF 對該查詢的前 3 名,並附上每項商品的分數與詞項頻率。最後,它用 TF-IDF 與 第 1 章所執行的 BM25 為全部 50 個訓練查詢評分:
1"""Computes TF-IDF over the inverted index, shows the IDF of each term of one train query and TF-IDF's top 3 for it, then scores every train query with TF-IDF and with BM25. The prose's point rests on the train nDCG@10 and judged@10 lines, and on the line that counts the queries where BM25 scores higher or lower."""2import math34import pandas as pd56from lib.lexical import LexicalSearch7from lib.lexical_by_hand import InvertedIndex, tokenize8from lib.metrics import evaluate9from lib.store import load_products, load_queries, product_text, qrels1011products, train, judgments = load_products(), load_queries("train"), qrels("train")12index = InvertedIndex(product_text(products))13n = len(index.lengths) # every product, the N in the IDF formula141516def tf_idf(query):17 """TF-IDF scores of the products that contain a query term, best first."""18 scores = {}19 for term in tokenize(query):20 postings = index.postings.get(term, {})21 # a term no product contains has no postings, so it adds nothing to any score22 idf = math.log(n / len(postings)) if postings else 0.023 for product_id, tf in postings.items():24 scores[product_id] = scores.get(product_id, 0.0) + tf * idf25 # stable: tied products keep the order in which they were first scored26 return pd.Series(scores, dtype=float).sort_values(ascending=False, kind="stable")272829# train query 36, by its ID; judgments grade 2, 1 and 0 as exact, partial and irrelevant30query, labels = train.at[36, "query"], {2: "exact", 1: "partial", 0: "irrelevant"}31for term in ["furniture"] + tokenize(query):32 print(f"idf of {term}: {math.log(n / len(index.postings[term])):.3f}")33print(f"\ntf-idf top 3 for {query!r}:")34for rank, (product_id, score) in enumerate(tf_idf(query).head(3).items(), start=1):35 counts = ", ".join(f"{term} {index.postings[term].get(product_id, 0)}" for term in tokenize(query))36 print(f" {rank} {score:4.1f} {labels[judgments[36][product_id]]:<8} {counts:<29} {products.at[product_id, 'name'][:22]}")37print()38# the top 100 of each scorer on every train query; bm25 is chapter 1's, from lib.lexical39runs = {"tf-idf": {query_id: list(tf_idf(text).index[:100]) for query_id, text in train["query"].items()},40 "bm25": LexicalSearch(products).run(train)}41results = {name: evaluate(run, judgments) for name, run in runs.items()} # one row per train query42for name, frame in results.items():43 print(f"{name} train ndcg@10: {frame['ndcg@10'].mean():.3f}")44 print(f"{name} train judged@10: {frame['judged@10'].mean():.3f}")45# rounded to three decimals, so a difference too small to show counts as a tie46change = (results["bm25"]["ndcg@10"] - results["tf-idf"]["ndcg@10"]).round(3)47print(f"train queries where bm25 scores higher, lower: {(change > 0).sum()}, {(change < 0).sum()}")
python tf-idf-by-hand.pyidf of furniture: 0.919
idf of laundry: 3.985
idf of basket: 3.925
idf of wheels: 4.839
tf-idf top 3 for 'laundry basket with wheels':
1 51.3 partial laundry 4, basket 9, wheels 0 dirty clothes basket ,
2 45.4 exact laundry 6, basket 3, wheels 2 laundry sorter basket
3 39.7 partial laundry 7, basket 3, wheels 0 weave laundry basket
tf-idf train ndcg@10: 0.579
tf-idf train judged@10: 0.836
bm25 train ndcg@10: 0.695
bm25 train judged@10: 0.930
train queries where bm25 scores higher, lower: 36, 10
TF-IDF 的第一名商品是partial,這是一個從未提到 wheels 的籃子,但它重複 basket 的次數比排在它之下的兩項商品都多。IDF 促成了這個結果。furniture 的 IDF 為 0.919,而查詢中的詞項,laundry 為 3.985,basket 為 3.925,wheels 為 4.839:它們較為罕見,而且彼此相近。IDF 如此接近時,重複出現的次數就壓過了缺少 wheels 的影響,分數也反映了這一點。三項商品中唯一提到 wheels 的完全符合商品,反而排在第二。在 TF-IDF 中,詞項頻率沒有上限,因此商品可以靠重複某個字詞而勝過另一項商品。
在訓練查詢上,TF-IDF 的平均 nDCG@10 為 0.579,BM25 則為 0.695;BM25 得分較高與較低的查詢數分別為 36, 10。TF-IDF 的 judged@10 為 0.836,BM25 則為 0.930;當某次執行的 judged@10 較低時,差距有一部分可能來自無人評判過的商品,而不是較差的商品。這項在訓練查詢上的比較,能告訴你該以哪一種評分器為基礎,而本書把證據留給測試查詢。
實用原則: 在任何詞彙式評分器中都以 IDF 為詞項加權,因為比對到罕見詞項是較好的證據。不要以原始 TF-IDF 為商品排名:應限制重複詞項所能增加的分數,並針對長文字加以校正,這正是 BM25 的做法。TF-IDF 則留給解釋排名時使用,因為你可以直接讀出每個詞項的 tf 與 idf。
此部分尚未翻譯,因此以英文呈現。
Rebuild BM25 by hand to match bm25s
BM25 keeps IDF and changes how term frequency counts, in two ways. With saturation, each repeat of a term adds less than the one before, and no number of repeats can push the term's contribution past a ceiling (Robertson and Zaragoza, 2009). The parameter k1 sets how quickly a term approaches it. With length normalization, a long text, which has more chances to contain any term, gets its term frequencies discounted. The parameter b sets how much: "b = 1 will perform full document-length normalisation, while b = 0 will switch normalisation off" (Robertson and Zaragoza). In the form bm25s computes by default (bm25s scoring):
idf(t) = ln(1 + (N − df(t) + 0.5) / (df(t) + 0.5))
bm25(q, d) = sum over query terms t of
idf(t) × tf(t, d) / (tf(t, d) + k1 × (1 − b + b × length(d) / average length))
Two details differ between textbooks and libraries. A common variant multiplies the fraction by k1 + 1, which grows every score by the same factor and so leaves the ranking unchanged (Robertson and Zaragoza, section 3.5.1). And Robertson's original IDF, without the 1 inside the logarithm, is negative for a term in more than half of the documents, so Lucene, an open-source search library, adds the 1 (Kamphuis et al., 2020). bm25s's default, method="lucene", is Lucene's formula computed with exact document lengths (bm25s README), where Lucene itself approximates them (Kamphuis et al.). "BM25" names a family of such variants, and a study of eight of them found no significant differences in effectiveness on three newswire collections (Kamphuis et al.).
Write the formula over the store's inverted index at bm25s's defaults, k1=1.5 and b=0.75, and check it against bm25s 0.3.16: first every product's score for each of the 80 queries, then the two rankings, by their top 100s and by nDCG@10:
1"""Writes BM25 by hand over the inverted index at bm25s's defaults, and checks every score and every ranking against bm25s. The prose's point rests on the IDF lines for the word your, the largest score difference, the same-top-100 line and the test nDCG@10 lines."""2import math34import pandas as pd56from lib.lexical import LexicalSearch7from lib.lexical_by_hand import InvertedIndex, tokenize8from lib.metrics import evaluate9from lib.store import load_products, load_queries, product_text, qrels1011products, queries = load_products(), load_queries()12index, library = InvertedIndex(product_text(products)), LexicalSearch(products) # by hand, and bm25s as chapter 1 uses it13# k1 and b at bm25s's defaults14n, k1, b = len(index.lengths), 1.5, 0.75151617def bm25(query):18 scores = {}19 for term in tokenize(query):20 df = len(index.postings.get(term, {}))21 # Lucene's IDF: the 1 in the logarithm keeps it positive, even for a term in most products22 idf = math.log(1 + (n - df + 0.5) / (df + 0.5))23 for product_id, tf in index.postings.get(term, {}).items():24 # length normalization: a product of average length gets a factor of 125 length = 1 - b + b * index.lengths[product_id] / index.average_length26 scores[product_id] = scores.get(product_id, 0.0) + idf * tf / (tf + k1 * length)27 return pd.Series(scores, dtype=float)282930df = len(index.postings["your"])31print(f"products with your: {df:,}")32# Robertson's IDF has no 1 in the logarithm, so it goes negative for a term in over half the products33print(f"robertson idf of your: {math.log((n - df + 0.5) / (df + 0.5)):.3f}")34print(f"lucene idf of your: {math.log(1 + (n - df + 0.5) / (df + 0.5)):.3f}")35for tf in [1, 2, 4, 9]: # one term, in a product of average length36 print(f"term weight at tf {tf}: {tf / (tf + k1):.3f}")37# products that share no term with a query score 0, as bm25s gives them38gaps = [(bm25(query).reindex(products.index, fill_value=0) - library.retriever.get_scores(tokenize(query))).abs().max()39 for query in queries["query"]]40print(f"\nlargest score difference from bm25s: {max(gaps):.0e}")41print("bm25s score type:", library.retriever.get_scores(["chair"]).dtype)42ranked = {query_id: list(bm25(query).sort_index().sort_values(ascending=False, kind="stable").index[:100])43 for query_id, query in queries["query"].items()} # equal scores in product_id order44library_ranked = library.run(queries) # lib.lexical also orders equal scores by product_id45print("same top 100 for every query:", "yes" if ranked == library_ranked else "no")46for split in ["train", "test"]:47 for name, run in [("by hand", ranked), ("with bm25s", library_ranked)]:48 print(f"{split} ndcg@10 {name}: {evaluate(run, qrels(split))['ndcg@10'].mean():.3f}")
python bm25-by-hand.pyproducts with your: 6,135
robertson idf of your: -0.045
lucene idf of your: 0.671
term weight at tf 1: 0.400
term weight at tf 2: 0.571
term weight at tf 4: 0.727
term weight at tf 9: 0.857
largest score difference from bm25s: 1e-06
bm25s score type: float32
same top 100 for every query: yes
train ndcg@10 by hand: 0.695
train ndcg@10 with bm25s: 0.695
test ndcg@10 by hand: 0.725
test ndcg@10 with bm25s: 0.725
The word your occurs in 6,135 of the 12,000 products. Robertson's original IDF gives it -0.045, and Lucene's gives it 0.671. A negative IDF would make a match on a word lower a product's score. The term weights show saturation: in a product of average length, one occurrence of a term earns 0.400 of its IDF, and nine earn 0.857.
The scores match. The largest difference over every product and query is 1e-06, at the precision of the float32 numbers bm25s returns. Matching scores don't settle a ranking on their own, though: where scores are equal, an implementation still has to choose which tied product comes first. Ours lists tied products by product ID. So does the book's shared BM25, lib.lexical from chapter 1, which takes every product's score from bm25s and then orders equal scores by product ID. Asked whether both give the same top 100 for every query, the example answers yes.
The rankings follow from the scores. On the train queries, the mean nDCG@10 is 0.695 by hand and 0.695 with bm25s; on the test queries, 0.725 and 0.725.
Working rule: Serve BM25 from a library such as bm25s, and keep a small version you wrote yourself to check it, because yours shows where every part of a score comes from. Compare two implementations by their scores first, then by their rankings. Before you compare rankings, break ties the same way in both, by product ID as the book's BM25 does, or tied products alone can make two correct implementations rank differently. When two BM25 systems rank differently, compare their tokenizers before their formulas. The study of variants held tokenization and stop words fixed, and notes that more mundane settings, such as the choice of stop words, often make larger differences than the formula (Kamphuis et al.).
此部分尚未翻譯,因此以英文呈現。
Stem terms so word forms match
A shopper types pool floats, and a product says float or floating. To the tokenizer, those are different terms, so they don't match. Stemming cuts common endings off words, so that the forms of a word share one term, its stem. Martin Porter designed his suffix-stripping algorithm for retrieval, and in his test it reduced a vocabulary of 10,000 words to 6,370 stems, a cut of about one third (Porter, 1980). His page recommends its successor, the Snowball English or Porter2 stemmer (Porter), which stems slightly over 5% of words differently (Snowball). Stemming trades precision for recall. It raises recall while harming precision, and it helps some queries a lot while hurting others as much (Manning et al., 2008).
A crude stemmer takes a few lines. Write one by hand that cuts -ing, -es, -ed or -s when at least three letters remain, and compare it with the Snowball English stemmer from PyStemmer, which bm25s's tokenizer recommends (bm25s tokenizer) and the book pins at 3.1.0 (PyStemmer). Then count the products whose text contains a word, and those whose text contains its stem:
1"""Compares a hand-written suffix stripper with the Snowball English stemmer on a few words, then counts the products whose text contains each word and its stem. The prose's point rests on the counts for floats and for molding, and on the vocabulary reduction line."""2import Stemmer34from lib.lexical_by_hand import InvertedIndex5from lib.store import load_products, product_text678def strip_suffix(word):9 """A stemmer by hand: cut the first ending that matches, if at least three letters are left."""10 # the first ending that matches is cut, so the order matters: "es" is tried before "s"11 for ending in ["ing", "es", "ed", "s"]:12 # at least three letters must remain, so short words such as "is" keep their endings13 if word.endswith(ending) and len(word) - len(ending) >= 3:14 return word[: -len(ending)]15 return word161718stemmer = Stemmer.Stemmer("english") # Snowball English, also called Porter219words = ["floats", "floating", "molding", "molded", "moldings", "shelves", "shelving", "shelf"]20for word, stem in zip(words, stemmer.stemWords(words)):21 print(f"{word}: snowball {stem}, by hand {strip_suffix(word)}")2223products = load_products()24text = product_text(products)25plain, stemmed = InvertedIndex(text), InvertedIndex(text, stem=True)26print()27for word in ["floats", "molding"]:28 print(f"products with {word}:", len(plain.postings[word]))29 print(f"products with the stem of {word}:", len(stemmed.postings[stemmer.stemWord(word)]))30# every product with a word whose stem is float: float, floats, floating and any other form31float_products = list(stemmed.postings["float"])32print("products with the stem of floats that say floating:", len(plain.postings["floating"].keys() & set(float_products)))33for product_class, count in products.loc[float_products, "product_class"].value_counts().head(2).items():34 print(f"products with the stem of floats in {product_class}: {count}")35print(f"vocabulary without stemming: {len(plain.postings):,} terms")36print(f"vocabulary with stemming: {len(stemmed.postings):,} terms")37print(f"vocabulary reduction: {1 - len(stemmed.postings) / len(plain.postings):.0%}")
python stemmer-merges-word-forms.pyfloats: snowball float, by hand float
floating: snowball float, by hand float
molding: snowball mold, by hand mold
molded: snowball mold, by hand mold
moldings: snowball mold, by hand molding
shelves: snowball shelv, by hand shelv
shelving: snowball shelv, by hand shelv
shelf: snowball shelf, by hand shelf
products with floats: 11
products with the stem of floats: 288
products with molding: 123
products with the stem of molding: 262
products with the stem of floats that say floating: 244
products with the stem of floats in Wall Mounted Shelves: 57
products with the stem of floats in Desks: 36
vocabulary without stemming: 20,393 terms
vocabulary with stemming: 15,258 terms
vocabulary reduction: 25%
The hand-written stemmer agrees with Snowball on every word but moldings, where it stops after cutting -s, and Snowball's rules go on to mold. Both turn shelves into shelv and leave shelf alone: rules that cut endings don't know that shelves is the plural of shelf.
The counts show both sides of the trade. floats is in 11 products and its stem in 288, but 244 of those say floating. The two most common product classes among them are wall-mounted shelves, with 57, and desks, with 36. So the stem reaches floating shelves as well as pool floats, and only the judgments can say which effect wins (next section).
molding occurs in 123 and its stem in 262, because mold also stands for molded, moldings and mold itself, a word with more than one meaning. The vocabulary shrinks by 25%, from 20,393 terms to 15,258 terms. Porter's test used different text and an earlier algorithm, so they don't compare directly.
To serve stemmed BM25 from bm25s, pass the same stemmer to bm25s.tokenize for the products and for every query. Then check that bm25s, given the same stemmer, scores like the hand-built index with stemming, InvertedIndex(text, stem=True) from lib.lexical_by_hand:
1"""Builds bm25s with the same stemmer as the hand-built index, then checks every score on every query against it. The prose's point rests on the line that prints the largest score difference from bm25s."""2import bm25s3import Stemmer45from lib.lexical_by_hand import InvertedIndex6from lib.store import load_products, load_queries, product_text78products, queries = load_products(), load_queries()9texts = product_text(products)10stemmer = Stemmer.Stemmer("english")1112library = bm25s.BM25() # k1=1.5, b=0.75, as in chapter 113# products and queries must go through the same stop list and stemmer, or their terms won't match14library.index(bm25s.tokenize(texts.tolist(), stopwords="en", stemmer=stemmer, show_progress=False),15 show_progress=False)16by_hand = InvertedIndex(texts, stem=True)1718gaps = []19for query in queries["query"]:20 tokens = bm25s.tokenize([query], stopwords="en", stemmer=stemmer, return_ids=False, show_progress=False)[0]21 scores = library.get_scores(tokens) # every product, in catalog order22 # search keeps only matching products, best first: reindex puts each in its catalog place, 0 for the rest23 gaps.append(abs(by_hand.search(query, k=len(products)).reindex(products.index, fill_value=0) - scores).max())24print("query terms for pool floats:", bm25s.tokenize(["pool floats"], stopwords="en", stemmer=stemmer,25 return_ids=False, show_progress=False)[0])26print(f"largest score difference from bm25s with a stemmer: {max(gaps):.0e}")
python bm25s-with-a-stemmer.pyquery terms for pool floats: ['pool', 'float']
largest score difference from bm25s with a stemmer: 2e-06
pool floats becomes pool and float, and the largest score difference over all products and queries is 2e-06, the same rounding as without stemming.
Working rule: Stem English product text and queries with the Snowball English stemmer, at indexing time and at query time alike: in bm25s, pass stemmer= to bm25s.tokenize on both sides. Read the products that a stem adds, as the floats counts do, before you trust a gain. When a stem merges words that your shoppers keep apart, such as molding and mold, keep a list of words you don't stem. For text in another language, use that language's stemmer.
在測試查詢上檢驗詞幹還原
詞幹還原以精確率換取召回率,因此只有相關性判斷能說明它對這個商店是否值得。是否採用詞幹還原,是根據 50 個訓練查詢決定的。這是本章五項規劃比較中的第一項,在 30 個測試查詢上執行。接著,將經過詞幹還原的索引與 BM25 一節中未經詞幹還原的索引相互比較:
1"""Compares the stemmed index with the unstemmed one on train and test queries, and runs the planned test comparison for stemming. The prose's point rests on the test permutation p and t-test p lines, and on the line that reports the query with the largest gain."""2from lib.lexical_by_hand import THRESHOLD, InvertedIndex, report_test_comparison3from lib.metrics import evaluate4from lib.store import load_products, load_queries, product_text, qrels56text = product_text(load_products())7indexes = {"without stemming": InvertedIndex(text), "with stemming": InvertedIndex(text, stem=True)}8scores = {split: {name: evaluate(index.run(load_queries(split)), qrels(split)) for name, index in indexes.items()}9 for split in ["train", "test"]}1011for split in ["train", "test"]:12 for name, frame in scores[split].items():13 print(f"{split} ndcg@10 {name}: {frame['ndcg@10'].mean():.3f}")14 print(f"{split} judged@10 {name}: {frame['judged@10'].mean():.3f}")15change = (scores["train"]["with stemming"]["ndcg@10"] - scores["train"]["without stemming"]["ndcg@10"]).round(3)16print(f"train queries better, worse: {(change > 0).sum()}, {(change < 0).sum()}") # for choosing, not evidence17for query_id in [410, 359]: # pool floats and french molding, train queries18 for name, frame in scores["train"].items():19 print(f"query {query_id} {name}: {frame.at[query_id, 'ndcg@10']:.3f}")2021print(f"\nthe planned test comparison, threshold {THRESHOLD:.2f}:")22after, before = scores["test"]["with stemming"]["ndcg@10"], scores["test"]["without stemming"]["ndcg@10"]23# the planned test comparison: permutation test, t-test and bootstrap interval24report_test_comparison(after, before)25gain = after - before26print("test query with the largest gain:", gain.idxmax())27print(f"its gain: {gain.max():.3f}")28print(f"mean test gain without it: {gain.drop(gain.idxmax()).mean():.3f}")
python measure-stemming.pytrain ndcg@10 without stemming: 0.695
train judged@10 without stemming: 0.930
train ndcg@10 with stemming: 0.725
train judged@10 with stemming: 0.950
test ndcg@10 without stemming: 0.725
test judged@10 without stemming: 0.927
test ndcg@10 with stemming: 0.774
test judged@10 with stemming: 0.950
train queries better, worse: 24, 14
query 410 without stemming: 0.360
query 410 with stemming: 0.921
query 359 without stemming: 0.961
query 359 with stemming: 0.809
the planned test comparison, threshold 0.01:
mean difference: 0.050
wins, losses, ties: 16, 6, 8
permutation p: 0.005
established at 0.01: yes
t-test p: 0.037
t-test agrees: no
99% interval: 0.016 to 0.162
interval agrees: yes
test query with the largest gain: 133
its gain: 0.635
mean test gain without it: 0.029
在訓練查詢上,詞幹還原使平均 nDCG@10 從 0.695 變為 0.725,judged@10 則從 0.930 變為 0.950。結果變好與變差的訓練查詢數量為 24, 14。pool floats 從 0.360 變為 0.921,french molding 則從 0.961 變為 0.809。這些訓練數字用來選擇詞幹還原,並不能證明它有幫助。
在測試查詢上,詞幹還原的增益在 0.01 的水準下成立,不過 t 檢定的結論並不一致(規劃比較):平均 nDCG@10 從 0.725 變為 0.774,平均差異為 0.050。Judged@10 同樣上升,從 0.927 變為 0.950,因此這項增益可能有一部分來自未經詞幹還原的執行中未被判斷的商品。
有一個查詢可以說明兩種檢定為何出現分歧。查詢 133,即 outdoor light fixtures,增益為 0.635;若不計入該查詢,平均增益為 0.029。t 檢定假設差異大致呈常態分布,因此單一的大幅增益會擴大差異的離散程度並降低 t 值;排列檢定則不對差異的分布形狀作任何假設(第 3 章)。這個查詢同時也是第 1 章發現其未經詞幹還原的前 10 名充滿未判斷燈泡的那一個。
實用原則: 以訓練查詢選擇文字處理上的變更,並且只有在其規劃比較成立時才保留。當排列檢定與 t 檢定的結論不一致時,應檢視各查詢中最大的差異,並在平均值旁一併報告不含最大增益的增益。詞幹還原的增益已成立,因此建立詞彙式搜尋時應進行詞幹還原。本書共用的 BM25 仍不做詞幹還原,使後續各章的結果保持可比較(決策)。對增益的幅度應視為不穩定。
此部分尚未翻譯,因此以英文呈現。
Tune BM25's parameters on train queries
BM25's two parameters have no single right value, and libraries ship different defaults. bm25s uses k1=1.5 and b=0.75 (bm25s source). Lucene uses k1=1.2 and b=0.75 (Lucene BM25Similarity). Kamphuis et al. (2020) report k1=0.9 and b=0.4 as the defaults of Anserini, a research toolkit. Robertson and Zaragoza (2009) give a rule of thumb, not a measurement: b between 0.5 and 0.8 and k1 between 1.2 and 2 are reasonably good in many circumstances, but the best values depend on the kind of documents and queries. So you tune them on your own train queries, and check the result on test queries.
The inverted index stores term frequencies and lengths, not scores, so k1 and b can change from one search to the next without rebuilding it. bm25s computes every score when it builds its index (Lù, 2024), which makes its searches fast, but each new k1 or b needs a new index. A sweep over the stemmed index tries a grid of 25 settings on the 50 train queries and picks the best. Then it compares the best with the defaults on the 30 test queries: the second planned comparison, at the threshold of 0.01.
Before you run it, predict: at the defaults, stemmed BM25 scores 0.774 on the test queries. How much will the best setting on train add?
1"""Sweeps k1 and b over the stemmed index on train queries, picks the best setting, and checks it against the defaults on test queries. The prose's point rests on the train best and grid-edge lines, and on the test permutation p line."""2import pandas as pd34from lib.lexical_by_hand import InvertedIndex, report_test_comparison5from lib.metrics import evaluate6from lib.store import load_products, load_queries, product_text, qrels78index = InvertedIndex(product_text(load_products()), stem=True) # stemmed terms, k1 and b set per search9train, test = load_queries("train"), load_queries("test")10# the grid: five values of k1 and five of b, with the defaults 1.5 and 0.75 among them11k1_values, b_values = [0.5, 0.9, 1.2, 1.5, 2.0], [0.0, 0.25, 0.5, 0.75, 1.0]121314def scores(queries, split, k1, b):15 """One row per query, with BM25 at these parameters."""16 return evaluate(index.run(queries, k1=k1, b=b), qrels(split))171819# one column per b, one row per k120grid = pd.DataFrame({b: {k1: scores(train, "train", k1, b)["ndcg@10"].mean() for k1 in k1_values} for b in b_values})21print("train ndcg@10, k1 down and b across:")22print(grid.round(3).to_string())23# the (k1, b) pair with the highest mean nDCG@10 on train24best_k1, best_b = grid.stack().idxmax()25print("settings in the grid:", grid.size)26print(f"best k1 on train: {best_k1}")27print(f"best b on train: {best_b}")28# a best value at an end of the grid can mean a better one lies beyond it29edge = best_k1 in (k1_values[0], k1_values[-1]) or best_b in (b_values[0], b_values[-1])30print("best setting on the grid's edge:", "yes" if edge else "no")31print(f"train ndcg@10 at the train best: {grid.at[best_k1, best_b]:.3f}")32print(f"train ndcg@10 at k1 1.5, b 0.75: {grid.at[1.5, 0.75]:.3f}")33print(f"train gain of the best over the defaults: {grid.at[best_k1, best_b] - grid.at[1.5, 0.75]:.3f}")34print(f"lowest train ndcg@10 in the grid: {grid.min().min():.3f}")35print()36runs = {"at k1 1.5, b 0.75": scores(test, "test", 1.5, 0.75), "at the train best": scores(test, "test", best_k1, best_b)}37for name, frame in runs.items():38 print(f"test ndcg@10 {name}: {frame['ndcg@10'].mean():.3f}")39 print(f"test judged@10 {name}: {frame['judged@10'].mean():.3f}")40# the planned test comparison: permutation test, t-test and bootstrap interval41report_test_comparison(runs["at the train best"]["ndcg@10"], runs["at k1 1.5, b 0.75"]["ndcg@10"])
python sweep-k1-and-b.pytrain ndcg@10, k1 down and b across:
0.00 0.25 0.50 0.75 1.00
0.5 0.707 0.710 0.716 0.720 0.720
0.9 0.711 0.711 0.716 0.722 0.720
1.2 0.709 0.711 0.715 0.723 0.720
1.5 0.709 0.714 0.719 0.725 0.715
2.0 0.714 0.720 0.726 0.729 0.713
settings in the grid: 25
best k1 on train: 2.0
best b on train: 0.75
best setting on the grid's edge: yes
train ndcg@10 at the train best: 0.729
train ndcg@10 at k1 1.5, b 0.75: 0.725
train gain of the best over the defaults: 0.004
lowest train ndcg@10 in the grid: 0.707
test ndcg@10 at k1 1.5, b 0.75: 0.774
test judged@10 at k1 1.5, b 0.75: 0.950
test ndcg@10 at the train best: 0.775
test judged@10 at the train best: 0.953
mean difference: 0.001
wins, losses, ties: 7, 6, 17
permutation p: 0.757
established at 0.01: no
t-test p: 0.754
t-test agrees: yes
99% interval: -0.008 to 0.008
interval agrees: yes
On train, the whole grid lies between 0.707 and 0.729. The best setting, k1 = 2.0 and b = 0.75, scores 0.729, against 0.725 at the defaults. The example reports whether it lies on the grid's edge: yes. A wider grid could find a higher train score, but with the whole grid this close, it would change little.
Tuning shows no established gain on the test queries. The best setting scores 0.775 against 0.774, with judged@10 of 0.953 and 0.950, and the difference isn't established (the planned comparisons).
If you predicted a gain of a few hundredths, the train grid makes it unlikely. On train, the best setting beats the defaults by 0.004, and even that is an optimistic estimate: of all the settings, it is the one that happened to fit these queries best, so on other queries you should expect less.
Working rule: Start from the library's defaults. Tune k1 and b on train queries when you change what you index, such as fields or stemming, and keep a tuned setting only if its planned comparison is established. The store's tuned setting isn't, so the store keeps k1=1.5 and b=0.75.
讓商品名稱的權重高於商品描述
商品的文字由數個部分組成,稱為欄位(field):商店的文字欄位有名稱、類別、分類與描述。這些欄位並非同等的證據。查詢詞出現在名稱中,比同一個詞出現在描述的某處,更能說明該商品是什麼。為欄位加權有兩種方式。最先想到的做法,是用 BM25 為每個欄位評分,再把分數相加。Robertson 與 Zaragoza(2009,第 3.6 節)主張相反的順序,也就是「先處理串流,再處理詞項」:先把每個詞項在各欄位的加權詞頻合併,再對該詞項的總證據做飽和處理。先合併詞項在各欄位的加權詞頻,再對總量做飽和處理,就是 BM25F。依他們的規則,把各欄位的分數相加,會讓同時在兩個欄位命中的詞項逃過飽和,因為每個欄位各自飽和。權重為整數時,簡單的 BM25F 與一般 BM25 的結果相同,只要後者所用的文字中,每個欄位重複的次數等於其權重(Robertson 與 Zaragoza,第 3.6.4 節),因此你可以用任何 BM25 函式庫來嘗試。
商店的搜尋只索引一個欄位,也就是把名稱、類別、分類與描述接在一起的欄位。第一次嘗試採用最先想到的做法:針對 50 筆訓練查詢並搭配詞幹還原,把名稱與其他三個欄位分開索引、分開評分,再將分數相加。分開索引時,每個欄位也有各自的 IDF 與各自的平均長度,所以改變的不只是飽和。依 Robertson 與 Zaragoza 的論點,我們預期它的表現會較差。在訓練查詢上,這個結果只能作為選擇的參考,並不構成證明:
1"""Scores the name and the other fields as separate BM25 indexes and adds the scores, then compares the result with one field on train queries. The prose's point rests on the two train nDCG@10 lines and the line that counts the queries that get better and worse."""2from collections import Counter34from lib.lexical_by_hand import InvertedIndex5from lib.metrics import evaluate6from lib.store import load_products, load_queries, product_text, qrels78products, train = load_products(), load_queries("train")9others = products["product_class"] + ". " + products["category"] + ". " + products["description"]10one_field = InvertedIndex(product_text(products), stem=True) # name, class, category, description11name, rest = InvertedIndex(products["name"], stem=True), InvertedIndex(others, stem=True) # own IDF and lengths1213summed = {}14for query_id, query in train["query"].items():15 scores = Counter(name.bm25(query)) + Counter(rest.bm25(query)) # each field saturates on its own16 # the top 100, as in every other run17 summed[query_id] = [product_id for product_id, _ in scores.most_common(100)]1819runs = {"one field": one_field.run(train), "fields scored apart": summed}20scores = {label: evaluate(run, qrels("train")) for label, run in runs.items()}21for label, frame in scores.items():22 print(f"{label}, train ndcg@10: {frame['ndcg@10'].mean():.3f}")23 print(f"{label}, train judged@10: {frame['judged@10'].mean():.3f}")24change = (scores["fields scored apart"]["ndcg@10"] - scores["one field"]["ndcg@10"]).round(3)25print(f"train queries better, worse with fields scored apart: {(change > 0).sum()}, {(change < 0).sum()}")
python fields-scored-apart.pyone field, train ndcg@10: 0.725
one field, train judged@10: 0.950
fields scored apart, train ndcg@10: 0.686
fields scored apart, train judged@10: 0.970
train queries better, worse with fields scored apart: 15, 24
分開評分時,各欄位的訓練 nDCG@10 為 0.686,單一欄位則為 0.725;judged@10 分別為 0.970 與 0.950。訓練查詢中變好與變差的數量為 15, 24。這足以讓我們選擇單一欄位而不採用這種設計,但不足以說明原因:飽和、IDF 與長度正規化同時都改變了。
第二次嘗試使用權重為整數的 BM25F:名稱在索引文字中計 1、2、3 或 5 次。它挑選訓練分數最佳的權重,再與單一欄位在 30 筆測試查詢上比較,這是第三項預先規劃的比較。
1"""Repeats the product name in the indexed text, once per extra weight, and picks the weight with the best train nDCG@10 for the test comparison. The prose's point rests on the best-weight line and the test permutation p line."""2from lib.lexical_by_hand import InvertedIndex, report_test_comparison3from lib.metrics import evaluate4from lib.store import load_products, load_queries, product_text, qrels56products, train, test = load_products(), load_queries("train"), load_queries("test")7# product_text already holds the name once, so weight - 1 more copies make it weight in all8indexes = {weight: InvertedIndex((products["name"] + ". ") * (weight - 1) + product_text(products), stem=True)9 for weight in [1, 2, 3, 5]} # BM25F with whole-number weights: the name counted weight times1011train_scores = {weight: evaluate(index.run(train), qrels("train")) for weight, index in indexes.items()}12for weight, frame in train_scores.items():13 print(f"name weight {weight}, train ndcg@10: {frame['ndcg@10'].mean():.3f}")14 print(f"name weight {weight}, train judged@10: {frame['judged@10'].mean():.3f}")15# on a tie, max keeps the first weight, the smaller one16best = max(train_scores, key=lambda weight: train_scores[weight]["ndcg@10"].mean())17print("best name weight on train:", best)18print()19runs = {"one field": indexes[1].run(test), "best name weight": indexes[best].run(test)}20scores = {label: evaluate(run, qrels("test")) for label, run in runs.items()}21for label, frame in scores.items():22 print(f"{label}, test ndcg@10: {frame['ndcg@10'].mean():.3f}")23 print(f"{label}, test judged@10: {frame['judged@10'].mean():.3f}")24# the planned test comparison: permutation test, t-test and bootstrap interval25report_test_comparison(scores["best name weight"]["ndcg@10"], scores["one field"]["ndcg@10"])
python repeat-the-name-field.pyname weight 1, train ndcg@10: 0.725
name weight 1, train judged@10: 0.950
name weight 2, train ndcg@10: 0.734
name weight 2, train judged@10: 0.968
name weight 3, train ndcg@10: 0.729
name weight 3, train judged@10: 0.970
name weight 5, train ndcg@10: 0.722
name weight 5, train judged@10: 0.972
best name weight on train: 2
one field, test ndcg@10: 0.774
one field, test judged@10: 0.950
best name weight, test ndcg@10: 0.786
best name weight, test judged@10: 0.970
mean difference: 0.012
wins, losses, ties: 15, 9, 6
permutation p: 0.149
established at 0.01: no
t-test p: 0.153
t-test agrees: yes
99% interval: -0.009 to 0.032
interval agrees: yes
在訓練查詢上,最佳的名稱權重為 2,得分為 0.734,單一欄位為 0.725;judged@10 分別為 0.968 與 0.950。
在測試查詢上,重複名稱並未顯示出已確立的增益:最佳名稱權重的得分為 0.786,單一欄位為 0.774;judged@10 分別為 0.970 與 0.950,增益並未確立(預先規劃的比較)。t 檢定與信賴區間都沒有不同的結論。
**實用原則:**不要把不同欄位的 BM25 分數相加。若要為欄位加權,應在飽和之前先合併詞頻,可使用 BM25F 或重複該欄位。在訓練查詢上調整權重,並且只有在預先規劃的比較結果確立時才保留。就這間商店而言,仍然維持使用單一的合併欄位。
此部分尚未翻譯,因此以英文呈現。
Index product attributes as a field
Shoppers often add a modifier, a word that narrows what they want: a color, a material, a size. The WANDS judges mark a product partial when it matches the thing asked for but not its modifiers. Product names and descriptions don't always state a modifier, but a catalog often keeps facts about a product as structured attributes, such as color: clear or material: glass. The store's products carry a few from WANDS: color, material, style, finish, shape, size, width, height and depth (examples/data/wands/README.md). Indexed as one more field, attributes give a modifier something to match. They also add terms to every product that has them, so whether they help is a question for the judgments.
In chapter 1, BM25's results for clear shower curtain couldn't show which curtains were clear. The example adds each product's attributes, names and values, to its indexed text, as a field with weight 1, combined before saturation as the previous section recommends. It counts the exact products for that test query that contain clear, with and without attributes. It measures this one candidate, fixed in advance, on the 50 train queries and checks it on the 30 test queries: the fourth planned comparison. Being planned, it goes to test whatever train shows.
1"""Adds each product's attributes, names and values, to its indexed text as one more field, and checks that single candidate on train and test. The prose's point rests on the two lines that count exact products with clear, and on the test permutation p line."""2from lib.lexical_by_hand import InvertedIndex, report_test_comparison, tokenize3from lib.metrics import evaluate4from lib.store import load_products, load_queries, product_text, qrels56products = load_products()7text = product_text(products)8with_attributes = text + ". " + products["attributes"] # names and values, one more field, weight 1910exact = [product_id for product_id, grade in qrels("test")[246].items() if grade == 2] # clear shower curtain11print("exact products for query 246:", len(exact))12print("exact, with clear in their text:", sum("clear" in tokenize(text[product_id]) for product_id in exact))13print("exact, with clear in text or attributes:", sum("clear" in tokenize(with_attributes[product_id]) for product_id in exact))14# a product whose attributes say clear and whose text does not, to show what the field adds15found = next(product_id for product_id in exact16 if "clear" in tokenize(products.at[product_id, "attributes"]) and "clear" not in tokenize(text[product_id]))17print(f"for example: {products.at[found, 'name']} -> {products.at[found, 'attributes']}")18names = {"color", "material", "style", "finish", "shape", "size", "width", "height", "depth"} # the attribute names19print("queries that contain an attribute name:", load_queries()["query"].map(lambda query: bool(names & set(tokenize(query)))).sum())20print("products whose attributes name size:", sum("size" in tokenize(value) for value in products["attributes"]))2122indexes = {"one field": InvertedIndex(text, stem=True), "with attributes": InvertedIndex(with_attributes, stem=True)}23scores = {split: {label: evaluate(index.run(load_queries(split)), qrels(split)) for label, index in indexes.items()}24 for split in ["train", "test"]} # one candidate, fixed in advance: tuned on nothing25for split in ["train", "test"]:26 print()27 for label, frame in scores[split].items():28 print(f"{split} ndcg@10, {label}: {frame['ndcg@10'].mean():.3f}")29 print(f"{split} judged@10, {label}: {frame['judged@10'].mean():.3f}")30print()31for query_id in [246, 58]: # clear shower curtain, medium size chandelier: test queries32 for label, frame in scores["test"].items():33 print(f"query {query_id} ndcg@10, {label}: {frame.at[query_id, 'ndcg@10']:.3f}")34# the planned test comparison: permutation test, t-test and bootstrap interval35report_test_comparison(scores["test"]["with attributes"]["ndcg@10"], scores["test"]["one field"]["ndcg@10"])
python add-attributes-field.pyexact products for query 246: 12
exact, with clear in their text: 4
exact, with clear in text or attributes: 8
for example: wynsum vinyl single shower curtain -> color: clear; width: 72; height: 84
queries that contain an attribute name: 1
products whose attributes name size: 950
train ndcg@10, one field: 0.725
train judged@10, one field: 0.950
train ndcg@10, with attributes: 0.717
train judged@10, with attributes: 0.948
test ndcg@10, one field: 0.774
test judged@10, one field: 0.950
test ndcg@10, with attributes: 0.787
test judged@10, with attributes: 0.963
query 246 ndcg@10, one field: 0.714
query 246 ndcg@10, with attributes: 0.844
query 58 ndcg@10, one field: 0.731
query 58 ndcg@10, with attributes: 0.667
mean difference: 0.013
wins, losses, ties: 8, 10, 12
permutation p: 0.303
established at 0.01: no
t-test p: 0.281
t-test agrees: yes
99% interval: -0.009 to 0.053
interval agrees: yes
For clear shower curtain, the attributes do what they should: 4 of the 12 exact products say clear in their text, and 8 do once attributes count, such as the vinyl curtain whose attributes say color: clear. For this query, nDCG@10 goes from 0.714 to 0.844. Indexing the attribute names has a cost, though: size now matches the 950 products whose attributes give a size. The store has 1 query that contains an attribute name, the test query medium size chandelier, and it goes from 0.731 to 0.667.
On train, judged@10 goes from 0.950 to 0.948, and nDCG@10 from 0.725 to 0.717. On test, judged@10 goes from 0.950 to 0.963, and nDCG@10 from 0.774 to 0.787, but the permutation test doesn't establish the gain (the planned comparisons).
Working rule: Keep structured attributes, and read the queries they help, but don't add them to the BM25 text on the strength of a few queries. Index the values without the names, so that a query word such as size doesn't match every product with a size, and keep the field only if its planned comparison is established. For the store, the attributes stay out of the BM25 text. When a modifier names an attribute value exactly, such as a color, a filter or a ranking feature can use it without adding its words to every product's text.
此部分尚未翻譯,因此以英文呈現。
Match phrases with term positions
BM25 scores a bag of words: it counts which terms a product contains and how often, never their order. To BM25, barn door and door barn are the same query. A phrase match needs the terms next to each other and in order, and an index of counts can't check that. A positional index stores, for each term and product, the positions where the term occurs, so that a phrase becomes a check on positions (Manning et al., 2008). bm25s precomputes one score for each pair of product and term (Lù, 2024). Its index keeps no positions (bm25s source), so phrases need an index of their own.
A positional index over the store's product names comes first, with stemmed terms as in the stemming section. Positions count terms after stop words are removed, so door for laundry holds the adjacent terms door and laundri: a phrase can match across a removed stop word. Take barn door, two words from one of the store's queries: assert that BM25 can't tell its two orders apart, and count the names with both words against those with the phrase:
1"""Builds a positional index over the product names, asserts that BM25 scores both word orders alike, and lists the names that have both words without the phrase. The prose's point rests on the two count lines, names with barn and door and names with the phrase barn door."""2from lib.lexical_by_hand import InvertedIndex, tokenize3from lib.store import load_products, product_text45products = load_products()6positions = {} # {term: {product_id: [where the term occurs in the name, counted after stop words go]}}7for product_id, name in products["name"].items():8 # positions count the terms left after stop words are removed, so a phrase can span one9 for place, term in enumerate(tokenize(name, stem=True)):10 positions.setdefault(term, {}).setdefault(product_id, []).append(place)111213def has_phrase(product_id, terms):14 """True if the terms occur next to each other, in this order, in the product's name."""15 def places(term):16 return positions.get(term, {}).get(product_id, [])17 # each term has to sit at the next position after the one before it18 return any(all(start + offset in places(term) for offset, term in enumerate(terms)) for start in places(terms[0]))192021index = InvertedIndex(product_text(products), stem=True)22# BM25 counts words, not their order, so both orders must score alike23assert index.bm25("barn door") == index.bm25("door barn")24both = set(positions["barn"]) & set(positions["door"])25print("names with barn and door:", len(both))26print("names with the phrase barn door:", sum(has_phrase(product_id, ["barn", "door"]) for product_id in both))27for product_id in sorted(product_id for product_id in both if not has_phrase(product_id, ["barn", "door"])):28 print(" ", products.at[product_id, "name"])
python phrase-positions-by-hand.pynames with barn and door: 71
names with the phrase barn door: 66
low ceiling single bypass double door barn hardware kit
artemas barn owl welcome non-slip outdoor door mat
vintage rustic wooden door of old barn duvet cover set
barnes entrance scraper non-slip outdoor door mat
glass barn 60 '' w x 76 '' h single sliding frameless shower door
BM25 gives barn door and door barn the same scores, as the code asserts. Of the 71 names that contain both barn and door, 66 contain the phrase. The names without it show what a phrase check catches and what it costs. Two door mats and a duvet cover match both words but aren't barn doors, and one of the mats matches only because barnes stems to barn. The bypass hardware kit, on the other hand, is hardware for barn doors, and the glass sliding shower door is a barn-style door. A strict phrase filter would remove both.
A bonus is gentler than a filter: a fixed amount added to a product's BM25 score for each pair of adjacent query terms that appears, in order, in its name. The bonus example uses PositionalIndex from lib.lexical_by_hand, which holds the same positions, and it picks the bonus on the 50 train queries, then checks it on the 30 test queries: the last planned comparison.
1"""Adds a bonus for each adjacent pair of query terms that appears in order in a product's name, picks the bonus on train and checks it on test. The prose's point rests on the test permutation p line and the test nDCG@10 lines."""2from lib.lexical_by_hand import InvertedIndex, PositionalIndex, report_test_comparison, tokenize3from lib.metrics import evaluate4from lib.store import load_products, load_queries, product_text, qrels56products = load_products()7index = InvertedIndex(product_text(products), stem=True)8names = PositionalIndex(products["name"], stem=True) # the positions phrase-positions-by-hand builds91011def with_bonus(split, bonus):12 """BM25's top 100, plus the bonus for each pair of adjacent query terms found, in order, in the name."""13 run = {}14 for query_id, query in load_queries(split)["query"].items():15 terms, scores = tokenize(query, stem=True), index.search(query)16 pairs = list(zip(terms, terms[1:]))17 # only BM25's top 100 get a bonus, so it reorders them and adds no product18 scores += [bonus * sum(names.has_phrase(product_id, list(pair)) for pair in pairs) for product_id in scores.index]19 run[query_id] = list(scores.sort_values(ascending=False, kind="stable").index)20 return evaluate(run, qrels(split))212223train_scores = {bonus: with_bonus("train", bonus) for bonus in [0, 0.5, 1, 2]}24for bonus, frame in train_scores.items():25 print(f"bonus {bonus}, train ndcg@10: {frame['ndcg@10'].mean():.3f}")26 print(f"bonus {bonus}, train judged@10: {frame['judged@10'].mean():.3f}")27best = max(train_scores, key=lambda bonus: train_scores[bonus]["ndcg@10"].mean())28print("best bonus on train:", best)29print()30# the defaults, with no bonus, and the best bonus on train31test_scores = {bonus: with_bonus("test", bonus) for bonus in [0, best]}32for bonus, frame in test_scores.items():33 print(f"bonus {bonus}, test ndcg@10: {frame['ndcg@10'].mean():.3f}")34 print(f"bonus {bonus}, test judged@10: {frame['judged@10'].mean():.3f}")35# the planned test comparison: permutation test, t-test and bootstrap interval36report_test_comparison(test_scores[best]["ndcg@10"], test_scores[0]["ndcg@10"])
python phrase-bonus-train-and-test.pybonus 0, train ndcg@10: 0.725
bonus 0, train judged@10: 0.950
bonus 0.5, train ndcg@10: 0.727
bonus 0.5, train judged@10: 0.956
bonus 1, train ndcg@10: 0.725
bonus 1, train judged@10: 0.964
bonus 2, train ndcg@10: 0.716
bonus 2, train judged@10: 0.968
best bonus on train: 0.5
bonus 0, test ndcg@10: 0.774
bonus 0, test judged@10: 0.950
bonus 0.5, test ndcg@10: 0.776
bonus 0.5, test judged@10: 0.950
mean difference: 0.002
wins, losses, ties: 6, 7, 17
permutation p: 0.758
established at 0.01: no
t-test p: 0.769
t-test agrees: yes
99% interval: -0.012 to 0.015
interval agrees: yes
On train, the best bonus is 0.5, which scores 0.727 against 0.725 without one, with judged@10 of 0.956 and 0.950.
The best bonus scores 0.776 against 0.774, with judged@10 of 0.950 and 0.950, and the gain isn't established (the planned comparisons).
Working rule: Don't add a phrase bonus to every query by default, and keep one only if its planned comparison is established. Build positions when shoppers quote phrases, or when word order changes what they want, as between table lamp and lamp table. Prefer a bonus that you measure on train queries to a filter, because a filter removes products like the hardware kit.
此部分尚未翻譯,因此以英文呈現。
What goes wrong in production
The index and the queries drift apart. Every step from the tokenizer to the stemmer must run the same way on products and on queries. Stem the queries but not the products, and a query term such as shelv finds no postings. Nothing warns you: bm25s leaves out query tokens that aren't in its vocabulary (bm25s source). Change text processing for both sides in one release, and rebuild the whole index.
Sizes, units and codes don't survive tokenizing. 7qt and 7 qt never meet, as the tokenizer section shows. Train query 205 ends in a product code, w003096809, that appears in no product's text in the sample: its postings hold 0 products, so no lexical scorer can match it. A misspelled term such as the ligth in ligth bulb can only match products with the same misspelling, and chapter 8 builds a corrector and shows what it still gets wrong.
IDF depends on the catalog. Every IDF in this chapter comes from the sample, which holds every product judged for the 80 queries plus randomly chosen unjudged ones (examples/data/wands/README.md). On the full catalog, document frequencies differ, and so do IDFs and scores. Recompute them whenever you rebuild the index.
A BM25 score has no fixed scale. Each query term adds at most its own IDF, so the highest possible score depends on which terms the query holds, and a score of 6 can be high for one query and low for another. Don't keep results above a fixed score threshold; cut the list by rank.
Stop words and stemming change meaning on a few queries. The store's judged queries have no negations, but shoppers type them, and the default stop list removes not and no. Stemming hurts some queries badly, as french molding shows in the stemming check. The judgments can't warn you about queries they don't include.
The test queries wear out. This chapter makes five planned comparisons on the same test queries, and the Bonferroni threshold of 0.01 keeps the chance of any false positive among them at 5% or less when none of the changes does anything. It can't count what nobody planned: every extra setting tried on test, and every look at a test query to explain a result, is another comparison. Confirm stemming's gain on queries and judgments that none of these choices has seen.
Working rule: Keep a set of probe queries for negations, sizes and codes, and read their results after every change to text processing. Store the tokenizer's and stemmer's settings with the index they built, log the terms that each query becomes, and watch for queries whose terms have no postings.
此部分尚未翻譯,因此以英文呈現。
Decisions this chapter made
Each setting here was picked on the train queries. Before reading any test result, the chapter fixed five planned comparisons on the test queries, read with chapter 3's harness: stemming and the attributes field as single candidates fixed in advance, and the best setting on train for k1 and b, the name weight and the phrase bonus. The attributes field went to test whatever train showed, because it was planned. Only an established difference changes a decision. Each column compares nDCG@10 on the test queries with the change against the same search without it, at the threshold of 0.01:
| Measure | Stemming | Best k1 and b |
Best name weight | Attributes field | Best phrase bonus |
|---|---|---|---|---|---|
| Mean difference | 0.050 | 0.001 | 0.012 | 0.013 | 0.002 |
| 99% interval | 0.016 to 0.162 | -0.008 to 0.008 | -0.009 to 0.032 | -0.009 to 0.053 | -0.012 to 0.015 |
| Permutation p | 0.005 | 0.757 | 0.149 | 0.303 | 0.758 |
| t-test p | 0.037 | 0.754 | 0.153 | 0.281 | 0.769 |
| Wins, losses, ties | 16, 6, 8 | 7, 6, 17 | 15, 9, 6 | 8, 10, 12 | 6, 7, 17 |
| Established | yes | no | no | no | no |
| t-test agrees | no | yes | yes | yes | yes |
| Interval agrees | yes | yes | yes | yes | yes |
- Tokenizer: bm25s's defaults. Lowercasing, tokens of two or more word characters (letters, digits or underscores), and its 33 English stop words, rebuilt by hand and matched on every product. They lose single-digit sizes and negations. Too few judged queries could measure either: a size-aware pattern changes 4 train queries and 0 test queries, and 0 queries hold a negation. The defaults stay until probe queries or new judgments can.
- Stemming: Snowball English from PyStemmer, on products and queries. Its test gain, from 0.725 to 0.774, is established by the permutation test, though the t-test disagrees and one query carries much of it. The book's shared baseline,
lib.lexicalfrom chapter 1, stays at bm25s's defaults without stemming, so that every chapter's results stay comparable. This chapter's stemmed BM25 isInvertedIndex(text, stem=True)inlib.lexical_by_hand, or bm25s withstemmer=. - Scoring: BM25 as bm25s computes it by default, Lucene's formula with exact lengths,
k1=1.5andb=0.75, with equal scores ordered by product ID. The best setting on train isn't established on test, so the defaults stay. - Fields: one field that joins name, class, category and description. Per-field scores, added, score lower on train. The best name weight on train and the attributes field aren't established on test.
- Phrases: no phrase bonus. Positions over product names are cheap to build, but the best bonus on train isn't established on test.
- Implementation: a by-hand index for experiments, a library for serving. The by-hand index lets
k1andbchange without rebuilding, and bm25s precomputes scores so that searches are fast. On the same test queries, semantic retrieval with the recordedSnowflake/snowflake-arctic-embed-m-v1.5embeddings scores 0.830 (chapter 1). - What the chapter showed: BM25 can be rebuilt by hand and matched score for score. Of the choices made on the train queries, only stemming held up on test, and even it rests on a few queries.
本章,於本版次中
版次 2026.11.10範例於 2026年11 月 19 通過測試本章 13 個範例 個範例中有 13 個通過
譯自英文書,版次 2026.11.10。