词法检索
阅读约需 97分钟 分钟,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 成为同一个词元。去除停用词,即 the 和 with 这类非常常见的词,就留下了搜索所比较的词项,而目录中的全部词项构成它的词表。商品只能依靠与查询共有的词项来匹配,因此这些步骤在任何打分开始之前,就已经决定了哪些内容可能匹配。
运行商店 BM25 的 bm25s 在这里做了三项选择。第一,它转为小写。第二,它用正则表达式 (?u)\b\w\w+\b 保留每一段由两个或更多单词字符(字母、数字或下划线)组成的片段,其文档字符串称这是 scikit-learn 的 CountVectorizer 所用的方法。第三,它去除 33 个英文停用词,其中包括 no、not、with 和 for。除非你传入词干提取器,否则它不会对单词做词干提取(bm25s 分词器、停用词)。为了逐步查看这些步骤,可以手工把它们写出来,在每件商品上用 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 为例,这是一条探测查询:它是为本章专门编写、用来测试某种行为的查询,不属于商店的查询。它会变成 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 为词项加权
并非每一次匹配都同样有价值。有两个思路可以给匹配加权。一个词项在商品文本中出现得越频繁,该商品就越可能与它相关:这就是词项频率,即 tf。而对稀有词项的匹配,比对常见词项的匹配说明的问题更多。Karen Spärck Jones 提出按包含词项的文档数量为词项加权,使得“对较不常见、更具体的词项的匹配,比对常见词项的匹配价值更大”(Spärck Jones, 1972;免费重印本)。这一权重后来成为逆文档频率,即 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,而查询中各词项的 IDF 分别是: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.
让商品名称的权重高于描述
商品的文本由若干部分组成,称为字段:商店的文本字段有名称、类别、分类和描述。它们提供的证据并不相等。查询词出现在名称中,比同一个词出现在描述某处,更能说明商品是什么。给字段加权有两种方式。最先想到的做法是用 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。