Modelo de Recuperación de Información Indexación Semántica Latente

Modelo de Recuperación de Información Indexación Semántica Latente Jose Luis Dumas Leon1,1 , Jesus Perez Martin1,2, 1

Facultad de Matematica y Computacion, Universidad de La Habana {j.dumas, j.martin}@lab.matcom.uh.cu

Resumen. El Modelo de Recuperación de Información Indexación Semántica Latente (LSI por sus siglas en inglés) es un modelo alternativo que maneja la búsqueda de información mediante la indexación de términos, ubicándolos en un contexto semántico común, en este trabajo se verá cómo se realiza este proceso y sus principales ventajas y desventajas con respecto a algunos de los MRI más conocidos. Palabras Claves: Modelo de Recuperación de Información (MRI), semántica, latente, sinonimia, polisemia, SVD, matriz término-documento.

1. Introducción Normalmente, la información se recupera, haciendo coincidir literalmente términos en los documentos con los de una consulta. Sin embargo, estos métodos pueden ser inexactos para determinadas consultas de los usuarios. Puesto que generalmente existen muchas maneras de expresar un concepto dado (sinonimia), los términos literales en la consulta del usuario no pueden coincidir con los de un documento pertinente. Además, la mayoría de las palabras tienen múltiples significados (polisemia), por lo que un macheo literal de los términos de la consulta puede implicar una recuperación de documentos que semánticamente son irrelevantes. Un mejor enfoque sería permitir a los usuarios recuperar información sobre la base de un tema conceptual o el significado de un documento. LSI intenta superar los problemas de la coincidencia lexicográfica utilizando índices conceptuales derivados estadísticamente en lugar de palabras individuales para la recuperación. LSI asume que hay alguna estructura subyacente o latente en el uso de la palabra que está parcialmente oculta por la variabilidad en la selección de palabras. Para estimar la estructura en el uso de las palabras dentro de los documentos se utiliza una descomposición de valores singulares (SVD) truncada. Luego la recuperación se realiza utilizando la base de datos de valores singulares y vectores obtenidos a partir de la SVD truncada. Datos de rendimiento muestran que estos vectores derivados estadísticamente son mejores indicadores del significado de términos individuales.

2. Fundamento del método LSI LSI es una técnica que proyecta consultas y documentos en un espacio con dimensiones semánticas “latentes”. En el espacio semántico latente, una consulta y un documento pueden tener una alta similitud de acuerdo al coseno incluso si no comparten ningún término, siempre y cuando sus términos sean semánticamente similares en un sentido que se describirá posteriormente. Podemos ver a LSI como una métrica de similitud que es una alternativa para expresar las medidas de solapamiento de palabras como tf*idf. El espacio semántico latente en el que proyectamos tiene menos dimensiones que el espacio original (el cual tiene tantas dimensiones como términos). LSI es, de ese modo, un método de reducción de dimensionalidad. Estas técnicas toman un conjunto de objetos que existen en un espacio de grandes-dimensiones y los representan en un espacio de pocas-dimensiones, frecuentemente en uno 2-dimensional o 3-dimensional con el propósito de visualizarlos. LSI es la aplicación de una técnica matemática particular, llamada Descomposición en Valores Singulares (SVD por sus siglas en inglés), a una matriz de términodocumento. SVD (y por lo tanto LSI) es un método de mínimos cuadrados. La proyección en el espacio semántico latente se elige de forma que las representaciones en el espacio original son reducidas tanto como sea posible cuando se mide por la suma de los cuadrados de las diferencias. SVD toma una matriz 𝐴 y la representa como  en un espacio dimensional más pequeño, tal que la “distancia” entre las dos matrices, medida por la norma cuadrática sea mínima: Δ =∥ 𝐴 − 𝐴̂ ∥2

(1)

La noma-2 para matrices es equivalente a la distancia Euclidiana para vectores. SVD proyecta un espacio 𝑛-dimensional en uno 𝑘-dimensional donde 𝑛 ≫ 𝑘. En nuestra aplicación, serán matrices término-documento, 𝑛 es el número de tipos de términos en la colección. Los valores de 𝑘 que se eligen con frecuencia son 100 y 150. La proyección transforma el vector de un documento del espacio 𝑛-dimensional de términos en un vector reducido al espacio 𝑘-dimensional. Hay varias maneras de reducir un espacio de grandes dimensiones. LSI elige una reducción óptima en el sentido que minimiza la distancia Δ. Esta configuración tiene la consecuencia de que las dimensiones del espacio reducido corresponden a los ejes de mayor variación1.

1

Esto está estrechamente relacionado con el Análisis de Componentes Principales (PCA), otra técnica para la reducción de dimensionalidad. Una diferencia entre las dos técnicas es que PCA sólo puede ser aplicado a una matriz cuadrada mientras que LSI se puede aplicar a cualquier matriz.

2.1. Matriz Término-Documento

Inicialmente se construye una matriz llamada matriz Término-Documento, 𝐴, para identificar las ocurrencias de los 𝑡 términos indexados en una colección de 𝑑 documentos. En la matriz 𝐴, cada fila representa un término y cada columna un documento, por lo tanto, cada elemento 𝐴𝑖𝑗 , 1 ≤ 𝑖 ≤ 𝑡, 1 ≤ 𝑗 ≤ 𝑑, es el peso del término 𝑖 en el documento 𝑗. Estos pesos pueden ser calculados como el producto del peso local del término 𝑖 en el documento 𝑗, 𝑙𝑖𝑗 , y el peso global del término 𝑖 en la colección de documentos, 𝑔𝑖 . Cada uno de los pesos anteriores puede ser calculado de diversas formas, en las tablas 1 y 2 se presentan los métodos más utilizados. Tabla 1. Funciones de peso local más usadas. Nombre Binaria Frecuencia de términos Log Augnorm

Fórmula 𝑙𝑖𝑗 = 1 si el término existe en el documento, 0 en otro caso. 𝑙𝑖𝑗 = 𝑡𝑓𝑖𝑗 número de ocurrencias del término 𝑖 en el documento 𝑗. 𝑙𝑖𝑗 = log(𝑡𝑓𝑖𝑗 + 1) 𝑡𝑓𝑖𝑗 ( )+1 𝑚𝑎𝑥𝑖 (𝑡𝑓𝑖𝑗 ) 𝑙𝑖𝑗 = 2

Tabla 2. Funciones de peso global más usadas. Nombre Binaria Normal

Gfldf Idf Entropía

Fórmula 𝑔𝑖 = 1 𝑔𝑖 = 𝑔𝑖 =

1

√∑𝑗 𝑡𝑓𝑖𝑗 2 𝑔𝑓𝑖 𝑑𝑓𝑖

, donde el 𝑔𝑓𝑖 es el número de veces que ocurre el termino 𝑖 en toda la

colección y el 𝑑𝑓𝑖 es el número de documentos en los cuales ocurre el termino 𝑖 𝑛 𝑔𝑖 = log 2 1 + 𝑑𝑓𝑖 𝑝 log 𝑝𝑖𝑗 𝑡𝑓 𝑔𝑖 = 1 + ∑𝑗 𝑖𝑗 donde 𝑝𝑖𝑗 = 𝑖𝑗 log 𝑛

𝑔𝑓𝑖

2.2. SVD La proyección SVD es computada por la descomposición de la matriz términodocumento 𝐴𝑡𝑥𝑑 en el producto de tres matrices 𝑇𝑡𝑥𝑛 , 𝑆𝑛𝑥𝑛 , 𝐷𝑑𝑥𝑛 : 𝐴𝑡𝑥𝑑 = 𝑇𝑡𝑥𝑛 𝑆𝑛𝑥𝑛 (𝐷𝑑𝑥𝑛 )𝑇

(2)

donde 𝑡 es el número de términos, 𝑑 es el número de documentos, 𝑛 = 𝑚𝑖𝑛(𝑡, 𝑑), 𝑇 y 𝐷 tienen columnas ortonormales, por tanto 𝑇𝑇 𝑇 = 𝐷 𝑇 𝐷 = 𝐼, 𝑟𝑎𝑛𝑔(𝐴) = 𝑟, 𝑆 = 𝑑𝑖𝑎𝑔(𝜎1 , 𝜎2 , … , 𝜎𝑛 ), 𝜎𝑖 > 0 ∀ 1 ≤ 𝑖 ≤ 𝑟, 𝜎𝑗 = 0 ∀ 𝑗 ≥ 𝑟 + 1.

2.3. Ejemplo del cálculo de SVD: Computemos SVD para la siguiente matriz: 0 0 𝐴 = [0 9] 3 0 Paso 1. Computar su transpuesta 𝐴𝑇 y el producto 𝐴𝑇 𝐴. 0 0 3 𝐴𝑇 = [ ] 0 9 0 0 0 0 0 3 9 0 𝐴𝑇 𝐴 = [ ] [0 9] = [ ] 0 9 0 0 81 3 0 Paso 2. Determinar los autovalores de 𝐴𝑇 𝐴 y ordenarlos descendentemente según su valor absoluto. Calcular sus raíces cuadradas para obtener los valores singulares de 𝐴. 9−𝜆 0 𝐴𝑇 𝐴 − 𝜆𝐼 = [ ] 0 81 − 𝜆 𝑇 |𝐴 𝐴 − 𝜆𝐼| = (9 − 𝜆)(81 − 𝜆) = 0 𝜆2 − 90𝜆 + 729 = 0 𝜆1 = 81 𝑦 𝜆2 = 9 𝜎1 = √𝜆1 = √81 = 9 𝑦 𝜎2 = √𝜆2 = √9 = 3 Paso 3. Construir matriz diagonal 𝑆 ubicando los valores singulares en orden descendente a lo largo de la diagonal. 9 0 𝑆=[ ] 0 3 𝑇 Paso 4. Usando los autovalores de 𝐴 𝐴 (Paso 2) calcular los autovectores de 𝐴𝑇 𝐴. Ubicarlos a lo largo de las columnas de 𝐷 y obtener su transpuesta 𝐷𝑇 . 0 1 𝐷 = 𝐷𝑇 = [ ] 1 0 Paso 5. Obtener la matriz 𝑇, donde los vectores 𝑡𝑖 deberán cumplir 𝐴𝑑𝑖 = 𝜎𝑖 𝑡𝑖 𝐴𝑑1 1 𝑡1 = = [0 9 0]𝑇 = [0 1 0]𝑇 𝜎1 9 𝐴𝑑2 1 𝑡2 = = [0 0 3]𝑇 = [0 0 1]𝑇 𝜎2 3 Entonces completamos con una base ortonormal de ℜ3 𝑡3 = [1 0 0]𝑇 0 0 1 𝑇 = [1 0 0] 0 1 0

2.4. Implicaciones de SVD para LSI Podemos ver SVD como un método para la rotación de los ejes del espacio ndimensional tal que el primer eje se ejecuta a lo largo de la dirección de la mayor variación entre los documentos, la segunda dimensión se ejecuta a lo largo de la dirección con la segunda mayor variación y así sucesivamente.

- 𝑇 representa los términos en este nuevo espacio. - 𝐷 representa los documentos en este nuevo espacio. - 𝑆 es una matriz diagonal que contiene los valores singulares de 𝐴 en orden descendente. El 𝑖 − é𝑠𝑖𝑚𝑜 valor singular indica la variación a lo largo de la 𝑖 − é𝑠𝑖𝑚𝑎 dimensión. Restringiendo las matrices 𝑇, 𝑆 y 𝐷 a sus primeras 𝑘 < 𝑛 filas se obtiene las matrices 𝑇𝑡𝑥𝑘 , 𝑆𝑘𝑥𝑘 , (𝐷𝑑𝑥𝑘 )𝑇 y su producto  𝐴̂𝑡𝑥𝑘 = 𝑇𝑡𝑥𝑘 𝑆𝑘𝑥𝑘 (𝐷𝑑𝑥𝑘 )𝑇

(3)

Se puede considerar que dichas matrices ya no contienen ruido que interfiere en nuestra recuperación de información y se utilizarán para poder hacer los cálculos necesarios para obtener la similitud de los documentos con la consulta. Es posible calcular la similitud entre dos documentos, entre dos términos, entre un término y un documento, y entre una consulta y un documento mediante la manipulación de las matrices ya “limpias”. En este caso nos interesa conocer el proceso para calcular la similitud de una consulta y un documento.

Fig. 1. Representación esquemática de lo que significa la reducción de dimensiones llevada a cabo por medio de SVD. En la figura de la izquierda, cada término está representado por cuatro dimensiones, tantas como documentos en la colección. En la de la derecha, los términos pasan a estar representados por dos dimensiones abstractas pero de una mayor utilidad funcional. A cada término se le infiere una probabilidad de estar representado en un concepto. Compruébese por ejemplo que al término t2 se le infiere cierta relación semántica con el documento d2 aunque como se muestra en la figura de la izquierda, t2 no aparece en d2.

En resumen:  Con los k valores más grandes, mostramos una aproximación por minimos cuadrados a la matriz original usando el menor conjunto de números (sacando aquellos con menor impacto).  Matriz reducida: - Compresión de la original. - “Sacar detalle” actúa como un “reductor de ruido” o “reductor de pormenores poco válidos”. - Puede mejorar el rendimiento (dependiendo del contexto)



SVD hace a LSI posible.

2.5. Consultas Con el propósito de la recuperación de información, la consulta de un usuario debe ser ubicada en el espacio k-dimensional como los documentos. Como la consulta (al igual que un documento) es un conjunto de palabras, su representación en dicho espacio puede ser determinada, por ejemplo, mediante el cálculo del vector: 𝑞̂ = 𝑞 𝑇 𝑇𝑡𝑥𝑘 𝑆 −1 𝑘𝑥𝑘

(4)

donde 𝑞 es simplemente el vector de las palabras de la consulta, multiplicado por los pesos de términos apropiados. La suma de esos vectores de términos k-dimensionales se refleja por 𝑞 𝑇 𝑇𝑡𝑥𝑘 en la ecuación anterior, y la multiplicación por 𝑆 −1 𝑘𝑥𝑘 diferencia los pesos de las dimensiones por separado. Por lo tanto, el vector de la consulta se obtiene de la suma ponderada de los vectores de los términos que la constituyen. El vector de la consulta puede ser comparado entonces con todos los documentos existentes y establecer un ranking por su similaridad (cercanía) a la consulta. Un medidor común de similaridad es el coseno entre el vector de la consulta (𝑞̂) y el del documento (columna correspondiente en (𝐷𝑑𝑥𝑘 )𝑇 ). Típicamente, los 𝑧 documentos más cercanos o todos los que excedan un umbral para el coseno serán devueltos al usuario.

2.6. Actualización Un problema para una aplicación práctica es cómo agregar consultas y nuevos documentos en el espacio reducido. La SVD únicamente nos brinda representaciones reducidas para los vectores de los documentos en la matriz 𝐴. No queremos hacer una nueva SVD cada vez que se hace una consulta o se añaden nuevos documentos y términos a la colección. Hay dos alternativas para lograr esto: re-obteniendo SVD para una nueva matriz de término-documento o “adjuntando” los nuevos términos y documentos a la SVD ya calculada. Recalcular SVD para una gran matriz de término-documento requiere más tiempo computacional y, para grandes problemas, puede ser imposible debido a los requerimientos de memoria. Este proceso permite que los nuevos 𝑝 términos y 𝑞 documentos afecten directamente la estructura semántica latente existente mediante la creación de una nueva matriz de termino-documento 𝐴(𝑡+𝑝)𝑥(𝑑+𝑞) , seguido de la obtension de SVD para esta nueva matriz, y la generación de una nueva matriz Â. En contraste, “adjuntar” se basa en la estructura semántica latente existente, la actual Â, y por lo tanto nuevos términos y documentos no tienen efecto sobre la representación de los existentes. Adjuntar requiere menos tiempo y memoria pero puede tener malos efectos sobre la representación de los nuevos términos y documentos. Además, con el fin de manejar grandes corpus de manera eficiente podemos querer hacer SVD para una parte de los documentos solamente (por ejemplo, un tercio o un cuarto). Los demás documentos serían “adjuntados” en la descomposición existente.

“Adjuntar” documentos es esencialmente el proceso descrito en la sección anterior sobre la representación de las consultas. Cada nuevo documento se representa como una suma ponderada de los vectores de los términos que lo componen. Una vez que se calcula un nuevo vector de documento, este se añade al conjunto de los vectores de los documentos existentes (columnas de la matriz (𝐷𝑑𝑥𝑘 )𝑇 ). Similarmente, nuevos términos pueden representarse como una suma ponderada de los vectores de los documentos donde aparece. Una vez que se calcula un nuevo vector de término, este se añade al conjunto de los vectores de los términos existentes (filas de la matriz 𝑇𝑡𝑥𝑘 ) El cálculo de estos nuevos vectores puede realizarse mediante las formulas: 𝑑̂ = 𝑑 𝑇 𝑇𝑡𝑥𝑘 𝑆 −1 𝑘𝑥𝑘

(5)

𝑡̂ = 𝑡𝐷𝑑𝑥𝑘 𝑆 −1 𝑘𝑥𝑘

(6)

3. LSI en acción En esta sección, LSI y el proceso de adjuntar discutido en la Sección 2.6 son aplicados a una pequeña base de datos de títulos de libros. En la Tabla 3, se muestran 17 títulos publicados en diciembre de 1993 (volumen 54, número 4) de la SIAM Review. Todas las palabras subrayadas en la Taba 3 denotan palabras claves que son usadas como referentes para los títulos. Tabla 3. Base de datos de títulos de libros revisados en SIAM Review. Las palabras claves subrayadas aparecen en más de un título, estas representan a los conceptos. Etiqueta B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14 B15 B16 B17

Título A Course on Integral Equations Attractors for Semigroups and Evolution Equations Automatic Differentiation of Algorithms: Theory, Implementation, and Application Geometrical Aspects of Partial Differential Equations Ideals, Varieties, and Algorithms - An Introduction to Computational Algebraic Geometry and Commutative Algebra Introduction to Hamiltonian Dynamical Systems and the N-Body Problem Knapsack Problems: Algorithms and Computer Implementations Methods of Solving Singular Systems of Ordinary Differential Equations Nonlinear Systems Ordinary Differential Equations Oscillation Theory for Neutral Differential Equations with Delay Oscillation Theory of Delay Differential Equations Pseudodifferential Operators and Nonlinear Partial Differential Equations Sine Methods for Quadrature and Differential Equations Stability of Stochastic Differential Equations with Respect to Semi-Martingales The Boundary Integral Approach to Static and Dynamic Contact Problems The Double Mellin-Barnes Type Integrals and Their Applications to Convolution Theory

Fig 2. Matriz término-documento de 16x17 que corresponde a los títulos de la tabla 2

Fig 3. Ploteo 2-dimensional de los terminos y documentos

Fig 4. Vector de la consulta application theory

Fig 5. Documentos devueltos basándonos en distintos números de factores LSI (k)

4. Costo de SVD Dumais 1995: “SVD toma solamente 2 minutos en un Sparc10 para una matriz de 2.000 x 5.000, pero el tiempo crece a entre 18 y 20 horas para matrices de 60.000 x 80.000” Hong 2000: “El Algoritmo SVD es 𝑂(𝑁 2 𝑘 3 ), con 𝑁 número de palabras más documentos, y 𝑘 el número de dimensiones en el espacio conceptual”. “Sin embargo, si la colección es estable, SVD se calcula sólo una vez, lo que significa un costo aceptable” Leif: Si hoy tenemos computadoras 100 veces más rápidas que Dumais en 1995, conjuntos de datos 20 veces más grandes y funciones SVD optimizadas (en vez de prototipos de investigación), debería tomar alrededor de unas 20 horas

5. Ventajas y desventajas El modelo LSI como alternativa ante otros modelos tiene beneficios e inconvenientes que deberán tenerse en cuenta si se desea utilizar este modelo, para según lo que nos plantee la problemática en cuestión, decidir si los beneficios superan a los inconvenientes o viceversa. A la par que nos brinda solución a problemas con los que otros modelos no pueden lidiar, para lograrlo, se requiere gran capacidad de cómputo y de almacenamiento.

5.1. Ventajas Dimensiones verdaderas (latentes): La suposición en LSI (y análogamente a otras formas de reducción de dimensionalidad como principal componente de análisis) es que las nuevas dimensiones son una mejor representación de las consultas y los documentos. Esta representación verdadera fue opacada por un proceso de generación que expresaba una dimensión particular con un conjunto de palabras en algunos documentos y un conjunto de palabras diferentes en otro documento. El análisis LSI recupera la estructura semántica original del espacio y sus dimensiones originales. Sinonimia: La sinonimia se refiere al efecto de que un mismo concepto fundamental puede ser descrito usando diferentes términos. Las estrategias de recuperación tradicionales sufren encontrando documentos sobre un mismo tema que tienen distinto vocabulario. En LSI, el concepto en cuestión así como también todos los documentos que están relacionados con él probablemente van a ser representados por una misma combinación ponderada de variables indexadas. Polisemia: Describe a las palabras que tienen más de un significado, lo cual es una propiedad común del lenguaje. Un gran número de palabras polisémicas en la consulta puede reducir la precisión de una búsqueda significativamente. Usando una representación reducida en LSI, uno espera que remover el “ruido” de los datos, el cual puede ser descrito como el raro y poco uso de ciertos términos. (Note sin embargo que esto debe funcionar solo cuando el significado real está cercano al significado promedio. Puesto que para LSI los vectores de los términos son precisamente un promedio de los diferentes significados de los términos, cuando el significado real difiere del significado promedio, LSI puede verdaderamente reducir la calidad de la búsqueda). Dependencia entre términos: Un modelo vectorial tradicional asume independencia entre términos y estos actúan como bases ortogonales del espacio vectorial. Puesto que hay fuertes asociaciones entre los términos en el lenguaje, esta asunción nunca se satisface. Mientras la independencia entre términos representa la aproximación de primer orden más razonable, esta puede ser mejorada teniendo en cuenta asociaciones entre términos en el proceso de recuperación. Añadir frases comunes como objetos de búsqueda es una simple aplicación de este acercamiento. Por otra parte, los factores LSI son ortogonales por definición, y los términos son ubicados en el espacio reducido de forma que reflejen las correlaciones en su uso dentro de los documentos. Es muy difícil explotar las ventajas de la asociación de términos sin un incremento dramático de los requerimientos computacionales del problema de

recuperación. Mientras la solución LSI es muy difícil de computar para grandes colecciones, solo necesita construirse una única vez para toda la colección y el rendimiento en el momento de la recuperación no sufre. En resumen:  Hay coincidencia parcial.  Permite hacer ranking.  Al pasar al espacio de los conceptos se pueden recuperar documentos que traten sobre el mismo tema.  Recupera documentos aun cuando este no contenga los términos presentes en las consultas.  Permite resolver problemas de la lengua como la sinonimia y la polisemia.

5.2. Desventajas Almacenamiento: También se podría argumentar que la representación SVD es más compacta. Muchos documentos tienen más de 150 términos únicos. Así que la representación vectorial esparcida ocupará más espacio de almacenamiento que la representación compacta SVD si reducimos a 150 dimensiones. Además, los vectores LSI son números reales, mientras que las frecuencias originales de los términos son enteros, añadiendo costos de almacenamiento. Usando vectores LSI, no podemos tomar los beneficios del hecho de que cada término aparece en un número limitado de documentos, lo cual representa la naturaleza dispersa de la matriz de términodocumento. Con los reciente avances en los medios de almacenamiento electrónico, los requerimientos de almacenamiento de LSI no son un problema crítico, pero la pérdida de poca densidad, tiene otras implicaciones más graves. Eficiencia: Una de las mejoras más importantes en la búsqueda en el espacio vectorial proviene del uso de un índice invertido. Como consecuencia, sólo los documentos que tienen algunos términos en común con la consulta deben ser examinados durante la búsqueda. Con LSI, sin embargo, la consulta debe ser comparada con todos los documentos de la colección. Hay, sin embargo, varios factores que pueden reducir o eliminar este inconveniente. Si la consulta tiene más términos que su representación en el espacio vectorial LSI, entonces el producto interno de la similitud tomara más tiempo en computarse en el espacio del término. Por ejemplo, si la retroalimentación se llevó a cabo utilizando el texto completo de los documentos pertinentes, el número de términos en la consulta es probable que incremente en varias veces el número de vectores LSI, que conduce a un correspondiente aumento en el tiempo de búsqueda. En resumen:  Costo computacional.  No se expresa la posibilidad de no tener un término, es decir, no hay posibilidades de forzar condiciones booleanas.  Imposibilidad de aplicar el modelo a colecciones grandes (de decenas de millones de elementos). “Si está planeando usar LSI, úselo para aquello que realmente sirve…”

6. Comparación con otros MRI Tabla 4. Comparación entre los MRI Booleano, Vectorial, Booleano Extendido, Fuzzy, Vectorial Generalizado, Redes Neuronales y LSI. Criterio

Booleano

Vectorial

Probabilístico

Documentos

Vectores de peso binarios Expresiones booleanas Teoría de conjuntos y álgebra booleana

Vectores de peso no binarios Vectores de peso no binarios Espacio t dimensional y algebra lineal de vectores Valores reales dados por tf*idf

Vectores de peso binarios Vectores de peso binarios Teoría de probabilidades

𝑃(𝑑𝑗 ∈ 𝑅𝑒𝑙) 𝑃(𝑑𝑗 ∉ 𝑅𝑒𝑙) No

tf*idf (idf normalizado del vectorial) Existe función para el AND y para el OR No

Consultas Framework

Binarios

Booleano Extendido Vectores de peso no binarios Expresiones booleanas Algebra booleana y operaciones del algebra lineal

Pesos

Binarios

Similitud

𝑆(𝑑𝑗, 𝑞) ∈ {0,1}

Dependencia entre términos Ranking Macheo Parcial

No

Valores entre 0 y 1 dados por el coseno No

No No

Sí Sí

Sí Sí

Sí Sí

Basado en Redes Neuronales Vectores de peso no binarios Vectores de peso no binarios

LSI Vectores de peso no binarios Vectores de peso no binarios transformados al espacio k dimensional Espacio t dimensional y algebra lineal de vectores Valores dados por tf*idf transformados por SVD Valores entre 0 y 1 dados por el coseno del ángulo entre el documento y la consulta Sí Sí Sí

Criterio

Fuzzy

Documentos

Vectores de peso binarios Expresiones booleanas

Vectorial Generalizado Vectores de peso no binarios Vectores de peso no binarios

Framework

Algebra booleana y teoría de conjuntos difusos

Algebra lineal de vectores y algebra booleana

Pesos

Binarios

Reales

Similitud

Reales entre 0 y 1 dados por la función de membresía

Reales

Dependencia entre términos Ranking Macheo Parcial

Sí

Sí

Espacio t dimensional, algebra lineal, teoría de grafos Reales dados por los pesos del Vectorial normalizados Reales dados por el nivel de activación del nodo que representa al documento Sí

Sí Sí

Sí Sí

Sí Sí

Consultas

7. Conclusiones y discusión El modelo LSI es una extensión del modelo vectorial o espacios vectorial. Existen varias razones por las que muchos autores decidieron su extensión; sin embargo una de las principales es la falta de asociación de conceptos esto es, que los términos en el modelo vectorial se toman tal y como están descritos en los índices y no tomando en cuenta su significado ni su relación con el documento ya que un término puede ser descrito utilizando diferentes palabras. Dentro de este modelo existe un aspecto importante que es la reducción de ruido encontrada en un documento, es decir que existen varios documentos que pueden tener algún término de una consulta; no obstante, no son considerados como documentos relevantes debido a que su semántica no es semejante a lo que se busca, así la idea de este modelo es eliminarlos, ya que los documentos que se considera que tienen la misma semántica se localizan en una posición cercana en un espacio multidimensional. Este proceso se realiza mediante SVD. Investigaciones han comprobado que los resultados de este modelo son buenos, pero el cálculo de la SVD es computacionalmente costoso, aunque existen varios algoritmos que han logrado su optimización. En última instancia, para decidir si las ventajas superan a los inconvenientes, tenemos que analizar el rendimiento de la recuperación. Mientras algunos experimentos han obtenido resultados prometedores, no muestran de manera concluyente que la recuperación utilizando LSI es superior al modelo vectorial básico. Algunos autores han tratado esta cuestión en el contexto del problema de enrutamiento y proporcionan pruebas de que la LSI mejora ligeramente el rendimiento de la tarea de enrutamiento. En otras palabras, el ganador todavía ha de ser proclamado.

Bibliografía 1. 2. 3. 4.

“Indexing by Latent Semantic Analysis”, Deerwester S., Dumais S.T., Harshman R., 1997. “An Introduction to Latent Semantic Analysis”, Lander T.K., Foltz P.W., Laham, D., 1998. “Latent Semantic Indexing: An overview”, Rosario B., INFOSYS 240, Spring 2000. “Using linear algebra for intelligent information retrieval”, M.W. Berry, S.T. Dumais & G.W. O'Brien, December 1994. 5. Información de la web