Okapi BM25

Az Okapi BM25 egy rangsoroló funkció , amelyet a keresőmotorok használnak a dokumentumok egy adott keresési lekérdezés szempontjából való relevanciájának rendezésére . Az 1970-es és 1980-as években Stephen Robertson , Karen Spark Jones és mások által kidolgozott valószínűségi modellen alapul .

Magát a függvényt BM25-nek (BM az angol best match szóból) hívják, de gyakran "Okapi BM25"-nek is nevezik az 1980-as és 1990-es években a londoni City Egyetemen létrehozott Okapi keresőmotor neve után , amelyben ezt a funkciót először alkalmazták. .

A BM25 és különféle későbbi módosításai (pl. BM25F) modern, TF-IDF- szerű rangsoroló függvények, amelyeket a gyakorlatban széles körben alkalmaznak a keresőkben. A webes keresésben ezek a rangsorolási függvények gyakran egy összetettebb, gyakran gépi úton tanult rangsoroló függvény összetevőiként szerepelnek.

A rangsorolási függvény

A BM25 egy keresőfunkció egy rendezetlen kifejezéshalmazon (" zsák szavak ") és egy dokumentumkészleten, amelyet az egyes dokumentumokban előforduló lekérdezőszavak alapján értékel, anélkül, hogy figyelembe venné a köztük fennálló kapcsolatot (pl. közelség). Ez nem egyetlen függvény, hanem különböző komponensekkel és paraméterekkel rendelkező függvénycsalád. Az alábbiakban ennek a funkciónak az egyik gyakori formáját ismertetjük.

Adott a szavakat tartalmazó lekérdezés , akkor a BM25 függvény a következő értékelést adja a dokumentum relevanciájáról a lekérdezés szempontjából : $K$ $q_{1},...,q_{n}$ $D$ $K$

{\text{score}}(D,Q)=\sum _{{i=1}}^{{n}}{\text{IDF}}(q_{i})\cdot {\frac {f( q_{i},D)\cdot (k_{1}+1)}{f(q_{i},D)+k_{1}\cdot (1-b+b\cdot {\frac {|D| }{{\text{avgdl))))))))

ahol a szógyakoriság ( angol kifejezés gyakorisága, TF ) a dokumentumban , a dokumentum hossza (a benne lévő szavak száma), és a gyűjteményben lévő dokumentum átlagos hossza. és szabad együtthatók, általában és ként választjuk őket . $f(q_{i},D)$ $q_{i}$ $D$ $|D|$ $avgdl$ $k_{1}$ $b$ $k_{1}=2,0$ $b=0,75$

${\text{IDF}}(q_{i})$ van egy inverz dokumentumgyakoriság ( eng. inverz dokumentum gyakoriság, IDF ) szavak . Az IDF-nek többféle értelmezése van, és képletében kismértékű eltérések vannak. Klasszikusan a következőképpen határozzák meg: $q_{i}$

\log {\frac {N}{n(q_{i})}},

ahol a gyűjteményben lévő dokumentumok teljes száma és a -t tartalmazó dokumentumok száma . De gyakrabban használják a képlet „simított” változatait, például: $N$ $n(q_{i})$ $q_{i}$

{\text{IDF}}(q_{i})=\log {\frac {Nn(q_{i})+0,5}{n(q_{i})+0,5}},

A fenti IDF képletnek a következő hátránya van. A gyűjteményben található dokumentumok több mint felében szereplő szavak esetében az IDF-érték negatív. Így bármely két majdnem azonos dokumentum jelenlétében, amelyek közül az egyikben van szó, a másikban nincs, a második magasabb pontszámot kaphat.

Más szóval, a gyakran előforduló szavak elrontják a dokumentum végső pontszámát. Ez nem kívánatos, ezért sok alkalmazásban a fenti képlet a következő módokon módosítható:

Általában figyelmen kívül hagyja az összes negatív kifejezést az összegben (ami egyenértékű a stoplistába lépéssel és az összes megfelelő nagy gyakoriságú szó figyelmen kívül hagyásával);
Állítson be alsó korlátot az IDF- re: ha az IDF kisebb, mint , akkor tekintse egyenlőnek a -val . $\varepsilon$ $\varepsilon$ $\varepsilon$
Használjon másik IDF-képletet, amely nem fogad el negatív értékeket.

Az IDF értelmezése az információelméletben

Tegyük fel, hogy a keresett szó előfordul a dokumentumokban. Ekkor egy véletlenszerűen kiválasztott dokumentum tartalmaz egy szót valószínűséggel (hol van a gyűjtemény dokumentumkészletének számossága). Ebben az esetben a " tartalmazza " kifejezés információs értéke a következő lesz: $q$ $n(q)$ $D$ ${\frac {n(q)}{N}}$ $N$ $D$ $q$

-\log {\frac {n(q)}{N}}=\log {\frac {N}{n(q))).

Most tegyük fel, hogy van két keresőszó és . Ha egymástól függetlenül írják be a dokumentumot, akkor a véletlenszerűen kiválasztott dokumentumban való megtalálásának valószínűsége a következő: $q_{1}$ $q_{2}$ $D$

{\frac {n(q_{1})}{N}}\cdot {\frac {n(q_{2})}{N}},

és ennek az eseménynek a tartalma

\sum _{{i=1}}^{{2}}\log {\frac {N}{n(q_{i})}}.

Nagyjából ezt fejezi ki a BM25 IDF komponense.

Módosítások

A BM25 függvény együtthatójának szélsőséges értékeivel a BM11 (at ) és BM15 (at ) néven ismert rangsoroló függvényeket kapunk . [egy] $b$ $b=1$ $b=0$
A BM25F [2] a BM25 egy olyan módosítása, amelyben a dokumentum több mező gyűjteményének tekinthető (például címsorok, törzsszöveg, linkszöveg), amelyek hossza egymástól függetlenül normalizálva van, és amelyek mindegyike a végső rangsorolási függvényben hozzárendelhető a saját jelentősége.

Jegyzetek

↑ Xapian: BM25 súlyozási séma . Hozzáférés dátuma: 2010. január 30. Az eredetiből archiválva : 2010. március 15. (határozatlan)
↑ Hugo Zaragoza, Nick Craswell, Michael Taylor, Suchi Saria és Stephen Robertson. Microsoft Cambridge a TREC-13-ban: Web és HARD sávok. Archiválva : 2009. augusztus 26., a Wayback Machine In Proceedings of TREC-2004, 2004.

Irodalom

Stephen E. Robertson, Steve Walker, Susan Jones, Micheline Hancock-Beaulieu és Mike Gatford. Okapi a TREC-3-nál. In Proceedings of the Third Text Retrieval Conference (TREC 1994). Gaithersburg, USA, 1994. november.
Stephen E. Robertson, Steve Walker és Micheline Hancock-Beaulieu. Okapi a TREC-7-nél. A hetedik szövegkereső konferencia anyagában. Gaithersburg, USA, 1998. november.
Karen Spärck Jones, Steve Walker és Stephen E. Robertson. Az információkeresés valószínűségi modellje: fejlesztés és összehasonlító kísérletek (1. és 2. rész). Információfeldolgozás és -kezelés, 36(6):779-840. 2000.
Nick Craswell, Hugo Zaragoza, Stephen Robertson. Microsoft Cambridge a TREC-14-ben: Enterprise Track. In Proceedings of the Fourteenth Text Retrieval Conference (TREC 2005). Gaithersburg, USA, 2005. november. Leírja az Okapi BM25F alkalmazását és hangolását.