Okapi BM25

Okapi BM25 es una función de clasificación utilizada por los motores de búsqueda para clasificar documentos por su relevancia para una consulta de búsqueda determinada. Se basa en un modelo probabilístico desarrollado en las décadas de 1970 y 1980 por Stephen Robertson , Karen Spark Jones y otros.

La función en sí se llama BM25 (BM del inglés best match ), pero a menudo se la llama "Okapi BM25" por el nombre del motor de búsqueda Okapi, creado en la City University London en las décadas de 1980 y 1990, en el que se aplicó por primera vez esta función. .

BM25 y sus diversas modificaciones posteriores (p. ej., BM25F) son modernas funciones de clasificación similares a TF-IDF que se utilizan ampliamente en la práctica en los motores de búsqueda. En la búsqueda web, estas funciones de clasificación a menudo se incluyen como componentes de una función de clasificación más compleja, a menudo aprendida por máquina .

La función de clasificación

BM25 es una función de búsqueda sobre un conjunto desordenado de términos (“ bolsa de palabras ”) y un conjunto de documentos, que evalúa en función de la aparición de palabras de consulta en cada documento, sin tener en cuenta la relación entre ellas (por ejemplo, proximidad). No es una sola función, sino una familia de funciones con diferentes componentes y parámetros. Una forma común de esta función se describe a continuación.

Dada una consulta que contiene las palabras , la función BM25 ofrece la siguiente evaluación de la relevancia del documento para la consulta : $q$ $q_{1},...,q_{n}$ $D$ $q$

{\text{puntuación}}(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{promedio))))))))),

donde es la frecuencia de palabras (frecuencia del término inglés , TF ) en el documento , es la longitud del documento (la cantidad de palabras que contiene) y es la longitud promedio del documento en la colección. y son coeficientes libres, por lo general se eligen como y . $f(q_{i},D)$ $q_{yo}$ $D$ $|D|$ $promedio$ $k_{1}$ $b$ $k_{1}=2.0$ $b=0,75$

${\text{FDI}}(q_{i})$ hay una frecuencia de documento inversa ( ing. frecuencia de documento inversa, IDF ) palabras . Hay varias interpretaciones de la IDF y ligeras variaciones en su fórmula. Clásicamente, se define como: $q_{yo}$

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

donde es el número total de documentos de la colección y es el número de documentos que contienen . Pero con mayor frecuencia, se utilizan versiones "suavizadas" de esta fórmula, por ejemplo: $norte$ $n(q_{i})$ $q_{yo}$

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

La fórmula IDF anterior tiene el siguiente inconveniente. Para palabras en más de la mitad de los documentos de la colección, el valor IDF es negativo. Así, en presencia de dos documentos casi idénticos, uno de los cuales tiene una palabra y el otro no, el segundo puede recibir una puntuación más alta.

En otras palabras, las palabras que aparecen con frecuencia estropearán la puntuación final del documento. Esto no es deseable, por lo que en muchas aplicaciones la fórmula anterior se puede ajustar de las siguientes maneras:

Ignorar en general todos los términos negativos en la suma (lo que equivale a entrar en la lista de exclusión e ignorar todas las palabras de alta frecuencia correspondientes);
Imponga un límite inferior a IDF : si IDF es menor que , entonces considérelo igual a . $\varepsilon$ $\varepsilon$ $\varepsilon$
Utilice otra fórmula IDF que no acepte valores negativos.

Interpretación de IDF en la teoría de la información

Suponga que la palabra de búsqueda aparece en los documentos. Luego, un documento seleccionado al azar contiene una palabra con probabilidad (donde es la cardinalidad del conjunto de documentos de la colección). En este caso, el valor de información de la frase " contiene " será el siguiente: $q$ $n(q)$ $D$ ${\frac{n(q)}{N}}$ $norte$ $D$ $q$

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

Ahora suponga que hay dos palabras de búsqueda y . Si ingresan al documento de forma independiente, la probabilidad de encontrarlos en un documento seleccionado al azar es la siguiente: $q_{1}$ $q_{2}$ $D$

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

y contenido de este evento

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

Esto es aproximadamente lo que expresa el componente IDF en BM25.

Modificaciones

Con valores extremos del coeficiente en la función BM25 se obtienen funciones de ranking, conocidas como BM11 (at ) y BM15 (at ). [una] $b$ $b=1$ $b=0$
BM25F [2] es una modificación de BM25, en la que el documento se considera como una colección de varios campos (como, por ejemplo, encabezados, texto del cuerpo, texto del enlace), cuyas longitudes se normalizan de forma independiente, y cada uno de los cuales se le puede asignar su propio grado de importancia en la función de clasificación final.

Notas

↑ Xapian: Esquema de ponderación BM25 . Fecha de acceso: 30 de enero de 2010. Archivado desde el original el 15 de marzo de 2010. (indefinido)
↑ Hugo Zaragoza, Nick Craswell, Michael Taylor, Suchi Saria y Stephen Robertson. Microsoft Cambridge en TREC-13: pistas Web y HARD. Archivado el 26 de agosto de 2009 en Wayback Machine In Proceedings of TREC-2004, 2004.

Literatura

Stephen E. Robertson, Steve Walker, Susan Jones, Micheline Hancock-Beaulieu y Mike Gatford. Okapi en TREC-3. En Actas de la Tercera Conferencia de Recuperación de Texto (TREC 1994). Gaithersburg, Estados Unidos, noviembre de 1994.
Stephen E. Robertson, Steve Walker y Micheline Hancock-Beaulieu. Okapi en TREC-7. En Actas de la Séptima Conferencia de Recuperación de Texto. Gaithersburg, Estados Unidos, noviembre de 1998.
Karen Spärck Jones, Steve Walker y Stephen E. Robertson. Un modelo probabilístico de recuperación de información: desarrollo y experimentos comparativos (partes 1 y 2). Procesamiento y Gestión de la Información, 36(6):779-840. 2000.
Nick Craswell, Hugo Zaragoza, Stephen Robertson. Microsoft Cambridge en TREC-14: Enterprise Track. En Actas de la Decimocuarta Conferencia de recuperación de texto (TREC 2005). Gaithersburg, EE. UU., noviembre de 2005. Describe la aplicación y el ajuste de Okapi BM25F.