La clasificación de consultas es uno de los problemas fundamentales en la recuperación de información (IR), [1] la disciplina científica/de ingeniería detrás de los motores de búsqueda . [2] Dada una consulta q y una colección D de documentos que coinciden con la consulta, el problema es clasificar, es decir, ordenar, los documentos en D según algún criterio para que los "mejores" resultados aparezcan al principio de la lista de resultados que se muestra al usuario. La clasificación en términos de recuperación de información es un concepto importante en la ciencia informática y se utiliza en muchas aplicaciones diferentes, como consultas de motores de búsqueda y sistemas de recomendación . [3] La mayoría de los motores de búsqueda utilizan algoritmos de clasificación para proporcionar a los usuarios resultados precisos y relevantes . [4]
El concepto de PageRank se remonta a la década de 1940 y la idea se originó en el campo de la economía. En 1941, Wassily Leontief desarrolló un método iterativo para valorar el sector de un país basándose en la importancia de otros sectores que le suministraban recursos. En 1965, Charles H Hubbell, de la Universidad de California en Santa Bárbara , publicó una técnica para determinar la importancia de los individuos basándose en la importancia de las personas que los respaldan. [5]
Gabriel Pinski y Francis Narin idearon un método para clasificar las revistas. [6] Su regla era que una revista es importante si es citada por otras revistas importantes. Jon Kleinberg , un científico informático de la Universidad de Cornell , desarrolló un método casi idéntico al PageRank , que se denominó Hypertext Induced Topic Search o HITS, y que trataba a las páginas web como "centros" y "autoridades".
El algoritmo PageRank de Google fue desarrollado en 1998 por los fundadores de Google, Sergey Brin y Larry Page , y es una parte clave del método de Google para clasificar páginas web en los resultados de búsqueda . [7] Todos los métodos anteriores son algo similares, ya que todos explotan la estructura de los enlaces y requieren un enfoque iterativo. [8]
Las funciones de clasificación se evalúan por diversos medios; uno de los más simples es determinar la precisión de los primeros k resultados mejor clasificados para algunos k fijos ; por ejemplo, la proporción de los 10 resultados principales que son relevantes, en promedio, en muchas consultas.
Los modelos IR se pueden dividir en tres tipos: modelos booleanos o BIR, modelos de espacio vectorial y modelos probabilísticos . [9] Se pueden encontrar varias comparaciones entre modelos de recuperación en la literatura (por ejemplo, [10] ).
El modelo booleano o BIR es un modelo de consulta de referencia simple en el que cada consulta sigue los principios subyacentes del álgebra relacional con expresiones algebraicas y en el que los documentos no se recuperan a menos que coincidan completamente entre sí. Dado que la consulta recupera el documento (1) o no lo recupera (0), no existe una metodología para clasificarlos.
Dado que el modelo booleano solo recupera coincidencias completas, no aborda el problema de los documentos que coinciden parcialmente. El modelo de espacio vectorial resuelve este problema al introducir vectores de elementos de índice, cada uno de los cuales tiene pesos asignados. Los pesos varían de positivos (si coinciden completamente o en cierta medida) a negativos (si no coinciden o coinciden de manera completamente opuesta) si hay documentos presentes. Frecuencia de términos: la frecuencia inversa de documentos ( tf-idf ) es una de las técnicas más populares, donde los pesos son términos (por ejemplo, palabras, palabras clave, frases, etc.) y las dimensiones son la cantidad de palabras dentro del corpus.
La puntuación de similitud entre la consulta y el documento se puede encontrar calculando el valor del coseno entre el vector de ponderación de la consulta y el vector de ponderación del documento utilizando la similitud del coseno . Se pueden obtener los documentos deseados clasificándolos según la puntuación de similitud y se pueden obtener los k documentos principales que tengan las puntuaciones más altas o sean más relevantes para el vector de consulta.
En el modelo probabilístico, la teoría de la probabilidad se ha utilizado como un medio principal para modelar el proceso de recuperación en términos matemáticos. El modelo de probabilidad de recuperación de información fue introducido por Maron y Kuhns en 1960 y desarrollado posteriormente por Roberston y otros investigadores. Según Spack Jones y Willett (1997): La razón para introducir conceptos probabilísticos es obvia: los sistemas de IR tratan con lenguaje natural, y este es demasiado impreciso para permitir que un sistema indique con certeza qué documento será relevante para una consulta en particular.
El modelo aplica la teoría de probabilidad a la recuperación de información (un evento tiene una probabilidad de ocurrencia de entre el 0 y el 100 por ciento), es decir, en el modelo de probabilidad, la relevancia se expresa en términos de probabilidad. Aquí, los documentos se clasifican en orden decreciente de probabilidad de relevancia. Tiene en cuenta el elemento de incertidumbre en el proceso de recuperación de información, es decir, la incertidumbre sobre si los documentos recuperados por el sistema son relevantes para una consulta determinada.
El modelo de probabilidad pretende estimar y calcular la probabilidad de que un documento sea relevante para una consulta determinada basándose en algunos métodos. El “evento” en este contexto de recuperación de información se refiere a la probabilidad de relevancia entre una consulta y un documento. A diferencia de otros modelos de recuperación de información, el modelo de probabilidad no trata la relevancia como una medida exacta de error o coincidencia.
El modelo adopta varios métodos para determinar la probabilidad de relevancia entre consultas y documentos. La relevancia en el modelo de probabilidad se juzga según la similitud entre consultas y documentos. El juicio de similitud depende además de la frecuencia de los términos.
Por lo tanto, para una consulta que consta de un solo término (B), la probabilidad de que un documento en particular (Dm) se considere relevante es la proporción de usuarios que envían el término de consulta (B) y consideran que el documento (Dm) es relevante en relación con el número de usuarios que enviaron el término (B). Como se representa en el modelo de Maron y Kuhn, se puede representar como la probabilidad de que los usuarios que envían un término de consulta en particular (B) consideren que un documento individual (Dm) es relevante.
Según Gerard Salton y Michael J. McGill, la esencia de este modelo es que si se pueden calcular estimaciones de la probabilidad de ocurrencia de varios términos en documentos relevantes, entonces se pueden estimar las probabilidades de que se recupere un documento, dado que sea relevante, o que no lo sea. [11]
Varios experimentos han demostrado que el modelo probabilístico puede dar buenos resultados. Sin embargo, estos resultados no han sido lo suficientemente mejores que los obtenidos utilizando el modelo booleano o el modelo de espacio vectorial. [12] [13]
Las medidas de evaluación más comunes son la precisión, la recuperación y la puntuación f. Se calculan utilizando conjuntos de documentos no ordenados. Estas medidas deben ampliarse o deben definirse nuevas medidas para evaluar los resultados de recuperación clasificados que son estándar en los motores de búsqueda modernos. En un contexto de recuperación clasificada, los conjuntos apropiados de documentos recuperados están dados naturalmente por los k documentos recuperados más importantes. Para cada uno de estos conjuntos, los valores de precisión y recuperación se pueden representar gráficamente para dar una curva de precisión-recuperación. [14]
La precisión mide la exactitud del proceso de recuperación. Si el conjunto real de documentos relevantes se denota por I y el conjunto de documentos recuperados se denota por O, entonces la precisión viene dada por:
La recuperación es una medida de la completitud del proceso de IR. Si el conjunto real de documentos relevantes se denota por I y el conjunto de documentos recuperados se denota por O, entonces la recuperación se da por:
La puntuación F1 intenta combinar la precisión y la recuperación. Es la media armónica de las dos. Si P es la precisión y R es la recuperación, la puntuación F se obtiene de la siguiente manera:
El algoritmo PageRank genera una distribución de probabilidad que se utiliza para representar la probabilidad de que una persona que haga clic al azar en los enlaces llegue a una página determinada. El PageRank se puede calcular para colecciones de documentos de cualquier tamaño. En varios artículos de investigación se supone que la distribución se divide de manera uniforme entre todos los documentos de la colección al comienzo del proceso computacional. Los cálculos de PageRank requieren varias pasadas por la colección para ajustar los valores aproximados de PageRank para que reflejen más fielmente el valor teórico real. Las fórmulas se dan a continuación:
es decir, el valor de PageRank para una página u depende de los valores de PageRank para cada página v contenida en el conjunto B u (el conjunto que contiene todas las páginas que enlazan a la página u ), dividido por la cantidad L ( v ) de enlaces de la página v .
De manera similar a PageRank , HITS utiliza el análisis de enlaces para analizar la relevancia de las páginas, pero solo funciona en pequeños conjuntos de subgráficos (en lugar de en el gráfico web completo) y además depende de la consulta. Los subgráficos se clasifican según los pesos en los centros y las autoridades donde se obtienen y muestran las páginas que ocupan el puesto más alto. [15]
