Okapi BM25

Okapi BM25 es una función de ranking utilizada en Recuperación de información para la asignación de relevancia a los documentos en un buscador, dicho de otra forma, es una función que nos permite ordenar por relevancia los documentos que contienen las palabras que el usuario ha introducido en la caja de búsqueda de un buscador como Google, Yahoo! o Live.

Esta función está basada en los modelos probabilísticos de Recuperación de información, concretamente en el BIR (Binary Independent Retrieval) desarrollado por Stephen E. Robertson y Karen Spärck Jones en los años 70.

El nombre de Okapi viene del primer sistema que implementó esta función de ranking, el cual fue desarrollado por Stephen Walker en la City University de Londres

La función de ranking

BM25 se basa en el concepto de bolsa de palabras mediante al cual se representan los documentos que deseamos ordenar en función de su relevancia con una consulta dada.

Dada una consulta $Q$, que contiene las palabras clave $q1,...,qn$, el valor de relevancia asignado mediante la función BM25 para el documentos $D$ será:

$score(D,Q)=\sum _{i=1}^{n}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|}{avgdl}})}}$

donde $f(qi,D)$ es la frecuencia de aparición en el documento $D$ de los términos que aparecen en la consulta $Q$, $|D|$ es la longitud del documento $D$ (en número de palabras), y $avgdl$ es la longitud media de los documentos en la colección sobre la cual estamos realizando la búsqueda. $k1$ y $b$ son parámetros que permiten ajustar la función a las características concretas de la colección con la que estamos trabajando. Aunque estos parámetros suelen depender de las características concretas de cada colección normalmente se asignan los valores $k1=2.0$ o $k1=1.2$ y $b=0.75$, los cuales se han establecido a partir de los experimentos que durante años se han realizado en las conferencias TREC. $IDF(qi)$ es el peso IDF (inverse document frequency) de las palabras clave que aparecen en la consulta $Q$. Normalmente el IDF se calcula mediante la siguiente función:

$IDF(q_{i})=\log {\frac {N-n(q_{i})+0.5}{n(q_{i})+0.5}}$

donde $N$ es el número total de documentos en la colección, y $n(qi)$ es el número de documentos que contienen la palabra clave $qi$.

Véase también

• Modelo de espacio vectorial
• Recuperación de información
• Implementación BM25 en Lucene [1]

Bibliografía

• A definitive guide to the TFxIDF variants, including BMxx variants, and the evolution of BM25
• Stephen E. Robertson; Steve Walker; Susan Jones; Micheline Hancock-Beaulieu; Mike Gatford (November 1994). Okapi at TREC-3. Proceedings of the Third Text REtrieval Conference (TREC 1994). Gaithersburg, USA. 
• Stephen E. Robertson; Steve Walker; Micheline Hancock-Beaulieu (November 1998). Okapi at TREC-7. Proceedings of the Seventh Text REtrieval Conference. Gaithersburg, USA. 
• Spärck Jones, K.; Walker, S.; Robertson, S. E. (2000). «A probabilistic model of information retrieval: Development and comparative experiments: Part 1». Information Processing & Management 36 (6): 779-808. doi:10.1016/S0306-4573(00)00015-7. 
• Spärck Jones, K.; Walker, S.; Robertson, S. E. (2000). «A probabilistic model of information retrieval: Development and comparative experiments: Part 2». Information Processing & Management 36 (6): 809-840. doi:10.1016/S0306-4573(00)00016-9. 
• Stephen Robertson & Hugo Zaragoza (2009). The Probabilistic Relevance Framework: BM25 and Beyond 3 (4). Found. Trends Inf. Retr. pp. 333-389. doi:10.1561/1500000019. 

Enlaces externos

• Robertson, Stephen; Zaragoza, Hugo (2009). The Probabilistic Relevance Framework: BM25 and Beyond. NOW Publishers, Inc. ISBN 978-1-60198-308-4. 

• Datos: Q2068750