Indexación Semántica Latente

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda


La indexación semántica latente (ISL) es un método de indexación y recuperación que utiliza un método numérico llamado descomposición en valores singulares (SVD por sus siglas en inglés) para identificar patrones en las relaciones entre los términos contenidos en una colección de textos no estructurados. La ISL se basa en el principio de que las palabras que se utilizan en el mismo contexto tienden a tener significados similares. La característica fundamental de la ISL es su habilidad para extraer el contenido conceptual de un documento, estableciendo asociaciones entre aquellos términos que ocurran en contextos similares. La ISL fue patentada en 1988 por Scott Deerwester, Susan Dumais, George Furnas, Richard Harshman, Thomas Landauer, Karen Lochbaum y Lynn Streeter.

La idea principal es emparejar por conceptos en lugar de por términos, o sea, un documento podría ser recuperado si comparte conceptos con otro que es relevante para la consulta dada. Esto se consigue mapeando los documentos (vector índice de términos) y los vectores consultas dentro de un espacio dimensional reducido el cual está asociado con conceptos, y puede que la recuperación de información en este espacio reducido sea superior a la obtenida en el espacio de términos indexados. Para esto se elige una forma de análisis denominada Descomposición en Valores Singulares (SVD).

Especificación del modelo de ISL[editar]

La ISL es una variación del Modelo Vectorial, en la que los documentos se representan a partir de vectores de pesos no binarios, al igual que las consultas, la función de similitud es el coseno del ángulo entre el vector del documento y el de la consulta y se trabaja como framework con el álgebra vectorial. A continuación se describirá el comportamiento del modelo.

Matriz Términos-Documentos[editar]

Para el análisis ISL primero se construye una matriz C donde las filas representan los términos y las columnas los documentos, esta matriz establece las relaciones término documento por lo que cada elemento x_{ij} representa el peso del término i en el documento j. Estos pesos pueden ser calculados como el producto del peso local del término l_{ij} en un documento específico y el peso global del término en la colección de documentos g_{i}. Los pesos anteriores pueden ser calculados de diversas formas como se muestran en las tablas a continuación.

Funciones de peso local más usadas.[editar]
Nombre Fórmula
Binaria l_{ij} = 1 si el término existe en el documento, 0 en otro caso
Frecuencia de término l_{ij} = \mathrm{tf}_{ij}, el número de ocurrencias del término i en el documento j
Log l_{ij} = \log(\mathrm{tf}_{ij} + 1)
Augnorm l_{ij} = \frac{\Big(\frac{\mathrm{tf}_{ij}}{\max_i(\mathrm{tf}_{ij})}\Big) + 1}{2}
Funciones de peso global más usadas.[editar]
Nombre Fórmula
Binaria g_i = 1
Normal g_i = \frac{1}{\sqrt{\sum_j \mathrm{tf}_{ij}^2}}
GfIdf g_i = \mathrm{gf}_i / \mathrm{df}_i, donde \mathrm{gf}_i es el número de veces que i ocurre en toda la colección, y \mathrm{df}_i es el número de documentos en los cuales ocurre el término i.
Idf g_i = \log_2 \frac{n}{1+ \mathrm{df}_i}
Entropy g_i = 1 + \sum_j \frac{p_{ij} \log p_{ij}}{\log n}, donde p_{ij} = \frac{\mathrm{tf}_{ij}}{\mathrm{gf}_i}

Resultados empíricos reportan que Log y Entropía , son funciones de peso que funcionan bien juntas. En otras palabras que cada elemento x_{ij} de C se calcula como:

g_i = 1 + \sum_j \frac{p_{ij} \log p_{ij}}{\log n}

x_{ij} = g_i \ \log (\mathrm{tf}_{ij} + 1)

Descomposición en Valores Singulares[editar]

El objetivo fundamental de ISL es encontrar una matriz C_k que constituya una aproximación a la matriz Términos-Documentos C. En esa aproximación se va a obtener información que no estaba disponible directamente en la matriz C, sino que se encontraba latente en esta. La matriz C_k debe cumplir las siguientes condiciones:

  • La norma de Frobenius de la diferencia con C_k debe ser mínima.
  • El rango debe ser al menos k, donde k es mucho menor que el rango de C. En este caso decimos que C_k es una aproximación de rango bajo.

La descomposición en valores singulares (SVD) puede ser usada para resolver el problema de la matriz de aproximación de rango bajo. Para esto se realiza el siguiente procedimiento que consta de tres pasos:

1- Hallar la SVD de la matriz Términos-Documentos. En otras palabras, siendo CR^{m*n} y rango r, se obtiene como resultado C = UEV^T , donde:
  • UR^{m*m} es una matriz cuyas columnas son vectores propios ortogonales de CC^T . Representa los términos en el espacio de términos.
  • VR^{n*n} es una matriz cuyas columnas son vectores propios ortogonales de C^TC. Representa los documentos en el espacio de documentos.
  • Los valores propios de CC^T son los mismos que los de C^TC.
  • ER^{m*n}, tal que E_{ii} es la raíz de los valores propios para 1ir y cero en otro caso.
2- Obtener de E la matriz E_k, remplazando por ceros los r-k menores valores propios en la diagonal de E.
3- Calculamos C_k = UE_kV^T. De esta forma se obtiene una aproximación de C de rango k.

Algo importante a tener en cuenta es que r debe ser lo suficientemente grande para evitar que se escape información relevante a la hora de hacer una consulta, pero a la vez debe ser lo suficientemente pequeño para permitir filtrar todos los detalles no relevantes.

Representación de las consultas[editar]

Una vez encontrada la matriz C_k se puede proceder a la recuperación de documentos. Para esto se realiza una transformación del vector de consulta q a su representación en el espacio ISL mediante:

qk = Ek-1UkTq

Se puede notar que la ecuación anterior no depende en ninguna medida de que q sea una consulta; este es simplemente un vector en el espacio de los términos. Esto significa que si tenemos una representación ISL de una colección de documentos, podemos agregar uno nuevo usando la ecuación antes planteada. Por supuesto, esto puede ser peligroso puesto que no se actualiza la frecuencia de los términos existentes en el sistema y no se adicionan los nuevos términos que posee el documento. La calidad del método ISL va en descenso a medida que se añaden nuevos documentos, por lo que eventualmente habría que volver a realizar los cálculos.

Función de Similitud[editar]

La más utilizada de las funciones de similitud entre los vectores d_j y q_i es el coseno del ángulo entre ambos vectores, o sea, d_j*q_i. Esta fórmula es no solo aplicable para calcular la similitud entre un documento y una consulta, sino también para computar la similitud entre dos documentos y entre dos términos. En el caso de los términos habría primero que convertir sus vectores representativos al espacio en que se está trabajando, es decir habría que obtener:

tk = Ek-1VkTt

Conveniencias del modelo ISL[editar]

La ISL como alternativa ante otros modelos tiene beneficios e inconvenientes que deberán tenerse en cuenta si se desea utilizar este modelo.

Ventajas[editar]

ISL resulta una buena aproximación de solución a dos de los principales problemas de las consultas booleanas: la sinonimia y la polisemia. Se puede utilizar para realizar una categorización automática de los documentos y particionarlos. Dado que es estrictamente matemático, es independiente del lenguaje, por lo tanto, puede extraer el contenido de cualquier documento independientemente del idioma en que está escrito sin estructuras auxiliares como los diccionarios y permite la búsqueda de términos de un idioma en documentos redactados en otro o varios idiomas, devolviendo resultados conceptualmente similares. Se adapta automáticamente a terminología cambiante y se ha comprobado que es muy tolerante a ruido. Maneja efectivamente datos diversos, ambiguos y contradictorios. Mientras menor sea la nueva dimensión mayor será el recobrado e increíblemente un valor en los cientos puede incrementar la precisión. Al igual que el modelo vectorial permite el macheo parcial y el ranking, además tiene en cuenta la dependencia entre términos.

Desventajas[editar]

Inicialmente, los mayores problemas de la ISL fueron la escalabilidad y el rendimiento, pues el costo temporal y espacial es relativamente alto con respecto a otras técnicas. Afortunadamente, la existencia en la actualidad de procesadores de alta velocidad y de memoria barata, han disminuido considerablemente esta situación. También resulta problemático determinar el valor óptimo de la nueva dimensión a utilizar, aunque experimentalmente se ha comprobado la efectividad de los valores propuestos previamente. Funciona mejor en aplicaciones donde haya poco solapamiento entre las consultas y los documentos. No hay formas cómodas de expresar negaciones de términos ni condiciones booleanas.

En resumen, ISL resuelve dos de las más problemáticas restricciones del Modelo Booleano, la sinonimia y la polisemia. También es usado para ejecutar categorización automática de documentos. La agrupación dinámica, basada en el contenido contextual de los documentos también es una tarea que puede ser lograda con ISL.

Referencias[editar]

  • Ricardo Baeza-Yates and Berthier Robeiro-Neto. Modern Information Retrieval. 1998.
  • Christopher Manning, Prabhakar Raghavan, and Hinrich Schuetze. An Introduction to Information Retrieval. Cambridge University Press, 2007.
  • Ed Greengrass. Information Retrieval: A Survey. 2000.