jueves, 10 de enero de 2013

Práctica11. Método de evaluación de un sistema de recuperación de información

La evaluación de sistemas de información y recuperación tiene una aplicación muy clara en el apartado de los algoritmos de recuperación y clasificación de contenidos. En este sentido, la práctica propuesta pone al alumno en el caso real del proceso de evaluación de un algoritmo de recuperación y clasificación automática.

A cada alumno se le asignará en clase una serie de categorías temáticas que comprenden unas páginas web de resultados. Se deberá comprobar que los contenidos recuperados bajo el paraguas de la categoría temática asignada, lo están correctamente. Esto implica determinar distintos valores:

  • Botón Marcar Relevante - Relevancia del 100% significa que el contenido está conforme con la categoría asignada automáticamente por el sistema.
  • Botón Marcar Irrelevante - Relevancia del 0% significa que el contenido es completamente opuesto a la categoría asignada automáticamente por el sistema.
  • Botón Marcar Grado de Relevancia - Relevancia del 80% - 60% - 40% y 20% significa que se ha considerado un documento parcialmente relevante en la medida porcentual que se indica.

Se recomienda hacer click en un único botón. En caso de equivocación, marcar seguidamente el botón correcto. Esto deshará la operación anterior y validará como buena la última efectuada. También se advierte, que según se evalúa el contenido, automáticamente los botones cambian de color, permitiendo al evaluador distinguir fácilmente los resultados que quedan por evaluar.

El proceso de evaluación se registra automáticamente en la base de datos, de tal manera que posteriormente se pueda comprobar si el algoritmo de clasificación acertó o no en la categorización de los contenidos en todas las áreas de conocimiento o por el contrario falló en algunas, así como determinar el motivo del fallo. Esto significa que no es necesario enviar ninguna práctica a través del campus virtual, ya que según se lleva a cabo la evaluación, ésta se va completando.

El alumno tiene una responsabilidad importante en la consecución de este trabajo, ya que su supervisión y evaluación servirá para determinar el grado de corrección y precisión del sistema de información, por ello se solicita la mayor concentración posible durante este proceso.

Listas de asignación

miércoles, 9 de enero de 2013

Práctica10. Prueba automática del modelo probabilístico

Efectuada la prueba manual del modelo probabilístico, se pueden advertir los detalles que operan durante el cálculo de los coeficientes de similaridad, obteniendo en esencia los pesos ajustados de los términos de la consulta del usuario. Este proceso también se emplea en muchos sistemas de recuperación, completamente automatizados, para tener un punto de vista diferente, se propone el desarrollo de la práctica con un simulador desarrollado ex-profeso par testar el comportamiento del cálculo de pesos de la consulta con una colección real. Se advierte al alumno que algunos de los factores correctores de la formulación empleada, fueron modificados para mejorar los resultados, obtenidos. No obstante la filosofía del modelo sigue intacta y se podrá comprobar el mecanismo de retroalimentación por relevancia que lo caracteriza.

Descargar práctica10. Prueba automática del modelo probabilístico

jueves, 20 de diciembre de 2012

Práctica9. Prueba manual del modelo probabilístico

A partir de las formulaciones del modelo probabilístico, se propone poner a pruena la resolución de una consulta con el modelo probabilístico en modo manual a partir de un fichero diccionario. Se obtendrán los resultados de similaridad para cada documento propuesto para finalmente comparar y discutir los resultados obtenidos.

Descargar práctica9. Prueba manual del modelo probabilístico

miércoles, 19 de diciembre de 2012

Modelo Probabilístico

Desarrollado por Robertson y Sparck Jones, fue introducido entre 1977 y 1979 y es conocido como modelo probabilístico ó de independencia binaria (BIR). Se fundamenta en la representación binaria de los documentos, al igual que en el modelo de recuperación booleano, indicando presencia o ausencia de términos mediante 0 y 1. Su diferencia radica en el método estadístico y en las premisas bajo las que se constituye su funcionamiento estableciendo las siguientes aseveraciones:
  • Según la consulta planteada por el usuario, los documentos de la colección se clasifican en dos grupos; 1) Conjunto de Documentos Relevantes y 2) Conjunto de Documentos Irrelevantes.
  • Existe una respuesta ideal del sistema, constituida por el conjunto de documentos relevantes, a la que se denomina Conjunto de Respuesta Ideal.
  • Existe una Consulta Ideal, que es aquella que proporciona un Conjunto de Respuesta Ideal o lo que es lo mismo el conjunto de documentos relevantes para el usuario.
  • Aunque a priori se desconoce cuál es la Consulta Ideal (el usuario no tiene porqué conocerla), sí se sabe que es una combinación de 0 y 1 por ser un modelo binario de recuperación. Se desconocen por tanto los términos que se deberían introducir para obtener el Conjunto de Respuesta Ideal.
Ponderación
El objetivo del modelo probabilístico es tomar la consulta del usuario para ser refinada sucesivamente hasta obtener el conjunto de respuesta ideal, mediante la reformulación sucesiva de los términos de su consulta, empleando para ello la ponderación de los términos. Esto significa que se modifican los valores 1 (presencia) por un número (peso) que permita acercar la consulta imperfecta a una consulta ideal. El proceso de ponderación de los términos de la consulta es el cálculo de probabilidad de que exista dicho término en el conjunto de los documentos relevantes y la probabilidad de que se encuentre presente en el conjunto de los documentos irrelevantes. Véase figura1.

Figura1. El cálculo de probabilidades como base para la ponderación de los términos

El método por defecto para el cálculo de pesos de los términos de la consulta se puede llevar a cabo mediante la razón de Odds. Es decir, la probabilidad de que el término aparezca en el conjunto de documentos relevantes entre la probabilidad de que el término aparezca en el conjunto de términos irrelevantes, véase figura2.

Figura2. Ratio Odds aplicado al cálculo de pesos de los términos de la consulta del usuario

Esta formulación requiere de un mayor control de precisión, debe observarse que inicialmente se desconoce cuál es el número de documentos relevantes e irrelevantes que conforman la colección. Esta situación, particularmente compleja de averiguar a priori, se resuelve, concediendo unos valores iniciales por defecto, denominados de "Máxima incertidumbre". Para la probabilidad de P(Ti/R) se le asigna el valor 0,5 que es intermedio entre 0 y 1 para indicar que la probabilidad de que el término se encuentre entre los documentos relevantes e irrelevantes es la misma, por ello se denomina de máxima incertidumbre. Para la probabilidad de P(Ti/R¬) se asigna el cociente de dividir la frecuencia de aparición del término en los documentos de la colección, entre el número total de documentos de la colección, véase figura3.

Figura3. Asignación de valores de aproximación inicial

Pero existen más factores que pueden afectar al peso final del término de la consulta del usuario, por ejemplo, cuando se tiene en cuenta que la probabilidad de la relevancia se basa tanto en la presencia como en la ausencia de los términos de la consulta y en la independencia de la distribución de los términos dentro del conjunto de documentos relevantes. En tal caso, se utiliza una formulación derivada para el cálculo de los pesos, que pone en relación el factor independencia de las distribuciones de términos en documentos relevantes, de presencia por relevancia e irrelevancia de una forma mucho más precisa, véase figura4.

Figura4. Método estándar para el cálculo de pesos de los términos de la consulta en el modelo probabilístico de independencia binaria

El cálculo del peso para el término de la consulta "Ti" de la figura4, incluye la suma de logaritmos de las probabilidades de presencia y ausencia en los conjuntos de documentos relevantes CDR (primera parte de la ecuación) y las probabilidades de presencia y ausencia en los conjuntos de documentos irrelevantes CDI (segunda parte de la ecuación). Aplicando los valores de aproximación inicial propuestos anteriormente, su formulación se asemejaría a la que se muestra en la figura5.

Figura5. Asignación de valores de aproximación al método estándar

El cálculo de la similaridad
Para cuantificar la similaridad de los documentos de la colección con la consulta expresada por el usuario se emplea la siguiente formulación, véase figura6, que pone en relación el peso de los términos de la consulta del usuario con los del documento. Se trata de una variante del cálculo de similaridad mediante el producto escalar, en la que el único elemento variable es el peso de la consulta.

Figura6. Cálculo de similaridad del modelo probabilístico

Una vez calculada la similaridad entre la consulta y los documentos de la colección, el sistema es capaz de ordenar los documentos de la colección conforme al orden decreciente de su probabilidad de relevancia con respecto a la consulta del usuario. Dicho de otra forma, se mostrará en primer lugar el documento cuya probabilidad de relevancia sea más alta. El modelo probabilístico, amplía su mecanismo de funcionamiento una vez ofrecidos los resultados al usuario, pidiendo su intervención para que señale la relevancia de los documentos. De esta forma el sistema ajusta mejor el CDR y el CDI, anteriormente mencionados, efectuando una nueva consulta que mejora y adapta el cálculo de los pesos de la consulta. Esta reformulación para el cálculo de los pesos consiste en asignar a la probabilidad de P(Ti/R) el cociente del número de documentos relevantes en los que se encuentra el término de consulta entre el número de documentos relevantes señalados por el usuario. A la probabilidad de P(Ti/R¬) se le asigna el cociente del número total de documento que tiene el término de consulta menos el número de documentos relevantes en los que se encuentra el término de consulta, entre el número total de documentos irrelevantes menos el número de documentos relevantes señalados por el usuario. Véase figura7.

Figura7. Asignación de valores de aproximación sucesivos

En el momento en el que el sistema asigna valores de aproximación sucesivos, se considera que se está retroalimentando con la información proporcionada por el usuario, este fenómeno se denomina, "retroalimentación por relevancia", lo que le permite calcular nuevos pesos para los términos de la consulta y aproximarse al conjunto de respuesta ideal. Este proceso de retroalimentación puede repetirse consecutivamente tantas veces como se configure en el sistema, aunque resulta habitual la repetición de 1 a 2 ciclos.

Ejemplo de aplicación
En la tabla1, se muestra la colección de prueba anteriormente utilizada para explicar otros modelos, como objeto de análisis probabilístico. Para ello obsérvese que se necesita conocer el número total de documentos que compone la colección y el número de documentos en los que aparecen los términos de la consulta del usuario. Ambos factores son esenciales para calcular los pesos de la consulta en una primera aproximación, aplicando el principio de máxima incertidumbre.

Cadena de consulta original del usuario
Los libros y la literatura de Unamuno en la biblioteca de la Universidad de Alcalá
Depuración de la consulta del usuario
Libros Literatura Unamuno Biblioteca Universidad Alcalá
Número total de documentos de la colección: 5235
Fichero diccionario
Documento1
Documento2
q = pesos de la consulta del usuario (aprox. inicial)
Frecuencia de aparición de q en la colección (Nº de docs)
Id
Término
Peso Binario
Peso Binario
T1
Clima
1
0
0
-
T2
Biblioteca
0
1
1,54
149
T3
Universidad
1
0
1,337
232
T4
Alcalá
1
0
1,954
55
T5
España
1
1
0
-
T6
Libros
0
1
0,508
1241
T7
Geografía
0
0
0
-
T8
Población
1
0
0
-
T9
Electricidad
0
0
0
-
T10
Ciencia
0
0
0
-
T11
Social
0
1
0
-
T12
Luz
1
0
0
-
T13
Unamuno
1
1
2,219
34
T14
Física
0
0
0
-
T15
Fluidos
1
0
0
-
T16
Literatura
1
1
0,378
1543
Cálculo de valores de aproximación inicial


Cálculo de similaridad (Primera vuelta)

Sim(doc1,q) = Universidad(1*1,337) + Alcalá(1*1,954) + Unamuno(1*2,219) + Literatura(1*0,378) = 5,888

Sim(doc2,q) = Biblioteca(1*1,54) + Libros(1*0,508) + Unamuno(1*2,219) + Literatura(1*0,378) = 4,645

Tabla1. Cálculo de similaridad según el método probabilístico

Como se observa los documentos de la colección pueden ser representados mediante un vector binario de 0 y 1, lo que implica un cálculo más sencillo de similaridad que se limitará a la suma de los pesos de los términos de las consultas presentes en cada documento de la colección. Aún así, la precisión es muy buena, si se compara con los resultados obtenidos con la formula de producto escalar en el modelo vectorial. Al igual que en aquel caso, también se pueden utilizar vectores de los documentos, conformados por pesos TF-IDF, obteniendo cifras superiores a las mostradas en la tabla1.

En la tabla2, se muestra un ejemplo del proceso de retroalimentación, en la que después de la primera vuelta de ejecución del sistema se ofrecen unos resultados que deberán ser evaluados por el usuario. Entre todos los resultados inspeccionados el usuario marca como relevantes 15 de ellos, de entre los cuales puede estar presente o no el término de la consulta, inicialmente utilizado. Por ejemplo el término "Biblioteca" aparece en 5 de los 15 resultados marcados como relevantes para el usuario. El sistema se vale de esta información, para refinar la consulta, asignando nuevos pesos, mediante la fórmula expresada en las figuras4 y 7. Como resultado de la precisión del usuario, los coeficientes y en definitiva el ordenamiento de los documentos de la colección resulta más exacto ordenando en sentido decreciente los resultados cuya probabilidad de relevancia sea mayor.
 
Cadena de consulta original del usuario
Los libros y la literatura de Unamuno en la biblioteca de la Universidad de Alcalá
Depuración de la consulta del usuario
Libros Literatura Unamuno Biblioteca Universidad Alcalá
Número total de documentos de la colección (N): 5235 // Documentos relevantes para el usuario (V): 15
Fichero diccionario
Doc1
Doc2
q = pesos de la consulta del usuario (aprox. inicial)
q = pesos refinados
(2ª vuelta)
Frecuencia de aparición de q en la colección (ni)
Documentos relevantes para el usuario con presencia del término de consulta (Vi)
Id
Término
Peso Binario
Peso Binario
T1
Clima
1
0
0
0
-
-
T2
Biblioteca
0
1
1,54
2,255
149
5
T3
Universidad
1
0
1,337
2,035
232
5
T4
Alcalá
1
0
1,954
2,995
55
6
T5
España
1
1
0
0
-
-
T6
Libros
0
1
0,508
1,462
1241
6
T7
Geografía
0
0
0
0
-
-
T8
Población
1
0
0
0
-
-
T9
Electricidad
0
0
0
0
-
-
T10
Ciencia
0
0
0
0
-
-
T11
Social
0
1
0
0
-
-
T12
Luz
1
0
0
0
-
-
T13
Unamuno
1
1
2,219
2,917
34
5
T14
Física
0
0
0
0
-
-
T15
Fluidos
1
0
0
0
-
-
T16
Literatura
1
1
0,378
0,746
1543
3
Cálculo de valores sucesivos de aproximación


Cálculo de similaridad (Segunda vuelta)

Sim(doc1,q) = Universidad(1*2,035) + Alcalá(1*2,995) + Unamuno(1*2,917) + Literatura(1*0,746) = 8,693

Sim(doc2,q) = Biblioteca(1*2,255) + Libros(1*1,462) + Unamuno(1*2,917) + Literatura(1*0,746) = 7,38

Tabla2. Ejemplo de retroalimentación por relevancia


Ventajas e inconvenientes del modelo Probabilístico

Ventajas
  • Retroalimentación por relevancia, acepta feedback.
  • Asume la independencia de los términos de la consulta.
  • Asigna pesos a los términos, permitiendo recuperar los documentos que probablemente sean relevantes.
  • Es considerado uno de los mejores modelos dados sus buenos resultados con colecciones reales y corpus de entrenamiento. 
  • Su método de recuperación es mediante equiparación parcial, superando al método de equiparación exacta del modelo booleano.
Inconvenientes
  • Mantiene el modelo binario de recuperación de información, no teniendo en cuenta todos los términos del documento como ocurriría en el modelo vectorial.
  • Asigna pesos a los términos, permitiendo recuperar los documentos que probablemente sean irrelevante.
  • Requiere alta capacidad de computación, resultando complejo de implementar. 
  • Necesita efectuar una hipótesis inicial que no siempre resulta acertada.
  • No tiene en cuenta la frecuencia de aparición de cada término en el documento, tal como lo haría un modelo vectorial.

Bibliografía

CROFT, W. B.; HARPER, D. J. 1979. Using probabilistic models of document retrieval without relevance information. Journal of Documentation. 35(4): pp.285-295

GROSSMANY, D.A.; FRIEDER, O. 2004. Information Retrieval, Algorithms and Heuristic. Springer.

MARTÍNEZ COMECHE, J.A. 2006. Los modelos clásicos de recuperación de información y su vigencia. En: Tercer Seminario Hispano-Mexicano de investigación en Bibliotecología y Documentación, UNAM, Centro Universitario de Investigaciones Bibliotecológicas. pp.187-206. Disponible en: http://eprints.rclis.org/bitstream/10760/9662/1/Modelos_RI_vers_def.pdf

ROBERTSON, S.E. 1977. The probability ranking principle in IR. Journal of Documentation,  33(4): pp.294-304

SPARCK JONES, K. 1979. Search term relevance weighting given little relevante information. Journal of Documentation. 35(1): pp. 30-48

VILARES, J. 2008. El Modelo Probabilístico: Características y Modelos derivados. Disponible en:  http://www.grupolys.org/docencia/ln/2008-09/tutorial_modelo_probabilistico_apuntes.pdf/tutorial_modelo_probabilistico_apuntes.pdf