BM25 och nyckelordssökning

BM25 är TF-IDF med två rättelser, och den har varit standard i sökmotorer i trettio år. Den är fortfarande svår att slå.

Rättelse 1 — mättnad. I TF-IDF är ett ord som förekommer 100 gånger tio gånger så relevant som ett som förekommer 10 gånger. Det stämmer inte. Efter några förekomster tillför ytterligare nästan ingenting. BM25 låter bidraget plana ut.

Rättelse 2 — mjukare längdnormalisering. TF-IDF delar rakt av med längden, vilket straffar långa dokument hårt. BM25 jämför med den genomsnittliga dokumentlängden och har en parameter för hur hårt det ska slå.

Resultatet är ett mått som bara har två inställningar (k1 och b), sällan behöver ändras, och nästan alltid är en stark baslinje.

$\mathrm{BM25}(q, d) = \sum_{t \in q} \mathrm{IDF}(t)\cdot\frac{f_{t,d}\,(k_1+1)}{f_{t,d} + k_1\left(1 - b + b\dfrac{|d|}{\text{avgdl}}\right)}$

med $\mathrm{IDF}(t) = \ln\!\left(\dfrac{N - n_t + 0{,}5}{n_t + 0{,}5} + 1\right)$.

Mättnaden i siffror (med $k_1 = 1{,}5$, längdfaktorn = 1):

BM25 närmar sig taket $k_1 + 1 = 2{,}5$ och kommer aldrig över. Det gör metoden robust mot nyckelordsspam och mot dokument som råkar upprepa ett ord.

Extremfallen: $b = 0$ ger ingen längdnormalisering alls, $k_1 = 0$ gör att bara förekomsten räknas (som Bernoulli).

När nyckelordssök slår vektorsök:

När vektorsök vinner: omskrivningar («bil» mot «fordon»), frågor formulerade i naturligt språk, och tvärspråkig sökning.

I praktiken används båda. Hybridsökning med reciprocal rank fusion slår nästan alltid vardera för sig — och det är standarduppsättningen i moderna RAG-system.

import math, re
from collections import Counter

class BM25:
    def __init__(self, korpus, k1=1.5, b=0.75):
        self.k1, self.b = k1, b
        self.dok = [re.findall(r"\w+", d.lower()) for d in korpus]
        self.text = korpus
        self.N = len(self.dok)
        self.langd = [len(d) for d in self.dok]
        self.avgdl = sum(self.langd) / self.N
        self.df = Counter(t for d in self.dok for t in set(d))
        self.tf = [Counter(d) for d in self.dok]

    def idf(self, t):
        n = self.df.get(t, 0)
        return math.log((self.N - n + 0.5) / (n + 0.5) + 1)

    def poang(self, fraga, i):
        s = 0.0
        for t in re.findall(r"\w+", fraga.lower()):
            f = self.tf[i][t]
            if not f:
                continue
            namnare = f + self.k1 * (1 - self.b + self.b * self.langd[i] / self.avgdl)
            s += self.idf(t) * f * (self.k1 + 1) / namnare
        return s

    def sok(self, fraga, k=3):
        p = sorted(((self.poang(fraga, i), i) for i in range(self.N)), reverse=True)
        return [(self.text[i], round(s, 3)) for s, i in p[:k] if s > 0]

korpus = [
    "Felkod E404 betyder att sidan inte hittades",
    "Sidan kunde inte hittas och servern svarade med ett fel",
    "Felkod E500 är ett internt serverfel",
]
bm = BM25(korpus)
for traff, p in bm.sok("E404"):
    print(f"{p:.3f}  {traff}")
# 1.833  Felkod E404 betyder att sidan inte hittades
#  ← exakt term: vektorsök hade rankat de två första nästan lika

# Mättnaden — det som skiljer BM25 från TF-IDF
k1 = 1.5
for f in (1, 2, 5, 20, 100):
    print(f"f={f:>3}  tfidf {f:>5.1f}   bm25 {f * (k1 + 1) / (f + k1):.2f}")
# f=  1  tfidf   1.0   bm25 1.00
# f=  5  tfidf   5.0   bm25 1.92
# f=100  tfidf 100.0   bm25 2.46   ← taket är k1 + 1 = 2.5