語彙的検索
読了まで約77 分分、12 節 節の 13 例 例。
このページの内容
この章を終えると、語彙的検索をゼロから構築できるようになる。具体的には、商品テキストを語に分割し、その語を索引化し、TF-IDF と BM25 で商品をスコアリングして、bm25s ライブラリとスコアが一致するところまで実装する。さらに、テキスト処理と BM25 のパラメータに対するどの変更を採用する価値があるかを、train クエリで選択し test クエリで確認することによって判断できるようになる。
語彙的検索(lexical retrieval)は、クエリと共通する語に基づいて商品を検索し、順位付けする手法である。本書では、買い物客が ストア の家具・家庭用品を検索するとき、bm25s ライブラリを通じた BM25 が結果の順位付けを担う。買い物客が 7qt slow cooker や pool floats と入力したとき、第1章 の BM25 による結果は精度が低い。test クエリでの平均 nDCG@10 が 0.725 であることはそれを示すが、理由までは示さない。第1章では BM25 を bm25s のデフォルト設定のままブラックボックスとして使ったためである。この章ではそのブラックボックスを開く。ストアの 12,000 件の商品を対象に各ステップを手作業で再構築して bm25s と照合し、その後、1つのステップずつ変更を加え、それぞれの変更をストアの 判定 に照らして測定する。
各変更は 50 件の train クエリ で選択し、30 件の test クエリで確認する。test の結果を読む前に、この章は test クエリでの比較計画を確定しておく。比較は5つあり、いずれも変更を加えない同じ検索との比較である。
- ステミング
- train で最良の
k1とbを、bm25s のデフォルトと比較する(チューニング) - 商品名に対する、train で最良の重み(フィールド)
- フィールドとしての商品属性(属性)
- train で最良のフレーズボーナス(フレーズ)
計画された比較が5つあるため、本書の規則 に従い、基準は p 値 0.01 とする。対応のある 順列検定 の p 値がこの基準を下回れば、その改善は確立されたとみなす。各比較では、対応のある t 検定 と 99% の ブートストラップ区間 も報告し、それぞれが順列検定と一致するかどうかを述べる。
この部分はまだ翻訳されていないため、英語で表示している。
Split product text into terms
Search never compares raw strings. The query and every product's text first go through the same steps. Splitting the text into pieces gives tokens. Lowercasing makes Chair and chair one token. Removing stop words, very common words such as the and with, leaves the terms that search compares, and all the terms in the catalog form its vocabulary. A product can only match a query on terms they share, so these steps decide what can match at all, before any scoring starts.
bm25s, which runs the store's BM25, makes three choices here. It lowercases. It keeps every run of two or more word characters, which are letters, digits or underscores, with the regular expression (?u)\b\w\w+\b, which its docstring describes as the method of scikit-learn's CountVectorizer. And it removes 33 English stop words, among them no, not, with and for. It doesn't stem words unless you pass it a stemmer (bm25s tokenizer, stop words). To see the steps one at a time, write them out by hand, check the result against bm25s.tokenize on every product, and run the train query 7qt slow cooker through them:
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
The number of products that the hand-written tokenizer and bm25s split differently is 0, so the trouble isn't in either one: it's in the rules they share. A shopper who types 7qt slow cooker wants a 7-quart cooker, and 7qt does survive as one token. But it matches 0 products, because product text writes the size apart, as 7 qt in 8 products, and the tokenizer drops the one-character 7. So the size plays no part in the ranking, on either side of the match, and BM25 can't tell a 7-quart cooker from any other slow cooker. Of the 9 products the judges marked exact for this query, BM25's top 10 holds 1.
A pattern that keeps single digits and splits numbers from their units, (?u)\d+|[^\W\d_]+, changes the terms of 4 train queries and 0 test queries, so the store's judgments can say little about it.
The stop list fails the same way, and bm25s raises no error. Take rug not wool, a probe query: one written for this chapter to test a behaviour, not one of the store's queries. It becomes rug wool, so a wool rug matches both of its terms. The judgments can measure this harm only on queries with a negation, and 0 of the store's queries contain not or no. Search systems have moved from long stop lists to short ones or none, in part because stop words carry meaning in some queries, and in part because keeping them has become cheap (Manning et al., 2008).
Working rule: Print the terms that your queries and products become before you tune any scoring, and run both through the same tokenizer. Start from bm25s's defaults, as the store does. When shoppers type sizes, quantities or model numbers, use a token pattern that keeps single digits and splits a number from its unit, such as the one above. When they type negations, turn the stop list off. Each is a change to search, so measure it on the train queries and check it on test queries before you keep it.
転置インデックスを構築する
これらの語からなるクエリをスコアリングするには、検索は各語を含む商品を知っていなければならない。クエリのたびにすべての商品のテキストを読む方法は、小さなサンプルであれば成り立つが、数百万件のカタログでは成り立たない。転置インデックス(inverted index)は、テキストと語の関係を逆向きにする。語ごとに、その語を含む商品のリストを保持するのである。このリストをその語のポスティング(postings)と呼ぶ(Manning et al., 2008)。ポスティングには、各商品とともに語頻度(term frequency)、すなわちその語が当該商品のテキストに現れる回数を格納する。ある語のポスティングに含まれる商品の数は文書頻度(document frequency)である。検索エンジンは検索対象の項目を文書と呼ぶが、本書ではそれらは商品に当たる。クエリが読むのは、そのクエリに含まれる語のポスティングだけである。
このストアのインデックスは、各語を、商品IDと語頻度の辞書に対応づける。あわせて、BM25が必要とする、各商品の語数での長さも保持する。構築は、前の節のトークナイザを用いて、すべての商品のテキストを1回走査するだけで済む。続いて、コードは train クエリ 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 件であり、3語を合わせると 158 件の商品に及ぶ。このクエリのスコアリングで読む必要があるのは、これらだけである。3語すべてを含む商品は 0 件である。7qt を含む商品が1件もないためである。したがって、クエリの語をすべて含む商品だけを返すブール AND クエリは、このクエリに対して何も返さない。BM25 のように、いずれかの語を含むすべての商品をスコアリングする検索であれば、スロークッカーを返すことができ、どれを上位にするかはスコアに委ねられる。
実践ルール: クエリの結果がおかしいと感じたら、スコアリングを変更する前に、そのクエリの語をインデックスで引いて確かめる。7qt のようにポスティングが空の語は、スコアラーが何をしても、どの商品にも寄与できない。その場合は、トークナイザかクエリを直す。ユーザーが入力するクエリでは、すべての語を含む商品ではなく、いずれかの語を含む商品に一致させる。一致しない語が1つあるだけで、結果が空になってしまうからである。本番の検索提供にはライブラリのインデックスを使い、ある語が何に一致するかを確かめるために、このような小さなインデックスを手元に置いておく。
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 と、train クエリ laundry basket with wheels の各語の IDF を示し、続いてそのクエリに対する TF-IDF の上位3件を、各商品のスコアと語の出現頻度とともに示す。最後に、50 件の train クエリすべてを TF-IDF と、第1章での実行どおりの BM25でスコア付けする。
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 の1位の商品は部分一致である。これは wheels という語を一度も含まないバスケットだが、basket を下位の2商品のどちらよりも多く繰り返している。この結果は IDF によって準備されている。furniture の IDF は 0.919 であり、クエリの語は laundry が 3.985、basket が 3.925、wheels が 4.839 である。いずれも前者よりまれで、互いに近い値になっている。IDF がこれほど近いと、スコアが示すとおり、繰り返しの効果が wheels の欠落を上回る。3件のうち wheels を含む唯一の商品である完全一致の商品は、2位に入る。TF-IDF では語の出現頻度に上限がないため、ある商品は語を繰り返すだけで別の商品より高いスコアを得られる。
train クエリ全体で、TF-IDF の平均 nDCG@10 は 0.579、BM25 は 0.695 である。BM25 のスコアが高いクエリと低いクエリの数は、それぞれ 36, 10 件である。TF-IDF の judged@10 は 0.836、BM25 は 0.930 である。ある実行の judged@10 が低い場合、その差の一部は、実際に劣った商品ではなく、誰も判定していない商品によるものかもしれない。train クエリでのこの比較は、どのスコアラーを土台にすべきかを教えてくれる。一方、本書は最終的な根拠をテストクエリのために取っておく。
実践ルール: 語彙的なスコアラーでは、まれな語での一致のほうが優れた証拠となるため、語を 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件の学習クエリから得たものである。これは、この章の計画済みの5つの比較の最初のものであり、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に上がっているため、この改善の一部は、ステミングなしの実行で未判定のままだった製品に由来する可能性がある。
2つの検定の結果が分かれる理由は、1つのクエリで説明できる。クエリ133、すなわちoutdoor light fixturesの改善幅は0.635であり、これを除いた平均改善幅は0.029である。t検定は差がおおよそ正規分布に従うと仮定するため、1件の大きな改善によって差の散らばりが広がり、tが小さくなる。一方、順列検定は差の分布の形について何も仮定しない(第3章)。このクエリは、ステミングなしの上位10件が第1章で未判定の電球だらけであると判明したものでもある。
実践ルール: テキスト処理の変更は学習クエリで選び、計画済みの比較が確立された場合にのみ採用する。順列検定とt検定が食い違うときは、クエリごとの差のうち最大のものを読み、平均と並べて、最大の1件を除いた改善幅も報告する。ステミングは確立されているので、語彙検索を構築するときにはステミングを行う。ただし、本書で共有するBM25はステミングなしのままとし、後の章の結果を比較可能に保つ(決定事項)。改善幅の大きさは不安定なものとして扱う。
学習用クエリでBM25のパラメータを調整する
BM25の二つのパラメータに唯一の正しい値はなく、ライブラリごとに既定値も異なる。bm25sはk1=1.5とb=0.75を用いる(bm25sのソース)。Luceneはk1=1.2とb=0.75を用いる(Lucene BM25Similarity)。Kamphuis et al. (2020)は、研究用ツールキットであるAnseriniの既定値としてk1=0.9とb=0.4を報告している。Robertson and Zaragoza (2009)は、測定結果ではなく経験則を示している。bは0.5から0.8の間、k1は1.2から2の間であれば多くの状況で十分によい値になるが、最適な値は文書とクエリの種類に依存する。そのため、自分の学習用クエリで調整し、その結果をテスト用クエリで確認する。
転置インデックスが保持するのは語の出現頻度と文書長であり、スコアではない。したがってk1とbは、インデックスを作り直さなくても検索ごとに変更できる。bm25sはインデックスを構築する時点ですべてのスコアを計算する(Lù, 2024)。これにより検索は高速になるが、k1やbを変えるたびに新しいインデックスが必要になる。ステミング済みインデックスに対するスイープでは、25通りの設定からなるグリッドを50件の学習用クエリで試し、最良の設定を選ぶ。続いて、その最良の設定と既定値を30件のテスト用クエリで比較する。これは閾値を0.01とする、二つ目の計画された比較である。
実行する前に予想してみよう。既定値でのステミング済みBM25は、テスト用クエリで0.774のスコアを示す。学習用クエリでの最良の設定は、これをどれだけ上積みするだろうか。
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
学習用クエリでは、グリッド全体が0.707から0.729の間に収まっている。最良の設定はk1 = 2.0、b = 0.75で、スコアは0.729である。既定値でのスコアは0.725である。この例は、最良の設定がグリッドの端にあるかどうかも報告している。結果はyesである。グリッドを広げれば、学習用クエリでより高いスコアが見つかるかもしれない。しかし、グリッド全体がこれほど近い値に収まっている以上、変化はわずかだろう。
調整しても、テスト用クエリで確立された利得は見られない。最良の設定のスコアは0.775、既定値のスコアは0.774である。judged@10はそれぞれ0.953と0.950であり、差は確立されていない(計画された比較)。
数百分の一ではなく、百分の数ポイント程度、つまり0.0数程度の利得を予想していたとすれば、学習用クエリのグリッドを見る限り、それは起こりにくい。学習用クエリでは、最良の設定は既定値を0.004上回る。ただしこれも楽観的な推定である。すべての設定のなかで、たまたまこれらのクエリに最もよく適合した設定が選ばれているため、別のクエリではこれより小さい利得を想定すべきである。
実践ルール: ライブラリの既定値から始める。フィールドやステミングなど、インデックスする内容を変えたときに、学習用クエリでk1とbを調整する。調整後の設定は、計画された比較で確立された場合にのみ採用する。このストアの調整後の設定は確立されなかったため、ストアはk1=1.5と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)から翻訳した。