Modelos alternativos en IR Curso doctorado Búsqueda y Recuperación de Información en la Web Félix Muñoz Jiménez [email protected] Resumen: En este trabajo se hace un breve repaso a los principales modelos alternativos de búsqueda de información, entrando más en detalle en el modelo de Indexación Semántica Latente (ISL). keywords: Modelos Alternativos, Indexación Semántica Latente (ISL), Latent Semantic Indexing (LSI). 1.Introducción: ..........................................................................................................1 2.Modelos Alternativos: ........................................................................................... 2 3. Modelo de Indexación Semántica Latente: .......................................................... 7 Figura 1..............................................................................................................................8 4. Referencias: ........................................................................................................ 14 5. Bibliografía: ........................................................................................................14

1.Introducción: La búsqueda de información en documentos se ha entendido tradicionalmente como un proceso automático, en el que, dada una consulta (expresando las necesidades de información del usuario) y una colección de documentos, se devuelve una lista ordenada de documentos supuestamente relevantes para la consulta. Un motor de búsqueda ideal recuperaría todos los documentos relevantes (recall) y sólo aquellos documentos que son relevantes (precisión). Para lograr esto se han ideado diferentes modelos basados en distintos paradigmas. Los primeros modelos, Modelo Booleano, Modelo Vectorial y Modelo Probabilístico, son los denominados clásicos. A partir de estos surgen los modelos alternativos, en general suelen ser extensiones a los modelos clásicos. En muchos de ellos se emplean nuevos paradigmas como son las Redes de Inferencia, redes de Creencia, las Redes Neuronales... etc... Todos intentan mejorar el proceso de búsqueda. En este trabajo haremos un breve repaso de los modelos alternativos más importantes y entraremos más en detalle en el Modelo de Indexación Semántica Latente ISL.

-1-

2.Modelos Alternativos: Los modelos alternativos se agrupan en tres categorías: -

Basados en teoría de conjuntos Modelos algebraicos Modelos probabilísticos extendidos

2.1.Basados en teoría de Conjuntos: 2.1.1 Conjuntos Difusos o Borrosos. Definición de conjunto difuso: Un conjunto difuso A de un dominio de discurso U es caracterizado por una función de pertenencia μA : U -> [0,1] que asocia cada elemento u de U un número μA A(u) en el intervalo [0,1]. Se basa en que la representación de un documento por un conjunto de términos no sea categórica. Se difumina la pertenencia para que no sea binaria. Recuperación de Información Difusa: Palabras claves en una consulta son consideradas como un conjunto difuso tal que se define una función de asociación de documentos a estos conjuntos difusos. Para ello, el uso de tesauros permite extender el grupo de palabras claves por aquellas semánticamente relacionadas. Un tesauro también puede ser usado como modelo de recuperación de información. Un tesauro puede ser construido, al definir una correlación término-término, con una matriz de correlación llamada matriz de conexión de palabras claves. Una matriz de correlación entre palabras ki y kl en un tesauro es calculada por:

donde ni es el número de documentos que contienen ki nl es el número de documentos que contienen kl ni,l es el número de documentos que contienen ki y kl. La correlación entre palabras en un tesauro determina el grado de pertenencia de un documento dj a al conjunto difuso de un término ki:

Esto se puede interpretar como que el documento dj pertenece al conjunto difuso de ki, si tiene palabras relacionadas a ki. Consultas son procesadas de la misma forma que el modelo Booleano, es decir, por una forma normal disyuntiva.

-2-

2.1.2 Modelo Booleano extendido. Los documentos se representan en un espacio con ejes definiendo el peso asociado a cada palabra índice de una consulta. La distancia entre el punto que representa un documento y el punto óptimo (dado por la forma disyuntiva o conjuntiva) define el grado de similitud entre la consulta y el documento. La formulación general:

donde p indica el tipo de distancia. La similitud entre consulta y documento esta dada por:

donde w es el peso de una palabra en el documento (tal como es definido en el modelo vectorial). Estas similitudes dadas para las formas conjuntivas o disyuntivas se pueden combinar para consultas más generales.

2.2.Modelos algebraicos: 2.2.1 Modelo Vector Generalizado. La independencia de las palabras clave en un modelo vectorial implica que el conjunto {k , k ,..., k } de vectores es linealmente independiente. Frecuentemente esta linealidad es interpretada como que los vectores son ortogonales. En el modelo vector generalizado, los pesos (weights) son considerados independientes pero no ortogonales. Sea el conjunto de palabras índices { k1, k2, ... kt } y los pesos wi,j asociados a las palabras índices y documentos [ki, dj]. Si los pesos son binarios, toda posible concurrencia de palabras índices pueden ser representada por el conjunto de 2t “minterms” dados por m1 = (0,0,...0), m2 = (1,0,...0) y mt = (1,1,...1). Considere la función gi(mj) que retorna el peso {0,1} de la palabra índice ki en el minterm mj. El 1

2

t

-3-

minterm m1 que contiene sólo 0 significa que el documento no tiene ninguna de las palabras índices y el minterm mt significa que el documento contiene todas las palabras índices. La idea del modelo generalizado es tomar el grupo de vectores mi que son ortogonales y adoptarlo como el conjunto de vectores bases para los subespacios de interés. Ortogonalidad no significa que las palabras índices son independientes. Por el contrario, las palabras índices son ahora correlacionadas por los vectores mi .

2.2.2 Modelo de Redes Neuronales. Recuperación de información es modelada como una red neuronal que contiene tres elementos: nodos representando las palabras en una consulta, nodos representando palabras en los documentos, y nodos representando los documentos. Los nodos de la consulta envían señales a los nodos de palabras en los documentos, quienes activan los nodos de los documentos. Este proceso puede continuar entre los nodos de palabras en documentos y nodos de documentos. Inicialmente, la activación de los nodos de la consulta es 1. Estos nodos envían señales a los nodos de palabras en documentos con un valor de:

Si las señales recibidas por los nodos de palabras en documentos activan el nodo, la señal de salida esta dada por:

Las señales recibidas por los documentos son sumadas y después de la primera vuelta, el nivel de activación del nodo documento j es:

Este proceso puede continuar en base a un umbral que se define para permitir la activación.

-4-

2.2.3 Indexación Semántica Latente. Se parte de la concepción de que un documento es recuperado si comparte conceptos con otro documento que es relevante a una consulta. La idea es traspasar un documento y una consulta a un espacio de dimensión menor que esta asociado con conceptos, se basa en la conjetura de que la recuperación de información en este nuevo espacio es superior que la recuperación de información en el espacio de palabras índices. Esta explicado con más detalle en el apartado 3 de este documento.

2.3. Modelos Probabilísticos Extendidos: 2.3.1 Redes de Inferencia. Las redes de inferencia consideran la probabilidad como un grafo de creencia en la recuperación de información. Este modelo asocia variables aleatorias con palabras claves, documentos, y consultas. Una variable aleatoria asociada a un documento j representa el evento de observar ese documento. La observación del documento genera una creencia sobre la variable aleatoria de las palabras índices asociadas al documento. La variable aleatoria de la consulta representa que la información requerida por la consulta ha sido satisfecha.

Todas las variables aleatorias son binarias. Sea {k1,k2,...,kt} con ki siendo las variables aleatorias con valores 0 o 1. Estas variables definen los 2t posibles estados de . Además, dj y q son también variables binarias aleatorias asociadas con el documento y consulta. Que un documento sea relevante es determinado por la cantidad de apoyo evidencial que la observación dj da a la consulta q. Esto esta dado en redes de inferencia por P(q^ dj). k =

k

-5-

2.3.2 Modelo de Red de Creencia. La red de creencia, a diferencia de las redes de inferencia, considera un espacio de probabilidad claramente definido. Como resultado, separa los documentos de las consultas. El conjunto de todos las palabras índices K = {k1,k2,...,kt} forma el universo de discurso que define el espacio de probabilidad de la red de creencia. Sea u ⊂ K, a cada k ∈ u subconjunto u esta asociado un vector k tal que g (k ) =1 ⇔ . Cada palabra clave es vista como un elemento concepto y K como un espacio de conceptos. Un concepto u en K representa ya sea un documento o una consulta. Sea c un concepto genérico en el espacio K que representa un documento o una consulta, entonces: i

i

Tanto los documentos como las consultas son modelados como nodos de una red a los cuales se le asocia una variable aleatoria. La topología de la red es diferente del modelo de red de Inferencia. La probabilidad P(q) o P(dj) representan el grado de cobertura de una consulta o documento en el espacio K (es posible que la consulta q cubra todos los conceptos posibles en K).

La evaluación de un documento basado en una consulta es interpretado como una relación de correspondencia de un concepto, es decir, el grado de cobertura dado al documento dj por la consulta q.

-6-

3. Modelo de Indexación Semántica Latente: La "Indexación Semántica Latente" (LSI) fue descrita originalmente en un paper por Deerwester, Dumais, Furnas, Landauer, y Harshman [DEER90]. Y es un tema de estudio activo. En los modelos clásicos de búsqueda básicamente se trata de medir la relevancia de un documento en base al número de concurrencia de las palabras contenidas en dicho documento con las palabras de la consulta. Una deficiencia de esta forma de medir la relevancia es que no se tiene en cuenta el contexto semántico de la palabra, y como consecuencia de esto van a aparecer dos problemas fundamentales en la búsqueda de información con estos métodos, la sinonimia (términos distintos con el mismo significado) y la polisemia (términos iguales con distintos significados). En los modelos clásicos no se van a tomar como relevantes documentos que contengan términos con el mismo significado que una de las palabras de la consulta este hecho perjudicará el denominado factor de “recall”, pero sin embargo se devolverán como relevantes documentos que contengan términos iguales a la consulta aunque tengan distinto significado, este hecho hará que se reduzca la “precisión”. La indexación semántica latente, propone un método para solucionar estos problemas. La idea es pasar de un conjunto de términos a un conjunto de entidades donde podamos sacar la estructura latente en la asociación entre términos y documentos. Para analizar esa estructura semántica latente se eligió un método de análisis (two-mode factor analysis) basado en la Descomposición en Valores Singulares (SVD).

Descomposición en Valores Singulares Para el análisis de la estructura semántica latente empezamos con una matriz rectangular de términos por documentos. Valga de muestra el ejemplo que dan los autores del modelo en su artículo original. Se trata de una colección de 9 documentos que contienen cada uno el título de un memorándum (figura 1). Hay dos clases de documentos 5 sobre interacción hombre-computadora y 4 sobre gráficos.

-7-

Figura 1 Llamemos X a la matriz formada por términos y documentos, donde cada celda de la matriz indica el número de veces que un término aparece en un documento (figura 2).

Figura 2: Matriz X

-8-

Esta matriz rectangular se descompone en el producto de tres matrices por el proceso llamado de “descomposición en valores singulares”. X = T0S0D’0 Donde T0 es una matriz ortogonal, S 0 es una matriz diagonal y D’0 es la traspuesta de la matriz ortogonal D0. Las columnas de T0 son los autovectores de XTX y las columnas de D0 son los autovectores de XXT y S0 la matriz de valores singulares. T0 representaría el espacio vectorial de los términos y D0 el espacio vectorial de los documentos.

Figura 3: Descomposición en valores singulares de la matriz X de términos-documentos.

Figura 4: Matrices T0 , D0 y S0 obtenidas en el ejemplo.

-9-

Se ordenan los valores singulares de en S0 de mayor a menor, se escogen los primeros k valores y el resto se descartan, se tiene entonces una nueva matriz singular S de rango k. Borramos las columnas correspondientes de T0 y D0 y tenemos T y D respectivamente. El resultado es una nueva matriz X de rango menor. Es decir hemos reducido el modelo a k dimensiones. Cada término y documento va a ser representado ahora por un vector de factores en un espacio de k dimensiones. El valor de k, es decir cuánto reducimos las dimensiones del modelo, es algo que se elige experimentalmente midiendo para cada k elegido la eficacia de recuperación. X ≈ Xhihat = TSD’ Se aproxima la matriz X a un modelo reducido.

Figura 5: Obtenemos la nueva matriz X a partir de la reducción de los valores singulares de la matriz S.

Figura 6 : Reducción a k = 2 en el ejemplo de los 9 documentos. Se elige dimensión 2 para que la interpretación geométrica pueda representarse.

- 10 -

Figura 7 : Matriz X reducida en el ejemplo de los 9 documentos.

Comparaciones fundamentales en el modelo: Para las comparaciones se utiliza la matriz reducida Xhihat. - Comparación de dos términos: El producto escalar entre dos filas de la matriz Xhihat nos dará la similitud entre dos términos a través de todos los documentos (Recordamos que el producto escalar nos daba la medida del coseno del ángulo). Si hacemos el producto de matriz Xhihat por su traspuesta obtenderemos la matriz de los productos escalares término a término. Se puede demostrar que este producto es:

Xhihat Xhihat’ = TS2T’ -

Comparación de dos documentos: El producto escalar entre dos columnas de la matriz Xhihat nos dará la similitud entre dos documentos a través de sus términos. Si hacemos el producto de la transpuesta de la matriz Xhihat por ella misma obtenderemos la matriz de los productos escalares documento a documento. Se puede demostrar que este producto es:

Xhihat´ Xhihat = DS2D’ -

Comparación de un término con un documento: El principal elemento de medida para la comparación entre un término y un documento es el valor de la celda de la matriz Xhihat cada celda de esta matriz relaciona un documento con un término.

-

Comparación de la consulta (query) con un documento: Para ello se utiliza un pseudo-documento Dq que va a representar a la consulta. Este Dq se calcula de la siguiente manera:

Dq = Xq TS-1 Donde Xq es el vector de términos de la consulta. Este Dq es como si fuera un fila de la matriz D y puede ser usado para comparar con otros documentos con el producto escalar.

- 11 -

Interpretación geométrica: Las filas de las matrices reducidas de vectores singulares se toman como coordenadas de los puntos que representan a los documentos y términos en un espacio de dimensión k cuyos ejes están reescalados por cantidades relacionadas con los valores de la diagonal de la matriz S. Los productos escalares (coseno del ángulo) entre los puntos nos darán las relaciones de similitud entre los distintos puntos. Para la consulta, al ser esta un pseudo-documento estará representada como un nuevo punto del espacio. En la siguiente figura (figura 8) se muestra una interpretación geométrica del ejemplo dado anteriormente.

Figura 8: Una representación bidimensional de los 12 términos y los 9 documentos del ejemplo puesto. Los términos están representados por los círculos negros, los documentos por los cuadrados blancos entre paréntesis los términos que contienen. La consulta se representa con un pseudo-documento q . Las escalas de los ejes son comparaciones de documento-documento o término-término. El cono de líneas punteadas es la región que corresponde a un coseno de 0,9 con la consulta q. Como se puede observar todos los documentos sobre human-computer están cerca de la consulta (es decir, dentro del cono) incluidos los documentos c3 y c5 que curiosamente no tienen ningún término de la consulta q.

- 12 -

El modelo ISL sigue en la actualidad siendo tema de estudio, la "Indexación Semántica" es un nombre para una familia de tecnologías para buscar y organizar colecciones de datos. El fin es encontrar patrones en datos no estructurados (documentos sin descripciones tales como palabras claves o tags especiales) y usar esos patrones para ofrecer una búsqueda más efectiva y servicios de categorización. Por ejemplo, se han tenido buenos resultados preliminares en la predicción de estructuras de proteínas, mediante el uso de algoritmos adaptados de un motor de búsqueda de textos [CUAD03]. Otro uso actual se encuentra en el campo de la pedagogía, donde sirve de medida de coherencia de textos, sirviendo por tanto para mejorar la redacción y comprensión [FOLT98]. También se investiga su uso para filtrado de información, concretamente contra el “spam” mensajes de electrónicos no deseados. Se están probando algoritmos basados en indexación semántica para reconocer mensajes “spam” [FOLT90].

- 13 -

4. Referencias: - [CUAD03] Cuadrado J., Ceglowski M. (2003).Using Latent Semantic Analysis in Bioinformatics. O'Reilly Biotechnology Conference. February 2003. - [DEER90] Deerwester, S., Dumais, S. T., Furnas, G. W., Landauer, T. K., & Harshman, R. (1990). Indexing by latent semantic analysis. Journal of the American Society for Information Science, 41(6), 391-407. - [FOLT90] Foltz, P. W. (1990) Using Latent Semantic Indexing for Information Filtering. In R. B. Allen (Ed.) Proceedings of the Conference on Office Information Systems, Cambridge, MA, 40-47. - [FOLT98] Foltz, P. W., Kintsch, W. & Landauer, T. K. (1998).The Measurement of Textual Coherence with Latent Semantic Analysis. Discourse Processes, 25, 285-307.

5. Bibliografía: - Deerwester, S., Dumais, S. T., Furnas, G. W., Landauer, T. K., & Harshman, R. (1990). Indexing by latent semantic analysis. Journal of the American Society for Information Science, 41(6), 391-407. - R. Baeza-Yates and B. Ribeiro-Neto. Modeling (chapter 2). In R. Baeza-Yates and B. Ribeiro-Neto, editors, Modern Information Retrieval. AWL England, 1999. - TURTLE, H.R. y CROFT, W.B. (1992): “A Comparison of Text Retrieval Models.” The Computer Journal , 35, 3, pp. 279-290. - http://research.nitle.org/lsi - http://www.cs.utk.edu/~lsi/

- 14 -