Okapi BM25

Función de clasificación utilizada por los motores de búsqueda

En la recuperación de información , Okapi BM25 ( BM es la abreviatura de best matching ) es una función de clasificación que utilizan los motores de búsqueda para estimar la relevancia de los documentos para una consulta de búsqueda determinada. Se basa en el marco de recuperación probabilística desarrollado en los años 1970 y 1980 por Stephen E. Robertson , Karen Spärck Jones y otros.

El nombre de la función de clasificación actual es BM25 . El nombre completo, Okapi BM25 , incluye el nombre del primer sistema que lo utilizó, que fue el sistema de recuperación de información Okapi, implementado en la City University de Londres ^[1] en los años 1980 y 1990. BM25 y sus variantes más nuevas, por ejemplo BM25F (una versión de BM25 que puede tener en cuenta la estructura del documento y el texto de anclaje), representan funciones de recuperación similares a TF-IDF utilizadas en la recuperación de documentos. ^[2]

La función de clasificación

BM25 es una función de recuperación de palabras que clasifica un conjunto de documentos en función de los términos de consulta que aparecen en cada documento, independientemente de su proximidad dentro del documento. Es una familia de funciones de puntuación con componentes y parámetros ligeramente diferentes. Una de las instancias más destacadas de la función es la siguiente.

Dada una consulta Q , que contiene palabras clave , la puntuación BM25 de un documento D es: ${\displaystyle q_{1},...,q_{n}}$

${\displaystyle {\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 \left(1-b+b\cdot {\frac {|D|}{\text{avgdl}}}\right)}}}$

donde es el número de veces que la palabra clave aparece en el documento D , es la longitud del documento D en palabras y avgdl es la longitud promedio del documento en la colección de texto de la que se extraen los documentos. y b son parámetros libres, generalmente elegidos, en ausencia de una optimización avanzada, como y . ^[3] es el peso IDF ( frecuencia inversa del documento ) del término de consulta . Generalmente se calcula como: ${\displaystyle f(q_{i},D)}$ ${\displaystyle q_{i}}$ ${\displaystyle |D|}$ ${\displaystyle k_{1}}$ ${\displaystyle k_{1}\in [1.2,2.0]}$ ${\displaystyle b=0.75}$ ${\displaystyle {\text{IDF}}(q_{i})}$ ${\displaystyle q_{i}}$

${\displaystyle {\text{IDF}}(q_{i})=\ln \left({\frac {N-n(q_{i})+0.5}{n(q_{i})+0.5}}+1\right)}$

donde N es el número total de documentos de la colección y es el número de documentos que contienen . ${\displaystyle n(q_{i})}$ ${\displaystyle q_{i}}$

Existen varias interpretaciones del IDF y ligeras variaciones en su fórmula. En la derivación original del BM25, el componente IDF se deriva del modelo de independencia binaria .

Interpretación teórica de la información de las FDI

He aquí una interpretación de la teoría de la información. Supongamos que un término de búsqueda aparece en los documentos. Entonces, un documento elegido al azar contendrá el término con una probabilidad (donde es nuevamente la cardinalidad del conjunto de documentos en la colección). Por lo tanto, el contenido de información del mensaje " contiene " es: ${\displaystyle q}$ ${\displaystyle n(q)}$ ${\displaystyle D}$ ${\displaystyle {\frac {n(q)}{N}}}$ ${\displaystyle N}$ ${\displaystyle D}$ ${\displaystyle q}$

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

Ahora supongamos que tenemos dos términos de consulta y . Si los dos términos aparecen en documentos de forma totalmente independiente entre sí, entonces la probabilidad de ver tanto como en un documento elegido al azar es: ${\displaystyle q_{1}}$ ${\displaystyle q_{2}}$ ${\displaystyle q_{1}}$ ${\displaystyle q_{2}}$ ${\displaystyle D}$

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

y el contenido informativo de dicho evento es:

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

Con una pequeña variación, esto es exactamente lo que expresa el componente IDF de BM25.

Modificaciones

• En los valores extremos del coeficiente b, BM25 se convierte en funciones de clasificación conocidas como BM11 (para ) y BM15 (para ). ^[4] ${\displaystyle b=1}$ ${\displaystyle b=0}$
• BM25F ^{[5] [2]} (o el modelo BM25 con extensión a campos ponderados múltiples ^[6] ) es una modificación de BM25 en la que se considera que el documento está compuesto de varios campos (como titulares, texto principal, texto de anclaje) con posibles diferentes grados de importancia, saturación de relevancia de términos y normalización de longitud. BM25F define cada tipo de campo como un flujo , aplicando una ponderación por flujo para escalar cada flujo contra la puntuación calculada.

• BM25+ ^[7] es una extensión de BM25. BM25+ se desarrolló para abordar una deficiencia del estándar BM25 en la que el componente de normalización de frecuencia de términos por longitud del documento no tiene un límite inferior adecuado; como resultado de esta deficiencia, los documentos largos que coinciden con el término de consulta a menudo pueden ser calificados injustamente por BM25 como si tuvieran una relevancia similar a los documentos más cortos que no contienen el término de consulta en absoluto. La fórmula de calificación de BM25+ solo tiene un parámetro libre adicional (un valor predeterminado es 1.0 en ausencia de datos de entrenamiento) en comparación con BM25: ${\displaystyle \delta }$

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

Referencias

1. "OKAPI". smcse.city.ac.uk . Consultado el 16 de octubre de 2023 .
2. Stephen Robertson y Hugo Zaragoza (2009). "El marco de relevancia probabilística: BM25 y más allá". Fundamentos y tendencias en la recuperación de información . 3 (4): 333–389. CiteSeerX 10.1.1.156.5282 . doi :10.1561/1500000019. S2CID  207178704. 
3. Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze. Introducción a la recuperación de información , Cambridge University Press, 2009, pág. 233.
4. "El esquema de ponderación BM25".
5. Hugo Zaragoza, Nick Craswell, Michael Taylor, Suchi Saria y Stephen Robertson. Microsoft Cambridge en TREC-13: Web y HARD tracks. En Actas de TREC-2004.
6. Robertson, Stephen; Zaragoza, Hugo; Taylor, Michael (13 de noviembre de 2004). "Extensión simple de BM25 a campos ponderados múltiples". Actas de la decimotercera conferencia internacional de la ACM sobre gestión de la información y el conocimiento . CIKM '04. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 42–49. doi :10.1145/1031171.1031181. ISBN . 978-1-58113-874-0.S2CID16628332  .​
7. Yuanhua Lv y ChengXiang Zhai. Normalización de frecuencia de términos de límite inferior. En Actas de CIKM'2011, páginas 7-16.

Referencias generales

• Stephen E. Robertson; Steve Walker; Susan Jones; Micheline Hancock-Beaulieu y Mike Gatford (noviembre de 1994). Okapi en TREC-3. Actas de la Tercera Conferencia sobre Recuperación de Textos (TREC 1994). Gaithersburg, Estados Unidos.
• Stephen E. Robertson; Steve Walker y Micheline Hancock-Beaulieu (noviembre de 1998). Okapi en TREC-7. Actas de la Séptima Conferencia de Recuperación de Textos. Gaithersburg, EE. UU.
• Spärck Jones, K. ; Walker, S.; Robertson, SE (2000). "Un modelo probabilístico de recuperación de información: Desarrollo y experimentos comparativos: Parte 1". Procesamiento y gestión de la información . 36 (6): 779–808. CiteSeerX  10.1.1.134.6108 . doi :10.1016/S0306-4573(00)00015-7.
• Spärck Jones, K. ; Walker, S.; Robertson, SE (2000). "Un modelo probabilístico de recuperación de información: Desarrollo y experimentos comparativos: Parte 2". Procesamiento y gestión de la información . 36 (6): 809–840. doi :10.1016/S0306-4573(00)00016-9.
• Stephen Robertson y Hugo Zaragoza (2009). "El marco probabilístico de relevancia: BM25 y más allá". Fundamentos y tendencias en la recuperación de información . 3 (4): 333–389. CiteSeerX  10.1.1.156.5282 . doi :10.1561/1500000019. S2CID  207178704.

Enlaces externos

• Robertson, Stephen ; Zaragoza, Hugo (2009). El marco de relevancia probabilística: BM25 y más allá (PDF) . NOW Publishers, Inc. ISBN 978-1-60198-308-4.