BM25 与倒排索引:稀有术语怎样影响排序
用四篇短文手算TF、IDF和长度归一,观察产品编号检索与词频饱和。
用户查“X-17退款”,语义相近的“X-18故障”未必有用。型号、错误码、函数名和精确短语通常需要词法匹配。BM25根据查询词在文档中的出现情况排序,词频、全库稀有程度和文档长度共同决定分数,不需要先把文本变成稠密语义向量。
倒排索引先减少要检查的文档
正排是“文档A包含哪些词”,倒排是“词x-17出现在哪些文档”。倒排列表还可以保存词频和位置;位置用于短语与邻近查询,普通BM25词袋评分本身不表达顺序。多个词可以做并集召回,再评分;必须包含所有词时则是另一种布尔约束。召回规则与打分公式是两件事。
把每个乘数解释清楚
这里采用常见正值IDF的BM25形式,每个查询词贡献如下,再对查询词求和:
IDF(t) = ln(1 + (N − df(t) + 0.5) / (df(t) + 0.5))
贡献(t,d) = IDF(t) × tf(t,d)(k1+1)
/ [tf(t,d) + k1(1−b+b×len(d)/avglen)]N是文档数,df是含该词的文档数,tf是当前文档中该词出现次数。df越小,词越稀有,IDF通常越大。tf增长不会让分数无限线性上涨,分式逐渐饱和;k1控制饱和速度。b控制长度归一,b=0时不惩罚长度,b=1时完整使用相对平均长度。具体搜索引擎可能采用等价排序的缩放、字段norm编码及重叠token处理,不能要求这里的浮点分数逐位等于引擎输出。
四篇文档长度为2、8、3、2,平均3.75。x-17出现在两篇,IDF为ln2约0.693147。A里x-17的tf=1,取k1=1.2、b=0.75,分母为 1+1.2×(0.25+0.75×2/3.75)=1.78,贡献约 0.693147×2.2/1.78=0.85646。A还因“退款”获得另一项贡献。
运行并改变长度归一参数
保存为 bm25.py,运行 python -X utf8 bm25.py。程序保留可检查的倒排列表,评分为便于教学遍历全部文档;实际引擎使用倒排与剪枝,不需要每次扫描全库。
"""透明的BM25算例;空格分词和完整遍历只为便于核对。"""
from collections import Counter,defaultdict
from math import log
def index(documents):
counts={key:Counter(text.lower().split()) for key,text in documents.items()}
postings=defaultdict(set)
for key,tokens in counts.items():
for token in tokens:postings[token].add(key)
return counts,postings
def rank(query,documents,k1=1.2,b=.75):
counts,postings=index(documents);n=len(counts)
avg=sum(sum(c.values()) for c in counts.values())/n
results=[]
for key,c in counts.items():
score=0
for term in set(query.lower().split()):
tf=c[term];df=len(postings[term]);idf=log(1+(n-df+.5)/(df+.5))
if tf:score+=idf*tf*(k1+1)/(tf+k1*(1-b+b*sum(c.values())/avg))
results.append((key,score))
return sorted(results,key=lambda item:(-item[1],item[0]))
DOCS={'A':'x-17 退款','B':'x-17 x-17 x-17 退款 说明 流程 条件 版本','C':'退款 退款 说明','D':'x-18 故障'}
if __name__=='__main__':
counts,postings=index(DOCS)
print('x-17 倒排列表',sorted(postings['x-17']))
print('平均长度',sum(sum(c.values()) for c in counts.values())/len(counts))
print('IDF(x-17)',round(log(1+(4-2+.5)/(2+.5)),6))
for b in (.75,0):print('b=',b,[(key,round(score,6)) for key,score in rank('x-17 退款',DOCS,b=b)])x-17 倒排列表 ['A', 'B']
平均长度 3.75
IDF(x-17) 0.693147
b= 0.75 [('A', 1.297533), ('B', 1.120084), ('C', 0.519659), ('D', 0)]
b= 0 [('B', 1.445906), ('A', 1.049822), ('C', 0.490428), ('D', 0)]B把x-17重复三次,但包含更多其他词;b=0.75时A排在B前,关闭长度归一后B更占优势。它说明排序是词频和长度共同作用的结果。把B的x-17继续重复十次,分数增长会逐渐变小;若仅用出现次数排序,重复堆词会受到过高奖励。
分词错误时,公式救不了结果
本例空格分词,因此x-17被保留为一个词。真实中文需要选择分词器、字/词策略或字符n-gram,并处理繁简、大小写、标点、同义词和领域词典。若写入时把x-17拆成x和17,查询时却保留为整体,倒排列表里可能没有这个词。索引与查询分析链要一致,同时为精确ID单独保存keyword字段,避免自然语言分析破坏标识符。
停用词删除可能误伤否定词;同义词扩展可能把不同版本号混为一谈。为标题、正文、产品编号分别建字段并设置权重,比把一切拼成同一大字符串更可控。但字段加权同样需要测试集,不能凭直觉无限提高标题权重。
BM25的边界与组合方式
“怎么取消订单”和“撤销购买流程”可能语义接近却没有共享词,BM25容易漏召回。另一方面,embedding可能把近似型号混淆。混合检索可以合并两类候选,再用融合或重排处理。不同检索器的原始分数尺度不可直接假设可比;分数0.8不是通用置信度,阈值要按同一检索配置和数据分布校准。
排错先看实际分词、词频、df、长度与字段,再看公式参数。调k1或b之前,要确认重要编号真的进入倒排索引。领域词典变更后,已有索引未必自动更新,需要重新分析和重建相关字段。
综合边界推演与面试追问
查询X-17,文档d1含一次精确编号且长10词,d2含五次但长1000词。先看分词是否把X-17保留为一致词项,再由倒排表得到候选。TF增加会饱和,IDF反映全库稀有度,长度归一可能让长文档不因重复堆词占优。
k1控制TF饱和速度,b控制长度影响;b=0移除长度归一可用于对照。精确术语适合词法路径,同义改写可能需要稠密补充;混合前不要把BM25原始分数解释成概率或直接与余弦相加。
无命中先查查询/文档token列表和倒排表;候选正确但排序异常,再打印N、df、tf、dl、avgdl及各乘项。中文分词和编号规范化变化要版本化,不能在一侧改分词后仍使用旧索引。
课后练习展开习题收起习题
先独立作答,再展开参考思路。检查自己的解释是否包含机制、条件和反例。
四篇文档中两篇含x-17,本例IDF是多少?
参考思路与常见误区
采用ln(1+(N-df+0.5)/(df+0.5)),代入N=4、df=2得到ln2约0.693147。df是含词的文档数,不是该词在全库出现的总次数。
常见误区:把同一文档重复三次算成三篇文档。
k1和b分别控制什么?b设零会怎样?
参考思路与常见误区
k1控制词频贡献的饱和,b控制文档长度归一程度。b为零取消相对长度因子,但仍有词频饱和和IDF;重复词多的长文可能更占优势。
常见误区:认为b为零关闭BM25或让词频完全线性增长。
编号没有召回,第一步应该调BM25参数吗?
参考思路与常见误区
先看索引和查询实际分词,检查连字符、大小写和领域词是否一致。可以为编号保留keyword字段,避免分析器破坏精确标识。词根本不在倒排中时调k1/b无效。
常见误区:忽略预处理,仅对评分公式做参数搜索。
倒排索引与BM25是同一件事吗?
参考思路与常见误区
倒排是词到候选文档及词频/位置的数据结构,BM25是对匹配证据计算得分的方法。布尔召回、短语约束、字段加权与BM25可以组合,词袋分数本身不表达完整词序。
常见误区:认为使用倒排就必须用BM25,或BM25天然理解短语顺序。
BM25和向量相似度可以直接相加吗?
参考思路与常见误区
原始分数通常不在相同尺度上,直接相加可能让一方主导。应校准、使用有定义的排名融合或重排,并在相关性测试集上验证。BM25适合精确词,向量有机会覆盖同义表达,两者各有漏召回。
常见误区:把任意检索分数0.8都理解成80%正确概率。
参数职责、IDF与默认值可核对 Lucene 9.12.1 BM25Similarity。继续看 向量距离与ANN。